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 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, 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, 17:30 - 18:15, 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.