Algoritmica e Laboratorio - Corso A

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

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 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Semestre: secondo.

Ricevimento studenti: lunedì 9-12 e su appuntamento. Eventuali variazioni di orario sulle lezioni e/o ricevimento, o comunicazioni sul corso verranno segnalate tramite Twitter all'account @FerraginaTeach

Registro delle lezioni: si tratta del registro ufficiale che riporta quanto indicato nel seguito.

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, ma 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 già sostenute.
• La registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo, e questo potrà avvenire in qualunque appello durante la prova orale.

Per avere una idea della tipologia delle prove, si consultino i testi degli anni scorsi.

Prossime date per la prova di laboratorio:

• [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-165.

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 “dell'esperto”.
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.