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 2019/20

Informacje o zajęciach (wspólne dla wszystkich grup)

Liczba godzin: 15
Limit miejsc: (brak limitu)
Literatura:

Literatura podstawowa

Ch. Papadimitriou, Złożoność obliczeniowa, WNT Warszawa, 2007, II wydanie.

A. Kościelski, Teoria obliczeń, wyd. UWr 1997.

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, 16:45 - 17:30, sala 1223
Dorota Dąbrowska 16/25 szczegóły
Wszystkie zajęcia odbywają się w budynku:
Kampus Wóycickiego Bud. 12
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.