Algorytmiczne modele zjawisk losowych (przedmiot obieralny-K1) I24000j

Efekty kształcenia
Symbol Student, który zaliczył przedmiot: Odniesienie do kierunkowych efektów kształcenia
EK1 posiada podstawową wiedzę o łańcuchach/procesach Markowa i ich zastosowaniach w modelowaniu rzeczywistych zjawisk losowych K_W01
K_U11

EK2 umie zrealizować grupowy eksperyment programistyczny związany z symulacją łańcucha lub procesu Markowa przy pomocy algorytmu probabilistycznego K_U11
K_U18

EK3 posiada podstawową wiedzę o sposobach analizy algorytmów probabilistycznych K_W01
K_W08

EK4 umie dokonać analizy łańcucha/procesu Markowa (wyznaczyć parametry) K_W01
K_U07

EK5 umie opracować model rzeczywistego zjawiska losowego w postaci łańcucha, procesu Markowa lub przy pomocy algorytmu probabilistycznego K_U07
K_U17

Efekt kształcenia Metoda weryfikacji Forma zajęć na której zachodzi weryfikacja
EK1 Kontakt ze studentem w czasie zajęć i podczas omawiania wyników sprawdzianu PS, W
EK2 kontakt ze studentem w czasie zajęć PS
EK3 Kontakt ze studentem w czasie zajęć i podczas omawiania wyników sprawdzianu PS, W
EK4 Kontakt ze studentem w czasie zajęć i podczas omawiania wyników sprawdzianu PS, W
EK5 Kontakt ze studentem w czasie zajęć PS
Bilans nakładu pracy studenta (w godzinach) 1 - Udział w wykładach 15x2 30
2 - Udział w zajęciach pracowni specjalistycznej 15x2 30
3 - Wykorzystanie treści wykładu do przygotowania się do zajęć pracowni specjalistycznej 15x1 15
4 - Przygotowanie do zaliczenia przedmiotu 10
5 - Praca domowa - projektowanie programów i eksperymenty 15x2 30
6 - Udział w konsultacjach 5
RAZEM: 120
Wskaźniki ilościowe Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela:
(6)+(1)+(2) 65 ECTS
2,5
Nakład pracy studenta związany z zajęciami o charakterze praktycznym:
(3)+(2)+(5) 75 3,0

Zaliczenie przedmiotu jest oparte o realizację zindywidualizowanego projektu
(1.5 godz.). Załączono przykład projektu.

Na projekt składa się:
a) opracowanie (niedużego) programu symulującego zachowanie pochłaniającego łańcucha/procesu Markowa o trzech stanach.
Przy pomocy symulacji wyznaczane są wartości średniej liczby kroków
do momentu pochłonięcia.
b) wyznaczenie, w oparciu o teorię łańcuchów/procesów Markowa teoretycznych wartości
średniej liczby kroków/średniego czasu do momentu pochłonięcia.
c) porównanie wartości wyznaczonych eksperymentalnie i teoretycznie oraz ocean jakości
pseudolosowego generatora użytego w symulacji.

Do realizacji projektu niezbędne są elementy wiedzy oraz umiejętności związanych z teorią łańcuchów/procesów Markowa (włącznie z prerekwizytami).

– studenci wykorzystują podstawowe fakty z Algebry Liniowej, Analizy Matematycznej
i Rachunku Prawdopodobieństwa,
– studenci wyznaczają macierze przejść niedużych programów probabilistycznych
interpretowanych jako łańcuchy/procesy Markowa,
– studenci wyznaczają (teoretyczne) wartości parametrówotrzymanych modeli Markowa
wykorzystując fakty dotyczące łańcuchów/procesów Markowa; studenci mogą posłużyć
się profesjonalnym oprogramowaniem (np. MatLab),
– studenci przeprowadzają eksperymenty programistyczne w celu wyznaczenia wartości
parametrów poprzez symulację,
– studenci formułują opinie na temat jakości generatorów pseudolosowych użytych
w symulacji,
– studenci przygotowują raport z realizacji projektu.

-----------------------------------------------------------------------------------------------

Przykład Projektu
-----------------------------------------------------------------------------------------------
Zadanie 1.

Dany jest algorytm probabilistyczny:

K: while x<>3 do
if x=1 then x:= random1
else x:= random2;

interpretowany z dyskretnym parametrem czasowym
w zbiorze {1, 2, 3} przy następujących realizacjach przypisań losowych

random1: 1: 0.0, 2: 0.4, 3: 0.6,
random2: 1: 0.3, 2: 0.0, 3: 0.7.

Posługując się, znanymi z zajęć, metodami rachunkowymi, proszę wyznaczyć
(a) macierze przejść algorytmów składowych oraz
algorytmu K,
(b) wektor średniej liczby kroków.

Zadanie 2.
Rozważamy proces Markowa P (z ciągłym parametrem czasowym) o zbiorze stanów
{1, 2, 3}, i zadanej macierzy intensywności
L = ... .
Proszę wyznaczyć
(c) wektor średnich czasów pochłonięcia.

Zadanie 3.
Organizując eksperyment programistyczny, poprzez implementację generatorów random1, random2, oraz procesu P z czasem ciągłym, z uwzględnieniem
macierzy L, proszę wyznaczyć (dla rzędu 1 000 powtórzeń „symulacji” procesu P):
(b’) wektor średniej liczby kroków,
(c’) wektor średnich czasów pochłonięcia.
Ponadto, proszę wyznaczyć
(d) procentową różnicę wartości między parametrami
wyznaczonymi teoretycznie oraz eksperymentalnie tzn. między wartościami
wyznaczonymi w punktach b i b’ oraz c i c’.

Sugestia 1:
W Zadaniu 1 wyznaczyć dla danego algorytmu K, odpowiadający mu łańcuch Markowa M (o trzech stanach).

a) podstawowa:

Feller W.: Wstęp do rachunku prawdopodobieństwa, PWN,
Warszawa 1977,

Kubik L., Krupowicz A.: Wprowadzenie do rachunku
prawdopodobieństwa i jego zastosowań, PWN,
Warszawa 1982,

Josifescu M.: Fnite Markov Processe and Their
Applications, John Wiley & Sons, New York,
London 1998,

Mirkowska G., Salwicki A.: Logika algorytmiczna dla
programistów, WNT, Warszawa 1985,

b) uzupełniająca:

Dańko W.: Algorytmiczne modele zjawisk losowych,
Wydawnictwa WSE w Białymstoku, Białystok 2006,