Powrót

Metody probabilistyczne w algorytmice (2018/2019)

Wykład odbywa się w czwartki w godz. 17:05 - 18:55 w sali 312B/D-1.
Przeznaczony jest dla studentów studiów drugiego stopnia Informatyki WPPT PWr.

Materiały

Literatura

Zaliczenie kursu

Ćwiczenia

Na ćwiczeniach będzie można zdobywać punkty za aktywność (maksymalnie 8). Będą także dwie zapowiedziane kartkówki (po 5 punktów). Za całokształt zyskać będzie można 18 punktów.

Laboratoria

Na laboratoriach trzeba będzie wykazać się umiejętnością rozwiązania zagadnień z list na laboratoria. Za każdą z 5 list otrzymać można po 5 punktów. Razem 25 punktów.

Egzamin

Egzamin będzie 11.02.2019 o godz. 9:15 w sali 312B/D-1. Egzamin poprawkowy będzie 15.02.2019 o godz. 9:15 w sali 312B/D-1 (oraz 18.02.2019 o godz.9:15 w sali 215/D-1). Maksymalna ocena z egzaminu to 50 punktów.

Ocena końcowa

Warunkiem koniecznym uzyskania pozytywnej oceny jest 6 punktów z ćwiczeń, 10 punktów z laboratorium i 20 punktów z egzaminu.

Zrealizowany materiał

  1. Elementy rachunku prawdopodobieństwa
    1. Przestrzeń probabilistyczna
    2. Funkcja mierzalna, zmienna losowa
    3. Wartość oczekiwana, wariancja
    4. Niezależne zmienne losowe
    5. Własności wartości oczekiwanej i wariancji
    6. Nierówność Markowa
    7. Nierówność Czebyszewa
  2. Eksperymentalne wyznaczanie parametrów rozkładu
    1. Nieobciążony estymator wartości oczekiwanej
    2. Nieobciążony estymator wariancji
  3. Quicksort
    1. Przypomnienie algorytmu i podstawowych jego własności
    2. Przypadek pesymistyczny
    3. Przypadek średni, czyli wartość oczekiwana liczby porównań wykonywanych przez algorytm; związek z liczbami harmonicznymi
  4. BST
    1. Nierówność Jensena
    2. Nierówność Jensena dla wartości oczekiwanych
    3. Związek liczby porównań w algorytmach Quicksort oraz tworzenia BST, wnioski o średniej głębokości węzła w BST
    4. Analiza wartości oczekiwanej wysokości BST
  5. Funkcje tworzące prawdopodobieństwa
    1. $F(z)=\sum{n=0}^\infty p_n z^n$, $G(z)=\sum_{n=0}^\infty q_n z^n$, gdzie $p_n=P(X=n)$, $q_n=P(X>n)$, $X$ jest zmienną losową o wartościach naturalnych
    2. Analiza zbieżności szeregów $F, G$
    3. Obliczanie wartości oczekiwanej i wariancji przy pomocy funkcji tworzących
    4. Suma niezależnych zmiennych losowych, splot szeregów
    5. Analiza liczby przypisań w algorytmie znajdowania maksymalnego elementu w tablicy
  6. Kule i urny
    1. Sortowanie kubełkowe
    2. Wartość oczekiwana najliczniejszego kubełka
    3. Rozkład dwumianowy i rozkład Poissona
    4. Suma niezależnych zmiennych o rozkładach Poissona
    5. Nierówności Chernoffa dla rozkładu Poissona
    6. Granica rozkładu dwumianowego
    7. Związek rozkładu liczby kul w urnach z rozkładem niezależnych zmiennych o rozkładzie Poissona
    8. Nierówności wiążące zmienne losowe związane z rozkładami dwumianowymi i Poissona
    9. Ograniczenia na rozmiar najliczniejszej urny
    10. Problem kolekcjonera kuponów
    11. Grafy losowe
    12. Wierzchołek izolowany w grafie
  7. Martyngały
    1. Warunkowa wartość oczekiwana
    2. $E(V|W)=E(E(V|W,U)|W)$
    3. Definicja i bazowy (generyczny) przykład martyngału $Z_i=E(Y|X_0,X_1,\ldots ,X_i)$
    4. Przykład martyngału na grafach losowych
    5. Własności warunkowej wartości oczekiwanej
    6. Nierówność Azumy
  8. Problem wyboru lidera (How to select a loser)
    1. Algorytm z rzucaniem monetą
    2. Funkcja tworząca
    3. Liczby Bernoulliego
    4. Wartość oczekiwana liczby rund potrzebnych do wyłonienia lidera (losera)
  9. Siła d-wyborów (the power of d-choices)
    1. Algorytm z pomocniczym wyborem d urn
    2. Przykłady zastosowań
    3. Górne oszacowanie na wartość oczekiwaną najliczniejszej urny

Powrót