| | | | corso | | |
Algoritmica A
Codice: | AA006 | Crediti: | 9 | Semestre: | 1 | Sigla: | ALG | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Paolo Ferragina
Tel. 0502212764Obiettivi 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 problems.
Programma
- Analisi di Algoritmi e Complessità
- Introduzione alla complessità di calcolo [CLR 1]
- Ordini di grandezza delle funzione [CLR 2]
- Algoritmi ricorsivi: Numeri di Fibonacci, Ricerca Binaria,
Mergesort, Moltiplicazione rapida, Moltiplicazione di matrici.[L 5]
- Relazioni di ricorrenza [CLR 4]
- Limiti inferiori alla complessit\`a [L 4.2]
- Progetto di Algoritmi e Strutture dei Dati
- Code, Pile, Heap [CLR 7]
- Heapsort [CLR 7]
- Quicksort [CLR 8]
- Ordinamento in tempo lineare [CLR 9]
- Tabelle hash [CLR 12]
- Alberi binari di ricerca [L 5]
- Grafi: rappresentazione e visite [CLR 23]
- Stringhe: ricerca esatta e approssimata [CLR 34]
- Classi di Complessità
- Enumerazione e non determinismo [dispense]
- Classi P, NP, NPC, RP [CLR 36]
- Algoritmi randomizzati [dispense]
- Modelli di Calcolo e Calcolabilità
- Indecidibilità e universalità [dispense]
- Macchina di Turing [dispense]
- Equivalenza tra modelli di calcolo [dispense]
Bibliografia
[CLR] T. H. Cormen, C. E. Leiserson, R. L. Rivest "Introduzione agli
algoritmi". Jackson Libri 1999.
[L] F. Luccio "La struttura degli Algoritmi". Boringhieri 1982.
Modalità di esame
Scritto e orale