Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Metody Monte Carlo

Koordynator przedmiotu:

Dr Maciej Romaniuk

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia II stopnia

Program:

Matematyka

Grupa przedmiotów:

Wspólne

Kod przedmiotu:

1120-MASMA-NSP-0016

Semestr nominalny:

3 / rok ak. 2018/2019

Liczba punktów ECTS:

6

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

1. godziny kontaktowe – 70 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) obecność na laboratoriach – 15 h d) obecność na egzaminie – 5 h e) konsultacje – 5 h 2. praca własna studenta – 85 h; w tym a) przygotowanie do ćwiczeń i do kolokwiów – 20 h b) przygotowanie projektu – 20 h c) zapoznanie się z literaturą – 10 h d) przygotowanie do egzaminu – 35 h Razem 155 h, co odpowiada 6 pkt. ECTS

Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:

a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) obecność na laboratoriach – 15 h d) obecność na egzaminie – 5 h d) konsultacje – 5 h Razem 70 h, co odpowiada 3 pkt. ECTS

Język prowadzenia zajęć:

polski

Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:

a) obecność na laboratoriach – 15 h b) przygotowanie projektu – 20 h Razem 35 h, co odpowiada 1 pkt. ECTS

Formy zajęć i ich wymiar w semestrze:

• Wykład30h
• Ćwiczenia15h
• Laboratorium15h
• Projekt0h
• Lekcje komputerowe0h

Wymagania wstępne:

Analiza matematyczna (rachunek różniczkowy i całkowy wielu zmiennych), Rachunek prawdopodobieństwa (pojęcie prawdopodobieństwa, zmiennej losowej, niezależności zmiennych losowych, rozkładu prawdopodobieństwa, wielowymiarowego rozkładu prawdopodobieństwa, gęstości prawdopodobieństwa, momentów zmiennych losowych, twierdzenia graniczne, podstawowe wiadomości o łańcuchach Markowa na przestrzeniach dyskretnych i ciągłych, podstawowe wiadomości o twierdzeniach ergodycznych dla łańcuchów Markowa), Statystyka matematyczna (pojęcie próby, hipotezy statystycznej, testu statystycznego, podstawowe wiadomości o wnioskowaniu bayesowskim)

Limit liczby studentów:

Bez limitu

Cel przedmiotu:

Celem kształcenia w zakresie przedmiotu Metody Monte Carlo jest zaznajomienie studentów ze współczesnymi metodami symulacji probabilistycznych i statystycznych, wykorzystujących narzędzia i algorytmy komputerowe. Student pozna odpowiednie algorytmy, metody i niezbędne twierdzenia matematyczne, a także podstawowe dziedziny zastosowań tych metod oraz będzie umieć wykorzystywać poznane metody w trakcie dalszej kariery naukowej i zawodowej.

Treści kształcenia:

1. Generatory probabilistyczne o rozkładzie jednostajnym: Generatory fizyczne a generatory programowe. Generator von Neumanna. Podstawowe informacje o generatorach o rozkładzie jednostajnym. Okres i struktura przestrzenna generatora. Zastosowanie testów statystycznych: niezależności i zgodności z rozkładem do sprawdzania jakości generatora. Problemy z określeniem jakości generatora. 2. Generatory liniowe: Generatory liniowe. Przykłady twierdzeń o okresie prostych generatorów liniowych. Generatory Fibonacciego. Uogólnione generatory Fibonacciego. 3. Generatory nieliniowe: Generatory nieliniowe, bazujące na operacji odwracania modulo i generatory kwadratowe. Kombinowanie generatorów. 4. Ogólne metody generowania z dowolnych rozkładów prawdopodobieństwa: Metoda odwracania dystrybuanty. Metoda eliminacji. Metoda ilorazu równomiernego. Metoda superpozycji rozkładów. Wady i zalety poszczególnych metod. Przykłady wykorzystania różnych metod generowania dla dowolnych rozkładów prawdopodobieństwa. 5. Szczegółowe metody generowania z określonych rozkładów prawdopodobieństwa: Generowanie zmiennych z rozkładu normalnego (algorytm Boxa – Mullera, algorytm Marsaglii i algorytm Marsaglii – Braya). Przykłady szczegółowych metod generowania z innych rozkładów prawdopodobieństwa. 6. Generowanie z wielowymiarowych rozkładów prawdopodobieństwa: Generowanie z wielowymiarowego rozkładu normalnego metodą dekompozycji macierzy kowariancji. Przekleństwo wielowymiarowości. Metoda przekształceń. 7. Całkowanie metodami Monte Carlo (MC): Wprowadzenie – igła Buffona. Metoda crude Monte Carlo. Przypomnienie probabilistycznych twierdzeń granicznych (centralnego twierdzenia granicznego i prawa wielkich liczb). Zastosowanie probabilistycznych twierdzeń granicznych w określaniu zbieżności metod MC. 8. Całkowanie metodami Monte Carlo (MC): Metoda próbkowania ważonego. Metoda zmiennych antytetycznych. Metoda zmiennych kontrolnych. Problem doboru optymalnych parametrów dla metod próbkowania ważonego i zmiennych antytetycznych. 9. Optymalizacja metodami Monte Carlo (MC): Podstawowa metoda optymalizacji algorytmem MC. Metoda gradientowa. Metoda symulowanego wyżarzania. Modele brakujących danych. 10. Zastosowanie metod Monte Carlo: Błąd metod Monte Carlo a błąd numerycznych metod deterministycznych. Zagadnienie całkowania metodami MC jako problem statystyki matematycznej. Obliczanie poziomu istotności testu metodami MC. Inne zastosowania metod MC – zagadnienia geometryczne, zagadnienia z matematyki ubezpieczeniowej i matematyki finansowej. Zalety i ograniczenia metod MC. 11. Przypomnienie podstawowych informacji o łańcuchach Markowa: Własność Markowa. Łańcuchy Markowa na przestrzeniach dyskretnych i ciągłych. Prawdopodobieństwo przejścia i jądro przejścia. Własności łańcuchów Markowa – jednorodność, nieprzywiedlność, nieokresowość, powracalność. Twierdzenia ergodyczne dla łańcuchów Markowa. 12. Metody Markov Chain Monte Carlo (MCMC): Algorytm Metropolisa – Hastingsa (MH). Problem wyboru gęstości proponującej (niezależny algorytm MH, błądzenie przypadkowe, inne gęstości proponujące). Twierdzenia dotyczące własności łańcucha Markowa wygenerowanego algorytmem MH. Dwuwymiarowy próbnik Gibbsa. Wielowymiarowy próbnik Gibbsa. Twierdzenia dotyczące własności łańcucha Markowa wygenerowanego próbnikiem Gibbsa. Algorytm MH a próbnik Gibbsa – porównanie własności. Hybrydyzowanie algorytmów MCMC przez mieszaninę i cykl. 13. Zastosowania metod MCMC: Przykładowe zastosowania metod MCMC (wnioskowanie bayesowskie za pomocą DAG-ów (direct, acyclic graph), fizyczne badania magnetyzacji, restauracja i odszumianie obrazów). Wady i zalety metod MCMC. Problem diagnostyki zbieżności metod MCMC. Przykłady metod diagnostyki zbieżności. 14. Bootstrap i resampling: Zasada bootstrapu. Przykładowe zastosowanie bootstrapu. Testowanie hipotez statystycznych metodą bootstrap. Ważony bootstrap. Metoda jackknife. Uogólnione podejście.

Metody oceny:

W ramach ćwiczeń odbędą się 2 kolokwia, z każdego z nich można otrzymać maksymalnie 25 punktów. W trakcie laboratorium odbędzie się prezentacja i dyskusja nad przygotowanym projektem komputerowym, z którego można otrzymać maksymalnie 20 punktów. Zaliczenie ćwiczeń wymaga zdobycia minimum 35 punktów. Z egzaminu testowego dotyczącego treści teoretycznych z wykładu otrzymać można maksymalnie 30 punktów. Ocena końcowa ustalana jest na podstawie sumy punktów za kolokwia, prezentację projektu komputerowego i egzamin.

Egzamin:

tak

Literatura:

1. Wieczorkowski R., Zieliński R., Komputerowe generatory liczb losowych, WNT, 1997 2. Robert Ch. P., Casella G., Monte Carlo Statistical Methods, Springer, 2004 3. Romaniuk M., Nowak P., Monte Carlo methods: theory, algorithms and applications to selected financial problems, ICS PAS, 2015 4. Law A. M., Simulation Modeling and Analysis, McGraw-Hill, 2015

Witryna www przedmiotu:

brak

Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka MMC_W01

Zna metody generowania zmiennych dla najważniejszych rozkładów prawdopodobieństwa, algorytmy generowania dla rozkładu normalnego, metody generowania wielowymiarowych zmiennych losowych; ma wiedzę na temat ich podstaw matematycznych
Weryfikacja: kolokwia, egzamin
Powiązane charakterystyki kierunkowe: M2SMAD_W15
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_W02

Zna metody i algorytmy Monte Carlo w zakresie całkowania i optymalizacji; ma wiedzę na temat ich podstaw matematycznych.
Weryfikacja: kolokwia, egzamin
Powiązane charakterystyki kierunkowe: M2SMAD_W15
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_W03

Zna główne metody i algorytmy Markov Chain Monte Carlo (algorytm Metropolisa – Hastingsa, próbnik Gibbsa); ma wiedzę na temat ich podstaw matematycznych.
Weryfikacja: kolokwia, egzamin
Powiązane charakterystyki kierunkowe: M2SMAD_W15
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_W04

Zna podstawowe metody i algorytmy repróbkowania (bootstrap i jackknife); ma wiedzę na temat ich podstaw matematycznych.
Weryfikacja: kolokwia, egzamin
Powiązane charakterystyki kierunkowe: M2SMAD_W15
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_W05

Ma podstawową wiedzę dotyczącą uwarunkowań związanych z działalnością badawczą w zakresie statystyki i analizy danych.
Weryfikacja: kolokwia, egzamin
Powiązane charakterystyki kierunkowe: M2_W02
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka MMC_U01

Umie generować próbki pseudolosowe z różnych rozkładów prawdopodobieństwa, w tym z rozkładu normalnego i rozkładów wielowymiarowych.
Weryfikacja: kolokwia, przygotowanie prezentacji projektu laboratoryjnego
Powiązane charakterystyki kierunkowe: M2SMAD_U04
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_U02

Umie stosować metody Monte Carlo w zagadnieniach całkowania i optymalizacji.
Weryfikacja: kolokwia, przygotowanie prezentacji projektu laboratoryjnego
Powiązane charakterystyki kierunkowe: M2SMAD_U16
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_U03

Umie stosować podstawowe algorytmy dla metod Markov Chain Monte Carlo.
Weryfikacja: kolokwia, przygotowanie prezentacji projektu laboratoryjnego
Powiązane charakterystyki kierunkowe: M2SMAD_U16
Powiązane charakterystyki obszarowe:

Charakterystyka MMC_U04

Umie stosować podstawowe algorytmy repróbkowania.
Weryfikacja: kolokwia, przygotowanie prezentacji projektu laboratoryjnego
Powiązane charakterystyki kierunkowe: M2SMAD_U16
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka MMC_KS01

Rozumie potrzebę uczenia się przez całe życie, potrafi inspirować i organizować proces uczenia się innych osób.
Weryfikacja: kolokwia, egzamin, przygotowanie prezentacji projektu laboratoryjnego
Powiązane charakterystyki kierunkowe: M2SMAD_K02
Powiązane charakterystyki obszarowe: