Indice:

Complexity Theory

Time and Space complexity su Turing Machines e altri modelli classici

Relazioni tra complexity classes

Riduzioni, completezza e istanze di linguaggi nelle diverse classi

Non standard computational models: DNA and Quantum Computing

Algoritmi su grafi alla base della computational complexity: reachability, trace equivalence and bisimulation

Information Theory

Concetti di base

Entropia e data compression

Mutual Information

Kolmogorov complexity

CAPACITA’ RELATIVE ALLE DISCIPLINE

Lo studente dovrà essere in grado di:

1.1. Conoscenza e capacità di comprensione

Definire formalmente i modelli classici di calcolo e le classi di complessità in tempo e spazio.

Presentare alcuni elementi di ogni classe di complessità studiata.

Esporre e dimostrare i risultati della teoria della complessità presentati durante il corso.

Definire i modelli di calcolo DNA e Quantum e confrontarli con i modelli classici.

Descrivere algoritmi su grafi.

Definire le nozioni standard della teoria dell’informazione.

Presentare i risultati classici sulla compressione dei dati presentati durante il corso.

1.2 Capacità di applicare conoscenza e comprensione

Classificare i linguaggi in termini di complessità.

Elaborare riduzioni tra linguaggi.

Definire e implementare algoritmi sui grafi per varianti dei problemi analizzati nel corso.

Modellare e risolvere semplici problemi di teoria dell’informazione: compressione dei dati e codifica dei canali.

CAPACITA’ TRASVERSALI / SOFT SKILLS

Lo studente dovrà essere in grado di:

2.1 Autonomia di giudizio

Stabilire se un problema può essere risolto in modo efficiente o meno.

Elaborare algoritmi efficienti per risolvere nuovi problemi.

Introdurre vincoli per rendere un problema trattabile.

Stimare le prestazioni di diversi sistemi di informazione e comunicazione.

2.2 Abilità comunicative.

Motivare le soluzioni proposte.

Spiegare quali condizioni aggiuntive potrebbero contribuire a risolvere il problema in modo più efficace.

Giustificare le scelte del modello computazionale e delle strutture dati.

Spiegare i metodi di codifica e di compressione e i limiti.

2.3 Capacità di apprendimento

Trovare e sfruttare soluzioni esistenti su problemi correlati.

Sfruttare nuovi strumenti per migliorare le complessità computazionali.

Si vedano anche le pagine:

https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/LM-informatica/all-B2

https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/lm-artificial-intelligence-cybersecurity/all-B2