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.

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.

Data Tipo Prova Documento

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, canale twitter, 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 sulla notazione asintotica
informatica/all-a/start.txt · Ultima modifica: 19/02/2019 alle 16:50 (5 ore fa) da Giuseppe Prencipe