Algoritmica e laboratorio
| Algoritmica I | |
|---|---|
| Sigla Corso: | ALL |
| Nome Docente/i: | Paolo Ferragina Roberto Grossi |
| Corso di laurea: | Informatica |
| Anno di corso: | 1 |
| Home page del corso: | ALL-A su dokuWiki ALL-B su dokuWiki |
Indice |
Programma
Obiettivi didattici
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.Saranno introdotte inoltre alcune tecniche per valutare le prestazioni degli algoritmi, o le limitazioni inerenti del calcolo. Infine si svolgerà una intensa attività di laboratorio che porterà a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.
Prerequisiti
Conoscenza del linguaggio C; Dimestichezza con l'uso dei puntatori e della ricorsione; Nozioni matematiche: proprietà e limiti di funzioni, sommatorie, numeri di Fibonacci, permutazioni, coefficienti binomiali, aritmetica modulare, numeri primi, metodi di dimostrazione (per induzione, per assurdo, per casi).
Programma completo
- Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
- Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, albero di decisione, limiti superiori e inferiori, caso pessimo e caso medio.
- 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.
- Oridnamento 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: rappresentazione, visita (DFS e BFS), DAG e ordinamento topologico, albero di copertura minimo, cammini minimi, componenti (fortemente) connesse.
Bibliografia
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms. MIT Press, third edition, 2009
- P. Crescenzi, G. Gambosi, R. Grossi, Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2005
Approfondimenti
Modalità di esame
L'esame consiste di tre prove:
- 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 di laboratorio.
- 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 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.
NOTA: Se si passa lo scritto e non il laboratorio si dovrà risostenere soltanto la prova di laboratorio.
Materiale aggiuntivo
Vecchi esami
Commenti
Corso molto interessante ed istruttivo. Professore chiarissimo nelle spiegazioni e molto disponibile.
