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
Konwersatorium (KON) Semestr zimowy 2021/22

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

Liczba godzin: 30
Limit miejsc: (brak limitu)
MS Teams: zespół: ZO 2021/22 - Dorota Dąbrowska
kod: hdmqq2d
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, dostępny online http://www.cs.princeton.edu/theory/complexity/book.pdf.

Zakres tematów:

1. Powtórzenie i rozszerzenie wiadomości o relacjach, funkcjach, funkcjach częściowych.

2. Języki. Zapis problemów decyzyjne jako zadań rozpoznawania języków.

3. Pojęcie maszyn abstrakcyjnych. Deterministyczne i niedeterministyczne automaty skończone.

4. Własności języków akceptowanych przez automaty skończone.

5. Deterministyczne i niedeterministyczne maszyny Turinga.

6. Deterministyczne i niedeterministyczne k-taśmowe maszyny Turinga.

7. Własności języków akceptowanych przez maszyny Turinga.

8. Przykłady problemów nierozstrzygalnych.

9. Miary złożoności obliczeniowej.

10. Modele obliczeń. Klasy złożoności czasowej.

11. Klasy złożoności pamięciowej.

12. Problemy NP-zupełne.

13. Problemy SAT i dowodzenie NP-zupełności.

14. Algorytmy SAT.

15. Prezentacja projektów.

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Akcje
1 każda środa, 9:45 - 11:15, sala e-learning
Dorota Dąbrowska 8/10 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.