Vai al contenuto principale
Se prosegui nella navigazione del sito, ne accetti le politiche:
  • Condizioni di utilizzo e trattamento dei dati
Prosegui
x
Se prosegui nella navigazione del sito, ne accetti le politiche:
  • Condizioni di utilizzo e trattamento dei dati
Prosegui
x
e-Learning - UNIMIB
  • Home
  • Altro
Ascolta questa pagina con ReadSpeaker
Italiano ‎(it)‎
English ‎(en)‎ Italiano ‎(it)‎
 Login
e-Learning - UNIMIB
Home
Percorso della pagina
  1. Area di Scienze
  2. Corso di Laurea Magistrale
  3. Informatica [F1802Q - F1801Q]
  4. Insegnamenti
  5. A.A. 2021-2022
  6. 1° anno
  1. Teoria della Computazione
  2. Introduzione
Unità didattica Titolo del corso
Teoria della Computazione
Codice identificativo del corso
2122-1-F1801Q132-F1801Q133M
Descrizione del corso SYLLABUS

Blocchi

Torna a Modelli e Computazione

Syllabus del corso

  • Italiano ‎(it)‎
  • English ‎(en)‎
Esporta

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

Programma esteso

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.

Prerequisiti

Nessuno

Modalità didattica

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.


Materiale didattico

Dispense e slides del docente.

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.

Esporta

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

Detailed program

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.

Prerequisites

None

Teaching form

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.

Textbook and teaching resource

Slides and written notes.

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.

Entra

Scheda del corso

Settore disciplinare
INF/01
CFU
6
Periodo
Primo Semestre
Tipo di attività
Obbligatorio
Ore
52
Lingua
Italiano

Staff

    Docente

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

Metodi di iscrizione

Iscrizione manuale
Iscrizione spontanea (Studente)

Non sei collegato. (Login)
Politiche
Ottieni l'app mobile
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy
  • Accessibilità
  • Statistiche