Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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)
- wykład problemowy

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- klasyczna metoda problemowa
- laboratoryjna

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

Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin, 30 miejsc więcej informacji
Laboratorium, 15 godzin, 16 miejsc więcej informacji
Wykład, 15 godzin, 30 miejsc więcej informacji
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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności mapa serwisu USOSweb 7.1.1.0-3 (2024-12-18)