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
Ecco il calendario delle lezioni di tutorato di
Progettazione di Algoritmi che si terranno agli inizi di Settembre:
5 set
ore 10-13 aula P6
6 set
ore 10-13 aula P6
8 set
ore 10-13 aula F1
9 set
ore 15-18 aula F1
La lezione di martedì 20 ottobre si terrà dalle 16
alle 18.
A
partire da lunedì 28/9 le lezioni si terranno in aula F8 anziché in aula F1.
Le
lezioni cominciano martedì 22 Settembre 2015
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.
Svolgimento del corso
Il corso prevede 48 ore
di lezione frontale che saranno
svolte secondo il seguente calendario previsto.
Eventuali ore di recupero potranno svolgersi il
venerdì dalle 15 alle 17 in aula F1 o in laboratorio P13.
Calendario delle lezioni
Le slides
delle lezioni sono reperibili sulla piattaforma di
e-learning.
Lezione 1 (Martedì 22 settembre 2015): Presentazione del corso.
Qualche esempio.
Lezione 2 (Lunedì 28 settembre 2015, Aula F8): Analisi
di algoritmi. Tempo di esecuzione e analisi asintotica. Notazioni asintotiche (par. 2.1, 2.2).
Lezione 3 (Martedì 29
settembre 2015): Notazioni
asintotiche e loro proprietà.
Lezione 4 (Lunedì 5
ottobre 2015): Tempi tipici di esecuzione di
algoritmi (par. 2.4). Tecnica Divide-et-impera: la ricerca binaria e MergeSort
(par. 5.1). Relazioni di ricorrenza. Ecco un elenco di esercizi sulla tecnica divide et impera
con i quali potrete esercitarvi Si consiglia di svolgere gli esercizi indicati
sulle slide, gli esercizi 3, 4, 5 e 6 a p. 67-68 del libro [KT] e gli esercizi
da questo elenco.
Lezione 5 (Martedì 6
ottobre 2015): Programmazione dinamica: il
calcolo dei numeri di Fibonacci (puoi consultare [DFI]). Principi della
programmazione dinamica (parr. 6.1 e 6.2).
Lezione 6 (Lunedì 12
ottobre 2015): Programmazione dinamica:
Selezione di intervalli pesati.
Lezione 7 (Martedì 13
ottobre 2015): Programmazione dinamica:
Allineamento di sequenze (par. 6.6). Esercizio di programmazione dinamica: il
problema della canoa. Esercizi consigliati sulla programmazione dinamica da questo elenco
ed es. 1 pag. 312 di [KT].
Lezione 8 (Lunedì 19
ottobre 2015): Programmazione dinamica:
Somma di Sottoinsiemi e il problema dello zaino (par. 6.4). Esercizi.
Lezione 9 (Martedì 20
ottobre 2015, ore 16-18): Programmazione dinamica: Struttura secondaria dell’RNA (par. 6.5).
Osservazioni conclusive sulla tecnica e sulla proprietà della sotto struttura
ottima. Si consiglia di svolgere gli esercizi da questo elenco (es. fino al 23).
Lezione 10 (Lunedì 26
ottobre 2015): Esercitazione sulla
programmazione dinamica: esercizio 2 dell’elenco.
Lezione 11 (Martedì 27
ottobre 2015): Esercitazione: problema
dello zaino e sue varianti. Problema dello zaino frazionario e metodo greedy.
Lezione 12 (Lunedì 2
novembre 2015): Metodo greedy:
il problema della selezione di intervalli. Il problema del partizionamento di
intervalli e della selezione che minimizza il ritardo (par. 4.1).
Lezione 13 (Martedì 3
novembre 2015): Metodo
greedy: il problema della selezione che minimizza il
ritardo (par. 4.2). Esercizio: cambio di monete.
Lezione 14 (Lunedì 9
novembre 2015): Test di valutazione (1)
sul programma fino alla programmazione dinamica e correzione. Codici
univocamente decifrabili e compressione di dati (par. 4.8).
Lezione 15 (Martedì 10
novembre 2015): Algoritmo di Huffman
per la ricerca dei codici ottimali. Correttezza dell’algoritmo di Huffman (par. 4.8).
Lezione 16 (Lunedì 16
novembre 2015): 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 17 (Martedì 17
novembre 2015): Visite BFS e DFS: implementazioni. 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).
Lezione 18 (Lunedì 23
novembre 2015): 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 (Martedì
24 novembre 2015): 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 (Lunedì 30
novembre 2015): Test di valutazione (2) su tecnica greedy
e grafi. 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 (Martedì 1
dicembre 2015, 13:30?-16): Problema del flusso: algoritmo di Ford-Fulkerson
e sua correttezza (parr. 7.1, 7.2).
Lezione 22 (recupero del 7/12)
(Venerdì 4 dicembre 2015,
ore 15-17 F8): Applicazione dell’algoritmo di Ford-Fulkerson al problema del matching
su grafi bipartiti (par. 7.5). Esercizio alla lavagna: dato un grafo, testare
se è bipartito, se sì, trovare matching massimale.
Lunedì 7 dicembre 2015: Ponte
Martedì 8 dicembre 2015: Festività dell’Immacolata Concezione
Esercitazione supplementare (Venerdì 11 dicembre 2015, ore 12-14 F8): Esercitazione
in preparazione agli esami: esercizio 1 p. 312 del [KT]; es. 4 dell’appello del
13/01/14 (MST).
Lezione 23 (Lunedì 14
dicembre 2015): Algoritmi intelligenti di ricerca esaustiva:
backtracking e branch-and-bound.
. ([DPV] par. 9.1).
Lezione 24 (Martedì 15 dicembre 2015):
Test
di valutazione (3) su grafi, flusso e algoritmi esaustivi. Esercitazione finale: es. 4
dell’appello del 15/07/14 (listello); es. 3 dell’appello del 22/06/15 (MaxST).
Eventuali altre ore di
recupero potranno essere svolte il venerdì dalle 15 alle 17
in aula F1 o nel laboratorio P13.
Nota: Da quest’anno il corso di Algoritmi è disattivato. Gli studenti che lo hanno nel proprio
piano di studio e non hanno ancora superato l’esame, sosterranno l’esame di
Progettazione di Algoritmi.