ALGORITMI E COMPLESSITA'

Obiettivi formativi

Gli obiettivi formativi del corso sono principalmente due. Il primo è fornire una introduzione alla progettazione e analisi degli algoritmi su solide basi concettuali e matematiche. Il secondo è fornire un'introduzione al fondamentale fenomeno della complessità computazionale dei problemi algoritmici. Per quanto riguarda il primo obiettivo si fornirà in particolare una introduzione alle principali tecniche di progettazione algoritmica attraverso una serie di problemi algoritmici notevoli. Per il secondo invece, ci si concentrerà sulle nozioni di indecidibilità e di NP.completezza.

Canale 1
ALESSANDRO PANCONESI Scheda docente
FLAVIO CHIERICHETTI Scheda docente

Programmi - Frequenza - Esami

Programma
Programmazione dinamica: Segmented Least Squares, Bellman-Ford Strutture dati: Union find; tabelle hash Greedy: Codici di Huffman Divide-et-Impera: Moltiplicazione di Interi Introduzione agli Algoritmi di approssimazione e a online learning (problema degli esperti) Introduzione alla calcolabilità e complessità: macchine di Turing; problemi indecidibili; riduzioni; NP-completezza
Prerequisiti
Non ci sono prerequisiti formali
Testi di riferimento
"Algorithm Design", Kleinberg, Tardos Dispense fornite dal docente
Frequenza
La presenza non è obbligatoria, ma è fortemente consigliata.
Modalità di esame
Esame scritto
Bibliografia
"Algorithm Design", Kleinberg, Tardos "Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein "Automata and computatability", Kozen
Modalità di erogazione
Le lezioni saranno svolte alla lavagna e/o con slide.
  • Codice insegnamento10603315
  • Anno accademico2025/2026
  • CorsoScienze matematiche per l’intelligenza artificiale
  • CurriculumCurriculum unico
  • Anno2º anno
  • Semestre1º semestre
  • SSDINF/01
  • CFU6
  • Ambito disciplinareAttività formative affini o integrative