7928718287

PRZEDMIOTOWE EFEKTY KSZTAŁCENIA

Z zakresu wiedzy studenta:

W1 Zna pojęcie modelu obliczeń, definicję i własności maszyny Turinga, podstawy lambda rachunku, model funkcji rekurencyjnych na liczbach naturalnych oraz ich własności

W2 Zna definicje klas złożoności obliczeniowej P, NP, co-NP, PSPACE i ich podstawowe własności jak zupełność i trudność

W3 Zna definicje i własności klas obliczeń losowych: RP, co-RP, ZPP, PP i BPP, oraz klas obliczeń równoległych NC

Z zakresu umiejętności studenta:

Ul Umie określić czy podany problem jest rozstrzygalny lub rozpoznawalny

U2 Potrafi określić złożoność obliczeniową problemu, jego należenie do określonej klasy złożoności i trudność w tej klasie

Z zakresu kompetencji społecznych studenta:

KI Potrafi wyjaśnić podstawowe zagadnienia związane z obliczalnością i trudnością problemów informatycznych

K2 Rozumie trudność rozwiązywania problemów informatycznych należących do określonych klas obliczeniowych

TREŚCI PROGRAMOWE
Forma zajęć - wykłady
Wy 1	Maszyna Turinga. Własności różnych modeli maszyny Turinga	2h
Wy2	Języki rekurencyjne i rekurencyjnie przeliczalne	2h
Wy3	Uniwersalna maszyna Turinga. Nierozstrzygalność problemu stopu	2h
Wy4	Twierdzenie Rice’a. Teza Churcha. Maszyna licznikowa	2h
Wy5	Funkcje rekurencyjne na liczbach naturalnych	2h
Wy6	Podstawy lambda rachunku	3h
Wy7	Problem odpowiedniości Posta	lh
Wy8	Podstawy złożoności obliczeniowej	2h
Wy9	Redukcje między problemami. Pojęcie problemu trudnego i zupełnego dla klasy złożoności	2h
Wy 10	Redukcje między problemami NP-zupełnymi. Silna NP-zupełność. Klasa co-NP.	2h
Wyli	Aproksymowalność	2h
Wy 12	Obliczenia losowe	2h
Wy 13	Obliczenia równoległe	2h
Wy 14	Klasa PSPACE. Alternujące maszyny Turinga.	2h
Wy 15	Inne klasy złożoności	2h