Theory of Computation
 |
This page is a stub article. It begs for completion. Help finish this page! Sign in and edit. |
Theory of Computation (TCOM) is a Computer Science course in the CTY program. It is offered only at Lancaster.
Course Description
From the CTY Course Catalog (2018):
Beyond programming lies a deeper understanding and appreciation of elegance in computing. In this advanced computer science class, students work with a series of mathematical models of computation to discover what is possible and impossible in the digital world, as well as gain a robust understanding of complexity in computer science.
Starting with the simplest computer models, deterministic finite automata, students build up to increasingly complicated models, including Turing machines, which are equivalent in power to any algorithm for solving problems. They next investigate computational problems that are fundamentally unsolvable, regardless of available computing power. Students also explore problems such as the Traveling Salesman, a problem that is computationally difficulty to solve but for which a potential solution is easily checked. Students then turn to the field of complexity theory, studying the computing resources different problems require in terms of both time and memory, as well as delving into the issue of P vs. NP, the most important unsolved computer science problem of our time. By the end of the course, students have a deeper understanding of ways to answer the question, “What exactly can a computer do?”
Course History
TCOM split off from CPS1 in 2001, and CPS1 became defunct.
