# 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
• 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, 2019-2020, 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

### Reference week

MoTuWeThFr
8-9
9-10
10-11
11-12CO3
12-13
13-14
14-15CM1221
CM5

15-16
16-17
17-18
18-19
19-20
20-21
21-22

Lecture
Exercise, TP
Project, other

### legend

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