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. 2018-2019 ======

Prof. Linda Pagli (teoria)\\
Prof. Roberto Grossi (lab)\\
Dott. Giulia Punzi (supporto)

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

==== Avvisi ====

  * Sono disponibili il [[progetto_18|[progetto]]] e il [[mini_progetto_18|[mini-progetto]]] del corso.
  * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento
  * Orario lezioni: mar 14:00‑16:00 (Fib E1), gio 9:00‑11:00 (Fib M-Lab), ven 14:00‑16:00 (Fib E1)
  * Per il ricevimento, consultare la homepage dei docenti
  * Nota: il contenuto di questa pagina è preliminare
==== 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_18|[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_progetto_18|[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_18|[mini-progetto]]] con votazione booleana (vedi sopra);
  * Parte seconda, comune per tutti: verifica tramite l'orale basato sul programma dettagliato (vedi sotto).


==== Date esame orale di teoria luglio 2019 ====

   * lunedì 15 ore 11.30 ufficio Pagli (studio 277 Dipartimento di informatica)
   * martedì 23 ore 10 ufficio Pagli 
   * lunedì 29 ore 11 ufficio Pagli  
==== 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]]. 


[[https://unimap.unipi.it/registri/printregistriNEW.php?re=3293423::::&ri=3410|Registro delle lezioni]]


^ Data ^ Argomento ^ Riferimenti e note ^
|26.02.2019| Presentazione del corso. Complessità di un algoritmo e di un problema nel modello di calcolo RAM (random access machine): esempio della moltiplicazione egizia. | [CGGR, cap.0, par.1.2] |
|28.02.2019| Le notazioni asintotiche, O, Omega e Teta. Problema del segmento di somma massima. |[CGGR, cap.0, par.6,7] |
|29.02.2019|Il problema del Sorting: SelectionSort, InsertionSort, Definizione e analisi. Paradigma del Divide et Impera e MergeSort. Analisi di mergeSort con equazione di ricorrenza risolta col metodo iterativo. |[CGGR, cap.1, par.1.2.1 e 1.2.2. Cap 3, par.3.1] |
|05.03.2019| Algoritmi randomizzati e variabili indicatrici: The hiring problem e permutazioni random. Quicksort randomizzato (analisi con variabili indicatrici).| [CLRS 5.1-5.3, 7.3] | 
|07.03.2019| Laboratorio: Insertion sort and quick sort randomizzato: soluzione ibrida con le due. | [[https://www.dropbox.com/sh/ker68qbw3i1l40b/AAA9NtC_ntA3KTByWKfbk0vaa?dl=0|codice]]  |
|08.03.2019| Limite inferiore per il problema del Sorting con la tecnica dell'albero di decisione. Eventi contabili: il problema del massimo. Il problema del primo e secondo, algoritmo del doppio torneo. | [CGGR pag.56.][[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori.  | 
|11.03.2019| Limite inferiore al problema del primo e secondo con la tecnica dell'oracolo. Code, code con priorità, Heap definizione, operazioni Enqueue e Dequeue. Un algoritmo ottimo di ordinamento: HeapSort| [CGGR 2.3, 2.4]. | 
|14.03.2019| Laboratorio: calcolo veloce del numero di inversioni in un array. | [[http://carp.di.unipi.it/asd1819/#/task/inversions_dup/statement|lab]]  |
|15.03.2019| Tecniche per la soluzione di equazioni di ricorrenza: sostituzione, albero di ricorsione, metodo dell'esperto.  Moltiplicazione rapida di due interi.| [CLRS 4.3, 4.4, 4.5; CGGR 3.5]. | 
|19.03.2019|  Algoritmo di Strassen per il prodotto di matrici. Ricerca Binaria iterativa e ricorsiva. Coppia di punti più vicini.| [ CGGR 3.3 e 3.7]. | 
|21.03.2019| Laboratorio: selezione del k-esimo elemento in un array. | [[http://carp.di.unipi.it/asd1819/#/task/kmin_dup/statement|lab]]  |
|22.03.2019|Alberi definizioni e proprietà. Alberi binari: rappresentazione in memoria, algoritmi ricorsivi di tipo Divide et Impera, Visite e applicazioni. Trasformazione da alberi ordinati a alberi binari.| [ CGGR da 3.8 a fine capitolo]. | 
|25.03.2019|Alberi binari di ricerca, operazioni di ricerca, inserzione, predecessore e successore, cancellazione e ordinamento. Alberi AVL, altezza nel caso pessimo, rotazioni.| [ CGGR par. 4.4]. | 
|28.03.2019| Laboratorio: altezza di un albero binario. | [[http://carp.di.unipi.it/asd1819/#/task/height_dup_dup/statement|lab]]  |
|29.03.2019|Tabelle Hash per implementare dizionari. Funzioni hash metodi di gestione delle collisioni. Liste di trabocco. Scansione lineare. Tempo medio di ricerca.| [ CGGR par. 4.1-4.3 fino al teorema 4.2.]. | 
|02.04.2019|Tabelle Hash. Scansione quadratica e doppio hash. Esempi. Il problema della cancellazione. Algoritmo di cancellazione per scansione lineare. | [ CGGR par. 4.3] {{:informatica:all-b:hash.pdf|Tabelle hash (Note di F.Luccio)}}| 
|04.04.2019| Laboratorio: operazioni di costruzione, ricerca e inserimento in un albero binario di ricerca. | [[http://carp.di.unipi.it/asd1819/#/task/bst_dup_dup/statement|lab]]  |
|08.04.2019| Grafi, terminologia, definizioni, rappresentazione in memoria, visita in ampiezza| [ CGGR par. 7.1,7.2.1 escluso codice 71. fino a pagina 222] | 
|09.04.2019| Cammini minimi su albero BSF, BSF-Explore, DFS ricorsiva e Ordinamento Topologico| [ CGGR par. 7.2.2 e 7.3] | 
|11.04.2019| Laboratorio: operazioni di range query (con priorità) in un albero binario di ricerca. | [[http://carp.di.unipi.it/asd1819/#/task/pbst/statement|lab]]  |
|12.04.2019| Algoritmo di Dijkstra, introduzione al problema del Minimal Spanning Tree| [ CGGR par. 7.4.1 e 7.4.2, 7.5 e 7.5.1] | 
|30.04.2019| Hash universale e hash perfetto | {{ :matematica:asd:asd_17:clrsuniversalhash.pdf | CLRS par. 11.3.3}} {{ :matematica:asd:asd_17:clrsperfecthash.pdf | CLRS par. 11.5}} |
|02.05.2019| Laboratorio: visita di grafi e diametro (parte I)| [[http://carp.di.unipi.it/asd1819/#/task/diameter_dup_dup/statement|lab]]  |
|03.05.2019| Cuckoo hashing.| {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Note in inglese}} |
|07.05.2019| Problema del Minimal Spanning Tree: algoritmo di Kruskal e algoritmo di Jarnik-Prim| [ CGGR par. 7.5] | 
|09.05.2019| Laboratorio: visita di grafi e diametro (parte II)| [[http://carp.di.unipi.it/asd1819/#/task/diameter_dup_dup/statement|lab]]  |
|10.05.2019| Paradigma della programmazione dinamica, numeri di Fibonacci, problema della Longest Common Subsequence, ricostruzione della sequenza| [ CGGR cap 6, fino a 6.3] | 
|14.05.2019| Paradigma della programmazione dinamica: ottimalità della sotto-struttura per LCS, Edit Distance e Zaino. Pseudopo-polinomialità| [ CGGR par.6.5, 6.8, CLRS pag.325 , [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note di F.
 Luccio]] ] | 
|16.05.2019| Laboratorio: rappresentazione dei grafi in memoria in C++ e presentazione progetto di esame| {{ :matematica:asd:asd_18:grafi.zip |codice }} {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |
|17.05.2019|GeneraBinarie e GeneraPermutazioni. Algoritmi Greedy per lo Zaino frazionato. Algoritmi enumerativi per lo Zaino0-1 e per il ciclo Hamiltoniano di un grafo. Verifica polinomiale. Classi P e NP | [ CGGR par.8.1, 8.2,   CLRS pag.885] |
|21.05.2019| Laboratorio: discussione del progetto in aula. | {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |
|23.05.2019| Laboratorio: creazione grafo di de Bruijn. | {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |
|24.05.2019| Riduzione polinomiale. Problemi NP-completi. Teorema di Cook-Levin, enunciato. Problemi aperti. Problemi NP-hard. Tecnica di restrizione.| [ CGGR par.8.3, 8.4, 8.5, 8.6, 8.7] |
|28.05.2019| Esempi di dimostrazioni di NP-completezza. Tecnica di similitudine , tecnica del gadget. Algoritmi di approssimazione. Algoritmi 2-approssimati per Vertex Cover e TSP, dimostrazioni.| [ CGGR par.8.8, 8.10, 8.11. CLRS pag.926-927] |
|30.05.2019| Question time sul progetto. | {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |