Fiches de cours 2017-2018

PDF
 

Theory of computation

CS-251

Enseignant(s) :

Vishnoi Nisheeth

Langue:

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

Dans les plans d'études

  • Informatique, 2017-2018, Bachelor semestre 4
    • Semestre
      Printemps
    • Forme de l'examen
      Pendant le semestre
    • Crédits
      4
    • Matière examinée
      Theory of computation
    • Cours
      2 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
  • Passerelle HES - IN, 2017-2018, Semestre printemps
    • Semestre
      Printemps
    • Forme de l'examen
      Pendant le semestre
    • Crédits
      4
    • Matière examinée
      Theory of computation
    • Cours
      2 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
  • Systèmes de communication, 2017-2018, Bachelor semestre 4
    • Semestre
      Printemps
    • Forme de l'examen
      Pendant le semestre
    • Crédits
      4
    • Matière examinée
      Theory of computation
    • Cours
      2 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
  • Mineur en Informatique, 2017-2018, Semestre printemps
    • Semestre
      Printemps
    • Forme de l'examen
      Pendant le semestre
    • Crédits
      4
    • Matière examinée
      Theory of computation
    • Cours
      2 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines

Semaine de référence

LuMaMeJeVe
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
En construction
Cours
Exercice, TP
Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand