Lezioni 1 e 2 - 3/03/2009

Algoritmi (vedi dispensa (194 K in pdf )

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

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

Lezioni 3 e 4 - 10/03/2009

• Esempi
  • Determinazione della connessione di un grafo
  • Algoritmo di Euclide per il MCD

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

Lezioni 5 e 6 - 11/03/2009

Complessità di problemi

• Problemi di decisione
• Classe P
• Classe NP
• Trasformazioni di problemi
• Problemi NP-completi (definizione)

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

Lezioni 7 e 8 - 17/03/2009

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

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

Lezioni 9 e 10 - 18/03/2009

• algoritmi randomizzati (min cut)

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 11 e 12 - 24/03/2009

• alberi binari: definizioni
• operazioni sugli alberi binari
• visita inorder

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

Lezioni 13 e 14 - 25/03/2009

• visite preorder e postorder
• complessità della costruzione di un albero binario
• profondità media

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

Lezioni 15 e 16 - 31/03/2009

• profondità media (numeri armonici)

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

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

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

Lezione 17 - 1/04/2009

• Quicksort

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

Lezioni 18 e 19 - 7/04/2009

• Mergesort
• Heapsort

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

Lezioni 20 e 21 - 8/04/2009

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

• Countsort
• Bucket sort
• Radix sort

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

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

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

Lezioni 22 e 23 - 15/04/2009

• Algoritmo per grafi aciclici
• Algoritmo di Bellman-Ford
• Cammini minimi con costi non-negativi. Algoritmo di Dijkstra.

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

Lezioni 24 e 25 - 21/04/2009

• implementazione dell'algoritmo di Dijkstra.
• Algoritmo di Floyd-Warshall
• Allineamento di stringhe

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

Lezioni 26 e 27 - 22/04/2009

• Allineamento di stringhe (esempio al calcolatore)
• Prodotto di matrici

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

Lezioni 28 e 29 - 28/04/2009

• Knapsack (01 e intero)
• Partizione

Altri algoritmi su grafi

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

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

Lezioni 30 e 31 - 29/04/2009

• Minimo albero di supporto: Prim e Boruvka
• Max flow
• Min cut (vedi appunti 273 K in pdf)

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

Lezioni 32 e 33 - 5/05/2009

• Assegnamento, accoppiamento, coperture e impaccamenti (vedi appunti 768 K in pdf)
• PL per accoppiamento e assegnamento

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

Lezione 34 e 35 - 6/05/2009

Programmazione lineare (vedi appunti 180 K in pdf)

• Proprietà geometriche della PL
• Problema duale
• Cenni algoritmo del simplesso

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

Lezioni 36 e 37- 13/05/2009

• Programmazione lineare intera
• branch-and-bound; branch-and-cut

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

Lezioni 38 e 39- 19/05/2009

• esempi al calcolatore di branch-and-bound e branch-and-cut
• generazione di odd hole inequalities
• TSP

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

Lezioni 40 e 41- 20/05/2009

• TSP
• Bin packing

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

Lezioni 42 e 43 - 26/05/2009

Esempi di modelli in biologia computazionale (file ppt)

• allineamento come
  • cammino hamiltoniano
  • non crossing matching

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

Lezioni 44, 45 e 46 - 27/05/2009

Esempi di modelli in biologia computazionale

• allineamento multiplo tramite routing cost trees
• allineamento strutturale
• il problema degli aplotipi minimi

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