Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie - Centralny System Uwierzytelniania
Strona główna

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

Materiały zawarte w kursie w Moodle.

Literatura uzupełniająca

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

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, dostępny 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 Liczba osób w grupie / limit miejsc 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.
ul. Dewajtis 5,
01-815 Warszawa
tel: +48 22 561 88 00 https://uksw.edu.pl
kontakt deklaracja dostępności USOSweb 7.0.0.0-4 (2023-10-17)