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. 2012-2013 ======

Prof. Roberto Grossi

==== Avvisi ====

  * Sono disponibili i dettagli per il [[progetto_12|[progetto]]] e il [[mini_progetto_12|[mini-progetto]]]
  * Calendario orali (contattare il docente per fissare una data specifica nel periodo indicato): 
     * fino al 31.05.2013;
     * dal 17.06.2013 al 4.07.2013;
     * dal 22.07.2013 al 31.07.2013.
  * Il docente sarà in missione di lavoro dal 2 al 7 giugno, dal 10 al 14 giugno e dal 5 al 21 luglio.
  * Aggiornata la parte seconda della sezione "Modalità di esame".
  * Sintesi degli argomenti svolti nel [[laboratorio_12|[laboratorio]]].
  * Esami: Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento.
  * 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_12|[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_12|[mini-progetto]]] con votazione booleana (vedi sopra);
    * [[progetto_12|[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 (par.4.5 facoltativo, [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (solo par.5.1 e 5.2), Capitolo 6 (saltare), Capitolo 7 (par. 7.1, 7.2, 7.3.1), Capitolo 8 (tutto tranne par. 8.7 e 8.11). 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=89101::::&ri=9172|Registro delle lezioni]]

^ Data ^ Argomento ^ Riferimenti e note ^
| 28.02.2013| Introduzione al corso, motivazioni, testi, modalità di esame. Esempio di problem solving: scheduling di lavori e ordinamento (per selezione), con analisi asintotica della complessità. | [CGGR, par.1.2,1.2.1] [[http://www.di.unipi.it/~grossi/html5/selectionSort.html|[alvie]]] | 
| 01.03.2013| Introduzione al Python (seminario del dott. Ottaviano).| [[laboratorio_12|[lab]]]| 
| 04.03.2013| Modello computazionale RAM. Complessità in tempo e spazio, dimensione di un problema computazionale, caso pessimo e caso medio, notazione asintotica. Complessità di alcuni costrutti programmativi.| [CGGR, par.0.3,0.6,0.7.1] | 
| 07.03.2013| Esempio: problema del segmento di somma massima, con analisi di complessità e correttezza. Complessità di un algoritmo e di un problema, limiti superiori e inferiori. "Fooling argument" per limiti inferiori lineari. | [CGGR, par. 0.7][[http://www.di.unipi.it/~grossi/html5/segmentSum.html|[alvie]]] | 
| 08.03.2013| Linguaggio C e Linux: passaggio di argomenti da linea di comando e generazione di array casuali di interi. Implementazione delle soluzioni per il problema del segmento di somma massima.| [[laboratorio_12|[lab]]] | 
| 11.03.2013| Limiti alla computabilità: problema della fermata di Turing. Prima classificazione di problemi in base alla loro complessità computazionale: indecibili, decidibili, esponenziali, polinomiali. Esempio di problema esponenziale: Torri di Hanoi e limiti superiori e inferiori. 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. | [CGGR, par. 0.1, 0.2, 0.4, 1.1] [[http://www.di.unipi.it/~grossi/html5/hanoiTower.html|[alvie]]][[http://www.di.unipi.it/~grossi/html5/dynamicArray.html|[alvie]]]| 
| 14.03.2013| Array di dimensione variabile: analisi ammortizzata del tempo e analisi dello spazio. Studio della complessità degli algoritmi di ordinamento per selezione e inserimento. Mergesort e relazione di ricorrenza. | [CGGR, par. 1.1, 1.2, 3.1] [[http://www.di.unipi.it/~grossi/html5/selectionSort.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/insertionSort.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/mergeSort.html|[alvie]]]| 
| 18.03.2013| Codice della fusione del mergesort e sua relazione con intersezione e unione di liste (insiemi) ordinate. Formula chiusa per l'equazione di ricorrenza del mergesort (seguirà teorema generale). Limiti superiori e inferiori per il problema dell'ordinamento mediante confronti (seguirà heapsort). Pile e code: operazioni supportate e complessità. | [CGGR, par. 2.1, 2.3, 3.1, teorema 2.4] [[http://www.di.unipi.it/~grossi/html5/stackArray.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/stackList.html|[alvie]]]| 
| 19.03.2013| Codice per l'implementazione della struttura di dati coda. | [[laboratorio_12|[lab]]] | 
| 22.03.2013| Coda con priorità: heap e operazioni supportate. Heapsort: ordinamento per confronti ottimo in tempo e spazio | [CGGR, 2.3, 2.4] [[http://www.di.unipi.it/~grossi/html5/heapArray.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/heapSort.html|[alvie]]] |
| 25.03.2013| Ricorsione e divide et impera. Mergesort, Quicksort, moltiplicazione di matrici. Relazioni di ricorrenza e teorema fondamentale di risoluzione.| [CGGR, par. 3.1, 3.2, 3.4, 3.6] [[http://www.di.unipi.it/~grossi/html5/mergeSort.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/quicksort.html|[alvie]]]| 
| 04.04.2013| Divide et impera: Coppia di punti più vicina. Esercizio: estendere il limite inferiore dell'ordinamento alla ricerca in un array ordinato. Alberi binari, cardinali e ordinali (con loro rappresentazione binarizzata). Problemi decomponibili su alberi: divide et impera per alberi, con esempi. | [CGGR, par. 3.3, 1.4, 3.8] | 
| 05.04.2013| Ricerca binaria ricorsiva: scrivere il codice ed estenderlo al caso di array ordinato con chiavi ripetute, per trovare l'occorrenza della chiave più a sinistra e quella più a destra.| [CGGR, par. 3.3] [[laboratorio_12|[lab]]] [[http://www.di.unipi.it/~grossi/html5/binarySearch.html|[alvie]]] | 
| 08.04.2013| Soluzione dell'esercizio su nodi cardine. Visite di alberi e loro uso. Alberi binari di ricerca e relazione con ricerca binaria. Operazioni di ricerca, inserimento e cancellazione in un albero binario di ricerca.  | [CGGR par. 3.8, 4.4.1] [[http://www.di.unipi.it/~grossi/html5/hingeNode.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/binaryTreePostorder.html|[alvie]]] [[http://www.di.unipi.it/~grossi/html5/binarySearchTree.html|[alvie]]] | 
| 11.04.2013| --- | [CGGR par. ]  [[http://www.di.unipi.it/~grossi/html5/avlInsert.html|[alvie]]] |