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

Złożoność obliczeniowa WM-I-ZO
Konwersatorium (KON) Semestr zimowy 2023/24

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

Liczba godzin: 30
Limit miejsc: (brak limitu)
Zaliczenie: Zaliczenie na ocenę
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. 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 Liczba osób w grupie / limit miejsc Akcje
1 każdy wtorek, 9:45 - 11:15, sala 1203
Dorota Dąbrowska 9/9 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.2.0-1 (2024-03-12)