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: il martedì dalle 16 alle 18 (per ricevimento in orari diversi da quanto previsto inviare 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

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://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)
informatica/all-b/start.txt · Ultima modifica: 18/04/2018 alle 17:14 (2 giorni fa) da Linda Pagli