|
|
Course Basics
|
CPSC 046 / MATH 046
|
Monday, Wednesday, Friday 9:30AM - 10:20AM, Science Center 181
|
| Lab A: |
Wednesday 1:15pm - 2:45pm, Science Center 256 |
| Lab B: |
Wednesday 3:00pm - 4:30pm, Science Center 256 |
| Instructor: |
Lila Fontes |
| Email: |
fontes at cs.swarthmore.edu |
| Office: |
Science Center 243 |
| Office Hours: |
M 10:30-11:30, M 2-4,T 3-4, Th 1-3, and by appointment |
| Textbook: |
Introduction to the Theory of Computation, Third
Edition by Sipser.
Errata.
|
|
| Course Discussion: |
Piazza
(mandatory enrollment)
|
Welcome to CS46.
This course is an introduction to the formal systems that are
commonly used as abstract models for computational processes.
We will study a variety of computational models, and classify
and solve problems in each of them. While computers are now
ubiquitous and the idea of an algorithm seems natural, where did
these ideas originate? Why, for instance, do we have memory on
our machines --- is it necessary for computation, or simply a
convenience?
Along the way, this course will develop mathematical
concepts which are fundamentally important for computer science:
decidability, undecidability, and
computational complexity. We will ask if there are problems that
are inherently hard or simply unsolvable by computers. We will
examine the limits of computers and computation, and consider
the consequences of these limits.
By approaching these topics from a formal standpoint, it aims to
teach students how to describe and to reason precisely about
computational objects.
|