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)

Learning Goals

The main objectives of the course are: - analyze the main techniques for algorithm design - classify, analyze, design, and implement algorithms - evaluate costs in terms of computational efficiency - choose and implement suitable data structures - make the best compromise among conflicting requirements (cost, simplicity, efficiency)

Metodi didattici

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

Teaching Methods

The teaching consists of synchronous sessions (frontal lectures both in classroom and laboratory).

Prerequisiti

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

Prerequisites

Basic mathematics (basic algebra, definition of function) Procedural programming

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.

Assessment

Two mid-term tests during the semester, which cover the topics covered in the classroom up to the test, or a written test on the exam sessions, which covers the entire program. Written tests include exercises aimed at verifying problem-solving, algorithm design, and coding skills. The score has an offset from 0 to 30 with honors.

Programma del Corso

Python 3 - Variabili, espressioni ed istruzioni; Funzioni; Istruzioni condizionali e ricorsione; Funzioni produttive; Iterazione; Stringhe; Liste; Dizionari; Tuple; File; Classi e oggetti; Classi e funzioni; Classi e metodi; Ereditarietà. 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.

Course Syllabus

Python 3 - Variabili, espressioni ed istruzioni; Funzioni; Istruzioni condizionali e ricorsione; Funzioni produttive; Iterazione; Stringhe; Liste; Dizionari; Tuple; File; Classi e oggetti; Classi e funzioni; Classi e metodi; Ereditarietà. 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.