Algoritmi e Strutture Dati I Corso D

Corso di Studi in INFORMATICA, Università di Pisa, Anno accademico 2000/2001
 

AVVISI
  1. Date degli orali:
    • 31-05-2001 ore 9:00 aula BETA (oppure stanza del docente)
    • 11-06-2001 ore 9:00 aula BETA
    • 06-07-2001 ore 9:00 aula BETA
    • 23-07-2001 ore 9:00 aula ALFA

  2. Si consiglia di guardare la versione estesa del programma.
  3. Progetto facoltativo da consegnare al momento dell'orale: alberi AVL.

Docente Prof. Roberto Grossi

Pagina Web principale  Algoritmi e Strutture Dati I

Calendario delle lezioni previste
(25 lezioni + 15 esercitazioni + 2 esercitazioni di recupero)
  Data Inizio Fine     Data Inizio Fine     Data Inizio Fine
1 12 Feb 9.00 11.00   16 8 Mar 9.00 11.00   31 10 Apr 11.00 13.00
2 13 Feb 11.00 13.00   17 12 Mar 9.00 11.00   32 11 Apr 11.00 13.00
3 14 Feb 11.00 13.00   18 13 Mar 11.00 13.00          
4 15 Feb 9.00 11.00   19 14 Mar 11.00 13.00   33 23 Apr 9.00 11.00
5 19 Feb 9.00 11.00   20 15 Mar 9.00 11.00   34 24 Apr 11.00 13.00
6 20 Feb 11.00 13.00   21 19 Mar 9.00 11.00          
7 21 Feb 11.00 13.00   22 20 Mar 11.00 13.00   35 26 Apr 9.00 11.00
8 22 Feb 9.00 11.00   23 22 Mar 9.00 11.00   36 30 Apr 9.00 11.00
9 26 Feb 9.00 11.00   24 22 Mar 16.00 18.00   37 2 Mag 11.00 13.00
10 27 Feb 11.00 13.00   25 29 Mar 9.00 10.00   38 3 Mag 9.00 11.00
11 28 Feb 11.00 13.00   26 2 Apr 9.00 11.00   39 7 Mag 9.00 11.00
12 1 Mar 9.00 11.00   27 3 Apr 11.00 13.00   40 8 Mag 11.00 13.00
13 5 Mar 9.00 11.00   28 4 Apr 11.00 13.00   41 9 Mag 11.00 13.00
14 6 Mar 11.00 13.00   29 5 Apr 9.00 11.00   42 10 Mag 9.00 11.00
15 7 Mar 11.00 13.00   30 9 Apr 9.00 11.00          

Calendario dei ricevimenti durante il semestre
(3 ore a settimana)
  Data Inizio Fine     Data Inizio Fine     Data Inizio Fine
1 12 Feb 14.30 17.30   5 12 Mar 14.30 17.30   9 23 Apr 14.30 17.30
2 19 Feb 14.30 17.30   6 19 Mar 14.30 17.30   10 30 Apr 14.30 17.30
3 26 Feb 14.30 17.30   7 2 Apr 16:30 17.30   11 7 Mag 14.30 17.30
4 5 Mar 14.30 17.30   8 9 Apr 14.30 17.30   12 14 Mag 14.30 17.30

Il ricevimento si svolge nella stanza del docente, oppure in aula ALFA/BETA, in Corso Italia 40, su richiesta. È fortemente consigliato agli studenti che abbiano evidente difficoltà nel seguire le lezioni.  In tal caso, il docente ripeterà i concetti principali delle lezioni da lui tenute nella settimana corrente.


Contenuti di massima delle lezioni
[premere qui per una versione estesa]

Problemi, algoritmi e complessità.

  1. Presentazione del corso e dei suoi prerequisiti.
  2. Prerequisiti e analisi asintotica delle funzioni.
  3. Esercitazioni.
  4. Formalizzazione di problemi, dati e algoritmi. Ordinamento e Insertion Sort.
  5. Modello di calcolo RAM. Complessità asintotica di un problema e di un algoritmo. Caso ottimo, caso medio e caso pessimo.
  6. Esercitazioni.
  7. Ricorsione: sua interpretazione mediante induzione e sua realizzazione mediante pila.
  8. Algoritmi divide et impera (1): Calcolo del massimo in un vettore. Primo e secondo elemento in un vettore. Ricerca binaria in un vettore ordinato.
  9. Algoritmi divide et impera (2): Equazioni di ricorrenza e teorema principale. Analisi degli algoritmi divide et impera.
  10. Algoritmi divide et impera (3): Applicazioni del teorema principale. MergeSort.
  11. Algoritmi divide et impera (4): Moltiplicazione veloce di polinomi. Generazione delle permutazioni e delle sequenze binarie.
  12. Esercitazioni.

Ordinamento e selezione.

  1. Heap e HeapSort.
  2. Esercitazioni.
  3. QuickSort.
  4. Tecniche di base per i limiti inferiori. Limite inferiore all'ordinamento per confronti.
  5. Mediano e k-esimo elemento.
  6. Counting Sort e Radix Sort (lezione svolta il 14/3).

Strutture di dati e algoritmi di ricerca.

  1. Strutture informative di base (I): pile, code e liste.
  2. Esercitazioni.
  3. Dizionari. Tabelle hash (1): liste concatenate.
  4. Tabelle hash (2): indirizzamento aperto.
  5. Esercitazioni
  6. Esercitazioni
  7. Discussione degli esercizi dati nella prima verifica (1 ora)
  8. Esercitazioni
  9. Strutture informative di base (II): alberi radicati.
  10. Alberi binari di ricerca.
  11. Alberi bilanciati (1): alberi AVL (prima parte).
  12. Alberi bilanciati (1): alberi AVL (seconda parte).
  13. Esercitazioni.
  14. Alberi bilanciati (2): alberi 2-3-4 e B-alberi.

Algoritmi su grafi. Intrattabilità e NP-completezza.

  1. Grafi e visite in ampiezza (BFS) e profondità (DFS).
  2. Esercitazioni.
  3. Esercitazioni.
  4. Grafi diretti aciclici (DAG) e ordinamento topologico. Algoritmi di enumerazione.
  5. Classi P e NP. Nozione di NP-completezza.
  6. Discussione di alcuni problemi NP-completi.
  7. Esercitazioni
  8. Esercitazioni
  9. Esercitazioni
  10. Esercitazioni


Programma d'esame degli anni passati