Strumenti Utente

Strumenti Sito


informatica:all-b:start

Algoritmica e Laboratorio - Corso B

Anno accademico 2017/2018

Informazioni Generali

Docenti Teoria/Esercitazioni: Linda Pagli (corso B) e Paolo Ferragina (corso A)

Docenti Laboratorio: Anna Bernasconi, Alina Sirbu, 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: su appuntamento inviarndo e-mail a linda.pagli@unipi.it).

Anni accademici precedenti

Orario Lezioni

Orario delle Lezioni
Martedì 9-11 E Teoria
Martedì 14-16 H, I, M Laboratorio
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 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
4/4/2018 primo compitino risultati primo compitinoSono ammessi al secondo compitino gli studenti con voto ≥ 17. Gli insufficienti non sono riportati. Correzione e visione dei compiti 11/04/2018 dalle 14 aula E
30/05/18
ore 9-11
Secondo Compitino testo, soluzione, lista dei risultati . Per la correzione e visione del compito: Aula A1, martedì 5 giugno, ore 10:00.
La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto di media (valido solo per i compitini) viene perso se si decide di sostenere la prova orale, la quale è quindi facoltativa per chi ha passato i compitini, ma può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in qualunque appello.
22/06/18 Primo Appello testo, soluzione, lista dei risultati (solo quelli che hanno riportato una votazione >=18). Per la correzione e visione del compito: Aula C, lunedì 25 giugno, ore 16:00.
La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto dello scritto viene perso se si decide di sostenere la prova orale, la quale è quindi facoltativa e può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in qualunque appello o ricevimento del docente.
13/07/18
ore 9-11
Secondo appello testo soluzione lista dei risultati Insufficienti e annullati non compaiono nella lista. Per la correzione e visione del compito: Aula C1, lunedì 16 luglio, ore 11:00 e lunedì 23 luglio ore 11.30 ufficio Pagli. Per registrazione 23/7/2018 ore 16.00 ufficio Pagli.
04/09/18
ore 9-11
Terzo appello

Prossime date per la prova di laboratorio:

Data Ora Aule
29/06/2018 9.30

Prossime date per le prove orali:

Data Ora Aula Note
29/06/2018 ore 11.30 ufficio pagli
16/07/2018 ore 11 Aula C1

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://algo1718.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/2018 Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.12 monete
20/02/2018 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Slide
21/02/2018 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 e pessimo. Selection sort: analisi di complessità. [CLRS] cap 1, cap 2: 2.1, 2.2.
22/02/2018 Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. [CLRS] cap 3. TCS cheat sheet Esercizi Notazioni O,Omega e Teta
27/02/2018 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.
27/02/2018 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
28/02/2018 MergeSort: complessità con albero di ricorsione. Esercitazione: Ricerca sequenziale analisi del caso medio, soluzione esercizi proposti nella lezione del 22/2.[CLRS] cap 1: 1.2
29/02/2018 Lezione non tenuta per emergenza neve
06/03/2018 Ricerca binaria. Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmo del torneo. [CLRS] cap 8: 8.1. Note di F. Luccio su limiti inferiori.
06/03/2018 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Slide
07/03/2018 Limite inferiore alla complessità del Sorting. Esercitazione: MergeInsertionSort. [CLRS] cap 8: 8.1, problema 2.1 pag.34
08/03/2017 Relazioni di ricorrenza: Teorema dell'esperto (Master Theorem) con esempi di applicazione. cap 4: 4.5, 4.6.1.
13/03/2018 Moltiplicazione veloce di interi di n cifre. Moltiplicazione veloce di matrici. Algoritmo di Strassen.Note di F. Luccio e di R. Grossi sulla moltiplicazione veloce di interi e matrici.
13/03/2018 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Slide
14/03/2018 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (ricorrenze, ricerca, ordinamento, divide et impera)
15/03/2018 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
20/03/2018 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)
20/03/2018 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Slide
21/03/2018 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (divide et impera, ricorrenze, ordinamento)
22/03/2018 Heap: definizione, realizzazione implicita come array. Code di priorità, operazioni, definizione e realizzazione mediante heap.[CLRS] cap 6: 6.1, 6.5.
27/03/2018 La struttura dati Heap: costruzione con Max-Heapify con analisi della complessità e correttezza. L'algoritmo Heapsort. Esercizi sull'Heap [CLRS] cap 6: 6.2, 6.3, 6.4.
27/03/2018 Laboratorio: Qsort e ripasso delle struct.Slide
28/03/2018 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (heap)
04/04/2018 prima verifica scritta compito1 e compito2
11/04/2018 Esercitazione: correzione e discussione sugli esercizi del compitino.
12/04/2018 Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. [CLRS] cap 8: 8.2, 8.3.
Si invitano gli studenti a studiare il Capitolo 10 [CLRS] per ripassare le nozioni di Pila, Coda e Lista, e algoritmi su queste strutture dati elementari.
17/04/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 11: 11.1, 11.2, 11.3, 11.3.1.
17/04/2018 Laboratorio: Esercizi d'esame: qsort e struct.Slide
18/04/2018 Tabelle hash a indirizzamento aperto: inserimento, ricerca, cancellazione; scansione lineare, scansione quadratica, doppio hashing; analisi al caso pessimo e medio (ricerca senza successo). Analisi del caso medio della ricerca [CLRS] cap 11: 11.2, 11.4. Tabelle hash (Note di F.Luccio)
24/04/2018 Algoritmi ricorsivi su alberi binari. Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (ricerca, minimo, massimo, successore, predecessore). [CLRS] cap 12: 12.1, 12.2. [CGGR]: Algoritmi ricorsivi su alberi binari Esercizi (alberi e alberi binari)
24/04/2018 Laboratorio: Liste monodirezionali e bidirezionali. Slide Esercizio 1 in aula.
26/04/2018 Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). Esercitazione: progettazione di algoritmi efficienti su alberi. [CLRS] cap 12: 12.3. Esercizi (dizionari, alberi binari, alberi binari di ricerca)
02/05/2018 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
03/05/2018 Generazione delle sequenze binarie. Generazione delle permutazioni. Esempi. [CGGR]: alcune note su generazione binarie e permutazioni
08/05/2018 Grafi: definizioni e allocazione in memoria. Il problema del ciclo euleriano e il problema del ciclo hamiltoniano: definizioni, e considerazioni computazionali. Enunciato del Teorema di Eulero. Alcune note su ciclo euleriano e hamiltoniano. [CLRS]: appendice B.4, cap 22: 22.1.
08/05/2018 Laboratorio: Alberi binari di ricerca. Slide
09/05/2018 Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità e correttezza, albero di visita in ampiezza e algoritmo PRINT-PATH. [CLRS] cap 22: 22.2
10/05/2017 Grafi: visita in profondità (DFS), analisi di complessità e correttezza, classificazione degli archi; ordinamento topologico di grafi diretti aciclici. [CLRS] cap 22: 22.3, 22.4 con teo 22.12, Esercizi
Esercizi da svolgere/svolti su alberi e tabelle hash. Testo 1 e testo 2
15/05/2017 Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci e del binomiale). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva, algoritmi LCS e PRINT-LCS.. Programmazione Dinamica (note di F. Luccio)
[CLRS] cap 15: 15.4.
15/05/2018 Laboratorio: Tabelle hash. Slide Esercizio 1 in aula
16/05/2018 LCS: Sottostruttura ottima. 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.
17/05/2018 Problema delle apparizioni approssimate. Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmo enumerativo per il problema dello zaino basato su genera binarie. Algoritmi pseudopolinomiali. [CLRS] cap 16: 16.2, Algoritmo PD per lo Zaino. [CGGR]: pseudopolinomialità.
22/05/2018 Teoria della complessità: le classi P e NP, i problemi NP completi . [BFL]: Le classi P, NP e NPC PvsNP
22/05/2018 Laboratorio: Simulazione prova di esame.
23/05/2018 Esercitazione: esercizi di ripasso su Grafi.
24/05/2018 Esercitazione: esercizi di ripasso su Programmazione Dinamica.
29/05/2018 Esercitazione: esercizi di ripasso. testo e soluzione testo e Soluzione
29/05/2018 Laboratorio: Grafi. Slide
informatica/all-b/start.txt · Ultima modifica: 23/07/2018 alle 09:27 (4 settimane fa) da Linda Pagli