# Coursebooks 2016-2017

## Theory of computation

Vishnoi Nisheeth

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 complexity theory (time and space complexity, P vs. NP problem, 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, 2016-2017, 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   CM2
9-10
10-11   CM1221
CM5

11-12
12-13
13-14
14-15
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