THEORY OF COMPUTATION
THEORY OF COMPUTATION
| A.Y. | Credits |
|---|---|
| 2022/2023 | 4 |
| Lecturer | Office hours for students | |
|---|---|---|
| Marco Bernardo | Thursday 16:00 - 18:00 or on demand |
| Teaching in foreign languages |
|---|
|
Course entirely taught in a foreign language
English
This course is entirely taught in a foreign language and the final exam can be taken in the foreign language. |
Assigned to the Degree Course
| Date | Time | Classroom / Location |
|---|
| Date | Time | Classroom / Location |
|---|
Learning Objectives
The objective of this course is to introduce the theoretical foundations of computer science, in particular decidability of computational problems, computability of functions and sets, and formal modeling of computing systems, through basic notations such as Turing machines, lambda calculus, and process algebras.
Program
01. Introduction to Informatics and Computation
01.01 Informatics: Science, Methodology, Technology
01.02 Socio-Economic Impact and Computational Thinking
01.03 Computational Problems and Algorithmic Solutions
01.04 A Brief History of Informatics
02. The Operational View: Turing Machines
02.01 A Classical Model of Computation
02.02 From Logicism to Incompleteness and Undecidability
02.03 Turing Machines and Universal Turing Machine
02.04 Computed Functions and Recognized Languages
03. The Functional View: Lambda Calculus
03.01 Syntax of Lambda Calculus
03.02 Semantics and Combinatory Logic
03.03 Recursive Functions via Fixed Points
03.04 Termination and Confluence
03.05 Lambda Calculus with Types
04. Computability of Functions, Sets, Problems
04.01 Church-Turing Thesis
04.02 Primitive and General Recursive Functions
04.03 Recursive and Recursively Enumerable Sets
04.04 Decidable and Undecidable Problems
04.05 Tractable and Intractable Problems
05. The Modeling View: Process Algebras
05.01 Concurrency and Communication
05.02 Syntax of Process Calculi
05.03 Interleaving Semantics
05.04 Truly Concurrent Semantics via Petri Nets
05.05 Computational Power of Process Calculi
05.06 Spectrum of Behavioral Equivalences
05.07 Strong Bisimilarity and Its Properties
05.08 Weak Bisimilarity and Its Properties
Bridging Courses
There are no mandatory prerequisites.
Teaching Material
The teaching material prepared by the lecturer in addition to recommended textbooks (such as for instance slides, lecture notes, exercises, bibliography) and communications from the lecturer specific to the course can be found inside the Moodle platform › blended.uniurb.it
Teaching, Attendance, Course Books and Assessment
- Teaching
Theory lectures.
- Attendance
Course attendance is strongly recommended.
- Course books
Hopcroft, Motwani, Ullman, "Automata Theory, Languages, and Computation", Pearson Addison-Wesley, 2006.
Barendregt, "The Lambda Calculus: Its Syntax and Semantics", North Holland, 2014.
Milner, "Communication and Concurrency", Prentice Hall, 1989.
- Assessment
Oral exam.
- Disability and Specific Learning Disorders (SLD)
Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.
To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.
| « back | Last update: 26/02/2023 |
