Docente: Giuseppe Prencipe

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

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

1. [[Introduzione al Corso]http://sbrinz.di.unipi.it/~peppe/MaterialeCorsi/CorsoAlgStrDati/] (26/04/2007)
2. Problemi Computazionali (26/04/2007)
   • Problemi decidibili e indecidibili
   • Problemi trattabili e intrattabili
   • Problemi NP-completi
   • Modello RAM e complessità computazionale (03/05/2007)
3. 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
4. Didattica della ricorsione
5. 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
6. 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)
7. 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
8. 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)
9. 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')

La prova finale (relazione o relazione + presentazione) ha come obiettivo quello della preparazione di una lezione di due ore in cui viene presentato uno degli argomenti trattati durante il corso.

In particolare, per meglio contestualizzare la prova, bisogna specificare:

1. tipologia della classe a cui e' diretta la lezione
2. obiettivi generali della lezione

Inoltre,

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