COMPUTABILITA' E COMPLESSITA'
Modulo COMPLESSITA'
Anno accademico 2024/2025 - Docente:
Vincenzo CUTELLO
Risultati di apprendimento attesi
Conoscenza e capacità di comprensione (knowledge and understanding): saranno acquisite le nozioni fondamentali sulle Notazioni asintotiche, Classi di complessità temporale, la classe NP e NP-completezza.Il problema della soddisfacibilità proposizionale (SAT) e il Teorema di Cook. Inoltre saranno acquisite le problematiche computazionali riguardanti diversi problemi come 3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet, HittingSet, SetCover, SubsetSum, Knapsack
Autonomia di giudizio (making judgements): lo studente sarà in grado di valutare in maniera formale la classe computazionale di problemi algoritmici.
Abilità comunicative (communication skills): saranno acquisite le necessarie abilità comunicative ed un'adeguata appropriatezza espressiva nella comunicazione di problematiche inerenti gli studi di complessità computazionale.
Capacità di apprendimento (learning skills): lo studente avrà la capacita di adattare le conoscenze acquisite anche a nuovi contesti, nonché di aggiornarsi attraverso la consultazione delle fonti specialistiche del settore della complessità.
Modalità di svolgimento dell'insegnamento
Lezioni frontali
Prerequisiti richiesti
- Elementi di matematica discreta e matematica del continuo
- Concetto intuitivo di algoritmo
- Elementi di logica matematica
Frequenza lezioni
Per una piena comprensione degli argomenti del corso e delle tecniche risolutive illustrate, la frequenza delle lezioni è fortemente consigliata.
Contenuti del corso
Notazioni asintotiche, Funzioni numeriche (Turing) computabili. Classi di complessità temporale
La classe NP e NP-completezza
Il problema della soddisfacibilità proposizionale (SAT). Teorema di Cook
Catalogo di problemi NP-completi (3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet,
HamiltonianPath, HamiltonianCircuit, LongestSimplePath, SetCover, HittingSet,
SubgraphIsomorphism, TravelingSalesman, 3-DimensionalMatching, Partition, SubsetSum, Knapsack)
Complessità spaziale delle macchine di Turing
Testi di riferimento
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]
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
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.
Esempi di domande e/o esercizi frequenti
1.Qual è la complessità computazionale del seguente algoritmo?
2. Descrivere la riduzione del seguente problema a 3SAT
3. Fornire un esempio di problema NP-hard ma non in NP
