*Conducted in terms:*2020Z, 2021Z

*ECTS credits:*6

*Language:*Polish

*Organized by:*Faculty of Mathematics, Informatics, and Mechanics

# Complexity theory 1000-716ZOB

Course content:

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

## Type of course

## Course coordinators

## 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 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.

## 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.

## Additional information

Additional information (*registration* calendar, class conductors,
*localization and schedules* of classes), might be available in the USOSweb system: