Università degli Studi di Urbino Carlo Bo / Portale Web di Ateneo


THEORY OF COMPUTATION
THEORY OF COMPUTATION

A.Y. Credits
2023/2024 8
Lecturer Email 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

Research Methods in Science and Technology (XXXIX)
Curriculum: PERCORSO COMUNE
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.

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: 09/03/2024

Il tuo feedback è importante

Raccontaci la tua esperienza e aiutaci a migliorare questa pagina.

Posta elettronica certificata

amministrazione@uniurb.legalmail.it

Social

Università degli Studi di Urbino Carlo Bo
Via Aurelio Saffi, 2 – 61029 Urbino PU – IT
Partita IVA 00448830414 – Codice Fiscale 82002850418
2024 © Tutti i diritti sono riservati

Top