DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Algoritmi e Strutture dei Dati: A.A. 2013-2014 ======

Prof. Roberto Grossi

==== Avvisi ====

  * IMPORTANTE: compilare il questionario [[http://www.questionario.unipi.it|disponibile in rete]]
  * Il testo del [[progetto_13|[progetto]]] e del [[mini_progetto_13|[mini-progetto]]] è disponibile.
  * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento.
  * Sintesi degli argomenti svolti nel [[laboratorio_13|[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.
  * Verifica tramite esercizi scritti di esame, orali e sviluppo di progetti.


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

  * Parte prima, a scelta una delle seguenti possibilità:
    * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un [[mini_progetto_13|[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_progetto_13|[mini-progetto]]] con votazione booleana (vedi sopra);
    * [[progetto_13|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto).
  * Parte seconda, comune per tutti:
    * verifica tramite l'orale basato sul programma dettagliato: 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 (solo par.5.1), Capitolo 6 (par. 6.1, 6.3, 6.4, 6.5), Capitolo 7 (par. da 7.1 a 7.4), Capitolo 8 (par. da 8.1 a 8.5 più par. 8.8). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]]. 


==== 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 ====

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

^ Data ^ Argomento ^ Riferimenti e note ^
| 04.03.2014| Introduzione al corso, motivazioni, testi, modalità di esame. Esempio di problem solving:  segmento di somma massima | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.7]] |
| 07.03.2014| Scheduling di lavori e ordinamento (insertion sort, selection sort), con analisi asintotica della complessità. Complessità di un algoritmo e di un problema, limiti superiori e inferiori. "Fooling argument" per limiti inferiori lineari. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.7, par.1.2]] | 
| 07.03.2014| Segmento di somma massima | [[laboratorio_13|lab]] | 
| 11.03.2014| Strutture di dati per rappresentare le istanze dei problemi: elementari e sequenze (array e liste). Memorizzazione di array e liste e impatto sul costo di accesso. Array di dimensione variabile. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par.  0.1, 0.2, 0.4, par. 1.1]] |
| 14.03.2014| Limiti superiori e inferiori per il problema dell'ordinamento mediante confronti. Semplici esempi di algoritmi lineari (ordinare zeri e uni mediante scambi). | [CGGR, teorema 2.4] | 
| 14.03.2014| Array di dimensione variabile | [[laboratorio_13|lab]] |
| 18.03.2014| Ricorsione e divide et impera. Mergesort e Quicksort. Relazioni di ricorrenza e teorema fondamentale di risoluzione.| [CGGR, par. 3.1, 3.2, 3.4] | 
| 21.03.2014| Divide et impera: ricerca binaria e coppia di punti più vicina | [CGGR, par. 3.3 e 3.7] | 
| 21.03.2014| Realizzazione di code e pile mediante liste concatenate | [[laboratorio_13|lab]] |
| 25.03.2014| Divide et impera: coppia di punti più vicina (cont.) moltiplicazione veloce di matrici. | [CGGR, par. 3.6 e 3.7] | 
| 28.03.2014| Alberi binari: rappresentazione e problemi decomponibili. | [CGGR, par. 1.4 e 3.8] | 
| 28.03.2014| Realizzazione di un dizionario mediante liste concatenate | [[laboratorio_13|lab]] |
| 01.04.2014| Alberi binari: visite. Alberi binari di ricerca. | [CGGR, par. 3.8 e 4.4] | 
| 04.04.2014| Alberi di ricerca AVL: proprietà e algoritmi. | [CGGR, par. 4.4] | 
| 04.04.2014| Realizzazione di aberi binari di ricerca | [[laboratorio_13|lab]] |
| 08.04.2014| Tabelle hash | [CGGR, par. 4.3] |
| 11.04.2014| Dizionari per stringhe: trie | [CGGR, par. 4.5] |
| 11.04.2014| Realizzazione di trie | [[laboratorio_13|lab]] |
| 15.04.2014| Nozione di casualità e complessità di Kolomogorov. Problemi decidibili e indecidibili: problema della fermata; problema di stabilire la complessità di Kolmogorov di una sequenza binaria.  | [[http://cs.stanford.edu/people/trevisan/cs172/notek.pdf|Note]] [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.1]] |
| 29.04.2014| Cuckoo hashing. Quicksort randomizzato: analisi con relazioni di ricorrenza. | [CGGR, par. 5.1] {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Note}} |
| 02.05.2014| Quicksort randomizzato: analisi con variabili indicatrici. Hash universale. | {{:magistraleinformatica:alg2:algo2_13:randqs.pdf|par. 7.3}}  {{:matematica:asd:asd_13:clrs_universal_hashing.pdf|par 11.3.3}}|
| 02.05.2014| Realizzazione del cuckoo hashing. | [[laboratorio_13|lab]] |
| 06.05.2014| Programmazione dinamica | [CGGR, par.6.1,6.3,6.4,6.5] |
| 09.05.2014| Rappresentazione e visita di grafi | [ [CGGR, par.7.1-7.3] |
| 09.05.2014| Esempi di programmazione dinamica | [[laboratorio_13|lab]] |
| 13.05.2014| Cammini minimi e algoritmo di Dijkstra. Pesi negativi: algoritmi di Bellman-Ford e Floyd-Warshall.| [CGGR, par.7.4] |
| 16.05.2014| Cammini euleriani e hamiltoniani. Classi di complessità P e NP. Colorazioni di grafi. Problema della soddisfacibilità (SAT). Riduzioni polinomiali e teorema di Cook-Levin (senza dimostrazione). | [CGGR, par. 8.1-8.5] |
| 16.05.2014| Generazione di grafi e visita in ampiezza | [[laboratorio_13|lab]] |
| 20.05.2014| Riduzione da 3-colorazione di mappe a SAT. Karp: riduzione da SAT a 3-SAT, e da 3-SAT a vertex cover (VC). | [CGGR, par. 8.1-8.5, 8.8]  |
| 23.05.2014| sospensione della didattica | elezioni |
| 23.05.2014| sospensione della didattica | elezioni |