Strumenti Utente

Strumenti Sito


informatica:all-a:start

Algoritmica e Laboratorio - Corso A

Anno accademico 2018/2019

Informazioni Generali

Docenti Teoria/Esercitazioni: Giuseppe Prencipe e Linda Pagli (corso A)

Docenti Laboratorio: Anna Bernasconi, Daniele De Sensi Rossano Venturini

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Semestre: secondo.

Ricevimento studenti Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento)

Ricevimento studenti: Pagli: su appuntamento, scrivere a linda.pagli@unipi.it

Registro delle lezioni: si tratta del registro ufficiale che riporta quanto indicato nel seguito.

NEW: Ricevimento Collettivo con i Counselor !!!!

A partire dal 13 Marzo, ogni Martedi' 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
A1 (da AA a DE) Aula H, martedì 16:00 - 18:00
A2 (da DI a NA) Aula M, martedì 16:00 - 18:00
A3 (da NE a ZZ) Aula M, venerdì 14:00 - 16:00

Orario Lezioni

Orario delle Lezioni
Lunedì 9-11 aula E Teoria
Martedì 16-18 aule H-I-M Laboratorio
Mercoledì 11-13 aula E Teoria
Venerdì 9-11 aula E Teoria
Venerdì 14-16 aula M 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, ma 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 già sostenute.
  • La registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo, e questo potrà avvenire in qualunque appello durante la prova orale.

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 d'esame.
03/06/19 Secondo Compitino

Registrazioni delle Lezioni

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-165.
  • [FL] P. Ferragina, F. Luccio. Il Pensiero Computazionale: dagli algoritmi al coding. Il Mulino, 2017. Solo pagine 64-65, Capitolo 7 e Capitolo 10.

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. 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 “dell'esperto”.
  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
18/02/2019 Questioni organizzative: pagina web, laboratori, ricevimento studenti e modalità di esame.
Introduzione al corso: nozione di algoritmo, problema, dimensione dell'input, limite inferiore/superiore alla complessità di un problema/algoritmo. Analisi di un problema semiserio: il problema delle 3, 4, 5 e 12 monete.
Capitolo 1 del CLRS, e 12 monete
19/02/2019 22/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
20/02/2019 Modello RAM e complessità computazionale di un algoritmo in tempo e spazio: caso pessimo, caso ottimo e caso medio. Notazione asintotica: O-grande, Omega e Theta, o-piccolo e omega-piccolo. CLRS: Capitolo 3
Slide
22/02/2019 Esercitazione: Notazione asintotica. SelectionSort, algoritmo, complessità. TCS cheat sheet
25/02/2019 InsertionSort: algoritmo, correttezza e complessita'.
26/02/2019 01/03/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
27/02/2019 Paradigma del Divide et Impera: descrizione, pseudo-codice e analisi della complessità in tempo mediante relazioni di ricorrenza. Esempio su calcolo del massimo di un vettore. MergeSort: algoritmo, correttezza e analisi di complessità del Merge. [CLRS] cap 2: 2.3; cap 4: 4.4.
01/03/2019 Esercitazione. Ricerca Sequenziale, con analisi caso medio, Ricerca Binaria ricorsiva, iterativa, che restituisce il k più a sinistra. Confronti e analisi.
04/03/2019 Algoritmi polinomiali ed esponenziali: definizione, confronto e caso di PC k-volte più veloce, con considerazioni. Problema della Torre di Hanoi: definizione, risoluzione con algoritmo ricorsivo e valutazione della complessità con relazione di ricorrenza. Pseudo-codice ricorsivo con valutazione della complessità: caso lineare e caso logaritmico. Consultare [FL].
Slide.
05/03/2019 08/03/2019 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Slide
06/03/2019 Enunciato del Teorema dell'esperto, con esempi.
08/03/2019 Dimostrazione del Teorema dell'esperto per il caso delle potenze. [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte)
11/03/2019 Esercizi sul Teorema dell'esperto. Algoritmo della Moltiplicazione veloce di interi e di matrici con analisi della complessità. [CLRS] con esercizi. Note di F. Luccio su moltiplicazione interi e matrici.
12/03/2019 15/03/2019 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Slide
13/03/2019 Quicksort: descrizione intuitiva, pseudo-codice, versione randomizzata, analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Studiare anche Partizione di Hoare (Problema [CLRS] 7.1) e Partizione con elementi uguali (Problema [CLRS] 7.2) [CLRS] cap 7
15/03/2019 Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmi per determinare il primo e secondo, algoritmo del doppio torneo. Note di F. Luccio su limiti inferiori. [CLRS] cap 8: 8.1.
18/03/2019 Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. La struttura dati Heap: proprietà, esempi, Max-Heapify con analisi della complessità e correttezza. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. [CLRS] cap 9: 9.1, 9.2 (leggere analisi al caso medio dalla seguente nota).
[CLRS] cap 6: 6.1 - 6.4.
19/03/2019 22/03/2019 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Slide
20/03/2019 Heapsort. Code di priorità: definizione, operazioni, realizzazione mediante heap. [CLRS] cap 6: 6.5.
22/03/2019 Esercitazione: problema del mergeInsertionSort, con analisi e limite inferiore. Algoritmi Divide et impera e come trasformazione di ricerca Binaria (cuspide, trova occorrenze)ricerca binaria sinistra
25/03/2019 Esercizi Master Theorem. Slides
26/03/2019 29/03/2019 Laboratorio: Qsort e ripasso delle struct.Slide
informatica/all-a/start.txt · Ultima modifica: 25/03/2019 alle 13:00 (7 ore fa) da Giuseppe Prencipe