| | | corso | | | | |
Algoritmica B
Codice: | AA006 | Crediti: | 9 | Semestre: | 1 | Sigla: | ALG | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Roberto Grossi
Tel. 0502212793Prerequisiti
- Conoscenza di un linguaggio di programmazione (Pascal, C, C++ o Java).
- 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).
- Per maggiori dettagli ed esercizi di verifica, visitare la pagina Web dei prerequisiti.
Obiettivi di apprendimento
Definire formalmente la nozione di algoritmo e di modello di calcolo.
Caratterizzare i dati da elaborare, organizzandoli e strutturandoli
nel modo più opportuno al fine di agevolarne l'uso da parte
degli algoritmi. Progettare algoritmi corretti (che risolvono
cioè sempre e solo il problema a cui si è interessati)
ed efficienti (cioè che lo risolvono il più velocemente
possibile o usano il minor spazio di memoria possibile), attraverso
l'esame di diversi paradigmi. Studiare le limitazioni inerenti dei
problemi da risolvere, in particolare di quelli la cui soluzione
richiede l'esame di tutte le possibilità.
Descrizione
Introduzione ai modelli di calcolo, all'analisi e alla
complessità degli algoritmi. Algoritmi ricorsivi e relazioni di
ricorrenza. Algoritmi di ordinamento. Strutture dati elementari e
avanzate. Algoritmi su grafi e stringhe. Enumerazione e non
determinismo. Problemi P, NP, RP, e NP-completi.
English Description
Introduction to the design, analysis and computation complexity of
algorithms and data structures. Basic techniques for the analysis of
algorithms. Design paradigms for efficient algorithms. Definition and
application of main and advanced data structures. Algorithms on graphs
and strings. Complexity of computationally hard problem
Programma
- Analisi di Algoritmi e Complessità
- Introduzione alla complessità di calcolo
- Ordini di grandezza delle funzione
- Algoritmi ricorsivi: Numeri di Fibonacci, Ricerca Binaria,
Mergesort, Moltiplicazione rapida, Moltiplicazione di matrici.
- Relazioni di ricorrenza
- Limiti inferiori alla complessità
- Progetto di Algoritmi e Strutture dei Dati
- Code, Pile, Heap
- Heapsort
- Quicksort
- Ordinamento in tempo lineare
- Tabelle hash
- Alberi binari di ricerca
- Grafi: rappresentazione e visite
- Stringhe: ricerca esatta e approssimata
- Classi di Complessità
- Enumerazione e non determinismo
- Classi P, NP, NPC, RP
- Algoritmi randomizzati
- Modelli di Calcolo e Calcolabilità
- Indecidibilità e universalità
- Macchina di Turing
- Equivalenza tra modelli di calcolo
Bibliografia
- [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest,
C. Stein.
Introduction to algorithms, MIT Press, second edition, 2001.
Sito Web ed
errata-corrige.
[Edizione più recente.]
- [CLR] T. H. Cormen, C. E. Leiserson, R. L. Rivest.
Introduzione agli algoritmi, Jackson Libri,
2000. [Fuori catalogo... disponibile in biblioteca.]
- [L] F. Luccio, La struttura degli Algoritmi,
Boringhieri, 1982. [Fuori catalago... disponibile in biblioteca.]
- Dispenze distribuite a lezione.
Modalità di esame
- L'esame consiste in una prova scritta e in una prova orale.
- Durante la prova scritta o le verifiche intermedie è
vietato portare e consultare libri o appunti.
- Il superamento di entrambe le verifiche intermedie consente
l'esonero dalla prova scritta per la sola sessione invernale, per cui
l'orale va sostenuto entro tale sessione (come da
regolamento didattico).