README

Contributors

• USTC 课程资源分享在线
  • 已收录课程

USTC 课程资源分享在线

原先依托于typst渲染的仓库不再维护，转用在线网站的形式，欢迎提交PR为仓库完善做出贡献！

已收录课程

• 研究生课程
  • 计算机科学与技术
    • COMP6001P算法设计与分析
    • COMP6002P组合数学
    • COMP6103P高级计算机网络
    • COMP6108P高级数据库系统

提交方式：

• Email
• ✅pull requests

CHANGELOG

Contributors

• Roadmap
• Changelog
  • 2026-01-15
  • 2026-01-14
  • 2026-01-13
  • 2026-01-12

Roadmap

• Download page source independently
• insert header and footer

Changelog

2026-01-15

• #plugin integrate gitinfo
  show git info
• #ui add tag style
  enhance tag visibility
• #ui insert header and footer (as markdown)
  page template config
• #feat download page source file
  markdown source file without decoration

2026-01-14

• #ui add progress bar
  reading progress bar at the top
• #ui add back-to-top button
  button scroll back to the top
• #ux add image zooming
  click-to-zoom for images

2026-01-13

• #ui integrate whichlang
  enhance code display
• #plugin integrate reading-time
  word count
• #plugin integrate toc
  inline outline

2026-01-12

• #integration integrate giscus
  github-base comments
• #plugin integrate katex
  enable latex display

计算机科学与技术

Contributors

• 目录

目录

• _COMP6001P算法设计与分析
  • 分布式算法复习知识点
  • 概率算法复习知识点
  • 近似算法复习知识点
• COMP6002P组合数学
  • ch02排列与组合
  • ch03二项式系数
  • ch04容斥原理
  • ch05生成函数
  • ch06递推关系
  • ch08Polya计数理论
• COMP6003P计算机应用数学
• COMP6004P计算机系统
• COMP6101P高级计算机体系结构
• COMP6102P并行算法
• COMP6103P高级计算机网络
  • 期末复习题型
• COMP6108P高级数据库系统
  • 2021-2022学年第一学期期末考试试卷

COMP6001P算法设计与分析

Contributors

• 分类

分类

• 笔记
  • 分布式算法复习知识点
  • 概率算法复习知识点
  • 近似算法复习知识点

分布式算法复习知识点

Contributors

• 一、分布式算法
  • 1.1 导论
  • 1.2 消息传递中的基本算法
    • 1.2.1 转移系统与安全性和活跃性
    • 1.2.2 系统
      • 异步系统
      • 同步系统
    • 1.2.3 复杂性度量
    • 1.2.4 生成树上的广播和敛播
      • 广播
      • 敛播
    • 1.2.5 构造生成树
    • 1.2.6 指定根构造 DFS 生成树
    • 1.2.7 不指定根构造 DFS 生成树
  • 1.3 环上选举算法
    • 1.3.1 异步环
      • $O(n^2)的算法$
      • $O(nlg(n))$的算法
    • 1.3.2 同步环
      • 证明上界的非均匀算法
      • 证明上界的均匀算法
      • 有限制的下界$O(nlgn)$
  • 1.4 计算模型
    • 1.4.1 Lamport 时间戳
    • 1.4.2 向量时间戳
    • 1.4.3 因果通信

转载自 cnblogs/学科笔记/中科大-算法分析与设计-分布式算法复习知识点.md at main · BamLubi/cnblogs 中科大-算法分析与设计-分布式算法复习知识点 - 小陆斑比 - 博客园

一、分布式算法

1.1 导论

并行处理与分布式处理的区别：

• 并行处理目标：使用所有处理器执行一个大任务。
• 分布式处理具有更高程度的不确定性和行为的独立性，每个处理器都有自己独立的任务。

分布式系统作用：

• 共享资源
• 改善性能
• 提高可靠性

模型：

• 异步共享存储模型：用于紧耦合机器
• 异步 msg 传递模型：用于松散耦合机器及广域网
• 同步 msg 传递模型：msg 延迟上界已知，系统执行划分为轮执行，是异步系统的特例

1.2 消息传递中的基本算法

每个处理器$p_i$可以模型化为一个具有状态集$Q_i$的状态机

初始状态：$Q_i$包含一个特殊的初始状态子集，每个inbuf必须为空，outbuf不一定为空。

转换函数：将可访问状态的inbuf转换到outbuf

配置：分布式系统上某点整个算法的全局状态

事件：计算事件和传递事件

执行：配置和事件交错的序列。

需满足安全性条件和活跃性条件。

1. 安全性：某个性质在每次执行的每个可达配置里都成立。“坏事从不发生”

2. 活跃性：某个性质在每次执行的某些可达配置里成立。“最终某个好事发生”

满足安全性条件称为执行。同时满足活跃性条件称为容许执行。

1.2.1 转移系统与安全性和活跃性

转移系统：$三元组TripleS=(C,\to ,I)$，$C$是配置集，$I$是初始配置的一个子集，$\to$是配置集上的二元转移关系。

可达：$\exists 序列{\gamma }_0\to {\gamma }_1\to \cdots \to {\gamma }_k=\delta ,且\forall 0\le i\le k-1,{\gamma }_i\to {\gamma }_{i+1},则称\delta 是可达的$

安全性：$S=(C,\to ,I),断言/性质P总是成立$

$\{P\}\to \{Q\}:\forall \gamma \to \delta ,ifP(\gamma ),thenQ(\delta )$，即如果 P 在转移前成立，则 Q 在转移后成立

定义：$P是S的不变式,\forall \gamma \in I,P(\gamma )成立且\{P\}\to \{P\},P总是成立$，P 为安全性条件

定理：如果 P 是 S 的不变式，那么对 S 的每次执行的每一配置 P 都成立

活跃性：在算法的每次执行的某些配置中，P 为真，且最终 P 为真。

判断方法：

• 范函数
• 无死锁 / 系统正常终止

范函数：$转移系统S和断言P,f:配置集C\to 良基集\omega$

良基集：$偏序集(\omega ,<)是良基的，当且仅当不存在无穷递减序列，即存在最小值$

1.2.2 系统

异步系统

异步：msg 传递时间和一个处理器的两个相继步骤之间的时间无上界

执行片段：一个有限或无限的序列，由配置和事件交替组成

执行：从初始配置开始的执行片段

调度：执行中的事件序列

容许执行：某个处理器有无限个计算事件（指处理器没有出错，并不是无限步），每个发送的 msg 都最终被传递。

同步系统

处理器按轮执行，一轮里，每个处理器可以发送一个 msg 到邻居，每个处理器一接受到 msg 就计算。

轮：配置和事件序列可以划分为不相交的轮，每轮由一个传递事件和一个计算事件组成。

同步系统与异步系统的区别：

1. 无错的同步系统中，算法的执行只取决于初始配置
2. 异步系统中，算法可能有不同的执行（不代表不同的结果）

1.2.3 复杂性度量

消息复杂度：所有容许执行上发送消息总数的最大值

时间复杂度：

• 同步系统：最大轮数
• 异步系统：所有计时容许执行中直到终止的最大时间

1.2.4 生成树上的广播和敛播

生成树 ST：具有共同顶点且不出现回路的子图。

最小生成树 MST：所有边权值和最小的生成树。

广播

基本步骤：

1. 根$p_r$发送$M$给所有的孩子。
2. 某节点收到父节点的$M$时，发送$M$给自己的所有孩子。

upon receiving no msg:
 if i=r then
        send <M> to all children;
  terminates;
upon receiving <M> from P_j:
 send <M> to all children;
 terminates;

消息复杂度$O(n)$

时间复杂度$O(h),h为生成树高度$

敛播

基本步骤：

1. 每个叶子节点发送消息给双亲
2. 每个非叶节点等待所有孩子的消息，之后再发消息给双亲

消息复杂度$O(n)$

时间复杂度$O(h),h为生成树高度$

1.2.5 构造生成树

Flooding 算法

消息复杂度：$O(2m-(n-1))$

事件复杂度：$O(D),D为网直径$

基本思想：

1. 根节点发送消息$M$给所有邻居

2. 当$P_i$收到来自$P_j$的消息$M$且是第一次收到消息$M$时，$P_i$发送$<parent>$给$P_j$，$P_i$向其他向自己发送消息$M$的节点发送$<reject>$，$P_i$向$P_j$以外的邻居发送消息$M$

3. $P_i$收到$P_j的<parent>$消息，则表明$P_i是P_j的父节点$

Code for Pi (0<=i<=n-1)
初值：parent=nil；集合children和other均为空集

upon receiving no message:
    if i=r and parent=nil then { //根尚未发送M
     send M to all neighbors;
     parent:=i;} //根的双亲置为自己
upon receiving M from neighbor pj:
    if parent=nil then { //pi此前未收到过M，M是pi收到的第1个msg
     parent:=j;
     send <parent> to pj; //pj是pi的双亲
     send M to all neighbors except pj;
    }else //pj不可能是pi的双亲，pi收到的M不是第1个msg
     send <reject> to pj;
upon receiving <parent> from neighbor pj:
    children:=children∪{ j }; //pj是pi的孩子，将j加入孩子集
    if children∪other包含了除parent外的所有邻居 then terminate;
upon receiving <reject> from neighbor pj:
    other:=other∪{ j }; //将j加入other，通过非树边发送的msg。
    if children∪other包含了除parent外的所有邻居 then terminate

异步模型中，构造以$p_r$为根的生成树

同步模型中，构造的一定是BFS。

在异步系统中无法生成 BFS，因为消息传递无上界，最坏可能出现单链。

1.2.6 指定根构造 DFS 生成树

基本思想：

1. 选定根节点$P_r$，向某一邻接节点发送消息$M$
2. $P_i$收到$P_j$的消息$M$是第一个来自邻接节点的消息时，认定$P_j$为其双亲，并向之后给自己发消息$M$的节点发送$<reject>$
3. $P_i$向未发过消息的邻居中任选一个发送消息$M$，并等待回复
4. $P_i$向所有邻居发过消息，则$P_i$终止

Code for Pi (0<=i<=n-1)
初值：
parent = nil；
children = Φ；
unexplored = Pi's neighbors

upon receiving no message:
 if i=r and parent=nil then { //当Pi为根且未发送M
     parent:=i; // 将parent设置为自身
      任意 Pj ∈ unexplored
       将 Pj 从 unexplored 中删去
     send M to Pj;}//endif
upon receiving M from neighbor Pj:
    if parent=nil then { //pi此前未收到过M
     parent:=j;
        将 Pj 从 unexplored 中删去
        if unexplored!=Φ then {
           任意 Pk ∈ unexplored
       将 Pk 从 unexplored 中删去
     send M to Pk;
        }else send <parent> to parent;
    }else send <reject> to pj; //当Pj已访问过
upon receiving <parent> or <reject> from neighbor pj:
    if received <parent> then add j to children; // Pj是Pi的孩子
    if unexplored = Φ then { //Pi的邻居均已访问
     if parent!=i then send <parent> to parent; //Pi非根，返回至双亲
      terminate; //以Pi为根的DFS子树已构造好
    }else{ //选择Pi未访问过的邻居访问
     任意 Pk ∈ unexplored
       将 Pk 从 unexplored 中删去
     send M to Pk;
    }

消息复杂度，时间复杂度：$O(m)$

1.2.7 不指定根构造 DFS 生成树

与领导者选举问题类似，为破对称问题

基本思想：

1. 每个结点均可自发唤醒，试图构造一根以自己为根的 DFS 生成树。若两棵 DFS 树试图链接同一节点（未必同时），选择根 ID 较大的 DFS 树加入。

2. 每个结点设置一个 leader 变量，即为当前 DFS 树的根 ID

3. 结点自发唤醒时，将自己的 leader 发送给某一邻居

Code for Pi (0<=i<=n-1)
初值：
parent = nil；
leader = 0;
children = Φ；
unexplored = Pi's neighbors

upon receiving no message: // 自主唤醒
    if parent=nil then { //若非空，则Pi在某子树上，则Pi失去竞选机会
     leader:=id; parent:=i; // 将parent设置为自身
      任意 Pj ∈ unexplored
       将 Pj 从 unexplored 中删去
     send <leader> to Pj;}//endif
upon receiving <new_id> from neighbor Pj:
    if leader<new_id then { //将Pi所在树合并到Pj所在树中
     leader:=new_id; parent:=j;
      unexplored:=all neighbors of Pi except Pj; //重置未访问邻居集
       if unexplored!=Φ then { //原Pi所在DFS树修改各自id
            任意 Pk ∈ unexplored
             将 Pk 从 unexplored 中删去
      send <leader> to Pk;
       }else send <parent> to parent;
    }else if leader=new_id then send <already> to Pj;
upon receiving <parent> or <already> from neighbor pj:
    if received <parent> then add j to children;
    if unexplored = Φ then { //Pi的邻居均已访问
     if parent!=i then send <parent> to parent; //Pi非根，返回至双亲
      else terminate as root of the DFS tree; //以Pi为根的DFS子树已构造好
    }else{ //选择Pi未访问过的邻居访问
     任意 Pk ∈ unexplored
       将 Pk 从 unexplored 中删去
     send <leader> to Pk;
    }

一个具有 m 条边，n 个节点的网络，自发启动的节点由 p 个，ID 值最大的启动时间为 t。

消息复杂度：$O(p{n}^2)$

时间复杂度：$O(t+m)$

1.3 环上选举算法

匿名的：环中处理器没有唯一的标识符，每个处理器具有相同的状态机。

一致性、均匀的：不知道处理器的数目

解释一致性和非一致性：

算法一：向右转发 n 步 msg，然后终止。 => non_uniform

算法二：向右转发 msg，直到 msg 发送者收到 msg。 => uniform

在一个匿名的、一致性算法中，所有处理器只有一个状态机。

在一个匿名的、非一致性算法中，每个 n 值对应一种状态机。

• 同步环系统不存在匿名的、一致性的领导者选举算法
• 异步环系统不存在匿名的领导者选举算法

1.3.1 异步环

开调度：在算法 A 的一次调度中，有一条边上无消息传递，则为开边。

（开调度未必是容许的调度，是容许执行的一个有限前缀）

异步环上的选举算法有消息复杂度下界$O(nlgn)$

$O(n^2)的算法$

基本思想：

1. 每个处理器发送一个标识符 msg 给左邻居，然后等着接收右邻居的 msg。
2. 每个处理器收到 msg 时，若收到的 id 大于自身，则向左邻居转发。
3. 若处理器收到自己的标识符 id，则宣布自己是 leader，并发终止 msg 给左邻居，然后终止
4. 若处理器收到终止 msg，则向左转发，然后终止

核心思想：处理器向左邻居发送标识符 msg，通过比对 id 确定 leader，只有最大的 id 消息会回到他自己。

Code for Pi (0<=i<=n-1)
初值：asleep=true; id = i;

While (receiving no message) do
  (1) if asleep do
      (1.1) asleep = false
      (1.2) send <id> to left-negihbor
   end if
End while
While (receiving <i> from right-neighbor) do
 (1) if id < <i> then send <i> to left-neighbor
       end if
 (2) if id = <i> then
      (2.1) send <Leader,i> to left-neighbor
      (2.2) terminates as Leader
   end if
End while
While (receiving <Leader,j> from right-neighbor) do
 (1) send <Leader,j> to left-neighbor
 (2) terminates as non-Leader
End while

消息复杂度：$O(n^2)$

$O(nlg(n))$的算法

k 邻居：据某一处理器距离不超过 k 的处理器，左边有 k 个，右边有 k 个，共有$2k+1$个。

基本思想：

1. 阶段 0：每个节点向两个 1-邻居发送 id 消息，若邻居的 id 小于此消息则回复 reply，否则吞没。若一个节点收到两个邻居的 reply，则自认为 leader，并进入阶段 1。
2. 阶段$l$：在上一阶段成为 leader 的处理器，继续发送 id 消息给$2^l$邻居，若收到来自左右两个方向的 reply，则自认为 leader。
3. 若收到自己的消息，则终止。

核心思想：第$l$阶段一个处理器试图成为其**$2^l$-邻居**的临时 leader。只有在$l-th$阶段成为 leader 的处理器才能继续$(l+1)-th$阶段。

Code for Pi (0<=i<=n-1)
初值：asleep=true;

upon receiving no msg:
      if  asleep then{
       asleep:=false;//每个结点唤醒后不再进入此代码
        send <probe,id, 0, 0> to left and right;
      }
upon receiving <probe, j, l,d> from left_or_right (resp, right):
    if(j=id) then //收到自己id终止，省略发终止msg
       send <leader,id> to left neighbour;
        terminate as the leader;
    if(j>id) and (d<2^l) then //向前转发probe msg
     send <probe, j, l, d+1> to right_or_left (resp, left)
    if(j>id) and (d≥2^l) then //到达最后一个邻居仍未没收
     send <reply, j, l > to left_or_right (resp, right) // 回答
    // 若j<id, 则没收probe消息
upon receiving <reply ,j , l> from left (resp, right):
    if j≠id then // 判断是否转发到初始点
     send <reply, j, l> to right (resp, left); //转发reply
    else //j=id时，Pi已收到一个方向的回答msg
     if already received <reply, j, l> from right (resp, left) then //也收到另一方向发回的reply
    send <probe, id, l+1, 0> to left and right; //Pi是phase l的临时leader，继续下一阶段
upon receiving <leader, idj> from right:
    send <leader, idj> to left;
    terminate as nonleader;

阶段$k$，临时 leader 树最多为$\frac{n}{2^k+1}$，启动的 msg 数目最多为$4\ast 2^k$

消息复杂度：$O(nlgn)$

1.3.2 同步环

消息复杂度上界$O(n)$，下界$O(nlgn)$

上界$O(n)$：

• 非均匀：要求环中所有节点开始于同一轮
• 均匀：节点可以开始于不同轮

证明上界的非均匀算法

必须知道环大小 n，所有节点开始于同一轮

假定 id 最小的为 leader

基本思想：按阶段运行，每个阶段由 n 轮组成。阶段$i$中，处理器 id 也为$i$的选举为 leader，然后终止算法。

各节点互不知道彼此的 id 值。

消息复杂度：恰有 n 个消息被发送，$O(n)$

证明上界的均匀算法

无需知道环大小

一个处理可以：自发唤醒或被动唤醒

基本思想：

1. 源于$id=i$节点的 msg，在被转发前延迟$2^i-1$轮。
2. 每个自发唤醒的节点绕环发送一个唤醒 msg，且无延迟
3. 若节点在启动前收到唤醒 msg，则该节点只作转发操作。

只有自发唤醒的节点，才有可能选为 leader

初值：asleep=true；waiting = ф；R = 计算事件中接收msg的集合；s = ф；//the msg to be sent

if asleep then {
    asleep:=false;
    if R = Φ then { // pi未收到过msg，属于自发唤醒
        min:=id;   // 参与选举
        s:=s+{<id>}; // 准备发送
    }else{ //已收到过msg，但此前未启动，被唤醒故Pi不参与
     min:=∞; //选举，置min为∞ ，使其变为relay结点
     // relay:=true; ？
    }
}
for each <m> in R do {// 处理完收到的m后相当于从R中删去
    if m < min then { // 收到的id较小时通过
     become not elected;  // Pi未被选中
     // 可用relay控制使转发节点不延迟？
     将<m>加入waiting且记住m何时加入; // m加入延迟转发
     min:=m;
    } // if m > min then it is swallowed
    if m=id then become elected; // Pi被选中
} //endfor
for each <m> in waiting do
    if <m> 是在2^m-1轮之前接收的 then
     将<m>从waiting中删去并加入S
send S to left;

发送的消息：

• 第一类：第一阶段的 msg（唤醒 msg）
• 第二类：最终 leader 的 msg 进入自己的第二阶段之前发送的第二阶段 msg（其他节点发的）
• 第三类：最终 leader 的 msg 进入自己的第二阶段之后发送的第二阶段 msg（包括 leader 发的）

第一类总数最多$n$

第二类总数最多$n$

第三类总数最多$2n$

消息复杂度：$O(4n)$

有限制的下界$O(nlgn)$

序等价：两个环$x_0,x_1,\cdots ,x_n-1$和$y_0,y_1,\cdots ,y_n-1$中$x_i<x_j,当且仅当y_i<y_j$

若一算法只与环上标识符之间的相对次序相关，而与具体 id 无关，则该算法一定只是基于标识符的比较

对于每个$n\ge 8,n是2的方幂$，存在大小为 n 的环$S_n$，使得基于比较的同步 leader 选举算法 A，在容许执行里发送的 msg 数目为$O(nlgn)$。

构造$S_n$

1. 定义大小为 n 的环$R_n^{rev}$，令$P_i$的 id 为$rev(i):i的二进制逆序列$
2. 将环划分为长度为$j,j为2的方幂$的连续片段，则这些片段是序等价的。
3. 片断数为$\frac{n}{j}$

1.4 计算模型

计算模型的复杂性：

• 系统由并发部件构成
• 无全局时钟
• 必须捕捉部件可能的失效

对策：

• 因果关系
• 一致状态
• 全局状态

为什么分布式系统缺乏全局系统状态？

1. 非即时通信（传播延时，资源竞争，丢失 msg 重发）

2. 相对性影响（大多数计算机的实际时钟存在漂移，时钟同步依旧是一个问题）

3. 中断（不可能在同一时刻观察一个分布式系统的全局状态）

次序：$e_1<e_2:事件e_1发生在e_2之前$

定序：

• 发生在同一节点上的事件满足全序，$e_1{<}_p{e}_2$
• $e_1$发送消息，$e_2$接收消息，则$e_1{<}_m{e}_2$

Happens-before 关系：${<}_H$，一种偏序关系

并发事件：两个事件不能由 ${<}_H$ 定序

有时将 Happens-before 关系描述为一个有向无环图

如何将 H 关系的偏序关系转变成全序关系：

• 在有向无环图 DAG 上的拓扑排序
• Lamport 算法

1.4.1 Lamport 时间戳

基本思想：

• 事件 e有附加时间戳：e.TS
• 节点有局部时间戳：my_TS
• msg有附加时间戳：m.TS
• 节点执行事件时，将自己的时间戳赋给该事件。
• 节点发送 msg时，将自己的时间戳给所有的 msg。

• 接收消息时，本地时间戳更新为最大值
• 发送消息时，使用本地时间戳打标签

Initially: my_TS = 0;
On event e:
    if(e == 接收消息m) then
     my_TS = max(m.TS, my_TS)); // 取msg时间戳和节点时间戳较大值
     my_TS++;
     e.TS = my_TS; // 给事件e打时间戳
     if(e == 发送消息m) then
      m.TS = my_TS; // 给消息打时间戳

每一时间的时间戳大于前驱时间的时间戳

问题：不同的时间可能有相同的时间戳（并发事件）

改进算法：使用节点地址作为时间戳低位，如$1.1,2.2$。标号后按字典序得到全序关系。

问题：无法通过时间戳判定两个事件是否有因果关系

1.4.2 向量时间戳

向量时间戳 VT：$e.VT是个数组，e.VT[i]=k表示再节点i上，事件e之前有k个事件(可包括自己)$

基本思想：

• 节点有局部向量时间戳：my_VT

• 事件 e 有向量时间戳：e.VT

• msg 有向量时间戳：m.VT

Initially: my_VT=[0,0,,,0];
On event e:
    if(e == 接收消息m) then
  for i= 1 to M do // 向量时间戳的每个分量只增不减
      my_VT[i] = max(m.VT[i], my_VT[i]);
    my_VT[self]++; // self是本节点的名字
    e.VT = my_VT; // 给事件e打时间戳
    if(e == 发送消息m) then
     m.VT = my_VT; // 给消息m打时间戳

向量时间戳比较：

e1.VT = (5,4,1,3)
e2.VT = (3,6,4,2)
e3.VT = (0,0,1,3)

1. e1 和 e2 之间没有完全大于或完全小于的关系，则 e1 和 e2 是并发的。

2. e3 在因果序上先于 e1

1.4.3 因果通信

处理器不能选择 msg 到达的时间，但是可以抑制过早到达的 msg。

如 TCP 中的 FIFO 通信。

基本思想：

• 抑制从 P 发送的消息，知道可以断定没有其他消息早于 m 发生
• 在每个节点上：
  • $earliest[1\dots M]:不同节点当前能够传递的消息时间戳的下界$
  • $blocked[1\dots M]P:阻塞队列数组，每个分量是一个队列$

Causal Msg Delivery
Definition:
    时间戳lk:
     使用Lamport时间戳,lk=1;
      使用向量时间戳,lk=(0,,,0,1,0,,,0),第k位为1;
Initially:
    earliest[k] = lk,k=1,,,M // 不同节点当前能传递的消息时间戳的下界
    blocked[k] = {},k=1,,,M // 阻塞队列置空

On the receipt of msg <m> from node P:
    delivery_list = {}
    if (blocked[p]==空) then
     earliest[p] = m.timestamp;
      blocked[p].push_back(m); // 处理收到的消息
    //处理阻塞队列
    while(∃k使blocked[k]非空 &&
     对i=1,,,M(除k和self外) not_earliest(earliest[i],earliest[k],i) )
      // 没有消息比k更早到
    {
     将blocked[k]队头元素m’出队，且加入到delivery_list;
     if (blocked[k]!=空) then
      earliest[k] = m’.timestamp；
     else
       increment earliest[k] by lk
    }
    deliver the msgs in delivery_list; // 按因果序

可能发生死锁（一节点上时间不发送你要的 msg）

该因果通信算法常用于组播。

概率算法复习知识点

Contributors

• 二、概率算法
  • 2.1 数字算法
  • 2.2 Sherwood 算法
  • 2.3 Las Vegas 算法
    • 2.3.1 八皇后问题
    • 2.3.2 模 p 平方根
    • 2.3.3 整数的因数分解
  • 2.4 Monte Carlo 算法
    • 2.4.1 主元素问题
    • 2.4.2 素数测定
    • 2.4.3 矩阵乘法验证

转载自 cnblogs/学科笔记/中科大-算法分析与设计-概率算法复习知识点.md at main · BamLubi/cnblogs 中科大-算法分析与设计-概率算法复习知识点 - 小陆斑比 - 博客园

二、概率算法

概率算法分类：

• 数字算法：求近似解
• Monte Carlo 算法：解判定问题或只有一个正确解的问题。答案未必正确。
• Las Vegas 算法：决不返回错误答案。
• Sherwood 算法：总是给出正确答案。

2.1 数字算法

找到数字问题的近似解

$\Pi$值计算：投飞镖模拟，单位圆和外切正方形。

$$\begin{gathered} >\frac{落在圆内}{总数}=\frac{k}{n}=\frac{\pi r^2}{4r^2}=\frac{\pi }{4} \\ >\Rightarrow \pi =4\frac{k}{n}> \end{gathered}$$

Darts(n){
    k=0;
    for i=1 to n do {
        x = uniform(0,1); y = uniform(0,1);
        if(x*x+y*y<=1) then k++;
    }
    return 4k/n;
}

数字积分：Monte Carlo 积分，但不是本课中的 MC 算法。

计算积分$S={\int }_0^{!}f(x)dx$

HitorMiss 算法：单位面积正方形投飞镖，落入积分函数下方的为 k，$\frac{k}{n}=\frac{S}{1}$

HitorMiss(f, n){
    k=0;
    for i=1 to n do {
        x = uniform(0,1); y = uniform(0,1);
        if(y<=f(x)) then k++;
    }
    return k/n;
}

Crude 算法：积分区间上随机取点，取算术平均值乘区间宽度。${\int }_a^{b}f(x)dx=(b-1)\frac{1}{n}{\sum }_{i=1}^{n}f(x_i)$

Crude(f,n,a,b){
    sum = 0;
    for i=1 to n do{
        x = uniform(a,b);
        sum = sum + f(x);
    }
    return (b-a)*sum/n;
}

相对而言，Crude 算法方差更小，但是 HitorMiss 算法在相同时间迭代次数更多。

解题思路：$\pi =4{\int }_0^1\sqrt{1-x^2}dx$

Trapezoid 确定性算法：梯形算法，将区间划分为 n-1 个子区间

$S=\delta \ast (f(a+\delta )+f(a+2\delta )+\cdots +\frac{f(a)+f(b)}{2})$

Trapezoid(f,n,a,b){
    // 假设n>=2
    delta = (b-a)/(n-1);
    sum = (f(a)+f(b))/2;
    for(x=a+delta; x<=b-delta; x+=delta){
        sum = sum + f(x);
    }
    return sum * delta;
}

确定性算法有时求不出解，概率算法适用于高维定积分。

概率计数：估计整数值，如集合的大小或者集合中不同对象数目的估计。

求集合的大小：有放回的随机抽取元素，k 是第 1 次出现重复元素之前所选出的数目。

$n足够大时,k=\beta \sqrt{n}=\sqrt{\frac{\pi }{2}n},即n=\frac{2k^2}{\pi }$

SetCount(X){
    k = 0; S = {}; a = uniform(X);
    do{
        k++;
        S = S U {a};
        a = uniform(X);
    }while(a不属于S)
    return 2k**2/pi
}

多重集合不同对象数目估计：将单词映射到长度为 m 的位串，$\pi (y,b)=\{\begin{array}{l}i,y[i]=b的最小i\\ k+1,y[i]!=b\end{array}$

WordCount(){
    y[1...m+1] = 0;
    for 磁带上的每个单词 x do {
        i = pi(h(x), 1); // x的散列值中等于1的最小位置，表示x是以 00...01....开头的
        y[i] = 1;
    }
    return pi(y, 0); // 返回y中等于0的最小位置
}
2^(k-2)<=n<=2^k，更准确的n=2^k/1.54703

2.2 Sherwood 算法

总是给出正确的答案，平滑不同输入实例的执行时间。

用途：平均性能较优，但是最坏性能较差时才使用。比如选择和排序，对元素的相对顺序敏感。

基本过程：

1. 将被解实例变换到一个随机实例。（预处理）
2. 用确定算法解随机实例，得到一个解。
3. 将此解变换为原实例的解。（后处理）

RH(x){
    // 用Sherwood算法计算f(x)
    n = length(x); // x的size为n
    r = uniform(A[n]); // 随机选取一个元素
    y = u(x,r); // 将原实例x转化为随机实例y
    s = f(y); // 用确定算法求y的解s
    return v(r,s); // 将s的解还原为x的解
}

选择和排序的 Sherwood 算法：将输入实例打乱，无需后处理。在调用确定性算法前，先洗牌

Shuffle(T){
    n = length(T);
    for i=1 to n-1 do {
        // 在T[1...n]中随机选取一个元素放在T[i]上
        j = uniform(1...n);
        sqap(T[i],T[j]);
    }
}

离散对数计算：$a=g^{x}modp,计算x=lo{g}_{g,p}a$

简单算法：

1. 计算$g^{x}modp,0\le x\le p-1$，x 有限个取值，因为离散对数$<g>$是个循环群
2. 验证$a=g^{x}modp$是否成立

dlog(g,a,p){ // 当这样的算法不存在时，算法返回p
    x = 0; y = 1;
    do{
        x++;
        y = y*g; // 计算y=g**x
    }while(a!=y%p && x!=p);
    return x;
}

定理：

• $lo{g}_{g,p}(st\%p)=(lo{g}_{g,p}s+lo{g}_{g,p}t)\%(p-1)$
• $lo{g}_{g,p}(g^r\%p)=r,0\le r\le p-2$

Sherwood 改造算法：

dlogRH(g, a, p){
    r = uniform(0..p-2);
    b = g^r mod p; // 求幂模b=g**r%p
    c = ba mod p; // 定理1
    y = dlog(g,c,p); // 使用确定性算法求log_{g,p}c, y=r+x
    return (y-r) mod (p-1); // 求x
}

$$>\begin{array}{rl}>y& =lo{g}_{g,p}(ba\%p)=(lo{g}_{g,p}b+lo{g}_{g,p}a)\%(p-1)\\ >& =(lo{g}_{g,p}(g^r\%p)+lo{g}_{g,p}a)\%(p-1)\\ >& =(r+x)\%(p-1)>\end{array}>$$

搜索有序表：数值数组和指针数组构成有序的静态链表。

时间为$O(n)$的确定算法：直接顺序搜索，平均时间$O(\frac{n}{2})$

Search(x, i){
    while x > val[i] do
     i = ptr[i];
     return i;
}
A(x){
    return Search(x, head);
}

时间为$O(n)$的概率算法：从随机的一个点左右开始顺序搜索，平均时间$O(\frac{n}{3})$

D(x){
    i = uniform(1..n);
    y = val[i];
    case{
        x<y: return Search(x, head);   // 从头开始搜索
        x>y: return Search(x, ptr[i]); // 从下一个位置开始搜索
        otherwise: return i; // case3 x==y
    }
}

平均时间为$O(\sqrt{n})$的确定算法：在前$\lfloor \sqrt{n}\rfloor$个数中找不大于 x 的最大整数的下标，从该数开始向后查找。

B(x){ // 设x在val[1..n]中
    i = head;
    max = val[i]; // max初值是表val中的最小值
    for j=1 to [sqrt(n)] do { // 在前根号n个数中找不大于x的最大整数y的下标
        y = val[j];
        if max < y <= x then {
            i = y; max = y;
        }
    }
    return Search(x, i);
}

2.3 Las Vegas 算法

特点：

• 更有效率的算法
• 时间上界可能不存在
• 可能找不到解，但如果找到一定是正确的
• 成功的概率随执行时间的增加而增加

算法的一般形式：$LV(x,y,success),x为输入,y为输出$

约定记号：

• $p(x),算法成功的概率$
• $s(x),算法成功时的期望时间$
• $e(x),算法失败时的期望时间$

一般会多次运行 LV 算法，知道成功

Obstinate(x){
    repeat
     LV(x,y,success);
    until success;
    return y;
}

找到正确解的期望时间：

$$>\begin{array}{rl}>t(x)& =p(x)s(x)+(1-p(x))(e(x)+t(x))\\ >& =s(x)+\frac{1-p(x)}{p(x)}e(x)>\end{array}>$$

2.3.1 八皇后问题

要求：

• 行不冲突：行号相等
• 列不冲突：列号相等
• 主对角线不冲突：行列号之差相等
• 辅对角线不冲突：行列号之和相等

传统回溯法：分别决定每一行放在哪个位置

i = j = 1;
while i ≤ 8 do { // 当前行号i≤ 8
    检查当前行i：从当前列j起向后逐列试探，寻找安全列号；
    if 找到安全列号 then {
        放置皇后，将列号记入栈，并将下一行置为当前行(i++);
        j=1; //当前列置为1
    } else {
        退栈回溯到上一行，即i--;
        移去该行已放置的皇后，以该皇后所在列的下一列作为当前列;
    }
}

Las Vegas 算法：

约定：

• $try[1\dots 8]表示第i个皇后放在(i,try[i])上$
• $try[1\dots k]称为k-promising$，当且仅当满足 k 皇后要求
• $\forall i!=j\in [1,k],try[i]-try[j]\notin \{i-j,0,j-i\}$

基本步骤：

1. 遍历改行所有的列位置是否可行，$\frac{1}{nb}$概率下选用该列
2. 如果有解则放，没解则退出

QueensLV(success){
    // 贪心的LV算法，所有皇后都是随机放置
    col, diag45, diag135 = {}; // 列、两个对角线初始化为空集
    k = 0; // 行号
    repeat
        nb = 0; // 计数器，nb值为(k+1)th皇后的open位置总数
     // 遍历列号，试探(k+1,i)是否安全
        for i=1 to 8 do {
            if (i!∈col) and (i-k-1!∈diag45) and (i+k+1!∈diag135) then {
                // 列i对(i+1)th皇后可用，但不马上放置
                nb = nb + 1;
                if uniform(1..nb)=1 then // 或许放在第i列
                 j = i;
            }
        }
        if(nb>0) then {
            // nb=0时无安全位置
            // 在所有nb个安全位置上，(k+1)th皇后选择位置j列的概率为1/nb
            k = k+1;
            try[k] = j;
            col = col ∪ {j};
            diag45 = diag45 ∪ {j-k};
            diag135 = diag135 ∪ {j+k};
        }
    until nb=0 or k=8; // 当找不到合适的位置，或者try是8-promising时，退出
    success = (nb>0);
}

算法 12 行，在所有可能的列位置上，选中某一列的概率都是$\frac{1}{nb}$，从最后一项往前倒推。

改进算法：联合回溯法和LV 算法，指定使用 LV 算法只确定前几行的位置。

...上述算法...
until nb=0 or k=stepVegas; // 已随机放好stepVegas个皇后
if nb>0 then
    backtrace(k, col, diag45, diag135, success);
else
    success = false;

2.3.2 模 p 平方根

$x\equiv y^2(modp),x\in [1,p-1],p为奇素数$，则

• x 为模 p 的二次剩余
• y 为 x 模 p 的平方根

定理：

• 任何一个模 p 的二次剩余有两个不同的平方根 $b,(p-b)$
• 1 到 p-1 之间的整数恰有一半时模 p 的二次剩余
• $\forall x\in [1,p-1],p为奇素数,有x^{(p-1)/2}\equiv \pm 1(modp)$
• $x是模p的二次剩余，当且仅当x^{(p-1)/2}\equiv 1(modp)$

如何判定x 是否为模 p 的二次剩余？计算$x^{\frac{p-1}{2}}(modp)$是否为 1。

如何计算x 模 p 的两个平方根？

• $ifp\equiv 3(mod4)$，则平方根为 $\pm x^{(p+1)/4}$

• $ifp\equiv 1(mod4)$，只能使用 LV 算法

例子：$p=53\equiv 1(mod4),x=7$，求 7 模 53 的平方根。

$$\begin{array}{rl}& \frac{p-1}{2}=26\\ & (2+\sqrt{7}{)}^{26}\equiv 0+41\sqrt{7}(mod53)\\ & 找到唯一的y,使得41y\equiv 1mod53,1\le y\le 52\\ & 使用Euclid算法,41\times 22\equiv 1(mod53)\\ & \therefore 22为一个平方根,53-22=31为另一个平方根\end{array}$$

基本步骤：

1. 随机取$a\in [1,p-1]$
2. 计算 c 和 d，$(a+\sqrt{x}{)}^{(p-1)/2}\equiv c+d\sqrt{x}(modp)$
3. 若$d=0$，则返回假
4. 若$c=0$，则找到 y，$dy\equiv 1(modp)$

rootLV(x, p, y, success){ // 计算y
    a = uniform(1..p-1); // 并不知道a取多少
    if a**2 % p == x % p then { // 可能性很小
        success = true; y =a;
    }else{
        计算c和d，使得0<=c,d<=p-1，(a+sqrt(x))**((p-1)/2) % p == c+d*sqrt(x) % p;
        if d==0 then success = false;
        else{ // c=0
            success = true;
            计算y使得，d*y % p == 1, 1<=y<=p-1 // 修改Euclid算法可求
        }
    }
}

算法成功的概率大于 0.5，因此平均调用两次即可求得 x 的平方根。

2.3.3 整数的因数分解

整数的素因数分解，$n=p_1^{m_1}{p}_2^{m_2}\cdots p_k^{m_k}$

朴素 split 算法：找到 n 的一个非平凡因数

split(n){
    // n是素数返回1，否则返回找到的n的最小非平凡因数
    for i=2 to [sqrt(n)] do
        if n % i == 0 then return i;
    return 1;
}

合数的二次剩余：上节的二次剩余要求 p 为奇素数，则恰有两个不同的平方根。若$n=pq,p和q为不同素数$，则二次剩余恰有4 个平方根。

Dixon 因数分解算法：

基本步骤：

1. 找到与 n 互素的整数 a 和 b，使得 $a^2\equiv b^2(modn)且a!\equiv \pm b(modn)$
2. 则 n 和 a+b 的最大公因子是一个非平凡因子，$x=gcd(n,a+b)$。

Dixon(n,x,success){ // 找合数n的某一非平凡因子
    if n是偶数 then {
        x = 2; success = true;
    }else{
        for i=2 to [log_{2}n] do {
            if n**(1/i) 是整数 then {
                x = n**(1/i); success = true; return;
            }
        }
        找到a, b，使得 a**2 % n == b**2 % n;
        if a % n == +-b % n then success = false;
        else {
            x = gcd(a+b, n); // 最大公因子
            success = true;
        }
    }
}

k-平滑：一个整数 x 的所有素因子均在前 k 个素数中。

确定 a 和 b 的取值：提前选定 n 和 k。

1. 随机选择$x\in [1,n-1]$。

   • 若 x 不与 n 互素，则找到了非平凡因子
   • 否则，$y=x^{2}modn$，若 y 是 k 平滑的，则将 x 和 y 的因数分解保存在表里。
   • 一直重复，直到选择了k+1 个互不相同的整数 x。

2. 在 k+1 个因式分解式中找到一个非空子集$\{y_1{y}_2\cdots y_k\}$，使得相应的因式分解的积中前 k 个素数的指数均为偶数（包含 0），如$y_1{y}_2{y}_4{y}_8=2^6{3}^4{5}^4{7}^{0}11^{2}13^{2}17^2$

3. 令$S=\{y_{s_1},y_{s_2},\cdots ,y_{s_k}\},a={\prod }_{y_i\in S}{x}_i,b=\sqrt{{\prod }_{y_i\in S}{y}_i}$，$ifa!\equiv \pm b(modn)$，则只需要求 a+b 和 n 的最大公因子即可。

时间分析：k 的取值将会影响 $x^{2}modn$是 k 平滑的可能性，以及因数分解 y 时的时间。通常取如下时间

$$\begin{gathered} L=e^{\sqrt{ln(n)\ast ln(ln(n))}} \\ k=\sqrt{L},期望时间O(L^2),成功概率至少0.5 \end{gathered}$$

2.4 Monte Carlo 算法

存在某些问题无法找到有效的算法获得正确解。MC 以高概率找到正确解。

约定：

• p-正确：一个 MC 算法以不小于 p 的概率返回一个正确的解
• 相容的、一致的：一个 MC 算法对同一实例返回相同的正确解。

多次调用同一个算法，选择出现次数最多的解，以增加一致的，p-正确算法成功的概率。

有偏算法：

• 偏真算法：MC 算法返回 true 时的解一定正确，只有返回 false 时才有可能产生错误的解。
• 偏$y_0$算法：算法返回$y_0$时总是正确的，返回非$y_0$时 p 概率正确。

重复调用一个一致的，p-正确的，偏$y_0$的 MC 算法 k 次，得到一个 $1-(1-p{)}^k$ -正确的算法。

2.4.1 主元素问题

一个具有 n 个元素的数组，若某一元素的个数大于$\frac{n}{2}$，则其为主元素。

判断 T 是否有主元素：随机设置一个 x，然后看看有多少个

maj(T){
    i = uniform(1..n);
    x = T[i];
    k = 0;
    for j=1 to n do
        if T[j] == x then
            k = k+1;
    return k>n/2;
}
偏真，0.5-正确的算法

重复调用降低错误率：

maj2(T){
    if maj(T) then return true; // 1次成功
    else return maj(T); // 调用2次
}
偏真，0.75-正确的算法

算法改进：控制算法出错概率小于$\epsilon >0$，应调用次数为$k=\lceil lg\frac{1}{\epsilon }\rceil$

// e 为错误概率
majMC(T, e){
    k = [lg(1/e)]; // 上取整
    for i=1 to k do
        if maj(T) then return true;
    return false;
}
// O(nlg(1/e))

2.4.2 素数测定

判定一个整数是否为素数，尚未找到有效的确定性算法或 LV 算法

简单的概率算法：

prime(n){
    d = uniform(2..[sqrt(n)]); // 下取整
    return (n mod d)!=0;
}

Fermat 小定理：$ifn是素数,则\forall a\in [1,n-1],有a^{n-1}modn=1$

变换命题：$if\exists a\in [1,n-1],使a^{n-1}modn!=1,则n不是素数$

素性测定算法：使用 Fermat 小定理，偏假的。即算法返回假，一定为假。

Fermat(n){
    a = uniform(1..n-1);
    if a**(n-1) mod n == 1 then return true; // 未必正确
    else return false; // 一定正确
}

伪素数和素性伪证据：符合 Fermat 小定理的合数，称为以 a 为底的伪素数，a 称为 n 的素性伪证据。

将 Fermat 测试重复多次，也不能降低误差。

强伪素数：n 是大于 4 的奇数，s 和 t 是整数，使得$n-1=2^{s}t,t为奇数$，集合$B(n)$满足如下条件：

$$\begin{array}{rl}& a\in B(n),2\le a\le n-2,且满足下述两个条件之一:\\ & 1.a^{t}modn=1\\ & 2.\exists 0\le i<s,a^{2^{i}t}modn=n-1\end{array}$$

• n 为素数，则 $\forall a\in [2,n-2],a\in B(n)$
• n 为合数，$ifa\in B(n)$，则称 n 为一个以 a 为底的强伪素数，a 为 n 素性的强伪证据。

Btest(a, n){
    // n为奇数，2<=a<=n-2, 返回true则代表a属于B(n)。则n为强伪素数或素数
    s=0; t=n-1; // t开始为偶数
    repeat
        s++;t/=2;
    until t mod 2 = 1; //n-1=(2**s)t, t为奇数
    x = a**t mod n;
    if x=1 or x=n-1 then return true; // 满足条件1或2
    for i=1 to s-1 do{
        x = x**2 mod n;
        if x=n-1 then return true; // 满足条件2
    }
    return false;
}
0.75-正确

强伪证据的数目比伪证据数目少很多。

$强伪证据\Rightarrow 伪证据$

Miller-Rabin 测试：0.75-正确，偏假的

MillRab(n){ // 奇n>4，返回真时表示素数，假时表示合数
    a = uniform(2..n-2);
    return Btest(a,n); // 测试n是否为强伪素数
}

RepeatMillRob：重复实验 k 次，$1-4^{-k}$-正确的 MC 算法

RepeatMillRob(n,k){
    for i=1 to k do
        if MillRob(n) == false then return false; // 一定是合数
    return true;
}

若给出出错概率不超过$\epsilon$，则重复次数为 $k=\lceil \frac{1}{2}lg\frac{1}{\epsilon }\rceil$

确定 n 素性时间为：$O(l{g}^{3}nlg\frac{1}{\epsilon })$

2.4.3 矩阵乘法验证

验证$矩阵AB=C$

设 $X_{1\times n}=(a_1,a_2,\cdots ,a_n),a_i\in \{0,1\}$，则问题转化为 $XAB=XC$

基本步骤：

1. 计算$XA$
2. 计算$XA$与$B$的乘积
3. 计算$XC$

GoodProduct(A,B,C,n){
    for i=1 to n do
        x[i] = uniform(0..1);
    if XAB=XC then return true;
    else return false;
}

偏假的，0.5-正确

返回假一定为假

改进算法：重复 k 次

RepeatGoodProduct(A,B,C,n,k){
    for i=1 to k do // 重复k次
        if GoodProduct(A,B,C,n) == false then return false;
    return true;
}

偏假的，$1-2^{-k}$-正确

给出错误概率：即$2^{-k}=\epsilon$

GP(A,B,C,n,e){
    k = [lg(1/e)]; // 上取整
    return RepeatGoodProduct(A,B,C,n,k);
}
// O(n**2log(1/e))

近似算法复习知识点

Contributors

• 三、近似算法
  • 3.1 NP-完全性理论
  • 3.2 相关问题总结
  • 3.3 近似算法
    • 3.3.1 多机调度问题
    • 3.3.2 装箱问题 BP
    • 3.3.3 旅行商问题 TSP

转载自 cnblogs/学科笔记/中科大-算法分析与设计-近似算法复习知识点.md at main · BamLubi/cnblogs 中科大-算法分析与设计-近似算法复习知识点 - 小陆斑比 - 博客园[TOC]

三、近似算法

3.1 NP-完全性理论

图灵机：

• 确定性图灵机 DTM：执行的动作唯一
• 非确定性图灵机 NTM：执行的动作有多个可选

P 类问题：$P=L:L能在多项式时间内被DTM接受$

用确定性算法在多项式时间内可解

多项式时间内可解的问题$=$P

NP 类问题：$P=L:L能在多项式时间内被NTM接受$

用非确定性算法在多项式时间内可解

多项式时间内可验证的问$=$NP

多一规约：$L_1和L_2是两个判定问题，实例I_2=f(I_1)$

$$\begin{gathered} \forall I\in U_1,I是L_1输出yes的实例\iff f(I)是L_2输出yes的实例 \\ L1{\le }_m{L}_2 \end{gathered}$$

多项式时间多一规约：$f$是多项式时间可计算的

NPC 问题：对于判定问题 q，满足$1)q\in NP;2)NP{\le }_m^{p}q;$

NP-hard 问题：对于判定问题 q，满足$2)NP{\le }_m^{p}q;$

$NPC⊑NP-hard$

解题思路：

• $一个问题不可判定\Rightarrow 该问题\notin NP\Rightarrow 该问题\notin NPC$
• 证明$q\in NPH$，找到$q^{\prime }\in NPC/NPH$，再将$q^{\prime }$多项式归约到$q$。
• 如果继续证明$q\in NP$，则$q\in NPC$
• NPC 问题：SAT 可满足性问题、最大独立集问题、背包问题、覆盖问题、路径问题
• NPH 问题：停机问题

规约策略：

• $X{\le }_{p}Y,Y{\le }_{p}X\Rightarrow X{\equiv }_{p}Y$，$最大独立集问题{\equiv }_p最小顶点覆盖问题$

• 特殊到一般，$最小顶点覆盖问题{\le }_p最小集合覆盖问题$

3.2 相关问题总结

1. 独立集问题(Independent-Set)：图的顶点集合的子集中，所有顶点两两没有边。
2. 团问题：图的顶点集合的子集中，所有顶点两两均有边。
3. 顶点覆盖问题(Vertex-Cover)：图的顶点集合的子集中，边集中至少有一个顶点在该子集中。
4. 集合覆盖问题(Set-Cover)：非空集合的若干非空子集合的并集等于原有集合。
5. 3-SAT 问题：**3-CNF(合取范式)**组成的布尔公式存在真值解。
6. 哈密尔顿圈问题：图中通过每一个顶点恰好一次的回路。

上述问题均是 NPC 的。

单源最短路径和欧拉环是 P 问题。

3.3 近似算法

三种放宽要求的可能性：

• 超多项式时间启发：存在一个伪多项式时间的算法，如背包问题。（缺点：只对弱 NPC 问题有效）
• 概率分析：不再要求问题的解满足所有输入实例。（缺点：选取一个特殊的输入分布不容易）
• 近似算法：不再要求总是找到最优解。设计一个算法找出所有情况下的次优解来解 NP-hard 问题、

近似解分类：

• 容易近似：背包问题、调度问题、装箱问题
• 中等难度：顶点覆盖问题、欧式 TSP 问题、Steiner Trees
• 难于近似：着色问题、TSP、Clique(团)

性能保证：在最优解和近似解之间建立某种联系。

绝对性能度量：绝对近似算法是优化问题的多项式时间近似算法 A，$\exists k>0$，使得

$$\forall I\in D,|A(I)-OPT(I)|\le k$$

含义：近似解和最优解相差某一小的常数。

对于大多数的 NPH 问题，不存在绝对近似算法，除非$P=NP$。

两种绝对近似算法：

• 图是否可以 3 着色：

  • G 为二部图，即可 2 着色
  • G 一定可以 4 着色，四色定理
  • $|A(G)-OPT(G)|\le 2$

• 图边着色最小颜色数：

  • 最大度 / 最大度+1
  • $|A(G)-OPT(G)|\le 1$

前提：已知最优解 或 值所在的小范围

对于大多数 NPH 问题，存在绝对近似算法当且仅当存在多项式精确算法。

反证不存在绝对近似算法：

• 背包问题，通过 Scaling 放大利润为 k+1 倍，再算解的值
• 最大团问题，构造$G^{k+1}$

相对性能度量：算法 A 在一个输入实例上的性能比为

$$\begin{gathered} R_A(I)=\{\begin{array}{l}\frac{A(I)}{OPT(I)},最小化问题\\ \frac{OPT(I)}{A(I)},最大化问题\end{array} \\ 1\le R_A(I)\le 1+\epsilon ,A为(1+\epsilon )-近似算法 \end{gathered}$$

含义：近似解和最优解比值为某一小的常数。

• 绝对性能比：$R_A=inf\{r|R_A(I)\le r,\forall I\in D\}=性能比上界集合中的最小值$
• 渐近性能比：$R_A^{\infty }=inf\{r|R_A(I)\le r,\forall I\in D且OPT(I)\ge N\}=最优解要足够大$
• 最佳可达性能比：$R_{MIN}(\Pi )=inf\{r\ge 1|\exists 多项式时间算法A,R_A^{\infty }\le r\}$
  • $\{\begin{array}{l}1,最容易近似\\ 有界,△TSP问题\\ 无界,难于近似\end{array}$

$1\le R_A^{\infty }\le R_A<\infty$

对于有 Scaling 性质的问题，$R_A^{\infty }=R_A$

很多问题找不到绝对近似算法。

有些问题找不到有界性能比近似算法。

3.3.1 多机调度问题

List 调度算法：n 个作业依次分配给当前负载最小的机器。

$\frac{A(I)}{OPT(I)}\le 2-\frac{1}{m}$

证明上界：

$$>\begin{array}{rl}>& A(I)=L,作业运行时间最长\\ >& OPT(I)\ge \frac{\sum P_i}{m}\ge \frac{m(L-P_{last})+P_{last}}{m}\\ >& \Rightarrow OPT(I)\ge A(I)+\frac{1-m}{m}{P}_{last}\\ >& \because OPT(I)\ge P_{last}\\ >& \therefore 1\ge \frac{A(I)}{OPT(I)}+(\frac{1}{m}-1)\frac{P_{last}}{OPT(I)}\\ >& \therefore \frac{A(I)}{OPT(I)}\le (2-\frac{1}{m})\frac{P_{last}}{OPT(I)}\le 2-\frac{1}{m}>\end{array}>$$

证明紧确界：有$n=m(m-1)+1$个作业

$$>\begin{array}{rl}>& P_1=\cdots =P_{n-1}=1,P_n=m\\ >& OPT(I)=前n-1个机器每个运行m个作业+第n个机器运行P_n=m\\ >& A(I)=前n个机器每个运行m-1个作业+第1个机器运行P_n=2m-1\\ >& R_A=2-\frac{1}{m}>\end{array}>$$

LPT 调度算法：将作业递序排列，然后 List 策略调度。

$\frac{A(I)}{OPT(I)}\le \frac{4}{3}-\frac{1}{3m}$

3.3.2 装箱问题 BP

n 件物品，每件物品在单位大小之内，按某种策略装入单位大小的箱子中，令箱子数最小。

首次适应算法 FF

$R_{FF}(I)\le 2$，$R_{FF}^{\infty }=1.7$

证明：

最多只有一个箱子是大于半空的。

物品的总大小至少为总箱子的一半，$[\sum S_i]\ge \frac{1}{2}FF(I)$。

最优解至少为物品的总大小，$OPT(I)\ge [\sum S_i]$。

$R_{FF}(I)=2$

递减首次适应 FFD

$R_{FFD}\ge 1.5$，$R_{FFD}^{\infty }=\frac{11}{9}$

3.3.3 旅行商问题 TSP

求最短哈密顿回路 HC，访问所有顶点一次的回路。

这里研究$△TSP$，即输入满足三角不等式

近邻法 NN：从当前顶点访问最近尚未访问的顶点，一次构造哈密尔顿圈 HC。$R_{NN}^{\infty }=\theta (lgn)$

MST 启发：先找一个欧拉环 ET，然后再”Short-Cut“获得哈密尔顿圈。

$R_{NN}^{\infty }=2$

有欧拉环，当且仅当图连通且顶点度数均为偶数。

MST：

1. 构造最小生成树
2. 每条边复制一个
3. 找到欧拉圈
4. 短路欧拉路的方法构造 HC，即遇到重复顶点就跳过。

CH 启发：不需要将所有边都复制，只在每对奇度顶点之间连线。

$R_{CH}^{\infty }=1.5$

CH：

1. 构造最小生成树
2. 每对奇度顶点之间连线
3. 找到欧拉圈
4. 短路欧拉路的方法构造 HC，即遇到重复顶点就跳过。

COMP6002P组合数学

Contributors

• 分类

分类

• 习题答案
  • ch02排列与组合
  • ch03二项式系数
  • ch04容斥原理
  • ch05生成函数
  • ch06递推关系
  • ch08Polya计数理论

ch02排列与组合

Contributors

• 1. 计算50！的尾部有多少个零？
• *2.比5400大的四位整数中，数字2，7不出现，且各位数字不同的整数由多少个?
• *3.12个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？
• 4. 有颜色不同的四盏灯。
  • (1) 把它们按不同的次序全部挂在灯杆上表示信号，共有多少种不同的信号？
  • (2) 每次使用一盏、二盏、三盏或四盏灯按一定的次序挂在灯杆上表示信号，共有多少种不同的信号？
  • (3) 在(2)中，如果信号与灯的次序无关，共有多少种不同的信号？
• 5. 现在有100件产品，从中任意抽取3件。
  • (1)共有多少种抽法？
  • (2) 如果100件产品中有2件次品，那么抽出的产品中至少有一件是次品的概率是多少？
  • (3) 如果100件产品中有2件次品，那么抽出的产品中恰好有一件是次品的概率是多少？
• 6. 把$q$个负号和$p$个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有$C_{p+1}^q$种。
• 7. 8个棋子大小相同，其中5个红的，3个蓝的，把它们放在$8\times 8$的棋盘上，每行每列只能放一个，问有多少种放法？若放在$12\times 12$的棋盘上，结果如何？
• 8. 有纪念章4枚、纪念册6本，赠送给10位同学，每人得一件，共有多少种不同的送法?
• *9.
  • (1)从整数1，2，…,100中选出两个数，使得它们的差正好是7，有多少种不同的选法?
  • (2)如果要求两数之差小于等于7，又有多少种不同的选法？（注意：应该是两数之差的绝对值小于等于7更加准确地反映出题意）
• *10.试求不定方程$x_1+x_2+\cdot +x_8=40$满足 $x_i\ge i(i=1,2,\cdot ,8)$的整数解个数？
• 11. 在一次选举中，甲、乙分别得到a张和b张票(a>b)，将全部a+b张选票按某种顺序排列，依次计票时甲所得的票数总是比乙多.问这种排列方法有多少种？
• 12. n个不同的字符顺序进栈恰一次，问有多少种不同的出栈方式？
• *13. 计数(0, 0)点到(n, n)点的不穿过直线y=x的非降落路径数.
• 14. 有n个不同的整数，从中取出两组来，要求第一组的最小数大于第二组里的最大数，问有多少种方案？
• 15. 试求n个完全一样的骰子能掷出多少种不同的点数？
• 16.凸10边形的任意3条对角线不共点，试求该凸10边形的对角线交于多少个点？又把所有的对角线分割成多少段?
• 17. 设 $n=p_1^{\alpha 1}{p}_2^{\alpha 2}\cdot p_l^{\alpha l}$,其中$p_1,p_2,\dots p_l$是l个不同素数，试求能整除n的正整数数目。
• 18. 将52张牌平均分给4个人，问每个人有一个5张牌的同花顺的概率是多少？
• 19.取定空间中的25个点，其中任意4点均不共面，问它们能决定多少个三角形？又能决定多少个四面体？
• 20. 考虑集合$1,2,\cdots ,n+1$的非空子集.
  • (1)证明最大元素恰好是j的子集数为$2^{j-1}$.
  • (2)利用(1)的结论证明 $1+2+2^2+\cdots +2^n=2^{n+1}-1$
• 21. 从整数1,2,…1000中选取3个数，使得它们的和正好被4整除，问有多少种选法？
• 22.
  • (1)在由5个0和4个1组成的字符串中，出现01或10的总的次数为4的字符串有多少个？
  • (2)在由m个0和n个1组成的字符串中，出现01或10的总的次数为k的字符串有多少个?
• *23. 5 封不同的信用通信通道传送，在两封信之间至少要放3个空格，一共要加入15个空格，问有多少种方法？
• 24. 将a,b.c,d,e,f,g,h排成一行，要求a在b的左侧，b在c的左侧，问有多少种排法?
• 25.从1至100的整数中不重复的选取两个数组成有序对(x, y)，使得x与y的乘积xy不能被3整除，
• 26. 在$m\times n$的棋盘中选取两个相邻的方格（即有一条公共边的方格）有多少种不同的选取方法？
• 27. 某电影院票房前有2n个人排队，每人欲购买一张5元的电影票.在这些人中，有n个人，每人有一张5元钞票，其余每人有一张10元钞票，而票房在卖票前无任何钞票，问使得每个人都能顺利地买到电影票的排队方式有多少种？
• 28.证明下列组合恒等式：
  • （1） ${\sum }_{k=0}^n(-1{)}^k\cdot k^2\cdot C_n^k=0$
  • （2）${\sum }_{k=0}^n=\frac{1}{(k+1)(k+2}{C}_n^k=\frac{2^{n+2}-n-3}{(n+1)(n+2)}$
  • （3）${\sum }_{k=0}^n\frac{k+2}{k+1}{C}_n^k=\frac{(n+3)\cdot 2^n-1}{n+1}$
  • （4）${\sum }_{k=0}^n(k+1{)}^2{C}_n^k=2^{n-2}\cdot (n^2+5n+4)$
  • （5） ${\sum }_{k=0}^n\frac{1}{k+2}\cdot C_n^k=\frac{n\cdot 2^{n+1}+1}{(n+1)(n+2)}$
  • （6）${\sum }_{k=0}^n{C}_{2n}^k=2^{2n-1}+\frac{1}{2}{C}_{2n}^n$
• 29. 以 $h_m(n)$表示用m种颜色去涂$2\times n$棋盘，使得相邻格子异色的涂色数，证明$h_m(n)=(m^2-3m+3{)}^{n-1}\cdot m\cdot (m-1)$
• 30. 上题中，若以 $h_m^{\prime }(n)$表示m种颜色去涂 $2\times n$ 棋盘，使得相邻格子异色且每种颜色至少使用一次的涂色方案，求 $h_m^{\prime }(n)$ 的计数公式.
• 31. 有20根完全相同的木棍从左到右竖立成一行，占据20个位置。要从中选出6根。
  • (1) 有多少种选择?
  • (2) 如果选出的木棍中没有两根是相邻的，又有多少种选择？
  • (3) 如果在所选出的每一对木棍之间必须至少有两根棍，有多少中选择？

转载自liuzengh/combinatorial-mathematics

1. 计算50！的尾部有多少个零？

编程题 Leetcode 172 Factorial Trailing Zeroes

def fun(n):
    if n<5:
        return 0
    return n//5 + fun(n//5)
fun(50)

一种有12个零。 注意到只能由$2\times 5$产生0(而如果一个数本身含有0， 一定是能被2和5整除的。)

{2，5}，{12,15}，{32,35}, {42,45}, {4,25}, 10, {20,50} 30, 40

*2.比5400大的四位整数中，数字2，7不出现，且各位数字不同的整数由多少个?

加法原则，如果首位大于5则，可以为6，8， 9, 于是有 $3\times 7\times 6\times 5$。如果首位为5，则次高位可以为4，6， 8， 9,于是有$1\times 4\times 6\times 5$，所以总的个数为: $3\times 7\times 6\times 5+1\times 4\times 6\times 5=750$

*3.12个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？

减法原则。$\frac{12!}{12}-2\frac{11!}{11}=9\times 10!$

4. 有颜色不同的四盏灯。

(1) 把它们按不同的次序全部挂在灯杆上表示信号，共有多少种不同的信号？

$A_4^4=24$

(2) 每次使用一盏、二盏、三盏或四盏灯按一定的次序挂在灯杆上表示信号，共有多少种不同的信号？

$A_4^1+A_4^2+A_4^3+A_4^4=64$

(3) 在(2)中，如果信号与灯的次序无关，共有多少种不同的信号？

$C_4^1+C_4^2+C_4^3+C_4^4=2^4-1=15$

5. 现在有100件产品，从中任意抽取3件。

(1)共有多少种抽法？

$C_{100}^3=161700$

(2) 如果100件产品中有2件次品，那么抽出的产品中至少有一件是次品的概率是多少？

$1-\frac{C_{97}^3}{C_{100}^3}$

(3) 如果100件产品中有2件次品，那么抽出的产品中恰好有一件是次品的概率是多少？

$\frac{C_3^1{C}_{97}^2}{C_{100}^3}$

6. 把$q$个负号和$p$个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有$C_{p+1}^q$种。

证明:先把$p$个正号排在一条直线上，那么包括两头在内，留出了$p+1$个空位置。由于负号不能相邻，所以原问题等价于从这$p+1$个空位置中选择$q$个位置把负号放入其中，则总的个数为：$C_{p+1}^q$

7. 8个棋子大小相同，其中5个红的，3个蓝的，把它们放在$8\times 8$的棋盘上，每行每列只能放一个，问有多少种放法？若放在$12\times 12$的棋盘上，结果如何？

参考2.4节例6

编程题Leetcode 51.N-Queens, 52.N-Queens II, 36-Valid Sudoku, 37.SudoKu Solver 暴力枚举；回溯法

先选位置再选颜色。

对于$8\times 8$的棋盘，每行都必须要放置一个棋子，可以先固定行，然后第1个棋子有8种列坐标可选，第2个棋子有7种列坐标可选，依次下去，总的选法数为8！，然后从8个棋子种选择5个着色为红色（这一步也可以看成计算多重集合$M=\{5\cdot R,3\cdot B\}$上的全排列个数）。$8!C_8^5=\frac{(8!{)}^2}{5!3!}$

如果是$12\times 12$的棋盘则先从12行中选择8行（无序），在从12列中排列8列(有序)，然后选择5个棋子着为红色即可 $C_{12}^8{A}_{12}^8{C}_8^5=\frac{(12!{)}^2}{3!(4!{)}^{2}5!}$

8. 有纪念章4枚、纪念册6本，赠送给10位同学，每人得一件，共有多少种不同的送法?

解法一：从10位同学中选择4位送纪念章，那么后剩余6位一定是送纪念册咯。$C_{10}^4$

解放二：匹配问题，可以看成给10个人打上送纪念章或纪念册的标签，那么就是多重集合$M=\{4\cdot 0,6\cdot 1\}$的全排列。（0，1分别对应纪念章和纪念册）

*9.

(1)从整数1，2，…,100中选出两个数，使得它们的差正好是7，有多少种不同的选法?

可以取两个数$x,y$，为不失一般性不妨取 $x<y$，则有$y=x+7$，由于$1\le x\le 100,1\le y\le 100$,则可以取$(1,8),(2,9),\dots ,(93,100)$.则一种有93种取法

(2)如果要求两数之差小于等于7，又有多少种不同的选法？（注意：应该是两数之差的绝对值小于等于7更加准确地反映出题意）

可以取两个数$x,y$，为不失一般性不妨取 $x<y$，则有$y=x+7$，由于$1\le x\le 100,1\le y\le 100$， 当x取1时，y可以取{2，3，4，5，6，7，8}，可以类推到x取到93的情况，当x取{94，95，… ,99, 100},y只需要取比x大的数即可。总的选法为：$93\times 7+{\sum }_{i=94}^{100}(100-i)=672$

*10.试求不定方程$x_1+x_2+\cdot +x_8=40$满足 $x_i\ge i(i=1,2,\cdot ,8)$的整数解个数？

令 $y_i=x_i-i$,则${\sum }_{i=1}^8{y}_i={\sum }_{i=1}^8{x}_i-{\sum }_{i=1}^8={\sum }_{i=1}^8{x}_i-36=40-36=4$

$C_{8+4-1}^{8-1}=C_{11}^4=330$

11. 在一次选举中，甲、乙分别得到a张和b张票(a>b)，将全部a+b张选票按某种顺序排列，依次计票时甲所得的票数总是比乙多.问这种排列方法有多少种？

该问题与第12题是等价的。相当于共有a个元素进栈，那么需要出栈b个元素一共有多少种不同的可能。 把1当成进栈，0当成出栈，那么共有（a+b）个移动次序，并满足任意时刻，进栈数大于出栈数（a>b）。

该问题与13题是等价的。相当于于计数(0, 0)点到(a, b)点的不穿过直线y=x的非降落路径数。（只考虑直线y=x下三角的情况）设往右走对应于甲的票，往上走对应于乙的票，那么不穿过直线y=x就保证了依次计票时甲所得得票数总是比乙多。

方法一：可以转换成13题的几何形式

方法二：写成递归函数，Catalan数

$C_{a+b-2}^{a-1}-C_{a+b-2}^a$

12. n个不同的字符顺序进栈恰一次，问有多少种不同的出栈方式？

参考7.2节Catalan数

编程题 Leetcode 946.Validate Stack Sequences 模拟

设f(n)为n个不同字符对应的计数。$f(n)=\frac{1}{n}{C}_{2n-2}^{n-1}$ $$f(n)=\sum _{i=0}^{n-1}f(i)f(n-i+1),f(0)=1,f(1)=1$$

*13. 计数(0, 0)点到(n, n)点的不穿过直线y=x的非降落路径数.

参考2.4节例3，7.2节例3

编程题 Leetcode 62.Unique Paths, 63 Unique Paths II 写成递推方程，用递归或者动态方程计算；用组合数表达出总的次数，转而编程计算组合数

从可以先从(0,0)到达(0, 1)或者(1, 0)，这两个点到(n,n)而不穿过$y=x$的非降落路径数是相等的。于是可以考虑从(1,0)到(n，n)不穿过直线$y=x$的非降落路径数，由于不穿过$y=x$，那么必定是要经过点(n, n-1)。

从(1,0)到(n,n-1)的非降落路径数为：$C_{2n-2}^{n-1}$。

从(1, 0)到(n, n-1)穿过直线$y=x$的非降落路径和从(0, 1)到(n, n-1)的非降落路径是对称的等于：$C_{2n-2}^n$

于是从点(0, 0)点到(n, n)点的不穿过直线y=x的非降落路径数为： $$2(C_{2n-2}^{n-1}-C_{2n-2}^n)=2(\frac{(2n-2)!}{n!(n-1)!}-\frac{(2n-2)!}{n!(n-2)!})=2\frac{(2n-2)!}{n!(n-1)!}=\frac{2}{n}{C}_{2n-2}^{n-1}$$

14. 有n个不同的整数，从中取出两组来，要求第一组的最小数大于第二组里的最大数，问有多少种方案？

可以把这n个数一一映射到集合{1, 2, …, n}上。依次取确定第二组里最大的数为n，n-1，…, 1;相应的第二组可以从剩余的n-1, n-2, …. 0个数中任意取整数构成一个组。则有: $$f(n)=\sum _{i=1}^n{2}^{i-1}\ast (2^{n-i}-1)=n{2}^{n-1}-2^n+1$$

15. 试求n个完全一样的骰子能掷出多少种不同的点数？

一个骰子有6个面，点数依次为1,2,3,4, 5, 6。则$f(n)={\sum }_i^n{x}_i,0\le x_i\le 6$, 计算函数f(n)值域的大小，为 $6^n$。

16.凸10边形的任意3条对角线不共点，试求该凸10边形的对角线交于多少个点？又把所有的对角线分割成多少段?

相交的点数：$C_n^4$

每条对角线分割成的段数：$\frac{n(1+{\sum }_{i=3}^{n-1}(i-2)(n-i))}{2}$

17. 设 $n=p_1^{\alpha 1}{p}_2^{\alpha 2}\cdot p_l^{\alpha l}$,其中$p_1,p_2,\dots p_l$是l个不同素数，试求能整除n的正整数数目。

素数分解定理，确保了任意整数能够被分解为多个素数的乘积形式。使用乘法法则，总的数目为： $$\prod _{i=1}^l(1+{\alpha }_i)$$

18. 将52张牌平均分给4个人，问每个人有一个5张牌的同花顺的概率是多少？

2： {3， 4， 5， 6， 7}, {4， 5， 6， 7， 8}， {5， 6， 7， 8， 9}

1： {6， 7， 8， 9， 10}， {7， 8， 9， 10 ，J}

19.取定空间中的25个点，其中任意4点均不共面，问它们能决定多少个三角形？又能决定多少个四面体？

三角形个数$C_{25}^3$, 四面体个数$C_{25}^4$。

20. 考虑集合$1,2,\cdots ,n+1$的非空子集.

(1)证明最大元素恰好是j的子集数为$2^{j-1}$.

如果集合A中的最大元素为j,那么A还可能包含$j-1,j-2,\cdots ,1$的数。利用乘法法则，个数为$2^{j-1}$

(2)利用(1)的结论证明 $1+2+2^2+\cdots +2^n=2^{n+1}-1$

根据最大元素的不同可以把集合$1,2,\cdots ,n+1$划分为n+1个不互斥的子集,但是不包含空集。从而有: $$\sum _{j=1}^{n+1}{2}^{j-1}=2^{n+1}-1$$

21. 从整数1,2,…1000中选取3个数，使得它们的和正好被4整除，问有多少种选法？

按对4取模的结果{0, 1, 2, 3}把这1000个数划分为4个等价类，代表元分别为0，1，2，3,每个类的元素个数相等。则有{013, 112, 220, 332, 000}，总的选法为: $250^3+250C_{250}^2\times 3+C_{250}^3$

22.

(1)在由5个0和4个1组成的字符串中，出现01或10的总的次数为4的字符串有多少个？

(2)在由m个0和n个1组成的字符串中，出现01或10的总的次数为k的字符串有多少个?

*23. 5 封不同的信用通信通道传送，在两封信之间至少要放3个空格，一共要加入15个空格，问有多少种方法？

如果第1封信之前和第5封信之后允许放置空格，则$x_1+x_2+x_3+x_4+x_5+x_6=15$, 其中$0\le x_1,3\le x_2,3\le x_3,3\le x_4,3\le x_5,0\le x_6$。等价于 ${\sum }_{i=1}^6{y}_i=3$, 其中$y_1=x_1,y_6=x_6,y_i=x_i-3(2\le i\le 5),0\le y_i$。则总的次数为：$A_5^5{C}_8^3=6720$

24. 将a,b.c,d,e,f,g,h排成一行，要求a在b的左侧，b在c的左侧，问有多少种排法?

设n为字母的个数，根据b所在的位置可以为$2，3，\cdots ,n-1$ $$\sum _{i=1}^{n-1}{A}_i^i{A}_{n-i-1}^{n-i-1}$$

25.从1至100的整数中不重复的选取两个数组成有序对(x, y)，使得x与y的乘积xy不能被3整除，

按对3取模的结果{0, 1, 2}把这100个数划分为3个等价类代表元分别为0，1，2，三个类的元素个数分别为：33， 34， 33。不能被3整除的取法为11， 12，22。总的个数为: $2\times (C_{34}^2+C_{34}^1{C}_{33}^1+C_{33}^2)$

26. 在$m\times n$的棋盘中选取两个相邻的方格（即有一条公共边的方格）有多少种不同的选取方法？

从$(i,j)$可以到$(i+1,j),(i,j+1)$， 总的选取方法为：$m\times (n-1)+n\times (m-1)$

27. 某电影院票房前有2n个人排队，每人欲购买一张5元的电影票.在这些人中，有n个人，每人有一张5元钞票，其余每人有一张10元钞票，而票房在卖票前无任何钞票，问使得每个人都能顺利地买到电影票的排队方式有多少种？

思路和题11，12，13类似。从前往后计数，拥有5元钞票的人的个数必须大于等于10人钞票的人数；同时要考虑到每个人是不同的物体。

$$n!n!\frac{1}{n}{C}_{2n-2}^{n-1}$$

28.证明下列组合恒等式：

（1） ${\sum }_{k=0}^n(-1{)}^k\cdot k^2\cdot C_n^k=0$

怎么看着像卷积公式

（2）${\sum }_{k=0}^n=\frac{1}{(k+1)(k+2}{C}_n^k=\frac{2^{n+2}-n-3}{(n+1)(n+2)}$

（3）${\sum }_{k=0}^n\frac{k+2}{k+1}{C}_n^k=\frac{(n+3)\cdot 2^n-1}{n+1}$

（4）${\sum }_{k=0}^n(k+1{)}^2{C}_n^k=2^{n-2}\cdot (n^2+5n+4)$

（5） ${\sum }_{k=0}^n\frac{1}{k+2}\cdot C_n^k=\frac{n\cdot 2^{n+1}+1}{(n+1)(n+2)}$