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.

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.