Indice

Algoritmi e Strutture dei Dati: A.A. 2018-2019

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

Avvisi

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

Modalità d'esame

Date esame orale di teoria luglio 2019

Testi e materiale didattico

Programma

Capitolo 0 (versione elettronica), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (più 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 errata-corrige, integrazioni ed esempi utilizzando ALVIE sul sito Web.

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.2019Il 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. 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.] 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. 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. lab
22.03.2019Alberi 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.2019Alberi 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. lab
29.03.2019Tabelle 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.2019Tabelle Hash. Scansione quadratica e doppio hash. Esempi. Il problema della cancellazione. Algoritmo di cancellazione per scansione lineare. [ CGGR par. 4.3] Tabelle hash (Note di F.Luccio)
04.04.2019 Laboratorio: operazioni di costruzione, ricerca e inserimento in un albero binario di ricerca. 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. 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 CLRS par. 11.3.3 CLRS par. 11.5
02.05.2019 Laboratorio: visita di grafi e diametro (parte I) lab
03.05.2019 Cuckoo hashing. Notes 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) 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 , Note di F. Luccio ]
16.05.2019 Laboratorio: rappresentazione dei grafi in memoria in C++ e presentazione progetto di esame codice lucidi
17.05.2019GeneraBinarie 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. lucidi
23.05.2019 Laboratorio: creazione grafo di de Bruijn. 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. lucidi