Podręcznik 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, sprzężenie, martygnały i rozmieszczenia zrównoważone.
Książka skierowana jest do studentów informatyki na wszystkich uczelniach wyższych,
studentów zastosowań matematyki oraz osób zajmującym się algorytmiką, biologią
obliczeniową i eksploracją danych.
Spis treści:
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
Literatura
Skorowidz
416 stron, B5, oprawa miękka
