====== Algoritmica e Laboratorio - Corso B ====== \\ ====== News ====== ** 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. ====== 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ì | 9-11 | A | Teoria | |Martedì | 9-11 | A | Teoria | |Mercoledì | 9-11 | A | Teoria | |Giovedì | 9-11 | H | Laboratorio | \\ ====== 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. __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 {{:informatica:all-b:algob_10:esamelab110912.pdf|}} \\ | Appelli di esame| Note | | 11.01.2012 ore 9:00 (scritto) | 11.01.2012 ore 15:00 (prova di laboratorio in aula H) | | 01.02.2012 ore 9:00 (scritto) | 01.02.2012 ore 15:00 (prova di laboratorio in aula M) | ====== 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 ===== (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 ===== [[http://unimap.unipi.it/registri/printregistriNEW.php?re=50979::::&ri=5777|Disponibile su Unimap]] ===== 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]. {{:informatica:all-b:algob_10:lez1.pdf|Lucidi}}} | | 08/3/11 | **Laboratorio**: Ripasso e esercizi su funzioni e puntatori. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:algob_10:lez2.pdf|Lucidi}} | | 10/3/11 | **Laboratorio**: Ripasso e esercizi su passaggio dei parametri. | {{:informatica:all-b:algob_10:lez3.pdf|Lucidi}} | | 10/3/11 | **Laboratorio**: Ripasso e esercizi su allocazione dinamica della memoria e gestione di stringhe. | {{:informatica:all-b:algob_10:lez4.pdf|Lucidi}} | | 24/3/11 | **Laboratorio**: Redirezione dell'input e timing di un programma. Problema del sottoarray di somma massima. | {{:informatica:all-b:algob_10:test_maxsum.zip|Test}} {{:informatica:all-b:algob_10:code5.zip|Soluzioni}}| | 31/3/11 | **Laboratorio**: Insertion Sort su Interi e Stringhe. Per casa: Implementare Merge Sort e Ricerca Binaria. | {{:informatica:all-b:algob_10:lez6.pdf|Esercizi}} {{:informatica:all-b:algob_10:code6.zip|Soluzioni}}| | 07/4/11 | **Laboratorio**: QuickSort su Interi e Stringhe. | {{:informatica:all-b:algob_10:lez7.pdf|Esercizi}} {{:informatica:all-b:algob_10:code7.zip|Soluzioni}}| | 14/4/11 | **Laboratorio**: Qsort su Interi e Stringhe. | {{:informatica:all-b:algob_10:lez8.pdf|Esercizi}} {{:informatica:all-b:algob_10:code8.zip|Soluzioni}}| | 28/4/11 | **Laboratorio**: Le struct in C e esercizi con le liste. | {{:informatica:all-b:algob_10:liste.pdf|Lucidi}} {{:informatica:all-b:algob_10:lez9.pdf|Esercizi}}| | 12/5/11 | **Laboratorio**: Alberi Binari di Ricerca. |{{:informatica:all-b:algob_10:lez11.pdf|Esercizi}} {{:informatica:all-b:algob_10:code11.zip|Soluzioni}}| | 19/5/11 | **Laboratorio**: Funzioni Hash. |{{:informatica:all-b:algob_10:lez12.pdf|Esercizi}} {{:informatica:all-b:algob_10:eserciziliste.pdf|Esercizi Aggiuntivi Liste}} {{:informatica:all-b:algob_10:code12.zip|Soluzione}}| | 26/5/11 | **Laboratorio**: Simulazione della prova di esame. |{{:informatica:all-b:algob_10:prova.pdf|Testo}}|