Algoritmica

Linda Pagli      Tel. 0502212735

1. Analisi di Algoritmi e Complessità

1.1 Introduzione alla complessità di calcolo [CLR 1]
1.2 Ordini di grandezza delle funzione [CLR 2]
1.3 Algoritmi ricorsivi: Numeri di Fibonacci, Ricerca Binaria, Mergesort, Moltiplicazione rapida, Moltiplicazione di matrici.[L 5]
1.4 Relazioni di ricorrenza [CLR 4]
1.5 Limiti inferiori alla complessità [L 4.2]

2. Progetto di Algoritmi e Strutture dei Dati

2.1 Code, Pile, Heap [CLR 7]
2.2 Heapsort [CLR 7]
2.3 Quicksort [CLR 8]
2.4 Ordinamento in tempo lineare [CLR 9]
2.5 Tabelle hash [CLR 12]
2.6 Liste e alberi [H 16]
2.7 Alberi binari di ricerca [B 8.1, 8.2]
2.8 Grafi: rappresentazione e visite [CLR 23]

3. Classi di Complessità

3.1 Enumerazione e non determinismo [B 17]
3.2 Classi P, NP, NPC [B 18]
3.3 Algoritmi randomizzati [B 20]

4. Modelli di Calcolo e Calcolabilità

4.1 Indecidibilit\`a e universalità [B 25]
4.2 Macchina di Turing [B 26]
4.3 Equivalenza tra modelli di calcolo [dispense]

[B] A. Bertossi "Algoritmi e Strutture di Dati". Utet 2000.
[CLR] T. H. Cormen, C. E. Leiserson, R. L. Rivest "Introduzione agli algoritmi". Jackson Libri 1999.
[H] C. S. Horstmann "Concetti di informatica e fondamenti di Java 2". Apogeo 2000.
[L] F. Luccio "La struttura degli Algoritmi". Boringhieri 1982.

Scritto e orale