Calendario delle lezioni - A.A. 2009-2010

Data Aula Inizio Fine Argomento
Mer 30 Settembre B3 8.30 10.30 Introduzione al corso. Relazioni fra Informatica e Biologia: Bioinformatica e Calcolo Naturale. La nozione di stringa.
Gio 1 Ottobre B3 13.30 15.30 Stringhe e grafi. La nozione di algoritmo.
Ven 2 Ottobre B3 13.30 15.30 Strutture di controllo: sequenza, selezione e iterazione (WHILE-DO, REPEAT-UNTIL). Variabili e assegnamenti.
Mer 7 Ottobre B3 8.30 10.30 Esercizio. Il ciclo FOR. Analisi di algoritmi: le risorse tempo e spazio.
Gio 8 Ottobre B3 13.30 15.30 SOSPESA per partecipazione a Career Day di Ateneo.
Ven 9 Ottobre B3 13.30 15.30 Definizione di complessità (in tempo) di un algoritmo. Le espressioni asintotiche. Algoritmi polinomiali ed esponenziali; efficienza.
Mer 14 Ottobre B3 8.30 10.30 Le classi P e NP. I problemi NP-completi. Il Problema del Percorso di Hamilton.
Gio 15 Ottobre B3 13.30 15.30 Il Problema del Commesso Viaggiatore. Introduzione all'allineamento di sequenze: allineamenti globali, locali, semiglobali, multipli. La nozione di allineamento.
Ven 16 Ottobre B3 13.30 15.30 La nozione di somiglianza. Tecniche di costruzione di algoritmi: programmazione dinamica e divide et impera. Applicazione della programmazione dinamica all'allineamento fra due sequenze.
Mer 21 Ottobre B3 8.30 10.30 L'algoritmo per l'allineamento globale ottimale di 2 sequenze: costruzione della matrice di somiglianza.
Gio 22 Ottobre B3 13.30 15.30 Ricostruzione dell'allineamento globale ottimale fra due sequenze a partire dalla matrice di somiglianza. Esercizi. Pseudocodice dell'algoritmo "Similarity".
Ven 23 Ottobre B3 13.30 15.30 ANNULLATA causa sciopero del trasporto pubblico.
Mer 28 Ottobre B3 8.30 10.30 Analisi di complessità dell'algoritmo "Similarity", e stima della complessità dell'algoritmo per la ricostruzione dell'allineamento globale. L'algoritmo di allineamento locale fra 2 sequenze. Cenni sull'algoritmo di allineamento semiglobale.
Gio 29 Ottobre B3 13.30 15.30 Scelta del sistema di punteggio; funzioni additive e subadditive. Allineamento multiplo di sequenze: stima della complessità dell'algoritmo basato sulla programmazione dinamica. Tecniche euristiche: allineamento a stella.
Ven 30 Ottobre B3 13.30 15.30 DNA Computing: l'esperimento di L. Adleman per la soluzione del problema del percorso di Hamilton.
Mer 4 Novembre B3 8.30 10.30 Il problema di protein folding: metodi e criteri per la definizione di un modello computazionale. Il modello reticolare HP.
Gio 5 Novembre B3 13.30 15.30 Gli algoritmi genetici.
Ven 6 Novembre B3 13.30 15.30 Cenni al teorema degli schemi per gli AG. Un'applicazione degli algoritmi genetici al problema di protein folding.