Metody probabilistyczne informatyki
dla informatyki analitycznej
semestr zimowy 2023/24
Instytut Informatyki Analitycznej
Wydział Matematyki i Informatyki
Uniwersytet Jagielloński
Prowadzący
Jędrzej Hodor,
Piotr Micek
Zajęcia
wykłady w piątki 8:30 - 10:00 (sala 1094)
ćwiczenia w środy 8:30 - 10:00 (grupa 1, sala 1094; grupa 2, sala 0086)
dyżury w środy 10:00 - 12:00
Kurs jest w dużej mierze oparty na materiale z książki Mitzenmachera i Upfala (referencja na końcu strony; znajdź drugą edycję!).
Aktualna punktacja
- aktywność [pdf] (aktualizacja: 19.I)
- kolokwium 1/2 [pdf (aktualizacja: 19.I]
- kolokwium 2/2 [pdf (aktualizacja: 31.I]
- podsumowanie [pdf] (aktualizacja: 31.I)
Warunki zaliczenia
W trakcie kursu można zdobyć 100 punktów, przy czym:
- na każdym z dwu kolokwiów można zdobyć 40 punktów
- za rozwiązywanie zadań domowych można zdobyć 20 punktów
- za pisemne rozwiązanie wyróżnionych zadań domowych (max. jedno na zestaw) będzie można dostać do 10 punktów bonusowych
Zestawy zadań będą publikowane co siedem dni (z pewnymi dłuższymi przerwami na święta lub kolokwia).
Liczba zestawów będzie równa $Z$, gdzie $Z\in\{10,11,12\}$.
Studenci przy pomocy elektronicznego formularza będą deklarować rozwiązania zadań z bieżącego zestawu.
Deklaracja rozwiązania równoważna jest gotowości prezentacji rozwiązania przy tablicy.
Prezentacja zadania co do zasady ma być bez pomocy (notatek).
Oczywiście w sytuacji gdy zadanie jest bardzo rachunkowe będziemy robić wyjątki, jednak student(ka) ma rozumieć rozwiązanie bez notatek.
Za deklarację bez pokrycia będą negatywne konsekwencje: zerowanie punktów za zestaw, ujemne punkty, itp.
Za rozwiązanie zadań pojedynczego zestawu będzie można uzyskać co najwyżej $X=\frac{20}{Z}$ punktów.
Jeśli zestaw zawiera $N$ zadań, a student zadeklarował $M$ zadań, to student uzyskuje $\min(\frac{M}{0.9\cdot N},1)\cdot X$ punktów za zestaw.
Deklaracje będą zbierane jedynie od studentów obecnych na zajęciach.
Poza tym obecność nie będzie mieć wpływu na ocenę.
Rozwiązania wyróżnionych zadań domowych nie będą podlegać systemowi deklaracji i będą mogły być spisywane
w grupach co najwyżej dwuosobowych (dwie osoby mogą być co najwyżej raz razem w grupie; studenci z różnych grup ćwiczeniowych mogą stworzyć grupę).
Rozwiązania będą akceptowane jedynie w formacie pdf, który został wygenerowany przez kompilator Latexa.
Rozwiązanie pisemne zadania będzie przyjmowane do 23:59:59 dnia poprzedzającego zajęcia na których omawiany jest zestaw z zadaniem.
Rozwiązanie należy wysyłać na adres matematyka.dyskretna.tcs@gmail.com.
Wysłanie rozwiązania równoważne jest gotowości prezentacji rozwiązania przy tablicy.
Prowadzący mogą też prosić autorów rozwiązania o indywidualne rozmowy (po zajęciach) weryfikujące poprawność i samodzielność rozwiązania.
Za każde poprawnie rozwiązane zadanie wyróżnione student otrzymuje $1$ punkt bonusowy.
Kodeks honorowy: Zabronione jest wyszukiwanie w sieci treści zadania wyróżnionego czy jego rozwiązania oraz konsultowanie rozwiązań poza grupą podpisaną pod rozwiązaniem.
Dozwolone jest korzystanie z książek i materiałów z sieci; jeśli student rozwiązał zadanie dzięki znalezieniu go,
lub bardzo podobnego, w materiałach to należy podać referencje do tych materiałów.
Każda wysłana pisemna praca ma zawierać oświadczenie autorów o zachowaniu powyższych wytycznych.
Poza grupami sformowanymi do konkretnych zestawów dyskusje na temat zadań i ich rozwiązań są dozwolone jedynie na forum.tcs oraz poprzez email z prowadzącym zajęcia.
Oceny z ćwiczeń wystawiane będą względem następujących progów:
- 5,0 -- (90,100]
- 4,5 -- (80,90]
- 4,0 -- (70,80]
- 3,5 -- (60,70]
- 3,0 -- (50,60]
- 2,0 -- (25,50]
- NZAL -- [0,25]
Wszyscy studenci, którzy otrzymali zaliczenie z ćwiczeń (tj. ocenę przynajmniej 3,0) przystąpią do egzaminu końcowego w formie ustnej.
Jeśli student otrzymał co najmniej 3,0 z ćwiczeń i egzaminu to jego ocena końcowa jest średnią arytmetyczną tych dwóch ocen zaokrągloną do góry do najbliższej oceny.
W pozostałych przypadkach student otrzymuje ocenę 2,0 lub NZAL.
Jeśli student otrzyma 2.0 może poprawić ocenę z ćwiczeń przystępując do kolokwium poprawkowego.
Nie będzie możliwości poprawy oceny NZAL z ćwiczeń.
Osoby uprawnione do przystąpienia do egzaminu które nie zdały (nie przystąpiły) w pierwszym terminie będą mogły podejść do egzaminu drugi raz w sesji poprawkowej.
Pytania egzaminacyjne
[pdf]
Materiały
zestawy ćwiczeń
- 11.X., Aksjomaty, niezależność, wartość oczekiwana [pdf]
- 18.X., Miara i całka [pdf]
- 25.X., Liniowość wartości oczekiwanej, wariancja [pdf]
- 8.XI., Wariancja, nierówność Czebyszewa i nierówność Markowa [pdf]
- 15.XI., Kule i urny [pdf]
- 29.XI., Łańcuchy Markowa [pdf]
- 20.XII., Rozkład jednostajny, igła Buffona [pdf](slajdy o igle Buffona [pdf, notatka o dowodzie z Księgi pdf])
- 10.I., Rozkład wykładniczy i proces Poissona [pdf]
- 12.I., Rozkład normalny, rozkład Cauchy'ego i CTG [pdf]
- 19.I., Sprzęganie łańcuchóœ Markowa [pdf]
Wykłady
- 4.X, weryfikacja równości dwu wielomianów,
podstawowe definicje (przestrzeń probabilistyczna), nierówność union bound,
niezależność zdarzeń, prawdopodobieńśtwo warunkowe
- 4.X (nagranie),
dyskretne zmienne losowe,
niezależność zmiennych losowych,
wartość oczekiwana,
liniowość wartości oczekiwanej
- 6.X,
nierówność Jensena,
rozkład dwumianowy,
warunkowa wartość oczekiwana (zdarzenie w warunku),
warunkowa wartość oczekiwana (zmienna w warunku),
rozkład geometryczny,
własność "bez pamięci"
- 13.X, teoria miary
- przed 20.X (nagranie),
problem kolekcjonera kuponów (wartość oczekiwana),
oczekiwana liczba porównań wykonanych przez Quicksort,
nierówność Markowa,
k-te momenty, wariancja i odchylenie standardowe, kowariancja,
własności wariancji,
wariancja zmiennej o rozkładzie dwumianowym,
- 20.X,
nierówność Czebyszewa, przykłady zastosowań, funkcja tworząca momentów zmiennej losowej, ogólny schemat otrzymywania nierówności Chernoffa
- 25.X,
nierówności Chernoffa dla niezależnych prób Poissona, aplikacja dla problemu estymacji parametru (wyciągamy próbkę wielkości n z całej populacji i estymuujemy prawdopodobieństwo występowania cechy przyjmując, że próbka powstaje z rozkładu dwumianowego), nierówności Chernoffa dla sumy niezależnych zmiennych przyjmujących jednostajnie wartości {-1,1} / {0,1}, aplikacja do problemu "set balancing"
- 5.XI (nagranie),
paradoks dnia urodzin, model kul i urn, ograniczenie górne na asymptotykę maksymalnego zapełnienia,
rozkład Poissona, suma niezależnych zmiennych o rozkładzie Poissona ma rozkład Poissona, tworząca momentów zmiennej o rozkładzie Poissona,
ograniczenia Czernowa dla zmiennych o rozkładzie Poissona,
rozkład Poissona jako granica rozkładów dwumianowych (twierdzenie 5.5 z książki, bez dowodu),
aproksymacja Poissona,
ograniczenie dolne na asymptotykę maksymalnego zapełnienia,
kolekcjoner kuponów: aplikacja aproksymacji Poissona
- 17.XI,
łańcuchy Markowa: podstawowe definicje, randomizowane algorytmy dla problemu 2-SAT i 3-SAT
- 19.XI kontynuacja wykładu o łańcuchach Markowa: (nagranie),
klasyfikacja stanów, rozkład stacjonarny
- 19.XI i dalej kontynuacja o łańcuchach Markowa: (nagranie (obowiązuje pierwsze 67'),
kolejka Markowa, losowe spacery po grafie
- 24.XI, ciągłe zmienne losowe:
ciągłe zmienne losowe, dystrybuant, gęstość, wartość oczekiwana, wspólna gęstość i dystrybuanta,
rozkład jednostajny, lemat o warunkowości, wartość oczekiwana k-tej statystyki
- 1.XII, rozkład wykładniczy,
własność bez pamięci, rozkłąd minimum zmiennych o rozkładzie wykładniczym,
kile i urny z feedbackiem
- 8.XII,
proces Poissona
- 15.XII,
rozkład normalny, CTG
- 15.I, (slajdy, nagranie),
sprzęganie łańcuchów Markowa
- 15.I, (slajdy, nagranie),
metody Monte Carlo
Archiwum kolokwiów
- 24.I.2024, kolokwium 2/2 [pdf]
- 6.XII.2023, kolokwium 1/2 [pdf]
- 25.I.2023, kolokwium 2/2 [pdf]
- 23.XI.2022, kolokwium 1/2 [pdf]
- 27.I.2022, kolokwium 3/3 [pdf]
- 13.I.2022, kolokwium 2/3 [pdf]
- 30.XI.2021, kolokwium 1/3 [pdf]
- 30.I.2020, kolokwium 2/2 [pdf]
- 04.XII.2019, kolokwium 1/2 [pdf]
Literatura
- M. Mitzenmacher, E. Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd edition, Cambridge University Press 2017
- Geoffrey G. Grimmet, David R. Stirzaker, Probability and Random Processes, Oxford University Press 2001