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 (03/05/2007)
   • 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