Metody Probabilistyczne i Statystyka 2023/24

Podstawowe informacje

Kurs ten przeznaczony jest dla studentów 2 roku (3 semestru) studiów I stopnia na kierunku Informatyka Algorytmiczna. Obejmuje on wykład (30 h) oraz ćwiczenia (30 h).


Rozkład zajęć:

  • Wykład (K.G.)
    • Czwartek, 1315–1500, s. 329 bud. A-1
  • Ćwiczenia
    • Poniedziałek, 915–1100, s. D3.1 bud. C-16 (K.G.)
    • Środa, 730–900, s. D3.1 bud. C-16 (dr hab. S. Żeberski, prof. uczelni)
    • Czwartek, 730–900, s. D3.1 bud. C-16 (dr hab. S. Żeberski, prof. uczelni)


Opis kursu (karta przedmiotu): MAP002214Wc.pdf

Terminy egzaminów

  • I  termin: 07.02.2024. (środa), godz. 1100–1300, s. 329 bud. A-1
  • II termin: 14.02.2024. (środa), godz. 1100–1300, s. 23 bud. C-3

Harmonogram egzaminów – zima 2023/2024 na stronie Wydziału Informatyki i Telekomunikacji

Listy zadań na ćwiczenia

  • Lista 0 – powtórka z matematyki dyskretnej i analizy
  • Lista 1 – ciała i \(\sigma\)-ciała zbiorów
  • Lista 2 – przestrzenie probabilistyczne, własności prawdopodobieństwa
  • Lista 3 – prawdopodobieństwo warunkowe, niezależność zdarzeń
  • Lista 4 – zmienne losowe i ich rozkłady, własności dystrybuanty, dyskretne zmienne losowe
  • Lista 5 – zmienne losowe o rozkładach dyskretnych i ciągłych, funkcje zmiennych losowych
  • Lista 6 – wektory losowe, niezależność zmiennych losowych, wartość oczekiwana dyskretnych zmiennych losowych
  • Lista 7 – wartość oczekiwana, wariancja i momenty wyższych rzędów zmiennych losowych
  • Lista 8 – wybrane rozkłady dyskretne oraz ciągłe i ich własności
  • Lista 9 – nierówności "ogonowe", kule i urny, birthday paradox, coupon collector's problem
  • Lista 10 – kowariancja i korelacja, sumy niezależnych zmiennych losowych, probabilistyczne funkcje tworzące
  • Lista 11 – centralne twierdzenie graniczne, zbieżność ciągów zmiennych losowych
  • Lista 12 – wprowadzenie do łańcuchów Markowa

Zasady zaliczenia kursu

Grupa kursów "Metody Probabilistyczne i Statystyka" obejmuje ćwiczenia oraz wykład (z egzaminem). Końcowa wspólna ocena z grupy kursów obliczana jest na podstawie wyników uzyskanych na ćwiczeniach i na egzaminie.


Zaliczenie ćwiczeń

  1. Wykładowca ogłasza z wyprzedzeniem listy zadań do samodzielnego rozwiązania. Na ćwiczeniach studenci prezentują rozwiązania zadań oraz wyjaśniane są wątpliwości dotyczące rozwiązań. Decyzję odnośnie wyboru zadań do rozwiązania podejmuje prowadzący.
  2. Podstawą zaliczenia ćwiczeń są:
    • punkty uzyskane na sprawdzianach przeprowadzanych na ćwiczeniach oraz
    • punkty uzyskane za zadania domowe do samodzielnego rozwiązania.
  3. Końcowy wynik punktowy z ćwiczeń \(C\) obliczany jest jako średnia punktów ze sprawdzianów i zadań domowych. Średnia może być podwyższona przez prowadzącego na podstawie aktywności studenta na ćwiczeniach, jednak nie wyżej niż do 6,0 (tj. \(C \in [0,6]\)).
  4. Punktacja z ćwiczeń nie podlega poprawianiu po zakończeniu zajęć.
Sprawdziany
  1. Sprawdziany będą polegały na rozwiązaniu jednego zadania i będą punktowane w skali od 0 do 5. Materiałem obowiązującym na sprawdzianie są dwie poprzednie listy zadań. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi.
  2. Nieusprawiedliwiona nieobecność na sprawdzianie lub nieoddanie rozwiązania skutkuje wynikiem 0. W przypadku usprawiedliwionej nieobecności prowadzący ustala ze studentem indywidualny termin zaliczenia sprawdzianu.
  3. Do obliczenia końcowego wyniku z ćwiczeń \(C\) brane są punkty ze wszystkich sprawdzianów z pominięciem jednego, za który otrzymano najmniejszą liczbę punktów.
Zadania domowe
  1. Wykładowca ogłasza z wyprzedzeniem zadania domowe do samodzielnego rozwiązania z jednolitym terminem realizacji dla wszystkich grup.
  2. Rozwiązania zadań studenci przesyłają przez platformę MS Teams.
  3. Każde zadanie domowe punktowane jest w skali od 0 do 5. Liczba punktów przyznana za rozwiązanie zadania zależeć będzie od jego jakości i kompletności.
  4. W przypadku opóźnienia do 2 tygodni uzyskany wynik punktowy mnoży się przez 0,5. Rozwiązania oddane jeszcze później skutkują otrzymaniem 0 punktów.
  5. W/w terminy ulegają przedłużeniu o okres usprawiedliwionej nieobecności. Okres ten może ulec przesunięciu w trudnych przypadkach losowych (prowadzący ustala ze studentem indywidualny termin).

Egzamin

  1. Terminy egzaminu oraz jego forma podane zostaną do końca czwartego tygodnia zajęć.
  2. Egzamin oceniany jest w skali od 2,0 do 5,5.
  3. Do egzaminu w II terminie mogą przystąpić osoby, które w I terminie uzyskały wynik niższy niż 3,0 (w tym osoby nieobcene), a także – wyłącznie za zgodą prowadzącego – osoby, których wynik z egzaminu jest rażąco niższy od wyniku uzyskanego na ćwiczeniach. W każdym przypadku wynik w II terminie nadpisuje wynik z I terminu.
  4. Na egzaminie jedyną dopuszczalną pomocą naukową jest kartka formatu A4 podpisana w taki sposób, aby z odległości 2 metrów dało się ustalić jej właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek, książek lub innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.

Prawa autorskie

Odpowiedzi na sprawdzianach, egzaminie oraz rozwiązania zadań domowych, co do których prowadzący nie może ustalić autorstwa (przypadek, gdy studenci porozumiewają się w trakcie sprawdzianu bądź egzaminu lub przedkładają rozwiązania zadań o identycznej formie), nie mogą być punktowane i są traktowane jako „brak odpowiedzi” / „nieoddane zadanie”.


Ocena końcowa z grupy kursów

  1. Warunkiem koniecznym zaliczenia grupy kursów jest uzyskanie co najmniej 2,5 punktów z ćwiczeń oraz zdanie egzaminu z wynikiem wyższym niż 2,0.
  2. Ocena końcowa obliczana jest jako średnia punktów z ćwiczeń \(C \) i wyniku egzaminu \(E\), tj. \(O = (C + E)/2\), zaokrąglona do najbliższej oceny w następujący sposób: \begin{split} & \texttt{if } C \lt 2,\!5 \texttt{ or } E = 2,\!0 \texttt{ then } ocena = 2.0 \\ & \texttt{else} \\ & \qquad ocena = \begin{cases} 3.0 & \texttt{if } \ O \lt 3,\!25 \\ 3.5 & \texttt{if } \ O \in [3,\!25, \ 3,\!75) \\ 4.0 & \texttt{if } \ O \in [3,\!75, \ 4,\!25) \\ 4.5 & \texttt{if } \ O \in [4,\!25, \ 4,\!75) \\ 5.0 & \texttt{if } \ O \in [4,\!75, \ 5,\!25) \\ 5.5 & \texttt{if } \ O \in [5,\!25, \ 5,\!75] \end{cases} \end{split}

Literatura podstawowa

  • M. Baron, Probability and Statistics for Computer Scientists, 2nd Edition, Chapman & Hall/CRC Press, 2013 (wersja cyfrowa jest dostępna dla studentów PWr w bazie O'Reilly Safari – patrz instrukcja na stronie Biblioteki PWr)
  • G. Grimmett, D. Welsh, Probability. An introduction, 2nd Edition, Oxford University Press, 2014
  • W. Kordecki, Rachunek prawdopodobieństwa i statystyka matematyczna. Definicje, twierdzenia, wzory, Oficyna Wydawnicza GiS, Wrocław 2010
  • M. Mitzenmacher, E. Upfal, Probability and Computing. Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd Edition, Cambridge University Press, 2017

Literatura uzupełniająca

  • R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995
  • J.L. Johnson, Probability and Statistics for Computer Science, John Wiley & Sons, 2008
  • S.M. Ross, A First Course in Probability, 9th Edition, Pearson Education Ltd., 2014
  • S.M. Ross, Introductory Statistics, 4th Edition, Academic Press, 2017
  • P. Billingsley, Prawdopodobieństwo i miara, Wydawnictwo Naukowe PWN, Warszawa 2021
  • P. Billingsley, Probability and Measure, 3rd Edition, John Wiley & Sons, 1995
  • W. Feller, An Introduction to Probability Theory and Its Applications, vol. I, 3rd Edition, John Wiley & Sons, 1968
  • G. Grimmett, R. Stirzaker, Probability and Random Processes, 3rd Edition, Oxford University Press, 2001

Materiały do kursu, przydatne linki i narzędzia

Zagadnienia omówione na wykładach (w przybliżeniu)

Slajdy do wykładów oraz pliki z obliczeniami numerycznymi i symbolicznymi będą udostępniane w zakładce 'Pliki' na kanale zespołu (Czw 13:15) Wykład - Metody Probabilistyczne i Statystyka (Zima 23/24) na platformie MS Teams.


  1. wykład (05.10.2023.)
    • informacje wstępne
      • organizacja pracy i zasady zaliczenia
      • literatura i materiały do kursu
    • wprowadzenie do kursu
      • zastosowania metod probabilitsycznych w informatyce
      • motywacje
    • ciała i \(\sigma\)-ciała podzbiorów
      • pojęcie ciała i \(\sigma\)-ciała
      • podstawowe własności
      • proste przykłady \(\sigma\)-ciał
      • \(\sigma\)-ciało generowane przez rodzinę podzbiorów
  2. wykład (12.10.2023.)
    • podstawowe pojęcia i intuicje związane z teorią miary
      • \(\sigma\)-ciało podzbiorów borelowskich \(\mathcal{B}(\mathbb{R}^{d}) = \sigma(OPEN(\mathbb{R}^{d}))\)
      • pojęcia przestrzeni mierzalnej, miary, przestrzeni z miarą, zbioru miary zero
      • nieformalnie o mierze Lebesgue'a (intuicje, podstawowe fakty dot. istnienia)
    • przestrzenie probabilistyczne
      • definicja przestrzeni probabilistycznej
      • podstawowe własności prawdopodobieństwa
    • przykłady przestrzeni probabilistycznych
      • przestrzenie kombinatoryczne
      • przestrzenie dyskretne
      • przestrzenie nieprzeliczalne ("geometryczna" definicja prawdopodobieństwa)
  3. wykład (19.10.2023.)
    • "geometryczna" definicja prawdopodobieństwa – uzupełnienie
    • omówienie Zadania domowego 1
    • prawdopodobieństwo warunkowe
      • wprowadzenie, podstawowe intuicje
      • definicja i przykłady
      • wzór na prawdopodobieństwo całkowite
      • twierdzenie (wzór) Bayesa
      • przykład – wiarygodność testów diagnostycznych (więcej przykładów)
    • niezależność zdarzeń
      • defnicja zdarzeń niezależnych
      • przykłady zdarzeń zależnych, niezależnych i parami niezależnych
      • przykład – niezawodność systemów
      • model – niezależne rzuty monetą (ciągi losowych bitów)
  4. wykład (26.10.2023.)
    • podstawowe intuicje związane z teorią miary – cd.
      • pojęcie funkcji mierzalnych – definicja, intuicje, przykład
      • równość prawie wszędzie (prawie na pewno, a.s.)
    • zmienne losowe
      • defnicja zmiennej losowej
      • rozkład zmiennej losowej
      • przykłady
    • dystrybuanta zmiennej losowej
      • defnicja, przykłady, własności
      • rozkłady dyskretne, ciągłe i mieszane
    • zmienne losowe dyskretne
      • funkcja masy prawdopodobieństwa (PMF)
      • przykłady
  5. wykład (09.11.2023.)
    • omówienie Zadania domowego 2 (model kul i urn)
    • rozkłady (absolutnie) ciągłe – wprowadzenie
      • funkcja gęstości prawdopodobieństwa (PDF)
      • pojęcie rozkładu (absolutnie) ciągłego
      • podstawowe własności gęstości
      • przykład – losowy punkt z odcinka \([0,1]\)
      • funkcja gęstości prawdopodobieństwa jako pochodna dystrybuanty
    • funkcje zmiennych losowych
      • funkcje dyskretnych zmiennych losowych
      • przykład – kwardat dyskretnej zmiennej losowej
      • funkcje zmiennych losowych o rozkładach ciągłych
      • przykład – funkcja liniowa \(Y = a X + b,\ a > 0\)
      • uogólnienie dla funkcji ściśle monotonicznych i różniczkowalnych
  6. wykład (16.11.2023.)
    • wektory losowe i rozkłady wielowymiarowe
      • pojęcie wektora losowego i dystrybuanty łącznej
      • rozkład łączny (joint distribution) i rozkłady brzegowe (marginal distributions)
      • wektory losowe o rozkładach dyskretnych i ciągłych
      • joint PMF/PDF, marginal PMF/PDF i ich własności
      • przykłady
      • funkcje wektorów losowych
    • niezależność zmiennych losowych
      • definicja ogólna
      • kanoniczny przykład niezależnych zmiennych losowych – rzuty na osie
      • niezależność zmiennych losowych o rozkładach dyskretnych i ciągłych
    • wartość oczekiwana zmiennej losowej – część 1.
      • wartość oczekiwana dyskretnej zmiennej losowej – defincja, przykłady
      • wartość oczekiwana funkcji dyskretnej zmiennej losowej
  7. wykład (23.11.2023.)
    • wartość oczekiwana zmiennej losowej – część 2.
      • wartość oczekiwana funkcji dyskretnej zmiennej losowej – przykład
      • wartość oczekiwana zmiennej losowej o rozkładzie ciągłym – definicja, przykłady
      • wartość oczekiwana funkcji zmiennej losowej i wektora losowego
      • wartość oczekiwana jako całka (definicja ogólna) – intuicja
      • własności wartości oczekiwanej
    • momenty i momenty centralne zmiennej losowej
      • definicja i podstawowe własności
    • wariancja zmiennej losowej
      • definicja, intuicje
      • przykład
      • własności wariancji zmiennej losowej
  8. wykład (30.11.2023.)
    • omówienie Zadania domowego 3 (ballanced allocation, eksperymantalna analiza probabilistyczna złożoności obliczeniowej algorytmu sortowania przez wstawianie)
    • wybrane rodziny rozkładów dyskretnych i ich podstawowe własności
      • rozkład Bernoulliego \(Ber(p)\)
      • rozkład dwumianowy (binomial) \(Bin(n,p)\)
      • rozkład Poissona \(Po(\lambda)\)
      • rozkład geometryczny \(Geo(p)\)
      • rozkład ujemny dwumianowy (negative binomial) \(NB(k,p)\)
    • wybrane rodziny rozkładów ciągłych i ich podstawowe własności
      • rozkład jednostajny \(U([a,b])\)
      • rozkład wykładniczy \(Exp(\lambda)\)
      • rozkład gamma \(Gamma(\alpha, \beta)\)
      • rozkład normalny \(\mathcal{N}(\mu, \sigma^2)\)
    • rozkłady prawdopodobieństwa w pakietach matematycznych
      • obliczenia symboliczne i numeryczne na przykładzie systemu Wolfram Mathematica
  9. wykład (07.12.2023.)
    • nierówności "ogonowe" dla zmiennych losowych
      • "ogony" zmiennych losowych – motywacje, uwagi
      • nierówność Markowa
      • nierówność Czebyszewa
      • przykład – szacowanie ogonów rozkładu dwumianowego
    • sumy niezależnych zmiennych losowych o rozkładach dyskretnych
      • funkcja masy ppb. sumy niezależnych zmiennych losowych
      • przykład – suma niezależnych zmiennych losowych o rozkładach \(Bin(n,p)\) i \(Bin(m,p)\)
    • sumy niezależnych zmiennych losowych o rozkładach ciągłych
      • gęstość sumy niezależnych zmiennych losowych jako splot gęstości
      • przykład – suma niezależnych zmiennych losowych o rozkładzie \(U([0,1])\)
  10. wykład (14.12.2023.)
    • zmienne losowe zależne
      • kowariancja
      • współczynnik korelacji
      • własności kowariancji i współczynnika korelacji
    • nierówność Cauchy'ego-Schwarza dla wartości oczekiwanych
    • funkcje tworzące prawdopodobieństwo dyskretnych zmiennych losowych
      • funkcje tworzące prawdopodobieństwo (PGF) – definicja, przykład
      • własności PGF
      • wykorzystanie PGF do wyznaczania wartości oczekiwanej i wariancji
      • twierdzenie o jednoznaczności PGF
      • PGF sumy niezależnych zmiennych losowych
  11. wykład (21.12.2023.)
    • funkcje tworzące momenty zmiennych losowych
      • funkcje tworzące momenty (MGF) – definicja, przykłady
      • MGF zmiennych losowych o rozkładach dyskretnych i ciągłych
      • własności MGF
      • wykorzystanie MGF do wyznaczania wartości oczekiwanej i momentów wyższych rzędów
      • MGF sumy niezależnych zmiennych losowych
      • twierdzenie o jednoznaczności MGF
      • uwagi dotyczące moemntów zmiennej losowej
    • ★ funkcje charakterystyczne zmiennych losowych (zagadnienie nieobowiązkowe)
      • funkcje charakterystyczne – definicja, uwagi, przykłady
      • podstawowe własności funkcji charakterystycznych
      • twierdzenie o jednoznaczności
    • lematy Borela-Cantellego
      • rodziny zdarzeń \((A_n)_{n \geq 1}\), zdarzenia \(\bigcup\limits_{n \geq 1} A_n\) oraz \(\bigcap\limits_{n \geq 1} A_n\)
      • przykład – proste błądzenie losowe na \(\mathbb{Z}\)
      • zdarzenia \(\{A_n \text{ i.o.}\} = \bigcap\limits_{n \geq 1} \bigcup\limits_{k \geq n} A_k\) (\(A_n\) infinitely often) oraz \(\{A_n \text{ ult.}\} = \bigcup\limits_{n \geq 1} \bigcap\limits_{k \geq n} A_k\) (\(A_n\) ultimately)
      • lematy Borela-Cantellego (z dowodami), przykłady zastosowania
  12. wykład (11.01.2024.)
    • omówienie Zadania domowego 4 (nierówności ogonowe, proste błądzenie losowe na \(\mathbb{Z}\), testowanie statystyczne PRNGs)
    • prawa wielkich liczb i zbieżność ciągów zmiennych losowych
      • prawa wielkich liczb – intuicje, motywacje, zastosowania
      • zbieżność według prawdopodobieństwa
      • słabe prawo wielkich liczb (WLLN) wraz z dowodem
      • zbieżność prawie na pewno (a.s.)
      • mocne prawo wielkich liczb (SLLN)
      • przykład ciągu zmiennych losowych zbieżnego według prawdopodobieństwa, ale nie prawie na pewno
    • centralne twierdzenie graniczne (CLT) i słaba zbieżność rozkładów
      • centralne twierdzenie graniczne – intuicje, motywacje
      • przykład numeryczny (Wolfram Mathematica) – odchylenia sum i.i.d. zmiennych losowych od wartości oczekiwanej
      • normalizacja zmiennej losowej
      • zbieżność według rozkładu (słaba zbieżność)
      • centralne twierdzenie graniczne ("wersja" Lindenberga-Lévy'ego)
      • CLT – uwagi, intuicje, interpretacja statystyczna
      • przykład zastosowania CLT – aproksymacja rozkładu dwumianowego rozkładem normalnym
      • przykład zastosowania CLT – statistical sampling (estymacja population proportion)
      • uwagi dotyczące słabej zbieżności – związki z innymi typami zbieżności, twierdzenie Lévy'ego o ciągłości
      • przykład ciągu zmiennych losowych zbieżnego według rozkładu, ale nie według prawdopodobieństwa
  13. wykład (18.01.2024.)
    • procesy stochastyczne – motywacje, intuicje, podstawowe pojęcia
    • łańcuchy Markowa – wprowadzenie
      • definicja, własność Markowa (własność braku pamięci)
      • prawdopodobieństwa przejść
      • jednorodne łańcuchy Markowa (ang. time homogeneous)
      • rozkład początkowy i rozkład po \(n\) krokach
      • macierz przejścia
      • prawdopodobieństwa przejścia w \(n\) krokach
    • łańcuchy Markowa – pierwsze proste przykłady
      • "uproszczona prognoza pogody" – dwustanowy łańcuch Markowa
      • prosty spacer losowy na grafie cyklicznym z 4 wierzchołkami
      • obliczanie rozkładów łańcucha Markowa w kolejnych krokach
      • macierze przejścia
  14. wykład (25.01.2024.)
    • łańcuchy Markowa – wprowadzenie (ciąg dalszy)
      • macierz przejścia w \(n\) krokach
      • wyznaczanie rozkładu łańcucha Markowa po \(n\) krokach na podstawie macierzy przejścia
      • równania Chapmana-Kołmogorowa
      • przykłady
    • reprezentacja grafowa łańcuchów Markowa (diagram przejścia)
    • stany komunikujące się, klasy komunikacji, stany pochłaniające
    • (nie)redukowalność i (nie)okresowość
      • (nie)redukowalne łańcuchy Markowa
      • okres stanu, stany nieokresowe, (nie)okresowe łańcuchy Markowa
      • przykłady (nie)redukowalnych i (nie)okresowych łańcuchów Markowa
      • nieredukowalne i nieokresowe łańcuchy Markowa – własności macierzy przejścia w \(n\) krokach
  15. wykład (01.02.2024.)
    • rozkład stacjonarny łańcucha Markowa ze skończoną przestrzenią stanów
      • rozkład stacjonarny – motywacje i intuicje
      • definicja i podstawowe własności
      • przykłady
    • zbieżność rozkładu łańcucha Markowa ze skończoną przestrzenią stanów w czasie
      • warunki na istnienie i jednoznaczność rozkładu stacjonarnego
      • warunki na zbieżność do rozkładu stacjonarnego
      • zbieżność do rozkładu stacjonarnego a macierz przejścia w \(n\) krokach
      • przykłady
      • jednostajny rozkład stacjonarny – podwójnie stochastyczna macierz przejścia
    • przykład zastosowania łańcuchów Markowa w algorytmice – Markov Chain Monte Carlo
      • zbiór niezależny w grafie nieskierowanym
      • algorytm MCMC generowania losowego zbioru niezależnego
      • analiza własności symulowanego łańcucha Markowa – prawdopodobieństwa przejść, nieredukowalność, nieokresowość, rozkład stacjonarny
      • kilka uwag o tempie zbieżności do rozkładu stacjonarnego
    • najważniejsze informacje dotyczące egzaminu