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

Po otrzymaniu zamówienia poinformujemy,
czy wybrany tytuł polskojęzyczny lub anglojęzyczny jest aktualnie na półce księgarni.