Il corso inizia il 24 settembre 2009.
Il calendario del corso è disponibile
a
questo
URL.
Finalità
Questo è un corso della Laurea Specialistica che intende
approfondire lo studio degli algoritmi iniziato nel corso di Algoritmi e Strutture Dati della laurea triennale.
Il concetto di algoritmo risulta essere centrale nell'Informatica, nello specifico,
e nelle Scienze in generale (vedi questo
saggio di Chazelle) ed in questo corso cercheremo di fornire evidenze
a supporto sia
della tesi specifica che della tesi generale.
La Teoria della NP-completezza sarà lo strumento principale di tale sforzo.
La Teoria della NP-completezza
fornisce un'interpretazione del fenomeno dell'apparente
intrattabilità
computazionale di importanti problemi decisionali e di ottimizzazione.
Al tempo stesso, il problema aperto principale di questa teoria
si interroga sulla natura del concetto
di prova efficiente che è fondamentale alla Matematica e
alle Scienze in generale.
La teoria della NP-completezza è oggetto di uno dei 7
Millenium Problem considerati
tra i più importanti e profondi problemi aperti della matematica contemporanea.
In classe saranno discussi i concetti di problema computazionale
efficientemente riducibile e di problema computazionale la cui soluzione ` verificabile efficientemente.
Le nozioni riducibilita' polinomiale tra problemi computazionali
e di completezza saranno introdotte al fine di presentare il
Teorema di
Cook-Levin.
A partire da questo risultato fondamentale
saranno ottenuti risultati di completezza per altri problemi computazionali
di particolare interesse quale CLIQUE, Colorabilità ed altri.
Una volta constatato che esistono problemi di ottimizzazione che
sarebbe interessante risolvere ma per cui temiamo non esista alcun
algoritmo efficiente, abbiamo due possibili modi di procedere:
o decidiamo di rilassare il concetto di efficiente
(e ci accontentiamo di progettare algoritmi superpolinomiali)
o decidiamo di rilassare il concetto di risolvere un
problema di ottimizzazione
(e ci accontentiamo di algoritmi che calcolano soluzioni sub-ottimali).
Quindi, dopo avere velocemente discusso il primo approccio,
studieremo in profondità il secondo approccio che consiste
nel risolvere problemi di ottimizzazione corrispondenti a linguaggi
NP-completi in maniera approssimata.
Il corso discuterà anche il ruolo della casualità
nel progetto degli algoritmi.
Sito dello scorso anno disponibile qui.
Orario delle lezioni
Martedì 9-11 aula P2 P11
Giovedì 9-11 aula P2 P11
Il corso inizia il 24 settembre, 2009.
Programma del corso
La lavagna dopo la prova del Teorema di Cook-Levin (grazie a Vincenzo Nigro).
La prima esercitazione con soluzioni.
La seconda esercitazione con soluzioni.
La terza esercitazione con soluzioni.
Ricevimento studenti
Il prof. G. Persiano riceve gli studenti presso il proprio studio (Stanza 3, Piano 4,
Stecca 7, Campus di Fisciano) o presso il laboratorio
Sistemi Globali (Stanza 1, Piano 2, Stecca 7, Campus di Fisciano)
il martedì e il giovedì alle 11.
Alternativamente, si può richiedere appuntamento (e-mail consigliata).
Impegno richiesto
Ogni ora di lezione frontale richiede
due ore di studio individuale.
Prossimi appelli
Testi di riferimento
Documenti e link
Blog su algoritmi
