Indice
Algoritmi e Strutture dei Dati
Docente: Giuseppe Prencipe
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 (prencipe@di.unipi.it) 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