Theory of Computation

From RealCTY
Jump to: navigation, search
Part of a series on
Realcty logo 20060831.png
CTY Courses
Category · Template · CAA Courses
Sites
Baltimore · Carlisle · Lancaster · Los Angeles · Saratoga Springs · Seattle
Humanities
Logic: PoR
International Politics · Law and Politics in US History
Ethics · Existentialism
Philosophy of Mind
Cognitive Psychology · Linguistics
Dissent
Newton, Darwin, and Einstein
The Art and Science of Filmmaking
Writing
Writing Your World · The Art of Fiction
Fiction and Poetry
Utopias and Dystopias
Persuasion and Propaganda
Math
Individually Paced Mathematics Sequence
Probability and Game Theory
Number Theory · Mathematical Logic
Cryptology · Advanced Cryptology
Topology
Economics
Macroeconomics and the Global Economy
Fundamentals of Microeconomics
Computer Science
Data Structures and Algorithms
Fundamentals of Computer Science
Theory of Computation
Science
FPHS Biology · FPHS Chemistry · FPHS Physics
Astrophysics
Paleobiology · Genetics · Neuroscience
Investigations in Engineering
Introduction to Biomedical Sciences · Electrical Engineering
Special Relativity · Intro to Organic Chemistry
Princeton
Global Politics: Human Rights and Justice
Human Nature and Technology
Politics and Film · Epidemiology
The Mathematics of Competitive Behavior
Science, Technology and Public Policy
Race and Politics · Politics in the Middle East
The Global Environment
Civic Leadership Institute (PBD/BRK)
Service, Leadership & Community Transformation
Defunct Courses
Beginning Ancient Greek · German 1
German 2
Latin 2
French 1 · French 2
Great Revolutions
American History
Modern European History · Eastern European History
Music Theory
History of Western Art
Renaissance Art
Introduction to American Studies: Race and Class
Medieval Art
Twentieth Century Art · Gandhi's India
American Studies: The Sixties · Women and US Social Reform
American Studies: The Harlem Renaissance
Intermediate Ancient Greek
Islam · The Asian Pacific Rim
Russian History
TCE: Literature and the Arts · TCE: Popular Culture
The Crafting of Drama
The Crafting of Poetry · TCE: Shakespeare
TCE: Science Fiction
TCE: Beyond the Ring and the Wardrobe
Advanced Mathematical Modeling
Advanced Mathematical Reasoning
Statistics · Calculus: A Conceptual Approach
Topics in Precalculus
Set Theory · Digital Logic
Theoretical Foundations of Computer Science
Introduction to Laboratory Sciences · Archaeology
Ecology
Microbiology · Selected Topics in Advanced Biology
Selected Topics in Advanced Chemistry
Selected Topics in Advanced Physics · Physical Anthropology
Advanced Physics: Mechanics
Scientific Investigations: St. Mary's River · Genomics
Volcanoes
Etymologies · Oceanography: The Hawaiian Pacific
Life Cycle of an Island: Hawaii
The History of Disease · The Critical Essay: Film
Wicked Art: Pictures, Pixels, and Pens
Latin I
Goodwives and Witches: Women in Colonial America
Freaks and Geeks in Popular Media
The Digital Revolution
Advanced Robotics
Playing God: The Ethics of Human Subjects Research

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.