hours:
Tuesday 13.15 --
15.--
Zaal P 017
Thursday 11.15 --
13.--
Zaal A 303 ; starting Feb 25 Tuesday 11.15 -
13.--
Zaal P 017.
Scheme of classes:
Week Tuesday Thursday
02
Jan 07 Intro:
know your numbers
Jan 09 Intro: Chapt 1
Papadimitriou
03
Jan 14 Intro:
tiling puzzel
Jan 16 Papadimitriou ch. 1 vervolg
04
Jan 21 1-tape TM
model
Jan 23 Gebruik TM model; k-tape model
05
Jan 28 (No Class:
abroad)
Jan 30 (No Class: abroad)
06
Feb 04 The 2-dim. tape
case
Feb 06 No Class: ph.d. thesis
I. Vermeulen
07
Feb 11 Random Access Machines Feb
13
Time ans Space on RAM model; Minsky theorem
08
Feb 18 (Midterm Exam
weeks)
Feb 20 (Midterm Exam weeks)
STARTING FEB 25 the Thursday meeting will move to Tuesday 11.15 - 13.-- Zaal P 017
09
Feb 25
Feb 25 Universal TM; Undecidability,
Diagonalization
methods
10
Mar
04
Mar 04 Abstract complexity theory, Fundamental
Complexity
classes
11
Mar
11
Mar 11 Hierarchy theorems, Savitch,
Immerman-Szelepczenyi
12
Mar
18
Mar 28 Elementary Reduction Theory
13
Mar 25 (Exam
weeks)
Mar 25 (Exam weeks)
14
Apr 01 (Exam
weeks)
Apr 01 (Exam weeks)
TheExcercise
Page is now open.
Course Contents:
The class of mathematical
problems
that can be solved using a computer can be
devided into subclasses,
depending
on the amount of time and/or memory
required for solving these
problems.
There are easy and hard problems.
Given the intuitive
transparency
of this distinction, it is quite disappointing that
it requires serious effort to
make this distinction formal. In particular,
making the difference
independent
of the machine model used is one of the
major achievements of the
branch
in computer science called Complexity Theory.
This course will focus on
the
basic machine models used in computation theory
and their corresponding
measures
for time and memory usage. The behavior of
their mutual simulations will
establish the required invariance of the complexity
classes defined using these
machine models.
Special attention will be
given
to the basic method for classifying problems
by their complexity: the
reduction
of one problem to another. This notion
is crucial in defining the
classes
P of tractable problems and the classes NP
and PSPACE of problems
presumed
to be intractable. The class NP is well
known on behalf of important
problems included in this class like the Traveling
Salesman problem
Course Implementation:
The course will closely
follow
the book by
Papadimitriou: Computational
Complexity, listed in the references below.
Don't forget to look at the
excercises
in the book;
they refer to lots of
interesting
material and some of them will be
discussed.
Sheets available: (will be opened according to progress in class)
Topics: Know
thy
Numbers:
Available in Powerpoint98
format
Topics:
Diagonalization
and Compression:
Available in Powerpoint98
format and pdf
format
No additional material so
far
has been made available for this course.
See however the material for
the related courses.
Reference Material Made
available
in Library: (will be extended
during
the course)
(don't
copy copyrighted material!)
P. van Emde Boas, Complexiteit
van verzamelingenmanipulatie,
voordracht uit het MC
Colloquium
Capita datastructuren, MC Syllabus 37, 43 -- 63, 1978 (in
Dutch).
More detailed popular expose
on the role of data structures in Algorithms Design.
P. van Emde Boas, Machine
Models and Simulations, form J. van Leeuwen, ed.
Handbook of Theoretical
Computer
Science, Vol. A, 1990, 3 -- 66.
A survey on Invariance issues
in Machine models covering far more material
than chapter 2 in
Papdimitriou's
book.
Literature:
(may
be extended during the course).
Computation Theory.
John E. Hopcroft &
Jeffrey
D. Ullman, Intorduction to Automata Theory,
Languages and Computation,
Addison Wesley, 1979.
David Harel, Algorithmics;
the Spirit of Computing, (second Edition),
Addison Wesley 1992.
A miniature version of this
material
appears in:
David Harel, Computers
Ltd.
; what they really can't do,
Oxford Univ. Press, 2000
Thomas A. Sudkamp, Languages
and Machines; An Introduction to the
Theory of Computer Science,
(second Edition), Addison Wesley 1997.
the previously used textbook
for the course Automata
and Complexity Theory
Harry R. Lewis &
Christos
H. Papadimitriou,
Elements of the Theory of
Computation, Prentice Hall 1981.
Christos H. Papadimitriou, Computational
Complexity,
Addison Wesley 1995.
Course Evaluation:
The course will be evaluated
on the basis of homework excercises
which will be handed out
during
the course.
Homework excercises may be
discussed
in class upon expiration
of the submission deadline.
Based on the problematic experiences during
the previous course electronic
submission of solutions will
not be accepted.
Related courses:
dr. Peter van Emde Boas: Theoretical Models (2nd trimester): Games and Computer Science
dr. Peter van Emde
Boas:
Intelligent Databases / Game Theory (3rd trimester): Intelligent
Databases