Algoritmi e Strutture Dati (II anno) - a.a. 1996-97
Ultima modifica: 01 Ottobre 1997.
Commenti a Eugenio Moggi.
- Docente:
Eugenio Moggi;
Assistenti:
Giovanna Guerrini,
Paola Magillo
- Corso
(Aula 505 - Lun 11-13, Mar 9-11, Mer 11-13, Gio 9-11, Ven 11-13):
Prerequisiti,
Programma,
Testi di Riferimento,
Argomenti delle lezioni,
Note
- Laboratorio
(SW1 - Lun 14-18 esercitazione guidata, Mer 14-18).
- Esami: Modalita' degli esame
(VEDI e-mail di COSTA),
testi e soluzioni di esami precedenti
situazione voti
Gli esami consistono di due prove scritte ed un orale.
- Il primo scritto e' di sbarramento. Esso serve a verificare se
uno studente si e' ripassato il programma ed ha acquisito un minimo di
familiarita con il C. Chi non passa tale scritto non e' ammesso alle
altre prove.
Durante tale scritto non e' consentita la consultazione di testi o
appunti. A partire da Giugno 1998 esso e' mutuato dallo scritto del
corso di Algoritmi e Strutture Dati (I anno).
- Il secondo scritto consiste di un progettino su struttura dati e
algoritmi. Esso serve a verificare la capacita' creativa-progettuale
e di analisi. In tale scritto non si richiede di scrivere del codice,
ma solo di dare una descrizione ad alto livello (p.e. a parole ed in
pseudo-codice) della soluzione, e di essere in grado di giustificarne
la correttezza e valutarne la complessita'
Se uno studente fa male l'orale, gli e' comunque consentito conservare
lo scritto agli appelli successivi. Tuttavia, chi consegna uno
scritto non puo' poi mantanere lo scritto precedente.
In segreteria sono disponibili i testi degli esercizi di esame
dell'a.a. 1995-96 e 1996-97.
Si presuppone la conoscienza del Pascal. E' opportuno aver seguito il
corso di Programmazione. Chi non ha Programmazione nel piano di
studi, dovrebbe seguiere il corso di Algoritmi e Strutture Dati per il
I anno di Informatica.
Il corso fornisce e' una panoramica sugli algoritmi e strutture dati
nel contesto di linguaggi imperativi sequenziali (tipo Pascal e C) con
particolare enfasi sull'analisi della complessita' concreta. Nel
corso viene anche introdotto il linguaggio C, ed alcuni risultati
fondamentali di calcolabilita'.
-
Calcolabilita' (riferimenti: dispense, fotocopie, [B]).
- nozione di algoritmo e funzione calcolabile;
- macchine di Turing (idea, formalizzazione, funzioni associate, tesi di
Church, numerazione effettiva,
MdT universale, problema dell'arresto);
- insiemi e predicati ricorsivi ed r.e. (def, esempi, teoremi di
caratterizzazione).
-
Il costo di esecuzione degli algoritmi (riferimenti: [CLR], fotocopie)
- generalita' (misure statiche/dinamiche, misure spazio e tempo,
complessita' come funzione dell'input e
della "dimensione", caso peggiore/medio, complessita' intrinseca dei problemi);
- le notazioni O, W, Q;
- stime della complessita' (tempo) di algoritmi in linguaggio evoluto.
-
Richiami ed approfondimenti: (riferimenti: [W], fotocopie)
- procedure: ricorsione, passaggio dei parametri, var. globali;
- liste, pile, code, alberi;
- i linguaggi C e PASCAL.
-
Strutture dati (riferimenti: [CLR], [B], fotocopie)
- richiami sulle nozioni di tipo di dato concreto e astratto e di
implementazione;
- implementazione semplici di "insiemi" (bit vectors, liste, liste
ordinate, arrays);
- hashing, binary search trees, tries, code a priorita'.
-
Ordinamenti (riferimenti: [CLR], [W], fotocopie)
- ordinamento di arrays: inserimento, selezione e scambio diretto;
heapsort, quicksort; complessita'
intrinseca del problema;
- ordinamento di liste (e files): split + merge
- ordinamenti "speciali": bucket-sort, radix-sort
-
Grafi (riferimenti: [CLR], [B], fotocopie)
- def.ni di: grafi diretti e non, cammini, cicli, connessione, alberi;
- visite, componenti connesse, topological sorting, tests di aciclicita';
- alcuni algoritmi notevoli.
-
Tecniche per il progetto di algoritmi (riferimenti: [B],
fotocopie))
- divide et impera, backtracking, programmazione dinamica, metodo greedy,...
-
[CLR] Cormen, Leiserson, Rivest: Introduzione agli algoritmi, Vol 1,
Jackson Libri
-
[B] Bertossi: Strutture, algoritmi, complessita', ECIG
-
[W] Wirth: Algoritmi + Strutture dati = Programmi, ed. Tecniche Nuove.
In segreteria studenti sono disponibili le dispense del corso. Esse
non sono sostitutive del Cormen!