Course Syllabus
Obiettivi
Conoscenza e comprensione
L'insegnamento di Teoria della Computazione ha l'obiettivo fondamentale di far acquisire allo studente gli strumenti teorici che permettono di comprendere la complessità computazionale dei problemi, come sono classificati in base alla loro complessità e quali sono le metodologie per risolverli, in modo esatto o con performance di approssimazione dimostrabili. Introduce anche metodologie algoritimiche e strutture dati avanzate per affrontare problemi fondamentali su testi di grandi dimensione.
In particolare lo studente sarà in grado di:
- Comprendere i concetti fondamentali del principale modello di calcolo (Macchina di Turing) e delle sue varianti
- Comprendere quali problemi possono essere risolti da un computer (decidibilità) e quali non possono essere risolti in un tempo ragionevole (intrattabilità)
- Comprendere gli algoritmi di approssimazione, cioè algoritmi che ottengono in tempi ragionevoli una soluzione dimostrabilmente vicina all'ottimo per problemi intrattabili in modo esatto
- Comprendere gli algoritmi parametrici, cioè algoritmi che permettono di affrontare in modo esatto alcuni problemi intrattabili limitando la crescita esponenziale dei tempi di calcolo dei loro algoritmi risolutivi a un parametro dell'istanza che risulta essere di valore limitato in casi pratici
- comprendere le basi teoriche e le applicazioni pratiche della ricerca esatta e approssimata di stringhe e delle strutture dati per l'indicizzazione di stringhe
Capacità di applicare conoscenza e comprensione
Lo studente sarà in grado di:
- capire come un problema può essere ridotto ad un altro per dimostrare la complessità relativa dei problemi
- classificare i problemi in base alla loro complessità computazionale (ad esempio, P, NP, NP-completi)
Autonomia di giudizio
Lo studente sarà in grado di:
- valutare se un problema è computabile o meno
- valutare quale algoritmo di ricerca utilizzare in un determinato contesto applicativo
- valutare quale struttura di indicizzazione utilizzare in un determinato contesto applicativo
Capacità comunicativa
- acquisizione del formalismo specifico alla disciplina della teoria della computazione
Capacità di apprendere
- acquisizione di capacità di astrarre rispetto a problemi computazionali affrontati nel corso
Contenuti sintetici
Nozioni di base di teoria della computazione: macchine di Turing, decidibilità e intrattabilità dei problemi computazionali. Riduzioni tra problemi computazionaii e classificazione dei problemi in funzione della complessità computazionale. Complessità di approssimazione e parametrica. Algoritmi di string matching esatto e approssimato. Strutture di indicizzazione.
Programma esteso
- Nozioni di base di teoria della computazione:
- Il modello di calcolo della macchina di Turing e equivalenza con le sue varianti principali (macchine multinastro, alfabeto non binario, macchine non deterministiche)
- Relazioni tra linguaggi formali e problemi computazionali
- Limiti di computabilità: indecidibilità dell'Halting Problem
- Trattabilità e intrattabilità, cioè classificazione dei problemi in funzione della complessità computazionale:
- Decidibilità in tempo polinomiale su macchine deterministiche (P, coP) e su macchine non deterministiche (NP, coNP)
- Equivalenza di decidibilità non deterministica in tempo polinomiale e verificabilità deterministica in tempo polinomiale
- Riduzioni polinomiali fra problemi di decisione
- NP-completezza del problema di Soddisfacibilità (SAT)
- Dimostrazioni di NP-hardness e NP-completezza
- Complessità di approssimazione
- Algoritmi parametrici
- Algoritmi di string matching esatto
- Automa a stati finiti
- Algoritmo di Knuth-Morris-Pratt
- Algoritmo basato su paradigma shift-and
- Algoritmi di string matching approssimato
- Algoritmo basato su paradigma shift-and
- Strutture di indicizzazione di testi
- Suffix Array
- Burrows-Wheeler Transform
- FM-index
Prerequisiti
Nozioni di base di linguaggi formali. Nozioni di base di algoritmi e strutture dati.
Modalità didattica
Lezioni ed esercitazioni in aula.
Tutte le attività sono tenute in presenza e non vengono registrate né trasmesse in streaming.
L'insegnamento viene erogato in Italiano.
Le attività previste sono 28 lezioni da 2 ore svolte in modalità erogativa nella parte iniziale ed in modalità interattiva nella parte successiva.
Materiale didattico
Dispense e slides del docente.
Libro: Sipser, Michael. Introduzione alla teoria della computazione.
Periodo di erogazione dell'insegnamento
Primo semestre.
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento consiste di una prova scritta.
La prova scritta è basata su domande a risposta aperta relative alle nozioni e tecniche presentate nel corso e su esercizi che richiedono l'applicazione delle nozioni e delle tecniche suddette.
La prova scritta viene valutata in base alla correttezza e completezza delle risposte.
Sono previste due prove scritte in itinere.
Orario di ricevimento
Il ricevimento è su appuntamento da concordare con i docenti.
Aims
Knowledge and Understanding
The course in Theory of Computation aims to provide students with the theoretical tools necessary to understand the computational complexity of problems, how they are classified based on their complexity, and the methodologies for solving them—either exactly or with provable approximation performance. It also introduces algorithmic methodologies and advanced data structures to tackle fundamental problems involving large-scale text data.
Specifically, the student will be able to:
- Understand the fundamental concepts of the main computazional model (Turing Machine) and its variants
- Understand which problems can be solved by a computer (decidability) and which cannot be solved in reasonable time (intractability)
- Understand approximation algorithms, i.e., algorithms that provide, in reasonable time, a provably near-optimal solution for problems that are intractable to solve exactly
- Understand parameterized algorithms, i.e., algorithms that allow exact solutions to certain intractable problems by restricting the exponential growth of computation time to a specific instance parameter that is limited in practical cases
- Understand the theoretical foundations and practical applications of exact and approximate string matching, as well as data structures for string indexing
Applying Knowledge and Understanding
The student will be able to:
- Understand how one problem can be reduced to another to demonstrate the relative complexity of problems
- Classify problems based on their computational complexity (e.g., P, NP, NP-complete)
Making Judgements
The student will be able to:
- Assess whether a problem is computable or not
- Evaluate which search algorithm to use in a specific application context
- Evaluate which indexing structure to use in a specific application context
Communication Skills
- Acquisition of the formal language specific to the discipline of Theory of Computation.
Learning Skills
- Development of the ability to abstract from computational problems addressed during the course.
Contents
Basic concepts of theory of computation: Turing machines, decidability, and intractability of computational problems. Reductions between computational problems and classification of problems based on computational complexity. Approximation and parametric complexity. String matching algorithms. Indexing structures.
Detailed program
- Basic concepts of theory of computation:
- The Turing Machine model of computation and its equivalence with its main variants (multitape machines, non-binary alphabet, nondeterministic machines)
- Relationships between formal languages and computational problems
- Limits of computability: undecidability of the Halting Problem
- Tractability and intractability, i.e., classification of problems based on computational complexity:
- Decidability in polynomial time on deterministic machines (P, coP) and on nondeterministic machines (NP, coNP)
- Equivalence of nondeterministic polynomial-time decidability and deterministic polynomial-time verifiability
- Polynomial reductions between decision problems
- NP-completeness of the Satisfiability Problem (SAT)
- Proofs of NP-hardness and NP-completeness
- Approximation complexity
- Parameterized algorithms
- Exact string matching algorithms
- Finite state automaton
- Knuth-Morris-Pratt algorithm
- Algorithm based on the shift-and paradigm
- Approximate string matching algorithms
- Algorithm based on the shift-and paradigm
- Text indexing structures
- Suffix Array
- Burrows-Wheeler Transform
- FM-index
Prerequisites
Basic concepts of formal languages. Basic concepts of algorithms and data structures.
Teaching form
Lectures and classroom exercises.
All activities are conducted in person and are not recorded or streamed.
Teaching is delivered in Italian.
There are 28 lectures of 2 hours each, conducted in a lecturing format initially and then in an interactive format.
Textbook and teaching resource
Slides and written notes.
Book: Sipser, Michael. Introduction to theory of computation.
Semester
First semester.
Assessment method
The assessment of learning consists of a written exam.
The written exam is based on open-ended questions related to the concepts and techniques presented in the course, as well as exercises requiring the application of the learnt concepts and techniques.
The written exam is evaluated based on the correctness and completeness of the answers.
Two mid-term written exams are scheduled.
Office hours
Office hours are by appointment to be arranged with the instructors.