Aproksymacja i złożoność
Informacje ogólne
Kod przedmiotu: | 1000-135APZ |
Kod Erasmus / ISCED: |
11.1
|
Nazwa przedmiotu: | Aproksymacja i złożoność |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty fakultatywne dla studiów 2 stopnia na matematyce Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Skrócony opis: |
Kurs jest wprowadzeniem do ogólnej teorii aproksymacji i złożonosci obliczeniowej zadań analizy numerycznej. Obejmuje zarówno klasyczną aproksymację wielomianową funkcji gładkich jak i aproksymacje bazujaca jedynie na informacji czesciowej o funkcji. Przedstawione zostana takze konstrukcje algorytmów optymalnych w danym modelu obliczeniowym. |
Pełny opis: |
A. Aproksymacja wielomianowa 1. Ogólne postawienie problemu, charakteryzacja elementów najlepszej aproksymacji 2. Aproksymacja w przestrzeniach Hilberta 3. Wielomiany algebraiczne i trygonometryczne, twierdzenie Weierstrassa 4. Aproksymacja trygonometryczna: operatory Fouriera i Fejera, twierdzenie Korowkina 5. Aproksymacja jednostajna: przestrzenie Haara, twierdzenie o alternansie 6. Twierdzenie o letargu 7. Twierdzenia Jacksona i Bernsteina B. Złozonosc obliczeniowa 1. Ogólny model obliczeniowy: informacja, bład i koszt algorytmu, złozonosc problemu 2. Przypadek pesymistyczny: promien informacji, optymalnosc algorytmów liniowych 3. Splajny i algorytmy splajnowe 4. Algorytmy adaptacyjne 5. Przypadek asymptotyczny 6. Przypadek randomizacyjny 7. Złozonosc wybranych problemów |
Literatura: |
1. E.W. Cheney, Introduction to Approximation Theory, AMS 2000. 2. J.F. Traub, G.W. Wasilkowski, H. Wozniakowski, Information-based Complexity, Academic Press 1988. 3. L. Plaskota, Noisy Information and Computational Complexity”, Cambridge Univ. Press, 1996. |
Efekty uczenia się: |
Wiedza i umiejetnosci: 1. Wie czym zajmuje sie teoria aproksymacji i jakie sa podstawowe problemy. 2. Zna twierdzenia dotyczace istnienia i jednoznacznosci elementów najlepszej aproksymacji oraz aproksymacji w przestrzeniach Hilberta i funkcji ciagłych. 3. Operuje pojeciami z zakresu aproksymacji trygonometrycznej i wielomianowej. 4. Zna twierdzenie o letargu i rozumie jego konsekwencje praktyczne i teoretyczne. 5. Rozumie twierdzenia o błedzie aproksymacji w zaleznosci od regularnosci funkcji. 6. Zna modele złozonosci obliczeniowej, odróznia koszt algorytmu od złozonosci zadania. Wie co to jest bład i koszt algorytmu w przypadku pesymistycznym. 7. Rozumie problem adaptacji i zna optymalne własnosci algorytmów splajnowych. 8. Zna przypadek asymptotyczny i jego zwiazki z przypadkiem pesymistycznym. 9. Rozumie istote algorytmów randomizacyjnych, ich zalety i wady. 10. Potra przeprowadzic analize złozonosci przykładowych problemów. Kompetencje społeczne: 1. Rozumie znaczenie aproksymacji w pracy badawczej w naukach przyrodniczych, 2. Rozumie koniecznosc badania złozonosci obliczeniowej w rozwiazywaniu problemów rzeczywistych. |
Metody i kryteria oceniania: |
Ocena: zadania domowe + egzamin pisemny (także ustny, w wyjątkowych przypadkach) |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WYK
CW
WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Leszek Plaskota | |
Prowadzący grup: | Leszek Plaskota | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Wykład - Egzamin |
Zajęcia w cyklu "Semestr zimowy 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Leszek Plaskota | |
Prowadzący grup: | Leszek Plaskota | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.