# Introduction to Theory of Computation (2020)

From CyberEdWiki

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.

## Contents

## Outcomes[edit]

To complete this KU, students should be able to:

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

## Topics[edit]

- Automata
- Turing machines
- Deterministic and non-deterministic finite automata
- Formal language theory
- Computability and non-computability
- Turing computability
- Analysis of Algorithms
- Complexity measures
- time and storage
- communications
- numbers of processors

- Big O notation
- Best, worst, and average complexity
- Upper and lower bounds on complexity
- Classes of Complexity
- P and NP
- Intractability

## Skills[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