Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Złożoność obliczeniowa problemów ciągłych

Informacje ogólne

Kod przedmiotu: 1000-135ZOP Kod Erasmus / ISCED: 11.183 / (0541) Matematyka
Nazwa przedmiotu: Złożoność obliczeniowa problemów ciągłych
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy:
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

fakultatywne

Skrócony opis:

Podstawy teorii złożoności dla rozwiązywania zadań matematyki ciągłej oraz prezentacja algorytmów optymalnych w tej teorii dla wybranych zadań.

Pełny opis:

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.

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.

Efekty uczenia się:

Wiedza i umiejętnośœci:

1. Zna podstawowe modele złożonoœci obliczeniowej dla zadań ciągłych, odróżnia koszt algorytmu od złożonoœci 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żonoœci obliczeniowej zadań ciągłych, w celu optymalizacji kosztu rozwiązania problemów rzeczywistych.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.