Złożoność obliczeniowa problemów ciągłych 1000-135ZOP
Wykład ma na celu przedstawienie wyników teoretycznych dotyczących złożoności obliczeniowej zadań matematyki ciągłej, takich jak całkowanie czy aproksymacja funkcji, jak również prezentację najważniejszych algorytmów, które okazują się optymalne w rozpatrywanym modelu obliczeniowym.
1. Ogólny model obliczeniowy dla problemów ciągłych. Zadanie, informacja, aproksymacja, koszt. Złożoność w różnych przypadkach.
2. Przypadek pesymistyczny. Promień i średnica informacji. Problemy liniowe. Optymalność algorytmów liniowych. Splajny i algorytmy splajnowe. Informacja adaptacyjna.
3. Przypadek średni. Promień i średnica informacji Problemy liniowe z miarą Gaussa. Algorytmy optymalne jako splajny. Informacja adaptacyjna.
4. Przypadek asymptotyczny.
5. Randomizacja i metody Monte Carlo.
6. Problemy wielowymiarowe. Przekleństwo wymiaru i tractability. Dyskrepancja i metody quasi-Monte Carlo. Algorytm Smolaka.
7. Informacja zaburzona, wygładzanie.
Rodzaj przedmiotu
Efekty kształcenia
Wiedza i umiejętności:
1. Zna podstawowe modele złożonoci obliczeniowej dla zadań ciągłych, odróżnia koszt algorytmu od złożonoci zadania.
2. Wie co to jest błąd i koszt algorytmu w przypadku pesymistycznym, rozumie problem adaptacji i zna optymalne własności algorytmów splajnowych.
3. Wie co to jest błąd i koszt algorytmu w przypadku średnim z miarą Gaussa, zna związki algorytmów optymalnych z miarami warunkowymi.
4. Zna przypadek asymptotyczny i jego zwišzki z przypadkami pesymistycznym i średnim.
5. Rozumie istotę algorytmów typu Monte Carlo, ich zalety i wady w porównaniu z algorytmami deterministycznymi.
6. Rozumie pojęcie przekleństwa wymiaru i zna podstawowe sposoby jego przezwyciężania: algorytmy (quasi-)Monte Carlo i algorytm Smolaka.
7. Zna algorytmy wygładzania danych dla zadań ciągłych z informacją zaburzoną deterministycznie lub losowo.
Kompetencje społeczne:
Rozumie konieczność badania złożonoci obliczeniowej zadań ciągłych, w celu optymalizacji kosztu rozwiązania problemów rzeczywistych.
Literatura
1. J.F. Traub, G.W. Wasilkowski, H. Woźniakowski, "Information-based Complexity", Academic Press, New York 1988.
2. L. Plaskota, "Noisy Information and Computational Complexity", Cambridge University Press, Cambridge 1996.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: