Uniwersytet Opolski - Centralny System Uwierzytelniania
Strona główna

Złożoność obliczeniowa

Informacje ogólne

Kod przedmiotu: 3.4.KRK.12TX.ZOb
Kod Erasmus / ISCED: 11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Złożoność obliczeniowa
Jednostka: Instytut Informatyki
Grupy:
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Skrócony opis:

Prezentacja najważniejszych rezultatów badań dotyczących klas złożoności, ich własności i wzajemnych zależności oraz omówienie wynikających z tych faktów wniosków dotyczących praktycznych problemów algorytmicznych.

Pełny opis:

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.

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.

Efekty uczenia się:

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.

Metody i 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.

Zajęcia w cyklu "Semestr zimowy 2023/2024" (zakończony)

Okres: 2023-10-01 - 2024-02-29
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Konwersatorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Lidia Tendera
Prowadzący grup: Lidia Tendera
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Egzamin - Egzamin
Konwersatorium - Zaliczenie na ocenę
Wykład - Zaliczenie
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Opolski.
pl. Kopernika 11a, 45-040 Opole https://uni.opole.pl kontakt deklaracja dostępności mapa serwisu USOSweb 7.0.4.0-www2-4 (2024-07-15)