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
Laboratorium (LAB) Semestr zimowy 2020/21

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

Strona zajęć: https://e.uksw.edu.pl/course/view.php?id=14595
Liczba godzin: 15
Limit miejsc: (brak limitu)
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.

http://uksw.edu.pl/images/artykuly/bhp/instrukcja_pierw_pomocy.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. Zapis problemów decyzyjne jako zadań rozpoznawania języków. Budowanie automatów skończonych rozpoznających zadane języki.

2. Budowanie deterministycznych i niedeterministycznych maszyn Turinga rozwiązujących problemy obliczeniowe. Języki akceptowane przez maszyny Turinga.

3. Przykłady problemów nierozstrzygalne.

4. Obliczanie miar złożoności obliczeniowej.

5. Dowodzenie prostych zależności między klasami złożoności.

6. Problemy NP-zupełne: przykłady.

7. Algorytmy SAT.

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Akcje
1 każdy wtorek, 14:00 - 14:45, sala e-learning
Dorota Dąbrowska 3/5 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.