Theoretical computer science is a discipline dealing with systematic ways to process information, especially using computers. Key original concepts of theoretical computer science include:
- development of methods for problem-solving (theory of algorithms),
- theoretical models to construct computers, i.e. machines able to apply algorithms (automata theory),
- a foundation of computability theory itself, i.e. exploring which problems are tractable by applying automata performing algorithms.
Theoretical minimum (in a nutshell)
You should be acquainted with:
Concepts you will learn in this part of BookofProofs
- What are grammatics of formal languages?
- Learn about and explain the Chomsky hierarchy of language classes_?
- Learn about regular and context-free languages?
- What is computability and learn some not computable problems?
- What is complexity of computation and how to measure it?
- Learn about different complexity classes of problems.
| | | | created: 2014-02-20 21:28:35 | modified: 2020-05-04 18:46:43 | by: bookofproofs
3.Computational Complexity Theory