SITE TITLE

LOGO DIETI

Algoritmi e strutture dati II


Titolo insegnamento in inglese: Algorithms and data structures II

Lingua: Inglese

Insegnamento: Algoritmi e strutture dati II

Anno di corso:  III 

CFU: 6

SSD: INF/01

Ore di lezione: 48

Semestre: 2

Modulo: Unico

Codice: 12566

Obiettivi formativi:
Il corso intende fornire un'introduzione  alle tecniche avanzate di progettazione degli algoritmi, alla complessità computazionale e alla trattabilità dei problemi. Vengono, in particolare, presentate le principali tecniche di dimostrazione di correttezza, esaminate le tecniche  di progettazione greedy e di programmazione dinamica, con applicazioni alla soluzione di vari problemi di ottimizzazione, di compressione dei dati e problemi su grafi pesati. Vengono introdotte le classi di complessità P e NP e il concetto di NP-completezza e di riduzione tra problemi. Vengono infine presentate tecniche di progettazione ed analisi di algoritmi approssimati e di algoritmi randomizzati. .

Contenuti:
Il problema della correttezza degli algoritmi: dimostrazioni per induzione, dimostrazioni di correttezza di algoritmi ricorsivi. Tecniche di progettazione di algoritmi: introduzione agli algoritmi greedy ed alla programmazione dinamica per la soluzione di problemi di ottimizzazione (ad es., problema dello zaino intero e frazionario, percorsi minimi su grafi pesati, i codici di Huffman, problemi di scheduling). Introduzione alla Teoria della Complessità: problemi trattabili e non trattabili, le principali classi di complessità (P e NP), il concetto di riduzione polinomiale tra problemi e il concetto di NP-completezza, esempi di problemi NP-completi e dimostrazioni di NP-completezza. Introduzione all'intrattablita' computazionale. Introduzione agli algoritmi approssimati; fattore di approssimazione; esempi di algoritmi approssimati per problemi du grafi. Introduzione agli algoritmi randomizzati. Progettazione ed analisi di algoritmi randomizzati per problemi di scheduling e problemi su grafi. 

Propedeuticità: Algoritmi e strutture dati I

Modalità didattiche: Lezioni frontali. Esercitazioni

Materiale didattico:

Jon Kleinberg e Eva Tardos: Algorithm Design, Addison-Wesley

Modalità di esame:

L'esame si articola in prova

Scritta e orale

 

 

 

     

 

 

 

In caso di prova scritta i quesiti sono

   

 

A risposta libera

 

   

 

Alto

 

 

Docente:  Galdi Clemente