Algoritmi E Strutture Dati 2016/2017

Il corso riguarda l'analisi e la progettazione di algoritmi. L'enfasi è sugli algoritmi efficienti. Saranno presentati i principali strumenti teorici utili per l'analisi e le principali tecniche di progettazione algoritmica (tecnica greedy, divide-et-impera, programmazione dinamica). Il corso è diviso in due parti. La prima parte copre: notazione asintotica, diversi metodi per stimare la complessità computazionale di algoritmi ricorsivi, il problema dell'ordinamento, strutture dati efficienti per implementare dizionari e code con priorità, e il problema del calcolo della distanza di edit fra due parole. La seconda parte riguarda problemi e algoritmi su grafi. Saranno presentati algoritmi efficienti per visitare un grafo, calcolare cammini minimi (in grafi pesati), trovare un minimo albero di copertura, e calcolare il flusso massimo di una rete con vincoli di capacità sugli archi.