Strumenti Utente

Strumenti Sito


informatica:all-b:algob_10:start

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: 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

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

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 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.

FAQ

(ancora non attivo)

Programma del corso

  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.

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
informatica/all-b/algob_10/start.txt · Ultima modifica: 04/10/2015 alle 10:12 (4 anni fa) da Roberto Grossi