7928718291

PRZEDMIOTOWE EFEKTY KSZTAŁCENIA

Z zakresu wiedzy studenta:

W1 Zna podstawowe narzędzia badania własności probablistycznych algorytmów takie jak: nierówność Chemoffa, metoda pierwszego i drugiego momentu, aproksymacja Poissona, funkcje tworzące prawdopodobieństwo, łańcuchy Markova, nierówności ogonowe.

W2 Zna zaawansowane narzędzia badania własności probablistycznych algorytmów takie jak: Lokalny Lemat Lovasza, proces Galtona-Watsona, równanie odnowienia, coupling łańcuchów Markova.

Z zakresu umiejętności studenta:

Ul Potrafi wybrać odpowiednie narzędzie probabilistyczne do analizy konkretnego problemu algorytmicznego.

U2 Potrafi sprawdzić poprawność uzyskanego analitycznego wyniku przeprowadzając symulacje i analizę.

Z zakresu kompetencji społecznych studenta:

KI Rozumie potrzebę stosowania narzędzi probabilistycznych do badania problemów algorytmicznych

K2 Potrafi zbudować wizualizację badanych zagadnień

TREŚCI PROGRAMOWE

Forma zajęć - wykłady

Wy 1

Własności zmiennych losowych i nierówności Chernoffa

2h

Wy2

Metoda probabilistyczna

4h

Wy3

Model kul i urn

3h

Wy4

Martyngały

3h

Wy 5

Inne nierówności ogonowe

2h

Wy6

Zmienne losowe przyjmujące wartości całkowite nieujemne i funkcje tworzące

2h

Wy7

Rozkłady złożone i procesy gałązkowe

3h

Wy8

Zdarzenia rekurencyjne

3h

Wy9

Łańcuchy Markova i metody ich badania

3h

Wy 10

Błądzenie przypadkowe

3h

Wyli

Coupling łańcuchów Markova

2h

Forma zajęć - ćwiczenia

Ćwl

Własności zmiennych losowych i nierówności Chernoffa

2h

Ćw2

Metoda probabilistyczna

4h

Ćw3

Model kul i urn

4h

Ćw4

Martyngały

3h

Ćw5

Nierówności ogonowe

2h

Ćw6

Funkcje tworzące prawdopodobieństwo

2h

Ćw7

Rozkłady złożone i procesy gałązkowe

3h

Ćw8

Zdarzenia rekurencyjne

4h

Ćw9

Błądzenie przypadkowe

4h

CwlO

Coupling łańcuchów Markova

2h