Teoria obliczeń i złożoności

egzamin

stacjonarne

Wymagana jest znajomość rachunku zdań i zbiorów, w tym pojęcie funkcji. Zalecana jest znajomość teoretycznych podstaw informatyki, w szczególności : języki formalne, maszyny Turinga.

Celem przedmiotu jest zaznajomienie studenta z podstawowymi pojęciami teorii obliczeń i złożoności, przyjmując maszynę Turinga jako podstawowy model teoretyczny komputera. Na wykladzie zostają omówione:

1. teoretyczne możliwości komputerów,

2. złożoność obliczeniowa czasowa i pamięciowa,

3. złożoność opisowa (Kołmogorowa) słów binarnych.

Po zakończonym wykładzie student powinien umieć:

1. konstruować maszyny Turinga rozwiązujące proste problemy,

2 kodować maszyny Turinga za pomocą słów binarnych,

3. omówić granice stosowalności komputerów, czyli omówic klasę języków rozpoznawalnych przez maszyny Turinga,

4. omówić problemy rozstrzygalne i korzystając z tego podać definicję algorytmu,

5. omówić złożoność obliczeniową czasową i pamięciową problemów

6. zdefiniować klasy złożoności obliczeniowych,

7. omówić problem P=NP.

Powyższe efekty uczenia się osiągane w ramach przedmiotu pozwalają na realizację kierunkowych efektów uczenia się, mających następujące oznaczenia w programie studiów:

8. opisać niektóre problemy NP-zupełne,

9. omówić złożoność opisową (Kołmogorowa) słów,

10. zdefiniować słowa losowe i kompresowalne.

Powyższe efekty kształcenia osiągane w ramach przedmiotu pozwalają na realizację kierunkowych efektów kształcenia, mających następujące oznaczenia w programie Informatyka II stopnia: 1100I-2A_W01, 1100I-2A_W03, 1100I-2A_U01, 1100I-2A_U11, 1100I-2A_U12, 1100I-2A_U14, 1100I-2A_K01, 1100I-2A_K02, 1100I-2A_K05, 1100I-2A_K06, 1100I-2A_K07, 1100Isi-2A_W12, 1100Isi-2A_U18.