Document Type
Syllabus
Publication Date
Fall 9-1-2024
Course Description
Theory of computation is the branch of computer science (and mathematics) that deals with how efficiently problems can be solved using a particular algorithm and model of computation. This field is divided into three basic branches: automata theory (and languages), computability theory, and computational complexity theory. These three branches are linked in their attempt to answer the question “What are the fundamental capabilities and limitations of computers?” Automata Theory is the study of abstract machines and automata, and the computational problems that can be solved using them. Automata comes from a Greek word meaning “self-acting.” Automata theory is closely related to formal language theory. An automaton is a finite representation of a formal language (that may be an infinite set). Different types of automata are classified by the class of formal languages that they can recognize. Computability Theory addresses the questions of what it means for a function to be computable, as well as the question of determining levels of non-computability and arranging functions within those levels. The field has also grown to include the study of generalized computability and definability. Computational Complexity Theory focuses on classifying computational problems according to their inherent difficulty. It continues with relating those classes to each other. A computational problem is understood to be a task that is amenable to being solved by a computer, which means it could be solved by a mechanical application of mathematical steps (an algorithm). This class should be useful to computer science majors in many ways. It will improve your ability to understand the efficiency of algorithms in general, regardless of programming language. It has direct application in cryptography, natural language processing, and quantum computing, among other fields. It will allow you to speak formally about algorithms.
Recommended Citation
Thede, Scott, "CSC 440A Theory of Computation Thede Fall 2024" (2024). All Course Syllabi. 720, Scholarly and Creative Work from DePauw University.
https://scholarship.depauw.edu/records_syllabi/720
Student Outcomes
Students who successfully complete this course will be able to do the following: Solve problems using finite-state automata of various types, and describe the operation of various finite-state automata, including DFAs, NFAs, and -NFAs Solve problems using regular expressions, and describe the operation of various regular expressions Describe various characteristics of regular languages Describe the characteristics and operations of context-free grammars Solve problems and write languages using context-free grammars Solve problems using push-down automata, describe the operation of various push-down automata, and explain the connection between CFGs and PDAs Describe the characteristics of context-free languages Describe the differences between various non-context-free languages Solve problems using Turing machines, and describe the operation of various Turing machines Describe and define recursively enumerable languages and their connection to Turing machines Describe how problems are proven unsolvable, and what it means for problems to be unsolvable Describe the concept of various levels of computational complexity, and what it means for a problem to be P, NP, NP-complete, P-SPACE, and other complexities.