Course Syllabus

Export

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.

Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale. Complessità di approssimazione e parametrica. 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.

1. Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale. Complessità di approssimazione.

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.

Nessuno

Lezioni frontali ed esercitazioni.

In caso di restrizioni per Covid-19, le lezioni e le esercitazioni potranno essere videoregistrate o trasmesse in modalità sincrona, con momenti sincroni (in streaming, non registrati) di discussione e risposta alle domande degli studenti.


Dispense e slides del docente.

Primo semestre.

Prova scritta. La prova scritta consiste nello svolgimento di esercizi relativi all'acquisizione di competenze specifiche nelle tematiche principali del programma del corso.

Per appuntamento.

Export

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).

Basic notions of theory of computation (decidability, intractability). Classification of problems with respect to their computational complexity. Approximation 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).

1. Basic notions of theory of computation (decidability, intractability, reductions). Classification of problems with respect to their computational complexity. Approximation 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.

None

Lectures and practice exercises.

In case of restrictions related to Covid-19 emergency, lectures and practice exercises could be done by means of recorded or online video, with specific non-recorded online meetings for discussing and answering possible questions from students.

Slides and written notes.

First semester.

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.

By appointment.

Enter

Key information

Field of research
INF/01
ECTS
6
Term
First semester
Activity type
Mandatory
Course Length (Hours)
52
Language
Italian

Staff

    Teacher

  • PB
    Paola Bonizzoni
  • RR
    Raffaella Rizzi
  • CZ
    Claudio Zandron

Enrolment methods

Manual enrolments
Self enrolment (Student)