Informational Methods (2020/2021)

Course code
4S00995
Name of lecturers
Ferdinando Cicalese, Giuditta Franco
Coordinator
Ferdinando Cicalese
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Location
VERONA
Period
II semestre dal Mar 1, 2021 al Jun 11, 2021.

Lesson timetable

Go to lesson schedule

Learning outcomes

The course introduces the fundamental discrete structures by emphasizing their use in the definition of mathematical models of biological relevance. The students will acquire knowledge about the es-sentials of discrete mathematics; formal notions and methods for studying problems by means of computers; methods for representation of biological information; and they will be able to apply such knowledge to analyze biological data of different types (genomic sequences, biological processes, networks of biological interactions) by means of information theoretic concepts.

Syllabus

Part1. Basics of set theory and languages
Relations, equivalences; numerical systems; Fibonacci series (golden ratio, Binet's theorem and applications); multisets, sequences, strings, and languages.

Part2. Discrete functions, dynamics and temporal series:
Metabolic processes; the epidemiological model SIR; geometric progression and Malthus model; population growth models (non linear); elements of dynamical systems

Part3. Elements of computability (formal languages and automata):
Formal grammars and languages; patterns and regular expressions; finite state automata; Turing machines; decidability semidecidability and undecidability.

Part4. Basics of graph theory:
Directed and undirected Graphs and their representations; forests and trees; spanning trees; connectivity problems; structural induction on graphs.

Part5. Elements of Information Theory and compression
Information sources; information measures, entropy, mutual information and informational divergence; information theoretic similarity and dissimilarity measures; uniquely decodable codes and prefix codes; optimal codes; compression based sequence similarity.

Reference books
Author Title Publisher Year ISBN Note
Stein, Drysdale, Bogart Discrete Mathematics for Computer Scientists Pearson 2011 978-0-13-137710-3
Michael Sipser Introduction to the Theory of Computation PWS 1997 053494728X
V. Manca Linguaggi e Calcoli -- principi matematici del coding bollati boringhieri 2019

Assessment methods and criteria

The exam will be an oral discussion to verify that the student has reached a sufficent level of fluency in the topics studied and the ability to employ the techniques and the aanalytical tools presented in class.