斯坦福CS109面向计算机科学的概率论讲义资源-CSDN文库

课程资源

需积分: 5 102 浏览量 2024-02-02 22:51:53 上传评论收藏 3.75MB PDF 举报

资源推荐

资源详情

资源评论

克里斯·皮奇讲座讲义#1

CS109 2017年9月25日

计数

基于Mehran Sahami的讲义

尽管你可能在三岁时对计数的概念有了相当好的理解，但事实证明，你必须等到现在才

学会真正的计数。你现在很高兴你选了这门课吧？但说真的，在下面我们介绍一些与计

数相关的性质，这些性质在将来可能对你有帮助。

求和法则

计数的求和法则：如果一个实验的结果可以是m个结果之一，也可以是n个结果之一，其

中m个结果集中的任何一个结果都不同于n个结果集中的任何一个结果，则实验的可能结

果有m + n个。

使用集合符号重写，求和法则表明，如果一个实验的结果可以从集合A或集合B中选择，

其中|A| = m，|B| = n，并且A与B的交集为空集，则实验的结果数为|A| + |B| = m + n。

例子1

问题：你正在运行一个在线社交网络应用程序，它的分布式服务器存放在两个不同的数

据中心，一个在旧金山，另一个在波士顿。旧金山数据中心有100台服务器，波士顿数据

中心有50台服务器。如果发送一个服务器请求到应用程序，它可能被路由到多大的服务

器集合中？

解决方案：由于请求可以发送到任何一个数据中心，并且两个数据中心中的机器都不相

同，所以使用计数的求和规则。根据这个规则，我们知道请求可能被路由到任何一个150

台服务器中（= 100 + 50）.

乘法规则

计数的乘法规则：如果一个实验有两个部分，第一部分可能有m个结果，第二部分可能有

n个结果，无论第一部分的结果如何，实验的总结果数为mn。

使用集合符号重写，乘法法则表明，如果一个由两个部分组成的实验在第一部分中有来

自集合A的结果，其中|A|=m，并且在第二部分中有来自集合B的结果（不论第一部分的结

果如何），其中|B|=n，则实验的总结果数为|A| |B|=mn。

请注意，计数的乘法法则与罗斯教材中给出的"计数的基本原理"非常相似。

例子2

问题：投掷两个6面骰子，面上编号为1到6。投掷的可能结果有多少种？

- 2 -

解决方案：请注意，我们关心的不是两个骰子的总值，而是所有投掷结果的集合。由于

第一个骰子可以有6个可能的值，而第二个骰子也可以有6个可能的值（不论第一个骰子

上出现了什么），因此潜在结果的总数为36（= 6 * 6）。以下是可能的结果的显式列表，

表示骰子对上的值：(1,

(1, 2) (1, 3) (1, 4) (1, 5) (1, 6)

(2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6)

(3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6)

(4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6)

(5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6)

(6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6)

例子3

问题：考虑一个具有100个桶的哈希表。两个任意的字符串独立地

进行哈希并添加到表中。有多少种可能的方式可以将字符串存储在

表中？

解决方案：每个字符串可以哈希到100个桶中的一个。由于哈希第一个

字符串的结果不会影响第二个字符串的哈希，所以两个

字符串可以以100 * 100 = 10,000种方式存储在哈希表中。

包含-排除原理

包含-排除原理：如果一个实验的结果可以从集合A

或集合B中选择，并且集合A和B可能有重叠（即A ÇB = Æ不一定成立），

那么实验的结果数为|A ÈB| = |A| + |B| - |A Ç B|。

请注意，包含-排除原理推广了任意集合A和B的求和计数规则。在A ÇB = Æ的情况下，

包含-排除原理与求和计数规则得到相同的结果，因为|Æ| = 0。

例子4

问题：通过网络发送一个8位字符串（一个字节）。接收方能够识别的有效字符串要么以

01开头，要么以10结尾。有多少这样的字符串？

解决方案：与接收方的要求匹配的潜在位字符串可以是以01开头的64个字符串（因为最

后6位未指定，允许有2

= 64种可能性），也可以是以10结尾的64个字符串（因为前6位未

指定）。当然，这两个集合有重叠，因为以01开头且以10结尾的字符串同时属于两个集

合。有2

=16个这样的字符串（因为中间4位可以是任意的）。将这个描述转化为相应的

集合表示，我们有：|A| = 64，|B| = 64，以及|A ÇB| = 16，所以根据包含-排除原理，有64

+ 64 –16 =112个与指定接收方要求匹配的字符串。

1 “die”是单数形式的“dice”（复数形式）的词。

克里斯·皮奇讲座讲义#2

CS109 2017年9月26日

组合数学

基于Chris和Mehran Sahami的例子

正如我们上节课提到的，"计数"中提出的思想是概率的核心。计数就像房子的基础（房

子是我们将在CS109中做的所有伟大事物，如机器学习）。房子很棒。另一方面，基础基

本上只是一个洞里的混凝土。但是不要建造没有基础的房子。相信我。

排列组合

排列规则：排列是n个不同对象的有序排列。这些对象可以以n x (n –1) x (n –2) x ... x 2 x 1

= n!种方式进行排列。

如果你在对一些不同对象的子集进行排列，或者一些对象是相同的，那么情况会稍有不

同。我们很快就会处理这些情况！

例子1

第一部分：iPhone有4位数字密码。如果屏幕上有4个数字上的污点。

有多少个不同的密码可能？

解决方案：由于密码的顺序很重要，我们应该使用排列。由于恰好有四个污点，我们知

道每个数字都是不同的。因此，我们可以使用排列公式：4！= 24

第二部分：如果屏幕上有3个数字上的污点呢？

解决方案：三个数字中有一个重复，但不知道是哪一个。通过制作三种情况（每种

情况具有相同数量的排列）来解决这个问题。让A、B、C代表3个数字：A B

C的4！种排列

但需要消除C的排列组合过多计数

3 x [ 4! / (2! 1! 1!) ] = 3 x 12 = 36

第C部分：如果屏幕上有2个数字上有2个污点怎么办？

解决方案：有两种可能性，2个数字各使用两次或者2个数字中的1个数字使用3次，

其他数字使用1次。

[4! / (2! 2!)] + 2 x [ 4! / (3! 1!) ] = 6 + (2 x 4) = 6 + 8 = 14

例子2

回顾一下二叉搜索树（BST）的定义，它是一棵满足以下三个属性的二叉树，对于树中的

每个节点n都成立：

1. n的值大于其左子树中的所有值。

2. 节点n的值小于其右子树中的所有值。

3. 节点n的左子树和右子树都是二叉搜索树。

剩余70页未读，继续阅读

评论收藏

内容反馈

绝不原创的飞龙

粉丝: 1w+
资源: 1091

斯坦福 CS109 面向计算机科学的概率论讲义

最新资源

斯坦福 CS109 面向计算机科学的概率论讲义

张伟+概率论讲义

张伟老师的概率论讲义

曹显兵.概率论讲义.doc

高等概率论讲义（港中文）.pdf

整理的 概率论（Kira张翀）讲义.pdf

概率论基础讲义内部讲义ppt

清华大学电子系概率论讲义

概率论讲义

【高斯课堂】概率论与数理统计 讲义笔记及练习题.zip

曹显兵.概率论讲义打印版.doc

北京大学概率论课件讲义习题2008

概率论与数理统计讲义

《概率论与数理统计》讲义笔记【高斯课堂】.pdf

2011新东方概率论基础讲义

概率论 美国经典讲义

ChatGPT教程（终极版）最全整理

博客中Kmeans以及FCM算法数据（免积分）

神经网络回归预测--气温数据集

hugging face的models-openai-clip-vit-large-patch14文件夹

XGBoost+LightGBM+LSTM-光伏发电量预测

Mathwork+Matlab+编程手册

Stable-Diffusion WEBUI 简体中文语言包（2023.05.30更新）

中文短信数据集-带标签

时间序列预测模型实战案例(Xgboost)(Python)(机器学习)包括时间序列预测和时间序列分类，点击即可运行！

亚博K210模型训练部署

Plecs电力电子仿真PLECS41.64 电力系统仿真软件免安装版本

机器学习期末复习题及答案

基于鲸鱼优化算法优化VMD参数试看效果代码(目标函数为样本熵)

r人工智能的概要介绍与分析

最新资源

整理的概率论（Kira张翀）讲义.pdf

【高斯课堂】概率论与数理统计讲义笔记及练习题.zip

概率论美国经典讲义