|
|
Course Basics
|
CPSC 046 / MATH 046
|
Tuesday, Thursday 9:55am-11:10am, Science Center 181
|
| Lab A: |
Monday 1:15pm - 2:45pm, Clothier 016 |
| Lab B: |
Monday 3:00pm - 4:30pm, Clothier 016 |
| Instructor: |
Lila Fontes |
| Email: |
fontes at cs.swarthmore.edu |
| Office: |
Science Center 258 |
| Office Hours: |
Th 2:15-4:15pm, F2-4pm, and by appointment |
| Textbook: |
Introduction to the Theory of Computation, Third
Edition by Sipser.
Errata.
|
| Clickers: |
You will need an iClicker (physical device, not the app) for
this class. Register your iClicker here.
|
| Course Discussion: |
Piazza
(mandatory enrollment)
|
| Lab assignments: | weekly, due Sunday 11:59pm
|
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? Do other methods of computation even exist? Could
we solve more interesting problems with another model?
Along the way, this course will develop mathematical concepts
which are fundamentally important for computer science:
decidability, undecidability, and computational complexity. We
will go beyond simply saying "this problem seems hard"
and show that some computational problems are inherently harder
than others, 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, this
course aims to teach students how to describe and to reason
precisely about computational objects.
|