Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Złożoność obliczeniowa

Informacje ogólne

Kod przedmiotu: 1000-218bZO
Kod Erasmus / ISCED: 11.304 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. / (brak danych)
Nazwa przedmiotu: Złożoność obliczeniowa
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obowiązkowe dla I roku studiów 2 stopnia na kierunku informatyka
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.

zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

obowiązkowe

Skrócony opis:

Teoria złożoności jest dziedziną komplementarną do algorytmiki. Podczas gdy algorytmika dostarcza najbardziej ekonomicznych rozwiązań problemów obliczeniowych, teoria złożoności tłumaczy, dlaczego niektóre problemy okazują się odporne na próby znalezienia dobrych algorytmów i klasyfikuje problemy obliczeniowe ze względu na ich trudność. Ocenia także walory różnych wzbogaceń tradycyjnego modelu obliczeń, jak obliczenia zrandomizowane, równoległe, interakcyjne, czy kwantowe.

Pełny opis:

1. Kodowanie obiektów przez słowa, problemy decyzyjne i funkcyjne.

2. Podstawowe modele obliczeń: maszyna Turinga, maszyna RAM, oraz obwody logiczne.

3. Złożoność czasowa i pamięciowa, pojęcie klasy złożoności.

4. Obliczalność w czasie wielomianowym i jej znaczenie praktyczne, nietrywialne przykłady.

5. Klasa NP, hipoteza P=/=NP, pojęcie redukcji, problemy NP-zupełne, problemy funkcyjne w NP.

6. Konstruktywne podejścia do trudnych problemów: algorytmy aproksymacyjne, efektywność względem wybranego parametru, średnia złożoność wielomianowa.

7. Obliczenia zrandomizowane, probabilistyczne klasy złożoności, generatory pseudolosowe i zagadnienie derandomizacji.

8. Klasa PSPACE i interakcyjne modele obliczeń: maszyny alternujące.

9. Funkcje jednokierunkowe i wykorzystanie trudnych problemów w kryptografii; dowody z zerową wiedzą.

10. Jak dowieść trudności: metoda przekątniowa, twierdzenia o hierarchii. Ograniczenie tej metody w stosunku do hipotezy P=/=NP.

11. Inne podejścia do dowodzenia trudności: złożoność informacyjna Kołmogorowa, zrandomizowane restrykcje w obwodach Boolowskich, złożoność komunikacyjna. Sukcesy i ograniczenia.

12. Fizyczne granice obliczalności, koncepcja obliczeń kwantowych.

Ostatnie trzy wykłady powinny zawierać pogłebiony materiał wybrany przez wykładowcę. Pogłebienie może dotyczyć zagadnień z głównego toku wykładu, ale też i spoza jego zakres. Do potencjalnych tematów należą:

- złożoność a kryptografia,

- złożoność a bazy danych,

- kody korekcyjne,

- problemy spełniania więzów (ang. constraint satisfaction problems),

- dowody interaktywne,

- gry z Naturą,

- PCP,

- złożoność kwantowa,

- złożoność parametryzowana,

- modele złożoności komunikacyjnej.

Literatura:

Ch. H. Papadimitriou, Złożoność obliczeniowa WNT, Warszawa 2002.

A.Arora, B.Barak Computational Complexity: A Modern Approach, Cambridge University Press, 2009 http://www.cs.princeton.edu/theory/complexity/

Oded Goldreich Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008 http://www.wisdom.weizmann.ac.il/~oded/cc-book.html

M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Efekty uczenia się:

Wiedza.

1. Ma pogłębioną wiedzę z działów matematyki niezbędnych do studiowania informatyki (teoria złożoności) [K_W01].

2. Dobrze rozumie rolę i znaczenie konstrukcji rozumowań matematycznych [K_W02].

3. Rozumie kolejne poziomy ogólności: złożoność algorytmu, złożoność problemu, klasa złożoności.

4. Rozumie pojęcia złożoności czasowej i pamięciowej w modelu sekwencyjnym maszyny Turinga oraz odpowiedniki tych pojęć w modelu sieci logicznych.

5. Rozumie niejednorodny i probabilistyczny model obliczeń i zna zależność pomiędzy nimi.

6. Zna przykłady problemów w podstawowych klasach złożoności: NC, L, NL, P, NP, PSPACE, P/poly, BPP.

7. Rozumie pojęcia redukcji między problemami i pojęcie NP-zupełności.

8. Zna kryteria jakości algorytmów aproksymacyjnych.

9. Zna przykłady pozytywnego wykorzystania złożoności obliczeniowej w kryptografii.

Umiejętności.

1. Posiada umiejętność konstruowania rozumowań matematycznych [K_U01].

2. Potrafi wyrażać problemy obliczeniowe w języku matematyki [K_U02].

3. Projektuje algorytmy w podstawowych modelach obliczalności: maszynach Turinga, obwodach logicznych [K_U04].

4. Identyfikuje przynależność i trudność problemów obliczeniowych w stosunku do ważnych klas złożoności: NC, P, NP, PSPACE, wykorzystując ich różne charakteryzacje [K_U05].

5. Ma umiejętności językowe w zakresie informatyki zgodne z wymaganiami określonymi dla poziomu B2+ Europejskiego Systemu Opisu Kształcenia Językowego, w szczególności: identyfikuje główne i poboczne tematy wykładów, pogadanek, debat akademickich, dyskusji, czyta ze zrozumieniem i krytycznie analizuje teksty akademickie, zabiera głos w dyskusji lub debacie naukowej, streszcza ustnie informacje, wyniki badań, opinie i argumenty autora zawarte w tekście naukowym [K_U14].

6. Potrafi w naturalnych przypadkach rozpoznać problemy trudne obliczeniowo.

7. Potrafi w typowych przypadkach zakwalifikować dany problem do jednej z głównych klas złożoności.

8. Potrafi w typowych przypadkach zaprojektować aproksymacyjny lub zrandomizowany algorytm dla problemu, dla którego nie jest znane rozwiązanie deterministyczne.

Kompetencje.

1. Rozumie znaczenie złożoności obliczeniowej jako bariery dla standardowych technik informatycznych, wymuszającej znajdowanie innych technik.

2. Rozumie użyteczność informacji o złożoności obliczeniowej problemów o znaczeniu praktycznym.

3. Rozumie znaczenie hipotez teorii złożoności wśród priorytetowych problemów matematyki współczesnej.

Metody i kryteria oceniania:

Na ocenę końcową składają się: zadania domowe (40% = dwie serie po 20% każda), wyniki kolokwium (20 %) oraz wyniki egzaminu pisemnego (40 %). Dodatkowo, po każdym wykładzie opublikowany będzie prosty quiz w moodle; by być dopuszczonym do egzaminu w pierwszym terminie, należy uzyskać przynajmniej 75% punktów z testów. Do oceny w drugim terminie nie wlicza się kolokwium (ale wliczają się zadania domowe). Oddawane rozwiązania zadań powinny być napisane w języku angielskim.

W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.

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

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Mikołaj Bojańczyk
Prowadzący grup: Mikołaj Bojańczyk, Wojciech Czerwiński, Paweł Parys, Marcin Pilipczuk, Michał Pilipczuk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2024/25" (w trakcie)

Okres: 2024-10-01 - 2025-01-26
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Marcin Pilipczuk
Prowadzący grup: Jakub Gajarský, Tomasz Gogacz, Marcin Pilipczuk, Michał Pilipczuk
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Uwagi:

Zajęcia na przedmiocie odbywają się w języku angielskim

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności mapa serwisu USOSweb 7.1.0.0-895557ea9 (2024-09-26)