Algoritmica e Laboratorio - Corso A - 2008/2009

Informazioni Generali

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio.

Ricevimento studenti
Ferragina	16-19	Lunedì	Stanza 295, Dipartimento di Informatica

Orario Lezioni

Orario delle Lezioni
Lunedì	11-13	A	Teoria
Martedì	9-11	A	Teoria
Mercoledì	9-11	A	Teoria
Giovedì	11-13	H	Laboratorio

Si pregano gli studenti che dispongono di un portatile di portarlo in Laboratorio.

Appelli di Esame

Data	Tipo Prova	Documento	Note
07/04/09	1° Compitino	testo e soluzione
25/05/09	2° Compitino	testo e soluzione	Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) il primo compitino.
28/05/09	Prova Lab	testo e soluzione	Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) entrambi i compitini. Laboratori H e M ore 16.
10/06/09	Appello 1	testo dello scritto e prova di laboratorio con soluzione	Prova di Algoritmica ore 9, aule H,I,M,A1,L1. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M.
26/06/09	Appello 2	testo dello scritto e prova di laboratorio , casi di test	Prova di Algoritmica ore 9, aule A1,D1,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M.
14/07/09	Appello 3	testo dello scritto e prova di laboratorio	Prova di Algoritmica ore 9, aule A,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M.
11/09/09	Appello 4	testo dello scritto e prova di laboratorio	Prova di Algoritmica ore 9, aule A. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M.
11/01/10	Appello 5	testo dello scritto e prova di laboratorio	Prova di Algoritmica ore 9. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M.

Libro di testo

[CGG] P. Crescenzi, G. Gambosi, R. Grossi. Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2005.
- Per approfondimenti ed errata: http://www.algoritmica.org/sda/pmwiki.php
Per il laboratorio, un testo fra:
- [KR] B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.
- [KP] A. Kelley, I. Pohl. C: Didattica e Programmazione, Addison-Wesley, quarta edizione, 2004.

Materiale per il Laboratorio

Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
Strumenti per la programmazione: Un editore testuale (tipo Emacs), e il compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows suggeriamo il compilatore e il debugger disponibili con MinGW, e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per AIL), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.

Programma del corso

Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
Ordinamento di interi: Counting sort, Radix Sort.
Ordinamento di stringhe: qsort-based e multi-key quicksort.
Sottosequenza di somma massima.
Programmazione dinamica: LCS, Partizione e Zaino
Generazione di combinazioni e permutazioni
Greedy: Huffman e Interval Scheduling
Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
Alberi: rappresentazione e visite.
Trie: rappresentazione, ricerca, Lcp e modifica.
Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
Algoritmi randomizzati: Quicksort, Karp-Rabin.
Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.

Registro delle Lezioni

Data	Argomento	Rif. Biblio
23/2/09	Laboratorio: richiami di linguaggio C. Editing, compilazione, debugging.	C code
24/2/09	Laboratorio: richiami di linguaggio C. Istruzioni varie e operatori, printf, scanf, vettori	Cap. 2-3, 7.1-7.4 di [KR], C code
26/2/09	Laboratorio: richiami di linguaggio C. Puntatori, funzioni e passaggio parametri	Cap. 5 di [KR], slides, C code
27/2/09	Laboratorio: richiami di linguaggio C. Allocazione dinamica della memoria (malloc), stringhe, vettori bidimensionali. Esercizio per casa: calcolo del bigramma di massima frequenza in una stringa.	Cap. 4 di [KR],slides, C code
2/3/09	Introduzione al corso: prerequisiti, definizione di algoritmo, modello RAM, problema formale e istanza, dimensione di una istanza, complessità in tempo e spazio, analisi asintotica al caso pessimo e caso medio, numero passi, confronto tra algoritmi.	Sez. 1.4 e 2.1 di [CGG]
3/3/09	Problema della sottosequenza di somma massima: algoritmi e analisi di complessità in tempo al caso pessimo. Classi P, NP e NP-completi (cenni). Risolvere vs Verificare. Un esempio di problema NP-Completo: Subset sum.	Sez. 2.3 di [CGG]
4/3/09	Problemi EXP-TIME. Problemi decidibili vs indecidibili. Tecnica della diagonalizzazione. Problema della fermata.	Sez. 1.1, 1.2, 1.2.1 e 1.3 di [CGG]. Non fare 1.2.2.
5/3/09	Laboratorio: Problema del Maggioritario: soluzione quadratica e lineare. Esercizio per casa: coding delle 3 soluzioni per il problema della “sottosequenza di somma massima”.	esercizi, testfile, C code
9/3/09	Notazione: O-grande, Omega-grande, o-piccolo, omega-piccolo e theta. Alcuni esercizi sulla notazione e sua interpretazione in termini di complessità di algoritmi e/o problemi. Introduzione al problema dell'ordinamento e algoritmo SelectionSort con analisi della complessità.	Sez. 2.2.1 e pag. 10 dell'appendice dell'errata corrige di [CGG].
10/3/09	Insertion Sort: proprietà e complessità. Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni. Esempi: min/max, ricerca di una chiave, ordinamento. Problema della ricerca di una chiave: scansione e ricerca binaria (iterativa e ricorsiva).	Sez. 2.2.2 e 2.3.1 e 2.4 di [CGG]. Studiare anche questo approfondimento dal libro di F. Luccio “La struttura degli algoritmi” (Boringhieri, 1982).
11/3/09	Tecnica “divide et impera”. Relazioni di Ricorrenza e teorema per la loro risoluzione (con dimostrazione). Risoluzione ricorsiva del problema “del massimo” e analisi di complessità. MergeSort: algoritmo, proprietà, e analisi della complessità.	Sez. 2.5.1 e 2.5.3 di [CGG], con teorema e sua dimostrazione alle pagine 10-11 dell'Errata Corrige.
12/3/09	Laboratorio: Lettura di un array da tastiera senza conoscerne la lunghezza: tecnica del doubling. Calcolo del numero di elementi distinti in un array ordinato. Esercizio per casa: coding di Selection Sort e Insertion Sort.	esercizi, testfile, C code
16/3/09	Moltiplicazione veloce di due interi di n cifre. Esercizi sul calcolo della complessità di algoritmi ricorsivi. Calcolo del numero x di occorrenze di un elemento in un vettore parzialmente ordinato di lunghezza n: soluzione O(n), soluzione di costo O(log n + x), soluzione di costo O(logn).	Sez. 2.5.2
17/3/09	Quicksort: proprietà, analisi della complessità (caso medio, ottimo e pessimo) e considerazioni pratiche. Due tecniche di “distribuzione. qsort del C come quicksort + insertionSort	Sez. 2.5.4 e per altra tecnica di distribuzione (oltre al codice 2.14) studiare anche questi appunti
18/3/09	Quicksort randomizzato. QuickSelect. Genera Binarie. Genera Permutazioni.	Sez. 1.2.2
19/3/09	Laboratorio: Implementazione del Quick Sort. Esercizio per casa: coding del Quicksort con three-way partition.	esercizi, C code
23/3/09	Programmazione dinamica e ricorsione con tabulazione (memoization): esempio con i numeri di Fibonacci. Sottosequenza comune più lunga: regola ricorsiva.	Sez. 2.7 tutta
24/3/09	Programmazione dinamica: Sottosequenza comune più lunga (lunghezza) – metodo di riempimento della tabella per riga/colonna/diagonale. Calcolo di una sottosequenza comune avente la lunghezza massima, calcolo della tabella in spazio ridotto (due sole righe). Partizione di un insieme di interi: regola ricorsiva.
25/3/09	Partizione di un insieme di interi: tabella e calcolo di una soluzione. Problemi NP-completi e algoritmi pseudo-polinomiali. Esercizio su “calcolo del minimo numero di caratteri da inserire in una stringa per renderla palindroma”.
26/3/09	Laboratorio: Esercizi con qsort su array di interi e stringhe. Esercizio per casa: ricerca su un array di stringhe ordinate e esercizio Divide-et-impera.	esercizi, C code
30/3/09	Counting Sort ed esercizi. Esempio di calcolo della tabella per la sottosequenza comune più lunga tra due stringhe.	appunti prestando attenzione al fatto che nello pseudo-codice gli indici degli array iniziano da 1
31/3/09	Esercizi su Divide-et-impera. Ordinamento dei suffissi di un testo con soluzione più che quadratica.
1/4/09	Ordinamento dei suffissi di un testo con il `qsort`. Radix sort e analisi della complessità.	appunti
2/4/09	Multi-key Quicksort, e analisi della sua complessità. Fingerprint di Karp-Rabin, analisi, e suo uso nel problema del dizionario di stringhe.	appunti su Multi-key quicksort, prestare attenzione al fatto che le stringhe hanno indici da 1 invece che 0, e quindi in classe abbiamo messo l invece di l+1. Per quanto riguarda KR-fingerprint si legga questo estratto di libro.
6/4/09	Esercitazione pre-compitino.
	Challenge: E' dato un testo che contiene una sottostringa ripetuta due volte e di lunghezza circa 1600 caratteri. Tutte le altre sottostringhe che si ripetono in questo testo hanno una lunghezza inferiore a 300 caratteri. Progettare un algoritmo che scopre quella sottostringa e la stampa a video. Gruppi di lavoro: composti da al massimo 2 studenti. Codice: Utilizzare questo esempio di programma C per poter leggere il testo dal suddetto file. Come partecipare: La soluzione –frase ripetuta e codice dell'algoritmo in C– deve essere spedita via email a `[email protected]` entro le ore 20:00 del 14 Aprile 2009. L'email deve avere soggetto “Challenge Corso A”, e deve riportare i nomi e le email degli studenti che l'hanno ottenuta.	Una possibile soluzione. Hanno partecipato con successo i gruppi: Ciccarelli-Miglianesi, Guelfi, Zanotto-Sabadin.
16/4/09	Laboratorio: Le struct in `C`. Esercizio per casa: Leggere una stringa da stdin, costruire tutti i suoi k-grammi (dove k è passato come input), contare le loro frequenze, e poi ordinarli in ordine decrescente di frequenza.	Sez. 6.1-6.4 di [KR] e C code.
20/4/09	Le liste: definizione e codice C. Operazioni di ricerca per chiave e posizione, inserimento e cancellazione. Esercizio su: inclusione tra due liste. Il problema UNION-FIND e sua soluzione efficiente.	Sez. 3.1 e 3.4.1
21/4/09	L'analisi ammortizzata: Union-Find, k-ricerche in un vettore, il contatore binario, array dinamico. L'analisi competitiva: Move-To-Front.	Sez. 3.4.2 e 3.4.3.
23/4/09	Laboratorio: Esercizi con le liste. Creazione di una lista e stampa dei suoi elementi. Ricerca in una lista e Move-To-Front.	esercizi C code
27/4/09	Algoritmi Greedy: Interval Scheduling e Codice di Huffman.	appunti su Interval Scheduling e appunti su Codice di Huffman
28/4/09	Codice di Huffman: esempio e dimostrazione di ottimalità.
29/4/09	Tabelle hash: definizione, proprietà, gestione dei conflitti (liste di trabocco e indirizzamento aperto), con analisi della complessità al caso pessimo e al caso medio.	Sez. 5.1-5.3
30/4/09	Laboratorio: Esercizi con le tabelle hash con gestione dei conflitti tramite liste di trabocco.	esercizi C code
4/5/09	Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo.	Tutta la sez. 4.1
5/5/09	Alberi Binari di Ricerca: definizione, proprietà e algoritmi per la ricerca di una chiave, l'inserimento e la cancellazione di un nodo.	Sez. 5.4
6/5/09	Alberi 1-bilanciati e alberi di Fibonacci. Alberi AVL e tecniche di bilanciamento: rotazione oraria e anti-oraria.	Sez. 5.4
7/5/09	Laboratorio: Esercizi con alberi.	esercizi C code ulteriori esercizi sulle liste
11/5/09	Trie: definizione, proprietà, ricerca esatta/prefisso, inserimento di una chiave. Richiami di Code e Pile, con loro implementazione mediante array e lista.	Sez. 5.6.1, 7.1, 7.3
12/5/09	La struttura dati Heap: definizione, proprietà, ricerca, Enqueue, Dequeue, decreaseKey, Heapify.	Sez. 8.1 e 8.2
12/5/09	Esercitazione
13/5/09	Costruzione Heap e heapsort. Grafi: terminologia e notazione.	Sez. 8.2.3 e 6.1
14/5/09	Laboratorio: Esercizi su Heap e Alberi. E' stata descritta la modalità di svolgimento della prova di laboratorio, il file `mainCompito.c`, qui in allegato, contiene lo schema di codice C preliminare che verrà distribuito all'inizio di ogni prova.	esercizi, testfile
18/5/09	Grafi: rappresentazione e chiusura transitiva. Visita BFS.	Sez. 6.1.2, 6.1.3, 7.4.1
19/5/09	Visita DFS. DAG e ordinamento topologico	Sez. 7.4.2, 7.5.1. Note dal libro Cormen et al, non fare le dimostrazioni del teo 22.7, 22.9 e 22.10.
19/5/09	Esercitazione	ore 16-18 aula E, ore 18-19 prova del sistema di sottomissione per la prova in Lab.
20/5/09	Componenti (fortemente) connesse	Sez. 7.5.2
21/5/09	Ricevimento studenti	Ore 17, studio Ferragina