Złożoność obliczeniowa 3.4.KRK.12TX.ZOb
Złożoność obliczeniowa w modelu maszyny Turinga; warianty modelu. Klasy złożoności obliczeniowej. Redukcje i zupełność. Dowody NP-zupełności i analiza złożoności problemu. Algorytmy aproksymacyjne. Pamięć wielomianowa. Ponadto przynajmniej jeden z tematów: Algorytmy probabilistyczne, Obliczenia równoległe.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza:
• Definiuje złożoność obliczeniową problemu.
• Wymienia podstawowe klasy złożoności obliczeniowej i związki między nimi.
• Zna przykłady problemów NP-zupełnych.
• Zna przykłady problemów optymalizacyjnych, dla których stosowane są algorytmy aproksymacyjne.
• Zna zasady tworzenia algorytmów probabilistycznych; lub: zna podstawowe klasy obliczeń równoległych.
• Zna przykład problemu PSPACE-zupełnego.
Umiejętności:
• Konstruuje maszyny Turinga i oblicza ich złożoność.
• Opisuje symulacje wybranych maszyn Turinga za pomocą maszyn prostszych.
• Potrafi zwięźle przedstawić pytanie „ czy P= NP ?”
• Wyznacza współczynnik aproksymacji dla przykładowych algorytmów aproksymacyjnych.
• Implementuje proste algorytmy probabilistyczne; lub: tworzy sieci logiczne dla prostych języków.
• Podaje przykład problemu obliczeniowo trudnego.
Kompetencje społeczne (postawy):
• Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia.
• Potrafi zrealizować proste zadanie zespołowe, pracując w kilkuosobowej grupie nad rozwiązaniem zadania praktycznego.
• Postępuje etycznie w zakresie wykorzystania efektów pracy innych osób.
• Rozumie potrzebę popularnego przedstawiania laikom wybranych osiągnięć teorii złożoności obliczeniowej.
Kryteria oceniania
zaliczenie z oceną; (konwersatorium i egzamin)
Konwersatorium: ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w przeciągu semestru za prace kontrolne, wystąpienia ustne, domowe prace pisemne i wykonanie zadań nieobowiązkowych.
Egzamin: pisemny.
Literatura
1. M. Sipser, Wprowadzenie do teorii obliczeń, WNT, 2009
2. Ch. H. Papadimitriou, Złożoność obliczeniowa, WNT, 2002. Lub nowe wydanie: Helion, 2012.
B. Literatura uzupełniająca:
1. J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Na-ukowe PWN, Nowe wydanie, Warszawa 2005.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: