====== Algoritmi e Strutture dei Dati: A.A. 2015-2016 ======

Prof. Roberto Grossi\\
Dott. Alessio Conte (supporto)

{{:matematica:asd:asd_14:asd_logo.jpg?200|}}

==== Avvisi ====

  * Sono disponibili i dati e il testo del [[progetto_15|[progetto]]] e del [[mini_progetto15|[mini-progetto]]].
  * IMPORTANTE: compilare il [[http://www.questionario.unipi.it|questionario in rete]]
  * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento.
  * Sintesi degli argomenti svolti nel [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AAC1eKTbzekRbNux4DvgNAtja|[laboratorio]]].
  * [[https://www.dropbox.com/sh/o7hyigl7ffbbbxa/Awg3RMaGgR|Immagini usate]] durante la lezione.
  * [[http://www.di.unipi.it/~grossi/html5/|Visualizzazioni in HTML5]] mostrate a lezione.
  * Per il ricevimento, consultare la [[http://www.di.unipi.it/~grossi|homepage del docente]].

==== Motivazioni ====

//"Fino a poco tempo fa, i matematici teorici consideravano un problema risolto se esisteva un metodo conosciuto, o algoritmo, per risolverlo; il procedimento di esecuzione dell'algoritmo era di importanza secondaria.
Tuttavia, c'è una grande differenza tra il sapere che è possibile fare qualcosa e il farlo. Questo atteggiamento di indifferenza sta cambiando rapidamente, grazie ai progressi della tecnologia del computer. Adesso, è importantissimo trovare metodi di soluzione che siano pratici per il calcolo.
La teoria della complessità studia i vari algoritmi e la loro relativa effficienza computazionale. Si tratta di una teoria giovane e in pieno sviluppo, che sta motivando nuove direzioni nella matematica e nello stesso tempo trova applicazioni concrete quali quello fondamentale della sicurezza e identificazione dei dati."//

-- E. Bombieri, Medaglia Fields, in //La matematica nella società di oggi//, Bollettino UMI, Aprile 2001

==== Contenuti ====

Introduzione al modello di calcolo, all'analisi e alla complessità degli algoritmi. Algoritmi ricorsivi e relazioni di ricorrenza: divide et impera e programmazione dinamica. Strutture di dati combinatorie con applicazioni: algoritmi per array, liste, alberi, pile, code, code di priorità, dizionari, grafi. Problemi P, NP, NP-completi e approssimazione.

==== Obiettivi formativi ====

Definire formalmente le nozioni di algoritmo e di modello di calcolo caratterizzandone gli aspetti rilevanti. Organizzare e strutturare i dati da elaborare nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi. Progettare algoritmi corretti (che risolvono cioè sempre e solo il problema a cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l'esame di paradigmi diversi e problemi provenienti dal mondo reale. Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilità.

==== Prerequisiti e metodologia ====

  * Conoscenza di un linguaggio di programmazione (C, C++, C#, Java, Phyton).
  * Lezioni frontali con esercitazioni.
  * Sviluppo di codice in laboratorio.
  * Uso di strumenti di visualizzazione.
  * Sviluppo di un progetto basato su "real-world data".


==== Modalità d'esame ====

  * Parte prima, a scelta una delle seguenti possibilità:
    * [[progetto_15|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto).
    * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un [[mini_progetto15|[mini-progetto]]] con votazione booleana (prova superata o meno per valutare le capacità programmative);
    * seminario basato su un argomento di ricerca nel campo dell'algoritmica, avente una votazione in trentesimi, più un [[mini_progetto15|[mini-progetto]]] con votazione booleana (vedi sopra);
  * Parte seconda, comune per tutti: verifica tramite l'orale basato sul programma dettagliato (vedi sotto).


==== Testi e materiale didattico ====

  * P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di Dati e Algoritmi, Pearson, seconda edizione, 2012 [CGGR].
     * [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|Capitolo 0, solo versione elettronica]], [[http://tinyurl.com/d9ajvky|Errata-corrige]],[[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|Sito Web]]
  * T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
  * C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.


==== Programma ====

Capitolo 0 ([[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|versione elettronica]]), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (più [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (par.5.1, 5.2, 5.3), Capitolo 6 (par. 6.1, 6.3, 6.4, 6.5, 6.8), Capitolo 7 (tranne par. 7.3.2), Capitolo 8 (tranne par. 8.7). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]]. 


[[http://unimap.unipi.it/registri/printregistriNEW.php?re=169264::::&ri=9172|Registro delle lezioni]]

^ Data ^ Argomento ^ Riferimenti e note ^
|24.02.2016| Presentazione del corso. Breve ripasso del linguaggio C. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AAC1eKTbzekRbNux4DvgNAtja|[laboratorio, lez.0]]] |
|26.02.2016| Discussione di un problema algoritmico in classe e relative soluzioni| - |
|29.02.2015| Problemi indecidibili: problema della fermata di Turing. Problemi esponenziali: Torri di Hanoi. Problemi polinomiali. | [CGGR, cap.0]|
|02.03.2016| Segmento di somma massima | [CGGR, cap.0],  [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AAC1eKTbzekRbNux4DvgNAtja|[laboratorio, lez.1]]]|
|04.03.2016|Gestione di una coda di stampa. Insertion sort. Selection sort. Analisi di algoritmi. | [CGGR, par.1.2] |
|07.03.2016|Quicksort (caso pessimo) e versione randomizzato (caso medio) | [CGGR, par.5.1], {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|[CLRS,par. 7.3]}}|
|09.03.2016| Implementazione del quicksort. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AAC1eKTbzekRbNux4DvgNAtja|[laboratorio, lez.2]]]  |
|11.03.2016| Mergesort. Complessità asintotica di un problema: limiti superiori e inferiori dell'ordinamento. Heap implicito e heapsort | [CGGR, par.2.4, 3.1]] |
|14.03.2016| Divide et impera su alberi: problemi decomponibili. Visita di alberi. Ricerca binaria e albero binario di ricerca corrispondente. |[CGGR, par. 1.4, 3.3, 3.8] |
|16.03.2016| Algorithm engineering per il quicksort. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AAC1eKTbzekRbNux4DvgNAtja|[laboratorio, lez.3]]]  |
|18.03.2016| Discussione del codice per lo heapsort. Alberi binari di ricerca: ricerca, inserimento, cancellazione. Il problema del dizionario: realizzazione mediante array, liste e alberi binari di ricerca. Limite inferiore logaritmico per la ricerca mediante confronti. | [CGGR, 4.1, 4.2, 4.4.1] |
|21.03.2016| Alberi binari di ricerca AVL: ricerca, inserimento, cancellazione. Dizionari per stringhe: trie | [CGGR, par. 4.4.2, 4.5] |
|23.03.2016| Implementazione degli alberi binari di ricerca. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AAC1eKTbzekRbNux4DvgNAtja|[laboratorio, lez.4]]]  |
|01.04.2016| Sospensione della didattica disposta dal presidente di corso. | Elezioni studentesche |
|04.04.2016| Hashing e tabelle hash. Liste trabocco, indirizzamento aperto, cuckoo hash (prima parte) | [CGGR, par. 4.3] {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Note in inglese}} |
|06.04.2016| Semplice implementazione del cuckoo hashing | [[http://pages.di.unipi.it/grossi/ASD_LAB/06aprile2016/cuckoo_simple.c |[laboratorio, lez.5]]] |
|08.04.2016| Cuckoo hash (seconda parte) | {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Note in inglese}}  [[http://www.cs.toronto.edu/~wgeorge/csc265/2013/10/17/tutorial-5-cuckoo-hashing.html|analisi insert]] | 
|11.04.2016| Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. | [CGGR, par. 7.1] |
|13.04.2016| Lettura da file di un grafo e creazione della sua rappresentazione in memoria mediante liste compatte di adiacenza | [[http://pages.di.unipi.it/grossi/ASD_LAB/lettura_grafo.c|[laboratorio, lez.6]]] |
|15.04.2016| Visita in profondità (DFS) di un grafo e ordinamento topologico. | [CGGR, par. 7.2.1, 7.3.1] |
|18.04.2016| Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. | [CGGR, par. codice 8.1, 7.2.1] |
|20.04.2016| Scrittura di uno header in C/C++ per la lettura di un grafo da file | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AABWUoaJBbbMg4UtwQwvcbOaa/lezione7?dl=0|[laboratorio, lez.7a]]] |
|22.04.2016| Grafi pesati e cammini minimi. Algoritmi di Dijstra e Floyd-Warshall. Albero di ricoprimento minimo (MST): regola del ciclo e del taglio. | [CGGR, par. 7.4, 7.5.1] |
|27.04.2016| DFS, BFS e calcolo eccentricità di un grafo. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AABWUoaJBbbMg4UtwQwvcbOaa/lezione7?dl=0|[laboratorio, lez.7b]]] |
|29.04.2016| Algoritmo di Jarnik-Prim mediante heap. Algoritmo di Kruskal con struttura di dati per union-find e analisi ammortizzata. | [CGGR, par. 5.3, 7.5.2-7.5.3] |
|02.05.2016| Programmazione dinamica. Fibonacci e sottosequenza comune più lunga. Partizione (subset sum) e zaino (knapsack). Problemi pseudo-polinomiali. | [CGGR, par. 6.1, 6.3-6.5] |
|04.05.2016| Programmazione dinamica per edit distance. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AABzfJW6WqQGc1mKKGMx0fVia/lezione8?dl=0|[laboratorio, lez.8]]] |
|06.05.2016| Lezione cancellata. | Aule chiuse a causa sciopero. |
|09.05.2016| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi. Nozione di certificato polinomiale. Definizione della classe NP. Relazione tra certificato polinomiale e non-determinismo polinomiale. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, par. 8.1-8.3] [[http://9gag.com/tv/p/ayzL0v/p-vs-np-and-the-computational-complexity-zoo|video]] |
|11.05.2016| Introduzione alla struttura delle proteine per il progetto (a cura del dott. Lorenzo Tattini). Parsing dei file PDB (Protein Data Bank) | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AACaAA8CRSdsQBBx1IhhgltLa/Lezione9?dl=0|[laboratorio, lez.9]]] |
|13.05.2016| Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da SAT a 3-colorazione di mappe (3-COL). Riduzioni a la Karp: da SAT a soddisfacibilità con clausole a 3 letterali (3-SAT), e da 3-SAT a vertex cover (VC). | [CGGR, par. 8.4-8.6, 8.8-8.10] |
|16.05.2016| Algoritmi di r-approssimazione. 2-approssimazione per min VC. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] |
|18.05.2016| Discussione del progetto su PDB. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AACCdbuqtV67hoK933ZevkWMa/Lezione10?dl=0|[laboratorio, lez.10]]] |