Lezioni 1 e 2 - 11/1/2005

Algoritmi (vedi dispensa (288 K in pdf )

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

Complessità di problemi

• Esempi
  • Ricerca dell'elemento massimo

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

Lezioni 3 e 4 - 12/1/2005

• Ricerca di un elemento
• Determinazione della connessione di un grafo

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

Lezioni 5 e 6 - 13/1/2005

• Torre di Hanoi
• Calcolo dei numeri di Fibonacci
• Algoritmo di Euclide per il MCD

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

Lezioni 7 e 8 - 18/1/2005

• Problemi di decisione
• Classe P
• Trasformazioni di problemi

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

Lezioni 9 e 10 - 19/1/2005

• Classe NP
• Problemi NP-completi

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

Lezioni 11 e 12 - 20/1/2005

• elenco di problemi in P e in NP-c

Strutture dati (vedi appunti (952 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)

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

Lezioni 13 e 14 - 25/1/2005

• code di priorità (come vettori ordinati)
• alberi binari
  • visite inorder, preorder e postorder

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

Lezioni 15 e 16 - 26/1/2005

• operazioni sugli alberi binari
• profondità media

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

Lezioni 17 e 18 - 27/1/2005

• complessità della costruzione di un albero binario

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

• Inserzione
• Bubblesort

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

Lezioni 19 e 20 - 1/2/2005

• Quicksort
• Mergesort

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

Lezioni 21 e 22 - 2/2/2005

• Heapsort

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

Lezioni 23 e 24 - 3/2/2005

Algoritmi di ordinamento lineare

• Hashing
• Countsort
• Radix sort
• Selezione della mediana

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

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

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

Lezioni 25 e 26 - 8/2/2005

• Algoritmo di Bellman-Ford

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

Lezioni 27 e 28 - 9/2/2005

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

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

Lezioni 29 e 30 - 10/2/2005

• Confronto di stringhe
• knapsack e partizione

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

Lezioni 31 e 32 - 15/2/2005

Altri algoritmi su grafi

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

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

Lezioni 33 e 34 - 16/2/2005

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

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

Lezioni 35 e 36 - 17/2/2005

• Esempi al calcolatore
• Assegnamento (vedi appunti 768 K in pdf)
  • cammini aumentanti
  • fomulazione come PL

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

Lezione 37 - 22/2/2005

Programmazione lineare (vedi appunti 180 K in pdf)

• Proprietà geometriche della PL

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

Lezioni 38 e 39 - 23/2/2005

• PL per accoppiamento e assegnamento
• Problema duale come copertura nodi

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

Lezioni 40 e 41 - 24/2/2005

• Problema duale come problema economico
• Problema dell'accoppiamento con PL e piani di taglio

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

Lezioni 42 e 43 - 1/3/2005

Problemi NP-completi

• Insiemi stabili
• TSP

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

Lezioni 45 e 45 - 2/3/2005

• PL intera , branch-and-bound

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

Lezioni 46 e 47 - 2/3/2005

• PL: generazione di colonne
  • esempio bin packing

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

Lezioni 48 e 49 - 3/3/2005

Esempi di modelli in biologia computazionale