Lezioni 1 e 2 -

Algoritmi (vedi dispensa (194 K in pdf )

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

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

Lezioni 3 e 4 -

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

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

Lezioni 5 e 6 -

Complessità di problemi

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

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

Lezioni 7 e 8 -

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

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

Lezioni 9 e 10 -

• 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 -

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

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

Lezioni 13 e 14 -

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

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

Lezioni 15 e 16 -

• 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 e 18 -

• Quicksort

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

Lezioni 19 e 20 -

• Mergesort
• Heapsort

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

Lezioni 21 e 22 -

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 23 e 24 -

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

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

Lezioni 25 e 26 -

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

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

Lezioni 27 e 28 -

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

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

Lezioni 29 e 30 -

• Knapsack (01 e intero)
• Partizione

Altri algoritmi su grafi

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

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

Lezioni 31 e 32 -

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

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

Lezioni 33 e 34 -

• Assegnamento, accoppiamento, coperture e impaccamenti

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

Lezione 35 e 36 -

Programmazione lineare (vedi appunti 180 K in pdf)

• PL per accoppiamento e assegnamento

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

Lezioni 37 e 38 -

• Problema duale
• Proprietà geometriche della PL

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

Lezioni 39 e 40-

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

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

Lezioni 41 e 42 -

Esempi di modelli in biologia computazionale (file ppt)

• allineamento multiplo come non crossing matching

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

Lezioni 43 e 44 -

Esempi di modelli in biologia computazionale

• allineamento multiplo tramite routing cost trees
• allineamento strutturale

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

Lezioni 45 e 46 -

Esempi di modelli in biologia computazionale

• ricostruzione di aplotipi

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

Lezioni 47 e 48 -

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

Lezioni 49 e 50 -