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
-
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 binaria (08/05/2007)
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
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
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:
Prerequisiti
Obiettivi formativi della lezione:
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)
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
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)
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