Computability Theory (CCOM5035)

Latest Course Syllabus-ABET Style () (PDF)

Credits: 3
Students should take this course at: 4th Year - 1st Semester

Pre-requisite: Data Structures (CCOM3034) and Modern Algebra 1 (MATE4081)


Description

In this course fundamental concepts, ideas, and models of the theory of computation are discussed. Topics included: introduction to automata and languages, introduction to compatibility theory, introduction to complexity theory.


Content

  • Mathematical preliminaries

  • Automata theory

  • Formal languages

  • Turing machines

  • Decidability

  • Reducibility

  • Complexity theory


Objectives

  • understand that there are real problems that cannot be solved by today's computers

  • Understand the fundamental concepts of the theory of computability.

  • Understand and utilize the basic concepts of automata theory and languages to explain the fundamental concepts of the theory of computability.

  • Understand the relation among the theory of computation and complexity theory.

  • study the contributions of diverse groups to computer science