Hide menu

Computation III

2004HT

Status Cancelled
School National Graduate School in Computer Science (CUGS)
Division SAS
Owner Anne Moe
Homepage http://www.ida.liu.se/zope/groups/cugs/CAC-ComputationIII

  Log in  




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
Last updated: 2012-05-03