Prof. Roberto Grossi

• Sono disponibili i dettagli per il [progetto] e il [mini-progetto]
• Calendario orali (contattare il docente per fissare una data specifica nel periodo indicato):
  • fino al 31.05.2013;
  • dal 17.06.2013 al 4.07.2013;
  • dal 22.07.2013 al 31.07.2013.
• Il docente sarà in missione di lavoro dal 2 al 7 giugno, dal 10 al 14 giugno e dal 5 al 21 luglio.
• Aggiornata la parte seconda della sezione “Modalità di esame”.
• Sintesi degli argomenti svolti nel [laboratorio].
• Esami: Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento.
• Per il ricevimento, consultare la homepage del docente.

“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

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.

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à.

• 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.
• Verifica tramite esercizi scritti di esame, orali e sviluppo di progetti.

• Parte prima, a scelta una delle seguenti possibilità:
  • 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);
  • [progetto] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto).
• Parte seconda, comune per tutti:
  • verifica tramite l'orale basato sul programma dettagliato: Capitolo 0 (versione elettronica), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (par.4.5 facoltativo, cuckoo hashing), Capitolo 5 (solo par.5.1 e 5.2), Capitolo 6 (saltare), Capitolo 7 (par. 7.1, 7.2, 7.3.1), Capitolo 8 (tutto tranne par. 8.7 e 8.11). Guardare errata-corrige, integrazioni ed esempi utilizzando ALVIE sul sito Web.

• P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di Dati e Algoritmi, Pearson, seconda edizione, 2012 [CGGR].
  • Capitolo 0, solo versione elettronica, Errata-corrige,Sito Web
• 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.

Registro delle lezioni