Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Teoria obliczeń i złożoności obliczeniowej
Tok studiów:
2014/2015
Kod:
IIN-1-508-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
5
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
Faliszewski Piotr (faliszew@agh.edu.pl)
Osoby prowadzące:
Faliszewski Piotr (faliszew@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Student zna i rozumie znaczenie pojęcia nierozstrzygalności problemów obliczeniowych. IN1A_W04 Kolokwium
M_W002 Student zna i rozumie podstawowe pojęcia teorii obliczeń i złożoności obliczeniowej. IN1A_W03 Kolokwium
M_W003 Student rozumie teoretyczne i praktyczne konsekwencje wysokiej złożoności zadań obliczeniowych. IN1A_W03 Kolokwium
Umiejętności
M_U001 Student potrafi wykazać równoważność obliczeniową rozważanych problemów IN1A_U07 Kolokwium
Kompetencje społeczne
M_K001 Student potrafi rozwiązaywać trudne, otwarte problemy w grupie. IN1A_K03 Aktywność na zajęciach
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Student zna i rozumie znaczenie pojęcia nierozstrzygalności problemów obliczeniowych. + - - - - - - - - - -
M_W002 Student zna i rozumie podstawowe pojęcia teorii obliczeń i złożoności obliczeniowej. + - - - - - - - - - -
M_W003 Student rozumie teoretyczne i praktyczne konsekwencje wysokiej złożoności zadań obliczeniowych. + - - - - - - - - - -
Umiejętności
M_U001 Student potrafi wykazać równoważność obliczeniową rozważanych problemów - + - - - - - - - - -
Kompetencje społeczne
M_K001 Student potrafi rozwiązaywać trudne, otwarte problemy w grupie. - + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Podstawowe pojęcia (2 godz.)
Problem obliczeniowy, problem funkcyjny, problem decyzyjny, języki formalne. Związek między problemami funkcyjnymi i problemami decyzyjnymi. Związek między problemami decyzyjnymi i językami formalnymi.

2. Modele obliczeń (4 godz.)
Maszyna Turinga (deterministyczna i niedeterministyczna). Wielotaśmowa maszyna Turina. Maszyna RAM. Równoważność modeli obliczeniowych, teza Turinga-Church’a.

3. Problemy nierozstrzygalne (4 godz.)
Pojęcie rozstrzygalności i akceptowalności języka. Klasy R, RE i coRE. Problem stopu. Metody dowodzenia nierozstrzygalności: metoda diagonalizacji, pojęcie redukcji między językami, tw. Rice’a. Przykłady problemów nierozstrzygalnych.

4. Hierarchia arytmetyczna (2 godz.)
Charakteryzacja klas RE i coRE przy pomocy kwantyfikatora egzystencjalnego i uniwersalnego. Pojęcie hierarchii arytmetyczne. Metoda wyznaczania przynależności języka do odpowiedniego poziomu hierarchii arytmetycznej.

5. Złożoność w sensie Kołmogorowa (2 godz.)
Pojęcie niekompresowalności napisów. Pojęcie złożoności Kołmogorowa napisu i jego podstawowe własności. Przykłady zastosowań złożoności Kołmogorowa.

6. Złożoność obliczeniowa (2 godz.)
Pojęcie złożoności czasowej i pamięciowej dla deterministycznych i niedterministycznych maszyn Turinga. Klasy P, NP, coNP, PSPACE oraz NPSPACE. Przykłady przynależności problemów do klas P, NP i PSPACE. Dowód, że PSPACE = NPSPACE.

7. Problemy NP-zupełne (8 godz.)
Pojęcie redukcji w czasie wielomianowym. Własności redukcji. Pojęcie problemu NP-zupełnego. Bezpośredni dowód NP-zupełności problemu spełnialności formuł logicznych. Zastosowanie redukcji do dowodów NP-zupełności. Przykłady problemów NP-zupełnych. Pojęcie słabej i silnej NP-zupełności.

8. Struktura klasy NP (2 godz.)
Problem równości klas P i NP. Istnienie języków w NP, które nie należą do P ani nie są NP-zupełne. Twierdzenie Ladnera. Twierdzenie Mahaney’a.

9. Hierarchia wielomianowa (4 godz.)
Pojęcie maszyny Turinga z wyrocznią. Definicja hierarchii wielomianowej. Związek hierarchii wielomianowej i hierarchii arytmetycznej. Własności hierarchii wielomianowej. Problem nieskończoności hierarchii wielomianowej. Klasy P i NP z wyrocznią NP ⋂ coNP. Pojęcia autoredukcji i samoredukcji języków.

Ćwiczenia audytoryjne:

1. Programowanie maszyny Turinga (2 godz.)
2. Równoważność modeli obliczeń (2 godz.)
3. Własności klas R, RE i coRE (1 godz.)
4. Redukcje między nierozstrzygalnymi problemami (3 godz.)
5. Klasyfikacja problemów w hierarchii arytmetycznej (1 godz.)
6. Własności klas P, NP i coNP (1 godz.)
7. Warianty problemu spełnialności formuł logicznych (3 godz.)
8. Dowodzenie NP-zupełności problemów (2 godz.)

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 75 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 28 godz
Samodzielne studiowanie tematyki zajęć 33 godz
Udział w ćwiczeniach audytoryjnych 14 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

W wypadku zaliczenia przedmiotu w pierwszym terminie, ocena końcowa jest równa ocenie z ćwiczeń, ale nie mniejsza niż 3.5. W przypadku zaliczenia przedmiotu w terminie drugim lub trzecim, ocena końcowa wynosi 3.0.

Wymagania wstępne i dodatkowe:

Ogólna znajomość matematyki z naciskiem na matematykę dyskretną. Podstawowa wiedza dotycząca: logiki, teorii grafów, metod konstruowania algorytmów.

Zalecana literatura i pomoce naukowe:

1. Sipser M.: Wprowadzenie do teorii obliczeń. WNT, Warszawa 2009
2. Papadimitriou C.H.: Złożoność obliczeniowa. WNT, Warszawa 2002
3. Bovet D.P, Crescenzi P.: Introduction to the theory of complexity. Prentice Hall, 1994
4. Wegener I.: Complexity Theory, Springer, 2005
5. Kościelski A.: Teoria obliczeń. Wydawnictwo Uniwersytetu Wrocławskiego, Wrocław 1997

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak