Anno Accademico 2005/2006
Corsi di Studio in Informatica
Università degli Studi di Pisa
II anno, I semestre, corso B
AVVISI
- Per il ricevimento, consultare la mia homepage.
- Martedì 21 febbraio 2006, alle ore 9:00, presso il mio
ufficio, sarà possibile svolgere le prove orali di esame
oppure fissare un calendario successivo per tali prove. È
anche un'occasione per visionare la correzione della propria prova
scritta.
- Per chi ha superato almeno una verifica intermedia e deve
svolgere solo gli orali, il termine ultimo è entro la fine di
febbraio 2006.
- Risultati del secondo appello (10.02.06):
235809 SU
241658 S? II
242238 S? II
246734 IN I
251179 IN II
252603 SU II
270302 SU I
270596 S? II
271497 24
276894 S?
290668 IN II
291561 SU
291677 25
291715 IN
- Risultati del primo appello (13.01.06):
242238 IN
252062 S?
270302 IN
272187 IN
272249 25
290455 20
290594 28
291000 30
291677 IN
291687 S?
291908 IN
291930 27
292954 SU
296227 SU
296615 IN
251866 S?
270596 IN
270667 S?
290668 12 (su 15 punti)
- Testo e soluzioni della prima verifica
(11.4.05), testo e soluzioni della seconda
verifica (21.12.05): i risultati di entrambe le verifiche sono in questa pagina.
MODALITÀ DI ESAME
- L'esame consiste in una prova scritta e in una prova orale,
insieme a una discussione della realizzazione in codice degli alberi
AVL (solo inserimento e ricerca) e dei grafi. Un grafo G supporta i
seguenti metodi sugli n vertici rappresentati come interi da 0 a n-1:
il costruttore che prende in ingresso una matrice d'adiacenza e decide
se e il grafo è orientato o meno in base alla simmetria della
matrice; G.n_vertici() e G.n_archi() per la sua dimensione;
G.arco(x,y) per verificare l'esistenza di un arco (x,y);
G.listaAdiacenza(x) per restituire la lista di adiacenza del vertice
x; G.bfs_vertici() e G.dfs_vertici() per ottenere la lista dei vertici
nell'ordine di visita mentre G.bfs_archi() e G.dfs_archi()
restituiscono la lista di archi in ordine di visita.
- Durante la prova scritta o le verifiche intermedie è
vietato portare e consultare libri o appunti.
- Il superamento di
entrambe le verifiche intermedie consente l'esonero dalla prova
scritta per la sola sessione invernale, per cui l'orale va sostenuto
entro tale sessione (come da regolamento didattico).
- Piccoli gruppi di studenti possono contattare il docente per
approfondire l'argomento facendosi assegnare un problema da risolvere
a casa, collettivamente e durante il semestre del corso. È
possibile collaborare, cercare su libri e su Internet. Tale
attività non è obbligatoria e non pregiudica il voto
finale dell'esame, ma si propone di sviluppare una maggiore
capacità di "problem solving" e di lavoro di gruppo, al
di là del semplice superamento dell'esame:
"A scuola si insegna agli scolari a non aiutarsi l'un l'altro, a non
suggerire a chi non sa, a preoccuparsi solo della promozione, a
conquistare un premio nella competizione con i compagni. Uomini
così educati non sono preparati alla conquista della
verità [...] né alla carità verso gli altri uomini, per
associarsi con loro in una vita migliore. L'educazione ricevuta li ha
preparati a quello che può considerarsi un episodio della vita
collettiva reale: la guerra."
--
M. Montessori, 1932
PROGRAMMA
Registro delle lezioni e prerequisiti
matematici al corso disponibili in linea.
Analisi di Algoritmi e
Complessità:
- Introduzione alla complessità di calcolo
- Ordini di grandezza delle funzione
- Algoritmi ricorsivi e divide et impera: Numeri di Fibonacci, Ricerca Binaria,
Mergesort, Moltiplicazione rapida
- Relazioni di ricorrenza
- Limiti inferiori alla complessità
Progetto di Algoritmi e Strutture dei
Dati:
- Liste e gestione ad auto-organizzazione (MTF)
- Alberi e loro rappresentazione succinta, minimo antenato comune (LCA)
- Code, Pile, Heap
- Heapsort
- Quicksort
- Ordinamento in tempo lineare: Counting Sort e Radix Sort
- Tabelle hash
- Alberi binari di ricerca: AVL
- Grafi: rappresentazione e visite, chiusura transitiva,
colorazioni di grafi a intervallo, reti complesse
Classi di Complessità:
- Enumerazione e non determinismo
- Classi P, NP, NPC
- Algoritmi randomizzati
Modelli di Calcolo e
Calcolabilità:
- Indecidibilità e universalità
- Problema della fermata
TESTI
- C. Demestrescu, I. Finocchi, G. F. Italiano,
Algoritmi e strutture dati,
McGraw Hill, 2004.
Sito Web.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest,
C. Stein.
Introduction to algorithms, MIT Press, second edition, 2001.
Sito Web ed
errata-corrige.
- Dispense del docente
MATERIALE INTEGRATIVO
- Brevi note introduttive.
- Segmento di somma massima.
- Moltiplicazione veloce.
-
Macchine di Turing + dispensa disponibile in copisteria.
-
Esercizi e animazione di alcuni algoritmi.
- Codice C per gli alberi AVL
(avl.h, avl.c).
- Testi di alcuni appelli precedenti:
2002.04.04,
2002.05.16,
2003.11.04,
2003.12.17,
2004.01.21,
2004.02.11,
2004.06.01,
2004.06.22,
2004.07.13,
2004.09.17.
PROGRAMMA DEGLI ANNI PRECEDENTI
MISCELLANEA