Computability theory 1000-I1TOB

30h - lecture, 30h - exercises, 50h - self-study - preparation for classes and literature study 35h - self-study - preparation for the exam 5h - exam Together - 150h, 6p. ECTS

Students posses the basic knowledge of the theory of computation supported by the theoretical background. In particular, they know and understand: * universal models of computations * counter machines * Turing machines * the notions of decidability and partial decidability * the examples of decidable, partial decidable and undecidable problems in computer science theory * the notions of time and space computational complexity * the computational complexity classes and the relations between them * the notions of hardness and completeness of computational problems * the examples of hard and complete problems

(in Polish) Student potrafi: U1: potrafi wykorzystać wiedzę matematyczną oraz informatyczną do formułowania, analizowania i rozwiązywania problemów obliczeniowych (KU_01), w szczególności: w szczególności * odróżniać problemy rozstrzygalne i częściowo rozstrzygalne od nierozstrzygalnych * dowodzić obliczalność, rozstrzygalność oraz częściową rozstrzygalność typowych problemów matematycznych * dowodzić trudność i zupełność problemów obliczeniowych przez sprowadzenie do znanych problemów obliczeniowych U2: potrafi projektować oraz analizować rozwiązania problemów obliczeniowych pod kątem ich poprawności i złożoności obliczeniowej (KU_07) U3: potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie; (KU_02)

(in Polish) Student: KK1: skutecznie przekazuje innym swoje myśli w zrozumiały sposób (KK_02) KK2: właściwie posługuje się terminologią fachową (KK_02) KK3: potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę (KK_02) KK4: rozumie potrzebę ciągłego uczenia się i doskonalenia swoich umiejętności (KK_03)

- informative (conventional) lecture

compulsory course

Basic knowledge in mathematics and computer science, including the set theory, discrete mathematics, formal languages theory, algorithms and programming.

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

• Description of 1000-I1TOB in USOSweb