Algoritmi e Strutture Dati II

                                     Programma a.a. 2000-2001
 
 

Testi:

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest "Introduzione agli Algoritmi", Vol.2, Jackson Libri,1994.

2. A.A. Bertossi "Strutture Algoritmi Complessità",ECIG
 
 

Algoritmi elementari su grafi. Algoritmi generici di visita. Visita in ampiezza e in profondità. Ordinamento topologico. Componenti fortemente connesse. ([1] Cap. 23 e Appunti)

Alberi di copertura minimi. Algoritmi di Kruskal e di Prim. ([1] Cap. 24)

Cammini minimi con sorgente singola. Rilassamento. Algoritmi di Dijkstra e Bellman-Ford. Cammini minimi con sorgente singola in grafi orientati aciclici. ([1] Cap. 25, fino a 25.4 compreso)

Cammini minimi tra tutte le coppie. Moltiplicazione di matrici. Algoritmo di Floyd-Warshall. Chiusura transitiva. ([1] Cap. 26, fino a 26.2 compreso)

Problemi NP-Completi. Non determinismo. Le classi di complessità P e NP. NP-completezza e riducibilità. Problemi NP-completi. ([2] Cap. 19, 20, 21)