Teoria obliczeń i złożoności

egzamin

16

16

niestacjonarne (zaoczne)

Wymagana jest znajomość rachunku zdań i zbiorów, w tym pojęcia funkcji. Zalecana jest znajomość teoretycznych podstaw informatyki, w szczególności: języków formalnych, maszyn 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 kursie student:

1. projektuje maszyny Turinga rozwiązujące proste problemy;

2. koduje maszyny Turinga za pomocą słów binarnych;

3. jest świadomy istnienia granic stosowalności komputerów, wiąże konkretne problemy z językami rozpoznawalnymi przez maszyny Turinga;

4. omawia problemy rozstrzygalne i podaje definicję algorytmu;

5. objaśnia pojęcia złożoności obliczeniowej czasowej i pamięciowej języków;

6. różnicuje klasy złożoności obliczeniowych;

7. uzasadnia praktyczne znaczenie problemu P=NP;

8. przedstawia niektóre problemy NP-zupełne;

9. definiuje złożoność opisową (Kołmogorowa) słów;

10. odnosi pojęcia słowa losowego i kompresowalnego do praktycznych zastosowań.

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.