Swedish web site
Computation III2004HT
|
|
Course plan
Lectures
Recommended for
Those interested in computability issues and complexity theory.
The course was last given
new
Goals
To give basic knowledge about computability and complexity theory.
Prerequisites
CUGS Computation II or similar. Mathematical maturity is essential
Contents
Basic computability theory, complexity classes (P, NP, PSPACE...), reductions, approximability, randomness.
Organization
Intensive course
Literature
Bovet, D.P., Crescenzi, P.: Intoduction to the Theory of Complexity, Prentice
Hall, 1994
Detailed reading list will be given later together with a detailed course
description.
Lecturers
Examiner
Peter Jonsson
Examination
Two sets of exercises. Deadlines will be decided later.
Credit
3 p
Organized by
Given by Department of Computer Science, Linköping University
Comments
The course will be given during autumn 2004. The exact course format will be
decided when the number of students is known. Please register as soon as
possible if you intend to attend this course.
Important note: Consider the possibility of following the ugrad-course TDDB41
instead of Computation III. The contents of the courses are the same but there
are more time for presenting the material and, more importantly, discussing it
in TDDB41. Also note that the examination is identical. TDDB41 is given during
spring 2004 (p. 2).
Course homepage: Not available yet. The TDDB41 homepage can be found here:
www.ida.liu.se/~petej/TDDB41/TDDB41.html
Page responsible: Director of Graduate Studies
