Lezioni 1 e 2 - 8/1/2008

Algoritmi (vedi dispensa (194 K in pdf )

• Definizione
• Misura della complessità
• Classi di Complessità

----------------------------------------------------------------

Lezioni 3 e 4 - 9/1/2008

• Esempi
  • Algoritmo di Euclide per il MCD
  • Calcolo dei numeri di Fibonacci
  • Determinazione della connessione di un grafo

----------------------------------------------------------------

Lezioni 5 e 6 - 10/1/2008

Complessità di problemi

• Problemi di decisione
• Classe P
• Classe NP

----------------------------------------------------------------

Lezioni 7 e 8 - 15/1/2008

• Trasformazioni di problemi

----------------------------------------------------------------

Lezioni 9 e 10 - 16/1/2008

• Problemi NP-completi

---------------------------------------------------------------

Lezioni 11 e 12 - 17/1/2008

• elenco di problemi in P e in NP-c
• algoritmi randomizzati

----------------------------------------------------------------

Lezioni 13 e 14 - 29/1/2008

Strutture dati (vedi appunti (173 K in pdf ))

• Specifica di una struttura dati
• Implementazione di una struttura dati
• Strutture dati elementari
  • pile
  • code
  • code di priorità (come vettori non ordinati)
  • code di priorità (come vettori ordinati)

----------------------------------------------------------------

Lezioni 15 e 16 - 30/1/2008

• alberi binari: definizioni
  • profondità media

----------------------------------------------------------------

Lezioni 17 e 18 - 31/1/2008

• complessità della costruzione di un albero binario
• operazioni sugli alberi binari

----------------------------------------------------------------

Lezioni 19 e 20 - 5/2/2008

• visite inorder, preorder e postorder

--------------------------------------------------------------

Lezioni 21 e 22 - 6/2/2008

Algoritmi di Ordinamento (vedi appunti (132 K in pdf ))

• limitazione inferiore per ordinamenti con confronto di chiavi
• Inserzione
• Bubblesort
• Quicksort

----------------------------------------------------------------

Lezioni 23 e 24 - 7/2/2008

• Mergesort
• Heapsort

---------------------------------------------------------------

Lezioni 25 e 26 - 12/2/2008

Algoritmi di ordinamento lineare (vedi appunti (56 K in pdf ))

• Countsort
• Bucket sort
• Radix sort

----------------------------------------------------------------

Lezioni 27 e 28 - 13/2/2008

Programmazione dinamica (vedi appunti (384 K in pdf ))

• Principio di ottimalità
• Cammini minimi e massimi
• Equazione di Bellman
• Algoritmo per grafi aciclici
• Algoritmo di Bellman-Ford
• Cammini minimi con costi non-negativi. Algoritmo di Dijkstra.
• Algoritmo di Floyd-Warshall

----------------------------------------------------------------

Lezioni 29 e 30 - 14/2/2008

• Allineamento di stringhe
• Knapsack

----------------------------------------------------------------

Lezioni 31 e 32 - 19/2/2008

• Partizione

Altri algoritmi su grafi

• Minimo albero di supporto (Kruskal) (vedi appunti 1884 K in pdf)
• strutture union-find

---------------------------------------------------------------

Lezioni 33 e 34 - 20/2/2008

Approfondimenti su programmazinoe dinamica

---------------------------------------------------------------

Lezioni 35 e 36 - 21/2/2008

• Min cut (vedi appunti 273 K in pdf)
  • min cut probabilistico

---------------------------------------------------------------

Lezione 37 e 38 - 26/2/2008

Programmazione lineare (vedi appunti 180 K in pdf)

• PL per accoppiamento e assegnamento

----------------------------------------------------------------

Lezioni 39 e 40 - 27/2/2008

• Problema duale
• Proprietà geometriche della PL

---------------------------------------------------------------

Lezioni 41 e 42 - 28/2/2008 -

• Insiemi stabili; TSP
• branch-and-bound; branch-and-cut

----------------------------------------------------------------

Lezioni 43 e 44 - 4/3/2008

Esempi di modelli in biologia computazionale (file ppt)

• allineamento multiplo come non crossing matching

----------------------------------------------------------------

Lezioni 45 e 46 - 6/3/2008

Esempi di modelli in biologia computazionale

• allineamento multiplo tramite routing cost trees
• allineamento strutturale

----------------------------------------------------------------

Lezioni 47 e 48 - 12/3/2008

Esempi di modelli in biologia computazionale

• ricostruzione di aplotipi

Conclusione del corso