Karol Gotfryd

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, 13¹⁵–15⁰⁰, s. 29 bud. D-1
• Ćwiczenia
  • Środa, 9¹⁵–11⁰⁰, s. 35 bud. C-4 (K.G.)
  • Środa, 13¹⁵–15⁰⁰, s. 34 bud. C-4 (dr P. Szczepaniak)
  • Piątek, 11¹⁵–13⁰⁰, s. D3.1 bud. C-16 (dr M. Michalski)

Opis kursu (karta przedmiotu): MAP002214Wc.pdf

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
• Lista 7 – wariancja, wybrane rozkłady dyskretne i ich własności, nierówności "ogonowe" + dodatkowo: kule i urny, birthday paradox, coupon collector's problem
• Lista 8 – wybrane rozkłady ciągłe i ich własności
• Lista 9 – kowariancja i korelacja, sumy niezależnych zmiennych losowych, probabilistyczne funkcje tworzące

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 z dwóch sprawdzianach przeprowadzanych na ćwiczeniach (składowe \(S_1\) i \(S_2\))
   • punkty za zadania domowe do samodzielnego rozwiązania (składowa \(Z\)).
3. Końcowy wynik punktowy z ćwiczeń \(C\) obliczany jest jako średnia punktów ze sprawdzianów i zadań domowych zgodnie ze wzorem \(C = (S_1 + S_2 + Z)/3\). Ś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ęć.
5. Kwestie tu nieustalone określa prowadzący ćwiczenia.

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 nieobecne), 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), lub w których nie zostały wyraźnie oznaczone źródła pochodzenia wykorzystywanych fragmentów (brak odpowiednich cytowań lub informacji o wygenerowaniu przez dostępne narzędzia, w tym AI), 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 if } O \ge 5,\!25 \texttt{ and } E \ge 5,\!0 \texttt{ then } ocena = 5.5\\ & \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 \ge 4,\!75 \end{cases} \end{split}

Literatura podstawowa

• G. Grimmett, D. Welsh, Probability. An introduction, 2^nd Edition, Oxford University Press, 2014
• M. Baron, Probability and Statistics for Computer Scientists, 3^rd Edition, Chapman & Hall/CRC Press, 2019 (wersja cyfrowa jest dostępna dla studentów PWr w bazie O'Reilly Safari – patrz instrukcja na stronie Biblioteki PWr)
• 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, 2^nd 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, 10^th Edition, Pearson Education Ltd., 2019
• S.M. Ross, Introductory Statistics, 4^th Edition, Academic Press, 2017
• P. Billingsley, Prawdopodobieństwo i miara, Wydawnictwo Naukowe PWN, Warszawa 2021
• P. Billingsley, Probability and Measure, 3^rd Edition, John Wiley & Sons, 1995
• W. Feller, An Introduction to Probability Theory and Its Applications, vol. I, 3^rd Edition, John Wiley & Sons, 1968
• G. Grimmett, R. Stirzaker, Probability and Random Processes, 4^th Edition, Oxford University Press, 2020

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

• C.M. Grinstead, J.L. Snell, Introduction to Probability – Open Textbook Library
• D. Lane, Introduction to Statistics – Open Textbook Library
• Random – a website devoted to probability, mathematical statistics, and stochastic processes
• RANDOM.ORG – the Random Number Service
• WolframAlpha

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) Metody Probabilistyczne i Statystyka - Wykład (Zima 24/25) na platformie MS Teams.

1. wykład (03.10.2024.)
   • informacje wstępne
     • organizacja pracy i zasady zaliczenia
     • literatura i materiały do kursu
   • wprowadzenie do kursu
     • zastosowania metod probabilistycznych 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
     • \(\sigma\)-ciało podzbiorów borelowskich \(\mathcal{B}(\mathbb{R}^{d}) = \sigma(OPEN(\mathbb{R}^{d}))\)
     • dodatkowe materiały online do wykładu i listy 1 na ćwiczenia
2. wykład (10.10.2024.)
   • podstawowe pojęcia i intuicje związane z teorią miary
     • pojęcia przestrzeni mierzalnej, miary, przestrzeni z miarą, zbioru miary zero
     • nieformalnie o mierze Lebesgue'a (intuicje, podstawowe fakty dot. istnienia)
   • przestrzenie probabilistyczne
     • próba formalnego opisu eksperymentu losowego – motywacje i intuicje
     • definicja przestrzeni probabilistycznej
     • podstawowe własności prawdopodobieństwa
   • przykłady przestrzeni probabilistycznych i ich podstawowe własności
     • przestrzenie kombinatoryczne
     • przestrzenie dyskretne (skończone i przeliczalne nieskończone)
     • nieistnienie rozkładu jednostajnego na przestrzeni przeliczalnej nieskończonej
3. wykład (17.10.2024.)
   • "geometryczna" definicja prawdopodobieństwa – przykład przestrzeni nieprzeliczalnej
   • 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
4. wykład (24.10.2024.)
   • niezależność zdarzeń – uzupełnienie
     • przykłady – niezawodność systemów, transmisje w sieciach single-hop
     • model – niezależne rzuty monetą (ciągi losowych bitów)
   • 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 (więcej przykładów)
     • związki funkcji masy prawdopodobieństwa z dystrybuantą
5. wykład (07.11.2024.)
   • zmienne losowe dyskretne – uzupełnienie
   • 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 i rozkładów ciągłych
     • 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
6. wykład (14.11.2024.)
   • funkcje zmiennych losowych o rozkładach ciągłych – uzupełnienie
     • przykład – funkcja liniowa \(Y = a X + b,\ a > 0\)
     • uogólnienie dla funkcji ściśle monotonicznych i różniczkowalnych
   • 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
7. wykład (21.11.2024.)
   • niezależność zmiennych losowych – uzupełnienie
     • niezależność zmiennych losowych o rozkładach dyskretnych i ciągłych
   • wartość oczekiwana zmiennej losowej
     • wartość oczekiwana dyskretnej zmiennej losowej – defincja, przykłady
     • wartość oczekiwana funkcji dyskretnej zmiennej losowej
     • 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
8. wykład (28.11.2024.)
   • wartość oczekiwana zmiennej losowej – uzupełnienie
     • wartość oczekiwana iloczynu zmiennych losowych
   • momenty i momenty centralne zmiennej losowej
   • definicja i podstawowe własności
   • wariancja zmiennej losowej
   • definicja, intuicje
   • odchylenie standardowe
   • przykład
   • własności wariancji zmiennej losowej
   • 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)\)
   • rozkłady prawdopodobieństwa w pakietach matematycznych
     • obliczenia symboliczne i numeryczne na przykładzie systemu Wolfram Mathematica
9. wykład (05.12.2024.)
   • wybrane rodziny rozkładów dyskretnych – uzupełnienie
     • wybrane własności rozkładu geometrycznego \(Geo(p)\) i ujemnego dwumianowego \(NB(k,p)\)
   • omówienie Zadania domowego 3 (ballanced allocation, eksperymantalna analiza probabilistyczna złożoności obliczeniowej algorytmu sortowania przez wstawianie, prosty model komunikacji z zakłóceniami)
   • 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)\)
   • nierówności "ogonowe" (koncentracyjne) dla zmiennych losowych – wprowadzenie
     • uwagi o istnieniu momentów zmiennej losowej
     • "ogony" zmiennych losowych – motywacje, uwagi
     • nierówność Markowa i Czebyszewa – wprowadzenie
10. 12.12.2024. – wykład z Baz danych i zarządzania informacją (dr inż. A. Lauks-Dutka) – zamiana za piątek 20.12.2024.
10. wykład (19.12.2024.)
    • nierówności "ogonowe" (koncentracyjne) dla zmiennych losowych – wprowadzenie
      • nierówność Markowa i Czebyszewa (z dowodami)
      • 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])\)
    • 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
11. wykład (20.12.2024.) – zamiana za czwartek 12.12.2024.
    • własności współczynnika korelacji – ciąg dalszy
      • zakres przyjmowanych wartości: \(-1 \leq \rho(X,Y) \leq 1\)
      • przypadek \(\rho(X,Y) = \pm 1\) – zależność prawie na pewno liniowa
    • funkcje tworzące prawdopodobieństwo zmiennych losowych o wartościach w zbiorze \(\mathbb{N}\)
      • 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
    • 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 momentó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
12. wykład (09.01.2025.)
    • nieskończone rodziny zdarzeń
      • rodziny zdarzeń \((A_n)_{n \geq 1}\), zdarzenia \(\bigcup\limits_{n \geq 1} A_n\) oraz \(\bigcap\limits_{n \geq 1} A_n\)
      • 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)
      • przykład – proste błądzenie losowe na \(\mathbb{Z}\)
    • lematy Borela-Cantellego (z dowodami), przykłady zastosowań
    • 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.)
      • przykład ciągu zmiennych losowych zbieżnego prawie na pewno
      • związki zbieżności prawie na pewno i wg prawdopodobieństwa
      • przykład ciągu zmiennych losowych zbieżnego według prawdopodobieństwa, ale nie prawie na pewno
      • mocne prawo wielkich liczb (SLLN)