DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea in Matematica » Algoritmi e Strutture dei Dati » Algoritmi e Strutture dei Dati: A.A. 2018-2019
matematica:asd:asd_18:start

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
Prossima revisione 		Revisione precedente
matematica:asd:asd_18:start [12/04/2019 alle 13:42 (5 anni fa)]
Linda Pagli [Programma] 		matematica:asd:asd_18:start [22/07/2019 alle 15:13 (5 anni fa)] (versione attuale)
Linda Pagli [Date esame orale di teoria luglio 19]
Linea 2: Linea 2:
  
 Prof. Linda Pagli (teoria)\\ Prof. Linda Pagli (teoria)\\
-Prof. Roberto Grossi (lab)+Prof. Roberto Grossi (lab)\\ 
 +Dott. Giulia Punzi (supporto)
  
 {{:matematica:asd:asd_14:asd_logo.jpg?200|}} {{:matematica:asd:asd_14:asd_logo.jpg?200|}}
Linea 8: Linea 9:
 ==== Avvisi ==== ==== 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   * 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)   * 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   * Per il ricevimento, consultare la homepage dei docenti
   * Nota: il contenuto di questa pagina è preliminare   * Nota: il contenuto di questa pagina è preliminare
-  * **OGGI la lezione é soppressa**. La lezione si terrà  lun 8, 16:00-18.00 (Fib E1) 
 ==== Motivazioni ==== ==== Motivazioni ====
  
Linea 47: Linea 48:
  
  
 +==== 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 ==== ==== Testi e materiale didattico ====
  
Linea 66: Linea 72:
 |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] | |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] | |28.02.2019| Le notazioni asintotiche, O, Omega e Teta. Problema del segmento di somma massima. |[CGGR, cap.0, par.6,7] |
-|28.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] |+|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] |  |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]]  | |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]]  |
Linea 76: Linea 82:
 |21.03.2019| Laboratorio: selezione del k-esimo elemento in un array. | [[http://carp.di.unipi.it/asd1819/#/task/kmin_dup/statement|lab]]  | |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]. |  |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]. | 
-|22.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]. | +|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]]  | |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.]. |  |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.]. | 
Linea 83: Linea 89:
 |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] |  |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] |  |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] |  |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}} |
matematica/asd/asd_18/start.1555076579.txt.gz · Ultima modifica: 12/04/2019 alle 13:42 (5 anni fa) da Linda Pagli

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki