Metodi informazionali (2020/2021)

Codice insegnamento
4S00995
Docenti
Ferdinando Cicalese, Giuditta Franco
Coordinatore
Ferdinando Cicalese
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
II semestre dal 1-mar-2021 al 11-giu-2021.

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

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.

Programma

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

Testi di riferimento
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

Modalità d'esame

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.