Strumenti Utente

Strumenti Sito


informatica:all-a:all08:start

Algoritmica e Laboratorio - Corso A - 2008/2009

Informazioni Generali

Docente: Paolo Ferragina

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.
11/01/10 Appello 6 testo dello scritto e prova di laboratorio

Libro di testo

  • [CGG] P. Crescenzi, G. Gambosi, R. Grossi. Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2005.
  • 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

  1. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
  2. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  3. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
  4. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  7. Ordinamento di interi: Counting sort, Radix Sort.
  8. Ordinamento di stringhe: qsort-based e multi-key quicksort.
  9. Sottosequenza di somma massima.
  10. Programmazione dinamica: LCS, Partizione e Zaino
  11. Generazione di combinazioni e permutazioni
  12. Greedy: Huffman e Interval Scheduling
  13. Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
  14. Alberi: rappresentazione e visite.
  15. Trie: rappresentazione, ricerca, Lcp e modifica.
  16. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  17. Algoritmi randomizzati: Quicksort, Karp-Rabin.
  18. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  19. 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 ferragina@di.unipi.it 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
informatica/all-a/all08/start.txt · Ultima modifica: 31/08/2010 alle 18:06 (9 anni fa) da peppe