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.

Lezione del 18/11/2008

Esercizio: il minimo albero ricoprente ha il minimo arco di peso massimo tra tutti gli alberi coprenti. Cammini minimi in grafi diretti: definizioni, prime proprieta' per grafi senza cicli negativi; albero dei cammini minimi: definizione e dimostrazione di esistenza.

Lezione del 13/11/2008

Implementazione nel linguaggio C della struttura dati Union-Find (slides), dell'algoritmo di Kruskal (slides) e dell'algoritmo di Prim (slides). Esercizio: Un grafo non diretto, connesso con pesi sugli archi tutti diversi ammette un unico minimo albero coprente.

Lezione del 11/11/2008

Algoritmo di Prim per il calcolo del minimo albero coprente: Correttezza, Implementazione non efficiente; Implementazione efficiente dell'algoritmo con tempo di calcolo O(|E| log |V|) che utilizza la struttura dati Heap.

Lezione del 06/11/2008

Implementazione ingenua e non efficiente dell'algoritmo di Kruskal; Struttura dati Union-Find; Utilizzo della struttura dati Union-Find per una implementazione efficiente dell'algoritmo di Kruskal con tempo di calcolo O(|E| log |V|).

Avviso

La lezione di oggi, 30 ottobre, non si e' tenuta poiche' il Consiglio di Facoltà ha disposto una giornata di blocco della didattica per consentire agli studenti che lo vogliano di partecipare alla manifestazione nazionale contro la legge 133.

Errata corrige

E' stato risolto il problema sulla versione 20081014 di libgraphs, non conteneva il Makefile.

Avviso

Contrariamente a quanto affermato in un precedente post, le lezioni del 28, 30 ottobre e 4 novembre si svolgeranno regolarmente. Saranno tenute dal Dott. Jacopo Avati che svolgera' alcuni temi di esame.

Lezione del 23/10/2008

Regola del taglio: Esiste un MST che contiene il minimo arco di un taglio del grafo di partenza; Tutti gli archi dell'MST sono archi di peso minimo di qualche taglio del grafo di partenza. Algoritmo di Kruskal per il calcolo dell'MST. Esercizio: i grafi a torneo contengono un cammino Hamiltoniano.

Avviso

Le lezioni del 28 e 30 ottobre e del 4 novembre non si terranno. Queste verranno recuperate gia' a partire da domani (23 ottobre) in quanto la lezione terminera' alle 14:00 anziche' alle 13:00.

Lezione del 21/10/2008

Grafi diretti: algoritmo di visita generica; arborescenza coprente; grafi fortemente connessi; algoritmo per la verifica della forte connettivita' di un grafo fortemente connesso in tempo O(|V| + |E|). Minimo albero coprente (MST) di un grafo non diretto e pesato sugli archi; Regola del ciclo (l'arco di peso massimo di un ciclo non appartiene a nessun MST ed ogni arco non nel MST crea un ciclo nell'MST composto di archi di peso minore).

Lezione del 16/10/2008

Complessita' della visita di un grafo rappresentato mediante liste di adiacenza; Implementazione delle strutture di appoggio per la visita di grafi (pile/code); Proprieta' dell'albero risultante dalla visita in ampiezza (il livello di un nodo sull'albero corrisponde alla distanza sul grafo del nodo dalla sorgente della visita); Visita di grafi ed esistenza di cicli.

Lezione del 14/10/2008

Albero di visita di un grafo; Realizzazione dell'algoritmo generico di visita con Pila e Coda (con implementazione dettagliata in C, vedere slides ed il file visit.c per un esempio di applicazione); Visita in ampiezza; Esempio: calcolo del diametro di un grafo.

Lezione del 9/10/2008

Componenti connesse di un grafo diretto; Partizione in componenti connesse, unicita' della partizione; Ricerca della componente connessa contenente un nodo dato, algoritmo di visita generica di un grafo e sua correttezza.

Lezione del 7/10/2008

Grafi, cenni preliminari: grafi diretti, non diretti, vicinato e grado di un nodo, cammini, cicli. Operatori basilari su grafi: creazione di un grafo; verifica dell'esistenza di un arco; inserimento di un nuovo arco; cancellazione di un arco; inserimento di un nuovo nodo; cancellazione di un nodo. Rappresentazioni dei grafi (e degli operatori) col calcolatore: Liste di archi; Matrice di adiacenza; Vettore di liste di adiacenza (con implementazione dettagliata in C, vedere slides). Valutazione delle tre rappresentazioni dal punto di vista della complessita' computazionale.

Per un esempio di utilizzo delle primitive su grafi definite a lezione si veda il programma simple.c nella cartella examples della libreria per la gestione dei grafi libgraphs.zip. Per le istruzioni di compilazione si faccia riferimento al file readme.txt che si trova all'interno dell'archivio.