CdSINFORMATICA
Codice735AA
CFU15
PeriodoAnnuale
LinguaItaliano
L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) e di programmazione che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.
The goal of the course is to introduce (basic) data structures and algorithmic and programming techniques that allow the student to solve problems on sequences, lists, trees and graphs with efficient (in time and in space) methods. Moreover, we will also discuss analythic methods for performances evalutaions of algorithms, as well as computability limitations.
Le conoscenze dello studente saranno verificate sulla base della sua capapcità di discutere e utilizzare i concetti e le tecniche più importanti presentati nel corso.
The student's knowledge will be verified by means of hir or her hability to discuss and use the methods and the techniques introduced in the course.
Capacità fondamentali nel progetto di algoritmi e strutture dati, e nella valutazione degli algoritmi.
Fundamental skills in the design of algorithms and data structures, in programming tecniques, and in algorithms evaluation.
Esame scritto ed eventuale orale
Mandatory written exam and a possible oral exam
Gli studenti saranno in grado di valutare le performance di algoritmi di base prima della loro implementazione, di progettare algoritmi efficienti per la risoluzione di problemi, e di conoscere problemi difficili per cui le scelte algoritmiche di progetto possono influenzare pesantemente il risultato.
Students will learn how to evaluate the performances of algorithms independently from their implementation, how to design efficient method to solve computational problems.
Esercitazioni di autovalutazione
Self-evaluation assignmnts
Fondamenti di matematica discreta, incluse sommatorie, logaritmi, serie numeriche, calcolo combinatorio, funzioni e limiti.
Basic Discrete Mathematics, including sums, logarithms, numerical series, combinatorics, functions and limits.
- Struttura di un calcolatore e ambienti di sviluppo. Analisi asintotica del costo computazionale. Rappresentazione delle informazioni. Problemi computazionali e algoritmi di risoluzione.
- Controllo delle operazioni e del flusso all’interno di un programma. Problem solving su array.
- Blocco e struttura dei programmi. Funzioni, passaggio dei parametri. Ricorsione,
- Algoritmi per ordinamento e ricerca.
- Strutture di dati dinamiche. Liste. Code e pile. Tabelle hash e dizionari.
- Divide et impera, programmazione dinamica, algoritmi greedy.
- Algoritmi per alberi e grafi.
- Cenni di calcolabilità e di classi di complessità.
- Computer Structure and development environments. Asyntotic analysis of computational costs. Information representations. Computational Problems and Algorithms.
- Operations and flux control and within a program. Problem solving on arrays.
- Blocks and programs structures. Functions, parameters passing. Recursion.
- Algorithms for sorting and searching.
- Dynamic Data Structures. Lists, Queues, Stacks. Hash Tables and Dictionaries.
- Divide et impera, dynamic programming, greedy algorithms.
- Algorithms on trees and on graphs.
- Basic calcolability and complexity classes.
Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.
Altri riferimenti verrano indicati e pubblicati sul classroom del corso.
Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.
I. Mastroeni, C. Priami. Semantica operazionale. Strumenti e applicazioni. CEDAM, 1999.
La frequenza e' altamente consigliata. Sul sito o classroom del corso verrannoforniti riferimenti bigliografici delle lezioni.
Attendance is highly recommended. On the google classroom material will be indicated for each class.
Prova Scritta ed eventuale orale
Mandatory written exam and optional oral exam
Google Classroom anni precedenti
Google Classroom of previous years