Esito prova scritta del 23/2/2009

I seguenti studenti identificati dallo pseudonimo hanno superato la prova scritta del 23/2/2009 e pertanto sono ammessi alla prova orale del 25/2/2009: ARTE, 0103921, DANIF, MAXIMUS, SIXTY88, KROMOR, ERPF, TEX, SIR_VALERIUS.
ATTENZIONE: Per sostenere la prova orale e' necessario iscriversi all'apposito appello utilizzando il servizio Totem.

Esito prova scritta del 3/2/2009

I seguenti studenti identificati dallo pseudonimo hanno superato la prova scritta del 3/2/2009 e pertanto sono ammessi alla prova orale del 5/2/2009: Cirillo Luca, De Carolis, LEONIDA88, LOST, Palumbo, Santelli, STEVEN, TIZIO, V@L.
ATTENZIONE: Per sostenere la prova orale e' necessario iscriversi all'apposito appello utilizzando il servizio Totem.
Gli studenti che non hanno superato la prova scritta sono invitati a consultare la soluzione proposta su questo blog. Se dovessero permanere dei dubbi relativi alla correzione si puo' visionare il proprio elaborato durante la prova orale del 5/2/2009.

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;

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'.