THEORY OF COMPUTATION
Syllabus for the course CS 5315, Spring 2005
Instructor: Vladik Kreinovich, office COMP 215, email
Class time: TR 6:00-7:20 pm, COMP 308
Office hours: TR 8:30-9:00 am, 12-12:30, 6-6:30, 7:30-8 pm, or by
Prerequisite: CS 3350
- to teach the foundations of computing, and
- to enable students to prove (not only to program).
- Turing's snakelike machine: not very fancy, but it can
compute anything (you just wait and wait and wait, ...). Finally:
something purely theoretical (and not real machines): recursive
functions. Church's bold statement: if anyone can compute anything
on any machine, I can compute it on a Turing snake! Universal
Turing machine. Can anyone really beat Church? We'll discuss the
attempts (Gandi, Kreisel, etc) if time allows.
You are accustomed to the fact that everything is computable, and if your
program does not work, that means a bad grade. Finally! Only in
this course! Computational problems that cannot be
solved! (and so you get a
bad grade, if your program solves them - just kidding).
- If a program requires a billion years to finish its computations,
only a crazy
theoretician can call it an algorithm. So, to sound more
reasonable, we will talk about computational complexity, realistic
(polynomial-time) computations, P and NP, NC, limitations on space
and on the number of processors, etc. "P=NP?" as a challenge to
mankind. Will science ever stop? Again, we will find here lots of
undecidability results. And maybe, as a project, you will be able
to prove that some problem that you were planning to solve is
- What to do if your problem turned out to be undecidable? For
sure: not to give up. It can be still decidable in some sense: for
almost all cases, by a Monte-Carlo algorithm that gives an answer
with probability close to 1, etc.
Few results and lots of open problems.
- Turing machine was invented in the 30s, P=NP problem appeared
when many of you guys were too young to count. What is
the modern state of the Theory of Computation? We'll try to cover
- algebraic computations,
- computations with real data
(including the idea of interval mathematics),
- fuzzy algorithms,
- neural computing,
- chemical computing,
- quantum computations, etc.
(Turn over, please)
After a few lectures, you will be
given a list of projects to choose from (or you may be smart enough to
propose something on your own). These projects will include mainly
theory; you'll have to read, analyze and discuss some theoretical
paper, and ideally come out with some new ideas (don't be afraid;
Nobel prize is desirable for an A, but not necessary).
MAIN SOURCE: Michael Sipser, Introduction to the Theory of
Computation, PWS Publishing Co.
TESTS AND GRADES: There will be two tests and one final exam.
Each topic means home assignments (mainly on the sheets of paper,
but some on the real computer). Some of them may be graded.
Maximum number of points:
(smart projects with ideas that can turn into
a serious scientific publication
get up to 40 points).
- first test: 10
- second test: 25
- home assignments: 10
- final exam: 35
- project: 20
A good project can help but it cannot completely cover possible
deficiencies of knowledge as shown on the test and on the
homeworks. In general, up to 80 points come from tests and home
- to get an A, you must gain, on all the tests and home assignments,
at least 90% of the possible amount of points (i.e., at least 72), and
also at least 90 points overall;
- to get a B, you must gain, on all the tests and home assignments,
at least 80% of the possible amount of points (i.e., at least 64), and
also at least 80 points overall;
- to get a C, you must gain, on all the tests and home assignments,
at least 70% of the possible amount of points (i.e., at least 56), and
also at least 70 points overall.
STANDARDS OF CONDUCT:
Students are expected to conduct themselves in a
professional and courteous manner, as prescribed by the
Standards of Conduct.
Students may discuss programming
exercises in a general way with other students, but the solutions must be
done independently. Similarly, groups may discuss project assignments with
other groups, but the solutions must be done by the group itself. Graded
work should be unmistakably your own. You may not transcribe or copy a
solution taken from another person, book, or other source, e.g., a web
page). Professors are required to - and will -
report academic dishonesty and
any other violation of the Standards of Conduct to the Dean of Students.
If you feel you may have a disability that requires
accommodation, contact the Disabled Student Services Office at 747-5148, go
to Room 106 E. Union, or e-mail to
SEE Y'ALL IN THE CLASS!