Anno Accademico 2009/2010
Università degli Studi di Pisa
II semestre

AVVISI

• NUOVO ORARIO: mar 16-18 (aula D3), gio 16-18 (lab.aula M), ven 11-13 (aula A1).
• Sintesi degli argomenti svolti a laboratorio: 4 marzo, 11 marzo
• Gli studenti di Fisica portano il programma ridotto (prime 25 lezioni) per 5 crediti corrispondenti ai punti 1-5 del programma dettagliato. In alternativa, possono portare tutti e 7 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 (35 lezioni) per 7 crediti corrispondenti ai punti 1-9 del programma dettagliato.
• Per il ricevimento, consultare la mia homepage.
• Appello del 14.07.09. Risultati:

  270601 voto 28 (5 CFU)
  401292 voto 27 (7 CFU)
  

• Appello del 18.06.09. Risultati:

  256044 voto 24 (5 CFU)
  Esercizi: 1. ok 2. occorre verificare se la ricerca ha successo 
  3bis. Le ultime chiavi non mi convincono.
  
  410525 voto 26 (7CFU)
  Esercizi: 1. ok con piccole sviste 2. occorre trasmettere il caso in
  cui la ricerca non ha successo 3. manca la fase di ricombinazione
  3bis. ok
  
  412542
  Esercizi: 1. no 2. occorre verificare se la ricerca ha successo
  3. non e' un approccio di tipo divide et impera
  
  270601
  1. no 2. manca come far salire il nodo in caso di ricerca con successo
  3bis. ok
  

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, il quale è ridotto per gli studenti di Fisica.

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 e NP-completi.

PROGRAMMA DETTAGLIATO

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 7 crediti corrispondenti ai punti 1-9 sotto).

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.

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

• Sintesi degli argomenti svolti nel laboratorio.
• Dispense del prof. P. Crescenzi: macchine di Turing, tesi di Church-Turing, teorema di Cook-Levin.
• 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.
• Codice C utilizzato in laboratorio. Esempio di una buona funzione hash (lookup2.c).
• 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).
• parsingParentesi.c e coppieLCA.c (richiedono albero.h).

MISCELLANEA

• È possibile spedirmi commenti costruttivi al fine di migliorare il corso. Collegandosi al sito http://riot.EU.org/anon/remailer-nossl.html.en viene garantito l'anonimato del mittente.