Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Złożoność Obliczeniowa ()
Tok studiów:
2019/2020
Kod:
AMAT-2-002-MF-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka finansowa
Kierunek:
Matematyka
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Prowadzący moduł:
dr Gőrlich Agnieszka (forys@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

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).

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
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 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
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 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
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 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
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 Aktywność na zajęciach
Umiejętności: potrafi
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 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
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 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (teoria algorytmów, logika) MAT2A_U19, MAT2A_U14, MAT2A_U04, MAT2A_W07, MAT2A_U08 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
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 Aktywność na zajęciach,
Odpowiedź ustna
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
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 + + - - - - - - - - -
Umiejętności
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) + + - - - - - - - - -
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu, brakujące elementy rozumowania oraz stopień trudności zagadnień matematycznych + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 101 godz
Punkty ECTS za moduł 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 14 godz
Samodzielne studiowanie tematyki zajęć 20 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (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.

Ćwiczenia audytoryjne (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.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Wykład jest klasycznym wykładem tablicowym. Mile widziana aktywność studentów podczas wykładu - np. zadawanie pytań wykładowcy.
  • Ćwiczenia audytoryjne: 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.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: 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.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: 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ęć.
Sposób obliczania oceny końcowej:

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 (co najwyżej trzech), A jest średnią arytmetyczną ocen uzyskanych z ćwiczeń w kolejnych terminach (co najwyżej trzech).

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.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  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
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

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.

Informacje dodatkowe:

Brak