Strumenti Utente

Strumenti Sito


informatica:all-a:all09:start

Algoritmica e Laboratorio - Corso A - 2009/2010

Informazioni Generali

Al Kowarizmi Docente: Paolo Ferragina

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

Informazioni: News distribuite tramite Twitter con hashtag “#algo2010”.

Ricevimento studenti: ore 16-19, ogni Lunedì, studio docente presso il Dipartimento di Informatica.

Registro: Disponibile nel sito UNIPI.

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.

Orario Lezioni

Orario delle Lezioni
Lunedì 11-13 E Teoria
Martedì 11-13 M Laboratorio
Giovedì 11-13 C Teoria
Venerdì 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, 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.

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

Data Tipo Prova Documento Note
08/04/2010, ore 11.00 Primo Compitino testo con soluzione, risultati
24/05/2010, ore 9.00 Secondo Compitino testo con soluzione, risultati
31/05/2010, ore 15.00 Prova di Laboratorio
22/06/2010, ore 14.30 Scritto testo con soluzione, risultati
23/06/2010, ore 15.00 Prova di Laboratorio
13/07/2010, ore 14.30 Scritto testo con soluzione e voti
14/07/2010 Prova di Laboratorio
13/09/2010, ore 9.00 Scritto Testo
13/09/2010 Prova di Laboratorio
01/02/2011 Scritto Testo.
02/02/2011 Prova di laboratorio
16/02/2011 Scritto Testo
02/02/2011 Prova di laboratorio

IMPORTANTE: Gli studenti della Classe 26 possono sostenere la prova scritta di ALL, e questa verrà riconosciuta come scritto dell'esame di Algoritmica (vecchio corso). Per quanto riguarda l'orale questo dovrà essere sostenuto con la Prof.ssa Pagli. Di contro il laboratorio di ALL non sostituisce l'esame LLS, che quindi dovrà essere svolto con il dott. Gervasi.

Libri di testo

A scelta tra:

  • [CLR] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, Third edition, 2009.
  • [CGG] P. Crescenzi, G. Gambosi, R. Grossi. Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2005. Per approfondimenti ed errata: http://www.algoritmica.org/sda/pmwiki.php

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 suggeriamo il compilatore e il debugger disponibili con MinGW, e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. 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 AIL), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.

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, Karp-Rabin.
  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
22/02/10 Laboratorio: Editing, compilazione. Richiami di linguaggio C: Istruzioni varie e operatori, array, printf, scanf. Cap. 2-3, 7.1-7.4 di [KR].slides
23/02/10 Laboratorio: Puntatori, funzioni e passaggio parametri. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. slides
23/02/10 Laboratorio: Esercitazione. slides
25/02/10 Laboratorio: Allocazione dinamica della memoria (malloc) slides soluzioni(2 e 3)
26/02/10 Laboratorio: Stringhe. slides (svolgere gli esercizi 3 e 4)
01/03/10 Introduzione al corso: nozioni di Algoritmo, Problema, istanza, dimensione dell'istanza, complessità in tempo e spazio al caso pessimo e caso medio, analisi asintotica e confronto di algoritmi. Algoritmi polinomiali ed esponenziali. Prerequisiti matematici.
02/03/10 Laboratorio: Codifica binaria. Poblema del maggioritario: soluzione quadratica, algoritmo ottimo slides soluzioni esercizi 3 e 4 del 26/02 note sul maggioritario (con esempio)
04/03/10 Problema sequenza somma-max: soluzione cubica, quadratica e lineare. Problemi indecidibili: tecnica della diagonalizzazione, problema della fermata. Problema delle torri di Hanoi. Una nota sul problema della fermata
02/03/10 Problema del RoadBlock. Definizione classi P, NP, NP-completi, EXPTIME. Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano (e confronto con Ciclo Elueriano), Zaino. Esempi di riduzioni: SAT - IP01 e SAT - Clique Alcuni appunti utili (P/NP e K-clique).
08/03/10 Notazione: O-grande, Omega-grande, o-piccolo, omega-piccolo e theta, con esercizi Notazioni Asintotiche (con esercizi) Sez. 2.2.1 e pag. 10 dell'appendice dell'errata corrige di [CGG].
09/03/10 Laboratorio: Coding del sottoarray di somma massima. Redirezione dell'input e timing di un programma. note testfiles codice somma massima Esercizio
11/03/10 Laboratorio: tecnica del doubling per allocazione dinamica di array, calcolo numero elementi distinti di un array ordinato. slidestestfiles intersezione in tempo quadratico
12/03/10 Laboratorio: note sull'implementazione del doubling. Selection Sort, esercizio: adattare Selection Sort all'ordinamento di stringhe. (N.B.: gli esercizi per casa sono un'utile verifica sulla comprensione degli argomenti trattati in laboratorio) soluzione esercizio su doubling slides testo degli esercizi
15/03/10 Insertion Sort: proprietà e complessità. Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni. Esempi: min/max, ricerca di una chiave, ordinamento. Problema della ricerca di una chiave: scansione e ricerca binaria (iterativa e ricorsiva). Studiare anche questo approfondimento dal libro di F. Luccio “La struttura degli algoritmi” (Boringhieri, 1982).
16/03/10 Laboratorio: funzione di libreria qsort. Svolgere l'esercizio 3 a casa esempio qsort_esercizi.pdf soluzioni(1 e 2)
18/03/10 Tecnica “divide et impera”. Relazioni di Ricorrenza e teorema per la loro risoluzione. MergeSort: algoritmo, proprietà, e analisi della complessità. La versione del Teorema da studiare è quella del CLR commentata anche in questi appunti.
19/03/10 Moltiplicazione veloce di due interi di n cifre. Ricerca Binaria: iterativa e ricorsiva, con analisi di complessità.
19/03/10 Esercitazione extra: Esercizi su notazione asintotica, algoritmi ricorsivi, e calcolo della loro complessità in tempo. Sul funzionamento degli algoritmi ricorsivi. Aula F1
22/03/10 Programmazione dinamica: definizione, proprietà, esempi: Numeri Fibonacci, coefficiente binomiale, problema del “rod cutting”. Alcuni appunti: clr, luccio.
23/03/10 Laboratorio: Esercizi sul MergeSort. Svolgere l'esercizio 4 a casasoluzioni (12/03/10) esercizio 3 (16/03/10) Esercizi input
23/03/10 Lezione extra: Quicksort: proprietà, analisi della complessità (caso medio, ottimo e pessimo) e considerazioni pratiche. Due tecniche di “distribuzione“. Quicksort randomizzato. qsort del C come quicksort + insertionSort. Studiare anche questi appunti e altra tecnica di distribuzione.
25/03/10 Counting sort e Radix sort, con valutazione della complessità.
26/03/10 Esercitazione pre-compitino.
Soluzioni esercizi di laboratorio del 23/03: codice
13/04/10 Due paradigmi algoritmici: Genera Binarie e Permutazioni, con esempi appunti per chi possiede il [CLR]
15/04/10 Le liste, operazioni, e la loro variante randomizzata (skip list) appunti per chi possiede il [CLR]
16/04/10 Code con priorità: Heap, e sue operazioni – Empty, First, Enqueue, Dequeue, IncreaseKey, DecreaseKey. Valutazione della complessità. Heapify (con dimostrazione di correttezza), BuildHeap e Heapsort.
19/04/10 Funzioni hash: metodo della moltiplicazione e della divisione. Tabelle hash con liste di trabocco.
20/04/10 Tabelle hash con indirizzamento aperto. Pattern matching su stringhe: metodo di Karp e Rabin. Algoritmo KR: simulazione e note
22/04/10 Esercitazione su Heap e Tabelle hash. Un richiamo sull'analisi ammortizzata. Appunti su analisi ammortizzata
23/04/10 Laboratorio: tipi di dato struct e liste slides
26/04/10 Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo.
27/04/10 Laboratorio: Richiami sulle liste, Tabelle hash con liste di trabocco. Decsirzione e uso di DDD. slides esercizisoluzioni
29/04/10 Alberi Binari di Ricerca: definizione, proprietà e algoritmi per la ricerca di una chiave, l'inserimento e la cancellazione di un nodo. Alberi 1-bilanciati e alberi di Fibonacci. Alberi AVL e tecniche di bilanciamento: rotazione oraria e anti-oraria. Appunti su cancellazione e ribilanciamento.
30/04/10 Pile e Code. Grafi: terminologia e notazione. Rappresentazione e chiusura transitiva. Esercizi sugli alberi.
03/05/10 Visita BFS: proprietà, algoritmo e dimostrazione di correttezza. Esercitazione.
04/05/10 Laboratorio: Esercizi sugli alberi binari di ricerca. esercizi slidessoluzioni
07/05/10 Visita DFS: proprietà, algoritmo, complessità, e dimostrazione di correttezza. DAG e ordinamento topologico.
10/05/10 Laboratorio: Esercitazione su alberi, liste ed heaps. slides
11/05/10 Simulazione della prova di laboratorio
13/05/10 Minimum Spanning Trees: Approccio Greedy, e dimostrazione correttezza. Algoritmo di Kruskal. Struttura dati Union-Find. Esercizio da svolgere per il prossimo laboratorio
14/05/10 Minimum Spanning Trees: Algoritmo di Prim.
17/05/10 Cammini Minimi: Algoritmo di Dijkstra, esempio e dimostrazione di correttezza.
18/05/10 Laboratorio: Correzione esercizio di auto-valutazione. slides soluzioni
20/05/10 Esercitazione su argomenti secondo compitino
21/05/10 Esercitazione su argomenti secondo compitino
informatica/all-a/all09/start.txt · Ultima modifica: 10/04/2013 alle 21:33 (5 anni fa) da Rossano Venturini