Complexity theory 1000-716ZOB
Formal languages, theory of computation (undecidable problems), complexity theory (NP-complete problems), approximation algorithms, randomized algorithms, parallelism.
Type of course
(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
Those who have completed their homework assignments and declared their readiness for the exam no later than January 7, can take the zero exam.
* 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 (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: