Corso di Progettazione di Algoritmi

Docente: Annalisa De Bonis

matricole congrue ad uno

a.a. 2016-17

Orario delle lezioni

• Lunedì: 13-15, P3
• Mercoledì: 14-16, P3

Orario di ricevimento

• Martedì: 16-17
• Mercoledì: 14:30-16:30

Programma del corso

Libri di testo

• KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
• S. DASGUPTA, C. H. PAPADIMITRIOU, AND U. V. VAZIRANI. ALGORITHMS. MCGRAW-HILL

Prove in itinere

• Risultati della I prova in itinere.
• Risultati delle due prove in itinere (voti espressi in trentesimi).

Materiale delle lezioni

N.B. il materiale qui pubblicato NON include tutto quello che viene detto a lezione e non è in alcun modo sostitutivo dei libri di testo.

• Efficienza degli algoritmi e analisi asintotica degli algoritmi
• Grafi (prima parte)
• Grafi (seconda parte)
• Algoritmi greedy (prima parte): Interval Scheduling, Interval Partitioning, Minimizzazione dei ritardi.
• Algoritmi greedy (seconda parte): Problema del Caching,
• Algoritmi greedy (terza parte): Problema dei Cammini Minimi,Problema del Minimo Albero Ricoprente.
• Algoritmi greedy (quarta parte): Problema del Minimo Albero Ricoprente, Clustering
• Algoritmi basati sulla tecnica della programmazione dinamica (prima parte): Interval Scheduling Pesato, Segmented Least Squares.
• Algoritmi basati sulla tecnica della programmazione dinamica (seconda parte): Subset Sums, Problema dello zaino, Allineamento di sequenze.
• Algoritmi basati sulla tecnica della programmazione dinamica (terza parte): Percorsi minimi (algoritmo di Bellman-Ford.
• Massimo flusso.
• Applicazioni del Massimo flusso.
• Problemi difficili e ricerca esaustiva intelligente.

Appelli

• Risultati della prova del 13 aprile 2018
• Risultati della prova del 21 febbraio 2018
• Risultati della prova del primo febbraio 2018
• Traccia della prova del primo febbraio 2018
• Risultati della prova del 10 novembre 2017
• Traccia della prova del 10 novembre 2017
• Risultati della prova del 15 settembre 2017
• Risultati della prova del 10 luglio 2017
• Traccia della prova del 10 luglio 2017.
• Risultati della prova del 23 giugno 2017
• Traccia della prova del 23 giugno 2017.
• Risultati della prova del 9 giugno 2017
• Traccia della prova del 9 giugno 2017.

Avvisi:

• 4/10/2017: L'attività di ricevimento studenti è momentaneamente sospesa e riprenderà giovedì 19 ottobre. Per questioni urgenti, si prega di mandare mail a debonis@dia.unisa.it .
• 8/6/2017: Oggi non ci sarà ricevimento studenti. Per questioni urgenti, si prega di mandare mail a debonis@dia.unisa.it .
• 6/6/2017: Oggi non ci sarà ricevimento studenti.
• 22/5/2017: La II prova in itinere del corso di Progettazione di Algoritmi si terrà mercoledì 31 maggio alle 14.
• 19/4/2017: Venerdì 21 aprile non verra` svolta l'esercitazione di Progettazione di Algoritmi.