Strumenti Utente

Strumenti Sito


informatica:all-a:all11:start

Algoritmica e Laboratorio A.A. 2011-2012

Informazioni Generali

Docente: Linda Pagli

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

Semestre: secondo.

Ricevimento studenti: dopo ogni lezione e su appuntamento.

Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Anno accademico 2011/2012

  • A.A. 2011/2012 (NB: il corso è unico; per comodità vengono usate le pagine del corso A)

Anni accademici precedenti

Orario Lezioni

Orario delle Lezioni
Martedì 14-16 A Teoria
Mercoledì 9-11 A Teoria
Giovedì 16-18 H, M Laboratorio
Venerdì 11-13 A Teoria

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

Obiettivi del Corso

L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.

Modalità e Appelli di Esame

L'esame consiste di tre prove:

  • Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18, nel qual caso lo studente è ammesso a sostenere la prova di laboratorio.
  • Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un test di idoneità il cui superamento permette allo studente di essere ammesso a sostenere la prova orale.
  • Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.

Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella.

Per avere una idea della tipologia delle prove, si consultino i testi dell'anno scorso.

Data Tipo Prova Documento Note
07/06/2012, ore 09.30 Scrittoalgo1_07062012.pdf lista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà Mercoledì 13 Giugno alle ore 9 nelle aule H e M; è possibile anche sostenere la prova in altro appello. L'orale sarà il 22 Giugno, alle ore 10 (studio Pagli)
13/06/2012, ore 09.00 Laboratorio Testo e input
26/06/2012, ore 14.30 Scritto algo1_26062012.pdf lista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà Venerdì 29 Giugno alle ore 9:30 nelle aule H e M. Chi non ha superato lo scritto non è ammesso alla prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. L'orale sarà il 6 luglio alle ore 10 (studio Pagli). Un numero limitato di studenti potrà sostenere l'orale venerdì alle 11 subito dopo la prova di laboratorio, sempre nell'ufficio Pagli.
29/06/2012, ore 09.30 Laboratorio Testo e input
11/07/2012, ore 09.30 Scritto algo1_11072012.pdflista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà venerdì 13 luglio alle ore 9:00 nelle aule H e M. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per venerdì 13 dopo la prova di laboratorio oppure il 19 luglio alle 10 ufficio Pagli.
13/07/2012, ore 09.00 Laboratorio Testo e input
11/09/2012, ore 15 Scritto algo1_11092012.pdflista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà il 13 settembre alle ore 9:30 nelle aule H e M. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il 13 alle 15 oppure il 21 settembre alle 10 ufficio Pagli.
13/09/2012, ore 09.30 Laboratorio Testo e input
15/01/2013, ore 9.30 Scrittoalgo1_150113.pdf risalg15-01-2013.pdf Coloro che hanno superato lo scritto con un voto ≥16, possono sostenere la prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il giorno 23 gennaio alle 9.30 nell'ufficio Pagli oppure il 5 febbraio alle 10 (aula A).
18/01/2013, ore 09.30 Laboratorio Testo e input
5/02/2013, ore 9.30 Scrittoalgo1_050213.pdf risalg5-02-2013.pdf Coloro che hanno superato lo scritto con un voto ≥17, possono sostenere la prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il giorno 11 febbraio alle 9.30 oppure il 14 febbraio alle 9.30 nell'ufficio Pagli.
08/02/2013, ore 09.30 Laboratorio Testo

Libri di testo

  • [CLR] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, Third edition, 2009.
  • [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. Oppure istallare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux sopra. 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.
  9. Sottosequenza di somma massima.
  10. Programmazione dinamica: LCS, Partizione e Zaino
  11. Algoritmi randomizzati: Quicksort.
  12. Generazione di combinazioni e permutazioni
  13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  14. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  15. Alberi: rappresentazione e visite.
  16. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  17. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  18. Grafi III: Minimum Spanning Tree e Shortest Path.

Registro delle Lezioni

Data Argomento Rif. Biblio
21/02/2012 Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio appunti
22/02/2012 Definizioni: problema, istanza, dimensione. Problemi indecidibili, il problema della fermata. Problemi intrattabili: le torri di Hanoi, algoritmo, analisi del numero di mosse. Crescita esponenziale. Libro [CGG] cap.1
23/02/2012 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Istruzioni varie e operatori, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi
24/02/2012 Laboratorio: Ripasso e esercizi su funzioni e puntatori. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi Soluzioni
28/02/2012 Definizione classi P, NP, NP-completi, EXPTIME. Esempio di problema in NP: il Sudoku, algoritmo esponenziale. Il certificato polinomiale. Libro [CGG] cap.1
29/02/2012 Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano, k-clique. Esempio di riduzione: SAT - k-Clique. Una riduzione (K-clique).
01/03/2012 Laboratorio: Puntatori, funzioni e passaggio parametri. Sez. 4.1-4.5 e 5.1-5.5 di [KR].
Lucidi Soluzioni
02/03/2012 Laboratorio: Allocazione dinamica della memoria (malloc) e stringhe. Lucidi Soluzioni
06/03/2012 Rappresentazione degli elementi di un insieme con vettore di appartenenza. Generazione di tutte le stringhe binarie, applicazione a PARTITION. Generazione di tutte le permutazioni, applicazione a HAMILTONIAN CYCLE. Esempi di certificati polinomiali. Considerazioni genrali su algortimi ricorsivi. Libro [CGG] cap.1
07/03/2012 Il modello RAM. Selection Sort e Insertion Sort: proprietà e complessità. Valutazione complessità asintotica al caso ottimo e pessimo. Formule utili
08/03/2012 Laboratorio: Sottoarray di somma massima. Redirezione dell'input e timing di un programma. Lucidi TestFile Soluzioni Libro [CGG] Sez.2.3
09/03/2012 Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni e dell'oracolo. Esempi: primo e secondo, ordinamento. Algoritmo del torneo e del doppio torneo. limiti inferiori
13/03/2012 Il problema della ricerca: limite inferiore, ricerca binaria iterativa e ricorsiva, rango. Analisi. Equazioni di ricorrenza. Paradigma Divide et Impera. Libro [CGG] Sez.2.4 e 2.5
14/03/2012 Equazioni di ricorrenza; Teorema principale; Esempi di applicazioni del teorema. ricorrenze
15/03/2012 Laboratorio: Insertion Sort su interi e stringhe. Ricerca Binaria. L'intero mancante. Lucidi Esercizi Soluzioni
16/03/2012 Moltiplicazione rapida, analisi. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort. Libro [CGG] Sez.2.5.2 e 2.5.3
20/03/2012 Moltiplicazione rapida di matrici, analisi. Esercizi su algortimi ricorsivi di tipo Divide et Impera e calcolo della complessità. Libro [CGG] Sez.2.6.1
21/03/2012 Ordinamento per distribuzione, Quick Sort, analisi del caso medio su istanze equiprobabili. Equazioni di ricorrenza non bilanciate, Quick Select per la selezione del k-esimo elemento. Libro [CGG] Sez.2.5.4 + Errata corrige del paragrafo
22/03/2012 Laboratorio: Quick Sort su interi e su stringhe. Varianti (pari&dispari, 3-way partition). La scala e cavalli. Esercizi Quicksort parziale La scala testfile Soluzioni
23/03/2012 Code di priorità. Definizione di Heap, operazioni Enqueue, Dequeue e Read per un Heap di massimo, Complessità. Allocazione implicita in array. Riorganizza Heap. Libro [CGG] Sez.8.1 e 8.2
27/03/2012 Code di priorità. Creazione dell'Heap in tempo lineare, Heap Sort, analisi. Introduzione alla Programmazioen Dinamica Libro [CGG] Sez.8.2.3 Programmazione Dinamica
28/03/2012 Algoritmi di programmazione dinamica per l'Edit Distance e la Longest Common Subsequence. Analisi e ricostruzione delle soluzioni Libro [CGG] Sez.2.7 e 2.7.1
29/03/2012 Laboratorio: Funzione qsort. Esercizi su stringhe e diversi ordinamenti. Il pirellone. Lucidi Esercizi Soluzioni
30/03/2012 Esercitazione scritta. Discussione e soluzione durante la lezione del 17/4. esercitazione_scritta
12/04/2012 Laboratorio: Esercizi con le struct e qsort. Elemento maggioritario e due uova. Lucidi Esercizi Soluzioni
13/04/2012 Counting Sort e Radix Sort. [CLR] cap. 8
17/04/2012 Esercitazione. Discussione e soluzione della esercitazione scritta del 12/04/2012
18/04/2012 Programmazione dinamica per problemi difficili: Partizione e Zaino. Pseudopolinomialità. Libro [CGG] Sez.2.7.2, 2.7.3 e 2.7.4
19/04/2012 Laboratorio: Esercizi liste. Ciclo in una lista.Lucidi Esercizi Soluzioni
20/04/2012 Definizione di problemi NP-hard. Riduzione polinomiale da Partizione a Zaino. Algoritmo di programmazione dinamica per Zaino. Introduzione alle strutture con puntatori: liste e alberi. Libro [CGG] Sez. 9.1 e 9.2.4
24/04/2012 Trasformazione da albero ordinato a albero binario. Allocazione in memoria di alberi binari. Alberi binari di ricerca e operazioni del dizionario Libro [CGG] Sez. 4.1 e 4.3 e 4.3.1 Sez 5.1, 5.2, 5.4.1
26/04/2012 Laboratorio: Esercizi alberi binari di ricerca. Orco e hobbit.Lucidi Esercizi Soluzioni
27/04/2012 Alberi binari di ricerca bilanciati in altezza. Alberi AVL, alberi di Fibonacci come caso pessimo. Altezza logaritmica degli AVL. Operazione di inserzione, rotazioni semplice e doppia. Libro [CGG] Sez. 5.4.2 La formula di Binet
02/05/2012 Alberi AVL: cancellazione. Tabelle hash, funzioni hash, organizzazione con liste di trabocco, analisi. Open hash: scansione lineare, agglomerati. Libro [CGG] Sez. 5.3, 5.3.1
03/05/2012 Laboratorio: Esercizi Tabelle Hash. Griglia infetta.Lucidi Esercizi
04/05/2012 Tabelle hash, indirizzamento aperto, scansione lineare: analisi, fenomeno degli agglomerati. Scansione quadratica, Doppio hash. Esempio. Libro [CGG] Sez. 5.3.2
08/05/2012 Esercitazione su alberi binari.
09/05/2012 Grafi: Definizioni e rappresentazione con matrice di adiacenza e liste di adiacenza Libro [CGG] Sez. 6.1.1, 6.1.2
10/05/2012 Laboratorio: Simulazione di una prova di esame.Esercizio
11/05/2012 Grafi: Visita BFS, albero BFS, teorema dei cammini minimi; visita DFS, albero DFS e classificazione degli archi. Libro [CGG] nuova edizione visite.pdf
15/05/2012 Grafi orientati aciclici: Ordinamento Topologico. Il problema del routing. Grafi pesati con pesi positivi: algoritmo di Dijstra per i cammini minimi. Libro [CGG] Sez. 7.5.1, 8.3, 8.3.1
16/05/2012 Algoritmo di Dijstra: esempio completo, dimostrazione di correttezza, analisi con implementazione di coda a Heap. Libro [CGG] Sez. 8.3.2 e 8.2.2
17/05/2012 Richiami sulle tabelle hash. Studio di una legge di scansione quadratica, eliminazione con spostamento nell'open hash a scansione lineare. Esempi di applicazioni delle tecniche di hashing.
18/05/2012 Problema del minimo albero di copertura. Algortimo di Kruskal. Union-Find con liste disgiunte. Libro [CGG] Sez. 8.4.1, 8.4.2 e 3.4.1
22/05/2012 Problema del minimo albero di copertura. Algortimo di Jarnik-Prim, complessità, esempi. Libro [CGG] Sez. 8.4.3
23/05/2012 Esercitazione su grafi
24/05/2012 Esercitazione di riepilogo
informatica/all-a/all11/start.txt · Ultima modifica: 21/02/2013 alle 09:01 (7 anni fa) da anna bernasconi