I principali obiettivi del corso sono: (i) analizzare le principali tecniche di progettazione degli algoritmi; (ii) classificare, analizzare, progettare e implementare algoritmi; (iii) valutare i costi in termini di efficienza computazionale; (iv) scegliere e implementare la struttura dati più adatta; (v) giungere al miglior compromesso tra esigenze conflittuali (costo, semplicità, efficienza).
Prerequisiti
Matematica di base (algebra di base, concetto di funzione). Programmazione procedurale.
Metodi didattici
L’insegnamento si compone di sessioni sincrone (lezioni frontali in aula e laboratorio).
Verifica Apprendimento
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
Testi
1) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. "Introduzione agli algoritmi e strutture dati", terza edizione, McGraw-Hill Education 2) Pierluigi Crescenzi, Giorgio Gambosi, Roberto Grossi, Gianluca Rossi. "Strutture di dati e algoritmi. Progettazione, analisi e programmazione", Pearson 3) Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. "Data Structures and Algorithms in Python", John Wiley & Sons Inc
Contenuti
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.