Coursebooks

Theory of computation

Lecturer(s) :

Svensson Ola Nils Anders

English

Summary

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematically precise understanding of their fundamental capabilities and limitations.

Content

• Basic models of computation (finite automata, Turing machine)
• Elements of computability theory (undecidability, reducibility)
• Introduction to time complexity theory (P, NP and theory of NP-completeness)

Keywords

theory of computation, Turing machines, P vs. NP problem, complexity theory, computability theory, finite automata, NP-completeness

Learning Prerequisites

Required courses

CS-101 Advanced information, computation, communication I

CS-250 Algorithms

Learning Outcomes

By the end of the course, the student must be able to:
• Perform a rigorous study of performance of an algorithm or a protocol
• Classify computational difficulty of a decision problem
• Define the notion of NP-completeness
• Analyze various computation models
• Design a reduction between two computational problems
• Characterize different complexity classes
• Explain P vs. NP problem

Transversal skills

• Use a work methodology appropriate to the task.
• Continue to work through difficulties or initial failure to find optimal solutions.

Teaching methods

Ex cathedra with exercises

Assessment methods

Written exam and continuous control

In the programs

• Semester
Spring
• Exam form
During the semester
• Credits
4
• Subject examined
Theory of computation
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Passerelle HES - IN, 2018-2019, Spring semester
• Semester
Spring
• Exam form
During the semester
• Credits
4
• Subject examined
Theory of computation
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Semester
Spring
• Exam form
During the semester
• Credits
4
• Subject examined
Theory of computation
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks
• Semester
Spring
• Exam form
During the semester
• Credits
4
• Subject examined
Theory of computation
• Lecture
2 Hour(s) per week x 14 weeks
• Exercises
2 Hour(s) per week x 14 weeks

Reference week

MoTuWeThFr
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
Under construction

Lecture
Exercise, TP
Project, other

legend

• Autumn semester
• Winter sessions
• Spring semester
• Summer sessions
• Lecture in French
• Lecture in English
• Lecture in German