Obiettivi formativi

Il corso intende presentare le strutture discrete fondamentali enfatizzandone il ruolo nella definizione di modelli matematici di rilevanza biologica. Nella prima parte, dopo una introduzione delle strutture discrete basilari, si analizzano i sistemi numerici, le rappresentazioni dei numeri e il principio di induzione strutturale e i principali schemi combinatori. Quindi si introducono i concetti di base dei linguaggi formali e degli automi e le nozioni di decidibilità, calcolabilità, semidecidibilità.

Conoscenza e capacità di comprensione: Gli studenti acquisiranno 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.

Capacità di applicare conoscenza e comprensione: Gli studenti saranno in grado di analizzare dati biologici di diversa natura (sequenze genomiche, processi biologici, reti di interazioni biologiche) mediante concetti teorico-informazionali;

Programma

Strutture discrete: insiemi, multinsiemi, sequenze, stringhe, operazioni, relazioni, funzioni, variabili, parentesi ed espressioni. Numeri e induzione: sistemi numerici, rappresentazioni di numeri, dimostrazioni per induzione, definizioni e induttive di importanti successioni numeriche. Induzione strutturale su stringhe, alberi e grafi. Schemi ricorrenti. Cenni ai linguaggi logici del primo ordine (termini, formule ed interpretazioni). Elementi di combinatoria: allocazioni e partizioni, coefficienti binomiali e multinomiali. Multinsiemi, Partizioni di insiemi e interi. Linguaggi, grammatiche e automi: pattern ed espressioni regolari, gerarchia di Chomsky, automi a stati finiti. Automi di calcolo e macchina di Turing. Decidibilita', semidecidibilita' ed indecidibilita'.

Modalità d'esame

Esame scritto ed orale.

Per superare l'esame scritto lo studente deve essere in grado di usare correttamente il formalismo appreso durante il corso descrivendo brevemente le soluzioni ai quesiti posti dal testo di esame.

L'esame orale parte dalla verifica delle soluzioni proposte, in cui lo studente deve giustificare quanto scritto ed eventualmente chiarire i passaggi non chiari. Durante il colloquio verranno posti delle domande specifiche sul programma svolto, intese ad appurare la comprensione dei concetti fondamentali che il corso si prefigge di trasmettere.

Materiale didattico
Manca, V. - Infobiotics. Springer, 2013 (Capitoli 5, 6, 7).
Manca V. - Vademecum all'Esame di Metodi Informazionali (con lista delle definizioni e dei teoremi più 100 esercizi svolti).