Algoritmi

Programma di Teoria

1) Introduzione.
Nozione intuitiva di problema e algoritmo. Progettazione e analisi di algoritmi. La complessità di un algoritmo, analisi nel caso peggiore e in quello medio.
2) Modello di calcolo.
Macchina ad accesso casuale (RAM). Sintassi e semantica del linguaggio RAM. Criteri di costo uniforme e logaritmico. Tempi di calcolo e spazio di memoria dei programmi RAM. Confronto tra tempi polinomiali ed esponenziali. Linguaggio ad alto livello (Algol-like) e corrispondente traduzione in linguaggio RAM.
3) Strutture dati elementari.
Vettori, liste, pile, code e loro implementazioni. Grafi orientati e non orientati, alberi, alberi ordinati, alberi binari e loro rappresentazioni in memoria. Procedure ricorsive, loro traduzione iterativa mediante gestione della pila delle chiamate. Algoritmi di attraversamento di alberi e grafi. Visite in profondità e in ampiezza.
4) Algoritmi di ordinamento.
Classificazione delle procedure di ordinamento e valutazione del numero minimo di confronti. Algoritmo di inserimento. La struttura dati di heap e l'algoritmo heapsort. Quicksort.
5) Strutture dati evolute.
Le strutture dati come algebre eterogenee e loro implementazione. Alberi di ricerca binaria, B-alberi. Operazioni "union-find" su partizioni: algoritmi basati su foreste con bilanciamento e compressione.
6) Metodi di progettazione.
Algoritmi Divide et Impera e analisi dei loro tempi di calcolo (Master Theorem). Mergesort, ricerca binaria, algoritmo divide et impera per il prodotto di interi.
Algoritmi di programmazione dinamica: chiusura transitiva di grafi e calcolo dei cammini minimi.
Algoritmi greedy. Algoritmo di Kruskal. Algoritmi di Prim e Dijkstra.

Programma di Laboratorio

Notazione asintotica. Valutazione asintotica di successioni numeriche e di somme. Principali equazioni di ricorrenza.
Richiami di linguaggio C: struttura dei programmi, tipi predefiniti, espressioni, istruzioni di controllo, input e output, strutture dati (array, matrici, stringhe, records), funzioni e procedure ricorsive, puntatori, allocazione dinamica della memoria.
Implementazione di strutture dati e algoritmi: procedure di ordinamento, liste, pile e code, grafi e alberi, procedure di attraversamento di grafi, alberi di ricerca bilanciati, esempi di programmazione dinamica e di algoritmi greedy.