Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Jerrum M. — Counting, sampling and integrating: algorithms and complexity
Jerrum M. — Counting, sampling and integrating: algorithms and complexity



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Counting, sampling and integrating: algorithms and complexity

Автор: Jerrum M.

Аннотация:

The subject of these notes is counting (of combinatorial structures) and related topics, viewed from a computational perspective. A major theme of the book is the idea of accumulating information about a set of combinatorial structures by performing a random walk (i.e., simulating a Markov chain) on those structures. These notes will be of value not only to teachers of postgraduate courses on these topics, but also to established researchers. For the first time this body of knowledge has been brought together in a single volume.


Язык: en

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2003

Количество страниц: 112

Добавлена в каталог: 07.12.2009

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
#P      13
#P-complete      14
#SAT      14
0,1-Perm      15
Almost uniform sampler      27
Almost uniform sampler, fully polynomial      27
Arborescence      4
Ball walk      66
bpp      93
Brooks's theorem      98
Brunn — Minkowsky theorem      84
Canonical paths technique      51
Complexity class, #P      13
Complexity class, BPP      93
Complexity class, FP      13
Complexity class, NP      12
Complexity class, P      11
Complexity class, RP      93
Conductance of the ball walk      89
Congestion      51
Continuised Markov chain      63
Coupling Lemma      37
Curvature condition      69
Decision problem      11
Detailed balance      32
Dimer model      9
Dirichlet form      52
Ergodic [Markov chain]      31
Eulerian circuit      4
FP      13
Fully polynomial almost uniform sampler      27
Fully polynomial randomised approximation scheme      26
Gapl      10
Hamilton cycle      11
Independent set      94
Ising model      9
Linear extensions of a partial order      42
Local conductance      70
Markov chain      30
Markov chain with continuous state space      67
Markov chain, continuised      63
Markov chain, ergodic      31
Markov chain, time reversible      32
Markovian coupling      36
Matching      49
Mixing time      35
Monomer-dimer system      49
Multicommodity flow problem      51
NP      12
NP-complete      12
Oracle model      65
P      11
Path coupling      41
Perfect matchings      5
Permanent [of a matrix]      15
Pfaffian orientation      5
Poincare inequality      52
Poincare inequality for the ball walk      73
Polynomial-time Turing reducibility      14
Probabilistic Turing machine      25
Probabilistically checkable proof      98
Proper q-colouring      33
Randomised approximation scheme      26
Randomised approximation scheme, fully polynomial      26
RP      93
Sampling problem      26
Spanning tree      1
Stationary distribution      31
Time reversible [Markov chain]      32
Total variation distance      26
Transition matrix      31
Turing machine, model      12
Turing machine, probabilistic      25
Volume of a convex body      65
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте