OVERVIEW

In the theoretical module, the course presents formal models of computer-based problem solving intended as the treatment of languages ​​and the related issues of computability and complexity. The course considers the main techniques for the construction of correct and efficient algorithms and data structures. In the laboratory module, design and programming tools in an object-oriented language aimed at developing an interpreter are exposed.

AIMS AND CONTENT

LEARNING OUTCOMES

The course is divided into two modules, focusing respectively on the theory of computation and object-oriented programming. The first module provides the theoretical foundations of computation models for formal language processing (finite automata, grammars, Turing machines), introducing key concepts in computability and complexity, along with fundamental strategies for algorithm design and analysis. The second module covers practical aspects of software development in C++ (2020 standard), with a focus on object-oriented programming, the use of the standard library, and essential design principles (UML diagrams, design patterns). The course aims to develop students’ ability to formalize and solve computational problems, design correct and efficient algorithms, and implement them using a modern and powerful programming language.

PREREQUISITES

To understand the course topics, it is necessary to know the concepts of procedural programming (main scalar and vector data types, declaration and use of variables, conditional choices, iterations, definition of functions), object-oriented programming (definition of classes and generic classes) and the C++ language as provided by the courses of Fundamentals of Computer Science. It is also advisable to have an exposure to the basic concepts of set theory, discrete mathematics and probability.

TEACHERS AND EXAM BOARD

EXAMS

EXAM DESCRIPTION

The exam includes two mandatory tests:

- Written test on the theory of computation, algorithms and data structures
- Develpment of a project assigned by the teacher

At the end of the first semester, there is an intermediate written test on the theory of computation only. All written tests include one or more open questions. The project is assigned at the end of the first semester and is carried out individually by the students. The project is valid for one year, i.e. the written exam must be carried out within one year from the date of delivery of the project. The project contributes to the final grade for a quarter (25%) of the overall score, while the written test contributes to three quarters (75%) of the overall score (25% for the theory of computation part, 50% for algorithms and data structures).

ASSESSMENT METHODS

The project will assess the student's ability to put into practice the concepts of computation theory in the context of a simple but realistic application (for example, an interpreter for a programming language) designed and implemented with the C++ language.

The written exam will assess the student's understanding of the concepts presented in class by carrying out exercises that involve both the solution of problems and the demonstration of properties relating to the proposed solutions.