計算理論的主要主題

The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church’s thesis; universal algorithms, undecidability and intractability; time and space complexity, nondeterminism, probabilistic computation and reductions of computational problems.
CS 332: Elements of the Theory of Computation, Fall 2021

Course Overview

This course is an introduction to the theory of computation. This is the branch of computer science that aims to understand which problems can be solved using computational devices and how efficiently those problems can be solved. To be able to make precise statements and rigorous arguments, computational devices are modeled using abstract mathematical “models of computation.” The learning objectives of the course are to:

Foremost, understand how to rigorously reason about computation through the use of abstract, formal models.
Learn the definitions of several specific models of computation including finite automata, context-free grammars, and Turing machines, learn tools for analyzing their power and limitations, and understand how they are used in other areas of computer science.

Learn how fundamental philosophical questions about the nature of computation (Are there problems which cannot be solved by computers? Can every problem for which we can quickly verify a solution also be solved efficiently?) can be formalized as precise mathematical problems.

Gain experience with creative mathematical problem solving and develop the ability to write correct, clear, and concise mathematical proofs.

Instructor:
 
Mark Bun, mbun [at] bu [dot] edu

Instr. Office Hours:
 
Mon 5:00-6:00 PM (MCS 114)

 
 
Fri 5:00-6:00 PM (MCS 114)

Teaching Fellow:
 
Islam Faisal, islam [at] bu [dot] edu

TF Office Hours:
 
Tue 5:00-6:00 PM (MCS B21)

 
 
Thu 4:00-5:00 PM (MCS B21)

Class Times:
 
Tue, Thu 2:00-3:15 PM (EPC 209)

Discussion Sections:
 
Wed 11:15-12:05 AM (MCS B31)

 
Wed 12:20-1:10 PM (KCB 104)

Important Links

Course Website: https://cs-people.bu.edu/mbun/courses/332_F21. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.

Piazza: https://piazza.com/bu/fall2021/cs332. All class announcements will be made through Piazza, so please set your notifications appropriately. Please post questions about the course material to Piazza instead of emailing the course staff directly. It is likely that other students will have the same questions as you and may be able to provide answers in a more timely fashion. Active participation on Piazza may add extra points to your participation grade.

Gradescope: https://gradescope.com. Sign up for a student account on Gradescope using your BU email address. The entry code for the course is 2RYZ3P. Homework assignments are to be submitted to Gradescope in PDF format.

Catalog Description

The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church’s thesis; universal algorithms, undecidability and intractability; time and space complexity, nondeterminism, probabilistic computation and reductions of computational problems.

Prerequisites

CS 131 (Combinatoric Structures) and CS 330 (Introduction to Algorithms). If you have not completed the prerequisites for the course, please schedule a meeting with me before registering.

Course Outline

Automata and Formal Language Theory. Deterministic finite automata, nondeterministic finite automata, regular expressions. Non-regular languages. Context-free grammars.

Computability Theory. Turing Machines and the Church-Turing thesis. Decidability, halting problem. Reductions.

Complexity Theory. Time complexity, space