Lezioni 1 e 2 - 13/1/2004

Algoritmi (vedi dispensa (288 K in pdf )

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

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

Lezioni 3 e 4 - 14/1/2004

Complessità di problemi
• Esempi
  • Ricerca dell'elemento massimo
  • Ricerca di un elemento
  • Determinazione della connessione di un grafo

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

Lezioni 5 e 6 - 15/1/2004

• Torre di Hanoi
• Calcolo dei numeri di Fibonacci

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

Lezioni 7 e 8 - 20/1/2004

• Problemi di decisione
• Classe P

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

Lezioni 9 e 10 - 21/1/2004

• Trasformazioni di problemi
• Classe NP
• Problemi NP-completi

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

Lezioni 11 e 12 - 22/1/2004

• elenco di problemi in P e in NP-c
• parallelismo

Strutture dati (vedi appunti (76 K in pdf )

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

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

Lezioni 13 e 14 - 27/1/2004

• code di priorità

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

Lezioni 15 e 16 - 28/1/2004

• alberi binari

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

Lezioni 17 e 18 - 29/1/2004

• alberi binari (prosecuzione)

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

Lezioni 19 e 20 - 3/2/2004

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

• Inserzione
• Quicksort

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

Lezioni 21 e 22 - 4/2/2004

• Mergesort
• Heapsort

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

Lezioni 23 e 24 - 5/2/2004

Hashing

• Indirizzamento diretto
• Risoluzione delle collisioni

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

Lezioni 25 e 26 - 10/2/2004

Programmazione dinamica

• Principio di ottimalità
• Cammini minimi e massimi
• Equazione di Bellman
• Algoritmo di Bellman-Ford

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

Lezioni 27 e 28 - 11/2/2004

• Algoritmo di Dijkstra
• Algoritmo di Floyd-Warshall

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

Lezioni 29 e 30 - 12/2/2004

• Confronto di stringhe

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

Lezioni 31 e 32 - 17/2/2004

• esercitazione in laboratorio

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

Lezioni 33 e 34 - 18/2/2004

Altri algoritmi su grafi

• Minimo albero di supporto (Kruskal, Prim, Boruvka)
  • strutture union-find

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

Lezioni 35 e 36 - 19/2/2004

• Max flow - min cut
  • min cut probabilistico (vedi appunti 32 K in pdf)

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

Lezioni 37 e 38 - 2/3/2004

• Assegnamento
  • cammini aumentanti
  • Teorema di König
  • fomulazione come PL

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

Lezioni 39 e 40 - 3/3/2004

• Accoppiamento
  • fomulazione come PL
  • piani di taglio

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

Lezioni 41 e 42 - 4/3/2004

• Esempi di uso di PL
• Problema duale per l'assegnamento

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

Lezioni 43 e 44 - 9/3/2004

Programmazione lineare

• Problema primale e duale
• Applicazione alla Programmazione dinamica

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

Lezioni 45 e 46 - 10/3/2004

Problemi NP-completi

• TSP
• Insiemi stabili

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

Lezioni 47 e 48 - 11/3/2004

• knapsack
  • come programmazione dinamica
• PL intera , branch-and-bound

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

Lezioni 49 e 50 - 12/3/2004

• PL: generazione di colonne
  • esempio bin packing