Strumenti Utente

Strumenti Sito


informatica:all-b:algob_17:start

Algoritmica e Laboratorio - Corso B

Anno accademico 2016/2017

Informazioni Generali

Docenti Teoria/Esercitazioni: Anna Bernasconi (corso B) e Paolo Ferragina (corso A)

Docenti Laboratorio: Andrea Marino, 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.

Ricevimento studenti: mercoledì, 11-13, ufficio BERNASCONI (per ricevimento in orari diversi da quanto previsto inviare e-mail a anna.bernasconi@unipi.it), fino a mercoledì 14 giugno. Dal 19 giugno il ricevimento sarà SOLO SU APPUNTAMENTO.

Anni accademici precedenti

Orario Lezioni

Orario delle Lezioni
Lunedì 9-11 A Teoria
Martedì 16-18 H, I, M Laboratorio
Mercoledì 14-16 A Teoria
Giovedì 9-11 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.
  • 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à.
  • 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.
  • LA PROVA ORALE E QUELLA DI LABORATORIO POSSONO ESSERE SOSTENUTE IN QUALUNQUE ORDINE E SOLO DOPO AVER SUPERATO LA PROVA SCRITTA.
  • Se la prova orale non viene superata, occorre ripetere soltanto quella.
  • SE LA PROVA DI LABORATORIO NON VIENE SUPERATA PER DUE VOLTE CONSECUTIVE, OCCORRE RIPETERE TUTTE LE PROVE GIA' SOSTENUTE.
  • Chiaramente la registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo.

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

Prossime date per la prova scritta:

Data Tipo Prova Documento Note
11/04/2017 Primo compitino testo lista dei risultati.
Correzione e visione scritti: venerdì 21 aprile, ore 14, aula A.
11/04/2017 Appello Straordinario testo lista dei risultati
Contattare la Prof.ssa Linda Pagli per visione scritti e prove orali.
01/06/2017,
ore 08.30
Secondo compitino testo e soluzione lista dei risultati.
Visione compitino: martedì 6 giugno, ore 9:00, aula C
12/06/2017,
ore 09.30
Primo appello testo e soluzione lista dei risultati.
Visione scritto: giovedì 15 giugno, ore 9:00, aula F1
3/07/2017,
ore 09.30
Secondo appello testo e soluzione lista dei risultati.
Visione scritto: mercoledì 5 luglio, ore 9:00, ufficio BERNASCONI
5/09/2017,
ore 09.00
Terzo appello testo e Soluzione lista dei risultati.
Visione scritto: giovedì 7 settembre, ore 9:30, ufficio BERNASCONI
Orali: giovedì 7 settembre e lunedì 11 settembre, ore 10:00, ufficio BERNASCONI, obbligatorio iscriversi (via email)
31/10/2017,
ore 09.00
Appello straordinario testo Visione del compito e orali: su appuntamento, a partire da lunedì 6 novembre.
Risultati:
516639: 18
520333: 18
557687: 21
19/01/2018,
ore 09.00
Quarto appello testo Visione del compito e orali: martedì 23 gennaio, ore 10, ufficio BERNASCONI (oppure su appuntamento).
Risultati:
519061: 18
531391: 18
550743: 24
561515: ins
05/02/2018,
ore 09.00
Quinto appello testo Visione del compito e orali: mercoledì 7 febbraio, ore 10, ufficio BERNASCONI (oppure su appuntamento).
Risultati:
519061: 21
544935: 21
545289: 19

Prossime date per la prova di laboratorio:

Data Ora Aule
07/06/2017 ore 9.00 Aule H,I,M
16/06/2017 ore 9.00 Aule H,I,M
07/07/2017 ore 9.00 Aule H,I,M
08/09/2017 ore 9.00 Aule H,I,M

Prossime date per le prove orali:

Data Ora Aula Note
06/06/2017 dalle ore 9:30 aula C obbligatorio iscriversi (via email)
07/06/2017 dalle ore 11:30 ufficio BERNASCONI obbligatorio iscriversi (via email)
08/06/2017 dalle ore 8:30 aula C1 obbligatorio iscriversi (via email)
15/06/2017 dalle ore 9:00 ufficio BERNASCONI obbligatorio iscriversi (via email)
26/06/2017 dalle ore 9:00 ufficio BERNASCONI obbligatorio iscriversi (via email)
5/07/2017 dalle ore 9:30 ufficio BERNASCONI obbligatorio iscriversi (via email)
24/07/2017 dalle ore 9:30 ufficio BERNASCONI obbligatorio iscriversi (via email)
7/09/2017 dalle ore 10:00 ufficio BERNASCONI obbligatorio iscriversi (via email)
11/09/2017 dalle ore 10:00 ufficio BERNASCONI obbligatorio iscriversi (via email)

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

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 (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
20/02/2017 Presentazione del corso. Moltiplicazione Egizia: algoritmo e analisi. Analisi di un problema semiserio: il problema delle 12 monete.12 monete
21/02/2017 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Slide
22/02/2017 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à (tempo e numero di confronti) al caso ottimo, medio e pessimo. Selection sort: analisi di complessità (numero di confronti). [CLRS] cap 1, cap 2: 2.1, 2.2.
23/02/2017 Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. [CLRS] cap 3. TCS cheat sheet Esercizi
27/02/2017 Paradigma del Divide et Impera. MergeSort: algoritmo, correttezza e analisi di complessità (metodo iterativo e albero di ricorsione). [CLRS] cap 2: 2.3, cap 4: introduzione, 4.4.
28/02/2017 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
1/03/2017 Ricerca binaria. Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. [CLRS] cap 8: 8.1. Note di F. Luccio su limiti inferiori.
2/03/2017 Limite inferiore per l'ordinamento per confronti. Relazioni di ricorrenza: Teorema dell'esperto (Teorema principale) con esempi di applicazione. Dimostrazione del teorema (solo per potenze esatte). [CLRS] cap 8: 8.1, cap 4: 4.5, 4.6.1.
6/03/2017 Moltiplicazione veloce di interi di n cifre. Esercitazione: applicazione del Teorema dell'esperto e analisi di complessità.Note di F. Luccio e di R. Grossi sulla moltiplicazione veloce di interi e matrici.
7/03/2017 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Slide
8/03/2017 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (ricorrenze, ricerca, ordinamento, divide et impera)
9/03/2017 Quicksort: proprietà, pseudocodice e analisi della complessità nel caso ottimo e pessimo. Discussione sul costo nel caso medio: analisi delle prestazioni per ripartizioni di proporzionalità costante. Quicksort randomizzato: discussione e pseudocodice. [CLRS] cap 7: 7.1, 7.2, 7.3
13/03/2017 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 (Note di F.Luccio)
14/03/2017 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Slide
15/03/2017 Heap: definizione, realizzazione implicita come array, proprietà, conservazione della proprietà di heap: procedura Max-Heapify. Costruzione di un heap in tempo lineare: algoritmo Build-Max-Heap. [CLRS] cap 6: 6.1, 6.2, 6.3.
16/03/2017 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.
20/03/2017 Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort.[CLRS] cap 8: 8.2, 8.3.
21/03/2017 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Slide
22/03/2017 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (heap)
23/03/2017 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.[CLRS] cap 10 (tutto), cap 11: 11.1, 11.2, 11.3, 11.3.1.
27/03/2017 Gestione delle collisioni mediante concatenamento: analisi al caso medio. Tabelle hash a indirizzamento aperto: inserimento, ricerca, cancellazione; scansione lineare, scansione quadratica, doppio hashing; analisi al caso pessimo e medio (ricerca senza successo).[CLRS] cap 11: 11.2, 11.4. Tabelle hash (Note di F.Luccio)
28/03/2017 Laboratorio: Qsort e ripasso delle struct.Slide
29/03/2017 Tabelle hash a indirizzamento aperto: analisi al caso medio di inserimento e ricerca con successo. Alberi binari: visite.[CLRS] cap 10: 10.4, cap 11: 11.4.
30/03/2017 Alberi e alberi binari: algoritmi ricorsivi su alberi binari, memorizzazione binarizzata. Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (ricerca, minimo, massimo, successore, predecessore). [CLRS] cap 10: 10.4, cap 12: 12.1, 12.2. [CGGR]: Algoritmi ricorsivi su alberi binari Esercizi (alberi e alberi binari)
3/04/2017 Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). Esercitazione: progettazione di algoritmi efficienti (dizionari, alberi binari, alberi binari di ricerca). [CLRS] cap 12: 12.3. Esercizi (dizionari, alberi binari, alberi binari di ricerca)
04/04/2017 Laboratorio: Esercizi d'esame: qsort e struct.Slide
5/04/2017 Esercitazione: Esercizi sulla prima parte del corso in preparazione del compitino.Esercizi svolti: array, alberi e dizionari
11/04/2017Primo compitino: ore 14, aule A, B, C, G, A1testo
20/04/2017 Alberi 2-3: definizione, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi 2-3 (ricerca; inserimento; cancellazione). [DFI]: Alberi 2-3
21/04/2017
ore 14, aula A
Correzione del primo compitino e visione scritti
21/04/2017
ore 16-18
Laboratorio: Liste. Slide
24/04/2017 Lezione rinviata a venerdì 28 aprile, ore 14, aula A.
26/04/2017 Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva. Programmazione Dinamica (note di F. Luccio)
[CLRS] cap 15: 15.4.
27/04/2017 LCS: ricostruzione della soluzione, algoritmi LCS-LENGTH e PRINT-LCS. Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione, algoritmo ED.Edit Distance (note di F. Luccio). [CLRS] cap 15: 15.4.
28/04/2017 Edit Distance: algoritmo ALLINEA. Studiare anche il problema della ricerca approssimata di un pattern in un testo sulle note di F. Luccio.
Esercitazione: Programmazione Dinamica.
Esercizi sulla Programmazione Dinamica Soluzioni Soluzioni (simulazioni)
2/05/2017 Laboratorio: Alberi binari di ricerca. Slide
3/05/2017 Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello zaino. Algoritmi pseudopolinomiali. [CLRS] cap 16: 16.2, Algoritmo PD per lo Zaino. [BFL]: generazione delle sequenze binarie e delle permutazioni. [CGGR]: pseudopolinomialità.
Appunti AA 2015/16
4/05/2017 Generazione delle permutazioni.
Esercitazione: dizionari.
8/05/2017 Esercitazione: programmazione dinamica, sequenze binarie e permutazioni. Esercizi Partizione di un insieme di interi Algoritmo enumerativo
09/05/2017 Laboratorio: Tabelle Hash. Slide
10/05/2017 Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi. [CLRS]: appendice B.4, cap 22: 22.1.
11/05/2017 Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità e correttezza. [CLRS] cap 22: 22.2 con lem/teo/cor da 22.1 a 22.5.
15/05/2017 Grafi: albero di visita in ampiezza e algoritmo PRINT-PATH; visita in profondità (DFS): analisi di complessità, proprietà. [CLRS] cap 22: 22.3 con lem/teo/cor 22.7, 22.8 e 22.9.
16/05/2017 Laboratorio: Simulazione prova di esame.
17/05/2017 Grafi: visita in profondità e classificazione degli archi; ordinamento topologico di grafi diretti aciclici. [CLRS] cap 22: 22.3, 22.4 con lem/teo/ 22.10, 22.11 e 22.12.
18/05/2017 Esercitazione: progettazione di algoritmi efficienti su grafi. Esercizi
22/05/2017 Introduzione alla computabilità: problemi indecidibili, il problema dell'arresto. Problemi intrattabili: le Torri di Hanoi. Lucidi 2017 The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006
23/05/2017 Laboratorio: Simulazione prova di esame.
24/05/2017 Teoria della complessità: le classi P e NP, i problemi NP completi (intervento di Fabrizio Luccio). [BFL]: Le classi P, NP e NPC Riduzioni polinomiali e problemi NP completi
25/05/2017 Esercitazione: certificati polinomiali e algoritmi di verifica.
29/05/2017 Esercitazione: esercitazione conclusiva in preparazione della prova scritta. Time with class! Let's count!
1/06/2017Secondo compitino: ore 8:30 (aula A)
informatica/all-b/algob_17/start.txt · Ultima modifica: 06/02/2018 alle 14:26 (6 anni fa) da Linda Pagli