COMPUTABILITA' E COMPLESSITA'

Modulo COMPLESSITA'

Conoscenza e capacità di comprensione: Saranno acquisite le nozioni fondamentali relative alle classi di complessità temporale, con particolare attenzione alla classe NP e al concetto di NP-completezza. Verranno inoltre approfonditi il problema della soddisfacibilità proposizionale (SAT) e il Teorema di Cook. Saranno infine esaminate le problematiche computazionali associate a diversi problemi classici, tra cui 3-SAT, n-SAT, Vertex Cover, Clique, Independent Set, Hitting Set, Set Cover, Subset Sum e Knapsack.

Autonomia di giudizio: Lo studente sarà in grado di valutare in modo rigoroso la classe computazionale di un problema algoritmico.

Abilità comunicative: Saranno acquisite le necessarie abilità comunicative e un’adeguata appropriatezza espressiva nella presentazione e discussione di problematiche inerenti gli studi di complessità computazionale, anche a interlocutori non esperti.

Capacità  di apprendimento: Lo studente avrà la capacità di applicare e adattare le conoscenze acquisite anche a nuovi contesti, nonché di aggiornarsi in modo autonomo attraverso la consultazione di fonti specialistiche nel settore della complessità computazionale.

Lezioni frontali

Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.

Informazioni per studenti con disabilità e/o DSA

A garanzia di pari opportunità e nel rispetto delle leggi vigenti, gli studenti interessati possono chiedere un colloquio personale in modo da programmare eventuali misure compensative e/o dispensative, in base agli obiettivi didattici ed alle specifiche esigenze. E' possibile rivolgersi anche al docente referente CInAP (Centro per l’integrazione Attiva e Partecipata - Servizi per le Disabilità e/o i DSA) del nostro Dipartimento, prof.ssa Patrizia Daniele.

- Elementi di matematica discreta e matematica del continuo

- Concetto intuitivo di algoritmo

- Elementi di logica matematica

Notazioni asintotiche (cenni), Classi di complessità temporale.
La classe NP e NP-completezza.
Il problema della soddisfacibilità proposizionale (SAT).
Teorema di Cook.
Catalogo di problemi NP-completi (a titolo indicativo): 3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet, HamiltonianPath, HamiltonianCircuit, LongestSimplePath, SetCover, HittingSet, SubgraphIsomorphism, TravelingSalesman, 3-DimensionalMatching, Partition, SubsetSum, Knapsack.
La lista è da intendersi non esaustiva: alcuni problemi potranno essere trattati solo brevemente e altri, non menzionati, potranno essere introdotti durante il corso.
Complessità spaziale delle macchine di Turing.

1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge, UK, 1986.  [Testo principale]

2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Lettura consigliata]

L’esame finale è essenzialmente scritto. La verbalizzazione potrà essere preceduta da una breve discussione sul compito scritto e, nei casi dubbi, da una breve verifica orale.

Il voto sarà attribuito secondo i seguenti criteri:

• Non approvato: lo studente non ha acquisito i concetti di base e non è in grado di rispondere ad almeno il 60% delle domande, né di svolgere gli esercizi assegnati.

• 18–23: lo studente dimostra una padronanza minima dei concetti fondamentali; le sue capacità di esposizione e collegamento sono modeste, ed è in grado di risolvere solo esercizi semplici.

• 24–27: lo studente possiede una buona conoscenza dei contenuti del corso; sa collegare in modo coerente i concetti ed esegue gli esercizi con pochi errori.

• 28–30 e lode: lo studente ha acquisito in modo completo tutti i contenuti del corso, dimostrando piena padronanza e capacità di rielaborazione critica; risolve gli esercizi in modo corretto e completo, senza errori.

A titolo esemplificativo, ecco alcuni esempi di domande d’esame:

1. Determinare e giustificare la complessità computazionale di un dato algoritmo.

2. Descrivere nei dettagli la riduzione del seguente problema a 3-SAT.

3. Fornire un esempio di problema NP-hard che non appartiene a NP e motivare la risposta.

4. Dimostrare che il problema CLIQUE è NP-completo.

5. Confrontare le classi di complessità P, NP e co-NP, discutendone le principali differenze.

Nota: gli esercizi sopra riportati sono solo esempi; la prova potrà includere anche domande su altri argomenti del programma.