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.
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.
| 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 |
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.
