Coursebooks 2017-2018

PDF
 

Theory of computation

CS-251

Lecturer(s) :

Vishnoi Nisheeth

Language:

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

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:

Transversal skills

Teaching methods

Ex cathedra with exercises

Assessment methods

Written exam and continuous control

In the programs

  • Computer Science, 2017-2018, Bachelor semester 4
    • 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, 2017-2018, 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
  • Communication Systems, 2017-2018, Bachelor semester 4
    • 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
  • Computer science minor, 2017-2018, 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

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