AA006 ALGORITMICA - Corso B (9 crediti)

Prof. Roberto Grossi

Anno Accademico 2003/2004
Corsi di Studio in Informatica
Università degli Studi di Pisa
II anno, I semestre, Corso B

AVVISI

• Quarto appello (22.6.04):

  DIANA    18
  FIORINI  18
  FRASSI   18
  

  Orali e verbalizzazione: venerdì 9.7.04 ore 9 presso il mio studio.

• Terzo appello (1.6.04):

  MATARESE N.   18
  

• Testo e risultati della prima verifica intermedia (4.11.2003).
• Testo, soluzione e risultati della seconda verifica intermedia (17.12.2003). Soluzione alternativa per l'esercizio 2.
• Per il ricevimento, consultare la mia homepage.

MODALITÀ DI ESAME

• L'esame consiste in una prova scritta e in una prova orale.
• Durante la prova scritta o le verifiche intermedie è vietato portare e consultare libri o appunti.
• Il superamento di entrambe le verifiche intermedie consente l'esonero dalla prova scritta per la sola sessione invernale (come da regolamento didattico).
• Vengono impostati alcuni problemi da risolvere a casa durante il semestre, per cui è possibile collaborare, cercare su libri e Internet. La seconda verifica e la prova scritta della sessione invernale possono contenere uno di tali esercizi. Questa possibilità favorisce uno studio meno impostato al mero superamento dell'esame:
  "A scuola si insegna agli scolari a non aiutarsi l'un l'altro, a non suggerire a chi non sa, a preoccuparsi solo della promozione, a conquistare un premio nella competizione con i compagni. Uomini così educati non sono preparati alla conquista della verità [...] ne' alla carità verso gli altri uomini, per associarsi con loro in una vita migliore. L'educazione ricevuta li ha preparati a quello che può considerarsi un episodio della vita collettiva reale: la guerra."
              -- M. Montessori, 1932

PROGRAMMA

Registro delle lezioni e prerequisiti matematici al corso disponibili in linea.

Analisi di Algoritmi e Complessità:

1. Introduzione alla complessità di calcolo [CLR 1]
2. Ordini di grandezza delle funzione [CLR 2]
3. Algoritmi ricorsivi: Numeri di Fibonacci, Ricerca Binaria, Mergesort, Moltiplicazione rapida, Moltiplicazione di matrici [L 5]
4. Relazioni di ricorrenza [CLR 4]
5. Limiti inferiori alla complessità [L 4.2]

Progetto di Algoritmi e Strutture dei Dati:

6. Code, Pile, Heap [CLR 7]
7. Heapsort [CLR 7]
8. Quicksort [CLR 8]
9. Ordinamento in tempo lineare [CLR 9]
10. Tabelle hash [CLR 12]
11. Alberi binari di ricerca [L]
12. Grafi: rappresentazione e visite [CLR 23]

Classi di Complessità:

14. Enumerazione e non determinismo [dispense]
15. Classi P, NP, NPC [CLR]
16. Algoritmi randomizzati [Karp-Rabin]

Modelli di Calcolo e Calcolabilità:

17. Indecidibilità e universalità [dispense]
18. Macchina di Turing [dispense]
19. Equivalenza tra modelli di calcolo [dispense]

TESTI

• [CLR] T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduzione agli algoritmi, Jackson Libri, seconda edizione, 2000 (copie in esaurimento... disponibile in biblioteca).
• [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, second edition, 2001. Sito Web ed errata-corrige.
• [L] F. Luccio, La struttura degli Algoritmi, Boringhieri 1982 (fuori catalago... disponibile in biblioteca).

MATERIALE INTEGRATIVO

• Brevi note introduttive
• Segmento di somma massima
• Moltiplicazione veloce
• Macchine di Turing + dispensa disponibile in copisteria.
• Esercizi e animazione di alcuni algoritmi

PROGRAMMA DEGLI ANNI PRECEDENTI

• Anno accademico 1997/1998
• Anno accademico 1998/1999
• Anno accademico 1999/2000
• Anno accademico 2000/2001
• Anno accademico 2001/2002

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.