Atnaujinkite slapukų nuostatas

El. knyga: Probabilistic Methods for Algorithmic Discrete Mathematics

Edited by , Edited by , Edited by , Edited by
  • Formatas: PDF+DRM
  • Serija: Algorithms and Combinatorics 16
  • Išleidimo metai: 14-Mar-2013
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • Kalba: eng
  • ISBN-13: 9783662127889
Kitos knygos pagal šią temą:
Probabilistic Methods for Algorithmic Discrete MathematicsDidesnis paveikslėlis
  • Formatas: PDF+DRM
  • Serija: Algorithms and Combinatorics 16
  • Išleidimo metai: 14-Mar-2013
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • Kalba: eng
  • ISBN-13: 9783662127889
Kitos knygos pagal šią temą:

DRM apribojimai

  • Kopijuoti:

    neleidžiama

  • Spausdinti:

    neleidžiama

  • El. knygos naudojimas:

    Skaitmeninių teisių valdymas (DRM)
    Leidykla pateikė šią knygą šifruota forma, o tai reiškia, kad norint ją atrakinti ir perskaityti reikia įdiegti nemokamą programinę įrangą. Norint skaityti šią el. knygą, turite susikurti Adobe ID . Daugiau informacijos  čia. El. knygą galima atsisiųsti į 6 įrenginius (vienas vartotojas su tuo pačiu Adobe ID).

    Reikalinga programinė įranga
    Norint skaityti šią el. knygą mobiliajame įrenginyje (telefone ar planšetiniame kompiuteryje), turite įdiegti šią nemokamą programėlę: PocketBook Reader (iOS / Android)

    Norint skaityti šią el. knygą asmeniniame arba „Mac“ kompiuteryje, Jums reikalinga  Adobe Digital Editions “ (tai nemokama programa, specialiai sukurta el. knygoms. Tai nėra tas pats, kas „Adobe Reader“, kurią tikriausiai jau turite savo kompiuteryje.)

    Negalite skaityti šios el. knygos naudodami „Amazon Kindle“.

Leave nothing to chance. This cliche embodies the common belief that ran­ domness has no place in carefully planned methodologies, every step should be spelled out, each i dotted and each t crossed. In discrete mathematics at least, nothing could be further from the truth. Introducing random choices into algorithms can improve their performance. The application of proba­ bilistic tools has led to the resolution of combinatorial problems which had resisted attack for decades. The chapters in this volume explore and celebrate this fact. Our intention was to bring together, for the first time, accessible discus­ sions of the disparate ways in which probabilistic ideas are enriching discrete mathematics. These discussions are aimed at mathematicians with a good combinatorial background but require only a passing acquaintance with the basic definitions in probability (e.g. expected value, conditional probability). A reader who already has a firm grasp on the area will be interested in the original research, novel syntheses, and discussions of ongoing developments scattered throughout the book. Some of the most convincing demonstrations of the power of these tech­ niques are randomized algorithms for estimating quantities which are hard to compute exactly. One example is the randomized algorithm of Dyer, Frieze and Kannan for estimating the volume of a polyhedron. To illustrate these techniques, we consider a simple related problem. Suppose S is some region of the unit square defined by a system of polynomial inequalities: Pi (x. y) ~ o.
The Probabilistic Method 1(35) Michael Molloy The First Moment Method 2(4) Satisfiability Problems 3(1) Graphs with High Girth and High Chromatic Number 4(2) The Second Moment Method 6(3) The Lovasz Local Lemma 9(6) The Basic Form 9(2) Disjoint Cycles 11(1) More General Forms 12(3) Concentration 15(5) The Semirandom Method 20(5) Triangle-free Graphs 22(1) Sparse Graphs 23(1) Dense Graphs 24(1) Ramsey Theory 25(4) An Upper Bound 26(1) A Weak Lower Bound 27(1) A Tight Lower Bound 28(1) Algorithms 29(7) The First Moment Method 29(1) The Lovasz Local Lemma 30(6) Probabilistic Analysis of Algorithms 36(57) Alan M. Frieze Bruce Reed Introduction 36(3) Some Basic Notions 38(1) Exact Algorithms for Hard Problems 39(17) Algorithms Which Almost Always Succeed 39(10) Polynomial Expected Time 49(7) Further Results 56(1) Faster Algorithms for Easy Problems 56(7) Perfect Matchings 57(1) Linear Programming 58(2) Shortest Paths 60(3) Asymptotic Optimality and Approximation 63(7) Bin Packing 63(1) Euclidean Travelling Salesman Problem 64(3) Asymmetric Travelling Salesman Problem 67(1) Disjoint Paths 68(2) Greedy Algorithms 70(6) Cliques, Stable Sets, and Colourings 70(1) Greedy Matchings 71(2) Knapsack Problems 73(3) Negative Results 76(7) Knapsack 78(4) k-Median 82(1) Quadratic Assignment 82(1) Further Results 83(1) Non-Algorithmic Issues 83(10) Thresholds 83(2) Concentration 85(8) An Overview of Randomized Algorithms 93(23) Rajeev Motwani Prabhakar Raghavan Introduction and Terminology 93(1) Organization of This Survey 94(1) Randomized Sorting 94(2) Foiling an Adversary 96(3) The Minimax Principle and Lower Bounds 99(3) Lower Bound for Game Tree Evaluation 100(2) The Probabilistic Method 102(3) Algebraic Methods and Randomized Fingerprints 105(7) Freivalds Technique and Matrix Product Verification 106(2) Extension to Identities of Polynomials 108(3) Detecting Perfect Matchings in Graphs 111(1) Further Reading 112(4) Mathematical Foundations of the Markov Chain Monte Carlo Method 116(50) Mark Jerrum Introduction 116(2) Approximate Counting, Uniform Sampling and Their Relationship 118(2) Sampling by Markov Chain Simulation 120(3) A Toy Example: Colourings of the Empty Graph 123(8) Canonical Paths 124(3) Geometry 127(2) Coupling 129(2) Some More Challenging Applications 131(12) Monomer-Dimer Coverings Via Canonical Paths 132(5) Linear Extensions of a Partial Order Via Geometry 137(3) Colourings of a Low-Degree Graph Via Coupling 140(3) A New Technique: Path Coupling 143(5) Exact Sampling by Coupling From the Past (CFTP) 148(9) A Monotone Example: the Random Cluster Model 151(2) A Non-Monotone Example: Random Forests 153(3) Further Applications 156(1) Key Open Problems 157(2) Matroid Bases 157(1) Permanent of a 0,1 Matrix 158(1) Contingency Tables 158(1) Details 159(7) Percolation and the Random Cluster Model: Combinatorial and Algorithmic Problems 166(29) Dominic Welsh Introduction 166(1) Classical Percolation Theory 166(3) The Ising and Q-State Potts Models 169(3) The Random Cluster Model 172(2) The Tutte Polynomial 174(7) The Random Cluster Model Again 181(5) Approximation Schemes 186(4) A Geometric Approach 190(5) Concentration 195(120) Colin McDiarmid Introduction 195(3) Inequalities for Sums of Bounded Independent Random Variables 198(7) Martingale Methods 205(23) The Independent Bounded Differences Inequality 206(6) Extensions 212(7) Martingales 219(3) Martingale Results 222(3) Remaining Proofs for Martingale Results 225(2) Centering Sequences 227(1) Talagrands Inequality 228(21) The Inequality 228(1) Some Applications 229(9) Proof of Talagrands Inequality 238(5) Ideas from Information Theory 243(6) Branching Processes and Their Applications in the Analysis of Tree Structures and Tree Algorithms 249(1) Luc Devroye Branching Processes 249(7) Branching Processes 249(3) Some Limit Results 252(3) Bibliographic Remarks 255(1) Search Trees 256(7) Height of the Random Binary Search Tree 256(6) Quadtrees 262(1) Bibliographic Remarks 262(1) Heuristic Search 263(7) Introduction 263(1) Depth First Search 263(4) Bounded Lookahead and Backtrack 267(2) Bibliographic Remarks 269(1) Branching Random Walk 270(13) Definition 270(1) Main Properties 271(4) Application to Analysis of Height of Trees 275(6) Refinements for Binary Search Trees 281(2) Bibliographic Remarks 283(1) Crump-Mode-Jagers Process 283(8) Introduction 283(2) The Main Result 285(2) Application to Various Tree Models 287(2) The Bellman-Harris Branching Process 289(2) Conditional Branching Processes 291(24) Introduction 291(3) Examples of Trees in the Uniform Random Tree Model 294(2) Catalan Trees and Dyck Paths 296(2) Cayley Trees 298(1) Fringe Subtrees 299(1) Size of a Galton-Watson Tree 300(2) Height of a Galton-Watson Tree 302(1) Components in Random Graphs 303(3) Bibliographic Remarks 306(9) Author Index 315(6) Subject Index 321
Daugiau apie elektronines knygas Daugiau apie elektronines knygas
Pastovi nuoroda: https://www.kriso.lt/db/97836621278892e.html
Raktažodžiai: