Corso
di Diploma in INFORMATICA
Università
di Pisa
Anno accademico 1998/99
tel. 050-887293 email: grossi@di.unipi.it Internet: http://www.di.unipi.it/~grossi |
Ogni lunedì alle ore 16:30-19:30 (luogo: stanza O-II-11 in Corso Italia 40). |
Scopi del corso:
|
|
Argomenti trattati:
Analisi di algoritmi e complessità (20 ore)
Dimensione dei dati di un problema. Ordini di grandezza delle funzioni. Caso pessimo, ottimo e medio. Complessità polinomiale e superpolinomiale. Limiti superiori e inferiori della complessità di un problema. Tecniche per la dimostrazione di limiti inferiori. Relazioni di ricorrenza: metodi di soluzione e teorema principale. Problemi computazionalmente difficili (5 ore)
|
Progetto di algoritmi (20 ore)
Divide et impera: Mergesort, Quicksort. Ricerca binaria. Moltiplicazione rapida. Ordinamento in tempo lineare. HeapSort. Verifica induttiva di proprietà su strutture dati. Strutture dati (35 ore)
|
GARA DI PROGRAMMAZIONE:
È attivata una gara di programmazione per la
realizzazione in TurboPascal 7.0 del più veloce algoritmo di
ordinamento basato sullo schema del QuickSort e delle sue
varianti. La realizzazione deve risultare in una procedura
procedure QS (var A: mioarray), dove mioarray = array
[1..N] of integer. Le procedure vanno spedite per e-mail entro le
ore 24:00 del 31 Maggio 1999 all'indirizzo: grossi@di.unipi.it. La gara
è valida se perverranno almeno 10 procedure. Nella stesura di
ciascuna procedura possono partecipare al più tre studenti di
ASD I (anche degli altri corsi A e B). Si prevedono ricchi premi per i
primi tre gruppi classificati. I file di riferimento sono i seguenti:
E' disponibile Free Pascal Win32 0.99.10 sulle macchine windows98. Vi si accede seguendo il seguente percorso: Start/Programs/Linguaggi/Free Pascal/FreePascal Manuals (documentazione html on-line) Start/Programs/Linguaggi/Free Pascal/Goto Bin Directory (shortcut che apre una shell dos nella directory degli eseguibili) E' stato attivato il link all'area comune asd1d disponibile da start menu di windows 98 in Programs/Linguaggi/asd1d ------------------------------------------------------------------------------ Ruggero Giordano System AdministratorLa gara avverrà alle ore 14:30 del 4/6 in Aula H del Polo Fibonacci. |
Orario delle lezioni e appelli di esame:
|
|
Riferimenti bibliografici e materiale didattico:
|
Testi di consultazione:
|
Modalità e tipologia d'esame:
|
Testi degli appelli precedenti e delle verifiche (anni 1996-98 a cura di A. Brogi):
|
|
|
Programma d'esame dettagliato:
Si consiglia di usare le versioni più recenti di Netscape e Internet Explorer abilitate a Java: se non supportano JDK1.1 possono dare problemi. Codice Java scritto da Pierluigi Crescenzi, Giancarlo Bongiovanni, Gaia Innocenti, Patrizia Pallai e Gabriella Rago © Copyright 1999. Per ulteriori animazioni di algoritmi e visualizzazione del loro codice Java, si vedano le pagine di Antonio Brogi. NOTA: Per non incorrere in possibili violazioni del copyright, si è ritenuto necessario limitare l'accesso ai link APPUNTI e MATERIALE. Sono pertanto consultabili solo da macchine appartenenti ai domini 131.114.4.* (Dipartimento di Informatica) e 131.114.11.* (Laboratori del Polo Fibonacci). |
N.ro | Data | Argomenti della lezione | Riferimenti ai testi |
1 | 15/02/99 | Organizzazione degli studenti in gruppi di lavoro | |
2 | 16/02/99 | Formalizzazione di un problema e dell'algoritmo risolutore. Esempio dell'Insertion Sort. | Par. 1.1 in [CLR] ANIMAZIONE |
3 | 17/02/99 | Modello RAM. Analisi dell'Insertion Sort. Caso pessimo e caso medio. Ordine di grandezza. Metodo Divide-et-Impera. Esempio del MergeSort. | Par. 1.2-1.3 in [CLR] ANIMAZIONE |
4 | 19/02/99 | Analisi del MergeSort. Complessità al caso pessimo. Applicazione dell'ordinamento: raggruppamento di parole aventi lo stesso anagramma. | Par. 1.3 in [CLR], Cap. 2 in [Be], APPUNTI |
5 | 22/02/99 | Notazione asintotica: "O grande", "Omega grande", "Teta grande". Proprietà transitiva, riflessiva, ecc. Soluzioni delle equazioni di ricorrenza nei metodi Divide-et-Impera: "master theorem". | Par. 2.1 e 4.3 in [CLR] |
6 | 23/02/99 | Funzioni tipiche della complessità: polinomiali, logaritmiche, esponenziali. Esempio di applicazione del "master theorem" al MergeSort. Dimostrazione della complessità del MergeSort mediante l'albero di ricorsione. Altro esempio di algoritmo di tipo Divide-et-Impera: la ricerca binaria. Realizzazione efficiente in Pascal. | Par. 2.2 e 4.2 in [CLR], par. 8.3 in [Be], APPUNTI |
7 | 24/02/99 | Applicazioni del "master theorem. Equazione di ricorrenza per la complessità della ricerca binaria: T(n) = T(n/2)+O(1). Equazione di ricorrenza per la ricerca del massimo: T(n) = 2 T(n/2) + O(1). Equazione di ricorrenza del tipo: T(n) = 2 T(n/2) + n2. Notazione e terminologia per gli alberi. | Par. 4.2-4.3 e 5.5 in [CLR], APPUNTI |
8 | 01/03/99 | Definizione e proprietà dello heap, con esempi. Esercizi sul metodo divide-et-impera e le equazioni di ricorrenza: calcolo del primo e secondo elemento; complessità dell'Insertion Sort rivisitata; moltiplicazione veloce di numeri a N cifre. | Par. 7.1 in [CLR], APPUNTI |
9 | 02/03/99 | Algoritmo di ordinamento HeapSort e sue procedure ausiliari, con esempi. | Par. 7.2-7.4 in [CLR] ANIMAZIONE |
10 | 03/03/99 | Analisi della complessità dello HeapSort. Coda di priorità realizzata mediante lo heap. Esercizio: esecuzione degli algoritmi Insertion Sort, MergeSort e HeapSort sulla sequenza d'ingresso [10, 70, 30, 50, 20, 60, 40, 80]. Esercizio: realizzazione dell'operazione di cancellazione nella coda di priorità. | Par. 7.3 e 7.5 in [CLR], APPUNTI, ANIMAZIONE-IS, ANIMAZIONE-MS, ANIMAZIONE-HS |
11 | 05/03/99 | Metodologia di svolgimento degli esercizi: esempio con la realizzazione dell'operazione di cancellazione nella coda di priorità. Un altro ordinamento di tipo divide-et-impera: l'algoritmo di ordinamento QuickSort. | Par. 8.1 in [CLR] ANIMAZIONE |
12 | 08/03/99 | Discussione della procedura PARTITION nell'algoritmo di ordinamento QuickSort e sua complessità. Versione "randomizzata" dell'algoritmo. Equazione di ricorrenza per il QuickSort al caso ottimo, pessimo e medio. Relativi alberi di ricorsione. | Par. 8.2-8.3 in [CLR] ANIMAZIONE |
13 | 09/03/99 | Analisi dettagliata della complessità del QuickSort. | Par. 8.4 in [CLR] |
14 | 10/03/99 | Analisi alternativa della complessità del QuickSort. Esercizio sul numero di nodi interni e di foglie in alberi binari. | Par. 3.3 in [Lu] APPUNTI |
15 | 12/03/99 | Esercitazione su proprietà di alberi binari dimostrabili con l'induzione: Metodo di decomposizione in sottoalberi e metodo di contrazione di un nodo interno. | APPUNTI |
16 | 15/03/99 | Limite inferiore Omega(n log n) alla complessità al caso pessimo degli algoritmi di ordinamento per confronti. Algoritmi che non usano confronti: Counting Sort, con esempi. | Par. 9.1-9.2 in [CLR], ANIMAZIONE-CS1, ANIMAZIONE-CS2 |
17 | 16/03/99 | Algortimi di ordinamento lineari: RadixSort e BucketSort, con esempi. Esercizi sul MergeSort e QuickSort. | Par. 9.3-9.4 in [CLR], ANIMAZIONE-RS1, ANIMAZIONE-RS2 ANIMAZIONE-BS. |
18 | 17/03/99 | Esercizi: dimostrazione per induzione della correttezza del radix sort; programma Pascal per il RadixSort usando il CountingSort; mediano con algoritmo randomizzato e sue varianti; svolgimento di alcuni esercizi d'esame sull'analisi di complessità. | Par. 9.3 e 10.1-10.2 in [CLR] |
19 | 19/03/99 | Tipo di dato Dizionario. Realizzazione mediante vettori e liste bidirezionali (con ordinamento o senza). | Parte III e Par. 11.1-11.2 in [CLR], APPUNTI |
20 | 22/03/99 | Tabelle ad accesso diretto e codifica delle chiavi alfanumeriche. | Par. 12.1 in [CLR] (lezione di una sola ora) |
21 | 24/03/99 | Tabelle hash e loro confronto con tabelle ad accesso diretto. Esempio di funzioni hash (metodo della divisione e della moltiplicazione). | Par. 12.2-12.3 in [CLR] |
22 | 26/03/99 | Collisioni e loro metodi di risoluzione: concatenamento e indirizzamento aperto. | Par. 12.2 e 12.4 in [CLR] (12.4 senza analisi), APPUNTI |
23 | 12/04/99 | Esercizi di ricerca su insiemi di reali. Discussione delle soluzioni proposte. | APPUNTI |
24 | 13/04/99 | Esercizi su liste e vettori ordinati | APPUNTI |
25 | 16/04/99 | Prima verifica, ore 16:15, aule A+B+C+E+A1+D1. | testo+soluzioni |
26 | 19/04/99 | Definizione di albero binari, loro rappresentazione in memoria e relative operazioni primitive in Pascal. Stampa in ordine simmetrico delle chiavi in un albero binario. Esercizio: progettare una funzione booleana che verifica l'uguaglianza tra alberi binari (l'ordine e la posizione dei figli di ciascun nodo deve essere rispettata). | UNIT alberi.pas per la gestione di alberi binari. Soluzione esercizio |
27 | 20/04/99 | Primitive in Pascal per la modifica di un albero binario. Introduzione dei puntatori al padre. Esercizio: verificare che, dati due nodi, uno sia antenato dell'altro. | UNIT alberi.pas per la gestione di alberi binari, soluzione esercizio. |
28 | 21/04/99 | Definizione di alberi binari di ricerca e loro relazione con la ricerca binaria. Operazioni di calcolo della minima (e massima) chiave e ricerca di chiavi in alberi binari di ricerca (in Pascal). Esercizio: verificare in tempo lineare che un albero binario soddisfi la proprietà di albero di ricerca. | Par. 13.1 e 13.2 in [CLR], UNIT abr.pas per la gestione di alberi binari di ricerca, soluzione esercizio. |
29 | 26/04/99 | Inserzione e cancellazione in alberi binari di ricerca. Analisi della complessità e realizzazione in Pascal. | Par. 13.3 in [CLR], UNIT abr.pas per la gestione di alberi binari di ricerca |
30 | 27/04/99 | Codice alternativo per la cancellazione, con copia delle informazioni. Esercizio: costruzione, in tempo lineare, di alberi binari di ricerca bilanciati da insiemi ordinati. | Codice Pascal per la cancellazione e per la soluzione dell'esercizio. |
31 | 28/04/99 | Alberi bilanciati mediante rotazioni: Alberi AVL. Loro proprietà, esempi di ricerca e inserzione con relative problematiche. | Par. 10.1 in [Bi], Par. 5.1.2 e 5.2.1 in [Lu] |
32 | 04/05/99 | Ricerca, inserzione, cancellazione (cenni) e rotazioni SS, SD, DS, DD in alberi AVL. | Par. 10.1 in [Bi], Par. 5.1.2 e 5.2.1 in [Lu], Codice Pascal per la ricerca e l'inserzione negli alberi AVL. |
33 | 05/05/99 | Visite ricorsive di alberi binari: anticipata, simmetrica, posticipata. Visite iterative di alberi binari di ricerca: anticipata (con pila) e per livelli (con coda). Visita iterativa di alberi di ricerca: simmetrica (con SuccAlbero). Esercizio: realizzazione del tipo di dato INSIEME mediante alberi AVL. | Par. 13.1 e relativi esercizi in [CLR], Par. 5.1 in [Bi], Codice Pascal per le visite. |
34 | 07/05/99 | Alberi bilanciati con operazioni di split e merge: i B-alberi e i 2-3-4-alberi. Definizione e proprietà; operazioni di ricerca e inserzione. | Cap. 19 in [CLR] (lettura obbligatoria: par. 19.3 sulla cancellazione). |
35 | 10/05/99 | Grafi: terminologia, rappresentazione con liste e matrici d'adiacenza. Esercizio: modificare la unit TurboPascal per la gestione del tipo di dato GRAFO, usando la matrice di adiacenza al posto delle liste di adiacenza (liste.pas). | Par. 5.4 e 23.1 in [CLR], Unit grafi.pas. |
36 | 11/05/99 | Esercizi su alberi AVL e B-alberi. Codice Pascal per le rotazioni AVL. | Unit AVL.pas contenente, tra l'altro, il codice Pascal per le rotazioni. |
37 | 12/05/99 | Visita in ampiezza o a ventaglio di grafi (BFS). Visita in profondità (DFS). Codice Pascal per le visite BFS e DFS nei grafi. | Par. 23.2 (senza le parti su "shortest paths" e "breadth-first trees"), 23.3 (senza le parti su "properties of depth-first search" e "classification of edges") in [CLR]. Codice Pascal per le visite BFS e DFS (necessita della unit grafi.pas). |
38 | 14/05/99 | Esercizi su funzioni hash. | APPUNTI |
39 | 17/05/99 | Problemi computazionalmente difficili. Problemi NP-completi. | Cap. 7 in [Lu], Par. 36.1, 36.2, 36.3 in [CLR]. |
40 | 18/05/99 | Esercizi su grafi e problemi computazionalmente difficili. Ricapitolazione degli argomenti trattati nel corso. | APPUNTI |
41 | 27/05/99 | Seconda verifica, ore 14:30, aule A+B+C+E+A1+B1. |