Obiettivi Formativi

I principali obiettivi del corso sono: analizzare le principali tecniche di progettazione degli algoritmi, classificare, analizzare, progettare ed implementare algoritmi, valutare i costi in termini di efficienza computazionale, giungere al miglior compromesso tra esigenze conflittuali (costo, semplicità, efficienza).

Metodi didattici

L’insegnamento si compone di sessioni sincrone (lezioni frontali in aula e laboratorio).

Prerequisiti

Matematica di base (algebra di base, concetto di funzione). Programmazione procedurale.

Verifiche dell'apprendimento

Due prove in itinere durante il semestre, le quali coprono gli argomenti trattati in aula fino alla prova, oppure una prova scritta in occasione degli appelli d'esame, la quale ricopre l'intero programma. Le prove scritte includono esercizi mirati a verificare le capacità di problem solving, progettazione di algoritmi e coding. Il punteggio ha un offset da 0 a 30 e lode.

Programma del Corso

Algoritmi e strutture dati - Insertion sort; Analisi degli algoritmi; Progettazione degli algoritmi; Notazione asintotica; Dividi et Impera: il metodo di sostituzione per risolvere le ricorrenze, il metodo dell'albero di ricorsione per risolvere le ricorrenze, il metodo dell'esperto per risolvere le ricorrenze, mergesort; Heap e heapsort; Quicksort; Ordinamento in tempo lineare: Countingsort; Alberi e alberi binari; Alberi binari di ricerca; Algoritmi elementari per grafi: rappresentazione dei grafi, visita in ampiezza, visita in profodità; Alberi di connessione minima: algoritmi di Kruskal e Prim; Cammini minimi: algoritmo di Dijkstra.