Infobiotica (2006/2007)

Obiettivi formativi

Il corso intende fornire gli strumenti formali di base per la rappresentazione discreta dell'informazione biologica e per l'analisi algoritmica di processi biologici. Il programma si articola in tre parti: i) strutture matematiche discrete, ii) linguaggi, grammatiche e automi, iii) algoritmi DNA.

STRUTTURE DISCRETE:

- Numeri naturali e sistemi numerici
- Induzione e Successioni
- La successione dei primi e la successione di Fibonacci
- Stringhe e sequenze nucleotidiche
- Alberi e sistemi a membrane
- Insiemi e relazioni
- Grafi e reti biologiche
- Funzioni e popolazioni molecolari
- Variabili e proposizioni
- Schemi e formule combinatorie

LINGUAGGI, GRAMMATICHE E AUTOMI:

- Linguaggi e operazioni sui linguaggi
- Grammatiche e accrescimenti biologici
- Pattern lineari
- Automi a stati finiti
- Espressioni regolari
- Calcolabilita', semidecidibilita' e decidibilita'
- Macchina di Turing e tesi di Church

ALGORITMI DNA:

- Struttura e rappresentazione del DNA
- Operazioni DNA di base
- Esperimento di Adleman
- SAT e algoritmo di Lipton
- Bioalgoritmi per risolvere SAT
- Estrazione e ricombinazione DNA con XPCR

Esame orale