Recupero della prova d'esame dell'1.2.2012 a causa del maltempo. La prova di esame scritto si svolgerà alle ore 10:00 del 7.2.2012 in aula D; quella di laboratorio si svolgerà alle ore 14:00 del 7.2.2012 in aula H. Importante: tale recupero è riservato agli studenti iscritti alla prova dell'1.2 (nel calendario degli appelli della sezione didattica del sito www.di.unipi.it) ma impossibilitati a partecipare a causa del maltempo. Per eventuali chiarimenti, contattare il prof. Grossi via email.

Riunione per fissare il calendario orali. A parte i pochi che rientrano nel caso sopra, per tutti gli altri candidati l'appuntamento è fissato in data 6.2.2012 alle ore 09:00 presso il mio studio: lo scopo è quello di svolgere l'esame orale per chi vuole sostenerlo in giornata e fissare il calendario degli orali per chi vuole sostenerlo successivamente.

Docente: Roberto Grossi

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.

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 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à il cui superamento permette allo studente di essere ammesso a sostenere la prova scritta.
• 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, nel qual caso lo studente è ammesso a sostenere la prova orale.
• Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.

IMPORTANTE per gli studenti della Classe 26: possono sostenere la sola prova scritta di AlL come scritto dell'esame di Algoritmica (vecchio corso) e devono contattare la prof. Pagli per la verbalizzazione; la prova di laboratorio LLS dovrà essere svolta con il dott. Gervasi.

Un centinaio di esercizi sono reperibili presso le vecchie pagine del corso

http://www.di.unipi.it/~grossi/ALG/

http://www.di.unipi.it/didadoc/asd1/page6.html

esamelab110912.pdf

• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2006.
  • CAPITOLI DA STUDIARE PER L'ESAME: Capitolo 1 (tutto), Capitolo 2 (tranne i paragrafi 2.5.2, 2.6), Capitolo 3 (tranne i paragrafi 3.2, 3.4.2, 3.4.3), Capitolo 4 (tranne i paragrafi 4.2, 4.3.2, 4.3.3, 4.3.4, 4.4), Capitolo 5 (tranne i paragrafi 5.5 e 5.6.2), Capitolo 6 (solo il paragrafo 6.1), Capitolo 7 (tranne i paragrafi 7.2 e 7.5.2), Capitolo 8 (tutto), Capitolo 9 (solo il paragrafo 9.1).
  • Per approfondimenti ed errata: http://www.algoritmica.org/sda/pmwiki.php
• Per il laboratorio: B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.

• 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 e i puntatori. 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 suggeriamo il compilatore e il debugger disponibili con MinGW, e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. 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 AIL), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.

(ancora non attivo)

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.
9. Problema dei matrimoni stabili e sottosequenza di somma massima.
10. Programmazione dinamica: LCS, Partizione e Zaino
11. Generazione di combinazioni e permutazioni
12. Greedy: Huffman e Zaino
13. Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
14. Alberi: rappresentazione e visite.
15. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto), trie.
16. Strutture dati randomizzate: Skip List.
17. Algoritmi randomizzati: Quicksort, Karp-Rabin.
18. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
19. Grafi II: albero di copertura minimo, cammini minimi, componenti (fortemente) connesse.

Disponibile su Unimap