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
- Liste Invertite (29/05/2007)
- Trie e Trie Compatti
Grafi