Module also offered within study programmes:
General information:
Name:
Computational Complexity
Course of study:
2019/2020
Code:
AMAT-2-015-MZ-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Mathematics in Management
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
dr Gőrlich Agnieszka (forys@agh.edu.pl)
Module summary

Pojęcia i twierdzenia teorii programowania (problemy rozstrzygalne i nierozstrzygalne) i teorii złożoności (klasy złożoności, problemy łatwe i NP.- trudne, schematy aproksymacyjne).

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 umie ocenić stopień zrozumienia przez siebie problemu, brakujące elementy rozumowania oraz stopień trudności zagadnień matematycznych MAT2A_K07, MAT2A_K02, MAT2A_K01 Activity during classes,
Oral answer
Skills: he can
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń, m.in. logiki predykatów i formalizmów funkcyjnych MAT2A_W02, MAT2A_W04, MAT2A_U13, MAT2A_U02, MAT2A_U03, MAT2A_W05 Activity during classes,
Test,
Oral answer
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z teorii programowania ( konstruować automaty i maszyny dla nowych problemów, decydować o rozstrzygalności problemów) i teorii złożoności (decydować o klasie złożoności problemu rozstrzygalnego) MAT2A_U19, MAT2A_U14, MAT2A_U01, MAT2A_W02, MAT2A_K02, MAT2A_U13, MAT2A_U02, MAT2A_U03, MAT2A_K01, MAT2A_U21 Activity during classes,
Test,
Oral answer
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (teoria algorytmów, logika) MAT2A_U19, MAT2A_U14, MAT2A_U04, MAT2A_W07, MAT2A_U08 Activity during classes,
Test,
Oral answer
Knowledge: he knows and understands
M_W001 zna podstawowe pojęcia i twierdzenia teorii programowania (problemy rozstrzygalne i nierozstrzygalne) i teorii złożoności (klasy złożoności, problemy łatwe i NP.- trudne, schematy aproksymacyjne) MAT2A_U19, MAT2A_W02, MAT2A_W04, MAT2A_U13, MAT2A_U02, MAT2A_W05 Activity during classes,
Test,
Oral answer
M_W002 rozumie potrzebę wprowadzenia formalizmu obliczeniowego oraz zna różne przykłady modelowania matematycznego wykorzystującego automaty, maszyny ze stopem i bez stopu, abstrakcyjny język programowania ( lambda rachunek) oraz formalizm funkcyjny MAT2A_U19, MAT2A_U14, MAT2A_U04, MAT2A_K05, MAT2A_U03 Activity during classes,
Test,
Oral answer
M_W003 zna podstawy teoretyczne ograniczeń obliczeniowych dla problemów modelowanych algorytmicznie oparte na teorii programowania (rozstrzygalności) oraz na teorii złożoności MAT2A_W11, MAT2A_U19, MAT2A_W08, MAT2A_K05, MAT2A_K01, MAT2A_U21 Activity during classes,
Test,
Oral answer
M_W004 zna najważniejsze fakty z historii teorii programowania i złożoności oraz wybrane nierozstrzygnięte hipotezy MAT2A_W06, MAT2A_W03, MAT2A_K05 Activity during classes
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 umie ocenić stopień zrozumienia przez siebie problemu, brakujące elementy rozumowania oraz stopień trudności zagadnień matematycznych + + - - - - - - - - -
Skills
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń, m.in. logiki predykatów i formalizmów funkcyjnych + + - - - - - - - - -
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z teorii programowania ( konstruować automaty i maszyny dla nowych problemów, decydować o rozstrzygalności problemów) i teorii złożoności (decydować o klasie złożoności problemu rozstrzygalnego) + + - - - - - - - - -
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (teoria algorytmów, logika) + + - - - - - - - - -
Knowledge
M_W001 zna podstawowe pojęcia i twierdzenia teorii programowania (problemy rozstrzygalne i nierozstrzygalne) i teorii złożoności (klasy złożoności, problemy łatwe i NP.- trudne, schematy aproksymacyjne) + + - - - - - - - - -
M_W002 rozumie potrzebę wprowadzenia formalizmu obliczeniowego oraz zna różne przykłady modelowania matematycznego wykorzystującego automaty, maszyny ze stopem i bez stopu, abstrakcyjny język programowania ( lambda rachunek) oraz formalizm funkcyjny + + - - - - - - - - -
M_W003 zna podstawy teoretyczne ograniczeń obliczeniowych dla problemów modelowanych algorytmicznie oparte na teorii programowania (rozstrzygalności) oraz na teorii złożoności + + - - - - - - - - -
M_W004 zna najważniejsze fakty z historii teorii programowania i złożoności oraz wybrane nierozstrzygnięte hipotezy + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 101 h
Module ECTS credits 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 14 h
Realization of independently performed tasks 20 h
Examination or Final test 2 h
Contact hours 5 h
Module content
Lectures (30h):

1.Maszyna z dostępem swobodnym i Maszyna Turinga oraz pojęcie funkcji obliczalnych. Teza Churcha.

2. Modyfikacje maszyn Turinga-taśmy wielościeżkowe, maszyny wielotaśmowe. Twierdzenie o równoważności obliczeniowej różnych modeli maszyn. Definicja niedeterministycznej maszyny Turinga. Usystematyzowanie i poszerzenie podstawowych pojęć teorii złożoności obliczeniowej takich jak złożoność czasowa i pamięciowa dla deterministycznego oraz niedeterministycznego modelu maszyny Turinga.

3. Formalizm funkcji rekurencyjnych – klasa funkcji prymitywnie rekurencyjnych i rekurencyjnych, tw. Goedla- Kleeniego o eliminacji rekursji (bd.), tw. Kleeniego o formie normalnej rekursji (bd.).

4. Elementy lambda-rachunku. Tw. o równoważności formalizmów funkcji rekurencyjnych, lambda rachunku i maszyn Turinga (bd.).

5. Przykłady języków rekurencyjnych, rekurencyjnie przeliczalnych i takich, które nie są rekurencyjnie przeliczalne. Dwa twierdzenia Rice’a (bd.).

6. Elementy logiki predykatów. Twierdzenie Goedla (bd.).

7. Klasy złożoności. Twierdzenie o przyspieszeniu liniowym. Twierdzenie o liniowej kompresji pamięci. Twierdzenie Bluma o przyspieszaniu (bd.). Hierarchie złożoności. Twierdzenie o hierarchii pamięciowej. Twierdzenie Savitcha. Inkluzje klas złożoności.

8. Klasy problemów P i NP. Twierdzenie o inkluzjach pomiędzy klasami. Definicja problemu decyzyjnego. Związek pomiędzy problemem decyzyjnym, a językiem akceptowanym przez maszynę Turinga. Definicja relacji transformalności wielomianowej i jej własności. Pojęcie równoważności problemów. Definicja problemu zupełnego w swojej klasie złożoności.

9. Problem spełnialności. Twierdzenie Cooka.

10. Twierdzenie o NP-zupełności problemu 3-spełnialności. Sześć najsławniejszych problemów NP-zupełnych. Techniki dowodzenia NP-zupełności: twierdzenia o NP-zupełności problemu pokrycia wierzchołkowego, cyklu Hamiltona, ścieżki Hamiltona itp.

11. Szczegółowe omówienie dowodzenia NP-zupełności przez zacieśnienie, lokalne zastąpienie oraz techniką składowych na podstawie poznanych twierdzeń. Definicja podproblemu. Analiza złożoności problemów i podproblemów za pomocą NP-zupełności. Analiza podproblemów na przykładzie twierdzeń o NP-zupełności problemu 3-kolorowalności grafów. Twierdzenie Brooksa (bd.).

12. Pojęcie problemu liczbowego. Definicja silnej NP-zupełności. Definicja problemu pseudowielomianowego. Algorytm dynamiczny dla problemu podziału jako przykład algorytmu pseudowielomianowego. Pojęcie transformacji pseudowielomianowej.

13. Pojęcie problemu nieliczbowego. Twierdzenie o złożoności problemów nieliczbowych. Pojęcie problemów silnie NP-zupełnych. Twierdzenie o silnej NP-zupełności problemów nieliczbowych. Dowodzenie silnej NP-zupełności za pomocą transformacji wielomianowej: problem 3-podziału, problem zanurzania grafów, problem podziału zadań, problem komiwojażera.

14. Definicja problemu optymalizacyjnego. Optymalizacyjne wersje pewnych problemów NP-zupełnych. Pojęcie transformacji w sensie Turinga. Pojęcie problemu NP-trudnego oraz NP-łatwego. Porównywanie trudności obliczeniowych problemów optymalizacyjnych na przykładzie optymalizacyjnego problemu pokrycia wierzchołkowego. Definicja rozwiązania optymalnego minimalizacji i maksymalizacji. Pojęcie algorytmu aproksymacyjnego. Stała aproksymacji.

Auditorium classes (30h):
Program ćwiczeń pokrywa się z programem wykładów

Rozwiązywanie problemów konstrukcyjnych (automatów i maszyn) oraz zadań dotyczących treści przekazywanych na kolejnych wykładach.

Additional information
Teaching methods and techniques:
  • Lectures: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Auditorium classes: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Dwa zaliczenia poprawkowe.

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: No
    – Participation rules in classes: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Method of calculating the final grade:

Ocena końcowa (OK) jest średnią ważoną ocen z odpowiedzi ustnej (U) i zaliczenia ćwiczeń audytoryjnych (A):
OK = 1/2 x U + 1/2 x A ,
gdzie U jest średnią arytmetyczną ocen uzyskanych podczas odpowiedzi ustnej w kolejnych terminach, A jest średnią arytmetyczną ocen uzyskanych z ćwiczeń w kolejnych terminach.

Uzyskanie pozytywnej oceny końcowej następuje po uzyskaniu obu pozytywnych wyników: z odpowiedzi ustnej i zaliczeniu ćwiczeń.

Odpowiedz ustna obejmuje treści wykładów 8-14 ( z powyższej listy). Warunkiem ubiegania się o zaliczenie ćwiczeń jest 80% obecności na ćwiczeniach.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  1. A. Aho, J. Hopcroft, J. Ullman, Projektowanie i analiza algorytmów, Helion, 2003.
  2. A. Aho, J. Hopcroft, J. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2003.
  3. G. Boolos, R. Jeffrey, Computability and Logic, Cambridge Univ. Press, 1980.
  4. M. Garey, D. Johnson, Computers and intractability, W. H. Freeman and Company, 2003
Scientific publications of module course instructors related to the topic of the module:

1. Pilśniak, Monika; Woźniak, Mariusz;
On the total-neighbor-distinguishing index by sums; Graphs Comb. 31, No. 3, 771-782 (2015).

2. Broere, Izak; Pilśniak, Monika; The distinguishing index of infinite graphs;
Electron. J. Comb. 22, No. 1, Research Paper P1.78, 10 p., electronic only (2015).

3. Kalinowski, Rafał; Pilśniak, Monika; Distinguishing graphs by edge-colourings.; Eur. J. Comb. 45, 124-131 (2015).

4. Imrich, Wilfried; Kalinowski, Rafał; Lehner, Florian; Pilśniak, Monika;
Endomorphism breaking in graphs; Electron. J. Comb. 21, No. 1, Research Paper P1.16, 13 p., electronic only (2014).

5. Kalinowski, Rafał; Pilśniak, Monika; Przybyło, Jakub; Woźniak, Mariusz; How to personalize the vertices of a graph? Eur. J. Comb. 40, 116-123 (2014).

6. Kalinowski, Rafał; Pilśniak, Monika; Przybyło, Jakub; Woźniak, Mariusz; Can colour-blind distinguish colour palettes? Electron. J. Comb. 20, No. 3, Research Paper P23, 12 p., electronic only (2013).

7. Borowiecki, Mieczysław; Grytczuk, Jarosław; Pilśniak, Monika; Coloring chip configurations on graphs and digraphs; Inf. Process. Lett. 112, No. 1-2, 1-4 (2012).

8. Cichacz, Sylwia; Görlich, Agnieszka; Tuza, Zsolt; Cordial labeling of hypertrees;
Discrete Math. 313, No. 22, 2518-2524 (2013).

9. Görlich, Agnieszka; Ẓak, Andrzej; Sparse graphs of girth at least five are packable;
Discrete Math. 312, No. 24, 3606-3613 (2012).

10. Cichacz, Sylwia; Görlich, Agnieszka; Nikodem, Mateusz; Żak, Andrzej;
A lower bound on the size of (H;1)-vertex stable graphs; Discrete Math. 312, No. 20, 3026-3029 (2012).

11. Cichacz, Sylwia; Görlich, Agnieszka; Zwonek, Magorzata; Żak, Andrzej;
On (C n ;k) stable graphs; Electron. J. Comb. 18, No. 1, Research Paper P205, 10 p., electronic only (2011).

12. Cichacz, Sylwia; Görlich, Agnieszka; Open trails in digraphs;
Opusc. Math. 31, No. 4, 599-604 (2011).

13. On Erdős-Sós conjecture for trees of large size / Agnieszka GÖRLICH, Andrzej ŻAK // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2016 vol. 23 iss. 1 art. no. P1.52, s. 1–14.

14. The distinguishing index of the Cartesian product of finite graphs / Aleksandra GORZKOWSKA, Rafał KALINOWSKI, Monika PILŚNIAK // Ars Mathematica Contemporanea ; ISSN 1855-3966. — 2017 vol. 12 no. 1, s. 77–87

15. The distinguishing index of the Cartesian product of countable graphs / Izak Broere, Monika PILŚNIAK // Ars Mathematica Contemporanea ; ISSN 1855-3966. — 2017 vol. 13 no. 1, s. 15–21.

16. Structural properties of recursively partitionable graphs with connectivity 2 / Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika PILŚNIAK // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2017 vol. 37 iss. 1, s. 89–115.

17. Distinguishing cartesian products of countable graphs / Ehsan Estaji, Wilfried Imrich, Rafał KALINOWSKI, Monika PILŚNIAK, Thomas Tucker // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2017 vol. 37 iss. 1, s. 155–164.

Additional information:

None