====== Algoritmica e Laboratorio - Corso B ====== \\ ====== News ====== 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 {{:informatica:all-b: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 {{:informatica:all-b:20100408.pdf|}} Testo e soluzioni della verifica del 24 maggio 2010 {{:informatica:all-b: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 [[informatica:all-b:risultatiVecchi|Vecchi risultati]] ====== Informazioni Generali ====== **Docente**: [[http://www.di.unipi.it/~grossi/|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ì | 11-13 | A | Teoria | |Martedì | 11-13 | H | Laboratorio | |Giovedi' | 11-13 | A | Teoria | |Venerdi' | 9-11 | B | Teoria | \\ ====== Obiettivi del Corso ====== {{:informatica:all-b:alk.gif?90|Al Kowarizmi}} 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. ===== 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 \\ ====== 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 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 [[http://www.eclipse.org/|Eclipse]] esteso con il suo plug-in [[http://www.eclipse.org/cdt/|Eclipse C/C++ Development Tooling]]. Per chi si trova a operare sotto Windows suggeriamo il compilatore e il debugger disponibili con [[http://www.mingw.org/|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. ===== FAQ ===== Le faq si trovano sulla loro (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 del Laboratorio ===== ^ Data ^ Argomento ^ Rif. Biblio ^ | 22/2/10 | **Laboratorio**: Basi del C e di compilazione sotto Unix. Struttura base del programma, blocchi condizionali e cicli, input/output, array. | [[http://www.di.unipi.it/~aorlandi/algo/es1.pdf|Esercizi]] | | 23/02/10 (matt) | **Laboratorio**: Puntatori, funzioni e passaggio parametri. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-a:lez2_230210.pdf|slides}}| | 23/02/10 (pom) | **Laboratorio**: Esercitazione. | {{:informatica:all-a:lez3_230210.pdf|slides}} | | 25/02/10 | **Laboratorio**: Allocazione dinamica della memoria (malloc), stringhe, vettori bidimensionali. | | 26/02/10 | **Laboratorio**: Esercitazione in aula. | | 02/03/10 | **Laboratorio**: Ricerca del maggioritario quadratica e lineare (soluzione lin. in aula). //Esercizi:// implementazione del sottosegmento di somma massima cubico, quadratico e lineare. | {{:informatica:all-a:all09:lez5.pdf|Esercizi}}, {{:informatica:all-b:maj.pdf|Appunti}} e {{:informatica:all-b:lez5.zip|soluzione lineare}} | | 08/03/10 | **Laboratorio**: Utilizzo di //time//, redirezione, doubling in lettura. Calcolo del numero di elementi distinti in un array ordinato. | {{:informatica:all-a:all09:lez6.pdf|Esercizi}}, {{:informatica:all-a:all09:code6.zip|Codice}} e {{:informatica:all-a:all09:testfile6.zip|Test cases}} | | 16/03/10 | **Laboratorio**: Insertion sort su interi e stringhe. Confronto con mergesort e ibrido merge/insertion sort | {{:informatica:all-b:lez7.pdf|Esercizi}} {{:informatica:all-b:isort_soluz.zip|Soluzioni commentate}} | | | 13/04/10 | **Laboratorio**: qsort() | {{:informatica:all-b:qsort.pdf|Slides e esercizi}} {{:informatica:all-b:qsort_soluz.zip|Soluzioni commentate}} | | | 20/04/10 | **Laboratorio**: Liste | {{:informatica:all-b:liste.pdf|Slides e esercizi}} {{:informatica:all-b:liste_soluz.zip|Soluzioni commentate}} | | 27/04/10 | **Laboratorio**: Liste e ddd | | | 04/05/10 | **Laboratorio**: Alberi e primo esempio di meccanismo d'esame. | {{:informatica:all-b:lez10.pdf|Esercizi}} e {{:informatica:all-b:lez10.zip|Soluzioni commentate}} | | 11/05/10 | **Laboratorio**: Grafi e visite. Altro esempio di meccanismo d'esame. | {{:informatica:all-b:lez11.pdf|Esercizi}} e {{:informatica:all-b:lez11.zip|Soluzioni commentate}} |