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.

Outcomes[edit]

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.

Topics[edit]

  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

Skills[edit]

NICE Framework Categories[edit]

CSEC 2017 Categories[edit]

Specialization Areas[edit]

none

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]

Contacts[edit]

Reference ID[edit]

ITC

Retrieved from "https://cyberedwiki.org//index.php?title=Introduction_to_Theory_of_Computation_(2020)&oldid=12648"