Algoritmi e strutture dati I

Il corso si propone di fornire le conoscenze di base per la progettazione e l'analisi di algoritmi e strutture dati efficienti. In particolare, verranno illustrate le tecniche di base per l'analisi della complessità degli algoritmi e per la valutazione dell'efficienza delle principali strutture dati. Tali concetti verranno illustrati a livello teorico e metodologico e applicati, a titolo esemplificativo, all’analisi di algoritmi specifici per risolvere problemi fondamentali (ad esempio, algoritmi di ordinamenti e di ricerca), di strutture dati elementari (tra cui liste, alberi, grafi) e strutture dati avanzate (come tabelle hash e alberi bilanciati).

Cenni al calcolo della complessità computazionale degli algoritmi: notazione asintotica; calcolo del tempo di esecuzione di algoritmi iterativi; calcolo del tempo di esecuzione di algoritmi ricorsivi, metodi di soluzione di equazioni di ricorrenza. Analisi di complessità dei principali algoritmi di ordinamento: insertion sort, selection sort, merge sort, heap sort, quick sort. Strutture dati elementari e algoritmi fondamentali: heap, code a priorità, stack, liste puntate, alberi. Alberi binari di ricerca, alberi bilanciati: algoritmi di ricerca, inserimento, cancellazione in alberi binari di ricerca, alberi AVL e alberi Rossi e Neri. Tabelle ad Accesso Diretto e Tabelle Hash. Rappresentazione di grafi e grafi pesati, algoritmi di attraversamento di grafi: algoritmi di visita in ampiezza (BFS) e in profondità (DFS). Applicazioni delle visite di grafi: cammini minimi in grafi non pesati, verifica dell'aciclicità di un grafo orientato, ordinamenti topologici di grafi aciclici, componenti fortemente connesse. Problemi su grafi pesati: albero minimo di copertura, cammini minimi su grafi pesati.