Złożoność obliczeniowa WM-I-ZO
Wykład (WYK)
Semestr zimowy 2020/21
Informacje o zajęciach (wspólne dla wszystkich grup)
| Strona zajęć: | https://e.uksw.edu.pl/course/view.php?id=14595 | ||
| Liczba godzin: | 15 | ||
| Limit miejsc: | (brak limitu) | ||
| Literatura: |
Literatura podstawowa Ch. Papadimitriou, Złożoność obliczeniowa, WNT Warszawa, 2007, II wydanie. Literatura uzupełniająca J. Hopcroft, R. Motwani, J. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN 2005. O. Goldreich, A. Wigderson, Complexity Theory - A Survey, dostępny online http://www.wisdom.weizmann.ac.il/~oded/PS/cc-wA.ps. S. Arora, Boaz Barak, Computational Complexity: A Modern Approach, online http://www.cs.princeton.edu/theory/complexity/book.pdf. |
||
| Metody i kryteria oceniania: |
Dla wszystkich efektów przyjmuje się następujące kryteria oceny we wszystkich formach weryfikacji: ocena 5: osiągnięty w pełni (bez uchwytnych niedociągnięć) ocena 4,5: osiągnięty niemal w pełni i nie są spełnione kryteria przyznania wyższej oceny ocena 4: osiągnięty w znacznym stopniu i nie są spełnione kryteria przyznania wyższej oceny ocena 3,5: osiągnięty w znacznym stopniu – z wyraźną przewagą pozytywów – i nie są spełnione kryteria przyznania wyższej oceny ocena 3: osiągnięty dla większości przypadków objętych weryfikacją i nie są spełnione kryteria przyznania wyższej oceny ocena 2: nie został osiągnięty dla większości przypadków objętych weryfikacją |
||
| Zakres tematów: |
1. Języki a problemy decyzyjne. Języki akceptowane przez automaty skończone. 2. Deterministyczne i niedeterministyczne maszyny Turinga a problemy obliczeniowe. Języki akceptowane przez maszyny Turinga. 3. Problemy nierozstrzygalne. 4. Miary złożoności obliczeniowej. Modele obliczeń. 5. Klasy złożoności czasowej i pamięciowej. Hierarchia czasowa i pamięciowa. 6. Problemy NP, coNP i NP-zupełne: definicja i przykłady. 7. Problem SAT jako przykład problemu NP-zupełnego. Translacje do problemów NP-zupełnych. Algorytmy SAT i ich zastosowania. |
||
Grupy zajęciowe
| Grupa | Termin(y) | Prowadzący |
Miejsca  |
Akcje |
|---|---|---|---|---|
| 1 |
każdy wtorek, 13:15 - 14:00,
sala e-learning |
Dorota Dąbrowska | 3/5 |
szczegóły |
|
Wszystkie zajęcia odbywają się w budynku: e-learning |
||||
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.