DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== 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}}|