Si richiede che lo studente abbia ben metabolizzato un linguaggio di programmazione e i concetti di astrazione funzionale e programmazione ricorsiva; e che sia in grado di dar vita a dei, sia pur semplici, processi di problem solving. E’ inoltre auspicabile una certa familiarità con discipline formali come l'algebra, la geometria, l'analisi matematica e il calcolo delle probabilità e, in particolar modo, con argomenti come la logica proposizionale, le dimostrazioni per induzione e per assurdo, gli insiemi numerabili, le matrici, il valore atteso di una variabile aleatoria.

Il corso di Algoritmi e Strutture Dati è rivolto a quegli studenti che, avendo già acquisito una buona padronanza di un linguaggio di programmazione, vogliano espandere le loro conoscenze sulla progettazione avanzata di soluzioni algoritmiche per problemi computazionali.

Conoscenze e comprensione: conoscere gli strumenti teorici alla base dell’analisi e progettazione di algoritmi.

Capacità di applicare conoscenze e comprensione: essere in grado di progettare algoritmi efficienti per problemi computazionali avanzati.

Autonomia di giudizio: essere in grado di valutare, tra le molteplici soluzioni possibili di un dato problema, quelle migliori o che meglio soddisfino certi requisiti.

Abilità comunicative: saranno illustrati strumenti teorici atti a comprendere e comunicare problematiche, modelli e soluzioni tipici dell’area della Teoria degli Algoritmi e della Complessità Computazionale.

Capacità di apprendimento: gli studenti saranno stimolati a implementare le soluzioni proposte durante le lezioni.

Lezioni teoriche frontali corredate da vari esercizi.

Prova scritta volta ad accertare non solo la conoscenza degli strumenti teorici illustrati durante il corso, ma anche la capacità del candidato di risolvere, in maniera efficiente, problemi computazionali.

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).

Pierluigi Crescenzi, Giorgio Gambosi, Roberto Grossi, “Strutture di Dati e Algoritmi”, Pearson Editore.