Risultati dello scritto del 16.02.2011:

   252011   INS
   423939   22
   452093   22
   452755   27
   454901   23
   454964   19

Hanno superato il laboratorio del 17.02.2011:

   452755
   433003
   454901

Risultati dello scritto dell'1.02.2011:

   439043   18
   439049   22
   454901   INS
   460073   19
   472005   30

Hanno superato il laboratorio del 2.02.2011:

   438911
   439049
   443831
   452456
   453884
   472005

Risultati dello scritto del 13.09.2010

   438911    18
   439043    INS
   439049    19
   443831    24
   452223    22
   453862    26
   454969    25
   PIU       INS
   

Hanno superato il laboratorio del 13.09.2010:

   440471
   453862
   454969     

Risultati dello scritto del 13.07.2010 (testo algo1_100713_soluzioni.pdf)

   422155    INS
   438547    27
   438911    INS
   439043    INS
   439049    INS
   440471    20
   451089    28
   451325    28
   451449    INS
   452223    INS
   452465    22
   452755    18
   453861    26
   460073    INS

Hanno superato il laboratorio del 14.07.2010:

   425019
   451089
   451325
   452465
   

Risultati dell'appello del 22 giugno 2010: gli studenti che non figurano nell’elenco hanno riportato una votazione insufficiente.

   Anzalone 25 
   Arizzi 26 
   Barbasso 27 
   Cacciamano 25 
   Casalena 23 
   Ceccotti 18 
   Conte 28 
   Conticelli 19 
   Fumia 18 
   Marchese 19 
   Mascellani 26 
   Mosca 18 
   Palmucci 18 
   Solinas 19 
   Venturini 24

Hanno superato il laboratorio del 23 giugno 2010:

   441923
   456568
   442725
   448460
   440911
   437653
   437319
   440317

Testo e soluzioni della verifica dell'8 aprile 2010 20100408.pdf

Testo e soluzioni della verifica del 24 maggio 2010 20100524.pdf

Voti finali delle due verifche (incrementati di 3):

   425019          24 
   441923          29
   451371          30 
   452173          27 
   452709          25 
   453841          21  
   454413          27 

Hanno superato il laboratorio del 31 maggio 2010:

   438547
   451371
   452173
   452709
   453841
   454413

Informazioni riguardo ai risultati di esami precedenti sono disponibili alla pagina Vecchi risultati

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.

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.

Le faq si trovano sulla loro (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.