Strumenti Utente

Strumenti Sito


informatica:all-b:start

Algoritmica e Laboratorio - Corso B

Anno accademico 2018/2019

Informazioni Generali

Docenti Teoria/Esercitazioni: Nadia Pisanti, Anna Bernasconi

Docenti Laboratorio: Anna Bernasconi, Giovanna Rosone, Rossano Venturini

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. 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.

Semestre: secondo.

NEW: Ricevimento Collettivo con i Counselor !!!

A partire dal 13 Marzo, ogni Mercoledi' dalle 11 alle 13 nella Sala Riunioni Est del Dipartimento di Informatica si terra' un ricevimento collettivo delle attivita' di Laboratorio tenuto dai quattro studenti counselor assegnati a questo corso.

Anni accademici precedenti

Gruppi Laboratorio

Gruppo Aula e orario
B1 (da AAA a DE) Aula H, lunedì 9:00 - 11:00
B2 (da DEA a MAN) Aula M, martedì 14:00 - 16:00
B3 (da MAO a ZZZ) Aula H, martedì 14:00 - 16:00

Orario Lezioni

Orario delle Lezioni
Lunedì 9-11 H Laboratorio (gruppo B1)
Martedì 11-13 E Teoria
Martedì 14-16 H, M Laboratorio (gruppi B2 e B3)
Mercoledì 14-16 E Teoria
Giovedì 9-11 E 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 due prove obbligatorie e una facoltativa:

  • Una prova scritta (obbligatoria) 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.
  • Una prova in laboratorio (obbligatoria) 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à.
  • Una prova orale (facoltativa) sul programma del corso, la cui valutazione finale è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.
  • Le prove possono essere sostenute in appelli diversi.
  • La prova di laboratorio puo' essere sostenuta solo dopo aver superato la prova scritta.
  • Se la prova di laboratorio non vine esuperata puo' essere ripetuta senza ripetere lo scritto, ma SE LA PROVA DI LABORATORIO NON VIENE SUPERATA PER DUE VOLTE CONSECUTIVE, OCCORRE RIPETERE ANCHE LO SCRITTO.
  • La prova orale e' facoltativa (salvo eccezioni motivate dal docente), puo' essere sostenuta solo dopo aver superato la prova scritta e la prova di laboratorio, e puo' dar luogo ad un incremento massimo di 4 punti rispetto al voto dello scritto. Se lo studente non intende sostenere la prova orale, ne' il docente ritiene che debba sostenerla, puo' registrare il voto dello scritto incrementato di 2 punti.
  • Se la prova orale non viene superata, occorre ripetere soltanto quella.

Per avere una idea della tipologia delle prove, si consultino i testi degli anni scorsi. Prossime date per la prova scritta:

Data Tipo Prova Documenti Avvisi
01/04/19 Primo Compitino Coloro che devono ancora assolvere gli OFA possono sostenere il compitino come test di autovalutazione, ma l'esito della loro prova non puo' essere considerato valevole come (semi)prova scritta d'esame.
03/06/19 Secondo Compitino

Prossime date per la prova di laboratorio:

Data Ora Aule

Prossime date per le prove orali:

Data Ora Aula Note

Libri di testo

  • [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.
  • [DFI] C. Demetrescu, I. Finocchi, G. Italiano. Algoritmi e strutture dati. McGraw-Hill, Seconda edizione, 2008. Solo pagine 161-166.
  • [CGGR] P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione). Pearson, 2012. Solo pagine 87-96.
  • [BFL] A. Bernasconi, P. Ferragina, F. Luccio. Elementi di Crittografia . Pisa University Press, 2015. Solo il capitolo 3.

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://algo1819.dijkstra.di.unipi.it/

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. Cenni di trattabilità (P, NP, NPC, EXP-TIME).
  12. Generazione di combinazioni e permutazioni
  13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  14. Dizionari: Alberi bilanciati (Alberi 2-3), 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
18/02/2019 19/02/2019 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Slide
19/02/2019 Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.12 monete
20/02/2019 Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: descrizione, pseudocodice, esempio. [CLRS] cap 1, cap 2: 2.1, 2.2.
21/02/2019 Insertion sort: analisi di complessità al caso ottimo e pessimo. Invariante di ciclo e dimostrazione di correttezza. Selection sort: pseudocodice, esempio, e analisi di complessità. [CLRS] cap 2.2.
25/02/2019 26/02/2019 Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Slide
26/02/2019 Esercitazione: Invariante di ciclo di SelectionSort, Ricerca Sequenziale e Binaria, Vettore Unimodulare. Per casa: Problema delle 9 monete, sorting di vettore binario in loco.
27/02/2019 Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. Caso ottimo e caso pessimo con la notazione asintotica. [CLRS] cap 3. TCS cheat sheet
28/02/2019 Paradigma del Divide et Impera: descrizione del paradigma, alberi di ricorsione, dimostrazione di correttezza mediante induzione. Esempi (min-max e potenza ennesima). MergeSort: cenno. [CLRS] cap 2: 2.3, cap 4: introduzione.
04/03/2019 05/03/2019 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Slide
05/03/2019 MergeSort: algoritmo, correttezza, analisi di complessità (metodo iterativo e albero di ricorsione). Esempio. [CLRS] cap 2: 2.3, cap 4: 4.3 e 4.4.
06/03/2019 Esercitazione: soluzione esercizi dati per casa. Mergeinsort. Altri esercizi su vettori.
07/03/2019 Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Limite inferiore per l'ordinamento per confronti. [CLRS] cap 8: 8.1. Note di F. Luccio su limiti inferiori.
11/03/2019 12/03/2019 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Slide
12/03/2019 Enunciato del Teorema dell'esperto, con esempi. Dimostrazione del Teorema dell'esperto per il caso delle potenze esatte. [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte)
13/03/2019 Relazioni di ricorrenza di ordine k. Esercizitazione sul Teorema dell'esperto: algoritmo della Moltiplicazione veloce con analisi della complessità. (Studiare anche prodotto veloce tra matrici.) Ricorrenze (dispensa Prof.Luccio: leggere introduzione, sezioni 1 e 3, saltando la sezione 2). moltiplicazione interi e matrici (note Prof.Luccio).
16/03/2019 Quicksort: descrizione intuitiva, pseudo-codice, correttezza e complessita' di Partition. Correttezza di Quicksort. Esempi. [CLRS] cap 7
18/03/2019 19/03/2019 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Slide
19/03/2019 Quicksort: analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Versione randomizzata, e analisi della complessità. [CLRS] cap 7
20/03/2019 La struttura dati Heap: definizione, realizzazione implicita come array, proprieta', costruzione (BuildHeap) con Max-Heapify. Analisi della complessità e correttezza di MaxHeapify. [CLRS] cap 6: 6.1, 6.2, 6.3.
21/03/2019 Analisi della complessità e correttezza di BuildHeap. L'algoritmo Heapsort. Esercizi sull'Heap. Code di priorità, operazioni, definizione e realizzazione mediante heap. [CLRS] cap 6: 6.3, 6.4., 6.5
25/03/2019 26/03/2019 Laboratorio: Qsort e ripasso delle struct.Slide
26/03/2019 Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. [CLRS] cap 8: 8.2, 8.3.
27/03/2019 Esercitazione
28/03/2019 Esercitazione
01/04/2019 PRIMA VERIFICA INTERMEDIA
informatica/all-b/start.txt · Ultima modifica: 24/03/2019 alle 20:16 (24 ore fa) da anna bernasconi