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

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

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

==== Avvisi ====

  * È disponibile il [[progetto_19|[progetto]]] del corso, non c'è una scadenza per la consegna.
  * L'insegnamento verrà erogato in modalità didattica a distanza: occorre accedere al sito [[https://esami.unipi.it]] con le proprie credenziali di Ateneo per poter partecipare (verrà utilizzato Microsoft Teams). 
  * Orario lezioni: mar 16:00‑18:00, gio 9:00‑11:00, ven 14:00‑16:00
  * Per il ricevimento, consultare la homepage dei docenti

==== 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_19|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione binaria (passato/non passato, con eventuale nota di merito se ben fatto; non richiede la presentazione del mini-progetto).
    * ABOLITO causa corvid-19: scritto con esercizi da svolgere, avente una votazione in trentesimi, più un mini-progetto con votazione booleana (prova superata o meno per valutare le capacità programmative);
    * ABOLITO causa corvid-19: seminario basato su un argomento di ricerca nel campo dell'algoritmica, avente una votazione in trentesimi, più un 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]]. 


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


^ Data ^ Argomento ^ Riferimenti e note ^
|25.02.2020| Presentazione del corso. Analisi di un problema semiserio: il problema delle 12 monete. | [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/12monete.pdf | 12 monete]] | 
|27.02.2020| Indecidibilità di problemi computazionali | [CGGR, cap.0, par.1] | 
|03.03.2020| Modello RAM, Notazioni asintotiche, Sottosequenza di somma massima | [CGGR, cap.0, par.6-7] | 
|10.03.2020|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] {{ :matematica:asd:asd_19:lez10marzo.pdf|lavagna }}|
|12.03.2020| 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.Limite inferiore con la tecnica dell'oracolo. | [CGGR pag.56 ][[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori.  | 
|17.03.2020| 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]. {{ :matematica:asd:asd_19:eq.ricorrena.pdf | equazioni ricorrenza}}| 
|19.03.2020| QuickSort e randomization.| [CGGR 3.4; CLRS 7.3 ]  {{ :matematica:asd:asd_19:20200319.pdf | lucidi}} | 
|24.03.2020| Algoritmo di Strassen per il prodotto di matrici. Ordina 012 e 3-Partition per QuickSort | [ CGGR 3.3]. | 
|26.03.2020| Code, code con priorità, Heap definizione, operazioni Enqueue e Dequeue. Un algoritmo ottimo di ordinamento: HeapSort| [CGGR 2.3, 2.4].{{ :matematica:asd:asd_19:lezione26.pdf |lavagna}} | 
|27.03.2020| Laboratorio: presentazione degli strumenti per la didattica a distanza. Insertion Sort e generazione di un array casuale. | lab  | 
|31.03.2020| Esercizi su Heap e Heapsort |{{ :matematica:asd:asd_19:le31.pdf | lavagna}}  | 
|02.04.2020| Array di dimensione variabile. Alberi: definizioni, proprietà, alberi binari, algoritmi ricorsivi, visite, memorizzazione.| [CGGR 1.1.3, 3.8 ] | 
|03.04.2020| Laboratorio: Quicksort e sua versione ibrida con Insertion Sort. | lab  | 
|07.04.2020| Alberi binari di ricerca per le operazioni del dizionario. Definizioni, Operazioni di ricerca, inserzione, cancellazione, ordinamento, minimo, massimo,precedente e successivo| [CGGR 4.4, 4.4.1]{{ :matematica:asd:asd_19:lez7aprile.pdf |lavagna}} | 
|09.04.2020|Alberi AVL, Alberi di Fibonacci, relazione tra altezza e numero di nodi, rotazioni dopo inserzione e cancellazione| [CGGR 4.4.2 ] {{ :matematica:asd:asd_19:lez9aprile.pdf |lavagna}}| 
|21.04.2020| Tabelle hash, funzioni hash, metodi per la gestione delle collisioni: liste di trabocco, scansione lineare. Algoritmi di ricerca, inserzione e cancellazione. Problemi per la cancellazione, cancellazione virtuale| [CGGR 4.3 ]{{ :informatica:all-a:lez20aprilr.pdf |lavagna}} |
|23.04.2020| Tabelle hash, Open hash: scansione quadratica e doppio hash. Numero medio di accessi, dimostrazione. Algoritmo di cancellazione con scambio per scansione a passo 1.| [ CGGR 4.3 ]{{ :matematica:asd:asd_19:lez23aprile.pdf |lavagna}} | 
|24.04.2020| Laboratorio: calcolo del numero di inversioni in un array: algoritmo quadratico e quasi lineare basato su mergesort. | lab  | 
|28.04.2020| Introduzione alla Programmazione Dinamica. Numeri di Fibonacci. Il problema della Longest Common Subsequence.|[ CGGR 6.1, 6.2, 6.3]{{ :matematica:asd:asd_19:lez28apr.pdf |lavagna}} |
|30.04.2019| Paradigma della programmazione dinamica: ottimalità della sotto-struttura per LCS. Problemi Edit Distance e Zaino.| [ CGGR par.6.5, , CLRS pag.325 , [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note di F.
 Luccio]] ]{{ :matematica:asd:[asd_19:lez30apr.pdf |lavagna}} | 
|05.05.2019| Zaino e pseudopolinomialità. Algoritmo brute-force per Zaino, vettore caratteristico, generazione dei sottoinsiemi di un insieme. Introduzione ai grafi| [ CGGR ] 7.1, 7.2.1, {{ :matematica:asd:asd_19:lez5maggio.pdf |lavagna}}| 
|07.05.2019| Visite BFS, BFS-explore e DFS. Alberi di copertura corrispondenti. Classificazione degli archi.| [ CGGR ]  7.2.1, 7.2.2, {{ :matematica:asd:asd_19:lez7maggio.pdf |lavagna}} | 
|08.05.2020| Laboratorio: alberi binari di ricerca, operazioni di base del dizionario | lab  | 
|12/05/2020 |Grafi orientati aciclici (DAG) e ordinamento topologico. Algoritmo di Dijkstra per i cammini minimi con esempio di simulazione. |[ CGGR ]  7.3.1, 7.4, 7.4.1, 7.4.2 {{ :matematica:asd:asd_19:lez12maggio.pdf |lavagna}}|
|14/05/2020 |Grafi: Analisi Algoritmo di Dijkstra. Minimal Spanning Tree. Algoritmo di Kruskal. Set Union su liste disgiunte.  |[ CGGR ] 7.5, 7.5.1, 7.5.2, 5.3 {{ :matematica:asd:asd_19:lez14maggio.pdf |lavagna}}|. 
|15.05.2020| Laboratorio: alberi binari di ricerca, operazione di range query | lab  | 
|19/05/2020 |Il problema P e NP. Introduzione all'NP-Completezza|{{ :informatica:all-a:pvsnp.pdf |PvsNP}} |
|21/05/2020 |Riducibilità polinomiale e problemi NP-completi. Teorema di Cook-Levin (senza dimostrazione) esempi di verifica polinomiale e riduzioni|[ CGGR ] Cap 8: fino a 8.7. 8.8 cenni, {{ :matematica:asd:asd_19:lez21maggio.pdf |lavagna}} |
|22.05.2020| Laboratorio: rappresentazione di grafi e visite | lab  | 
|26.05.2020| Laboratorio: calcolo del diametro del grafo | lab  | 
|05.06.2020| Laboratorio: discussione collettiva del progetto d'esame | lab  |