| Description |
1 online resource (409 pages) |
| Series |
Discrete Mathematics and Its Applications Ser |
|
Discrete Mathematics and Its Applications Ser
|
| Contents |
Cover; Half Title; Title Page; Copyright Page; Dedication; Table of Contents; Preface; List of Figures; List of Tables; 1: Background on computational complexity; 1.1 General overview of computational problems; 1.2 Deterministic decision problems: P, NP, NP-complete; 1.3 Deterministic counting: FP, #P, #P-complete; 1.4 Computing the volume of a convex body, deterministic versus stochastic case; 1.5 Random decision algorithms: RP, BPP. Papadimitriou's theorem; 1.6 Stochastic counting and sampling: FPRAS and FPAUS; 1.7 Conclusions and the overview of the book; 1.8 Exercises; 1.9 Solutions |
|
I: Computational Complexity of Counting2: Algebraic dynamic programming and monotone computations; 2.1 Introducing algebraic dynamic programming; 2.1.1 Recursions, dynamic programming; 2.1.2 Formal definition of algebraic dynamic programming; 2.1.3 The power of algebraic dynamic programming: Variants of the money change problem; 2.1.3.1 Counting the coin sequences summing up to a given amount; 2.1.3.2 Calculating the partition polynomial; 2.1.3.3 Finding the recursion for optimization with algebraic dynamic programming; 2.1.3.4 Counting the total sum of weights |
|
2.1.3.5 Counting the coin sequences when the order does not count2.2 Counting, optimizing, deciding; 2.3 The zoo of counting and optimization problems solvable with algebraic dynamic programming; 2.3.1 Regular grammars, Hidden Markov Models; 2.3.2 Sequence alignment problems, pair Hidden Markov Models; 2.3.3 Context-free grammars; 2.3.4 Walks on directed graphs; 2.3.5 Trees; 2.4 Limitations of the algebraic dynamic programming approach; 2.5 Exercises; 2.6 Solutions; 3: Linear algebraic algorithms. The power of subtracting |
|
3.1 Division-free algorithms for calculating the determinant and Pfaffian3.2 Kirchhoff's matrix-tree theorem; 3.3 The BEST (de Bruijn-Ehrenfest-Smith-Tutte) algorithm; 3.4 The FKT (Fisher-Kasteleyn-Temperley) algorithm; 3.5 The power of subtraction; 3.6 Further reading; 3.7 Exercises; 3.8 Solutions; 4: #P-complete counting problems; 4.1 Approximation-preserving #P-complete proofs; 4.1.1 #3SAT; 4.1.2 Calculating the permanent of an arbitrary matrix; 4.1.3 Counting the most parsimonious substitution histories on an evolutionary tree; 4.1.4 #IS and #Mon-2SAT |
|
4.2 #P-complete proofs not preserving the relative error4.2.1 #DNF, #3DNF; 4.2.2 Counting the sequences of a given length that a regular grammar can generate; 4.2.3 Computing the permanent of a non-negative matrix and counting perfect matchings in bipartite graphs; 4.2.4 Counting the (not necessarily perfect) matchings of a bipartite graph; 4.2.5 Counting the linear extensions of a poset; 4.2.6 Counting the most parsimonious substitution histories on a star tree; 4.2.7 Counting the (not necessarily perfect) matchings in a planar graph; 4.2.8 Counting the subtrees of a graph |
| Notes |
4.2.9 Number of Eulerian orientations in a Eulerian graph |
|
Print version record |
| Subject |
Computational complexity.
|
|
Sampling (Statistics)
|
|
Computational complexity
|
|
Sampling (Statistics)
|
| Form |
Electronic book
|
| ISBN |
9781351971614 |
|
1351971611 |
|
1315266954 |
|
9781315266954 |
|
1351971603 |
|
9781351971607 |
|
