Computer Science
CS 3800: Theory of Computation
Lecture - 4 credits
ND
EI
IC
FQ
SI
AD
DD
ER
WF
WD
WI
EX
CE
- Introduces the theory behind computers and computing aimed at answering the question, “What are the capabilities and limitations of computers?” Covers automata theory, computability, and complexity.
- The automata theory portion includes finite automata, regular expressions, nondeterminism, nonregular languages, context-free languages, pushdown automata, and noncontext-free languages.
- The computability portion includes Turing machines, the Church-Turing thesis, decidable languages, and the Halting theorem.
- The complexity portion includes big-O and small-o notation, the classes P and NP, the P vs.
- NP question, and NP-completeness.
Introduces the theory behind computers and computing aimed at answering the question, “What are the capabilities and limitations of computers?” Covers automata theory, computability, and complexity. Show more.