THEORY OF COMPUTATION
THEORY OF COMPUTATION
| A.Y. | Credits |
|---|---|
| 2023/2024 | 8 |
| 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
01.01 Informatics: Science, Methodology, Technology
01.02 Socio-Economic Impact and Computational Thinking
01.03 A Brief History of Informatics
01.04 Why Theory Matters: Software Disasters
02. Introduction to Computation
02.01 Computational Problems and Algorithmic Solutions
02.02 A Classical Model of Computation
02.03 From Logicism to Incompleteness and Undecidability
02.04 Induction, Enumerations, Encodings
03. The Operational View: Turing Machines
03.01 Automata and Turing Machines
03.02 The Universal Turing Machine
03.03 Languages Recognized by Turing Machines
03.04 Functions Computed by Turing Machines
04. The Functional View: Lambda Calculus
04.01 Syntax of Lambda Calculus
04.02 Semantics and Combinatory Logic
04.03 Recursive Functions via Fixed Points
04.04 Termination and Confluence
04.05 Lambda Calculus with Types
05. Computability for Functions, Sets, Problems
05.01 Church-Turing Thesis
05.02 Primitive and General Recursive Functions
05.03 Recursive and Recursively Enumerable Sets
05.04 Decidable and Undecidable Problems
05.05 Tractable and Intractable Problems
06. The Modeling View: Process Algebras
06.01 Concurrency and Communication
06.02 Syntax of Process Calculi
06.03 Interleaving Semantics via Labeled Transition Systems
06.04 Computational Power of Process Calculi
06.05 Spectrum of Behavioral Equivalences
06.06 Strong Bisimilarity and Its Properties
06.07 Weak Bisimilarities and Their Properties
06.08 Truly Concurrent Semantics via Petri Nets
06.09 Truly Concurrent Semantics via Event Structures
06.10 Truly Concurrent Bisimilarities
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 on a topic agreed upon with the lecturer.
- Disabilità e DSA
Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.
A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.
| « back | Last update: 09/03/2024 |
