76978 - TEORIA DI ALGORITMI E STRUTTURE DATI

Il corso introduce le principali metodologie per la specifica, l'analisi e la realizzazione di algoritmi e strutture dati statiche e dinamiche. Argomenti trattati (Conoscenze): - introduzione all'analisi di algoritmi - notazione O, Theta, Omega, per gli ordini di grandezza delle funzioni di complessitá - algoritmi ricorsivi, ricorrenze e soluzione di ricorrenze con diversi metodi - algoritmi di ordinamento (InsertionSort,SelectionSort,Mergesort,Quicksort,HeapSort) - algoritmi di ordinamento lineare (es.: CountingSort) - strutture dati elementari come liste e code - tabelle hash - alberi binari di ricerca ed operazioni su di essi - alberi binari bilanciati (Red-Black trees) ed operazioni su di essi - alberi B ed operazioni su di essi - grafi orientati, non orientati, pesati e non pesati, visita su grafi in ampiezza e in profonditá, ordinamento topologico, ciclicità, alberi di copertura minimi, percorsi minimi Al termine del corso lo studente sará capace di (Abilitá): - Analizzare un algoritmo per la risoluzione di un problema in termini della sua complessitá asintotica, e confrontare due soluzioni diverse - Riconoscere un problema di ordinamento e scegliere o progettare il miglior algoritmo di ordinamento per risolverlo - Progettare ed analizzare una struttura dati elementare o non elementare a supporto di un algoritmo, offrendo opportuni metodi di accesso ed analizzandone la complessitá asintotica - Progettare ed analizzare una struttura dati di tipo albero, offrendo opportuni metodi di accesso ed analizzandone la complessitá asintotica - Progettare ed analizzare una struttura dati di tipo grafo, offrendo opportuni metodi di accesso ed analizzandone la complessitá asintotica