Questa è una vecchia versione del documento!
Indice
Algoritmi e Strutture dei Dati: A.A. 2016-2017
Avvisi
- La lezione di lunedì 24.4.17 si terrà regolarmente (argomento:grafi).
- Orario lezioni: lun 11-13, mer 11-13, ven 14-16.
- IMPORTANTE: compilare il questionario in rete
- Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento
- Mesi in cui è possibile consegnare il progetto e completare l'orale: gennaio, febbraio, giugno, luglio, settembre.
- 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.
Data | Argomento | Riferimenti e note |
---|---|---|
01.03.2017 | Presentazione del corso. | - |
03.03.2017 | Didattica sospesa per assemblea degli studenti. | - |
06.03.2017 | Complessità di un algoritmo e di un problema nel modello di calcolo RAM (random access machine): esempio del segmento di somma massima. | [CGGR, cap.0] |
08.03.2017 | Laboratorio. Breve ripasso del linguaggio C, con esercizi | lab1 |
10.03.2017 | Problema dell'ordinamento: selection sort, insertion sort, limite inferiore per il problema dell'ordinamento mediante confronti. | [CGGR, par.1.2, teorema 2.4] |
13.03.2017 | Problema dell'ordinamento: quick sort, albero di ricorsione, algoritmi randomizzati (quick sort) e analisi con variabili indicatrici. | [CGGR, par.5.1], [CLRS,par. 7.3] |
15.03.2017 | Laboratorio. Insertion sort e quicksort. | lab2 |
17.03.2017 | Problema dell'ordinamento: mergesort. Divide et impera, relazioni di ricorrenza e teorema principale: quick sort; ricerca binaria (con limite inferiore per confronti). | [CGGR, par.3.1-3.4] |
20.03.2017 | Divide et impera: moltiplicazione veloce tra matrici; coppia di punti più vicini. | [CGGR, par.3.6, 3.7] |
22.03.2017 | Laboratorio. Qsort con interi e stringhe. | lab3 |
24.03.2017 | Divide et impera su alberi: problemi decomponibili. Visita di alberi. Ricerca binaria e albero binario di ricerca corrispondente. Heap binario implicito. Heapsort. | [CGGR par. 2.4, 3.6, 3.7] |
27.03.2017 | Discussione del codice per lo heapsort. Alberi binari di ricerca. | [CGGR, 2.4, 4.4.1] |
29.03.2017 | Laboratorio. Alberi binari. | lab4 |
31.03.2017 | Lezione impossibilitata a tenersi per sciopero del personale | - |
03.04.2017 | Alberi binari di ricerca: ricerca, inserimento, cancellazione. Il problema del dizionario: realizzazione mediante array, liste e alberi binari di ricerca. | [CGGR, 4.1, 4.2, 4.4.1] |
05.04.2017 | Laboratorio. Alberi binari di ricerca. | lab5 |
07.04.2017 | Alberi binari di ricerca AVL: ricerca, inserimento, cancellazione. | [CGGR, par. 4.4.2] |
10.04.2017 | Hashing e tabelle hash. Liste trabocco, indirizzamento aperto | [CGGR, par. 4.3] |
12.04.2017 | Laboratorio. Tabelle Hash. | lab6 |
19.04.2017 | Laboratorio. Strumenti per il debugging. | lab7 |
21.04.2017 | Cuckoo hashing. | Note in inglese Analisi in inglese |
24.04.2017 | Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. | [CGGR, par. 7.1] |
26.04.2017 | Laboratorio. Lettura e creazione di un grafo. | lab8 |