Avviso

E' stata aggiornata la raccolta degli esercizi svolti a lezione (link). Attenzione: la soluzione dell'esercizio sullo Steiner tree (Esercizio 15) e' diversa da quella mostrata a lezione che presentava un baco.

Esercitazione del 27/01/2009 - ULTIMA LEZIONE

Minimo Steiner Tree di un grafo: caso particolare in cui i nodi da coprire sono 3. NP-completezza di Max NAE 3-Sat via riduzione da Max 2-Sat.

Esercitazione del 22/01/2009

Eccentricita' dei nodi di un grafo, calcolo dei centri: diverse soluzioni. NP-completezza di Max Exacly 2-Sat via riduzione da Max 2-Sat.

Avviso

La lezione di martedi 20 gennaio e' annullata. Le lezioni riprenderanno giovedi' 22 gennaio.

Esercitazione del 15/01/2009

Ciclo di costo minimo passante per un arco di un grafo fortemente connesso con pesi positivi. NP-Completezza di Max 2-Sat: riduzione da 3-Sat.

Avviso

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

Avviso

Sono state aperte sul sito delphi le prenotazioni per gli appelli di febbraio. Si ricorda che la prenotazione e' obbligatoria.

Gli studenti fuori corso che intendono laurearsi entro maggio hanno a disposizione la data del 3/2/2009. Costoro devono prenotarsi obbligatoriamente all'appello relativo all'a.a. 2007/2008.

Esercitazione del 13/01/2009

Ripasso generale sull'NP-completezza. NP-completezza del problema dell'Hitting Set.

Esercitazione del 08/01/2009 (Tenuta da Jacopo Avati)

Elenco degli esercizi svolti:

* Esercizio 1 dell'appello del 18/09/2007;

* Esercizio 1 dell'appello del 05/07/2007;

* Dato un grafo G pesato, non orientato e connesso ed un nodo r, dire se esiste una costante che limita superiormente il rapporto tra il costo dell'albero dei cammini minimi di G con radice r ed il costo di un minimo albero coprente di G;

* Dato un grafo non orientato, connesso e con pesi sugli archi positivi e tutti distinti e dato un nodo r, si dica se il minimo albero coprente e l'albero dei cammini minimi da r hanno sempre archi in comune.

* Esercizio 1 dell'appello del 10/06/2008;