دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
برای ارتباط با ما می توانید از طریق شماره موبایل زیر از طریق تماس و پیامک با ما در ارتباط باشید
در صورت عدم پاسخ گویی از طریق پیامک با پشتیبان در ارتباط باشید
برای کاربرانی که ثبت نام کرده اند
درصورت عدم همخوانی توضیحات با کتاب
از ساعت 7 صبح تا 10 شب
ویرایش: 2 Edition
نویسندگان: Michael Mitzenmacher. Eli Upfal
سری:
ISBN (شابک) : 9781107154889, 2016041654
ناشر: Cambridge University Press
سال نشر: 2017
تعداد صفحات: 490
زبان: English
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود)
حجم فایل: 12 مگابایت
در صورت تبدیل فایل کتاب Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب احتمال و محاسبات: تصادفی سازی و تکنیک های احتمالی در الگوریتم ها و تجزیه و تحلیل داده ها نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
این نسخه جدید که بسیار گسترش یافته است، فقط به یک پیشینه ابتدایی در ریاضیات گسسته نیاز دارد و مقدمه ای جامع از نقش تصادفی سازی و تکنیک های احتمالی در علوم کامپیوتر مدرن ارائه می دهد. فصلها و بخشهای جدید اضافهشده موضوعاتی از جمله توزیعهای عادی، پیچیدگی نمونه، بعد VC، پیچیدگی Rademacher، قوانین قدرت و توزیعهای مرتبط، هش کردن فاخته، و لمای محلی Lovasz را پوشش میدهند. مطالب مرتبط با یادگیری ماشین و تجزیه و تحلیل کلان داده دانش آموزان را قادر می سازد تا تکنیک ها و کاربردهای مدرن را بیاموزند. در میان بسیاری از تمرینها و مثالهای جدید، تمرینهای مرتبط با برنامهنویسی هستند که به دانشآموزان آموزش عالی در حل مسائل مربوطه میدهند. این کتاب یک ابزار آموزشی ضروری برای همراهی یک دوره یک یا دو ترم برای دانشجویان مقطع کارشناسی ارشد در علوم کامپیوتر و ریاضیات کاربردی فراهم می کند.
Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics including normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. Material relevant to machine learning and big data analysis enables students to learn modern techniques and applications. Among the many new exercises and examples are programming-related exercises that provide students with excellent training in solving relevant problems. This book provides an indispensable teaching tool to accompany a one- or two-semester course for advanced undergraduate students in computer science and applied mathematics.
Cover Half title Title Copyright Dedication Contents Preface to the Second Edition Preface to the First Edition 1 Events and Probability 1.1 Application: Verifying Polynomial Identities 1.2 Axioms of Probability 1.3 Application: Verifying Matrix Multiplication 1.4 Application: Naïve Bayesian Classifier 1.5 Application: A Randomized Min-Cut Algorithm 1.6 Exercises 2 Discrete Random Variables and Expectation 2.1 Random Variables and Expectation 2.1.1 Linearity of Expectations 2.1.2 Jensen\'s Inequality 2.2 The Bernoulli and Binomial Random Variables 2.3 Conditional Expectation 2.4 The Geometric Distribution 2.4.1 Example: Coupon Collector\'s Problem 2.5 Application: The Expected Run-Time of Quicksort 2.6 Exercises 3 Moments and Deviations 3.1 Markov\'s Inequality 3.2 Variance and Moments of a Random Variable 3.2.1 Example: Variance of a Binomial Random Variable 3.3 Chebyshev\'s Inequality 3.3.1 Example: Coupon Collector\'s Problem 3.4 Median and Mean 3.5 Application: A Randomized Algorithm for Computing the Median 3.5.1 The Algorithm 3.5.2 Analysis of the Algorithm 3.6 Exercises 4 Chernoff and Hoeffding Bounds 4.1 Moment Generating Functions 4.2 Deriving and Applying Chernoff Bounds 4.2.1 Chernoff Bounds for the Sum of Poisson Trials 4.2.2 Example: Coin Flips 4.2.3 Application: Estimating a Parameter 4.3 Better Bounds for Some Special Cases 4.4 Application: Set Balancing 4.5 The Hoeffding Bound 4.6* Application: Packet Routing in Sparse Networks 4.6.1 Permutation Routing on the Hypercube 4.6.2 Permutation Routing on the Butterfly 4.7 Exercises 5 Balls, Bins, and Random Graphs 5.1 Example: The Birthday Paradox 5.2 Balls into Bins 5.2.1 The Balls-and-Bins Model 5.2.2 Application: Bucket Sort 5.3 The Poisson Distribution 5.3.1 Limit of the Binomial Distribution 5.4 The Poisson Approximation 5.4.1* Example: Coupon Collector\'s Problem, Revisited 5.5 Application: Hashing 5.5.1 Chain Hashing 5.5.2 Hashing: Bit Strings 5.5.3 Bloom Filters 5.5.4 Breaking Symmetry 5.6 Random Graphs 5.6.1 Random Graph Models 5.6.2 Application: Hamiltonian Cycles in Random Graphs 5.7 Exercises 5.8 An Exploratory Assignment 6 The Probabilistic Method 6.1 The Basic Counting Argument 6.2 The Expectation Argument 6.2.1 Application: Finding a Large Cut 6.2.2 Application: Maximum Satisfiability 6.3 Derandomization Using Conditional Expectations 6.4 Sample and Modify 6.4.1 Application: Independent Sets 6.4.2 Application: Graphs with Large Girth 6.5 The Second Moment Method 6.5.1 Application: Threshold Behavior in Random Graphs 6.6 The Conditional Expectation Inequality 6.7 The Lovász Local Lemma 6.7.1 Application: Edge-Disjoint Paths 6.7.2 Application: Satisfiability 6.8* Explicit Constructions Using the Local Lemma 6.8.1 Application: A Satisfiability Algorithm 6.9 Lovász Local Lemma: The General Case 6.10* The Algorithmic Lovász Local Lemma 6.11 Exercises 7 Markov Chains and Random Walks 7.1 Markov Chains: Definitions and Representations 7.1.1 Application: A Randomized Algorithm for 2-Satisfiability 7.1.2 Application: A Randomized Algorithm for 3-Satisfiability 7.2 Classification of States 7.2.1 Example: The Gambler\'s Ruin 7.3 Stationary Distributions 7.3.1 Example: A Simple Queue 7.4 Random Walks on Undirected Graphs 7.4.1 Application: An s–t Connectivity Algorithm 7.5 Parrondo\'s Paradox 7.6 Exercises 8 Continuous Distributions and the Poisson Process 8.1 Continuous Random Variables 8.1.1 Probability Distributions in R 8.1.2 Joint Distributions and Conditional Probability 8.2 The Uniform Distribution 8.2.1 Additional Properties of the Uniform Distribution 8.3 The Exponential Distribution 8.3.1 Additional Properties of the Exponential Distribution 8.3.2* Example: Balls and Bins with Feedback 8.4 The Poisson Process 8.4.1 Interarrival Distribution 8.4.2 Combining and Splitting Poisson Processes 8.4.3 Conditional Arrival Time Distribution 8.5 Continuous Time Markov Processes 8.6 Example: Markovian Queues 8.6.1 M/M/1 Queue in Equilibrium 8.6.2 M/M/1/K Queue in Equilibrium 8.6.3 The Number of Customers in an M/M/∞ Queue 8.7 Exercises 9 The Normal Distribution 9.1 The Normal Distribution 9.1.1 The Standard Normal Distribution 9.1.2 The General Univariate Normal Distribution 9.1.3 The Moment Generating Function 9.2* Limit of the Binomial Distribution 9.3 The Central Limit Theorem 9.4* Multivariate Normal Distributions 9.4.1 Properties of the Multivariate Normal Distribution 9.5 Application: Generating Normally Distributed Random Values 9.6 Maximum Likelihood Point Estimates 9.7 Application: EM Algorithm For a Mixture of Gaussians 9.8 Exercises 10 Entropy, Randomness, and Information 10.1 The Entropy Function 10.2 Entropy and Binomial Coefficients 10.3 Entropy: A Measure of Randomness 10.4 Compression 10.5* Coding: Shannon\'s Theorem 10.6 Exercises 11 The Monte Carlo Method 11.1 The Monte Carlo Method 11.2 Application: The DNF Counting Problem 11.2.1 The Naïve Approach 11.2.2 A Fully Polynomial Randomized Scheme for DNF Counting 11.3 From Approximate Sampling to Approximate Counting 11.4 The Markov Chain Monte Carlo Method 11.4.1 The Metropolis Algorithm 11.5 Exercises 11.6 An Exploratory Assignment on Minimum Spanning Trees 12 Coupling of Markov Chains 12.1 Variation Distance and Mixing Time 12.2 Coupling 12.2.1 Example: Shuffling Cards 12.2.2 Example: Random Walks on the Hypercube 12.2.3 Example: Independent Sets of Fixed Size 12.3 Application: Variation Distance Is Nonincreasing 12.4 Geometric Convergence 12.5 Application: Approximately Sampling Proper Colorings 12.6 Path Coupling 12.7 Exercises 13 Martingales 13.1 Martingales 13.2 Stopping Times 13.2.1 Example: A Ballot Theorem 13.3 Wald\'s Equation 13.4 Tail Inequalities for Martingales 13.5 Applications of the Azuma–Hoeffding Inequality 13.5.1 General Formalization 13.5.2 Application: Pattern Matching 13.5.3 Application: Balls and Bins 13.5.4 Application: Chromatic Number 13.6 Exercises 14 Sample Complexity, VC Dimension, and Rademacher Complexity 14.1 The Learning Setting 14.2 VC Dimension 14.2.1 Additional Examples of VC Dimension 14.2.2 Growth Function 14.2.3 VC dimension component bounds 14.2.4 ε-nets and ε-samples 14.3 The ε-net Theorem 14.4 Application: PAC Learning 14.5 The ε-sample Theorem 14.5.1 Application: Agnostic Learning 14.5.2 Application: Data Mining 14.6 Rademacher Complexity 14.6.1 Rademacher Complexity and Sample Error 14.6.2 Estimating the Rademacher Complexity 14.6.3 Application: Agnostic Learning of a Binary Classification 14.7 Exercises 15 Pairwise Independence and Universal Hash Functions 15.1 Pairwise Independence 15.1.1 Example: A Construction of Pairwise Independent Bits 15.1.2 Application: Derandomizing an Algorithm for Large Cuts 15.1.3 Example: Constructing Pairwise Independent Values Modulo a Prime 15.2 Chebyshev\'s Inequality for Pairwise Independent Variables 15.2.1 Application: Sampling Using Fewer Random Bits 15.3 Universal Families of Hash Functions 15.3.1 Example: A 2-Universal Family of Hash Functions 15.3.2 Example: A Strongly 2-Universal Family of Hash Functions 15.3.3 Application: Perfect Hashing 15.4 Application: Finding Heavy Hitters in Data Streams 15.5 Exercises 16 Power Laws and Related Distributions 16.1 Power Law Distributions: Basic Definitions and Properties 16.2 Power Laws in Language 16.2.1 Zipf\'s Law and Other Examples 16.2.2 Languages via Optimization 16.2.3 Monkeys Typing Randomly 16.3 Preferential Attachment 16.3.1 A Formal Version 16.4 Using the Power Law in Algorithm Analysis 16.5 Other Related Distributions 16.5.1 Lognormal Distributions 16.5.2 Power Law with Exponential Cutoff 16.6 Exercises 17 Balanced Allocations and Cuckoo Hashing 17.1 The Power of Two Choices 17.1.1 The Upper Bound 17.2 Two Choices: The Lower Bound 17.3 Applications of the Power of Two Choices 17.3.1 Hashing 17.3.2 Dynamic Resource Allocation 17.4 Cuckoo Hashing 17.5 Extending Cuckoo Hashing 17.5.1 Cuckoo Hashing with Deletions 17.5.2 Handling Failures 17.5.3 More Choices and Bigger Bins 17.6 Exercises Further Reading Index