Kurs jest w dużej mierze oparty na materiale z książek:

• M. Mitzenmacher, E. Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd edition, Cambridge University Press 2017
• D. Levin, Y. Peres, Markov chains and mixing times, 2nd edition, American Mathematical Society 2017

• aktywność [pdf] (aktualizacja: 21.X)

• 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, rozmowa z Dziekanem, 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 punkty bonusowe (każde zadanie będzie miało przypisaną max. ilość punktów do zdobycia; domyślnie to będzie 1 punkt).

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.

• 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]

• 8.X., Aksjomaty, niezależność, wartość oczekiwana [pdf]
• 15.X., Liniowość wartości oczekiwanej, wariancja i metoda probabilistyczna [pdf]
• 22.X., Miara i całka [pdf]

• 4.X, weryfikacja równości dwu wielomianów, podstawowe definicje (przestrzeń probabilistyczna), nierówność union bound, niezależność zdarzeń, prawdopodobieńśtwo warunkowe weryfikacja mnożenia macierzy, prawo całkowitego przawdopodobieństwa,
• 4.X (nagranie), dyskretne zmienne losowe, niezależność zmiennych losowych, wartość oczekiwana, liniowość wartości oczekiwanej
• 11.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"
• 11.X (do obejrzenia przed 25.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,

• 24.I.2024, kolokwium 2/2 [pdf]
• 6.XII.2023, kolokwium 1/2 [pdf]