Indice

Algoritmica - corso A e B

Docente: Linda Pagli

Programma del corso

Programma

Orario delle lezioni

Giorno Orario Aula
Lun 9-11 A
Mar 9-11 A
Gio 9-11 A

Orario di ricevimento

Durante il periodo di lezione e esami:

Giorno Orario Luogo
Mercoledì 15.30-18.30 Studio Pagli (277DE) presso Dipartimento di Informatica

Altrimenti concordare via posta elettronica

Avvisi Urgenti

Per tutti gli avvisi urgenti vedete nella pagina degli avvisi.
E' possibile richiedere di essere avvisati automaticamente via e-mail ogni volta che un nuovo avviso viene postato. Seguire le istruzioni indicate nelle FAQ.

Materiale didattico

Il libro di testo è: P.Crescenzi, G.Gambosi, R.Grossi. Strutture di dati e algoritmi. Pearson-Addison Wesley 2006. ERRATA.

Al link http://www.algoritmica.org è disponibile il software di visualizzazione per quasi tutti gli algoritmi del libro.

Testo di consultazione di carattere enciclopedico è: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, second edition, 2001.

Altro testo di consultazione: C.Demetrescu, I. Finocchi, G. Italiano: Algoritmi e Strutture Dati, MacGraw-Hill, seconda edizione 2008.

Modalità di esame

L’esame di Algoritmica consiste di una prova scritta e di una prova orale. Durante la prova scritta gli studenti non possono consultare i propri libri e appunti. L'esame scritto dunque consiste di esercizi e domande teoriche. Il superamento di entrambe le verifiche intermedie consente l'esonero dalla prova scritta per la sola sessione invernale.

Risultati e soluzioni

soluzione primo appello

soluzione secondo appello

Registro delle lezioni

Giorno Ore Argomenti Riferimenti
22/9/2008 2 Lezione: Introduzione agli algoritmi. Problema delle 12 monete.
23/9/2008 2 Lezione: Problemi indecidibili. Problema della fermata. Problemi intrattabili. Torri di Hanoi e crescita esponenziale. Cap. 1, par. 1.1, 1.2
25/9/2008 2 Lezione: Classi di complessità P, NP e NPC e relazioni tra esse. Sudoku, backtracking, verifica polinomiale. Cap. 1, par. 1.3
29/9/2008 2 Lezione: Problema della Partizione, Generazione di stringhe binarie, Modello RAM Cap. 1, par. 1.4
30/9/2008 2 Lezione: Complessità asintotica, Notazioni “Teta”, “O” grande e “Omega” Dispense in copisteria
2/10/2008 2 Esercitazione: Confronto tra funzioni. Segmento di somma massima: 3 soluzioni di complessità decrescente Par.2.3, 2.3
6/10/2008 2 Lezione: Allocazione dinamica della memoria, Limiti inferiori, albero di decisione. Par.2.1.3, 2.3.1
7/10/2008 2 Lezione: Il problema della ricerca: limite inferiore. Tecnica Divide et Impera, Ricerca Binaria Par.2.4, 2.5
9/10/2008 2 Esercitazione: Modifica di ricerca binaria per il calcolo del Rango. Alg. Divide et impera per determinare il Minimo e il Massimo di un insieme
13/10/2008 2 Lezione: Teorema fondamentale. Moltiplicazione Rapida. MergeSort Par.2.5.1, 2.5.2, 2.4.3
14/10/2008 2 Esercitazione: Esercizi sul teorema fondamentale. Algoritmo di Fusione, MergeInsertionSort.
16/10/2008 2 Lezioni sospese dal Preside.
20/10/2008 2 Lezioni sospese dal Preside.
21/10/2008 2 Lezione: Quicksort, Quickselect, analisi del tempo medio. Par.2.5.4, 2.5.5
23/10/2008 2 Lezione: Moltiplicazione di matrici. Par.2.6, 2.6.1
27/10/2008 2 Lezione: Serie di Fibonacci. Tecnica della Programmazione Dinamica. Fibonacci, Par.2.7
28/10/2008 2 Esercitazione: Esercizi su equazioni di ricorrenza, serie di Fibonacci e Divide et impera.Esercizi
29/10/2008 2 Esercitazione: Soluzione del compito del novembre 2007. Compito07
30/10/2008 2 Esercitazione: Esercizi su equazioni di ricorrenza e Divide et impera.
03/11/2008 2 Esercitazione scrittaprimocompitino.doc
06/11/2008 2 Esercitazione: Correzione del primo compitino.
10/11/2008 2 Lezione: Programmazione Dinamica: LCS; Ricostruzione della sequenza. Par.2.7.1
11/11/2008 2 Lezione: Programmazione Dinamica: Partizione e Zaino; Ricostruzione delle soluzioni. Problemi Pseudo-polinomiali. Par.2.7.2, 2.7.3, 2.7.4
13/11/2008 2 Lezione: Il problema dei matrimoni stabili. Strutture, algoritmo e dimostrazione di correttezza. Par.3.2, 3.2.1, 3.2.2
17/11/2008 2 Lezione: Analisi ammortizzata. Liste autoaggiustanti, Move to Front. Par. 3.4.2
18/11/2008 2 Lezione: Tecniche di analisi ammortizzata. Alberi e alberi binari. Par.3.4.3, 4.1
20/11/2008 2 Lezione: Alberi: Visite, Decomposizione, nodo cardine. Visita in ampiezza, trasformazione primo figlio, successivo fratello. Par. 4.1.1, 4.1.2, 4.3.1, 4.3.2, 4.4
24/11/2008 1 Lezione: Dizionari come tabelle hash: funzioni hash Par. 5.3
25/11/2008 2 Lezione: Tabelle hash: liste di trabocco e indirizzamento aperto Par. 5.3.1, 5.3.2
01/12/2008 2 Lezione: Dizionari come alberi binari di ricerca. Operazioni fondamentali. Par. 5.4, 5.4.1
02/12/2008 2 Lezione: Alberi AVL. Alberi di Fibonacci. Rotazioni Par. 5.4.2
03/12/2008 2 Esercitazione: Esercizi e applicazioni di tabelle hash.
04/12/2008 2 Lezione: Grafi, definizioni, rappresentazione, visite BFS e DFS Par. 6.1, 6.1.2, 6.1.3, 7.4.1, 7.4.2
09/12/2008 2 Lezione: Esempi di visite. Code con priorità, Heap, operazioni di Inserzione e Estrazione in tempo logaritmico. Creazione e Heapsort Par. 8.1, 8.2.2, 8.2.1, 8.2.3
10/12/2008 2 Esercitazione: Esercizi su alberi binari e alberi binari di ricerca Par. 8.1, 8.2.2, 8.2.1
11/12/2008 2 Esercitazione: Esercizi di riepilogo e su alberi bilanciati
15/12/2008 2 Esercitazione: Il problema dell'Edit Distance, esercizi su grafi e alberi immagine binaria di alberi ordinali