Strumenti Utente

Strumenti Sito


matematica:asd:asd_17:start

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

Prof. Roberto Grossi
Luca Versari

Avvisi

  • Lezioni del 9 e 16 maggio cancellate per consentire agli studenti di seguire un altro corso.
  • Orario lezioni: mar 11-13, mer 14-16, ven 14-16.
  • Per il ricevimento, consultare la homepage del docente.
  • Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento
  • Mesi consigliati per consegnare il progetto e completare l'orale: gennaio, febbraio, marzo, giugno, luglio, settembre, ottobre.
  • Immagini usate durante la lezione.
  • Visualizzazioni in HTML5 mostrate a lezione.
  • Per il ricevimento, consultare la 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.
  • Sviluppo di un progetto basato su “real-world data”.

Modalità d'esame

  • Parte prima, a scelta una delle seguenti possibilità:
    • [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] 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] 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].
  • 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 (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
27.02.2018 Presentazione del corso. Complessità di un algoritmo e di un problema nel modello di calcolo RAM (random access machine): esempio del segmento di somma massima. Problema dell'ordinamento: selection sort, insertion sort. [CGGR, cap.0, par.1.2,]
28.03.2018 Laboratorio: segmento di somma massima http://carp.di.unipi.it/asd1718/#/task/sum_dup/statement http://carp.di.unipi.it/asd1718/#/task/maxsum_dup/statement
02.03.2018 Problema dell'ordinamento: limite inferiore per il problema dell'ordinamento mediante confronti, mergesort, albero di ricorsione, algoritmi randomizzati (quick sort) e analisi con variabili indicatrici. [CGGR, par.5.1], [CLRS,par. 7.3]
06.03.2018 Problema dell'ordinamento: selection sort, insertion sort, limite inferiore per il problema dell'ordinamento mediante confronti. [CGGR, par.1.2, teorema 2.4, par.3.1-3.4]
07.03.2018 Laboratorio: ordinamento e problemi collegati (parte I). http://carp.di.unipi.it/asd1718/#/task/kmin/statement http://carp.di.unipi.it/asd1718/#/task/sort_dup/statement http://carp.di.unipi.it/asd1718/#/task/inversions/statement
09.03.2018 Heap binario implicito. Heapsort. [CGGR par. 2.4, 3.6, 3.7]
13.03.2018 Divide et impera, relazioni di ricorrenza e teorema principale: ricerca binaria, moltiplicazione veloce tra matrici; coppia di punti più vicini. [CGGR, par.3.6, 3.7]
14.03.2018 Laboratorio: ordinamento e problemi collegati (parte II). http://carp.di.unipi.it/asd1718/#/task/kmin/statement http://carp.di.unipi.it/asd1718/#/task/sort_dup/statement http://carp.di.unipi.it/asd1718/#/task/inversions/statement
16.03.2018 Divide et impera su alberi: problemi decomponibili. Visita di alberi. Ricerca binaria e albero binario di ricerca corrispondente. Alberi binari di ricerca: ricerca, inserimento, cancellazione. [CGGR par. 4.4.1]
20.03.2018 Il problema del dizionario: realizzazione mediante array, liste e alberi binari di ricerca. Alberi binari di ricerca AVL: ricerca, inserimento, cancellazione. [CGGR, par. 4.1, 4.4.2]
21.03.2018 Laboratorio: alberi binari di ricerca http://carp.di.unipi.it/asd1718/#/task/bst_dup/statement
23.03.2018 Discussione dettagliata del codice per gli alberi binari di ricerca AVL. [CGGR, par. 4.1, 4.4.2]
27.03.2018 Funzioni hash e tabelle hash con liste concatenate e indirizzamento aperto [CGGR, par. 4.3]
28.03.2018 Hash universale e hash perfetto CLRS par. 11.3.3 CLRS par. 11.5
06.04.2018 Cuckoo hashing. Notes Note in inglese
10.04.2018 Skip list. Karp-Rabin fingerprint e string matching. [CGGR, par. 5.2] [CLRS par.32.2]
11.04.2018 Laboratorio: hashing (parte I) http://carp.di.unipi.it/asd1718/#/task/hash_dup/statement
13.04.2018 Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. Visita in profondità (DFS) di un grafo, cicli, e ordinamento topologico. [CGGR, par. 7.1, 7.2.1]
17.04.2018 Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. Grafi pesati e cammini minimi. Algoritmo di Dijkstra. CGGR, par. 7.3.1, 7.4]
18.04.2018 Laboratorio: hashing (parte II) http://carp.di.unipi.it/asd1718/#/task/hash_dup/statement
20.04.2018 Algoritmo di Floyd-Warshall. Albero di ricoprimento minimo (MST): regola del ciclo e del taglio. Algoritmo di Jarnik-Prim mediante heap. [CGGR, par. 7.5.1-7.5.2]
24.04.2018 Programmazione dinamica. Fibonacci e sottosequenza comune più lunga. Zaino (knapsack). Problemi pseudo-polinomiali. [CGGR, par. 6.1, 6.3-6.5]
27.04.2018 Algoritmo di Kruskal per MST con struttura di dati per union-find e analisi ammortizzata. [CGGR, par. 5.3, 7.5.3]
02.05.2018 Laboratorio: grafi http://carp.di.unipi.it/asd1718/#/task/graph_dup/statement http://carp.di.unipi.it/asd1718/#/task/diameter_dup/statement
04.05.2018 Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi, colorazione di mappe (grafi) planari. Nozione di certificato polinomiale. Definizione della classe NP. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). [CGGR, par. 8.1-8.3] video
08.05.2018 Relazione tra certificato polinomiale e non-determinismo polinomiale. Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da 3-colorazione di mappe (3-COL) a SAT. [CGGR, par. 8.4-8.6]
11.05.2018 Riduzioni a la Karp: da SAT a soddisfacibilità con clausole a 3 letterali (3-SAT), da vertex cover (VC) a 3-SAT, da independent set (IS) a VC, da hitting set (HS) a VC. Algoritmi di r-approssimazione. [CGGR, par. 8.8-8.9]
15.05.2018 2-approssimazione per min VC e max SAT. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. [CGGR, par. 8.10-8.11] [TBA]
18.05.2018 Algoritmi esatti parametrizzati. [TBA]
23.05.2018 Esercitazione: grafi e discussione progetto http://carp.di.unipi.it/asd1718/#/task/dijkstra/statement
matematica/asd/asd_17/start.txt · Ultima modifica: 16/05/2018 alle 08:18 (10 giorni fa) da Roberto Grossi