Complexity theory 1000-716ZOB
Course content:
Formal languages, theory of computation (undecidable problems), complexity theory (NP-complete problems), approximation algorithms, randomized algorithms, parallelism.
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.
Notes
|
Term 2024Z:
None |
Additional information
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: