Il corso intende presentare le strutture discrete fondamentali enfatizzandone il ruolo nella definizione di modelli matematici di rilevanza biologica. Al termine dell’insegnamento, gli studenti acquisiranno quindi conoscenza di fondamenti della matematica discreta; nozioni e strumenti formali fondamentali per lo studio di problemi trattabili mediante calcolatore; metodi di rappresentazioni delle informazioni in ambito biologico; e saranno in grado di analizzare dati biologici di diversa natura (sequenze ge-nomiche, processi biologici, reti di interazioni biologiche) mediante concetti teorico-informazionali.
Parte1. Richiami di insiemistica e linguaggi:
Relazioni, ordinamenti, quozienti ed equivalenze, equipotenza; sistemi numerici; successioni numeriche, successione di Fibonacci (sezione aurea, teorema di Binet, e applicazioni in natura); multinsiemi, sequenze, stringhe, e linguaggi.
Parte2. Funzioni discrete, dinamiche e serie temporali:
Processi metabolici; modello epidemiologico SIR; progressione geometrica e modello (neutrale ed esteso) di Malthus (eventualmente soggetto a vincoli); modelli non lineari di crescita di popolazioni biologiche in presenza di competizione: la mappa logistica; cenni di sistemi dinamici (analisi di stabilita', orbite periodiche e regimi caotici).
Parte3. Elementi di Linguaggi formali e automi:
Grammatiche e linguaggi; pattern ed espressioni regolari; automi a stati finiti; macchine di Turing; Decidibilita', semidecidibilita' ed indecidibilita’.
Parte4. Grafi e Alberi:
Grafi orientati e grafi non-orientati e loro rappresentazioni; foreste e alberi; alberi ricoprenti; problemi di connettività; induzione strutturale su grafi;
Parte5. Elementi di Teoria dell'informazione e compressione dati:
Sorgenti di informazione; misure per la quantità di informazione prodotta e scambiata da una sorgente; entropia; mutua informazione; divergenza informazionale (Kullback Leibler); misure di similarità teorico informazionali; codici UD e prefissi; codifica ottima; uso di compressori per misurare similarità tra sequenze
| Autore | Titolo | Casa editrice | Anno | 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 |
L'esame consiste in un colloquio orale volto a verificare la comprensione degli argomenti presentati durante il corso e la capacità di applicare le tecniche e gli strumenti analitici presentati.
