Anno Accademico 2011/2012
Università degli Studi di Pisa
II semestre

AVVISI

• ESAME:

  Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento.

  Per la consegna del progetto e gli orali nel mese di luglio, gli interessati sono pregati di fissare una data entro il 20.7.2012.

• Sintesi degli argomenti svolti nel laboratorio.
• Gli studenti di Fisica portano il programma ridotto per 5 crediti corrispondenti ai punti 1-5 del programma dettagliato. In alternativa, possono portare tutti e 6 i crediti, i quali possono essere riconosciuti interamente come MAT oppure 5 crediti come FIS e i rimanenti 2 come MAT.
• Gli studenti di Matematica portano il programma intero per 6 crediti corrispondenti ai punti 1-9 del programma dettagliato.
• Per il ricevimento, consultare la mia homepage.

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

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).
• 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.

MODALITÀ D'ESAME

• Parte prima, a scelta una delle seguenti possibilità:
  1. 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);
  2. 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);
  3. 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 1 (tutto), Capitolo 2 (tranne il paragrafo 2.6), Capitolo 3 (tranne i paragrafi 3.2, 3.4.3), Capitolo 4 (tranne i paragrafi 4.2.2, 4.3.2, 4.3.3, 4.3.4, 4.4), Capitolo 5 (tranne i paragrafi 5.5 e 5.6.2), Capitolo 6 (solo i paragrafi 6.1 e 6.2.3), Capitolo 7 (tranne i paragrafi 7.2 e 7.5.2), Capitolo 8 (tutto), Capitolo 9 (tutto). Guardare l'errata e le integrazioni sul sito Web e guardare gli esempi utilizzando ALVIE. Dispense del prof. P. Crescenzi e capitolo 2 del testo Ausiello et al. (in fondo a questa pagina, nella sezione "Materiale Integrativo"). Gli studenti di Fisica portano solo la parte relativa ai Capitoli 1--5.

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, grafi, pile, code, code di priorità e dizionari. Problemi P, NP, NP-completi e approssimazione.

PROGRAMMA

Registro delle lezioni disponibile in linea ed elenco delle attività di laboratorio in fondo a questa pagina (NOTA - studenti di Fisica: prime 25 lezioni per 5 crediti corrispondenti ai punti 1-5 sotto; studenti di Matematica: tutte le 35 lezioni per 6 crediti corrispondenti ai punti 1-9 sotto).

Registro delle attività laboratorio.

1. Problemi computazionali. Indecibilità di problemi computazionali - Trattabilità di problemi computazionali (rappresentazione e dimensione dei dati, algoritmi polinomiali ed esponenziali) - Problemi NP-completi - Modello RAM e complessità computazionale.
2. Sequenze: array. Sequenze lineari: modalità di accesso e allocazione della memoria, array di dimensione variabile - Opus: scheduling della CPU (ordinamento per selezione e per inserimento) - Complessità di problemi computazionali (limiti superiori e inferiori) - Ricerca di una chiave (ricerca binaria) - Ricorsione e paradigma del divide et impera (moltiplicazione veloce di numeri, ordinamento per fusione, ordinamento e selezione per distribuzione) - Alternativa al teorema fondamentale delle ricorrenze - Opus: array a più dimensioni e matrici nella grafica (moltiplicazione veloce, sequenza ottima di moltiplicazioni) - Paradigma della programmazione dinamica (sottosequenza comune più lunga, partizione di un insieme di interi, problema della bisaccia, pseudo-polinomialità).
3. Sequenze: liste. Liste (ricerca, inserimento e cancellazione, liste doppie e liste circolari) - Opus: problema dei matrimoni stabili - Liste randomizzate. - Liste ad auto-organizzazione - Tecniche di analisi ammortizzata.
4. Alberi. Alberi binari (algoritmi ricorsivi, inserimento e cancellazione) - Opus: minimo antenato comune - Visita per ampiezza: rappresentazione implicita e succinta (rank, select, limite inferiore sullo spazio) - Alberi cardinali, alberi ordinali e parentesi bilanciate.
5. Dizionari. Liste doppie - Tabelle hash - Alberi binari di ricerca (AVL) - Opus: trie, ricerca testuale e ordinamento di suffissi.
6. Grafi. Grafi (alcuni problemi, rappresentazione, cammini minimi e chiusura transitiva mediante moltiplicazione di matrici) - Opus: colorazione di grafi (assegnazione delle lunghezze d'onda e grafi a intervalli).
7. Pile e code. Pile (implementazione mediante array e mediante riferimenti) - Code (implementazione mediante array e mediante riferimenti) - Opus: visite di grafi (ampiezza, profondità) - Grafi diretti aciclici e ordinamento topologico.
8. Code con priorità. Code con priorità (heap e ordinamento heapsort).
9. NP-completezza. Definizione delle classi P, NP, NPC - Riduzioni polinomiali. Algoritmi di approssimazione.

TESTI E MATERIALE DIDATTICO

• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006. Sito Web ed errata-corrige (testo principale). Guardare l'errata e le integrazioni sul sito Web e guardare gli esempi utilizzando ALVIE.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, second edition, 2001. Sito Web ed errata-corrige (testo di consultazione).
• C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, 2004. Sito Web (testo di consultazione).

MATERIALE INTEGRATIVO

• Dispense del prof. P. Crescenzi: macchine di Turing, tesi di Church-Turing, teorema di Cook-Levin.
• Capitolo 2 del testo Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela e Protasi sugli algoritmi di approssimazione.
• ALVIE: ALgorithm VIsualization Environment. Istruzioni: scaricare il file e decomprimerlo; andare nella directory ALVIE e lanciare il file alvie.bat (Windows) o alvie.sh (Linux/MacOSX). Occorre aver installato Java Runtime Environment (JRE 5.0). Contattare il docente per ottenere la libreria di sviluppo per ALVIE.
• Esempi di testi di esame e di esercizi: testo, testo, testo, testo, testo, testo, testo, testo, testo, testo, testo, testo.
• Codice C utilizzato in laboratorio. Esempio di una buona funzione hash (lookup2.c). Altro codice: parsingParentesi.c e coppieLCA.c (richiedono albero.h).
• Sito con sequenze random da scaricare (in alternativa alla funzione rand): www.random.org.
• Compilatore GCC per Windows: MingW. Tabellina riassuntiva dei comandi per il debugger GDB: gdb refcard (copia cache).

MISCELLANEA

• È possibile spedirmi commenti costruttivi al fine di migliorare il corso. Collegandosi a siti come http://www.sendanonymousemail.net/ o simili viene garantito l'anonimato del mittente.