Strumenti Utente

Strumenti Sito


informatica:all-b:algob_14:start

Algoritmica e Laboratorio - Corso B

Anno accademico 2013/2014

Informazioni Generali

Docenti: Anna Bernasconi, Rossano Venturini

(Docenti corso A: Linda Pagli, Rossano Venturini)

Assistente: Roberto Santoro

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ì 11-13 A Teoria
Mercoledì 11-13 A Teoria
Giovedì 14-16 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. 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
02/04/2014, ore 11.00 Scritto (primo compitino)algo1_020414.pdf
28/05/2014, ore 11.00 Scritto (secondo compitino)algo1_28052014.pdf
09/06/2014, ore 11.00 Scritto algo1_090614.pdf
08/07/2014, ore 9:30 Scritto algo1_08072014.pdf, Soluzioni
08/09/2014, ore 9.30 Scritto algo1_08092014.pdf, Soluzioni
04/11/2014, ore 9.00 Scritto algo1_04112014.pdf
14/01/2015, ore 9.00 Scritto algo1_14012015.pdf,algo140115sol.pdf
12/02/2015, ore 9.00 Scritto algo1_12020215.pdf Risultati. Visione scritti: lunedì 16 febbraio, ore 12-13 ufficio Bernasconi. Orali: 18 febbraio, ore 10, ufficio Bernasconi (oppure su appuntamento).

Prossime date per le prove di laboratorio:

Data Ora Aule Documento
13/06/2014 9:00 H, I, M Testo 1 Testo 2 Test1 Test2
27/06/2014 9:00 H, I, M Testo Test
16/07/2014 9:00 H, I, M Testo Test
15/09/2014 9:00 H, I, M Testo e test
06/11/2014 9:00 I, M Testo e test
16/01/2015 9:00 H, I, M Testo e test
17/02/2015 9:00 H, I, M

Prossime date per le prove orali:

Data Ora Aula
03/06/2014 9:15 aula A1
16/06/2014 9:15 aula B
30/06/2014 9:15 ufficio Bernasconi
10/07/2014 9:30 ufficio Bernasconi
16/07/2014 11:00, 14:00 ufficio Bernasconi
24/07/2014 14:00 ufficio Bernasconi
16/09/2014 9:30 ufficio Bernasconi
20/01/2015 10:00 ufficio Bernasconi
18/02/2015 10:00 ufficio Bernasconi

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 il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.
  • Sistema di Autovalutazione: http://vinello.isti.cnr.it:8888

Programma del corso

  1. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  2. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
  3. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  4. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  5. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  6. Ordinamento di interi: Counting sort, Radix Sort.
  7. Ordinamento di stringhe: qsort-based.
  8. Sottosequenza di somma massima.
  9. Programmazione dinamica: LCS, Partizione e Zaino
  10. Algoritmi randomizzati: Quicksort.
  11. Generazione di combinazioni e permutazioni
  12. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  13. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  14. Alberi: rappresentazione e visite.
  15. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  16. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  17. Grafi III: Minimum Spanning Tree e Shortest Path.
  18. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).

Registro delle Lezioni

Data Argomento Rif. Biblio
18/02/2014 Introduzione al corso: intervento del Prof. Roberto Grossi.
19/02/2014 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi Istruzioni per testing
20/02/2014 Laboratorio: Funzioni e puntatori. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
21/02/2014 Nozioni di Algoritmo, Problema, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete. 12 monete
25/02/2014 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; Formule utili
26/02/2014 Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
27/02/2014 Laboratorio: Allocazione dinamica della memoria. Lucidi
28/02/2014 Array di dimensione variabile. Selection Sort e Insertion Sort: proprietà e complessità al caso ottimo, medio e pessimo. [CGGR]: cap. 1.
04/03/2014 Algoritmi di ordinamento stabili. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo.limiti inferiori
05/03/2014 Limite inferiore per l'ordinamento per confronti. Il problema della ricerca: ricerca binaria ricorsiva: analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort. [CGGR]: pag 56, cap 3.
06/03/2014 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Lucidi
07/03/2014 Esercitazione: progettazione di algoritmi e analisi di complessità.
11/03/2014 Relazioni di ricorrenza: Teorema principale (con dimostrazione) ed esempi di applicazione. Ricorrenze (dispensa Prof. Luccio).
12/03/2014 Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi al caso medio. [CGGR]: cap 3 e cap 5.
13/03/2014 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Lucidi
14/03/2014 Selezione dell'elemento di rango r in un array (QuickSelect). Moltiplicazione veloce di interi e matrici.[CGGR]: cap 3 e cap 5.
18/03/2014 Esercitazione: progettazione di algoritmi e analisi di complessità. Esercizi
19/03/2014 Code con priorità: definizione, operazioni Empty, Enqueue, Dequeue, First. Heap di massimo: definizione, proprietà e rappresentazione in memoria (allocazione implicita in un array). [CGGR]: cap 2.
20/03/2014 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Puzzle: La scala e Corsa di cavalli Lucidi QuickSortParziale Partizionamento
24/03/2014 Heap di massimo: implementazione delle operazioni Enqueue, First, Dequeue. HeapSort: definizione e analisi. [CGGR]: cap 2.
25/03/2014 Ordinamento di interi: Counting sort e Radix Sort. [CLR] cap. 8
26/03/2014 Esercitazione: progettazione di algoritmi e analisi di complessità.
27/03/2014 Laboratorio: Qsort e ripasso delle structLucidi
28/03/2014 Esercitazione: progettazione di algoritmi e analisi di complessità (heap, numeri di Fibonacci).
02/04/2014 Prima prova di verifica intermedia.
08/04/2014 Algoritmi per il calcolo dei numeri di Fibonacci. Correzione della prima prova di verifica intermedia.
09/04/2014 Introduzione alla Programmazione Dinamica. Distanza tra due stringhe (Edit Distance). Programmazione dinamica (dispensa Prof. Luccio) ; [CGGR]: cap 6.
10/04/2014 Laboratorio: Esercizi d'esame: qsort e structLucidi
11/04/2014 Programmazione Dinamica: Longest Common Subsequence, Partizione di un insieme di interi. [CGGR]: cap 6.
15/04/2014 Algoritmi pseudopolinomiali. Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. [CGGR]: cap 6. Esercizi
16/04/2014 Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi cardinali. Alberi ordinali: memorizzazione binarizzata. [CGGR]: cap 1, cap 3.
17/04/2014 Laboratorio: Liste Lucidi
30/04/2014 Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione. [CGGR]: cap 4.
02/05/2014 Alberi binari 1-bilanciati: alberi di Fibonacci; dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni). [CGGR]: cap 4; lucidi.
06/05/2014 Alberi AVL: esempio di inserimento con rotazioni, cancellazione: cenni. Introduzione alle tabelle hash. [CGGR]: cap 4.
07/05/2014 Dizionari: realizzazione con tabelle hash (con liste di trabocco e a indirizzamento aperto). [CGGR]: cap 4.
07/05/2014 Esercitazione: progettazione di algoritmi di programmazione dinamica per problemi su scacchiera.EserciziPD: soluzioni
08/05/2014 Laboratorio: Alberi Lucidi
09/05/2014 Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL.EserciziAB
13/05/2013 Grafi: definizioni, rappresentazione di grafi in memoria. [CGGR]: cap 7.
14/05/2013 Grafi: visita in ampiezza e in profondità; classificazione degli archi. [CGGR]: cap 7.
14/05/2013 Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). Esercizi, soluzioni.
15/05/2014 Laboratorio: Tabelle Hash Lucidi
16/05/2014 Ordinamento topologico di un grafo diretto aciclico (DAG): algoritmo e analisi. [CGGR]: cap 7.
20/05/2014 Problemi indecidibili: il problema della fermata. Problemi intrattabili: le torri di Hanoi (algoritmo, analisi del numero di mosse); generazione delle stringhe binarie. [CGGR] prologo.
21/05/2014 Generazione di tutte le permutazioni. Le classi di complessità P e EXP. Il certificato polinomiale e la classe NP. Nozione di Riduzione Polinomiale. Problemi NP-completi. Esempio di riduzione: SAT - Clique. [CGGR] prologo, cap 8; Lucidi.
21/05/2014 Esercitazione: progettazione di algoritmi efficienti su grafi. Esercizi e soluzioni
22/05/2014 Laboratorio: Simulazione prova d'esame
27/05/2014 Esercitazione: certificati polinomiali e algoritmi di verifica.
28/05/2014 Seconda prova di verifica intermedia.
informatica/all-b/algob_14/start.txt · Ultima modifica: 08/05/2015 alle 13:32 (5 anni fa) da anna bernasconi