SSD

Crediti

INF/01

12

Obiettivi Formativi

Il corso ha lo scopo di introdurre i concetti fondamentali riguardanti il progetto e l’analisi di algoritmi e delle strutture dati che essi utilizzano, illustrando le principali tecniche di progettazione e alcune strutture dati fondamentali, insieme all’analisi della complessità computazionale.

Competenze acquisite

Al termine del corso il candidato dovrà essere in grado di applicare i concetti e  le tecniche presentati nell’insegnamento al progetto di algoritmi per la soluzione di semplici problemi, alla scelta delle strutture dati adeguate, alla stima della complessità computazionale, inoltre dovrà essere in grado di presentare in maniera efficace problemi e relativi algoritmi risolutivi, sapendo confrontare in maniera critica differenti soluzioni algoritmiche di un medesimo problema.

Programma

Algoritmi, modelli di calcolo e metodologie di analisi: Introduzione informale agli algoritmi. Modelli di calcolo. Notazione asintotica. Ricorrenze.
Tecniche fondamentali per il progetto di algoritmi: Tecnica divide et impera. Programmazione dinamica.
Algoritmi su grafi: Rappresentazione di grafi. Visite in ampiezza e in profondità. Alberi di copertura minimi (Kruskal e Prim)

Strutture dati elementari: Array, liste e alberi.
Alberi binari di ricerca.
Heap e code di priorità.
Tabelle Hash.
Ordinamento: Insertion sort, Merge sort, Heapsort, Quicksort.
Ordinamento in tempo lineare: counting sort, radix sort.
Programmazione dinamica.

Testi Consigliati

C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2008.

B. Kernighan, D. M. Ritchie, Il linguaggio C, Pearson Education Italia, 2019

R. Sedgewick, Algoritmi in C, Pearson Education Italia, 2002

Modalità di Verifica

–         Prova scritta con domande aperte e scelta multipla

–         La durata della prova e di massimo 3 ore

–         La valutazione viene espressa in trentesimi