Strumenti Utente

Strumenti Sito


informatica:all-b:algob_15:start

Algoritmica e Laboratorio - Corso B

Anno accademico 2014/2015

Informazioni Generali

Docenti: Anna Bernasconi, Rossano Venturini, Nadia Pisanti, Andrea Farruggia

(Docenti corso A: Linda Pagli, Rossano Venturini, Giovanna Rosone, Andrea Farruggia)

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 B Teoria
Mercoledì 11-13 B Teoria
Giovedì 14-16 H,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
14/04/2015, ore 11.00 Scritto (primo compitino)algo1_140415.pdf lista dei risultati.
29/05/2015, ore 9.00 Scritto (secondo compitino)testo e soluzioni lista dei risultati. Visione scritti: martedì 3 giugno, dalle 14:30 alle 15:30, ufficio Bernasconi.
12/06/2015, ore 9:30 Scritto testo e soluzioni lista dei risultati. Visione scritti: lunedì 15 giugno, dalle 14:30 alle 15:30, ufficio Bernasconi.
03/07/2015, ore 9:30 Scritto testo e soluzioni lista dei risultati. Visione scritti: lunedì 6 luglio, dalle 11:00 alle 12:00, ufficio Bernasconi.
10/09/2015, ore 14:30 Scritto testo e soluzioni lista dei risultati. Visione scritti: lunedì 14 settembre, dalle 10:00 alle 11:00, ufficio Bernasconi. Orali: mercoledì 16 settembre, ore 9:15, ufficio Bernasconi
11/01/2016, ore 9:00 Scritto testo e soluzioni lista dei risultati. Visione scritti: mercoledì 13 gennaio, dalle 11:00 alle 12:00, ufficio Bernasconi. Orali: martedì 19 gennaio, ore 9:00, ufficio Bernasconi, oppure su appuntamento
01/02/2016, ore 9:00 Scritto testo e soluzionilista dei risultati. Visione scritti: giovedì 4 febbraio, dalle 9:00 alle 10:00, ufficio Bernasconi. Orali: giovedì 4 febbraio, ore 10:00, ufficio Bernasconi, oppure su appuntamento

Prossime date per le prove di laboratorio:

Data Ora Aule Documento
04/06/2015 9:00 H-M-I Testo TestSet
22/06/2015 9:00 H-M-I Testo
09/07/2015 9:00 H-M-I
15/09/2015 9:00 H-M-I
06/11/2015 10:00 M Appello straordinario
13/01/2016 9:00 H-M-I
03/02/2016 9:00 H-M-I

Prossime date per le prove orali:

Data Ora Aula
venerdì 5/06/2015 9:30 aula A1
mercoledì 10/06/2015 9:30 ufficio Bernasconi
martedì 16/06/2015 9:30 ufficio Bernasconi
martedì 23/06/2015 9:30 ufficio Bernasconi
lunedì 29/06/2015 9:30 ufficio Bernasconi
venerdì 10/07/2015 9:30 ufficio Bernasconi
giovedì 23/07/2015 15:00 ufficio Bernasconi
mercoledì 16/09/2015 9:15 ufficio Bernasconi
martedì 19/06/2015 9:00 ufficio Bernasconi
martedì 4/02/2016 10:00 ufficio Bernasconi

Libri di testo

  • [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 consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. 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:10000

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
24/02/2015 Nozioni di Problema, Algoritmo, Limite Inferiore. Analisi di un problema semiserio: il problema delle 12 monete. Moltiplicazione Egizia.12 monete
25/02/2015 Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: correttezza e analisi di complessità al caso ottimo, medio e pessimo. [CLRS] cap 1, cap 2: 2.1, 2.2.
26/02/2015 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Funzioni e puntatori. Cap. 2-3, Sez. 4.1-4.5, 5.1-5.5 e 7.1-7.4 di [KR]. Lucidi
27/02/2015 Selection sort: correttezza e analisi di complessità. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. [CLRS] cap 3.
3/03/2015 Paradigma del Divide et Impera. MergeSort: algoritmo, correttezza e analisi di complessità. [CLRS] cap 2: 2.3.
4/03/2015 Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero di decisione. Esempi: algoritmo del torneo e del doppio torneo, albero di decisione per l'insertion sort su tre elementi. [CLRS] cap 8: 8.1. limiti inferiori Il problema del torneo
5/03/2015 Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi
6/03/2015 Limite inferiore per l'ordinamento per confronti. Il problema della ricerca: ricerca sequenziale e ricerca binaria. [CLRS] cap 8: 8.1.
10/03/2015 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (divide et impera, ricerca, ordinamento)
11/03/2015 Relazioni di ricorrenza: metodo dell'albero di ricorsione, metodo dell'esperto (Teorema principale) con esempi di applicazione. [CLRS] cap 4: 4.4, 4.5.
12/03/2015 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Lucidi
13/03/2015 Dimostrazione del teorema principale (solo per potenze esatte). Moltiplicazione veloce di interi e matrici. [CLRS] cap 4: 4.2, 4.6.1. Moltiplicazione veloce di interi (Prof. Grossi)
17/03/2015 Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato. [CLRS] cap 7: 7.1, 7.2, 7.3.
18/03/2015 Quicksort randomizzato: analisi della complessità nel caso medio. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo atteso lineare. [CLRS] cap 7: 7.4.2, cap 9: 9.1, 9.2 (senza analisi nel caso medio). Numero di confronti di Randomized-Quicksort (Prof. Luccio)
19/03/2015 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Lucidi
20/03/2015 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (divide et impera, ricorrenze, ordinamento)
24/03/2015 Heap: definizione, realizzazione implicita come array, proprietà, conservazione della proprietà di heap, costruzione. [CLRS] cap 6: 6.1, 6.2, 6.3.
25/03/2015 Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. L'algoritmo Heapsort. Code di priorità: definizione, operazioni, realizzazione mediante heap. [CLRS] cap 6: 6.3, 6.4, 6.5.
26/03/2015 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Lucidi QuickSortParziale Partizionamento
27/03/2015 Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort.[CLRS] cap 8: 8.2, 8.3.
31/03/2015 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (heap)
1/04/2015 Esercitazione: progettazione di algoritmi e analisi di complessità.
2/04/2015 Laboratorio: Qsort e ripasso delle struct.Lucidi
14/04/2015 Prima prova di verifica intermedia. lista dei risultati
15/04/2015 Correzione della prima prova di verifica intermedia. Alberi binari: visite, algoritmi ricorsivi su alberi binari. [CLRS] cap 10: 10.4. [CGGR]: Algoritmi ricorsivi su alberi binari
16/04/2015 Laboratorio: Esercizi d'esame: qsort e struct.Lucidi
17/04/2015 Alberi: memorizzazione binarizzata. Dizionari: realizzazione con alberi binari di ricerca (ricerca, minimo, massimo, successore). [CLRS] cap 10: 10.4, cap 12: 12.1, 12.2.
21/04/2015 Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). [CLRS] cap 12: 12.3.
22/04/2015 Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni). [CGGR]: Alberi AVL, rotazioni.
23/04/2015 Laboratorio: Liste. Lucidi
24/04/2015 Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL.EserciziAB
28/04/2015 Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio).[CLRS] cap 11: 11.2, 11.2, 11.3, 11.3.1.
29/04/2015 Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. [CLRS] cap 11: 11.4. Dispense Prof. Luccio
30/04/2015 Laboratorio: Alberi. Lucidi
5/05/2015 Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva. [CLRS] cap 15: 15.4.
6/05/2015 LCS: ricostruzione della soluzione, algoritmi LCS-LENGTH e PRINT-LCS. Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione. [CLRS] cap 15: 15.4. Edit Distance (dispense Prof. Luccio).
7/05/2015 Laboratorio: Tabelle Hash. Lucidi
8/05/2015 Edit Distance: algoritmi ED e ALLINEA. Apparizioni approssimate di una sequenza in un testo (cenni). Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). Esercizi su dizionari e alberi Soluzioni
12/05/2015 Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmi pseudopolinomiali. Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello zaino. [CLRS] cap 16: 16.2, esercizio 16.2.2 (algoritmo PD per lo Zaino). [CGGR]: generazione delle sequenze binarie, pseudopolinomialità.
13/05/2015 Grafi: definizioni, rappresentazione di grafi in memoria, visita in ampiezza (BFS). [CLRS]: appendice B.4, cap 22: 22.1, 22.2.
14/05/2015 Laboratorio: Simulazione della prova di laboratorio.
15/05/2015 Visita in ampiezza di un grafo: algoritmo BFS e analisi di complessità, albero di visita in ampiezza e algoritmo PRINT-PATH, esplorazione di un grafo con insieme di vertici non noto. Implementazione di una coda su array. Esercitazione: esercizi sulla Programmazione Dinamica. [CLRS] cap 22: 22.2 (senza dimostrazioni), cap 10: 10.1. Esercizi sulla Programmazione Dinamica Soluzioni
19/05/2015 Grafi: visita in profondità (DFS); classificazione degli archi; ordinamento topologico di grafi diretti aciclici. [CLRS] cap 22: 22.3, 22.4.
20/05/2015 Esercitazione: progettazione di algoritmi efficienti su grafi.Esercizi
21/05/2015 Laboratorio: Soluzione della prova di laboratorio della scorsa settimana. soluzione
22/05/2015 Introduzione alla computabilità, problemi indecidibili. Il problema dell'arresto. Le classi di complessità P e NP: introduzione.Lucidi
26/05/2015 Teoria della complessità: classe P; nozione di certificato polinomiale e classe NP; nozione di riduzione polinomiale; problemi NP-completi. Esempi: problema del ciclo euleriano; generazione di tutte le permutazioni e problema del ciclo hamiltoniano; riduzione SAT - Clique. [CLRS] cap 34: 34.1. Lucidi Generazione delle permutazioni e problema del ciclo hamiltoniano.
29/05/2015 Seconda prova di verifica intermedia.
informatica/all-b/algob_15/start.txt · Ultima modifica: 09/02/2016 alle 14:09 (3 anni fa) da anna bernasconi