•    Employment
  •    Academia
  •    Research
    • NICE Framework
    • CAE Program

Introduction to Theory of Computation

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.

Topics

  1. Analysis of Algorithms
  2. Complexity measures
  3. Best, worst, and average complexity
  4. Upper and lower bounds on complexity
  5. Classes of Complexity
  6. Formal language theory

Outcomes

  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.

KSA-T

Below are the Knowledge, Skills, Abilities and Tasks (KSA-T) identified as being required to perform this work role.
Learn More about the KAS-T's.

  • Knowledge
  • Skills
  • Abilities
  • Tasks
ID DESCRIPTION
K0015 Knowledge of computer algorithms.
K0018 Knowledge of encryption algorithms
K0325 Knowledge of Information Theory (e.g., source coding, channel coding, algorithm complexity theory, and data compression).
ID DESCRIPTION
ID DESCRIPTION
ID DESCRIPTION