Strumenti Utente

Strumenti Sito


matematica:asd:asd_18:start

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

Prof. Linda Pagli (teoria)
Prof. Roberto Grossi (lab)

Avvisi

  • 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)
  • Per il ricevimento, consultare la homepage dei docenti
  • Nota: il contenuto di questa pagina è preliminare

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
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.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].
matematica/asd/asd_18/start.txt · Ultima modifica: 22/03/2019 alle 18:01 (3 giorni fa) da Roberto Grossi