Lezioni 1 e 2 - 17/04/2007

Algoritmi (vedi dispensa (194 K in pdf )

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

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

Lezioni 3 e 4 - 18/04/2007

Complessità di problemi

• Esempi
  • somme e moltiplicazioni di numeri
  • Algoritmo di Euclide per il MCD

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

Lezioni 5 e 6 - 19/04/07

• Torre di Hanoi
• Calcolo dei numeri di Fibonacci
• Determinazione della connessione di un grafo

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

Lezioni 7 e 8 - 24/04/2007

• Determinazione della connessione di un grafo

• Problemi di decisione
• Classe P
• Classe NP

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

Lezioni 9 e 10 - 26/04/2007

• Trasformazioni di problemi
• Problemi NP-completi
• elenco di problemi in P e in NP-c

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

Lezioni 11 e 12 - 2/05/2007

• algoritmi randomizzati

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

• Specifica di una struttura dati
• Implementazione di una struttura dati
• Strutture dati elementari
  • pile
  • code

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

Lezioni 13 e 14 - 3/05/2007

• code di priorità (come vettori non ordinati)
• code di priorità (come vettori ordinati)
• alberi binari
  • definizioni

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

Lezioni 15 e 16 - 8/05/2007

• visite inorder, preorder e postorder
• operazioni sugli alberi binari

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

Lezioni 17 e 18 - 9/05/2007

• profondità media
• complessità della costruzione di un albero binario

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

• limitazione inferiore per ordinamenti con confronto di chiavi

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

Lezioni 19 e 20 - 10/05/2007

• Inserzione
• Bubblesort
• Quicksort
• Mergesort

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

Lezioni 21 e 22 - 22/05/2007

• Heapsort

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

• Countsort

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

Lezioni 23 e 24 - 23/05/2007

• Bucket sort
• Radix sort

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

• Principio di ottimalità
• Cammini minimi e massimi
• Equazione di Bellman

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

Lezioni 25 e 26 - 23/05/2007

• Algoritmo per grafi aciclici
• Algoritmo di Bellman-Ford

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

Lezioni 27 e 28 -24/05/2007

• Cammini minimi con costi non-negativi. Algoritmo di Dijkstra.
• Algoritmo di Floyd-Warshall

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

Lezioni 29 e 30 - 29/05/2007

• Allineamento di stringhe
• Knapsack

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

Lezioni 31 e 32 - 30/05/2007

• Partizione

Altri algoritmi su grafi

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

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

Lezioni 33 e 34 - 30/05/2007

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

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

Lezione 35 e 36 - 31/05/2007

Programmazione lineare (vedi appunti 180 K in pdf)

• PL per accoppiamento e assegnamento

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

Lezioni 37 e 38 - 5/06/07

• Problema duale
• Proprietà geometriche della PL

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

Lezioni 39 e 40 - 6/06/07

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

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

Lezioni 41 e 42 - 7/06/07

• TSP

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

Lezioni 43 e 44 - 12/06/2007

Esempi di modelli in biologia computazionale (file ppt)

• allineamento multiplo come non crossing matching

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

Lezioni 45 e 46 - 13/06/2007

Esempi di modelli in biologia computazionale

• allineamento multiplo tramite routing cost trees
• allineamento strutturale

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

Lezioni 47 e 48 - 14/06/2007

Esempi di modelli in biologia computazionale

• ricostruzione di aplotipi

Conclusione del corso