Algoritmi e Strutture dei Dati

Materiale Didattico

Testo consigliato: P. Crescenzi, G. Gambosi e R. Grossi, Strutture di dati e algoritmi, Pearson – Addison Wesley, 2006

Contenuti del Corso

Problemi Computazionali
Array e liste
Alberi e grafi
Dizionari
Pile e code
NP-completezza

Sommario delle lezioni

[[Introduzione al Corso]http://sbrinz.di.unipi.it/~peppe/MaterialeCorsi/CorsoAlgStrDati/] (26/04/2007)
Problemi Computazionali (26/04/2007)
- Problemi decidibili e indecidibili
- Problemi trattabili e intrattabili
- Problemi NP-completi
- Modello RAM e complessità computazionale (03/05/2007)
Sequenze
- Sequenze lineari: array e liste
- Algoritmi di Ordinamento
  - Selection Sort
  - Insertion Sort
- Complessità dei problemi conputazionali
  - Ricerca del Segmento di Somma Massima
- Ricerca binaria (08/05/2007)
  - Limite inferiore della ricerca per confronti
- Ricorsione e Paradigma del Divide et Impera
  - Equazioni di ricorrenza e teorema fondamentale
  - Mergesort
  - Quicksort, Quicksort randomizzato e analisi del caso medio
- Moltiplicazione Veloce di due Matrici (10/05/2007)
- Paradigma della Programmazione Dinamica
  - Fibonacci
  - Moltiplicazione di n matrici: ricerca della sequenza ottima
  - Partizione di un insieme di interi (15/05/2007)
  - Il problema dello Zaino
Didattica della ricorsione
Sequenze: Le Liste (17/05/2007)
- Inserimento e Cancellazione
- Problema dei Matrimoni Stabili
- Skip List e Liste Randomizzate
- Liste per Insiemi Disgiunti
- Liste ad Auto-Organizzazione (Move-To-Front)
- Cenni sull'Analisi Ammortizzata
Alberi (22/05/2007)
- Alberi Binari
- Visite (Anticipata, Posticipata, Simmetrica)
- Minimo Antenato Comune e Range-Min Query
- Memorizzazione Implicita e Succinta e Visita per Ampiezza
- Alberi k-ari e Ordinali (24/05/2007)
Dizionari
- Liste e Dizionari
- Tabelle Hash
- Gestione delle Collisioni
- Alberi Binari di Ricerca
- AVL: Alberi Binari di Ricerca Bilanciati (29/05/2007)
- Liste Invertite
- Trie e Trie Compatti
Grafi (31/05/2007)
- Rappresentazione dei Grafi (Matrice e Lista)
- Chiusura Transitiva
- Colorazione dei Grafi
- Modelli di Reti Complesse
- Motori di Ricerca e Classificazione (14/06/2007)
Code e Pile
- Realizzazione tramite array e liste
- Notazione polacca inversa e pile
- Visite su Grafo mediante Coda (ampiezza)
- Visite su Grafo mediante Pila (profondita')

Indicazioni per la prova finale

La prova finale (relazione o relazione + presentazione) ha come obiettivo quello della preparazione di una lezione (o serie di lezioni) in cui viene presentato uno degli argomenti trattati durante il corso. Due sono le opzioni disponibili.

OPZIONE 1

L’esame consiste in una relazione scritta di 5/6 pagine ca. e in un frammento di lezione alla lavagna di 20 minuti ca. La relazione deve contenere:

Tipologia della classe a cui e' diretta la lezione
In quale corso di studi si colloca la lezione
Collocazione della lezione nell’ambito del modulo di Algoritmi e Strutture Dati:
- Quali lezioni vengono fatte prima
- Quali lezioni vengono fatte dopo
Prerequisiti
Obiettivi formativi della lezione:
- Perché viene presentata
- Cosa ci si aspetta che gli studenti imparino ….
Descrizione dettagliata degli argomenti presentati durante la lezione (con relativi tempi)
Descrizione di uno/due/tre esercizi di diversa difficoltà da presentare agli studenti per verificare l’apprendimento (un /due esercizio da fare in classe durante la lezione e un esercizio da assegnare a casa)
- Spiegare di ogni esercizio le finalità
Identificazione dei punti di criticità della lezione

La lezione di 20/25 minuti deve vertere su un argomento presentato nella relazione. Deve svolgersi in questo modo:

  * Breve descrizione dei prerequisiti, della collocazione e degli obiettivi (5 minuti)
  * Lezione teorica (15 minuti)
  * Spiegazione e/o soluzione dell’esercizio (5 minuti)

Nei limiti del possibile la lezione deve essere autocontenuta.

OPZIONE 2

Preparazione di un sottomodulo composto di più lezioni. L’esame consiste in una relazione scritta di 15 pagine ca. La relazione deve contenere:

In quale corso di studi si colloca il sottomodulo
Collocazione del sottomodulo nell’ambito del modulo di Algoritmi e Strutture Dati:
- Quali lezioni vengono fatte prima
- Quali lezioni vengono fatte dopo
- Motivazioni sulla durata del sottomodulo/proporzioni con l’intero modulo di sistemi
Prerequisiti
Obiettivi formativi del modulo
- Perché viene presentata
- Cosa ci si aspetta che gli studenti imparino ….
Descrizione delle lezioni. Per ogni lezione:
- Argomenti presentati
- Tempi da dedicare ai singoli argomenti
- Descrizione di uno/due esercizi di diversa difficoltà da presentare agli studenti per verificare l’apprendimento (un esercizio da fare in classe e un esercizio da assegnare a casa)
  - Spiegare di ogni esercizio le finalità
Identificazione dei punti di criticità del sottomodulo

La relazione deve essere consegnata per e-mail ([email protected]) entro il 7 Settembre Il docente si riserva di richiedere revisioni/modifiche che vanno consegnate entro il 15 Settembre

Per entrambe le opzioni,

se vengono presentati algoritmi, fornire cenni sulla loro complessita' utilizzando la metedologia ritenuta piu' opportuna
se vengono presentate strutture dati, fornire esempi significativi del loro utilizzo e cenni sulla complessita' delle principali operazioni fornite sulle stesse