University of Warsaw - Central Authentication System

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:	(in Polish) Przedmioty obieralne dla II-III roku bioinformatyki (dla programu studiów od roku 2021/22) Elective courses for 3rd grade Bioinformatics
ECTS credit allocation (and other scores):	6.00 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. 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 2023/24" (past)

Time span:	2023-10-01 - 2024-01-28	Selected timetable range: weekly course term Navigate to timetable MO TU WYK CW W TH FR
Type of class:	Classes, 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 2024/25" (future)

Time span:	2024-10-01 - 2025-01-26	Selected timetable range: weekly course term Navigate to timetable
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Paweł Urzyczyn
Group instructors:	Adam Cicherski, Paweł Urzyczyn
Students list:	(inaccessible to you)
Examination:	Examination

Course descriptions are protected by copyright.
Copyright by University of Warsaw.