Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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

zobacz na planie zajęć

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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.