Lezione del 18/12/2008

Problemi di ottimizzazione. L'esistenza di un algoritmo polinomiale per un problema di ottimizzazione il cui corrispondente decisionale e' NP-Completo implica P=NP. Algoritmi di approssimazione polinomiale per problemi di ottimizzazione il cui corrispondente decisionale e' NP-Completo. Un algoritmo 2-approssimante per il problema del Min Vertex Cover.

Lezione del 16/12/2008

Il problema della copertura degli archi di un grafo tramite nodi (Vertex Cover o VC). NP-Completezza di Vertex Cover mediante riduzione da 3-soddisfacibilita'.

Avviso

E' stata aggiornata la raccolta degli esercizi svolti a lezione (link).

Lezione del 11/12/2008

Problemi computazionalmente intrattabili. Le classi di problemi P e NP. Congettura P diverso da NP. Problemi NP-Completi. Teorema di Cook-Levin: NP-Completezza del problema della soddisfacibilita' (senza dimostrazione). Riduzioni polinomiali ed NP-Completezza. Il problema della 3-soddisfacibilita' e' NP-Completo: riduzione da soddisfacibilita'.

Lezione del 09/12/2008

Riduzioni polinomiali e risultati negativi: Il problema del minimo insieme convesso non puo' essere risolto in tempo o(n log n). Esercizio: Un algoritmo di complessita' temporale lineare per il calcolo dell'albero dei cammini minimi quando i pesi degli archi sono interi e di numero costante.

Avviso: cambio aula martedi' 09/12/2008

A causa dei lavori di manutenzione delle aule la lezione di martedi 9 dicembre in aula 8.

Lezione del 04/12/2008

Problemi decisionali. Riduzioni polinomiali tra problemi decisionali. L'algoritmo per la verifica della forte connettivita' di un grafo diretto come riduzione polinomiale dal problema della verifica dell'esistenza di una arborescenza coprente. Proprieta' delle riduzioni polinomiali.

Avviso

E' stata aggiornata la libreria per la gestione dei grafi libgraphs.

Avviso

E' stata aggiornata la raccolta degli esercizi svolti a lezione (link).

Lezione del 02/12/2008

Implementazione in C degli algoritmi per il calcolo dei cammini minimi: Bellman-Ford; Dijkstra; Floyd-Warshall (vedere slides). Esercizio: proprieta' dell'insieme di archi costituito dall'unione dei minimi archi incidente ai nodi del grafo nel caso in cui tutti gli archi hanno peso diverso.