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

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

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

*Problemi computazionalmente difficili*
Problemi decisionali, di ricerca e di ottimizzazione. Classi di complessità.