Anno Accademico 2001/2002
Corsi di Studio in Informatica
Università degli Studi di Pisa
I anno (9 crediti), Corso B
AVVISI
CALENDARIO
|
Data |
Ora |
|
|
Data |
Ora |
|
|
Data |
Ora |
1 |
18 Feb |
9.00 |
|
12 |
15 Mar |
11.00 |
|
23
|
23 Apr |
9.00 |
2 |
19 Feb |
9.00 |
|
13 |
22 Mar |
11.00 |
|
24
|
26 Apr |
11.00 |
3 |
21 Feb |
14.00 |
|
14 |
25 Mar |
9.00 |
|
25
|
29 Apr |
9.00 |
4 |
22 Feb |
11.00 |
|
15 |
26 Mar |
9.00 |
|
26
|
30 Apr |
9.00 |
5 |
4 Mar |
9.00 |
|
16
|
9 Apr |
9.00 |
|
27
|
2 Mag |
14.00 |
6 |
5 Mar
|
9.00 |
|
17
|
11 Apr |
14.00 |
|
28
|
3 Mag |
11.00 |
7 |
7 Mar |
14.00 |
|
18
|
15 Apr |
9.00 |
|
29
|
6 Mag |
9.00 |
8 |
8 Mar |
11.00 |
|
19 |
16 Apr |
9.00 |
|
30 |
7 Mag |
9.00 |
9 |
11 Mar |
9.00 |
|
20 |
18 Apr |
14.00 |
|
31 |
9 Mag |
14.00 |
10 |
12 Mar |
9.00 |
|
21 |
19 Apr |
11.00 |
|
32 |
10 Mag |
11.00 |
11 |
14 Mar |
14.00 |
|
22 |
22 Apr |
9.00 |
|
33
|
13 Mag
|
9.00
|
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à [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]
- Liste e alberi [H 16]
- Alberi binari di ricerca [B 8.1, 8.2]
- Grafi: rappresentazione e visite [CLR 23]
Classi di Complessità:
- Enumerazione e non determinismo [B 17]
- Classi P, NP, NPC [B 18]
- Algoritmi randomizzati [B 20]
Modelli di Calcolo e
Calcolabilità:
- Indecidibilità e universalità [B 25]
- Macchina di Turing [B 26]
- Equivalenza tra modelli di calcolo [dispense]
TESTI
- [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, seconda edizione, 2000.
- [H] C. S. Horstmann, Concetti di informatica e
fondamenti di Java 2,
Apogeo 2000.
- [L] F. Luccio, La struttura degli Algoritmi,
Boringhieri 1982.
- [G] R. Grossi, Cenni su rappresentazione
dei dati elementari,
operazioni
elementari a costo unitario e costo
computazionale
dei costrutti in pseudocodice.
Cancellazione
da uno heap.
Analisi dello hash con liste concatenate.
Inserzione in un 2-3-albero.
Esercizi e animazione di alcuni algoritmi. 2000-2002.
PROGRAMMA DEGLI ANNI PRECEDENTI
MISCELLANEA