Course Catalog

Theory of Computation for Business Informatics (CSEN 507)

Offered By:  Management Technology Faculty

Course Prerequisites

Description

This course introduces students to three areas of theoretical computer science: formal languages, computability theory, and complexity theory.

The module comprises three parts:
  1. Formal languages: regular and context-free languages; context-sensitive languages (context-sensitive grammars and linear-bounded automata); type-0 languages (unrestricted grammars and Turing machines); the Chomsky hierarchy.
  2. Computability theory: recursive and recursively enumerable languages; Turing-computable functions; decidable and undecidable problems; Church's thesis.
  3. Complexity theory: time and space complexity of Turing machines; the complexity classes P and NP; reducibility, NP-hardness and NP-completeness; examples of NP-complete problems.

 

GUC Chat Bot