Church-Turing Thesis

Strings and encodings

Deterministic finite automaton (DFA)

Turing Machines

Universality

Stable Matching

Randomness

Cryptography

Decidability

Boolean Circuits

Randomized Algorithms

Interactive Proofs

Time Complexity

NP (complexity)

Modular arithmetic

Gödel's Incompleteness Theorems

Graphs

NP-completeness

Group Theory

Probability theory

Fields and Polynomials

Graph Algorithms

Matchings and Bipartite Graphs

Approximation Algorithms

Quantum Computation

15-251 Great Ideas in Theoretical Computer Science Carnegie Mellon University Fall 2018 The course provides a rigorous introduction to the foundations of computer science, improving abstract thinking skills and preparing students to be innovators in the field. Topics include computation, computational complexity, and real-world applications of computational concepts. Prerequisites imply this is an intermediate-level course.  Broadly speaking, the course has several goals. First, it provides a rigorous/formal introduction to the foundations of computer science, which is the science that studies computation in all its generality. An important component of this is improving your analytic and abstract thinking skills since nature's language is mathematics. Second, the course intends to prepare you to be innovators in computer science by presenting some of the great ideas that people in the past have contributed to science and humanity. We hope that you will learn from their examples. Third, the course gives you opportunities to improve your social skills by emphasizing cooperation, clarity of thought, and clarity in the expression of thought.

More specifically, some of the main learning objectives are the following.

- Define mathematically the notions of computation, computational problem, and algorithm.
- Express, analyze and compare the computability and computational complexity of problems.
- Use mathematical tools from set theory, combinatorics, graph theory, probability theory, and number theory in the study of computability, computational complexity, and some of the real-world applications of computational concepts.
- State and explain the important and well-known open problems in the theory of computation.
- Write clearly presented proofs that meet rigorous standards of correctness and conventional guidelines on style.
- Identify and critique proofs that are logically flawed and/or do not meet the expected standards of clarity.
- Cooperate with other people in order to solve challenging and rigorous problems related to the study of computer science.

Note that even though all of the topics we discuss in the course have real-world applications, often we will not be explicitly discussing the applications. This is because initially it is better to separate concerns regarding real-world applications from the exploration of fundamental truths and knowledge that shape how we view and understand the world. The quest for truth and understanding, wherever it takes us, eventually do produce applications, some that we hoped to achieve, and some that were beyond our wildest dreams. The focus of the course is on that quest for truth and understanding, which is arguably more important than specific applications. The formal prerequisites for the course are (15-122 or 15-150) and (21-127 or 21-128 or 15-151). In particular, we expect the students to have taken an introductory computer science course that goes beyond basic computer programming and covers algorithmic thinking. On the mathematics side, we expect the students to have experience reasoning abstractly and know how to write formal proofs. 

15-251 Great Ideas in Theoretical Computer Science

Theoretical Computer Science

Church%E2%80%93Turing thesis

Church-Turing Thesis

1 courses cover this concept

15-251 Great Ideas in Theoretical Computer Science