Autor: Michael Mitzenmacher, Eli Upfal

ISBN: 978-83-204-3438-5

Ilość stron: 416

Data wydania: 04/2009

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