Algoritmica e Laboratorio - Corso B

Docenti Teoria/Esercitazioni: Anna Bernasconi (corso B) e Paolo Ferragina (corso A)

Docenti Laboratorio: Andrea Marino, Giovanna Rosone, Rossano Venturini

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. Il corso consiste ogni settimana di tre lezioni di didattica frontale in aula e di una esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Semestre: secondo.

Ricevimento studenti: mercoledì, 11-13, ufficio BERNASCONI (per ricevimento in orari diversi da quanto previsto inviare e-mail a [email protected]), fino a mercoledì 14 giugno. Dal 19 giugno il ricevimento sarà SOLO SU APPUNTAMENTO.

• A.A. 2015/2016
• A.A. 2014/2015
• A.A. 2013/2014

Si pregano gli studenti che dispongono di un portatile di portarlo in Laboratorio.

L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.

L'esame consiste di tre prove:

• Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18.
• Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un test di idoneità.
• Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.
• Le prove possono essere sostenute in appelli diversi.
• LA PROVA ORALE E QUELLA DI LABORATORIO POSSONO ESSERE SOSTENUTE IN QUALUNQUE ORDINE E SOLO DOPO AVER SUPERATO LA PROVA SCRITTA.
• Se la prova orale non viene superata, occorre ripetere soltanto quella.
• SE LA PROVA DI LABORATORIO NON VIENE SUPERATA PER DUE VOLTE CONSECUTIVE, OCCORRE RIPETERE TUTTE LE PROVE GIA' SOSTENUTE.
• Chiaramente la registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo.

Per avere una idea della tipologia delle prove, si consultino i testi dell'anno scorso.

Prossime date per la prova scritta:

Prossime date per la prova di laboratorio:

Prossime date per le prove orali:

• [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.
• [DFI] C. Demetrescu, I. Finocchi, G. Italiano. Algoritmi e strutture dati. McGraw-Hill, Seconda edizione, 2008. Solo pagine 161-166.
• [CGGR] P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione). Pearson, 2012. Solo pagine 87-96.
• [BFL] A. Bernasconi, P. Ferragina, F. Luccio. Elementi di Crittografia . Pisa University Press, 2015. Solo il capitolo 3.

Per il laboratorio, un testo fra:

• [KR] B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.
• [KP] A. Kelley, I. Pohl. C: Didattica e Programmazione, Addison-Wesley, quarta edizione, 2004.

• Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
• Strumenti per la programmazione: Un editore testuale (tipo Emacs), e il compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.
• Sistema di Autovalutazione: http://algo1617.dijkstra.di.unipi.it/

1. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
2. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
3. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
4. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
7. Ordinamento di interi: Counting sort, Radix Sort.
8. Ordinamento di stringhe: qsort-based.
9. Sottosequenza di somma massima.
10. Programmazione dinamica: LCS, Partizione e Zaino
11. Algoritmi randomizzati: Quicksort.
12. Generazione di combinazioni e permutazioni
13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
14. Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto).
15. Alberi: rappresentazione e visite.
16. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
17. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
18. Grafi III: Minimum Spanning Tree e Shortest Path.