Strumenti Utente

Strumenti Sito


informatica:all-b:algob_13:start

Algoritmica e Laboratorio - Corso B

Anno accademico 2012/2013

Informazioni Generali

Docenti: Anna Bernasconi, Rossano Venturini

(Docenti corso A: Linda Pagli, Giuseppe Prencipe)

Assistente: Diego Ceccarelli

Impegno: 12 CFU.

Codice: 008AA

Periodo: primo anno, secondo semestre.

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

Anni accademici precedenti

Orario Lezioni

Orario delle Lezioni
Martedì 9-11 B Teoria
Mercoledì 11-13 B Teoria
Giovedì 16-18 M Laboratorio
Venerdì 11-13 B 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. Possono sostenere la prova di laboratorio solo gli studenti che hanno superato la prova scritta.
  • 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
03/04/2013, ore 11.00 Scritto (primo compitino)algo1_030413.pdf
30/05/2013, ore 9.00 Scritto (secondo compitino)algo1_300513sol.pdf
12/06/2013, ore 9.00 Scritto algo1_120613.pdf, soluzioni
12/07/2013, ore 9.00 Scritto algo1_120713.pdf
9/09/2013, ore 15.00 Scritto algo1_090913.pdf
4/11/2013, ore 14.00 Scritto algo1_041113.pdf
21/01/2014, ore 9.30 Scritto Testo e soluzioni
7/02/2014, ore 9.30 Scritto Testo

Prossime date per le prove di laboratorio:

Data Ora Aule Documento
11/06/2013 9:30 H e M Testo TestSet
14/06/2013 9:30 H e M Testo TestSet
16/07/2013 9:30 H e M Testo TestSet
12/09/2013 9:30 H e M Testo
08/11/2013 10:30 H e M Testo
24/01/2014 9:30 H e M Testo
11/02/2014 9:30 H e M

Prossime date per le prove orali:

Data Ora Aula
14/06/2013 9:30 aula B
19/06/2013 9:00 aula A1
27/06/2013 9:30 nel mio studio
17/07/2013 9:00 aula C1
13/09/2013 9:30 aula C
17/09/2013 9:30 aula L1
27/01/2014 9:30 nel mio studio
13/02/2014 9:30 nel mio studio

Libri 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/home
  • [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.

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.

Lavagna

Registro delle Lezioni

Data Argomento Rif. Biblio
19/02/2013 Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio. appunti
20/02/2013 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi Sito Esercitazioni
21/02/2013 Laboratorio: Ripasso e esercizi su funzioni e puntatori. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
22/02/2013 Problemi indecidibili, il problema della fermata. Problemi intrattabili: le torri di Hanoi, algoritmo, analisi del numero di mosse. Crescita esponenziale. Lucidi; [CGGR] prologo; [CGG] cap. 1
27/02/2013 Laboratorio: Funzioni e passaggio dei parametri. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
28/02/2013 Laboratorio: Allocazione dinamica della memoria (malloc) e stringhe. Lucidi
01/03/2013 Il metodo algoritmico (intervento di Pilu Crescenzi). Generalizzazione del problema delle Torri di Hanoi e crescita polinomiale. Algoritmi polinomiali. Le classi di problemi P ed EXP. [CGGR] prologo; [CGG] cap. 1
05/03/2013 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. Il Sudoku. La classe NP. [CGGR]: prologo; pag 185 e 211 (solo definizione di Partition e Hamiltonian Cycle) [CGG]: cap. 1; pag 75 e 207 (solo definizione di Partition e Hamiltonian Cycle)
06/03/2013 Il certificato polinomiale e la classe NP. Nozione di Riduzione Polinomiale. Problemi NP-completi. Il Problema SAT. Esempio di riduzione: SAT - Clique. [CGGR]: prologo; [CGG]: cap. 1; Lucidi
07/03/2013 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. File di test per intersezione File di test per sottoarray di somma massima
08/03/2013 Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo e caso medio. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. Notazione asintotica (dispensa Prof. Luccio); [CGGR]: introduzione; [CGG]: cap. 1; Esercizi; Formule utili
12/03/2013 Array di dimensione variabile. Selection Sort e Insertion Sort: proprietà e complessità al caso ottimo, medio e pessimo. [CGGR]: cap. 1; [CGG]: cap. 2; lavagna.
13/03/2013 Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo, ordinamento per confronti, ricerca.limiti inferiori; [CGGR]: pag. 56; [CGG]: pag 46; lavagna
14/03/2013 Laboratorio: Sottoarray di somma massima lineare, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Lucidi sottoarray somma massima Lucidi Array Stringhe Puzzle: L'intero mancante
15/03/2013 Soluzione degli esercizi proposti: generazione di tutti i sottoinsiemi di k elementi. Algoritmo di soluzione e verifica della k-clique. Algoritmo per il problema della Subset-Sum. Soluzioni
19/03/2013 Il problema della ricerca: ricerca binaria ricorsiva; Analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort. [CGGR]: cap 3; [CGG]: cap. 2; lavagna
20/03/2013 Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi al caso medio. [CGGR]: cap 3 e cap 5; [CGG]: cap. 2; lavagna
21/03/2013 Laboratorio: Quick Sort su interi e su stringhe. Varianti (pari&dispari, 3-way partition). Quicksort parziale Pseudocodice Distribuzione Puzzle: la scala e cavalli
22/03/2013 Relazioni di ricorrenza: Teorema principale (con dimostrazione) ed esempi di applicazione. ricorrenze.pdf; lavagna; Esercizi
26/03/2013 Moltiplicazione veloce di interi e matrici. Esercitazione: progettazione di algoritmi e analisi di complessità.[CGGR]: cap 3; [CGG]: cap. 2; lavagna
27/03/2013 Selezione dell'elemento di rango r in un array (QuickSelect). Esercitazione: progettazione di algoritmi e analisi di complessità.[CGGR]: cap 3 e cap 5; [CGG]: cap. 2; lavagna
28/03/2013 Laboratorio: Qsort e ripasso delle structLucidi qsort Lucidi struct Puzzle: Pirellone
3/04/2013 Prima prova di verifica intermedia.
9/04/2013 Correzione della prima prova di verifica intermedia. Code con priorità, Heap come albero binario completo a sinistra, relazione tra numero di nodi e altezza. [CGGR]: cap 2 ; [CGG]: cap. 8; lavagna
10/04/2013 Operazioni Enqueue, First, Dequeue per un Heap di massimo. Complessità. Allocazione implicita in array. HeapSort. [CGGR]: cap 2 ; [CGG]: cap. 8; lavagna
11/04/2013 Laboratorio: Esercizi d'esame: qsort e structPuzzle: Elemento maggioritario
12/04/2013 Ordinamento di interi: Counting sort e Radix Sort. Introduzione alla Programmazione Dinamica.[CLR] cap. 8; Programmazione dinamica (dispensa Prof. Luccio) ; [CGGR]: cap 6; [CGG]: cap 2; lavagna
16/04/2013 Programmazione Dinamica: Edit Distance, Longest Common Subsequence (introduzione al problema).Programmazione dinamica (dispensa Prof. Luccio); [CGGR]: cap 6; [CGG]: cap 2; lavagna
17/04/2013 Programmazione Dinamica: Longest Common Subsequence, Partizione di un insieme di interi. [CGGR]: cap 6; [CGG]: cap 2; lavagna
18/04/2013 Laboratorio: Liste Lucidi Puzzle: Ciclo in una lista
19/04/2013 Programmazione Dinamica: Il problema dello Zaino. Pseudopolinomialità. Esercizi sulla programmazione dinamica. [CGGR]: cap 6; [CGG]: cap 2; lavagna, Esercizi
23/04/2013 Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi cardinali. Alberi ordinali: memorizzazione binarizzata. Dizionari. [CGGR]: cap 1, cap 3, cap 4; [CGG]: cap 4, cap 5; lavagna
24/04/2013 Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione, alberi di Fibonacci. [CGGR]: cap 4; [CGG]: cap 5; lavagna
26/04/2013 Esercitazione: operazione DecreaseKey in un heap; simulazione di un algoritmo di programmazione dinamica per il problema dello Zaino. Progettazione di algoritmi di programmazione dinamica per problemi su scacchiera. ese26-4-2012.pdf
30/04/2013 Alberi binari 1-bilanciati: dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni). [CGGR]: cap 4; [CGG]: cap 5; lavagna
02/05/2013 Laboratorio: Alberi Lucidi Puzzle: Orco e Hobbit
03/05/2013 Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL. Esercizi Alcune soluzioni
07/05/2013 Dizionari: funzioni hash, realizzazione del dizionario con tabelle hash con liste di trabocco e a indirizzamento aperto. [CGGR]: cap 4; [CGG]: cap 5; lavagna
08/05/2013 Tabelle hash a indirizzamento aperto: analisi al caso medio; scansione lineare, quadratica, doppio hash. [CGGR]: cap 4; [CGG]: cap 5; tabelle hash (dispensa Prof. Luccio); lavagna
09/05/2013 Laboratorio: Tabelle Hash Lucidi Puzzle: Griglia infetta
10/05/2013 Grafi: definizioni, rappresentazione di grafi in memoria; visita in ampiezza. [CGGR]: cap 7; [CGG]: cap 6; lavagna
14/05/2013 Visita in ampiezza di un grafo: analisi e proprietà. Visita in profondità. Ordinamento topologico di un grafo diretto aciclico. [CGGR]: cap 7; [CGG]: cap 6; lavagna
15/05/2013 Ordinamento topologico di un DAG: algoritmo e analisi. Ricerca di cammini minimi su grafi pesati: algoritmo di Dijkstra. [CGGR]: cap 7; [CGG]: cap 6,8; lavagna
16/05/2013 Laboratorio: Simulazione della prova di laboratorioTesto Input Codice sottoposto
17/05/2013 Algoritmo di Dijkstra: simulazione, correttezza e analisi. [CGGR]: cap 7; [CGG]: cap 8; lavagna
21/05/2013 Liste per insiemi disgiunti (Union-Find). Problema della ricerca del minimo albero di copertura: Algoritmo di Kruskal. [CGGR]: cap 5, 7; [CGG]: cap 3, 8; lucidi; lavagna
22/05/2013 Esercitazione: progettazione di algoritmi efficienti su grafi. lavagna
23/05/2013 Laboratorio: Lezione facoltativa su comandi da terminale in aula H dalle 14:00 alle 16:00
24/05/2013 Esercitazione di riepilogo. lavagna
30/05/2013 Seconda prova di verifica intermedia.
informatica/all-b/algob_13/start.txt · Ultima modifica: 08/05/2015 alle 13:29 (4 anni fa) da anna bernasconi