Algoritmi e Strutture Dati
Testo di Riferimento:
Pierluigi Crescenzi, Giorgio Gambosi, Roberto Grossi. "Strutture di Dati e Algoritmi", Pearson Education Addison-Wesley, 2006, ISBN 8871922735.
Programma Preliminare del Corso:
Problemi Computazionali: problemi decidibili e indecidibili, problemi trattabili e intrattabili.
Complessità di un Algoritmo: il modello RAM a costi uniformi, notazione asintotica, le classi di complessità P, NP, EXP (cenni), problemi NP-completi (cenni).
Esempi di Analisi della Complessità: algoritmi Selection Sort e Insertion Sort.
Limitazioni Superiori e Inferiori alla Complessità di un Problema Computazionale: algoritmi ottimi.
Esempi di Algoritmi Ottimi: calcolo del segmento di somma massima, ricerca sequenziale e binaria di una chiave in un array.
Paradigma Divide et Impera: definizione della tecnica.
Metodi di Soluzione di Relazioni di Ricorrenza: metodo di iterazione, metodo di sostituzione, metodo dell'albero di ricorsione, metodo del cambio di variabile, Teorema Master e sua dimostrazione.
Algoritmi Divide et Impera: moltiplicazione di interi di lunghezza arbitraria, moltiplicazioni di matrici, Merge Sort, Quick Sort.
Paradigma della Programmazione Dinamica: definizione della tecnica.
Algoritmi di Programmazione Dinamica: parentesizzazione ottima del prodotto di n matrici, sottosequenza comune di lunghezza massima, partizionamento, problema dello zaino.
Algoritmi Pseudo-Polinomiali.
Le liste.
Il Problema dei Matrimoni Stabili.
Alberi binari: visite, problemi decomponibili, soluzione efficiente in spazio al problema del minimo antenato comune.
Il Problema del Dizionario: implementazione tramite liste doppie, tabelle hash con liste di trabocco e a indirizzamento aperto, alberi binari di ricerca e alberi AVL (cenni).
Modalità d'Esame:
L'esame consiste in una prova scritta (qui potete trovare alcuni esercizi tratti dalle prove d'esame, mentre qui potete trovare le soluzioni di alcuni esercizi scelti).
Materiale del Corso: