skip navigation

This page looks better in modern browsers. Please upgrade.

Brown Home Brown Home Brown Home Brown CS

CSCI0510

(Formerly CS051 )

Models of Computation

Instructor(s):
Anna Lysyanskaya
Course Home Page:
http://www.cs.brown.edu/courses/csci0510/
Location: CIT 368
Meeting Time: Mon, Wed 9:30-10:50
Exam Group: 03
Semester: 1
Offered This Year?  Yes
When Offered? Every Year

Description

This course introduces basic models of computation including languages, finite-state automata and Turing machines. Proves fundamental limits on computation (incomputability, the halting problem). Provides the tools to compare the hardness of computational problems (reductions). Introduces computational complexity classes (P, NP, PSPACE and others). Prerequisite: CSC0220.

Edit this page
Page Owner: webmaster Last Modified: Wed Sep 3 12:06:24 2008