Algorytmy i losowość 1000-2M04AL
1. Wprowadzenie - dyskretny rachunek prawdopodobieństwa.
2. Nierówności probabilistyczne.
3. Proces kolekcjonowania kuponów.
4. Martyngały - wrzucanie kul do urn.
5. Metoda probabilistyczna i Lokalny Lemat Lovasza.
6. Extractory i expandery - wzmacnianie losowości.
7. Generowanie liczb pseudolosowych.
8. Lancuchy Markowa - bładzenie w grafie.
9. Generowanie rozkładów pseudo-losowych.
10. Metody przybliżonego zliczania.
11. Podstawy hierarchii złożoności algorytmów randomizowanych.
12. Aproksymacyjne algorytmy randomizowane.
13. Perełki wśród algorytmów randomizowanych.
Rodzaj przedmiotu
Literatura
1. R. Motwani, P. Raghavan: Randomized Algorithms.
2. N. Alon, J. Spencer: The Probabilistic Method.
3. V. Vazirani: Approximation Algorithms.
4. Prace konferencyjne i czasopismowe z ostatnich kilku lat.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: