Algorytmy probabilistyczne
Informacje ogólne
Kod przedmiotu: | 1000-MS1-AlgProbab |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Algorytmy probabilistyczne |
Jednostka: | Wydział Matematyki i Informatyki |
Grupy: | |
Punkty ECTS i inne: |
4.00
|
Język prowadzenia: | polski |
Wymagania wstępne: | Podstawowe umiejętności w zakresie analizy matematycznej. Kurs rachunku prawdopodobieństwa. |
Całkowity nakład pracy studenta: | udział w wykładach - 15 godzin - udział w ćwiczeniach - 15 godzin - udział w laboratorium - 15 godzin - przygotowanie do zaliczenia ćwiczeń - 30 godzin - przygotowanie do zaliczenia egzaminu - 30 godzin - lektura literatury - 15 godzin Łącznie 120 godzin. (4 ECTS) |
Efekty uczenia się - wiedza: | W1. Student rozumie różnicę między algorytmem randomizowanym a algorytmem probabilistycznym. W2. Zna podstawowe metody Monte Carlo. W3. Rozumie metody obliczeń oparte na łańcuchach Markowa. W4. Zna najważniejsze zastosowania dynamicznych metod Monte Carlo. |
Efekty uczenia się - umiejętności: | U1. Student potrafi napisać i zaimplementować prosty algorytm Monte Carlo U2. Umie symulować najważniejsze rozkłady prawdopodobieństwa. U3. Potrafi empirycznie ocenić jakość prowadzonych symulacji. |
Efekty uczenia się - kompetencje społeczne: | K1. Student ma świadomość powszechności metod probabilistycznych i statystycznych w funkcjonowaniu współczesnych społeczeństw (K_K02) K2. Student zna niebezpieczeństwa związane z manipulacją danymi (K_K01) |
Metody dydaktyczne: | Wykład konwencjonalny wspomagany komputerowo Ćwiczenia rachunkowe Samodzielne programowanie. |
Metody dydaktyczne eksponujące: | - pokaz |
Metody dydaktyczne podające: | - wykład informacyjny (konwencjonalny) |
Metody dydaktyczne poszukujące: | - ćwiczeniowa |
Metody dydaktyczne w kształceniu online: | - metody służące prezentacji treści |
Skrócony opis: |
Przedmiot stanowi pomost między podstawowym kursem z rachunku prawdopodobieństwa, a zaawansowanymi metodami modelowania stochastycznego. W oparciu o znane pojęcia i fakty budowane są metody obliczeniowe (Monte Carlo, Markov Chain Monte Carlo) powszechnie używane w zastosowaniach. W tle doskonalone są techniki symulacyjne studenta. |
Pełny opis: |
1. Algorytmy randomizowane a algorytmy probabilistyczne. 1.1.Quicksort jako przykład algorytmu randomizowanego. 1.2 Nierówności Chernoffa i pogłębiona analiza Quicksortu. 2..Algorytmy Monte Carlo. 2.1 Prosta metoda Monte Carlo. Generatory liczb losowych. 2.2 Metoda odwracania dystrybuanty. 2.3 Specjalne metody Monte Carlo. 2.4 Metoda eliminacji i jej warianty. 2.5 Próbkowanie ważone. 2.6 Metody redukcji wariancji. 3. Dynamiczne metody Monte Carlo (MCMC). 3.1 Łańcuchy Markowa z dyskretną przestrzenią stanów. 3.2 Rozkłady stacjonarne. Równania równowagi szczegółowej. 3.3 Klasyfikacja stanów łańcucha Markowa. 3.4 Twierdzenie ergodyczne dla łańcuchów Markowa. 3.5 Algorytm Metropolisa-Hastingsa. 3.6 Pola Gibbsa i metoda symulowanego wyżarzania. 3.7 Łańcuchy Markowa z przeliczalną przestrzenią stanów. |
Literatura: |
1. O. Häggström, „Finite Markov chains and algorithmic applications”, Cambridge University Press, Cambridge 2002. 2. M. Harchol-Balter, „Introduction to Probability for Computing”, Cambridge University Press, Cambridge 2024. 3. M. Romaniuk, „Metody Monte Carlo”, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa 2019. 4. R. Wieczorkowski i R. Zielinski, „Komputerowe generatory liczb losowych”, Wydawnictwo Naukowo-Techniczne, Warszawa 1997. |
Metody i kryteria oceniania: |
Ćwiczenia kończą się zaliczeniem na ocenę na podstawie sprawdzianów pisemnych – U2, W2, W4, K1 Laboratoria kończą się zaliczeniem U1, U2, U3, K1, Wykład kończy się egzaminem ustnym – W1, W2, W3, K1, K2 |
Praktyki zawodowe: |
Nie dotyczy |
Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2025-02-24 - 2025-09-30 |
Przejdź do planu
PN CW
WT WYK
LAB
LAB
ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 15 godzin, 30 miejsc
Laboratorium, 15 godzin, 16 miejsc
Wykład, 15 godzin, 30 miejsc
|
|
Koordynatorzy: | Adam Jakubowski | |
Prowadzący grup: | Adrian Falkowski, Adam Jakubowski | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Laboratorium - Zaliczenie Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.