University of Warsaw - Central Authentication SystemYou are not logged in | log in
course directory - help

Complexity theory

General data

Course ID: 1000-716ZOB Erasmus code / ISCED: (unknown) / (unknown)
Course title: Complexity theory Name in Polish: Złożoność obliczeniowa
Organizational unit: Faculty of Mathematics, Informatics, and Mechanics
Course groups: Elective courses for 3rd grade Bioinformatics
ECTS credit allocation (and other scores): 6.00
view allocation of credits
Language: Polish
Type of course:

obligatory courses

Short description:
Full description:

Course content:

Formal languages, theory of computation (undecidable problems), complexity theory (NP-complete problems), approximation algorithms, randomized algorithms, parallelism.

Bibliography:

* Sipser, M., Wprowadzenie do teorii obliczeń. WNT 2009.

* Harel, D., Feldman, Y., Rzecz o istocie informatyki: Algorytmika. wyd. 4., WNT 2008.

* Papadimitriou, Ch. H., Złożoność obliczeniowa. WNT 2002.

Learning outcomes:

(KW_01) has an in-depth knowledge in branches of maths necessary to study bioinformatics

(KW_02) well understsnds the role and importance of mathematical constructions and mathematical reasoning

(K_U01) has the ability to perform mathematical reasoning

(K_U02) can express computational problems in the language of mathematics

(K_U04) can design algorithms using the bacic models of computation: Turing

machines, boolean circuits

(K_U05) can identify membership and hardness of computational problems with respect to the important complexity classes: NC, P, NP, PSPACE,

using their various characterizations

Assessment methods and assessment criteria:

Written exam.

Those who have completed their homework assignments and declared their readiness for the exam no later than January 7, can take the zero exam.

Classes in period "Winter semester 2021/22" (past)

Time span: 2021-10-01 - 2022-02-20
Choosen plan division:


magnify
see course schedule
Type of class: Class, 30 hours more information
Lecture, 30 hours more information
Coordinators: Paweł Urzyczyn
Group instructors: Paweł Urzyczyn
Students list: (inaccessible to you)
Examination: Examination

Classes in period "Winter semester 2022/23" (future)

Time span: 2022-10-01 - 2023-01-29
Choosen plan division:


magnify
see course schedule
Type of class: Class, 30 hours more information
Lecture, 30 hours more information
Coordinators: Paweł Urzyczyn
Group instructors: Paweł Urzyczyn
Students list: (inaccessible to you)
Examination: Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.