Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Złożoność obliczeniowa

Informacje ogólne

Kod przedmiotu: 1000-218bZO Kod Erasmus / ISCED: 11.304 / (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: 8.00
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 kształcenia:

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ę: wyniki systematycznej pracy w ciągu semestru (do 40%), wyniki kolokwium (do 25 %) oraz wyniki egzaminu pisemnego. Warunkiem dopuszczenia do egzaminu w pierwszym terminie jest przekroczenie minimalnego progu punktów, którego wysokość jest podana na pierwszych zajęciach. Do drugiego terminu można podejść niezależnie od progu punktów, ale punkty uzyskane za zadania domowe i kolokwium liczą się do oceny końcowej.

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-01-26
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Parys
Prowadzący grup: Lorenzo Clemente, Filip Murlak, Paweł Parys, Janusz Schmude, Szymon Toruńczyk, Karol Węgrzycki
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2018/19" (w trakcie)

Okres: 2018-10-01 - 2019-01-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia więcej informacji
Wykład więcej informacji
Koordynatorzy: Paweł Parys
Prowadzący grup: Wojciech Czerwiński, Eryk Kopczyński, Vincent Michielini, Paweł Parys
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.