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.

Lezione del 27/11/2008

Esercizio: Un albero dei cammini minimi di un grafo e' ancora un albero dei cammini minimi dello stesso grafo nel caso in cui a tutti gli archi viene sommata la stessa costante? Cammini minimi tra tutte le coppie di nodi di un grafo orientato con cicli di costo non negativo: cammini minimi k-vincolati; algoritmo di Floyd-Warshall per il calcolo di tutte le distanze minime e cammini minimi.

Lezione del 25/11/2008

Cammini minimi su grafi con pesi non negativi: Condizione di Dijkstra sulla appartenenza di un arco (u,v) al cammino minimo da s a v; Algoritmo di Dijkstra ed implementazione con heap, correttezza e complessita' computazionale O(|E|log |V|). Esercizio: Un MST di un grafo e' ancora un MST nel caso in cui a tutti gli archi viene sommata la stessa costante? Ed nel caso di un albero dei cammini minimi?

Avviso

Nella sezione "Materiale didattico" di questo blog e' stato pubblicato un documento contenente la raccolta degli esercizi svolti a lezione e relativa soluzione.

Lezione del 20/11/2008

Cammini minimi di grafi diretti pesati: condizione necessaria e sufficiente affinche' un arco faccia parte di un cammino minimo; algoritmo di Bellman-Ford per il calcolo dell'albero dei cammini minimi nel caso in cui il grafo non contenga cicli negativi; correttezza e complesita' computazionale dell'algoritmo di Bellman-Ford.

Esercitazioni del 30/10 e 4/11/2008 (Tenute da Jacopo Avati)

Implementazione in C degli algoritmi per connettivita', connettivita' forte e calcolo componenti connesse (vedere slides). Elenco esercizi svolti:

* Dato un grafo orientato con pesi strettamente positivi, si costruisce un nuovo grafo che ha gli stessi nodi ma come archi solo quegli (u,v) che, fissato un nodo s, rispettano la legge d(s,u)+w(u,v)=d(s,v) (dove d(i,j) e' la distanza di peso minimo da i a j). Si dimostri che il secondo grafo e' aciclico.

* Dato un grafo non orientato con pesi tutti diversi, dimostrare che il secondo mst non e' unico.

* esercizio 2 dell'appello del 10/06/2008.

* esercizio 2 dell'appello del 1/2/2007.

* esercizio 3 dell'appello del 1/2/2007.