University of Warsaw - Central Authentication System

Approximation and complexity

General data

Course ID:	1000-135APZ
Erasmus code / ISCED:	11.1 The subject classification code consists of three to five digits, where the first three represent the classification of the discipline according to the Discipline code list applicable to the Socrates/Erasmus program, the fourth (usually 0) - possible further specification of discipline information, the fifth - the degree of subject determined based on the year of study for which the subject is intended. / (0541) Mathematics The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Approximation and complexity
Name in Polish:	Aproksymacja i złożoność
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for 2nd stage studies in Mathematics
ECTS credit allocation (and other scores):	6.00 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	English
Type of course:	elective monographs
Short description:	Introduction to two key concepts in numerical analysis: approximation and complexity. Classical polynomial approximation of smooth functions. Approximation based on partial information. Construction of optimal algorithms in prescribed model of computation.
Full description:	A. Classical polynomial approximation 1. Problem formulation, a general characterization of optimal approximations 2. Approximation in Hilbert spaces 3. Algebraic and trigonometric polynomials, the Weierstrass theorem 4. Trigonometric approximation: Fourier and Fejer operators, Korovkin's theorem 5. Uniform approximation: Haar spaces, the Chebyshev theorem 6. Berntein's lethargy theorem 7. Theorems of Jackson and Bernstein B. Information-based approximation 1. Information, error and cost of algorithms, problem complexity 2. Worst case setting: radius of information, optimality of linear algorithms 3. General splines and spline algorithms 4. Adaptive algorithms versus nonadaptive algorithms 5. Asymptotic setting 6. Randomization 7. Complexity of selected problems
Bibliography:	(in Polish) 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.
Learning outcomes:	(in Polish) 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.
Assessment methods and assessment criteria:	(in Polish) Ocena: zadania domowe + egzamin pisemny (także ustny, w wyjątkowych przypadkach)

Classes in period "Winter semester 2025/26" (future)

Time span:	2025-10-01 - 2026-01-25	Selected timetable range: weekly course term Go to timetable MO TU W WYK CW TH FR
Type of class:	Classes, 30 hours more information Lecture, 30 hours more information
Coordinators:	Leszek Plaskota
Group instructors:	Leszek Plaskota
Students list:	(inaccessible to you)
Credit:	Course - Examination Lecture - Examination

Course descriptions are protected by copyright.
Copyright by University of Warsaw.