Strumenti Utente

Strumenti Sito


informatica:all-a:all10:start

Algoritmica e Laboratorio - Corso A - 2010/2011

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 “#algo2011”.

Ricevimento studenti: su appuntamento.

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ì 9-11 C1 Teoria
Martedì 9-11 B Teoria
Mercoledì 9-11 C Teoria
Giovedì 9-11 M-lab Laboratorio

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.

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
06/06/2011, ore 09.00 Scritto Risultati della classe 26 (questi sosterranno solo la prova orale con la Prof.ssa Pagli). Gli altri (lista dei risultati ordinati per matricola) che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà il 15 Giugno, alle ore 15; è possibile anche sostenere la prova in altro appello. L'orale è il 20 Giugno, alle ore 10.30 (studio Ferragina)
15/06/2011, ore 15.00 Laboratorio soluzione
21/06/2011, ore 09.00 Scritto Visione compiti ore 8.45, prima del Laboratorio, aula M. Risultati: Santo (INS), Capasso (27), Sammartano (INS), Lucchesi (18), Corsi (INS), Mazza (28), Salvadori (26), Bottai (INS), Gradilone (INS), Bonfigli (27), Mazzurco (28).
22/06/2011, ore 09.00 Laboratorio Orali Venerdì 24 Giugno, ore 13.30, aula B1
07/07/2011, ore 09.00 Scritto Paonessa (18), Gradilone (INS). Visione compiti domani mattina prima del Laboratorio.
08/07/2011, ore 09.00 Laboratorio Orali Martedì 12 Luglio, ore 14, studio Ferragina.
09/09/2011, ore 15.30 Scritto Pandolfi (INS), Lorito (22), Sammartano (22). Gli studenti Gradilone e Mastrosimone sono ammessi con riserva a svolgere il Laboratorio di Lunedì 12 avendo riportato un voto leggermente insufficiente allo scritto; se passeranno il Lab allora la prova scritta gli verrà considerata superata, altrimenti dovranno ripetere lo scritto a un prossimo appello.
12/09/2011, ore 14.30 Laboratorio gli studenti che hanno passato il lab (incluso Paonessa) sono attesi domani martedì 13 presso lo studio del prof Ferragina per la prova orale alle ore 15.
11/01/2012, ore 09.00 Scritto Pandolfi (INS), Tovani (INS), Caprini (26), Gradilone (24).
11/01/2012, ore 15.00 Laboratorio Orale lunedì 16 gennaio, ore 18, studio Ferragina.
01/02/2012, ore 09.00, aula A,B Scritto
01/02/2012, ore 15.00 Laboratorio Risultati scritto Feb 1: Tempone (INS), Paolini (22), Lusardi (23), Pandolfi (22), Pulcinelli (28), Pantaleo (30).
07/02/2012, ore 10.00, aula D Scritto Recupero della prova d'esame dell'1.2.2012 a causa del maltempo.
07/02/2012, ore 14.00, aula H Laboratorio La prova orale si svolgerà il giorno 15 febbraio alle ore 9.15 presso il Dipartimento di Informatica, studio Ferragina.

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. Oppure istallare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux sopra. 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.
  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
07/03/11 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. Esistenza problemi indecidibili. Prerequisiti matematici e indecidibilità (par 1.4)
08/03/2011 Problemi indecidibili: tecnica della diagonalizzazione, problema della fermata. Problemi esponenziali: RoadBlock e torri di Hanoi. Definizione classi P, NP, NP-completi, EXPTIME. Una nota sul problema della fermata. Alcuni appunti utili (P/NP).
09/03/2011 Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano (e confronto con Ciclo Elueriano), Zaino, k-clique. Esempi di riduzioni: SAT - IP01 e SAT - k-Clique. Notazione asintotica: O-grande, Omega-grande e Theta, con esempi. Una riduzione (K-clique).
10/03/2011 Laboratorio: Editing, compilazione. Richiami di linguaggio C: Istruzioni varie e operatori, array, printf, scanf. Cap. 2-3, 7.1-7.4 di [KR].
slides (soluzioni nelle slides della Esercitazione 2)
10/03/2011 Laboratorio: Puntatori, funzioni e passaggio parametri. Sez. 4.1-4.5 e 5.1-5.5 di [KR].
slides soluzioni
14/03/2011 Laboratorio: Tecniche di passagio dei parametri. slides soluzioni
15/03/2011 Laboratorio: Allocazione dinamica della memoria (malloc) slides soluzioni
16/03/2011 Laboratorio: Stringhe slides soluzioni
21/03/2011 Selection Sort e Insertion Sort: proprietà e complessità. Esercizi di valutazione complessità asintotica al caso pessimo.
22/03/2011 Laboratorio: Codifica binaria. Sottoarray di somma massima. Redirezione dell'input e timing di un programma. slides(1) slides(2) soluzioni testfiles
23/03/2011 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). appunti
24/03/2011 Tecnica “divide et impera”. Relazioni di Ricorrenza e teorema per la loro risoluzione. MergeSort: algoritmo, proprietà, e analisi della complessità.
28/03/2011 Moltiplicazione veloce tra interi. Esercitazione su calcolo complessità algoritmi ricorsivi.
29/03/2011 Quicksort: algoritmo, complessità al caso pessimo e medio (con dimostrazione), esempi. 2 tipi di procedure PARTITION. analisi caso medio e altra distribuzione
30/03/2011 Heapsort: definizione heap, proprietà, realizzazione come array, fix-heap, build-heap, heapsort.
31/03/2011 Laboratorio: Insertion sort su interi e stringhe. Ricerca binaria su stringhe. MergeSort su interi esercizi soluzioni(1)
04/04/2011 Pile, Code e code con priorità realizzate mediante heap.
05/04/2011 Considerazioni sulla crescita esponenziale e sulla rappresentazione degli elementi di un insieme. Il vettore di appartenenza. Algoritmo di base per la generazione di configurazioni binarie e sua applicazione a problemi di allocazione tipo “zaino”.
06/04/2011 Algoritmo di base per la generazione di tutte le permutazioni di un insieme e sua applicazione a problemi tipo “ciclo hamiltoniano”. Introduzione alla programmazione dinamica. genera e permuta
07/04/2011 Laboratorio: Quick Sort su interi e su stringhe. Varianti (pari&dispari, 3-way partition) esercizi quick_sort_parziale
11/04/2011 Problemi risolubili efficientemente atraverso sottobproblemi. Il calcolo dei coefficienti binomiali. Il calcolo della pi lunga sottosequenza comune. Esempi.
12/04/2011 Problema della edit distance. Individuazione delle apparizioni approssimate di un pattern in un testo. Esercizi. Introduzione all'odinamento in tempo lineare.
13/04/2011 Gli algoritmi di Counting Sort e Radix Sort. Esercizi.
14/04/2011 Esercitazione pre-compitino.
28/04/2011 Laboratorio: Libreria qsort. Esercizi su stringhe e diversi ordinamenti. esercizi soluzioni
02/05/2011 Le liste: ricerca, inserimento, cancellazione. Gli alberi binari di ricerca: definizione, proprietà, visite, ricerca, min, max, predecessore e successore, con analisi della complessità in tempo.
03/05/2011 Inserimento e cancellazione di un nodo in un albero binario di ricerca
04/05/2011 Alberi AVL: rotazione semplice e doppia appunti
05/05/2011 Laboratorio: Le struct e le liste. Esercizi. slidesesercizi
soluzioniLettura consigliata
09/05/2011 Esercitazione su alberi e algoritmi ricorsivi.
10/05/2011 Tabelle hash: problema del dizionario, funzioni hash (metodo divisione, moltiplicazione e universale), gestione delle collisioni con liste di trabocco e open addressing.
11/05/11 Laboratorio: Esercizi sugli alberi binari di ricerca. slides esercizi soluzioni
12/05/11 Laboratorio: SIMULAZIONE PROVA DI LABORATORIO. testo esercizio e istruzioni soluzione
16/05/11 Grafi: definizione, notazione, terminologia, rappresentazioni (sequenza di archi, matrice di adiacenza e liste di adiacenza). Visita BFS con analisi di complessità ed esempio.
17/05/11 Grafi: dimostrazione di correttezza della BFS. Visita DFS: algoritmo, complessità, tipologie di archi, teorema del cammino minimo. Esempio.
18/05/11 Laboratorio: Richiami sulle liste, Tabelle hash con liste di trabocco. slides esercizi soluzioni
19/05/11 Topological sort, algoritmo, complessità e dimostrazione di correttezza. Problema MST: schema algoritmico di risoluzione, correttezza, complessità. Algoritmo di Kruskal, con esempio.
24/05/11 Algoritmo di PRIM. Esempio.
25/05/11 Problema dei cammini minimi: Bellman-Ford e Dijkstra. Correttezza e complessità.
26/05/11 Laboratorio: SIMULAZIONE PROVA DI LABORATORIO. testo
30/05/11 Esercitazione in Aula A, con corso B.
31/05/11 Esercitazione sul programma della seconda parte del corso.
01/06/11 Esercitazione sul programma della seconda parte del corso.
informatica/all-a/all10/start.txt · Ultima modifica: 11/09/2015 alle 08:55 (4 anni fa) da Rossano Venturini