Lezioni 1 e 2 - 19/4/2006

Algoritmi (vedi dispensa (288 K in pdf )

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

Complessità di problemi

• Esempi
  • somme e moltiplicazioni di numeri

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

Lezioni 3 e 4 - 20/4/2006

• Ricerca dell'elemento massimo
• Ricerca di un elemento
• Determinazione della connessione di un grafo

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

Lezioni 5 e 6 - 26/4/2006

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

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

Lezioni 7 e 8 - 27/4/2006

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

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

Lezioni 9 e 10 - 2/5/2006

• 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

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

Lezioni 11 e 12 - 3/5/2006

• code di priorità (come vettori non ordinati)
• code di priorità (come vettori ordinati)

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

Lezioni 13 e 14 - 4/5/2006

• alberi binari
  • visite inorder, preorder e postorder

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

Lezioni 15 e 16 - 9/5/2006

• operazioni sugli alberi binari
• profondità media

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

Lezioni 17 e 18 - 10/5/2006

• complessità della costruzione di un albero binario

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

• limitazione inferiore per ordinamenti con confronto di chiavi

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

Lezioni 19 e 20 - 11/5/2006

• Inserzione
• Bubblesort
• Quicksort

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

Lezioni 21 e 22 - 16/5/2006

• Mergesort
• Heapsort

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

Lezioni 23 e 24 - 17/5/2006

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

• Countsort
• Radix sort

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

Lezioni 25 e 26 - 18/5/2006

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

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

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

Lezioni 27 e 28 - 23/5/2006

Esercitazioni in laboratorio (programmi in c)

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

Lezioni 29 e 30 - 24/5/2006

Esercitazioni in laboratorio (programma in c per bst)

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

Lezioni 31 e 32 - 25/5/2006

• Allineamento di stringhe

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

Lezioni 33 e 34 - 30/5/2006

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

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

Lezioni 35 e 36 - 31/5/2006

• knapsack e partizione

Altri algoritmi su grafi

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

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

Lezione 37e 38 - 6/6/2006

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

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

Lezioni 39 e 40 - 7/6/2006

Programmazione lineare (vedi appunti 180 K in pdf)

• PL per accoppiamento e assegnamento

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

Lezioni 41 e 42 - 8/6/2006

• Problema duale
• Proprietà geometriche della PL
• Insiemi stabili

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

Lezioni 43 e 44 - 13/6/2006

• TSP

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

Lezioni 45 e 46 - 14/6/2006

Esempi di modelli in biologia computazionale (file ppt)

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

Lezioni 47 e 48 - 15/6/2006

Esempi di modelli in biologia computazionale