Complexity theory
General data
Course ID:  1000716ZOB  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 (NPcomplete 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 indepth 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:  20211001  20220220 
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:  20221001  20230129 
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 
Copyright by University of Warsaw.