Tytuł: | Metody probabilistyczne i obliczenia Algorytmy randomizowane i analiza probabilistyczna | | Autor: | Michael Mitzenmacher, Eli Upfal | | ISBN: | 978-83-204-3438-5 | | Ilość stron: | 416 | | Data wydania: | 04/2009 | | Wydawnictwo: | WNT | |
| Cena: | 61.95zł | |
Książka dotyczy zastosowania probabilistyki w informatyce. Stanowi doskonałe wprowadzenie do metod i paradygmatów probabilistycznych.
Pierwsza część książki to materiał bazowy, na który składają się próbkowanie losowe, wartość oczekiwana, nierówność Markowa, nierówność Czebyszewa, oszacowania Chernoffa, modele urnowe, metoda probabilistyczna i łańcuchy Markowa.
W drugiej części Autorzy zagłębiają się w bardziej zaawansowane zagadnienia, takie jak rozkłady ciągłe, zastosowania ograniczonej niezależności, entropia, metody Monte Carlo, przędzenie, martygnały i rozmieszczenia zrównoważone.
Książka skierowana jest do studentów informatyki na wszystkich uczelniach wyższych, studentom zastosowań matematyki oraz osobom zajmującym się algorytmiką, biologią obliczeniową i eksploracją danych.
Rozdziały:
1. Zdarzenia i prawdopodobieństwo 1.1. Zastosowanie: weryfikacja równości wielomianów 1.2. Aksjomaty prawdopodobieństwa 1.3. Zastosowanie: weryfikacja mnożenia macierzy 1.4. Zastosowanie: zrandomizowany algorytm przekroju minimalnego (Min-Cut) 1.5. Zadania
2. Dyskretne zmienne losowe i wartość oczekiwana 2.1. Zmienne losowe i wartość oczekiwana 2.2. Zmienne losowe o rozkładzie Bernoulliego i dwumianowym 2.3. Warunkowa wartość oczekiwana 2.4. Rozkład geometryczny 2.5. Zastosowanie: oczekiwany czas algorytmu sortowania szybkiego (quicksort) 2.6. Zadania
3. Momenty zmiennych losowych i odchylenia 3.1. Nierówność Markowa 3.2. Wariancja i momenty zmiennej losowej 3.3. Nierówność Czebyszewa 3.4. Zastosowanie: zrandomizowany algorytm obliczania mediany 3.5. Zadania
4. Nierówności Chernoffa 4.1. Funkcje tworzące momenty 4.2. Wyprowadzenie i zastosowanie nierówności Chernoffa 4.3. Lepsze oszacowania szczególnych przypadków 4.4. Zastosowanie: równoważenie zbiorów 4.5. Zastosowanie: przesyłanie pakietów w sieciach rzadkich 4.6. Zadania
5. Schematy urnowe i grafy losowe 5.1. Przykład: problem urodzin 5.2. Schematy urnowe 5.3. Rozkład Poissona 5.4. Aproksymacja poissonowska 5.5. Zastosowanie: haszowanie 5.6. Grafy losowe 5.7. Zadania 5.8. Zadanie badawcze
6. Metoda probabilistyczna 6.1. Prosty argument przeliczeniowy 6.2. Metoda wartości oczekiwanej 6.3. Derandomizacja metodą warunkowych wartości oczekiwanych 6.4. Próbkuj i modyfikuj 6.5. Metoda drugiego momentu 6.6. Nierówność dla warunkowych wartości oczekiwanych 6.7. Lokalny lemat Lovasza 6.8. Konstrukcje jawne z użyciem lokalnego lematu 6.9. Lokalny lemat Lovasza: przypadek ogólny 6.10. Zadania
7. Łańcuchy Markowa i spacery losowe 7.1. Łańcuchy Markowa: definicje i reprezentacje 7.2. Klasyfikacja stanów 7.3. Rozkład stacjonarny 7.4. Spacery losowe na grafach nieskierowanych 7.5. Paradoks Parrondo 7.6. Zadania
8. Rozkłady ciągłe i proces Poissona 8.1. Ciągłe zmienne losowe 8.2. Rozkład jednostajny 8.3. Rozkład wykładniczy 8.4. Proces Poissona 8.5. Procesy Markowa z czasem ciągłym 8.6. Przykład: kolejki Markowa 8.7. Zadania
9. Entropia, losowość i informacja 9.1. Entropia 9.2. Entropia i współczynniki dwumianowe 9.3. Entropia: miara losowości 9.4. Kompresja 9.5. Kodowanie: twierdzenie Shannona 9.6. Zadania
10. Metoda Monte Carlo 10.1. Metoda Monte Carlo 10.2. Zastosowanie: problem przeliczania wartościowań DNF 10.3. Od przybliżonego próbkowania do przybliżonego przeliczania . . 10.4. Metoda Monte Carlo oparta na łańcuchach Markowa 10.5. Zadania 10.6. Zadanie badawcze o minimalnych drzewach rozpiętych
11. Sprzężenie łańcuchów Markowa 11.1. Odległość w sensie całkowitej wariacji i czas mieszania 11.2. Sprzężenie 11.3. Zastosowanie: odległość w sensie całkowitej wariacji jest nierosnąc 11.4. Zbieżność geometryczna 11.5. Zastosowanie: próbkowanie przybliżone właściwych kolorowań 11.6. Sprzężenie ścieżkowe 11.7. Zadania
12. Martyngały 12.1. Martyngały 12.2. Momenty stopu 12.3. Tożsamość Walda 12.4. Nierówności ogonowe dla martyngałów 12.5. Zastosowania nierówności Azumy-Hoeffdinga 12.6. Zadania
13. Niezależność parami i uniwersalne funkcje haszujące 13.1 Niezależność parami 13.2. Nierówność Czebyszewa dla zmiennych niezależnych parami 13.3. Rodziny uniwersalne funkcji haszujących 13.4. Zastosowanie: znajdowanie przeciążeń w strumieniach danych 13.5. Zadania
14. Rozmieszczenia zrównoważone 14.1. Siła podwójnego wyboru 14.2. Dwa wybory: oszacowanie dolne 14.3. Zastosowanie siły podwójnego wyboru 14.4. Zadania
|