Contention Resolution慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

在本章里和大家一起学习随机算法

在本课程中

我们已经学习了贪婪算法分治算法

动态规划网络流算法等

而随机算法

也是一种算法设计与分析的主要方法

我们这里说的随机

指的是每次掷一个无偏的硬币

各有1/2的可能出现“字”或“背”

为什么要研究随机算法呢

因为随机往往会带来简单快速的算法

对于一些特定的问题

甚至随机算法是唯一已知的有效算法

随机算法的应用范围很广

如打破对称性协议图上的算法

随机快速排序哈希表

负载平衡及密码等等

我们先来看一下争端解决问题

分布式系统中争端解决问题定义为

给定n个进程P_1,…,P_n

它们都需要调用一个共享的数据库

如果有两个或多于两个进程

同时调用数据库

那么所有进程都被锁定

设计一个协议以保证所有的进程

都能够调用数据库

一个限制是

进程之间不能相互通讯

进程之间是平行的对称的

如果各自为政

很难保证所有进程都能访问数据库

我们面临的问题是

如何打破进程之间的对称性呢

我们给出的协议是一个随机算法

在时刻t

每个进程以p=1/n的概率调用数据库

定义事件S[i,t]

为进程i在时刻t成功调用数据库

那么这个事件发生的概率≥1/(e·n)≤1/(2n)

证明事件S[i,t]发生

当且仅当进程i调用数据库

而其它进程都没有调用数据库

每个进程是否调用数据库是独立的

因此 Pr[S(i,t)]=p(1-p)^n-1

令p=1/n

我们有 Pr[S(i,t)]=1/n(1-1/n)^n-1

由简单的微积分计算

可知当n从2增长

(1-1/n)^n-1从1/4单调递增趋近于1/e

(1-1/n)^n-1从1/2单调递减趋近于1/e

因此命题得证

我们再来证明

协议执行en轮后

进程i没有成功调用数据库的概率

至多为1/e

e·n(c ln n)轮后

这个概率至多为n^-c

证明定义事件F[i,t]为进程i从1到t轮

都没有成功调用数据库

因为每轮协议的执行是独立的

由之前的讨论可知

Pr[F(i,t)]≤(1-1/(en))^t

这里令t=┌en┐

那么Pr[F(i,t)]≤(1-1/(en))^┌en┐≤(1-1/(en))^en≤1/e

再令t=┌en┐┌cln n┐

我们有 Pr[F(i,t)]≤(1/e)^cln n≤n^-c

最后我们得到结论

2en ln n轮后

所有进程都成功调用数据库的概率

至少为1-1/n

证明定义事件F[t]为至少有一个进程

从1到t轮都没有成功调用数据库

那么Pr[F(t)]=对所有的i

事件F(i,t)的并发生的概率

由Union bound

它≤对所有的i

事件F(i,t)发生的概率之和

由之前的讨论

它≤n(1-1/(en))^t

令t=2┌en┐┌cln n┐

我们有Pr[F(t)]≤nn^-2=1/n

因此命题得证

这里用到了Union bound

是概率论中一个基本的结果

给定事件E_1,…,E_n

它们的并发生的概率≤它们分别发生的概率之和

算法设计与分析课程列表：

1 Introduction of Algorithm

-1.1 Introduction

--Introduction

-1.2 A First Problem: Stable Matching

--A First Problem: Stable Matching

-1.3 Gale-Shapley Algorithm

--Gale-Shapley Algorithm

-1.4 Understanding Gale-Shapley Algorithm

--Understanding Gale-Shapley Algorithm

-Homework1

-Lecture note 1

--Lecture note 1 Introduction of Algorithm

2 Basics of Algorithm Analysis

-2.1 Computational Tractability

--Computational Tractability

-2.2 Asymptotic Order of Growth

--Asymptotic Order of Growth

-2.3 A Survey of Common Running Times

--A Survey of Common Running Times

-Homework2

-Lecture note 2

--Lecture note 2 Basics of Algorithm Analysis

3 Graph

-3.1 Basic Definitions and Applications

--Basic Definitions and Applications

-3.2 Graph Traversal

--Graph Traversal

-3.3 Testing Bipartiteness

--Testing Bipartiteness

-3.4 Connectivity in Directed Graphs

--Connectivity in Directed Graphs

-3.5 DAG and Topological Ordering

--DAG and Topological Ordering

-Homework3

-Lecture note 3

--Lecture note 3 Graph

4 Greedy Algorithms

-4.1 Coin Changing

--Coin Changing

-4.2 Interval Scheduling

--Interval Scheduling

-4.3 Interval Partitioning

--Interval Partitioning

-4.4 Scheduling to Minimize Lateness

--Scheduling to Minimize Lateness

-4.5 Optimal Caching

--Optimal Caching

-4.6 Shortest Paths in a Graph

--Shortest Paths in a Graph

-4.7 Minimum Spanning Tree

--Minimum Spanning Tree

-4.8 Correctness of Algorithms

--Correctness of Algorithms

-4.9 Clustering

--Clustering

-Homework4

-Lecture note 4

--Lecture note 4 Greedy Algorithms

5 Divide and Conquer

-5.1 Mergesort

--Mergesort

-5.2 Counting Inversions

--Counting Inversions

-5.3 Closest Pair of Points

--Closest Pair of Points

-5.4 Integer Multiplication

--Integer Multiplication

-5.5 Matrix Multiplication

--Video

-5.6 Convolution and FFT

--Convolution and FFT

-5.7 FFT

--FFT

-5.8 Inverse DFT

--Inverse DFT

-Homework5

-Lecture note 5

--Lecture note 5 Divide and Conquer

6 Dynamic Programming

-6.1 Weighted Interval Scheduling

--Weighted Interval Scheduling

-6.2 Segmented Least Squares

--Segmented Least Squares

-6.3 Knapsack Problem

--Knapsack Problem

-6.4 RNA Secondary Structure

--RNA Secondary Structure

-6.5 Sequence Alignment

--Sequence Alignment

-6.6 Shortest Paths

--Shortest Paths

-Homework6

-Lecture note 6

--Lecture note 6 Dynamic Programming

7 Network Flow

-7.1 Flows and Cuts

--Flows and Cuts

-7.2 Minimum Cut and Maximum Flow

--Minimum Cut and Maximum Flow

-7.3 Ford-Fulkerson Algorithm

--Ford-Fulkerson Algorithm

-7.4 Choosing Good Augmenting Paths

--Choosing Good Augmenting Paths

-7.5 Bipartite Matching

--Bipartite Matching

-Homework7

-Lecture note 7

--Lecture note 7 Network Flow

8 NP and Computational Intractability

-8.1 Polynomial-Time Reductions

--Polynomial-Time Reductions

-8.2 Basic Reduction Strategies I

--Basic Reduction Strategies I

-8.3 Basic Reduction Strategies II

--Basic Reduction Strategies II

-8.4 Definition of NP

--Definition of NP

-8.5 Problems in NP

--Problems in NP

-8.6 NP-Completeness

--NP-Completeness

-8.7 Sequencing Problems

--Sequencing Problems

-8.8 Numerical Problems

--Numerical Problems

-8.9 co-NP and the Asymmetry of NP

--co-NP and the Asymmetry of NP

-Homework8

-Lecture note 8

--Lecture note 8 NP and Computational Intractability

9 Approximation Algorithms

-9.1 Load Balancing

--Load Balancing

-9.2 Center Selection

--Center Selection

-9.3 The Pricing Method: Vertex Cover

--The Pricing Method: Vertex Cover

-9.4 LP Rounding: Vertex Cover

--LP Rounding: Vertex Cover

-9.5 Knapsack Problem

--Knapsack Problem

-Homework9

-Lecture note 9

--Lecture note 9 Approximation Algorithms

10 Local Search

-10.1 Landscape of an Optimization Problem

--Landscape of an Optimization Problem

-10.2 Maximum Cut

--Maximum Cut

-10.3 Nash Equilibria

--Nash Equilibria

-10.4 Price of Stability

--Price of Stability

-Homework10

-Lecture note 10

--Lecture note 10 Local Search

11 Randomized Algorithms

-11.1 Contention Resolution

--Contention Resolution

-11.2 Linearity of Expectation

--Linearity of Expectation

-11.3 MAX 3-SAT

--MAX 3-SAT

-11.4 Chernoff Bounds

--Chernoff Bounds

-Homework11

-Lecture note 11

--Lecture note 11 Randomized Algorithms

Exam

-Exam

Contention Resolution在线视频