Kaisa_2012_3_photo by Veikko Somerpuro

Ilmoittaudu
14.8.2017 klo 09:00 - 13.12.2017 klo 23:59
Moodle
Kirjaudu sisään nähdäksesi Moodlen kurssiavaimen.

Viestit

Lisää uusi viesti

Käyttäjän Åsa Hirvonen kuva

Åsa Hirvonen

Julkaistu, 9.12.2017 klo 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).

Käyttäjän Åsa Hirvonen kuva

Åsa Hirvonen

Julkaistu, 1.9.2017 klo 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).

Aikataulu

Tästä osiosta löydät kurssin opetusaikataulun. Tarkista mahdolliset muut aikataulut kuvauksesta.

PäivämääräAikaOpetuspaikka
Ma 4.9.2017
10:15 - 12:00
Ma 11.9.2017
10:15 - 12:00
Ti 12.9.2017
10:15 - 12:00
Ma 18.9.2017
10:15 - 12:00
Ti 19.9.2017
10:15 - 12:00
Ma 25.9.2017
10:15 - 12:00
Ti 26.9.2017
10:15 - 12:00
Ma 2.10.2017
10:15 - 12:00
Ti 3.10.2017
10:15 - 12:00
Ma 9.10.2017
10:15 - 12:00
Ti 10.10.2017
10:15 - 12:00
Ma 16.10.2017
10:15 - 12:00
Ti 17.10.2017
10:15 - 12:00
Ma 30.10.2017
10:15 - 12:00
Ti 31.10.2017
10:15 - 12:00
Ma 6.11.2017
10:15 - 12:00
Ti 7.11.2017
10:15 - 12:00
Ma 13.11.2017
10:15 - 12:00
Ti 14.11.2017
10:15 - 12:00
Ma 20.11.2017
10:15 - 12:00
Ti 21.11.2017
10:15 - 12:00
Ma 27.11.2017
10:15 - 12:00
Ti 28.11.2017
10:15 - 12:00
Ma 4.12.2017
10:15 - 12:00
Ti 5.12.2017
10:15 - 12:00
Ma 11.12.2017
10:15 - 12:00
Ti 12.12.2017
10:15 - 12:00

Muu opetus

06.09. - 18.10.2017 Ke 10.15-12.00
01.11. - 29.11.2017 Ke 10.15-12.00
13.12.2017 Ke 10.15-12.00
Lauri Ylinen
Opetuskieli: englanti

Materiaalit

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

Tehtävät

Kurssin suorittaminen

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.

Kuvaus

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