Introduction to Theory of Computation (2020)

From CyberEdWiki
Jump to: navigation, search

The intent of the Introduction to Theory of Computation Knowledge Unit is to provide students with the basic knowledge of finite automata and their application to computation.


After completing the KU, students will be able to:

  1. Describe the theory of abstract machines or automata and what can be computed with them.
  2. Differentiate the characteristics of computable and non-computable functions.
  3. Describe the concept of complexity and quantify the resources required for computation of basic problems.


  1. Automata
  2. Turing machines
  3. Deterministic and non-deterministic finite automata
  4. Formal language theory
  5. Computability and non-computability
  6. Turing computability
  7. Analysis of Algorithms
  8. Complexity measures
    • time and storage
    • communications
    • numbers of processors
  9. Big O notation
  10. Best, worst, and average complexity
  11. Upper and lower bounds on complexity
  12. Classes of Complexity
    • P and NP
    • Intractability


NICE Framework Categories[edit]

CSEC 2017 Categories[edit]

Specialization Areas[edit]


See also[edit]

Related Knowledge Units

Further reading[edit]

Suggested textbooks[edit]

Suggested academic readings[edit]

Sample knowledge test[edit]

Sample skills test[edit]

Sample abilities test[edit]

Additional notes or materials[edit]


Reference ID[edit]