Syllabus del corso
Obiettivi
Scopo del corso è insegnare allo studente come progettare, valutare e implementare algoritmi efficienti, utilizzando in modo opportuno le tecniche di programmazione e le strutture dati adeguate.
Conoscenza e capacità di comprensione
- Conoscenza dei concetti fondamentali relativi ai problemi computazionali
- Conoscenza delle tecniche base per dimostrare la correttezza di un algoritmo
- Conoscenza del funzionamento dei paradigmi di programmazione ricorsiva e divide-et-impera
- Conoscenza del funzionamento di algoritmi di ordinamento
- Conoscenza delle tecniche per valutare l'efficienza di algoritmi e strutture dati
- Conoscenza del funzionamento e delle caratteristiche di diverse strutture dati fondamentali
Conoscenza e capacità di comprensione applicate
- Capacità di analizzare la correttezza formale di un algoritmi iterativo e ricorsivo
- Capacità di applicazione dei paradigmi di programmazione ricorsiva e divide-et-impera per risolvere nuovi problemi computazionali
- Capacità di applicazione delle tecniche di valutazione dell'efficienza degli algoritmi iterativi, ricorsivi e divide-et-impera
- Capacità di simulare il funzionamento di algoritmi complessi e strutture dati fondamentali su istanze specifiche
- Capacità di utilizzare correttamente le strutture dati fondamentali per risolvere nuovi problemi computazionali
Autonomia di giudizio
- Capacità di scegliere l'algoritmo più efficiente e/o più indicato per risolvere nuovi problemi computazionali specifici
- Capacità di scegliere la struttura dati più efficiente e/o più indicato per risolvere nuovi problemi computazionali specifici
Abilità comunicative
- Saper utilizzare correttamente lo pseudocodice per presentare formalmente e in modo non ambiguo un algoritmo
- Saper comprendere e utilizzare il lessico corretto per comprendere o descrivere le caratteristiche di un algoritmo e di una struttura dati
Capacità di apprendere
- Essere in grado di ricercare e selezionare criticamente un nuovo algoritmo più indicato per risolvere un nuovo problema computazionale
- Essere in grado di ricercare e selezionare criticamente una nuova struttura dati più indicata per risolvere un nuovo problema computazionale
Contenuti sintetici
Metodologie di base per progettare algoritmi e analizzarne l’efficienza. Strutture dati fondamentali: definizioni e utilizzo
Programma esteso
- Introduzione: Algoritmo, problema, istanza.
- Analisi di algoritmi: Valutazione dei tempi di esecuzione, caso pessimo, ottimo e medio.
- Programmazione ricorsiva e approccio Divide-et-Impera: Mergesort e Quicksort.
- Valutazione del tempo di esecuzione di algoritmi ricorsivi: equazioni di ricorrenza.
- Altri algoritmi di ordinamento: ordinamento in tempo lineare.
- Strutture dati fondamentali: Array, liste, pile e code.
- Alberi Binari e Alberi Binari di Ricerca
- Heap e code con priorità. Heapsort.
- Grafi e loro rappresentazione in memoria.
- Algoritmi di visita dei grafi: BFS e DFS.
Prerequisiti
Nozioni base di programmazione e di analisi matematica
Modalità didattica
Lezioni, esercitazioni e approfondimenti sperimentali. Attività di studio individuali supportate dal libro di testo consigliato.
Le lezioni sono tenute in italiano. Tutte le attività verranno svolte in presenza: 32 ore di lezioni frontali di 2/3 ore ciascuna in modalità erogativa, 44 ore (20 ore di esercitazione di 2/3 ore ciascuna e 24 ore di laboratorio di 4 ore ciascuna) in modalità interattiva.
Materiale didattico
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, ed. Mc. Graw Hill.
Periodo di erogazione dell'insegnamento
Secondo semestre
Modalità di verifica del profitto e valutazione
L'accertamento dei risultati di apprendimento avviene mediante una prova scritta individuale, finalizzata a verificare il raggiungimento degli obiettivi formativi dell'insegnamento relativi alla conoscenza degli algoritmi e delle strutture dati, alla capacità di analizzarne correttezza ed efficienza e alla capacità di applicare tali conoscenze alla soluzione di problemi computazionali.
La prova scritta è valutata in trentesimi e comprende:
- Esercizi di progettazione e sviluppo di algoritmi ricorsivi o iterativi per problemi non affrontati direttamente durante il corso, finalizzati a verificare la capacità di applicare conoscenze e metodologie alla risoluzione di problemi (Descrittore di Dublino 2);
- Esercizi di simulazione e analisi del comportamento di algoritmi e strutture dati studiati durante il corso, finalizzati a verificare la comprensione dei meccanismi di funzionamento e la capacità di analizzarne correttezza ed efficienza (Descrittori di Dublino 1 e 2);
- Domande aperte finalizzate a verificare la conoscenza dei concetti, delle definizioni e delle proprietà fondamentali degli algoritmi e delle strutture dati, nonché la capacità di utilizzare in modo appropriato il lessico disciplinare (Descrittori di Dublino 1 e 4).
Le domande di teoria contribuiscono complessivamente fino a 8 punti.
In alternativa alla prova scritta finale sono previste due prove parziali riservate agli iscritti al primo anno, svolte a metà corso e nel primo appello di giugno. Ciascuna prova è strutturata come la prova scritta completa e verifica i risultati di apprendimento relativi agli argomenti trattati fino a quel momento.
Ciascuna prova parziale è valutata in trentesimi ed è considerata sufficiente se raggiunge un punteggio di almeno 16/30. Se entrambe le prove parziali sono sufficienti, allora il voto finale è ottenuto dalla media dei due punteggi delle due prove parziali, approssimata per eccesso. La prova si intende superata se il voto ottenuto è almeno 18/30.
È possibile recuperare una sola prova parziale nell'appello di luglio in caso di assenza, insufficienza o per il miglioramento del risultato conseguito.
Criteri di valutazione
La valutazione delle prove scritte tiene conto dei seguenti aspetti:
- correttezza formale delle soluzioni proposte;
- capacità di individuare e applicare algoritmi e strutture dati appropriati;
- capacità di analizzare correttezza, complessità computazionale ed efficienza delle soluzioni;
- completezza e accuratezza delle risposte;
- chiarezza espositiva e uso corretto del linguaggio tecnico e dello pseudocodice.
La graduazione del voto segue indicativamente i seguenti criteri:
- 18-21/30: raggiungimento dei risultati di apprendimento essenziali;
- 22-25/30: buona comprensione degli argomenti e corretta applicazione delle tecniche principali;
- 26-29/30: conoscenza approfondita degli argomenti e capacità di risolvere autonomamente problemi complessi;
- 30/30: padronanza completa degli argomenti, correttezza rigorosa delle soluzioni e pieno raggiungimento delle capacità comunicative.
Il punteggio di 30 e lode è attribuito a prove eccellenti caratterizzate da pieno raggiungimento degli obiettivi formativi e particolare rigore, completezza e chiarezza espositiva. Il punteggio di 30 e lode conseguito in una prova parziale corrisponde a 31 punti ai fini del calcolo della media.
Orario di ricevimento
Su appuntamento
Aims
The aim of the course is to teach to design, evaluate and implement efficient algorithms, making use of the most appropriate progamming techniques and data structures.
Knowledge and Understanding
- Knowledge of basic concepts related to computational problems
- Knowledge of basic techniques to prove the correctness of an algorithm
- Knowledge of how recursive and divide-and-conquer programming paradigms work
- Knowledge of how sorting algorithms work
- Knowledge of techniques to evaluate the efficiency of algorithms and data structures
- Knowledge of how different fundamental data structures work and their characteristics
Applying Knowledge and Understanding
- Ability to analyze the formal correctness of iterative and recursive algorithms
- Ability to apply recursive and divide-and-conquer paradigms to solve new computational problems
- Ability to apply techniques to evaluate the efficiency of iterative, recursive, and divide-and-conquer algorithms
- Ability to simulate how complex algorithms and fundamental data structures work on specific examples
- Ability to correctly use fundamental data structures to solve new computational problems
Making Judgments
- Ability to choose the most efficient and/or most suitable algorithm to solve specific new computational problems
- Ability to choose the most efficient and/or most suitable data structure to solve specific new computational problems
Communication Skills
- Ability to correctly use pseudocode to formally and clearly present an algorithm
- Ability to understand and use the correct terminology to describe or understand the characteristics of an algorithm or a data structure
Learning Skills
- Ability to search for and critically select a new algorithm that is more suitable for solving a new computational problem
- Ability to search for and critically select a new data structure that is more suitable for solving a new computational problem
Contents
Basic techniques to develop algorithms and to analyse their efficiency. Introduction to the use of fundamental data structures.
Detailed program
- Introduction and basic definitions: algorithm, problem, instance.
- Computational complexity analysis of algorithms.
- Recursive programming and Divide-and-Conquer programming technique: Mergesort and Quicksort.
- Time complexity for recursive algorithms: recursive equations.
- Linear time sorting algorithms.
- Basic data structures: arrays, linked lists, stacks, queues.
- Binary trees and Search Binary Trees.
- Heap and priority queues. Heapsort.
- Graphs and graph representation.
- Traversing algorithms for graphs: BFS and DFS
Prerequisites
Basics of Computer Programming and Calculus.
Teaching form
Theoretical lectures, exercises, and practical implementation of proposed algorithms. Further exercises are available through the textbook.
The course is taught in Italian. All activities are in-person: 32 hours in unidirectional mode (2 or 3 hours per lesson), 44 hours in interactive mode, of which 20 hours (2 or 3 hours per lesson) for exercises and 24 (4 hours per lesson) for laboratory.
Textbook and teaching resource
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Mit Press ed.
Semester
Second semester
Assessment method
Assessment of learning outcomes is carried out through an individual written examination aimed at verifying the achievement of the course learning objectives related to the knowledge of algorithms and data structures, the ability to analyze their correctness and efficiency, and the ability to apply such knowledge to the solution of computational problems.
The written examination is graded on a 30-point scale and includes:
- Exercises requiring the design and development of recursive or iterative algorithms for problems not directly addressed during the course, aimed at assessing the ability to apply knowledge and methodologies to problem solving (Dublin Descriptor 2);
- Exercises involving the simulation and analysis of the behavior of algorithms and data structures covered during the course, aimed at assessing the understanding of their operating principles and the ability to analyze their correctness and efficiency (Dublin Descriptors 1 and 2);
- Open-ended questions aimed at assessing knowledge of the fundamental concepts, definitions, and properties of algorithms and data structures, as well as the ability to use the appropriate disciplinary terminology (Dublin Descriptors 1 and 4).
The theory questions contribute up to 8 points overall.
As an alternative to the final written examination, two midterm examinations are offered to first-year students. These are held halfway through the course and during the first examination session in June. Each midterm has the same structure as the full written examination and assesses the learning outcomes related to the topics covered up to that point.
Each midterm examination is graded on a 30-point scale and is considered passed if a score of at least 16/30 is achieved. If both midterms are passed, the final grade is obtained as the arithmetic mean of the two scores, rounded up to the nearest integer. The examination is considered passed if the resulting final grade is at least 18/30.
Students may retake only one of the two midterm examinations during the July examination session in case of absence, failure, or to improve the previously obtained result.
Assessment Criteria
The evaluation of written examinations is based on the following criteria:
- Formal correctness of the proposed solutions;
- Ability to identify and apply appropriate algorithms and data structures;
- Ability to analyze correctness, computational complexity, and efficiency of the proposed solutions;
- Completeness and accuracy of the answers;
- Clarity of presentation and appropriate use of technical terminology and pseudocode.
The grading scale is interpreted as follows:
- 18-21/30: achievement of the essential learning outcomes;
- 22-25/30: good understanding of the topics and correct application of the main techniques;
- 26-29/30: thorough knowledge of the topics and ability to solve complex problems independently;
- 30/30: complete mastery of the topics, rigorous correctness of the solutions, and full achievement of the expected communication skills.
The grade of 30 cum laude is awarded for outstanding performances demonstrating full achievement of the learning objectives, together with exceptional rigor, completeness, and clarity of presentation. A grade of 30 cum laude obtained in a midterm examination is counted as 31 points for the purpose of calculating the final average.
Office hours
By appointment