Course Syllabus
Obiettivi
Teoria della Computazione ha come obiettivo l'acquisizione di strumentalità di base dell'informatica volte alla comprensione della complessità computazionale dei problemi, alla loro classificazione e alle metodologie algoritmiche per la loro soluzione. Inoltre, si intende fornire capacità in merito alla soluzione di problematiche teoriche poste dalle nuove tecnologie (web, dati massivi, reti complesse, etc.) mediante strutture dati recentemente proposte.
Contenuti sintetici
Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale. Approcci moderni per la gestione, indicizzazione, compressione di dati massivi sia con strutture dati che con tecniche algoritmiche innovative. Strutture dati succinte (FM-index), indicizzazione e ricerca per i big-data con tecniche di hashing probabilistico, algoritmi di compressione dati.
Programma esteso
1. Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale.
2. Approcci moderni per la gestione, indicizzazione, compressione di grandi moli di dati, sia con strutture dati che con tecniche algoritmiche avanzate.
3. Strutture dati di indicizzazione (FM-index, bloom filters, hashing), pattern matching, paradigma shift-and, compressione dati LZ, strutture dati succinte.
4. Applicazioni ed esemplificazioni all'analisi di big-data.
Prerequisiti
Nessuno
Modalità didattica
Lezioni frontali ed esercitazioni.
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
Prova scritta. La prova scritta consiste nello svolgimento di esercizi relativi all'acquisizione di competenze specifiche nelle tematiche principali del programma del corso.
Orario di ricevimento
Per appuntamento.
Aims
Theory of Computation deals with the acquisition of basic theoretical tools that allow to understand the computational complexity of problems, how they are classified according to their complexity and then how they can be solved by algorithmic methodologies. The course provides skills on the use and design of novel data structures that are relevant in dealing with modern applications (web, complex networks, massive data, and so on).
Contents
Basic notions of theory of computation (decidability, intractability). Classification of problems with respect to their computational complexity. Modern approaches to indexing, compression of large data sets by using novel data structures and algorithmic techniques. Indexing data structures (suffix tree, trie, hashing, FM-index), pattern matching, the shift-and paradigm, data compression. Applications to the WEB (complex networks).
Detailed program
1. Basic notions of theory of computation (decidability, intractability, reductions). Classification of problems with respect to their computational complexity.
2. Modern approaches to indexing, compression of massive data sets by using novel data structures and algorithmic techniques.
3. Indexing data structures (bloom filters, hashing), pattern matching, the shift-and paradigm, data compression, succinct data structures.
4. Applications to the analysis of massive data.
Prerequisites
None
Teaching form
Lectures and practice exercises.
Textbook and teaching resource
Slides and written notes.
Textbook: Sipser, Michael. Introduction to the Theory of Computation. 3rd ed.
Semester
First semester.
Assessment method
Oral exam. The written exam consists of a list of exercises whose solution requires the acquisition of skills related to the main topics of the course syllabus.
Office hours
By appointment.