Questa è una vecchia versione del documento!
Indice
Algoritmica e Laboratorio - Corso B
News
Orali per il mese di agosto: mar 02.08.2011 ore 9 presso lo studio del docente: iscriversi agli orali sul foglio affisso sulla porta dello studio.
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
Informazioni Generali
Docente: Roberto Grossi
Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio.
Ricevimento studenti | |||
---|---|---|---|
Grossi | ore | giorno | Stanza 361, Dipartimento di Informatica |
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.
Orario delle Lezioni | |||
---|---|---|---|
Giorno | Orario | Aula (Corso B) | Tipologia |
Lunedì | 9-11 | A | Teoria |
Martedì | 9-11 | A | Teoria |
Mercoledì | 9-11 | A | Teoria |
Giovedì | 9-11 | H | Laboratorio |
Obiettivi del Corso
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.
Modalità di esame
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.
Esercizi e testi di esame
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
Appelli di esame | Note |
09.09.2011 ore 9 (scritto) | 12.09.2011 ore 14:30 (prova di laboratorio) |
Libro di testo
- 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.
Materiale per il Laboratorio
- 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 compilatoregcc
, 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 minimaleeditor+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.
FAQ
(ancora non attivo)
Programma del corso
- Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
- Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
- Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
- Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
- Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
- Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
- Ordinamento di interi: Counting sort, Radix Sort.
- Ordinamento di stringhe.
- Problema dei matrimoni stabili e sottosequenza di somma massima.
- Programmazione dinamica: LCS, Partizione e Zaino
- Generazione di combinazioni e permutazioni
- Greedy: Huffman e Zaino
- Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
- Alberi: rappresentazione e visite.
- Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto), trie.
- Strutture dati randomizzate: Skip List.
- Algoritmi randomizzati: Quicksort, Karp-Rabin.
- Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
- Grafi II: albero di copertura minimo, cammini minimi, componenti (fortemente) connesse.
Registro Elettronico delle Lezioni
Registro del Laboratorio
Data | Argomento | Rif. Biblio |
---|---|---|
07/3/11 | Laboratorio: Basi del C e di compilazione sotto Unix. Struttura base del programma, blocchi condizionali e cicli, input/output, array. | Cap. 2-3, 7.1-7.4 di [KR]. Lucidi} |
08/3/11 | Laboratorio: Ripasso e esercizi su funzioni e puntatori. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi |
10/3/11 | Laboratorio: Ripasso e esercizi su passaggio dei parametri. | Lucidi |
10/3/11 | Laboratorio: Ripasso e esercizi su allocazione dinamica della memoria e gestione di stringhe. | Lucidi |
24/3/11 | Laboratorio: Redirezione dell'input e timing di un programma. Problema del sottoarray di somma massima. | Test Soluzioni |
31/3/11 | Laboratorio: Insertion Sort su Interi e Stringhe. Per casa: Implementare Merge Sort e Ricerca Binaria. | Esercizi Soluzioni |
07/4/11 | Laboratorio: QuickSort su Interi e Stringhe. | Esercizi Soluzioni |
14/4/11 | Laboratorio: Qsort su Interi e Stringhe. | Esercizi Soluzioni |
28/4/11 | Laboratorio: Le struct in C e esercizi con le liste. | Lucidi Esercizi |
12/5/11 | Laboratorio: Alberi Binari di Ricerca. | Esercizi Soluzioni |
19/5/11 | Laboratorio: Funzioni Hash. | Esercizi Esercizi Aggiuntivi Liste Soluzione |
26/5/11 | Laboratorio: Simulazione della prova di esame. | Testo |