Algoritmica, 2006-07

Questa è la pagina dell'insegnamento Algoritmica del corso di laurea in Scienze dell'Informazione, Università di Modena e Reggio Emilia, per l'A.A. 2006/07. Gli studenti del primo anno di Matematica fruiscono dell'insegnamento sotto il nome di Informatica Generale II.

La pagina contiene le seguenti sezioni:

Orario delle lezioni

Avvisi (in ordine cronologico inverso)

20 febbraio 2008
Appello di domani, 21 febbraio 2008.  La prova scritta avrà luogo in aula XII, presso il Dipartimento di Matematica (ore 11.00).
18 gennaio 2008
Risultati dello scritto del 17 gennaio 2008.  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta.La prova orale si terrà il giorno 23 gennaio 2008 con inizio alle ore 10.00, nello studio del docente presso il Dip. di Ingegneria dell'Informazione.
31 dicembre 2007
Date degli appelli.  I prossimi appelli si terrammo nei giorni 17 gennaio 2008 e 21 febbraio 2008, alle ore 11.00. L'appello del 17 gennaio 2007 avrà luogo nell'Aula VIII del Dipartimento di Matematica (l'aula per l'appello di febbraio verrà comunicata con successivo avviso).
4 dicembre 2007
Appello straordinario per fuori corso  L'appello dell'11 dicembre 2007 si svolgerà alle ore 14.30 in Aula X presso il Dipartimento di Matematica.
20 novembre 2007
Appello straordinario per fuori corso  Il giorno martedì 11 dicembre 2007 si terrà un appello straordinario riservato agli studenti fuori corso (sia di Scienze dell'Informazione sia di matematica). Con successiva comunicazione verrà indicata l'ora e il luogo. È obbligatorio iscriversi completando e inviando la seguente email parzialmente precompilata entro il giorno 30 novembre 2007.
7 settembre 2007
Appello del 6 settembre 2007  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì 11 settembre, con inizio alle ore 10.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
21 luglio 2007
Appello del 19 luglio 2007  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì 24 luglio, con inizio alle ore 14.30, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
3 luglio 2007
Spostamento data orali  Causa malattia del docente, gli esami orali previsti per domani (4 luglio 2007) sono spostati a lunedì 9 luglio 2007, ore 14.00, sempre presso lo studio del docente (che si scusa per i possibili disagi).
28 giugno 2007
Appello del 27 giugno 2007  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno mercoledì 4 luglio, con inizio alle ore 9.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
15 giugno 2007
Appello del 13 giugno 2007  Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli orali si terranno martedì 19 giugno, con inizio alle ore 9.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
23 maggio 2007
Prova d'esame simulata  La prova si terrà martedì 29 maggio 2007, a partire dalle ore 14.15, nell'Aula IV del Dipartimento di Matematica
18 maggio 2007
Date appelli  Nella sezione relativa agli esami sono state inserite le date dei prossimi appelli (sessioni di giugno-luglio e settembre)
21 marzo 2007
Rinvio esercitazione.  L'esercitazione di laboratorio del 27 marzo 2007 è rinviata a causa di indisponibilità del docente. Con successivo avviso verrà comunicata la data del recupero.
28 febbraio 2007
Inizio lezioni  Le lezioni inizieranno regolarmente domani, 1 marzo 2007, alle ore 9.00 nell'aula IV del Dipartimento di Matematica

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, i grafi e gli algoritmi di base sui grafi, oltre ad un campione "selezionato" di algoritmi particolarmente significativi dal punto di vista delle metodologie di sviluppo e delle applicazioni. 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 dalle elevate prestazioni.

Programma

Lezioni e materiale didattico

Libro di testo

P. Crescenzi, G. Gambosi, R. Grossi
Strutture di dati e algoritmi
Pearson Education Italia S.r.L.

Libri di consultazione

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

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
Introduzione agli algoritmi e strutture dati
McGraw-Hill

Lezioni

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

Data lezione Argomento Libro di testo Materiale
1 marzo 2007 Informazioni generali sull'insegnamento. Obiettivi. Problemi indecidibili. Paragrafo 1.1
2 marzo 2007 Problemi indecidibili e problemi intrattabili. Problemi probabilmente intrattabili.
La classe NP. Il problema del commesso viaggiatore. Dimensione dei problemi.
Algoritmi polinimiali ed esponenziali. Modello di calcolo astratto (macchina di Von Neumann).
Calcolo del "tempo di esecuzione" di un programma.
Paragrafi 1.1-1.4
6 marzo 2007 Laboratorio: algoritmi e programmi ricorsivi Paragrafi 1.2 e 1.3 Lucidi e software: 1, 2
7 marzo 2007 Sequenze lineari. Modalità di accesso e allocazione della memoria.
Array di dimensione variabile. Il problema dello scheduling della CPU.
Paragrafi 2.1 e 2.2 (introduzione)
8 marzo 2007 Problema dell'ordinamento. Ordinamento per selezione (solo cenni) e per inserimento.
Calcolo parametrizzato del tempo di esecuzione dell'insertion sort.
Paragrafi 2.2.1, 2.2.2 e 2.3
9 marzo 2007 Complessità  dei problemi computazionali: limiti superiori e inferiori. Problema del segmento di somma massima
Ricerca sequenziale e ricerca binaria. Complessità della ricerca per confronti.
Paradigma divide-et-impera, ricorsione ed equazioni di ricorrenza.
Formulazione ricorsiva della ricerca binaria.
Paragrafi 2.3, 2.4 e 2.5 (introduzione)
13 marzo 2007 Esercizi di base sulle sequenze. Ordimento per inserimento. Stima dei tempi di esecuzione. Lucidi e software: 1, 2
14 marzo 2007 Algoritmo di inserimento per fusione (mergesort). Teorema fondamentale delle ricorrenze.
Moltiplicazione veloce di numeri interi. Ordinamento per distribuzione (quicksort).
Paragrafi 2.5.1, 2.5.2, 2.5.3 e 2.5.4 (parte iniziale)
15 marzo 2007 Algoritmo di ordinamento per distribuzione (quicksort). Dimostrazione di correttezza. Calcolo del tempo d'esecuzione nel best-case e nel worst-case. Paragrafo 2.5.4
16 marzo 2007 Analisi del comportamento "in media" del quicksort con scelta casuale (uniforme) del pivot.
Moltiplicazione di matrici: motivazioni applicative dal settore della "computer graphics" per lo sviluppo di algoritmi efficienti. Algoritmo di Strassen. Introduzione al problema della moltiplicazione di una sequenza di matrici.
Paragrafi 2.5.4, 2.5.5, 2.6 (introduzione), 2.6.1 e 2.6.2
20 marzo 2007 Laboratorio: implementazione dell'algoritmo mergesort Lucidi e software: 1, 2
21 marzo 2007 Moltiplicazione di una sequenza di matrici. Algoritmo ricorsivo per il calcolo del numero ottimo (minimo) di operazioni. Analisi del costo e delle ragioni di inefficienza. Soluzione più efficiente mediante tecnica di "memoization". Paragrafo 2.6.2
22 marzo 2007 Algoritmo di programmazione dinamica per il problema della sequenza di moltiplicazioni di matrici Paragrafo 2.6.2
23 marzo 2007 Esercitazione sul calcolo di sommatorie e soluzione di ricorrenze
28 marzo 2007 Paradigma della programmazione dinamica: aspetti generali. Problema del calcolo della sottosequenza comune pił lunga (LCS). Paragrafi 2.7 (introduzione) e 2.7.1
29 marzo 2007 Problema del partizionamento di un insieme di interi. Cenni su pseudopolinomialità e programmazione dinamica. Paragrafi 2.7.2 e 2.7.4
30 marzo 2007 Esercizi svolti alla lavagna su tecnica divite-et-impera e programmazione dinamica
3 aprile 2007 Laboratorio: implementazione dell'algoritmo quicksort Lucidi e software: 1, 2
4 aprile 2007 Liste concatenate, liste doppie e liste circolari. Problema dei matrimoni stabili. Soluzione algoritmica. Paragrafi 3.1 e 3.2
12 aprile 2007 Dimostrazione di correttezza dell'algoritmo per il problema dei matrimoni stabili. Strutture dati e implementazione. Paragrafo 3.2
13 aprile 2007 Concetti generali sui grafi. Alberi liberi e alberi radicati. Rappresentazione di alberi (radicati) mediante strutture collegate. Alberi binari. Algoritmi ricorsivi su alberi binari. Paragrafi 6.1, 4.1 (introduzione) e 4.1.1
17 aprile 2007 Laboratorio: implementazione dell'algoritmo per il calcolo della Longest Common Subsequence Lucidi e software: 1, 2
18 aprile 2007 Nozione di bilanciamento di un albero binario. Visite di alberi binari (anticipata, simmetrica, posticipata e in ampiezza). Problema del minimo antenato comune. Paragrafi 4.1.1 e 4.2
19 aprile 2007 Riduzione del problema del minimo antenato comune al problema del calcolo del minimo in un intervallo di numeri Paragrafo 4.2.1
20 aprile 2007 Soluzione in spazio O(n log n) al problema del minimo in un intervallo. Visita per ampiezza e rappresentazione implicita di alberi binari. Paragrafi 4.2.2 e 4.3 (introduzione) e 4..3.1
24 aprile 2007 Laboratorio: implementazione dell'algoritmo per il calcolo dei matrimoni stabili (stable marriage) Lucidi e software: 1, 2
26 aprile 2007 Svolgimento di esercizi d'esame su (algoritmi definiti su) alberi binari
27 aprile 2007 Ancora esercizi sugli alberi binari (algoritmi definititi su alberi binari e proprietà di alberi binari)
2 maggio 2007 Dizionari. Cenni alla realizzazione mediante liste. Realizzazione mediante tabelle hash. Paragrafi 5.1, 5.2 e 5.3
3 maggio 2007 Gestione delle collisioni mediante liste di trabocco. Indirizzamento aperto con scansione lineare Paragrafi 5.3.1 e 5.3.2
4 maggio 2007 Indirizzamento aperto con hashing doppio. Alberi binari di ricerca. Realizzazione delle operazioni di ricerca, inserzione e cancellazione. Paragrafi 5.3.2 e 5.4.1
8 maggio 2007 Laboratorio: realizzazione di un dizionario mediante hashing dizionario.c
9 maggio 2007 Alberi AVL. Problemi definiti su grafo Paragrafi 5.4.2 e 6.1.1
10 maggio 2007 Problemi definiti su grafo. Rappresentazione di grafi mediante matrice di adiacenza e liste di adiacenza. Connettività e prodotto di matrici. Paragrafi 6.1.1, 6.1.2 e 6.1.3
11 maggio 2007 Calcolo efficiente della chiusura transitiva. Calcolo del page rank di una pagina web. Paragrafi 6.1.3, 6.4 (introduzione) e 6.4.1
15 maggio 2007 Laboratorio: implementazione dell'algoritmo di page rank Lucidi e software: 1, 2
16 maggio 2007 Pile e code. Definizioni ed implementazione mediante array e liste. Paragrafi 7.1 e 7.3
17 maggio 2006 Web crawling e visita di grafi. Visita in ampiezza. Paragrafi 7.4 (introduzione) e 7.4.1
22 maggio 2007 Laboratorio: implementazione dell'algoritmo di ricerca in ampiezza. Lucidi e software: 1, 2
23 maggio 2007 Visita in profondità di un grafo e applicazioni (determinazione della presenza di cicli e calcolo di ordinamenti topologici di grafi diretti aciclici). Paragrafi 7.4.2, 7.5 (introduzione) e 7.5.1
24 maggio 2007 Code con priorità, struttura heap e algoritmo heapsort. Paragrafi 8.1 e 8.2
29 maggio 2007 Prova di autovalutazione e relativa correzione.
30 maggio 2007 Algoritmi di cammino minimo (single source) su grafi pesati: Dijkstra e Bellman-Ford. Paragrafo 8.3
31 maggio 2007 Algoritmi per il calcolo del Minimum-Spanning-Tree in grafi pesati (sugli archi): Kruskal e Jarnik-Prim. Paragrafo 8.4

Esami

Modalità

Prova scritta e orale

Appelli

Data appello Ora Luogo Esito scritto
13 giugno 2007 15.00 Dipartimento di Matematica, Aula IV Visualizza
27 giugno 2007 15.00 Dipartimento di Matematica, Aula I Visualizza
19 luglio 2007 10.00 Dipartimento di Matematica, Aula I Visualizza
6 settembre 2007 15.00 Dipartimento di Matematica, Aula I Visualizza
17 gennaio 2008 11.00 Dipartimento di Matematica, Aula VIII Visualizza
21 febbraio 2008 11.00 Dipartimento di Matematica, Aula XII
 
http://algo.ing.unimo.it
Ultimo aggiornamento della pagina: 28 febbraio 2007.
Mauro Leoncini (leoncini AT unimore DOT it)

Valid HTML 4.01! Valid CSS! Eurolinux Software Patent Petition