Algoritmica, 2004-05

Questa è la pagina dell'insegnamento "Algoritmica" del corso di laurea in Scienze dell'Informazione, Università di Modena e Reggio Emilia, per l'A.A. 2004/05. L'insegnamento è suddiviso in due moduli (Algoritmi e strutture dati I e II), rispettivamente di 6 e 4 crediti formativi. Del primo modulo fruiscono gli studenti del corso di laurea in Matematica, per i quali vale come insegnamento di "Informatica Generale II".

La pagina contiene le seguenti sezioni:

Orario delle lezioni

Avvisi (in ordine cronologico inverso)

24 febbraio 2006
Esami orali  L'ultima sessione di esami orali si terrà giovedì 2 marzo alle ore 10.15 presso lo studio del docente (primo piano del Dip. di Ingegneria dell'Informazione)
19 gennaio 2006
Appello del 18 gennaio 2006  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno mercoledì prossimo (25 gennaio 2006), con inizio alle ore 14.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione
21 dicembre 2005
Date appelli  Nella sezione relativa agli esami sono state inserite le date degli appelli della sessione gennaio-febbraio 2006.
19 settembre 2005
Ancora sugli orali  Sono pervenute molte richieste di sostenere esami orali in giorni diversi. Ovviamente non è possibile soddisfare tutte le esigenze personali. La successiva sessione (dopo quella di mercoledì 21 settembre 2005) si terrà quindi ad inizio ottobre (data e ora verranno comunicate con successivo avviso).
14 settembre 2005
Continuazione orali  Gli studenti sono convocati per il giorno 21 settembre 2005 alle ore 14.30 presso l'ufficio del docente.
12 settembre 2005
Informazione sugli orali  A seguito di molte richieste ricevute, si precisa che la sessione di esami del 14 settembre p.v. inizierà stilando un calendario delle prove. Detto calendario terrà conto, nei limiti del possibile e del ragionevole, di tutte le esigenze degli studenti. Gli studenti che non possono essere presenti possono farsi rappresentare da un amico. Si ricorda tuttavia che la regola base prevede che gli orali debbano essere sostenuti nella stessa sessione dello scritto. Le eccezioni saranno possibili, ma dovranno essere adeguatamente motivate.
10 settembre 2005
Appello del 7 settembre 2005  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta.
9 settembre 2005
Data esami orali  Gli esami orali si terranno il giorno mercoledì 14 settembre alle ore 15 presso lo studio del docente (dip. di Ingegneria dell'Informazione). Con un prossimo avviso sarà segnalata la presenza online dei risultati della prova scritta del 7 settembre u.s.
6 settembre 2005
Spostamento aula  Causa l'inagibilità dell'aula IV, lo scritto di domani si terrà in aula VI. L'accesso a tale aula è possibile dall'esterno del Dipartimento. Gli studenti sono comunque pregati di farsi trovare puntuali (ore 10.30) nel luogo di riunione, presso il centralino del Dipartimento, da dove (insieme) ci recheremo in aula VI.
2 agosto 2005
Appello del 27 luglio 2005  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Con successivo avviso saranno comunicati luogo, data e ora della correzione.
4 luglio 2005
Appello del 4 luglio 2005  La correzione si terrà il giorno 7 luglio 2005 alle ore 10.00 in aula XII del dipartimento di matematica. In seguito verrà concordato un calendario per gli orali.
9 giugno 2005
Appello del 7 giugno 2005  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. La correzione si terrà il giorno 15 giugno 2005 alle ore 14.00 (in un'aula da stabilire). Esami orali (per gli ammessi) a seguire.
26 maggio 2005
Prova di autovalutazione  Il giorno 1 giugno 2005 alle ore 10 si terrà una prova modellata su quelle d'esame, che potrà essere sostenuta dagli studenti ai fini di autovalutazione.
26 maggio 2005
Date appelli  Nella sezione relativa agli esami sono state inserite le date degli appelli della sessione giugno-settembre 2005.
22 marzo 2005
Rinvio lezione  La lezione di domani (23 marzo 2003) non si terrà a causa di una sopraggiunta indisponibilità del docente. La data del recupero verrà comunicata in seguito. Il docente si scusa per gli eventuali inconvenienti causati.
9 marzo 2005
Ricevimento studenti (parziale rettifica)  La data e il giorno fissati in precedenza rimangono validi per gli studenti del corso di Laurea in Matematica. Per gli studenti di Scienze dell'Informazione, il ricevimento è fissato il venerdì alle ore 14 (si prega di avvisare alla fine della lezione del mattino). In entrambi i casi, il ricevimento si terrà nello studio del docente al primo piano del Dipartimento di Matematica.
28 febbraio 2005
Ricevimento studenti  Per tutto il secondo semestre (nei periodi di lezione) il ricevimento studenti è fissato nei giorni di mercoledì, dalle ore 14.30 alle 16.
28 febbraio 2005
Conferma inizio lezioni  La prima lezione si terrà regolarmente mercoledì 2 marzo 2005 (giornata in cui è stato indetto uno sciopero dalle organizzazioni della docenza).
10 gennaio 2005
Inizio lezioni  Mercoledì 2 marzo 2005.

Obiettivi e programma del corso


Obiettivi formativi. L'insegnamento introduce le principali metodologie di progettazione e le tecniche algoritmiche di base. Tale introduzione viene fatta seguendo gli argomenti classici di un corso introduttivo di algoritmica, e cioè le strutture dati di base, gli algoritmi di ordinamento e quelli di ricerca, oltre ad un campione "selezionato" di algoritmi particolarmente significativi dal punto di vista delle metodologie di sviluppo. Lo studente sarà portato ad apprezzare l'importanza di una fase progettuale in cui vengano considerate la correttezza e l'efficienza degli algoritmi in termini di consumo spazio-tempo. Al riguardo, verranno introdotte le nozioni di complessità asintotica del caso medio e di quello più sfavorevole. Sono previste ore di laboratorio per aiutare lo studente a sviluppare la capacità di tradurre algoritmi teoricamente efficienti in programmi con elevate prestazioni.

Programma (I modulo).

Programma (II modulo).

Lezioni e materiale didattico

Libro di testo

C. Demetrescu, I. Finocchi, G.F. Italiano
Algoritmi e strutture dati
McGraw-Hill

Lezioni

La seguente tabella descrive l'argomento delle lezioni svolte, con i riferimenti al libro di testo e ad eventuale materiale aggiuntivo (ad esempio, maggiori dettagli sugli argomenti o software sviluppato in laboratorio)

Data lezione Argomento Libro di testo Materiale
2 marzo 2005 Introduzione agli algoritmi Cap. 1, paragrafi 1.1-1.7 Dettagli
3 marzo 2005 Modelli di calcolo e metodologie di analisi Cap. 2, paragrafi 2.1, 2.4 e 2.4.1 Dettagli
3 marzo 2005 Ricerca sequenziale e ricerca binaria Cap. 2, paragrafi 2.4.2 e 2.4.3 Dettagli
4 marzo 2005 Analisi della ricerca binaria Cap. 2, paragrafo 2.4.3 Dettagli
4 marzo 2005 Limitazioni inf. e sup. di complessità , notazione asintotica Cap. 2, paragrafi 2.2 e 2.3 Dettagli
4 marzo 2005 Strutture dati elementari Cap. 3, introduzione Dettagli
Note di sintesi sulla prima parte Appunti
9 marzo 2005 Laboratorio: ricerca sequenziale e binaria Cap. 2, paragrafi 2.4.2 e 2.4.3 Software: 1, 2
9 marzo 2005 Laboratorio: tipo di dato stack e implementazione con array Cap. 3, paragrafi 3.1 e 3.2 Software: 1, 2
10 marzo 2005 Record e puntatori, liste lineari Cap. 3, paragrafo 3.1.2 Dettagli
10 marzo 2005 Puntatori: discussione di un esempio di programma in C++ Software
11 marzo 2005 Code, alberi e loro rappresentazione, visita di alberi Cap. 3, paragrafi 3.2 e 3.3 Dettagli
16 marzo 2005 Laboratorio: implementazione di una coda Software: 1, 2
17 marzo 2005 Ordinamento: metodi quadratici e heapsort Cap. 4, Introduzione, paragrafi 4.2.1, 4.3 Dettagli
18 marzo 2005 Mergesort, analisi di algoritmi ricorsivi Cap. 4, par. 4.4; Cap. 2, par. 2.5.1 e 2.5.3 Dettagli
18 marzo 2005 Quicksort Cap. 4, paragrafo 4.5 (escluso 4.5.1) Dettagli
31 marzo 2005 Analisi del quicksort. Complessità dell'ordinamento. Cap. 4, paragrafo 4.5.1 e 4.1 Dettagli
1 aprile 2005 Ordinamento in tempo lineare Cap. 4, paragrafi 4.6 e 4.7 Dettagli
1 aprile 2005 Calcolo del convex-hull di un insieme di punti Cap. 15, paragrafi 15.1 (introduzione) e 15.1.1 Dettagli
6 aprile 2005 Laboratorio: esperimenti con vari alg. di ordinamento Software: 1, 2
8 aprile 2005 Inviluppo convesso di un insieme di n punti: scansione di Graham. Cap. 15, paragrafi 15.1.1 e 15.1.3. Dettagli
8 aprile 2005 Statistiche d'ordine. Cap. 5, paragrafi 5.1 (introduzione) e 5.1.1 Dettagli
9 aprile 2005 Statistiche d'ordine Cap. 5, paragrafi 5.1.2 e 5.2 Dettagli
9 aprile 2005 Tecniche algoritmiche Cap. 10, paragrafi 10.1 e 10.2 Dettagli
13 aprile 2005 Laboratorio: algoritmo Graham's scan per il convex hull Software: 1, 2
13 aprile 2005 Laboratorio: algoritmi quickselect e heapselect Software: 1, 2
14 aprile 2005 Programmazione dinamica Cap. 10, paragrafo 10.2.1 Dettagli
15 aprile 2005 Tecnica greedy Cap. 10, paragrafo 10.3 Dettagli
15 aprile 2005 Definizioni preliminari sui grafi Cap. 11, paragrafo 11.1 Dettagli
20 aprile 2005 Laboratorio: programmazione dinamica Software: 1, 2
20 aprile 2005 Laboratorio: tecnica greedy Software: 1, 2
21 aprile 2005 Visita in ampiezza di un grafo Cap. 11, paragrafo 11.3.1 Dettagli
22 aprile 2005 Visita in profondità . Componenti connesse Cap. 11, paragrafi 11.3.2, 11.3.3, 11.4 e 11.5 Dettagli
27 aprile 2005 Laboratorio: rappresentazione di grafi e visita in ampiezza Software: 1, 2
27 aprile 2005 Laboratorio: ricerca in profondità Software: 1, 2
28 aprile 2005 Minimo albero di copertura Cap. 12, par 12.1, 12.2 (escluso 12.2.1) e 12.3 (escluso 12.3.1) Dettagli
29 aprile 2005 Cammini minini Cap. 13, par. 13.1, 13.2, 13.3, 13.5 (escluso 13.5.1) Dettagli
5 maggio 2005 Alberi binari di ricerca. Alberi AVL Cap. 6, paragrafi 6.1 e 6.2.1 Dettagli
6 maggio 2005 Alberi AVL. Alberi 2-3 Cap. 6, paragrafi 6.2.2, 6.2.3 e 6.4 (introduzione) Dettagli
11 maggio 2005 Laboratorio: alberi binari di ricerca Software: 1, 2
12 maggio 2005 Alberi 2-3, B-alberi Cap. 6, paragrafi 6.4 e 6.5 (tranne 6.5.2) Dettagli
13 maggio 2005 B-alberi, tabelle Hash Cap. 6, paragrafo 6.5.2. Cap. 7, paragrafi 7.1, 7.2, 7.3.1 Dettagli
18 maggio 2005 Laboratorio: alberi binari di ricerca e hashing Software: 1, 2
19 maggio 2005 Tabelle hash Cap. 7, paragrafo 7.3.2 Dettagli
19 maggio 2005 Code con priorità Cap. 8, introduzione Dettagli
20 maggio 2005 Code con priorità Cap. 8, paragrafi 8.1 e 8.2 Dettagli
25 maggio 2005 Laboratorio: tecnica hashing Software: 1, 2
26 maggio 2005 Algoritmi e strutture dati per insiemi disgiunti Cap. 9, paragrafi 9.1 e 9.2.1 Dettagli
1 giugno 2005 Prova di autovalutazione Testo: 1, 2

Scarica i dettagli degli argomenti affrontati a lezione in formato postscript oppure in formato pdf.

Esami

Appelli

Data appello Ora Luogo Esito scritto
7 giugno 2005 14.30 Dipartimento di Matematica, aula IV Visualizza
4 luglio 2005 10.30 Dipartimento di Matematica, aula VI Visualizza
27 luglio 2005 14.30 Dipartimento di Matematica, aula I Visualizza
7 settembre 2005 10.30 Dipartimento di Matematica, aula IV Visualizza
18 gennaio 2006 9.00 Dipartimento di Matematica, aula VI Visualizza
2 febbraio 2006 14.30 Dipartimento di Matematica, aula VI
22 febbraio 2006 9.00 Dipartimento di Matematica, aula VI
 
http://algo.ing.unimo.it
Ultimo aggiornamento della pagina: 21 dicembre 2005.
Mauro Leoncini (leoncini AT unimore DOT it)

Valid HTML 4.01! Valid CSS! Eurolinux Software Patent Petition