INGEGNERIA DEGLI ALGORITMI (ONLINE) 2011-2012
NEWS
	(07/03/2012) Il secondo appello invernale (da recuperare) è fissato per il giorno lunedì 19 Marzo, ore 10:00, aula 9 nuovi edifici. Per iscriversi mandate una email con il consueto formato il giovedì precedente (15 Marzo). La verbalizzazione si farà nel pomeriggio del giorno stesso.
	(24/02/2012) Questa mattina mi sono svegliato con la febbre alta, e non sono in grado di venire all'esame. Ho telefonato in presidenza e segreteria studenti per farvi avvisare, ma non mi hanno risposto. Mi dispiace per l'inconveniente. Se vedete il sito, per favore avvisate gli altri studenti. L'esame sarà rinviato a data da fissare. Tenete d'occhio il sito nei prossimi giorni.
	(24/01/12) Per i due appelli invernali di Ingegneria degli Algoritmi, fate riferimento alle date e al regolamento del mio corso di "Informatica" (gli esami avverranno in parallelo). Trovate tutte le informazioni nella relativa pagina sul mio sito.
	(28/10/11) Alcune note per gli studenti degli anni passati. L'esame di Ingegneria degli Algoritmi (9 crediti) risulta dalla fusione dei vecchi esami di Algoritmi e Strutture Dati (tenuto da me) e Laboratorio di Programmazione (tenuto dal Prof. Faruolo). Da quest'anno io sono responsabile unico del corso. L'esame di Ingegneria degli Algoritmi è suddiviso in due parti, scritto/orale e progetto, corrispondenti rispettivamente ad ASD e LabProg, che possono essere sostenute separatamente. Gli studenti che dovessero sostenere, in base al loro piano di studi, i vecchi esami devono semplicemente svolgere la relativa parte dell'esame di Ingegneria degli Algoritmi (comunicandomi prima nome e numero di crediti dell'esame che devono sostenere).
INFORMAZIONI GENERALI
	Obiettivi del corso: fornire strumenti di base per la progettazione e l'analisi formale di algoritmi e strutture dati.
	Collocazione del corso: secondo anno, primo semestre.
	Numero crediti: 9.
	Interazione con il docente: domande sulla teoria e/o sugli esercizi possono essere poste via email all'indirizzo grandoni@disp.uniroma2.it. Risponderò il prima possibile. Ricevo gli studenti su appuntamento.
	Testi: "Algoritmi e Strutture Dati", C. Demetrescu, I. Finocchi, G. F. Italiano, McGraw-Hill, 2008 (o edizione successiva). Per il progetto, può essere utile il testo "Progetto di Algoritmi e Strutture Dati in Java", C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G. F. Italiano, McGraw-Hill. Come manuale Java, consiglio "Fondamenti di Java", H. Schildt, McGraw-Hill.
	Modalità d'esame: l'esame consiste di due parti: (1) La prima parte è uno scritto/orale, in cui occorre risolvere un insieme di esercizi. Un esercizio può essere sia una domanda di natura teorica sui contenuti del corso, sia la richiesta di applicare un dato algoritmo ad un dato input (illustrando dettagliatamente i vari passaggi). Sotto trovate un esempio di compito. (2) La seconda parte comporta lo sviluppo (individuale) di un programma in Java, e la stesura di una relazione dettagliata sul lavoro svolto. Codice e relazione vanno consegnati alcuni giorni prima della data d'esame (comunicherò le date esatte), e saranno poi discussi il giorno dell'esame. Sotto trovate i dettagli del progetto. Per superare l'esame occorre ottenere un voto sufficiente in entrambe le parti. E' possibile sostenere le due parti in appelli e anche in sessioni diverse, purché il tutto si svolga entro l'anno accademico (cioè entro la sessione autunnale del 2012).
	Appelli: ci saranno due appelli in ciascuna delle sessioni invernale (6/2/12-3/3/12), estiva (2/7/12-28/7/12) ed autunnale (3/9/12-29/9/12). Nella sessione estiva ciascuno studente potrà sostenere uno solo degli appelli.
	Modalità di frequenza: gli studenti hanno la possibilità (non l'obbligo) di seguire le lezioni frontali con il Prof. Italiano (consultate il suo sito per orari etc.). E' importante però notare che il corso frontale può differire leggermente negli argomenti trattati e che l'esame può essere di tipologia piuttosto diversa.
	Modalità d'erogazione: online.
	Voti: sono disponibili qui le proposte di voto (rimuovo periodicamente i voti verbalizzati)
PROGRAMMA
	Modelli di calcolo e metodologie di analisi: notazione asintotica; analisi di caso medio e pessimo; analisi di algoritmi randomizzati; analisi ammortizzata.
	Strutture Dati Elementari: pile e code; rappresentazione e visita di alberi.
	Ordinamento: insertionsort, selectionsort, bubblesort; mergesort; heap ed heapsort; quicksort; integersort e radixsort.
	Selezione: heapselect; quickselect randomizzatto; quickselect deterministico.
	Alberi di Ricerca: alberi binari di ricerca; alberi AVL.
	Tabelle Hash: tabelle ad accesso diretto; tecniche di hashing; liste di collisione; indirizzamento aperto.
	Code con Priorità: heap binari; heap binomiali.
	Union-Find: quickfind; quickunion; bilanciamento della union; compressione durante la find.
	Grafi: rappresentazione; visite in ampiezza e profondità.
	Minimo Albero Ricoprente: algoritmo di Kruskal; algoritmo di Prim.
	Cammini Minimi: algoritmo di Bellmann, Ford e Moore; algoritmo di Dijkstra; algoritmo di Floyd e Warshall.
MATERIALE DIDATTICO
Slides (nella versione stampabile in bianco e nero alcune figure si vedono male):
	cap0 (stampabile): informazioni generali
	cap1 (stampabile): un'introduzione informale agli algoritmi
	cap2 (stampabile): modelli di calcolo e metodologie di analisi
	cap3 (stampabile): strutture dati elementari
	cap4 (stampabile): ordinamento
	cap5 (stampabile): selezione e statistiche di ordine
	cap6 (stampabile): alberi di ricerca
	cap7 (stampabile): tavole hash
	cap8 (stampabile): code con priorità
	cap9 (stampabile): union-find
	cap11 (stampabile): grafi e visite di grafi
	cap12 (stampabile): minimo albero ricoprente
	cap13 (stampabile): cammini minimi
Esercizi svolti: Sotto trovate uno scritto completo con le relative soluzioni. Tale esame è solo un esempio di massima su come sarà l'esame effettivo. In particolare, quest'ultimo potrà toccare argomenti diversi e avere diversa difficoltà. Vi prego di segnalarmi eventuali errori/problemi.
	Esempio scritto
PROGETTO
	Trovate qui la descrizione del progetto.