La definizione di informatica proposta dall’ACM (Association for Computing Machinery),
una delle principali organizzazioni scientifiche di informatici di tutto il
mondo, è la seguente:
”L’informatica è la scienza degli algoritmi che
descrivono e trasformano l’informazione: la loro teoria, analisi, progetto,
efficienza, realizzazione e applicazione.”
“Before there were computers, there were
algorithms. But now that there are computers, there are even more algorithms,
and algorithms lie at the heart of computing.” T. H. Cormen, C. E. Leiserson, R. L. Rivest, C.
Stein, Introduction to Algorithms, Third edition.
Cos’è
un algoritmo?
Ascoltate Digito
Ergo Sum!
Avvisi
Le
lezioni cominciano lunedì 6 Marzo 2017
Il corso di
Progettazione di Algoritmi è il naturale proseguimento del corso di
Introduzione agli Algoritmi e alle Strutture Dati. Anche se non vi è una
propedeuticità formale, si presuppongono noti i concetti acquisiti in tale
corso. La parte relativa all’analisi asintotica degli algoritmi, alla tecnica
del divide et impera e alle relazioni di ricorrenza verrà brevemente ripresa
nelle prime lezioni.
Sono
disponibili il programma e il syllabus
del corso.
I libri di testo di riferimento
sono:
[KT] Kleinberg, Tardos. Algorithm Design. Pearson Addison Wesley.
[DPV] S. Dasgupta,
C. H. Papadimitriou, and U. V. Vazirani.
Algorithms. McGraw-Hill.
Altri libri di consultazione sono:
[CLR1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduzione
agli Algoritmi, prima edizione, McGraw Hill.
[CLRS2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduzione
agli Algoritmi, seconda edizione, McGraw Hill.
[DFI] C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e Strutture Dati , Mc-Graw Hill, 2004.
Le slides
delle lezioni utilizzano in parte quelle del Prof. Kevin Wayne,
Princeton University, disponibili sul sito del testo [KT] e quelle pubblicate da altri docenti di
Algoritmi.
Potete visualizzare il
comportamento di alcuni degli algoritmi che vedremo nel corso su questi siti: qui e qui.
Svolgimento del corso
Il corso è di 6 CFU e prevede 48 ore di lezione frontale che saranno svolte
secondo il seguente calendario previsto.
Eventuali ore di recupero potranno svolgersi il
martedì dalle 15 alle 17 in aula F1 o in laboratorio Reti.
Le slides delle lezioni e maggiori informazioni per chi segue
il corso saranno reperibili sulla piattaforma di
e-learning.
Calendario di massima delle lezioni
Lezione 1 (Lunedì 6 marzo 2017): Presentazione del corso.
Qualche esempio.
Lezione 2 (Martedì 7 marzo 2017):
Grafi: definizioni, visita di grafi BFS e DFS. Problemi su
componenti connesse in grafi (orientati e non). (parr. 3.1, 3.2, 3.3). Test per grafi
bipartiti. (parr. 3.4, 3.5).
Lezione 3 (Lunedì 13 marzo 2017): Tecnica
Divide-et-impera: la ricerca binaria e MergeSort
(par. 5.1). Relazioni di ricorrenza.
Lezione 4 (Martedì 14
marzo
2017): Programmazione dinamica:
il calcolo dei numeri di Fibonacci (puoi consultare [DFI]). Principi della
programmazione dinamica (parr. 6.1 e 6.2).
Lezione 5 (Lunedì 20 marzo 2017): Programmazione dinamica: Selezione di intervalli pesati.
Lezione 6 (Martedì 21
marzo
2017): Programmazione dinamica:
Allineamento di sequenze (par. 6.6).
Lezione 7 (Lunedì 27 marzo 2017): Programmazione dinamica: Somma di Sottoinsiemi e il problema dello zaino
(par. 6.4).
Lezione 8 (Martedì 28 marzo 2017, 9-11): Programmazione dinamica: Struttura secondaria dell’RNA (par.
6.5).
Lezione 9 (Martedì 28 marzo
2017 ore 15-17, F1, recupero 1):
Esercitazione sulla programmazione dinamica.
Lezione 10 (Lunedì 3 Aprile 2017): Visite BFS e DFS: algoritmi e implementazioni (par. 3.2).
Lezione 11 (Martedì 4 Aprile 2017): Problemi su
componenti connesse in grafi (orientati e non). (parr. 3.1, 3.2, 3.3). Test per grafi
bipartiti. (parr. 3.4, 3.5). Ordine topologico in DAG (par. 3.6). Esercizi.
Lezione 12 (Martedì 4 Aprile 2017 ore 15-17, F1,
recupero 2): Esercizi
PD e grafi
Lezione 13 (Lunedì 10 Aprile 2017): Esercitazione su domande a risposte multiple e quesiti di esame.
Lezione 14 (Martedì 11
Aprile 2017): Prima Prova intercorso.
Lunedì 17 Aprile: Vacanze pasquali
Martedì 18 Aprile: Vacanze pasquali
Lunedì 24 Aprile: Ponte
Martedì 25 Aprile: Festa della Liberazione
Lunedì 1 Maggio: Festa del Lavoro
Lezione 15 (Martedì 2
maggio 2017): Metodo greedy 1: il problema della selezione di intervalli e della
partizione di intervalli (par. 4.1).
Lezione 16 (Lunedì 8
maggio 2017): Metodo greedy 2: il problema della selezione che
minimizza il ritardo (par. 4.2). Esercizio: cambio di monete.
Lezione 17 (Martedì 9
Maggio 2017): Metodo greedy
3: Codici univocamente decifrabili e compressione di dati. Algoritmo di Huffman per la ricerca dei codici ottimali. Correttezza
dell’algoritmo di Huffman (par. 4.8).
Lezione 18 (Mercoledì 10
maggio 11-13, P3, (al posto di Cerulli) recupero 3): Albero minimo di ricoprimento: algoritmi di Kruskal, di Prim e Reverse-Delete
(par. 4.5). Implementazioni degli algoritmi di Prim e
Kruskal (par.4.6, cenni).
Lezione 19 (Lunedì 15
maggio 2017): Implementazione
dell’algoritmo di Kruskal (par. 4.6, cenni).
Applicazione di MST: clustering (par. 4.7). Calcolo di cammini minimi: algoritmo
di Dijkstra (par. 4.4).
Lezione 20 (Martedì
16 Maggio 2017): Algoritmo di Dijkstra:
implementazione e corretteza. Calcolo di cammini
minimi con costi anche negativi: algoritmo di Bellman-Ford
(par. 6.8; facoltativo: implementazioni che migliorano lo spazio di memoria).
Lezione 21 (Lunedì 22
maggio 2017): Problema del
flusso: algoritmo di Ford-Fulkerson e sua correttezza
(parr. 7.1, 7.2).
Lezione 22 (Martedì 23
Maggio 2017): Applicazione dell’algoritmo di Ford-Fulkerson
al problema del matching su grafi bipartiti (par.
7.5). Esercitazione in preparazione agli esami.
Lezione 23 (Lunedì 29
maggio 2017): Algoritmi
intelligenti di ricerca esaustiva: backtracking e branch-and-bound ([DPV] par. 9.1).
Lezione 24 (Martedì 30
Maggio 2017): Esercitazione finale.
Prove
di esame previste