Esame orale: sabato 14.9 ore 10 e martedì 20 ore 18.

Risultati dello scritto del 9.9.2011:

   441800   suff
   463763   ins
   464879   20
   466905   venire a vedere la correzione
   467101   20
   467641   ins
   468087   suff
   470199   25
   473029   22

Hanno superato il laboratorio del 12.9.2011:

   464885
   441389
   470199

Risultati dello scritto del 7.7.2011:

   422257   ins
   441761   ins
   464587   ins
   465077   22
   466759   27
   466905   ins
   467101   ins
   470199   ins

Hanno superato il laboratorio dell'8.7.2011:

   464879
   466759

Risultati dello scritto del 21.6.2011:

   422257   ins
   441389   20
   441800   ins
   451351   20
   453089   suff
   457989   20
   463763   ins
   464587   ins
   465169   ins
   466089   24
   466905   ins
   471565   25
   473029   ins

Hanno superato il laboratorio del 22.6.2011:

   439043
   451051
   451351
   452068
   452093
   452853
   453845
   454089
   454964
   460073
   464229
   464247
   464561
   466089
   468405
   468827
   471565
   472131

Risultati dello scritto del 6.6.2011:

   437435   21
   441800   ins
   444043   suff
   444151   suff
   451051   21
   451449   27
   452068   24
   452826   24
   452853   21
   453089   ins
   453845   21
   454089   suff
   457989   ins
   463763   ins
   464091   24
   464229   30-
   464247   27
   464433   suff
   464561   24
   464587   ins     
   464879   suff
   464885   suff
   466759   suff
   466905   ins
   468405   suff
   468827   suff
   469299   27
   472131   27

Hanno superato il laboratorio del 15.6.2011:

   437666
   442988
   443136
   451842
   456464
   456796
   459248
   464091
   466632
   466766
   469528
   421500
   437435
   444151
   451742
   464262
   467680
   469299
   471062
   471122

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

• 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