https://www.youtube.com/playlist?list=PLu0nzW8Es1x0Ivn-757Za_ps090FJxOPd
教授问好大家,感谢大家参加这门离散数学与概率论课程。问是否有学生还在等待名单,是否有人还没被批准进课。
这门课程将通过屏幕录制分享,使得学生在两三天后就能获得课堂录音。同时将课程上传到edx平台,使任何人都能在线学习。目前课堂与在线课程可以互通,在测试期学生可以同时参与课堂与在线测试与作业,帮助优化在线课程。
这门课将着重将简单而深远的离散数学原理应用于重要的工程计算机科学领域,比如人工智能、系统、安全、通信等。每周学习一个主题后,都将给出其在这些领域中的应用实例。
教授希望减轻学习胆怯的学生。这门课与过去课程不同,它将强调解决问题的技巧,不是为数学而数学。许多问题具有谜题的性质。此外,这门课将培养解决问题的能力,这对求职也很重要。
教授提出一个用两个沙漏实现9分钟的题目,给学生思考时间。其后学生提出了几种答案,都很有想象力但不是正确答案。教授表示都值得喝彩,然后继续征求正确答案。
量词用来描述命题的通用性,如“对每个自然数”或“存在整数”。
命题是指可以是真或假的语句。逻辑连接词如“并且”“或”可以连接多个命题。条件句“如果P则Q”其实际含义是P和Q在真值表上满足某种关系。
条件句“如果P则Q”其逆句“如果不Q则不P”总是与条件句等价。而反句“如果Q则P”可能与条件句不等价。
考虑表达式“对每个自然数n,n平方加n加41是一个质数”。通过计算得知在n等于41时,该表达式不成立,因此这个全称定理不正确。
使用全称量词“对每个X”或存在量词“存在X”可以把语意表达成逻辑符号形式。例如把“没有人去派对不修边幅”表达为“对每个人X,如果X去派对,则X修边幅”。把语句转化为其逆真值或取反形式也是可能的。
素数的定义:如果正整数n大于1,且只有1和它本身能整除它,则n为素数。
常见的素数有:2,3,5,7,11,13等。
该定理指出:在正整数中有无限多个素数。
假设正整数中只有有限个素数:{p1,p2,…,pk}
设Q=p1×p2×…×pk,将Q加1得Q+1
利用每个数都有素数因子这个定律,可以得出Q+1也有素数因子。但Q+1不在原始素数列表内,产生矛盾。
所以原假设不成立,正整数中必有无限个素数。
除1和它本身外,若正整数n大于1其他数字都无法整除它,则称n为素数。
一个数若大于1,那么它或者是素数,或者存在素数能整除它。这是个重要定律。
在证明过程中会使用到引理,即可独立证明的有用结论。
通过假设立论得到矛盾,可以推翻原假设,这是反证法的原理。
模态算术又称钟算术,是一种限定在有限范围内的算术运算。它可以像钟表数字那样循环并无限延伸。常见的模态算术运算包括:
在模态算术中,记号“a等于b(mod m)”表示a与b对模m进行同余,即m能整除a-b。同余关系具有等价关系的性质。
模态算术存在两种观点:
仅考虑0-m-1范围内的数字。超出范围后循环回零开始。
将所有整数分为m个互异同余类。每个类取一个代表元素0-m-1作为标记。这样每一个整数实际上都对应了一个同余类。
两种观点等价,选择任一观点进行运算都一致。
在模态算术中,许多常规运算也可以成立:
将整数模m看作为一个整体,称为“整数模m”,也就是有限模组Zm。
有限模组Zm具有封闭性:在Zm中进行算术运算所得结果还在Zm中。同时Zm还满足结合律、交换律等公理,因此Zm实际上形成一个有限域。
有限模组中的模态算术工作具有良好的对称性,从而导出许多有趣的性质,在密码学等应用中尤其重要。
以上就是本视频中关于模态算术的概述。
GCD表示两个数的最大公约数。
最直观的计算方法是从最小的数字开始试探各个可能的因子,直到找到能整除两个数的最大公约数。但是这个方法效率很低。
另一种方法是计算两个数的质因数分解式。例如60=2^2×3×5, 42=2×3×7。 then找出两者公共的最大幂次,即GCD=2×3=6. 但是分解质数也是一个高度复杂的问题。
使用Big O符号来评估算法效率。
算法运行时间通常用输入长度n来表示。例如一个长度为100位的二进制数n,其实际值为2^100约1兆计。
一般情况下,时间复杂度按输入长度n的函数性质分为:
这里b为算法基数,随着n增加,b^n增长得特别快,所以指数时间意味着算法效率极低。
欧几里得算法使用除法方法来计算两个数的GCD,效率远高于上述两种方法。
它重复使用下面的步骤,直到a被除尽为止:
重复上述步骤,最后的余数就是两个初始数的GCD。时间复杂度为O(logn)。
欧几里得算法Time efficiency远高于其他方法,所以被广泛应用于密码学等数理计算中。
上次我们讨论了什么是单射函数和满射函数。单射函数是指一个函数从一个集合映射到另一个集合时,每个元素在目标集合只对应一个元素。满射函数是指一个函数将一个集合全部映射到另一个集合。
双射函数是指一个函数既是单射也是满射。也就是说该函数将一个集合的每个元素都一一对应映射到目标集合,而且目标集合没有没有对应元素。
在群论中,双射可以理解为将一个集合中的所有元素重新命名。例如在模15下,f(x)=4x mod 15就是一个双射函数。
直接计算可以证明f(x)=x2 mod 15并不是一个双射函数。因为x和-x的平方都对应相同的结果,导致一个元素可能对应多个元素,违反单射性。
在计算x2 mod 15时发现,1有4个平方根值,即1、4、11、14。这表明1模15下有多个平方根,而平常我们知道实数 seulement有正负两个平方根。这就是量子计算能够快速分解大整数的契机。
使用中国剩余定理,可以将一个数模另一个数分解成两个模数下的结果。15可以分解成3和5。那么就可以通过x模3和x模5来表示x模15。通过这样的转换,1模15下就可以区分出4个不同的平方根值。这就是量子计算算法能够分辨正负号的原理。
非零多项式的度数为d时,该多项式最多有d个根。
添加两个多项式时,结果多项式的度数小于或等于两多项式度数的最大值。
乘法时,结果多项式的度数等于两多项式度数之和。
除法时,商多项式的度数小于等于被除多项式的度数减去除数多项式度数。余数多项式的度数小于等于除数多项式的度数减一。
当将多项式设置为0时得出的解称为此多项式的根。例如对于多项式x^3 - x,其根有0,1,-1。
将相同顺序项相加,形成新的多项式。例如对多项式 x^3 + 9x^2 + 6x - 5 和多项式 x + 2 进行加法,得到的结果为 x^3 + 9x^2 + 7x + 1。
根据项次相乘原理,将一个多项式各项与另一个多项式各项相乘,相同项次项相加,构成结果多项式。
例如对多项式 x^3 + 9x^2 + 6x - 5 和多项式 x + 2 进行乘法,得到结果多项式为 x^4 + 10x^3 + 45x^2 - 76x + 45。
根据长除法原理,按照项次从高到低依次做除法,得到商多项式和余数。
例如将多项式 x^3 + 9x^2 + 6x - 5 除以多项式 x + 2,得到商多项式为 x^2 + 7x - 8,余数为 11。
1950-1960年冷战时期,美国为防止核武器被错误使用,研究如何分散核按钮授权信息。分散授权就是将核武器启动码分散给多位官员,要求至少几位同时授权才能启动。
任意K位官员掌握各自信息后,能联合恢复启动码
K-1位官员的信息中无法包含任何启动码信息
使用多项式插值原理实现上述要求。
选择多项式P(x)的系数域为有理数、实数或复数域等ffields
P(x)的deg为D,则P(x)最多有D个根
如果知道P(x)在D+1个点的值,就能完全确定P(x)
将密码视为P(x)在x=0时的值。将P(x)在n个随机点的值分散给n位官员
任意K位官员提供信息就能确定P(x),但K-1位无法获得任何信息
除模质数外,还可以构建有限域。如mod 5下{0,1,2,3,4}具有加法、乘法等ffield的性质。
如果 seulement关心多项式的基本代数性质,工作在ffield中最佳,如有理数域、实数域、复数域及有限域。
错误纠正码广泛应用于各种通讯 medium,例如视音频、大数据等。它也用于存储数据,例如快速降低成本的RAID系统。
错误纠正码能修复在数据传输过程中发生的错误。传统方法是增加冗余度,发送原始信息和校验码。只要错误数量不超限,就能恢复原始信息。
溢出错误:部分数据丢失。检查位可以检测,通过增加冗余度补上丢失部分。
一般错误:数据收到了,但内容错误。难度比溢出错误大,因为无法确定哪部分数据错误。需增加更多冗余度进行错误检测和纠正。
使用n个字符构成原始信息,增加k个冗余字符,形成编码后的n+k个字符进行传输。只要错误数量低于某个阈值,就能通过冗余信息恢复原始信息。
两个关键参数:1. 冗余程度k/n 2. 能容忍的最大错误数量。通常性能越好,冗余度越高。
提供错误检测和纠正能力,保障信息可靠传输。
应用于各种通信媒介,数字存储系统。
启发后续更高效的数据保护技术。
以上内容概括了错误纠正码的基本原理、类型和应用。
概率理论起源于17世纪60年代,帕斯卡和费马通过通信讨论了某些游戏中的概率问题。概率理论在20世纪成为科学的基石。
概率理论描述了不确定性,它适用于掷骰子、抛硬币等涉及机会性的情况。随着粒子数量的增加,不确定性会导致确定性。例如,我们之所以能够确定空气的质量,是因为空气中粒子数量趋近无限。
统计物理学和量子力学都具有内在的概率性质。量子力学认为,概率论不仅描述我们对世界的认识不确定性,而是世界本身的属性。
概率理论广泛应用于统计推理、人工智能和算法等领域。今天如果在这些领域做研究而不使用概率工具,研究范围将非常有限。
计数是概率论的基础,它可以用采样的方式理解:
对一个包含6个单位(1-6)的总体采样,即抓取总体中的单位。这种采样方式称为有放回采样,因为每次采样后该单位会放回总体中。
对一个包含52个卡(C1-C52)的卡组采样,即抓取卡组中的卡。这种采样方式称为无放回采样,因为每次采样后的卡不会放回卡组中。
无论采样对象数量为多少,采样可能的结果组合数都很大。计数就是确定各种采样情况下可能结果的数量。
对总体进行n次有放回采样,不同结果的数量为总体单位数量的n次方。例如掷六面骰子4次,可能结果为6^4。
对总体进行n次无放回采样,第一项adopt选项数量为总体数量,第二项选项数量为总体数量减1,以此类推。最后计算各项乘积即为不同结果的数量。例如从52张卡抽5张,可能结果为5251504948。
理解了这些基本概念后,计数问题就变得非常简单。掌握计数对概率论的研究至关重要。
实验:指的是可以重复进行的活动,例如掷硬币、掷骰子等。
样本空间:是指一个实验可能产生的所有结果组合,称为样本空间Ω。
事件:实验结果的一个子集合,是样本空间Ω中的一个子集。
概率:一个事件发生的可能性,用0-1之间的小数表示。
掷骰子:样本空间Ω={1,2,3,4,5,6},掷出奇数的概率为1/2,原因是6个数中有3个数是奇数。
掷两个骰子:样本空间Ω有36种可能结果。得到对数(所有点数相同)的概率是6/36=1/6。sum为7的概率是6/36=1/6。
硬币掷掷三次:样本空间Ω有2^3=8种结果。至少出现一次头的概率是7/8。出现准确一次头的概率是3/8。
概率定义:一场实验产生的所有可能结果称为样本空间Ω,一个子集称为事件,事件的概率等于该事件元素在样本空间Ω中的元素数除以样本空间Ω中的元素总数。
随掷次数增加,样本空间Ω中的元素个数呈指数增长,直接计数已无法计算概率,需要概率论知识来计算。
生日悖论问:在某个班级里,有n个学生,他们要比较是否有两个学生生日相同。n需要多大,才有大概50%的概率出现两人生日相同?
一般认为当n等于365/2时,概率为50%,但是实际上n需要更大,大概是25。
我们定义事件A为:有至少两名学生生日相同。定义事件B为:没有两名学生生日相同。
计算事件B的概率P(B)比较简单。样本空间Ω的事件点个数为365^n种,B中的事件点个数为365阶乘/(365-n)阶乘。所以P(B)=365阶乘/(365-n)阶乘/365^n
计算几个n值得P(B),可以发现当n=25时,P(B)约为0.5。
事件A就是Ω-B,所以P(A)=1-P(B)。实际计算结果与经验估计相符合。
蒙迪汉尔悖论中,有三扇门背后分别藏着车、纸和纸。参赛者随机选择一扇门。主持人打开其中一扇不是车的门,询问参赛者是否要换另一扇门。
一开始,参赛者选择正确门的概率为1/3。如果不换,正确率不变为1/3。如果换门,正确率为2/3,因为主持人必定打开其中一扇纸门,参赛者选择另一扇就必有2/3概率抽中车门。
所以,在蒙迪汉尔悖论中,换门策略的成功概率 higher 所以应选择换门。
条件概率的独立性有两种等价定义:
两个事件A和B的概率交集等于A的概率乘以B的概率:P(A∩B)=P(A)×P(B)
| 知道B后,A的条件概率不变:P(A | B)=P(A) |
独立性的直观理解是:知道一个事件后,不会影响 anderen事件的概率。
常见独立事件例子:掷硬币、掷两枚骰子等。但人难以直观理解长串相同结果的概率不变,因为心里产生偏差。
使用条件概率公式计算联合事件的概率:
| P(A∩B)=P(A)×P(B | A)=P(B)×P(A | B) |
| 如果A和B独立,则P(A | B)=P(A),P(B | A)=P(B),联合概率为: |
P(A∩B)=P(A)×P(B)
投球入筐两个球是否独立:根据投球入筐的概率不因先前球入筐与否而改变,两个事件独立。
放球入箱是否独立:如果球数少于箱数,事件独立;但球数大于等于箱数,先后箱状态将影响对方,不再独立。
拉取两张牌是否独立:由于牌数量固定,掺入的概率不因先前牌而改变,两个事件独立。
随机变量是对一个随机试验结果的数值表示。它有一个域(可能取值的集合)和一个概率分布(不同取值的概率)。
随机变量的定义需要从直观理解过渡到更形式的定义。它反映了不确定性,是概率论的基本概念。
随机变量是指把样本空间上的每个样点映射到实数的一个函数。比如掷骰子,事件空间是1-6个点,根据掷出的点数,我们可以定义随机变量X来表示点数。
概率分布描述了随机变量取各个可能值的概率。例如掷一个骰子,随机变量X可能取1-6的值,则它的概率分布可以表示为:
P(X=1)=1/6 P(X=2)=1/6 … P(X=6)=1/6
二项分布描述了重复采样定点的成功实验次数。例如掷硬币n次,硬币朝正面朝正面和反面面出现的概率分别为P和Q(1-P),则成功次数X服从二项分布:
P(X=k)={nPk(1-P)(n-k)
随机变量的期望定义为各可能值与其概率的乘积之和。对于离散型随机变量:
E(X)=Σa*P(X=a)
也就是把所有可能的值a乘以其概率P(X=a)求和。期望可以理解为随机变量的“平均”值。
除期望外,随机变量的方差、标准差等也可以描述它的概率分布,在实际问题中运用这些统计量可以对随机变量进行建模。难以计算概率分布时,通过分析这些统计量可以对随机变量形状有更深入的了解。
预测选举需要通过抽取随机样本来估计总体分布。但是,人口分布不均匀,直接随机选择点后选取的人不构成随机样本。正确的方法是根据各地人口密集程度,以不同概率抽取不同地区的人作为样本。
如果采访随机样本后的投票选择,与抛掷一个偏向某面(比如51%概率正面)的硬币相对应。每次采访一个随机样本,就是再抛掷这枚硬币一次。
预测要求给出投票希望的精确概率值。但实际抛掷有两个误差来源:
估计值可能与实际概率值有一定误差。
每次抛掷结果都有可能因运气因素偏离概率,产生5%的错误率。
要求预测值在ε误差范围内成立的概率为1-δ。公式可以计算出抛掷硬币的次数n,才能满足这两个指标。n越大,ε和1-δ值越小,预测就越精确可靠。
通过理解抽样与概率对应关系,可以利用统计学理论给出样本数量的最佳值,使预测结果在相关误差范围内具有很高概率。这种方法比仅依靠主观感觉和经验要科学得多。
probabilistic distributions 常见的离散型概率分布有3种:
二项分布:掷硬币n次,统计拿到的正面朝上的次数。概率公式为:P(X=k) = C(n,k)p^kq^(n-k)
几何分布:掷硬币,统计等待第一次出现正面朝上的掷硬币次数。概率公式为:P(X=k) = q^(k-1)p
伯努利试验:每个试验的结果是成功或失败,试验之间互相独立。
二项分布的数学期望为:E(X)=np
方差为:Var(X)=npq
这是因为X可以表示为X1+X2+…+Xn,其中Xi表示每个掷硬币的结果,且彼此独立。
根据定义,计算W1的概率分布为:P(W1=k)=q^(k-1)p
计算W1的期望值:E(W1)=ΣkP(W1≥k)=1/p
另一种计算方法:
几何分布表示掷硬币等待第一个正面结果的次数,其期望值等于倒数的成功概率1/p。
连续概率概率是指随机变量可以取任意实数值的概率分布。与离散概率不同,连续概率采用概率密度函数来描述分布。
概率密度函数f(x)满足:
f(x) ≥ 0,概率密度必须为非负值。
∫ from −∞ to +∞ f(x) dx = 1,整体概率为1。
间隔[a, b]内随机变量x概率为∫ from a to b f(x) dx
例如选择一点在0-l之间的直线段上。则概率密度函数为:
f(x) = 1/l, x 在0-l区间内
f(x) = 0, 其他地方
随机变量X的期望为:
E(X) = ∫ from -∞ to +∞ x * f(x) dx
如在0-l区间选择点,则E(X)=l/2
随机变量X的方差为:
Var(X) = E(X^2) - [E(X)]^2 = ∫ from -∞ to +∞ x^2 * f(x) dx - [∫ from -∞ to +∞ x * f(x) dx]^2
指数分布是用于描述等待事件发生时间的连续概率分布。它有一个参数 λ,称为频率参数。
指数分布的概率密度函数为:
f(x) = λe^(-λx) , x≥0
其中λ为正实数。
指数分布的期望值为:E(X)=1/λ
方差为:Var(X)=1/λ^2
高斯分布(Gaussian distribution)也称正态分布,是一种常见的连续概率分布。
它的概率密度函数为:
f(x) = 1/sqrt(2πσ^2) * e^(-(x-μ)^2/2σ^2)
其中:
高斯分布的期望值为μ,方差为σ^2。
卡尔曼滤波是一个线性最小二乘估计问题的解决方法,用于从一系列连续但含噪声的观测值中获得系统状态的最优估计值。它可以 muy有效地从观测数据中提取信息,进行状态估计。
还将讨论可计算性理论和无穷集合的相关概念,如可数集合和不可数集合。
考试将在12月14日周五晚上7点至10点在教室进行。
推理问题很常见。它涉及隐藏的随机变量X,我们无法直接观察X,只能通过噪声测量获得Y1,Y2等一系列观测结果。我们希望通过Y1,Y2等观测结果,推断X的分布。
推理问题在许多领域都存在,比如:
我们可以用概率模型来形式描述推理问题:
| 我们知道观测值Y给定X的条件分布P(Y | X) |
| 我们希望通过观测结果推断X给定观测值的后验分布P(X | Y1,Y2…Ym) |
假设在赌场有n台老虎机,每个机器都有不同的赢面率。我们可以:
我们可以将每个机器看作一个带偏差的硬币。通过多次投币测试,获得该机器的头尾次数,从而判断其胜率高低。这就是一个简单的离散变量推理问题。
若要控制航天器月球着陆,关键在于实时估计其位置。但我们无法直接观测位置,只能通过传感器间接获得位置测量结果,这往往含有误差。
我们可以建立航天器位置与传感器测量之间的关系模型,并给出位置和测量结果的先验分布。然后通过贝叶斯推断,实时更新位置的后验分布估计,用于控制系统决策。这是一个连续变量的推理问题。
以上两个例子展示了推理问题在离散与连续变量情况下的基本模型。后续课程将进一步系统讨论不同推理算法。
在幼儿园时,我们学习计数是通过一对一对应的方式。例如用三个物体来代表三个玩具,然后以一对一的方式将三个物体一一对应映射到三个玩具上。
数学家后来 formalized 这个概念,把它定义为一个函数 f:
我们说两个集合 S 和 T 有相同基数,如果存在一个双射函数 f,它可以使 S 对应到 T。
对有限集合来说,如果它们元素个数不同,那么基数就不同。但是对于无限集合来说,情况不一定这样。
例如:
自然数集 N 和正整数集 Z^+。它们元素个数看起来不同,但实际上可以建立双射,将 N 对应到 Z^+。
自然数集 N 和能被 2 整除的自然数集 {0,2,4,…}。虽然后者元素似乎少,但可以建立双射,证明它们基数相同。
我们可以通过构建双射函数来比较不同类型无限集合的基数大小。
计算机无法解决的问题通常都是那些没有算法可以解决的问题。例如停机问题就是计算机无法判定任意程序是否会停机的问题。