Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-059-MZ-s
Name:
Algorithms and Complexity for Continuous Problems
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
prof. dr hab. Kacewicz Bolesław (kacewicz@agh.edu.pl)
Academic teachers:
prof. dr hab. Kacewicz Bolesław (kacewicz@agh.edu.pl)
dr Przybyłowicz Paweł (pprzybyl@agh.edu.pl)
Module summary

Seminarium częściowo zapewnia studentowi udział w badaniach.
Seminarium jest wybierane zgodnie z zainteresowaniami, rozszerza wiedzę teoretyczną lub zastosowania, zapoznaje z fachową literaturą.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Potrafi samodzielnie wyszukiwać informacje w literaturze, także w językach obcych i zna ograniczenia swojej wiedzy. MA2A_K02, MA2A_K01, MA2A_K06 Activity during classes,
Oral answer,
Diploma thesis,
Presentation
M_K002 Rozumie i docenia znaczenie uczciwości intelektualnej w działaniach własnych i innych osób. MA2A_K04 Activity during classes
Skills
M_U001 Potrafi w sposób zrozumiały, w mowie i piśmie, przedstawić poprawne rozumowanie matematyczne, formułować twierdzenia i definicje MA2A_U03, MA2A_K05, MA2A_U01, MA2A_U02 Activity during classes,
Oral answer,
Diploma thesis,
Presentation
M_U002 Potrafi prezentować i przeprowadzać dowody, w których stosuje w razie potrzeby również narzędzia z innych działów matematyki MA2A_U14 Activity during classes,
Oral answer,
Diploma thesis,
Presentation
Knowledge
M_W001 Posiada wiedzę na temat zasad poprawnego formułowania definicji i twierdzeń matematycznych oraz zasad poprawnej prezentacji dowodów matematycznych MA2A_W02, MA2A_W06 Activity during classes,
Oral answer,
Diploma thesis
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Potrafi samodzielnie wyszukiwać informacje w literaturze, także w językach obcych i zna ograniczenia swojej wiedzy. - - - - - + - - - - -
M_K002 Rozumie i docenia znaczenie uczciwości intelektualnej w działaniach własnych i innych osób. - - - - - + - - - - -
Skills
M_U001 Potrafi w sposób zrozumiały, w mowie i piśmie, przedstawić poprawne rozumowanie matematyczne, formułować twierdzenia i definicje - - - - - + - - - - -
M_U002 Potrafi prezentować i przeprowadzać dowody, w których stosuje w razie potrzeby również narzędzia z innych działów matematyki - - - - - + - - - - -
Knowledge
M_W001 Posiada wiedzę na temat zasad poprawnego formułowania definicji i twierdzeń matematycznych oraz zasad poprawnej prezentacji dowodów matematycznych - - - - - + - - - - -
Module content
Seminar classes:
Zajęcia seminaryjne:

1. Złożoność zadań ciągłych – informacje wstępne, model błędu najgorszego przypadku, podstawowe twierdzenia (Lemat Smolyaka) i definicje.

2. Model asymptotyczny – definicja, twierdzenie Trojana, porównanie z błędem najgorszego przypadku.

3. Całkowanie wielowymiarowe – postawienie problemu, oszacowania z góry i z dołu na złożoność, konstrukcja algorytmu optymalnego.

4. Model najgorszego przypadku dla równań różniczkowych zwyczajnych – sformułowanie problemu obliczeniowego, oszacowania z góry.

5. Model najgorszego przypadku dla równań różniczkowych zwyczajnych – oszacowania z dołu i algorytmy optymalne.

6. Model asymptotyczny dla równań różniczkowych zwyczajnych – oszacowania z góry.

7. Model asymptotyczny dla równań różniczkowych zwyczajnych – oszacowania z dołu i algorytmy optymalne.

8. Złożoność obliczeniowa rozwiązywania równań różniczkowych zwyczajnych z osobliwościami – sformułowanie problemu obliczeniowego w przypadku osobliwej funkcji prawej strony, konstrukcja algorytmu optymalnego wykrywającego osobliwość.

9. Złożoność obliczeniowa rozwiązywania równań różniczkowych zwyczajnych z osobliwościami – ograniczenia z dołu.

10. Podstawowe informacje dotyczące całkowania stochastycznego w sensie Itô – konstrukcja całki Itô, izometria Itô, formuła Itô.

11. Złożoność całkowania stochastycznego w sensie Itô w przypadku informacji standardowej o procesie Wienera – informacje wstępne o modelu średnim, oszacowania z góry i z dołu, optymalność algorytmu Milsteina.

12. Złożoność całkowania stochastycznego w sensie Itô w przypadku informacji całkowej o procesie Wienera – oszacowania z góry i z dołu, optymalność algorytmu Wagnera-Platena.

13. Złożoność całkowania stochastycznego w sensie Itô funkcji deterministycznych regularnych – oszacowania z góry i z dołu, optymalność algorytmu Itô-Taylora.

14. Złożoność całkowania stochastycznego w sensie Itô funkcji deterministycznych osobliwych- oszacowania z góry i z dołu, optymalność algorytmu Itô-Taylora z adaptacyjną siatką.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 60 h
Module ECTS credits 2 ECTS
Participation in seminar classes 30 h
Preparation for classes 28 h
Contact hours 2 h
Additional information
Method of calculating the final grade:

Ocena końcowa OK jest oceną z aktywności na zajęciach i jakości prezentacji OZ.
OK = OZ

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:

Monografie i artykuły naukowe opublikowane w ostatnich latach z tej dziedziny.

Scientific publications of module course instructors related to the topic of the module:

1. Kacewicz B., Przybyłowicz P. (2008) „Optimal adaptive solution of initial-value problems with unknown singularities” , Journal of Complexity 24, 455–476.

2. Kacewicz B., Przybyłowicz P. (2014), „Optimal solution of a class of non-autonomous initial-value problems with unknown singularities”, Journal of Computational and Applied Mathematics 261, 364-377,

3. Kacewicz B., Przybyłowicz P. (2014), „Optimal adaptive solution of piecewise regular systems of IVPs with unknown switching hypersurface”, Applied Mathematics and Computation 228, 116-127

4. Kacewicz B., Przybyłowicz P. (2015), „Complexity of the derivative-free solution of systems of IVPs with unknown singularity hypersurface”, Journal of Complexity 31, 75-97

5. Kacewicz, Bolesław; Almost optimal solution of initial-value problems by randomized and quantum algorithms; J. Complexity 22, No. 5, 676-690 (2006).

6. Kacewicz, Bolesław; Improved bounds on the randomized and quantum complexity of initial-value problems; J. Complexity 21, No. 5, 740-756 (2005).

7. Przybyłowicz, Paweł; Optimality of Euler-type algorithms for approximation of stochastic differential equations with discontinuous coefficients; Int. J. Comput. Math. 91, No. 7, 1461-1479 (2014).

Additional information:

None