Portale di Ateneo - Unibs.it Portale di Ateneo - Unibs.it

In breve:

Paradigmi di sintesi di algoritmi.
Fondamenti matematici per l'analisi di complessità degli algoritmi.
Algoritmi di ordinamento e selezione.
Strutture dati fondamentali, tabelle hash, alberi binari di ricerca, grafi.
Teoria della computabilità e NP-completezza.

Per esteso:

*Analisi di algoritmi e complessità*
Dimensione dei dati di un problema. Caso pessimo, ottimo e medio.

*Progettazione di algoritmi*
Paradigma iterativo (Insertionsort). Paradigma divide et impera (Mergesort).

*Ordine di grandezza delle funzioni*
Notazione asintotica.

*Ricorrenze*
Metodi risolutivi. Alberi di ricorsione. Metodo principale.

*Algoritmi di ordinamento: Heapsort*
Heap. Mantenimento delle proprietà dello heap. Costruzione di uno heap.
Algoritmo Heapsort. Code con priorità.

*Algoritmi di ordinamento: Quicksort*
Algoritmo Quicksort. Prestazioni di Quicksort. Versione randomizzata di Quicksort. Analisi.

*Ordinamento in tempo lineare*
Limiti inferiori per l'ordinamento. Counting Sort. Radix Sort. Bucket Sort.

*Mediano e selezione*
Minimo e massimo. Selezione con tempo medio lineare.

*Strutture dati fondamentali*
Strutture di base. Realizzazione di puntatori e oggetti. Rappresentazione di alberi radicati.

*Tabelle hash*
Tabelle a indirizzamento diretto. Funzioni hash. Indirizzamento aperto.

*Alberi binari di ricerca*
Operazioni di visita, ricerca, inserimento e cancellazione.

*Grafi*
Rappresentazioni. Visita in ampiezza e in profondità. Ordinamento topologico. Cammini minimi da sorgente unica. Cammini minimi tra tutte le coppie di vertici.

*Programmazione dinamica*
Fasi dello sviluppo di algoritmi. Esempio: ottimizzazione della parentesizzazione per il prodotto di una sequenza di matrici.

*Computabilità*
Macchina di Turing deterministica, multi-nastro, non-deterministica. Tesi di Church-Turing. Macchina di Turing universale. Problema della terminazione. Indecidibilità.

*Problemi NP e oltre NP*
Problemi decisionali, di ricerca, di enumerazione e di ottimizzazione. Classi di complessità P, NP e coNP. NP-Completezza. Riducibilità. Classe PSPACE.