tmiki-2015

Metody probabilistyczne algory (tmiki)

Zasady zaliczania

Suma punktów (z kolokwium/egzaminu i ćwiczeń):

6 => bdb

5 => db+

4 => db

3 => dst+

2 => dst

Laboratorium: dst, db, bdb przy oddanych odpowiednio 50%, 75%, 100% kodach (można oddawać w parach / w wyjątkowych sytuacjach trójkach).

Ważenie: ćwiczenia i kolokwium: 70%, lab: 30%.

Oficjalne terminy egzaminu (I i II termin):

I Piątek 29 stycznia, 9:00 - 11:00, sala D1.215

II Piątek 5 luty, 9:00 - 11:00, sala D1.215

Wykłady

• 1. Nierówności Markova i Chebysheva

  2. Ograniczenie Chernoffa

  3. Aproksymacja Poissona

  4. Metoda probabilistyczna

Planowane wykłady

• 1. Metoda probabilistyczna, ciąg dalszy

  2. Łańcuchy Markowa (ale to na koniec - sporo wykładów)

  3. Ciągły rozkład Poissona, kolejki

  4. Metoda Monte Carlo (nie mylić z algorytmami Monte Carlo)

  5. Martyngały

  6. może Power of Two Choices

Ćwiczenia

1. Ćwiczenia 1

2. Ćwiczenia 2

3. Ćwiczenia 3

4. Ćwiczenia 4

5. Ćwiczenia 5

6. Ćwiczenia 6

Laboratorium

• 1. Laboratorium 1, termin przysłania 31.10/1.11, a omówienie najpóźniej na kolejnym laboratorium

  2. Laboratorium 2, termin przysyłania: 21.11/22.11, a omówienie najpóźniej na kolejnym laboratorium

1. Laboratorium 3, (luźny) termin przysyłania: 2015 rok

2. Laboratorium 4, termin przysyłania i oddania: koniec semestru

Literatura

• 1. Probability and Computing, Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal

Ciekawe prace

• 1. Random walks and electric networks, Peter G. Doyle, J. Laurie Snell, 5 July 2006