Strumenti Utente

Strumenti Sito


matematica:asd:asd_14:start

Algoritmi e Strutture dei Dati: A.A. 2014-2015

Prof. Roberto Grossi
Dott. Alessio Conte (conte@di.unipi.it)

Avvisi

  • La mattina di venerdì 24 luglio sarà dedicata a chi vuole sostenere orali e/o consegnare il progetto a partire dalle ore 8:30. L'occasione successiva sarà fissata a fine agosto o inizio settembre (data da concordare con gli eventuali interessati).
  • IMPORTANTE: compilare il questionario in rete
  • Sono disponibili i testi del [progetto] e del [mini-progetto]
  • Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento.
  • Sintesi degli argomenti svolti nel [laboratorio].
  • 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
24.02.2015 Presentazione del corso. Breve ripasso del linguaggio C. [laboratorio, lez.0]
25.02.2015 Problemi indecidibili: problema della fermata di Turing. Problemi esponenziali: Torri di Hanoi. Problemi polinomiali. [CGGR, cap.0]
27.02.2015 Gestione di una coda di stampa. Insertion sort. Selection sort. Analisi di algoritmi. [CGGR, par.1.2]
03.03.2015 Segmento di somma massima [CGGR, cap.0], [laboratorio, lez.1]
04.03.2015 Quicksort (caso pessimo) e versione randomizzato (caso medio) [CGGR, par.5.1], [CLRS,par. 7.3]
06.03.2015 Heap implicito e heapsort [CGGR, par.2.4]
10.03.2015 Uso di argc, argv e memory mapped file per estrarre le parole da un testo [mmap], [laboratorio, lez.2]
11.03.2015 Complessità asintotica di un problema: limiti superiori e inferiori dell'ordinamento. Mergesort. [CGGR, par.2.4, 3.1]
15.03.2015 Paradigma divide et impera: relazioni di ricorrenza. Moltiplicazione veloce tra matrici. Coppia di punti più vicina. [CGGR, 3.1, 3.2, 3.6, 3.7]
17.03.2015 Implementazione del quicksort. [laboratorio, lez.3]
18.03.2015 Ricerca binaria. Divide et impera su alberi: problemi decomponibili. Visita di alberi. [CGGR, 1.4, 3.3, 3.8]
20.03.2015 Il problema del dizionario: realizzazione mediante array, liste e alberi binari di ricerca [CGGR, 4.1, 4.2, 4.4.1]
24.03.2015Implementazione del quicksort su stringhe. [laboratorio, lez.4]
25.03.2015 Alberi binari di ricerca bilanciati: alberi AVL [CGGR, 4.4.2]
27.03.2015 Skip list. Tabelle Hash. [CGGR, 5.2, 4.3]
31.03.2015 Laboratorio: alberi binari di ricerca [laboratorio, lez. 5]
01.04.2015 Cuckoo hashing. Note in inglese analisi insert
10.04.2015 Grafi: rappresentazione e alcune proprieta'. Grafi bipartiti e bicolorazione. [CGGR, 7.1]
14.04.2015 Laboratorio: dizionari di stringhe e ricerca binaria [laboratorio, lez. 6]
15.04.2015 Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. [CGGR, codice 8.1, 7.2.1]
17.04.2015 Visita in profondità (DFS) mediante ricorsione. Alberi BFS e DFS. DAG e ordinamento topologico. [CGGR, 7.2.2, 7.3.1]
21.04.2015 Laboratorio: word-graph in liste di adiacenza relativo al testo indicizzato nel dizionario [laboratorio, lez.7]
22.04.2015 Grafi pesati e cammini minimi. Algoritmi di Dijstra e Floyd-Warshall [CGGR, 7.4 ]
24.04.2015 Albero di ricoprimento minimo (MST): regola del ciclo e del taglio. Algoritmo di Jarnik-Prim mediante heap. [CGGR, 7.5.1, 7.5.3]
28.04.2015 Laboratorio: DFS e ricerca di cicli nei grafi [laboratorio, lez.8]
29.04.2015 MST: algoritmo di Kruskal con struttura di dati per union-find e analisi ammortizzata. [CGGR, 5.3, 7.5.2]
05.05.2015 Laboratorio: progetto d'esame [progetto]
06.05.2015 Programmazione dinamica: Fibonacci e sottosequenza comune più lunga. [CGGR, 6.1, 6.3]
08.05.2015 Programmazione dinamica: Partizione (subset sum) e zaino (knapsack). Problemi pseudo-polinomiali. [CGGR, 6.4, 6.5]
12.05.2015 Laboratorio: edit distance [laboratorio, lez.9]
13.05.2015 Laboratorio: progetto d'esame [progetto]
15.05.2015 Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi. Nozione di certificato polinomiale. [CGGR, 8.1, 8.2]
19.05.2015 Definizione della classe NP. Relazione tra certificato polinomiale e non-determinismo polinomiale. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). [CGGR, 8.3]
20.05.2015 Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da SAT a 3-colorazione di mappe (3-COL). [CGGR, 8.4, 8.5]
22.05.2015 Riduzioni a la Karp: da soddisfacibilità con clausole a 3 letterali (3-SAT) a SAT, e da 3-SAT a vertex cover (VC). Algoritmi di r-approssimazione: min VC. [CGGR, 8.6, 8.8, 8.9, 8.10]
29.05.2015 2-approssimazione per min VC. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. [CGGR, 8.10, 8.11]
matematica/asd/asd_14/start.txt · Ultima modifica: 22/07/2015 alle 05:50 (3 anni fa) da Roberto Grossi