Kaisa_2012_3_photo by Veikko Somerpuro

Anmäl dig
14.8.2017 kl. 09:00 - 13.12.2017 kl. 23:59
Moodle
Logga in för att se kursnyckeln för Moodle.

Meddelande

Åsa Hirvonen

Publicerad, 9.12.2017 kl. 17:37

I added a 14th set of exercises as practice for the exam. They are not supposed to be a preview of the exam, but going through them will probably help in preparing for the exam. Choose which ones you want to look at in class on Wednesday, as we won't have time for all.
Also, these exercises are not counted for the exercise points for the course (i.e. completely voluntary to do).

Åsa Hirvonen

Publicerad, 1.9.2017 kl. 19:27

Due to the lecturer's sick leave, the lectures will only start on week 37 (i.e., Mon 11.9.). However, exercises start already on Wed 6.9. - assignments will appear shortly. In the meantime, read the introduction and chapter 0 of the book (intro + chapter 1.1 of web draft).

Tidsschema

I den här delen hittar du kursens tidsschema. Kontrollera eventuella andra tider i beskrivning.

DatumTidPlats
mån 4.9.2017
10:15 - 12:00
mån 11.9.2017
10:15 - 12:00
tis 12.9.2017
10:15 - 12:00
mån 18.9.2017
10:15 - 12:00
tis 19.9.2017
10:15 - 12:00
mån 25.9.2017
10:15 - 12:00
tis 26.9.2017
10:15 - 12:00
mån 2.10.2017
10:15 - 12:00
tis 3.10.2017
10:15 - 12:00
mån 9.10.2017
10:15 - 12:00
tis 10.10.2017
10:15 - 12:00
mån 16.10.2017
10:15 - 12:00
tis 17.10.2017
10:15 - 12:00
mån 30.10.2017
10:15 - 12:00
tis 31.10.2017
10:15 - 12:00
mån 6.11.2017
10:15 - 12:00
tis 7.11.2017
10:15 - 12:00
mån 13.11.2017
10:15 - 12:00
tis 14.11.2017
10:15 - 12:00
mån 20.11.2017
10:15 - 12:00
tis 21.11.2017
10:15 - 12:00
mån 27.11.2017
10:15 - 12:00
tis 28.11.2017
10:15 - 12:00
mån 4.12.2017
10:15 - 12:00
tis 5.12.2017
10:15 - 12:00
mån 11.12.2017
10:15 - 12:00
tis 12.12.2017
10:15 - 12:00

Övrig undervisning

06.09. - 18.10.2017 ons 10.15-12.00
01.11. - 29.11.2017 ons 10.15-12.00
13.12.2017 ons 10.15-12.00
Lauri Ylinen
Undervisningsspråk: Engelska

Material

We follow approximately chapters 1-5 of the book Arora, S., Barak, B. Computational Complexity: A Modern Approach. A draft of the book is available on the authors' page http://theory.cs.princeton.edu/complexity/

Other recommended texts are
C. H. Papadimitriou: Computational complexity (1994)
J. Paris: Computational Complexity (lecture notes, 2007-08), available at http://www.maths.manchester.ac.uk/~jeff/lecture-notes/MATH63011.ps

Uppgifterna

Kursbeskrivningen

The course is evaluated based on a final exam and the exercises the student solved during the course.
The course exam will be organized in the December general exam of the department (13.12. at 16-20). A second possibility is offered in the January general exam.

Beskrivning

Optional course.

Master's Programme in Mathematics and Statistics is responsible for the course.

The course belongs to the Mathematics and Applied mathematics module.

The course is available to students from other degree programmes.

Routine in mathematics

Master studies

The course is an introductory course to computational complexity theory.

Recommended time/stage of studies for completion: 1. or 2. year

Term/teaching period when the course will be offered: varying

Turing machines, basic complexity classes, hierarchy theorems, reductions and completeness

C. H. Papadimitriou: Computational complexity (1994); S. Arora and B. Barak: Computational complexity: a modern approach (2009)

Lectures and exercise classes

Exam and excercises, Course will be graded with grades 1-5

Exam, other methods will be described later