Algoritmica, 2005-06

Questa è la pagina dell'insegnamento Algoritmica del corso di laurea in Scienze dell'Informazione, Università di Modena e Reggio Emilia, per l'A.A. 2005/06. L'insegnamento è suddiviso in due moduli, rispettivamente di 6 e 4 crediti formativi. Del primo modulo fruiscono gli studenti del secondo anno (immatricolati cioè nel 2004-05) del corso di laurea in Matematica. Gli studenti del primo anno di Matematica (immatricolati cioè nel 2005-06) fruiscono di entrambi i moduli. Per tutti gli studenti di Matematica il nome dell'insegnamento è Informatica Generale II.

La pagina contiene le seguenti sezioni:

Orario delle lezioni

Avvisi (in ordine cronologico inverso)

9 febbraio 2007
Appello del 7 febbraio 2007  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì prossimo (20 febbraio 2007), con inizio alle ore 14.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
22 gennaio 2007
Appello del 18 gennaio 2007  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno giovedì prossimo (25 gennaio 2007), con inizio alle ore 9.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
20 dicembre 2006
Date appelli  Nella sezione relativa agli esami sono state inserite le date dei prossimi due appelli (sessione invernale).
19 settembre 2006
Appello del 19 settembre 2006  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno giovedì prossimo (21 settembre 2006), con inizio alle ore 9.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
5 settembre 2006
Sessione d'esami di settembre  Il prossimo appello si terrà il giorno 19 settembre 2006 alle ore 14.30 presso l'aula V del Dip. di Matematica.
20 luglio 2006
Orali e visione dello scritto (per i non ammessi)  Sono pervenute alcune richieste di avere alternative alla data 25 luglio. Chi fosse interessato a sostenere la prova orale o, per i non ammessi, a visionare il compito, potrà farlo anche nella giornata del 24 luglio (lunedì). Prego però gli interessati di comunicarmelo precedentemente via email. Sono spiacente di non poter prevedere ulteriori date a causa di impegni precedentemente assunti.
19 luglio 2006
Appello del 18 luglio 2006  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì prossimo (25 luglio 2006), con inizio alle ore 10.30, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
1 luglio 2006
Appello del 29 giugno 2006  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì prossimo (4 luglio 2006), con inizio alle ore 10.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione
16 giugno 2006
Appello del 13 giugno  A parziale correzione del precedente avviso, si informa che gli orali dell'appello in oggetto si terranno in due turni: mattina (ore 10.30) e pomeriggio (ore 14.30) del giorno 20/6/2006. Gli studenti ammessi possono presentarsi indifferentemente a uno dei due turni.
14 giugno 2006
Appello del 13 giugno 2006  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì prossimo (20 giugno 2006), con inizio alle ore 10.30, nello studio del docente presso il dip. di Ingegneria dell'Informazione
24 febbraio 2006
Variazioni orario  Si invitano gli studenti, eventualmente interessati, a prendere nota del cambiamento dell'orario di lezione di alcuni insegnamenti del corso di Laurea in Scienze dell'Informazione (le modifiche non riguardano il presente insegnamento)
28 gennaio 2006
Inizio lezioni  Mercoledì 1 marzo 2006

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 argomenti classici di un corso introduttivo di algoritmica, e cioè le strutture dati di base ed alcune strutture dati avanzate, algoritmi di ordinamento e di selezione, algoritmi su grafo e geometrici. 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.

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
1 marzo 2006 Informazioni generali sull'insegnamento. Introduzione agli algoritmi. Cap. 1, paragrafi 1-3 Dettagli
2 marzo 2006 Introduzione agli algoritmi. Cap. 1, paragrafo 3 Dettagli
2 marzo 2006 Introduzione agli algoritmi. Cap. 1, paragrafi 4-7 Dettagli
7 marzo 2006 Modelli di calcolo Cap. 2, paragrafi 1-3 e 4.1 Dettagli
8 marzo 2006 Metodi di analisi Cap. 2, paragrafi 4.3 e 5.1 Dettagli
9 marzo 2006 Strutture dati elementari Cap. 3, paragrafo 1 Dettagli
14 marzo 2006 Algoritmi per il calcolo dei numeri di Fibonacci Software: 1, 2
14 marzo 2006 Ricerca sequenziale e binaria in un array Software: 1, 2
14 marzo 2006 Tipo di dato dizionario Software: 1, 2
15 marzo 2006 Richiami sulle classi in C++ Dettagli
16 marzo 2005 Pile e code. Esercizi sull'analisi di algoritmi ricorsivi. Cap. 3, paragrafo 2 Dettagli
21 marzo 2006 Pile e code Software: 1, 2
22 marzo 2006 Grafi, alberi e possibili rappresentazioni Cap. 3, paragrafi 3 e 3.1. Cap. 11, paragrafi 1 e 2 Dettagli
23 marzo 2006 Rappresentazioni e visita di alberi Cap. 3, paragrafi 3.2 e 3.3 Dettagli
29 marzo 2006 Ordinamento: algoritmi quadratici e una limitazione inferiore di complessità Cap. 4, paragrafi 1 e 2 Dettagli
30 marzo 2006 Mergesorst, heapsort e quicksort Cap. 4, paragrafi 3, 4 e parte introduttiva del 5 Dettagli
4 aprile 2006 Algoritmi di ordinamento Software: 1, 2
5 aprile 2006 Quicksort (versioni ricorsiva e iterativa). Integer sort Cap. 4, paragrafo 5 (senza dim.) e 6 Dettagli
6 aprile 2006 Bucket e radix sort. Selezione e statistiche d'ordine Cap. 4 paragrafi 6 e 7. Cap. 5, paragrafi 1 e 2 Dettagli
10 aprile 2006 Calcolo deterministico del mediano. Esercizi su temi d'esame Cap. 5, paragrafo 3 Dettagli
11 aprile 2006 Statistiche d'ordine Software: 1, 2
20 aprile 2006 Tecniche algoritmiche Cap. 10, paragrafi 1 (escluso 1.2) e 2 Dettagli
2 maggio 2006 Programmazione dinamica Software: 1, 2
3 maggio 2006 Programmazione dinamica, tecnica greedy Cap. 10, paragrafi 2.1, 3.1 e 3.2 Dettagli
4 maggio 2006 Visita di grafi Cap. 11, paragrafi 3 e 4 Dettagli
9 maggio 2006 Algoritmi greedy e visita di grafi Software: 1, 2
10 maggio 2006 Minimo albero di copertura Cap. 12, paragrafi 1, 2 e 3 Dettagli
11 maggio 2006 Strutture union-find Cap. 9, paragrafi 1, 2 e 3 (escluso union-by-size) Dettagli
16 maggio 2006 Visita di grafi e minimo albero di copertura Software: 1, 2
17 maggio 2006 Algoritmo di Kruskal con union-find, code con priorità Cap. 12, paragrafi 2.1. Cap. 8, paragrafo 1 Dettagli
18 maggio 2006 Algoritmo di Prim e code con priorità. Svolgimento di esercizi. Cap. 8, paragrafo 1. Cap. 12, paragrafo 3.1 Dettagli
23 maggio 2006 Svolgimento di esercizi d'esame Dettagli
24 maggio 2006 Problemi di cammino minimo su grafi orientati Cap. 13, paragrafo 1 Dettagli
25 maggio 2006 Alg. di Bellman-Ford, cammini su grafi aciclici, algoritmo di Dijkstra Cap. 13, paragrafi 2, 3, 4 e 5 (escluso 5.1) Dettagli
30 maggio 2006 Esercitazione su tutti gli argomenti del corso Dettagli
31 maggio 2006 Calcolo di cammini minimi Cap. 13, paragrafo 5.1 Dettagli
31 maggio 2006 Algoritmi geometrici Cap. 15, paragrafo 1 (introduzione) e 1.3 Dettagli
7 giugno 2006 Esercitazione su tutti gli argomenti del corso Dettagli

Esami

Modalità

Prova scritta e orale

Appelli

Data appello Ora Luogo Esito scritto
13 giugno 2006 14.30 Dipartimento di Matematica, Aula I Visualizza
29 giugno 2006 9.00 Dipartimento di Matematica, Aula I Visualizza
18 luglio 2006 14.30 Dipartimento di Matematica, Aula I Visualizza
19 settembre 2006 14.30 Dipartimento di Matematica, Aula V Visualizza
18 gennaio 2007 10.00 Dipartimento di Matematica, Aula IV Visualizza
7 febbraio 2007 10.00 Dipartimento di Matematica, Aula IV Visualizza
 
http://algo.ing.unimo.it
Ultimo aggiornamento della pagina: 28 gennaio 2006.
Mauro Leoncini (leoncini AT unimore DOT it)

Valid HTML 4.01! Valid CSS! Eurolinux Software Patent Petition