METODY PROBABILISTYCZNE I OBLICZENIA MITZENMACHER M. UPFAL ELI Księgarnia

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

Księgarnia nie działa. Nie odpowiadamy na pytania i nie realizujemy zamówien. Do odwolania !.