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
adobe algorytmy apache asp autocad asembler bsd c++ c# delphi dtp excel flash html java javascript linux matlab mysql office php samba voip uml unix visual studio windows word
Księgarnia Informatyczna zaprasza.