Strumenti Utente

Strumenti Sito


informatica:all-a:all16:start

Algoritmica e Laboratorio - Corso A

Anno accademico 2015/2016

Informazioni Generali

Docenti: Linda Pagli, Rossano Venturini, Andrea Marino, Giulio Pibiri

(Docenti corso B: Anna Bernasconi, Rossano Venturini,Nadia Pisanti, Andrea Farruggia)

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio.

Semestre: secondo.

Ricevimento studenti: durante le lezioni il mercoledì alle 2.30 ufficio pagli, poi su appuntamento.

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.

AVVISO

su http://mediateca.unipi.it sono a disposizione disposizione le video-lezioni fino al 2 marzo. Bisogna registrarsi con le credenziali di ateneo.

Orario Lezioni

Orario delle Lezioni
Martedì 14-16 H, M Laboratorio
Mercoledì 11-13 C Teoria
Giovedì 14-16 C Teoria
Venerdì 11-13 C Teoria

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, nel qual caso lo studente è ammesso a sostenere la prova di laboratorio.
  • 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à il cui superamento permette allo studente di essere ammesso a sostenere la prova orale.
  • 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. Se una prova non viene passata, occorre risostenere soltanto quella.

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

Data Tipo Prova Documento Note
31/03/2016, ore 9:00 Scritto (primo compitino)algo1_310316.pdf lista dei risultati (sono ammessi alla seconda prova di verifica intermedia gli studenti con voto >= 17)
25/05/2016, ore 9:00 Scritto (secondo compitino)Testo e soluzionilista dei risultati (sono ammessi alla seconda prova di verifica intermedia gli studenti con voto >= 17) Visione scritti e inizio orali: lunedì 30 maggio, dalle 9:30 alle 13.00 ufficio Pagli.
27/06/2016, ore 9:00 Scritto Testo e soluzioni lista dei risultati Visione scritti: giovedì 30 giugno, ore 9:30, ufficio Pagli.
13/07/2016, ore 9:00 Scritto Testo lista dei risultati Visione scritti: lunedì 18 luglio, ore 9:30, ufficio Pagli.
05/09/2016, ore 9:00 Scritto Testolista dei risultati Visione scritti: lunedì 12 settembre, ore 9:30, ufficio Pagli.
31/10/2016, ore 15 Scritto, Appello straordinario Risultati Visione scritti e orali su appuntamento
23/01/2017, ore 15 Scritto Testo Risultati Visione scritti e orali su appuntamento

Prossime date per le prove orali:

Data Ora Aule Note
30/06/2016 10:00 da decidere obbligatorio iscriversi (via email)
01/07/2016 10:00 da decidere obbligatorio iscriversi (via email)
4/07/2016 11.00 da decidere obbligatorio iscriversi (via email)
19/07/2016 9.30 uffico Pagli obbligatorio iscriversi (via email)
12/09/2016 9.30 uffico Pagli obbligatorio iscriversi (via email)

Prossime date per le prove di laboratorio:

Data Ora Aule Documento Note
05/04/2016 14:00 H Appello straordinario riservato a studenti lavoratori e fuori corso
09/06/2016 9:00 H,M,I Appello riservato agli studenti che hanno superato i compitini o appelli precedenti
04/07/2016 9:00 H,M,I
25/07/2016 9:00 H,M,I
09/09/2016 9:00 H,M,I

Libri di testo

  • [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.

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://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 (AVL), 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 Lavagne
23/02/2016 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Lucidi.
24/02/2016 Nozioni di Problema, Algoritmo, Limite Inferiore. Analisi di un problema semiserio: il problema delle 12 monete. Moltiplicazione Egizia.12 monete lav1.pdf
25/02/2016 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. [CLRS]: cap 1, cap 2: 2.1, 2.2. lav2.pdf
26/02/2016 Selection Sort definizione e analisi. Paradigma del Divide et Impera. Merge: definizione e complessità. Merge-Sort: definizione [CLRS]: cap 2: 2.3lav3.pdf
01/03/2015 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
02/03/2016 Selection Sort definizione e analisi. Paradigma del Divide et Impera. Merge: definizione e complessità. Merge-Sort: correttezza e complessità. Definizione e uso delle notazioni asintotiche [CLRS]: cap 2: 2.3, cap 3: 3.1. TCS cheat sheetlav4.pdf
03/03/2016 Esercitazione: progettazione di algoritmi e analisi di complessità.Esercizi (ricerca, ordinamento, divide et impera)lav5.pdf
04/03/2016 I problemi della ricerca e dell'ordinamento. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo. limiti inferiorilav6.pdf
08/03/2016 Laboratorio: Esercizi.
09/03/2016 Tecnica dell'oracolo o avversario: Limite inferiore per il problema del doppio torneo. Equazioni di ricorrenza: metodi iterativo e con albero di ricorsione. Enunciato del Teorema dell'esperto. oracol.pdf, [CLRS]: cap 4: 4.4, 4.5lav7.pdf
10/03/2016 Esercitazione: progettazione di algoritmi e analisi di complessità. lav8.pdf
11/03/2016 Moltiplicazione veloce di interi e matrici. Esercitazione: esercizi sull'applicazione del Teorema Principale.[CLRS] cap 4: 4.2. Moltiplicazione veloce di interi (appunti del Prof. Grossi) lav9.pdf
15/03/2016 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Lucidi
16/03/2016 Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi della complessità nel caso medio. [CLRS] cap 7: 7.1, 7.2, 7.3, 7.4.2 Numero di confronti di Randomized-Quicksort (Appunti del Prof. Luccio) lav10.pdf
17/03/2016 QuickSelect: proprietà e analisi della complessità nel caso ottimo e pessimo. Esercitazione: progettazione di algoritmi e analisi di complessità. [CLRS] cap 9: 9.9, analisi al caso medio esclusa Esercizi (divide et impera, ricorrenze, ordinamento) lav11.pdf
18/03/2016 Heap: definizione, realizzazione implicita come array, proprietà, conservazione della proprietà di heap. Code di priorità[CLRS] cap 6: 6.1, 6.2, 6.5.lav12.pdf
22/03/2015 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe, e QuickSort. Lucidi Lucidi
23/03/2016 Costruzione dell'Heap, HeapSort, analisi[CLRS] cap 6: 6.3, 6.4 lav13.pdf
24/03/2016 Esercitazione: progettazione di algoritmi e analisi di complessità. lav14.pdf
31/03/2016 Prima prova di verifica intermedia. lista dei risultati
6/04/2016 Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort.[CLRS] cap 8: 8.2, 8.3.lav15.pdf
7/04/2016 Correzione della prima prova di verifica e discussione errori. lav16.pdf
8/04/2016 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 e medio).[CLRS] cap 11: 11.2, 11.2, 11.3, 11.3.1. lav17.pdf
12/04/2016 Laboratorio: Qsort e ripasso delle struct.Lucidi
13/04/2016 Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. [CLRS] cap 11: 11.4. Dispense Prof. Lucciolav18.pdf
14/04/2016 Esercitazione: progettazione di algoritmi e analisi di complessità su heap e tabelle hash. lav19.pdf
15/04/2016 Alberi binari: visite, algoritmi ricorsivi su alberi binari. [CLRS] cap 10: 10.4. [CGGR]: Algoritmi ricorsivi su alberi binari lav20.pdf
19/04/2016 Laboratorio: Esercizi d'esame: qsort e struct.Lucidi
20/04/2016 Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (ricerca, minimo, massimo, successore); inserimento e cancellazione. [CLRS] cap 12: 12.1, 12.2, 12.3. lav21.pdf
21/04/2016 Esercitazione: progettazione di algoritmi efficienti su alberi binari e alberi binari di ricerca.EserciziAB lav22.pdf
22/04/2016 Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni.). [CGGR]: Alberi AVL, rotazioni. lav23.pdf
26/04/2016 Laboratorio: Liste. Lucidi
27/04/2016 Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva. [CLRS] cap 15: 15.4.
28/04/2016 LCS: ricostruzione della soluzione, algoritmi LCS-LENGTH e PRINT-LCS. [CLRS] cap 15: 15.4.
29/04/2016 Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). Esercizi su dizionari e alberi Soluzioni lavagna
3/05/2016 Laboratorio: Alberi binari di ricerca. Lucidi
4/05/2016 Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione, algoritmi ED e ALLINEA. Edit Distance (dispense Prof. Luccio). lav24.pdf
5/05/2016 Esercitazione: Programmazione Dinamica.Esercizi sulla Programmazione Dinamica lav25.pdf
10/05/2016 Laboratorio: Tabelle Hash. Lucidi
11/05/2016 Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmi pseudopolinomiali. Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello zaino. [CLRS] cap 16: 16.2, esercizio 16.2.2 (algoritmo PD per lo Zaino). [CGGR]: generazione delle sequenze binarie, pseudopolinomialitàlav26.pdf
12/05/2016 Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi (ciclo hamiltoniano e ciclo euleriano). Visita in ampiezza (BFS), algoritmo e analisi di complessità, [CLRS]: appendice B.4, cap 22: 22.1, 22.2lav27.pdf
13/05/2016 Grafi: albero di visita in ampiezza e algoritmo PRINT-PATH; esplorazione di un grafo con insieme di vertici non noto; visita in profondità (DFS). [CLRS] cap 22: 22.2, 22.3 (senza dimostrazioni).lav28.pdf
18/05/2016 Grafi: visita in profondità (DFS), analisi di complessità, classificazione degli archi; ordinamento topologico di grafi diretti aciclici. [CLRS] cap 22: 22.3, 22.4. lav29.pdf
19/05/2016 Esercitazione: progettazione di algoritmi efficienti su grafi.Esercizi lav30.pdf
20/05/2016 Introduzione alla computabilità, problemi indecidibili. Il problema dell'arresto. Teoria della complessità: le classi P e NP.Calcolabilità Complessità
24/05/2016 Laboratorio
25/05/2016 Seconda prova di verifica intermedia.
informatica/all-a/all16/start.txt · Ultima modifica: 23/01/2017 alle 13:20 (20 mesi fa) da Linda Pagli