Sillabo dell'insegnamento

• B - Algoritmi
* A - Algoritmi fondamentali
Algoritmi e Strutture Dati. Esempi di Algoritmi: il Problema della Connettività. Analisi Empiriche. Analisi degli algoritmi. Velocità di crescita delle funzioni. Ricorrenze Fondamentali. Esempi.
* SDF - Strutture di Dati Fondamentali
Array. Il Crivello di Eratostene. Liste Concatenate. Inserimento, Cancellazione e Ricerca di un elemento nella lista. Elezione alla Giuseppe Flavio. Pile. Valutazione di un'espressione in forma Polacca mediante una Pila. Pile e ricorsione. Code.
* A - Algoritmi fondamentali
Algoritmi di Ordinamento Elementari. L'Heapsort. Il Quicksort. Analisi worst case e analisi caso medio del quicksort.
* SDF - Strutture di Dati Fondamentali
Alberi: definizioni, rappresentazioni e proprietà. Algoritmi di attraversamento di un albero: preordine, inordine e postordine. Valutazione delle espressioni in forma prefissa tramite alberi binari
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Divide et Conquer, Ricerca Binaria, le Torri di Hanoi, il Problema del Massimo; Programmazioni Dinamica, Numeri di Fibonacci, Problema dello Zaino (versione programmazione dinamica).
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Tecniche Greedy: Optimal Storage on Tapes. Il Problema dello Zaino (versione 'greedy'). Esempi: Ricerca Minimo e Massimo, Moltiplicazione d'interi, Moltiplicazione di Matrici; Mergesort; Prodotto di n matrici. Longest Common Subsequence, Riconoscimento Grammatiche Context Free.
* SDF - Strutture di Dati Fondamentali
Rappresentazione di Grafi, Visite su Grafi,
* ASC - Algoritmi su Strutture Combinatorie
Biconnettivita' e Connettivita' Forte, Algoritmi di Spanning Tree Minimo, Algoritmi per Cammini Ottimi.
* ASC - Algoritmi su Strutture Combinatorie
Algoritmi su grafi. Albero di ricopriento di costo minimo di un albero non orientato: Algoritmo di Kruskal e algoritmo di Prim.
* ASC - Algoritmi su Strutture Combinatorie
Biconnettività su un grafo non orientato. Connettività forte su un grafo orientato.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Relazione tra Macchina di Turing e RAM. Complessità Computazionale e Linguaggi di Programmazione ad Alto Livello.
TAA - Tecniche Algoritmiche Avanzate
Macchine di Turing Non Deterministiche, Le classi P ed NP, NP Completezza del Problema della Soddisfattibilità. Ulteriori Problemi Np Completi.