|Teoria||9||II semestre, I semestre||Ugo Solitro|
|Esercitazioni||3||II semestre, I semestre||Romeo Rizzi|
This course proposes providing the fundamentals skills in order to analyze and resolve problems by means of developing programs.
The general objectives of this module are
- the knowledge of the principles of programming and of programming languages,
- the mastery of fundamental techniques for analyzing problems and developing their algorithmic solutions,
- the introduction to the methods for the evaluation of correctness and efficiency of algorithms.
In the laboratory, we will practice the above principles by means of a programming activity.
- Problems and Solutions.
- Models of Computations: abstract machine, compiler and interpreter.
- Programming languages: formal languages, compiler, interpreter.
- Laboratory: introduction to linux and to the developing environment.
PART I - Problems, algorithms and programs.
- Imperative programming
- Elementary of programming: basic instructions and development of simple programs; variables, expressions and assignment.
- Data types. The general concept of data type: characterisation and data representation. Abstract Data Types.
- Primitive data types: characterisation, use and related problems.
- Structured data types: array, record, file, pointer, string and other data structures.
- Program structure. Fundamental instructions. Sub-programs: structure, parameters and visibility. Recursion.
- Object Oriented Programming.
- Basics of objects: classes, objects, attributes, constructors, modifiers.
- Advanced data structures: representation of sequences, vector and matrices; inductive and dynamic data structures; introduction to lists, trees and graphs.
PART II - Analysis of Algorithms
- Correctness: termination, logic properties; methods for the correctness verification.
- Efficiency of algorithms.
- Introduction to the complexity. Performance of algorithms. Evaluation of efficiency. Computational costs.
- Asymptotic estimation of the complexity in time and space. The worst and medium case.
- Amortised analysis.
- Study of fundamental examples.
- Sequences: static and dynamic implementation and algorithms.
- Research and Sorting Algorithms: basic search, binary search, insertion and selection sort, merge sort, quick sort.
- Matrices and Vectors: implementation, operations and algorithms.
- Dynamic sequences: abstract definition and implementation; basic operations.
- Trees. Abstract definition and implementation. Basic operation. Binary research trees.
- Introduction to algorithms on graphs.
Didactic method (concise version)
The subjects will be presented, when possible, according to the following schema.
- Introduction to the subject.
- Analysis of the problem related.
- In-depth study of the subject through the development of exercises, even practical, with the support of the teacher and tutors, if available.
- Correction of some exercises.
- Final discussion on the activities.
(last update: 26/09/2018)
The final exam consists of a written test, a practical test and a final oral exam.
The written and practical test can be partially replaced by ongoing test.
|Teoria||Bertossi, Alan e Montresor, Alberto||Algoritmi e strutture di dati (Edizione 3)||Città Studi Edizioni, De Agostini Scuola||2014||978-8-825-17395-6|
|Teoria||Walter Savitch||Programmazione con Java (seconda edizione) (Edizione 2)||Pearson||2013||9788871929613|