Algorytmy probabilistyczne (p. obieralny) MAT3512

Treści programowe:

Część I. Dyskretny Parametr Czasu.

I.1. Skończone Łańcuchy Markowa.

Macierz przejścia. Trajektorie (obliczenia), liczba kroków
trajektorii,
Prawdopodobieństwo realizacji trajektorii.
Macierz przejścia w n-krokach między dwoma stanami.
Klasyfikacja stanów (pochłaniające, chwilowe, ...).
Rodzaje łańcuchów Markowa: pochłaniające, regularne,
ergodyczne.
Asymptotyczna macierzy przejścia pochłaniającego łańcucha
Markowa.
Średnia liczba kroków trajektorii pochłaniającego łańcucha
Markowa.
Ergodyczne i regularne i łańcuchy Markowa.
Średnia liczba kroków pierwszego powrotu do stanu,
Średnia liczba kroków pierwszego przejścia między stanami.

I.2. Iteracyjne Algorytmy Probabilistyczne. Skończone
Interpretacje.

Semantyka obliczeń iteracyjnych algorytmów
probabilistycznych.
Wzajemne interpretowalność skończonych łańcuchów
Markowa oraz iteracyjnych algorytmów probabilistycznych
interpretowanych w (ustalonej) skończonej dziedzinie.
Algebraiczne semantyka dla iteracyjnych algorytmów
probabilistycznych
interpretowanych w skończonych dziedzinach.
Asymptotyczna macierz przejścia iteracyjnego algorytmu
probabilistycznego.
Średnia liczba kroków trajektorii iteracyjnego algorytmu
probabilistycznego.

I.3. Uwagi o jakości generatorów pseudolosowych.

II. Ciągły Parametr Czasu.

II.1. Skończone Procesy Markowa.

Chapman’a-Kołmogorowa semantyka obliczeń dla skończenie
stanowych procesów Markowa. Macierz przejścia w chwili t.
Pochłaniając, regularne i ergodycznej procesy Markowa.
Średnia liczba kroków obliczeń dla pierwszego przejścia
między stanami.
Średni czas obliczenia realizującego pierwsze przejście między
stanami.
Średnia liczba kroków obliczeń dla powrotu do stanu.
Średni czas obliczenia realizującego powrót do stanu.

II.2. Algorytmy Iteracyjne Probabilistyczne. Skończone
Interpretacje.

Określenie semantyki obliczeń iteracyjnych algorytmów
probabilistycznych z czasem ciągłym w oparciu o semantykę
obliczeniową pochłaniających procesów Markowa.

II.3 Przykłady wykorzystania modelu iteracyjnych algorytmów
probabilistycznych z ciągłym parametrem czasu do analizy
rzeczywistych procesów losowych.