Algoritmica e Laboratorio - Corso B

Questo corso non e' piu' erogato per cambio ordinamento: questa pagine contiene tuttavia tutte le informazioni per sostenere l'esame per gli iscritti al vecchio ordinamento.

Docenti Teoria/Esercitazioni: Nadia Pisanti, Anna Bernasconi

Docenti Laboratorio: Anna Bernasconi, Giulio Pibiri, 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.

A.A. 2019-2020: La didattica frontale e' stata sospesa dal 5 Marzo 2020.
Di conseguenza, le lezioni teoriche dal 5 Marzo sono state svolte on-line e registrate e sono disponibili per gli studenti mediante link in questa pagina web nella sezione “Registro delle Lezioni”. Nella stessa sezione, per tutte le lezioni e' disponibile una versione .pdf della lavagna.

• A.A. 2018/2019
• A.A. 2017/2018
• A.A. 2016/2017
• A.A. 2015/2016

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 in due prove obbligatorie che possono essere sostenute anche in appelli diversi:

• Una prova di Laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi. La prova avra’ luogo sulla consueta piattaforma d’esame accessibile via browser nelle date indicate sul portale esami di ateneo, e sara’ validata da un colloquio orale immediatamente successivo. Tale prova è da intendersi come un test di idoneità e l'iscrizione deve essere fatta sul portale esami.
• Una prova orale sul programma del corso la cui valutazione finale è in trentesimi, atta a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente; le date sono indicate in questa pagina web e l'iscrizione è da farsi via mail entro le scadenza indicate per ogni data.
• La prova orale puo' essere sostenuta da chiunque, anche senza aver superato il laboratorio.
• Precisazioni (a grande richiesta):
  • Se la prova orale non viene superata, occorre ripetere soltanto quella.
  • Se la prova di laboratorio non viene superata, occorre ripetere soltanto quella.
  • Ovvero: chi supera una prova (scritta o di laboratorio) non dovra' mai piu' ripeterla: vale per sempre.
  • Chi avesse gia' superato lo scritto in passato puo' sostenere direttamente la prova di laboratorio (e, se superata, si contatti il docente per la verbalizzazione).

Istruzioni piu’ dettagliate verranno fornite via mail agli iscritti alle prove. Per questo motivo, e per la necessita’ nelle nuove condizioni di organizzare al meglio le prove, l’iscrizione e’ tassativamente obbligatoria.

Le date delle prove di laboratorio sono sul portale esami e l'iscrizione deve avvenire sul portale

Le date delle prove orali sulla teoria sono le seguenti e l'iscrizione (obbligatoria) deve avvenire per mail nelle modalita' indicate:

Per ogni data sono riportati i numeri di matricola degli iscritti alla prova.

• [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.
• Materiale didattico di supporto per il laboratorio
• Altro materiale di supporto per il laboratorio preparato da uno studente
• Sistema di Autovalutazione: http://algo1920.dijkstra.di.unipi.it/

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