算法第一章精.ppt

《算法第一章精.ppt》由会员分享，可在线阅读，更多相关《算法第一章精.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法第一章课件第1页，本讲稿共40页n例例 随机试验随机试验 E：掷一枚均匀的骰子，观：掷一枚均匀的骰子，观 察其点数为几。察其点数为几。n样本点样本点记为：1,2,3,4,5,6，注意：注意：这这 里数字里数字 k 用来用来表示表示事件事件:“点数为点数为 k”。n样本空间样本空间：=1,2,3,4,5,6 则所有则所有基本事件基本事件为：1,2,3,4,5,6。n集合集合 A=1,3,5 可表示事件：可表示事件：“点数为奇数点数为奇数”,n因为，因为，集合集合A与与事件事件“点数为奇数点数为奇数”存在下面的存在下面的一一一对应关系一对应关系：n事件：事件：“点数为奇数点数为奇数”发生，当且

2、仅当发生，当且仅当 A中的某一个基本事件发生。中的某一个基本事件发生。第2页，本讲稿共40页发生必导致发生必导致 发生发生特别有特别有发生或发生或 发生发生即即 至少有一个发生至少有一个发生,称为事件称为事件 的的和和从集合和事件两方面来理解从集合和事件两方面来理解从集合和事件两方面来理解从集合和事件两方面来理解1.5.1、事件的关系与运算事件的关系与运算第3页，本讲稿共40页同时发生同时发生 称为事件称为事件 的的积积 类似地可定义类似地可定义 个事件的积个事件的积发生发生 不发生不发生 称为事件称为事件 的的差差第4页，本讲稿共40页,记为记为记为记为即即 不能同时发生不能同时发生且且若若

3、,则称则称 互为互为逆事件逆事件若若,则称则称互不相容互不相容(互斥互斥)或称为或称为对立事件对立事件“骰子出现骰子出现1点点”“骰子出现骰子出现2点点”互斥互斥第5页，本讲稿共40页对立事件与互斥事件的区别对立事件与互斥事件的区别 ABABA、B 对立对立A、B 互斥互斥互互 斥斥对对 立立第6页，本讲稿共40页德德摩根（摩根（De MorganDe Morgan）律）律第7页，本讲稿共40页 记记 号号 概率论概率论 集合论集合论 (S)样本空间样本空间,必然事件必然事件 空间空间,全集全集 不可能事件不可能事件 空集空集 样本点样本点 元素元素 A 事件事件 集合集合A是是B的子事件的子

4、事件 A是是B的子集的子集 A与与B是相等事件是相等事件 A与与B是相等集合是相等集合 A与与B互不相容互不相容(互斥互斥)A与与B无相同元素无相同元素A与与B的并的并(和和)事件事件 A与与B的并集的并集A与与B的交的交(积积)事件事件 A与与B的交集的交集A与与B的差事件的差事件 A与与B的差集的差集A的对立事件的对立事件(逆事件逆事件)A的余的余(补补)集集第8页，本讲稿共40页 课堂练习课堂练习1.1.若若A是是B的子事件的子事件，则，则 =()=()，AB=()2.2.设当事件设当事件A与与B同时发生时同时发生时C也发生也发生,则则()是是C的子事件的子事件；C是是 的子事件；的子事

5、件；AB是是C的子事件；的子事件；C是是AB的子事件。的子事件。第9页，本讲稿共40页3.3.设事件设事件A=A=甲种产品畅销，乙种产品滞销甲种产品畅销，乙种产品滞销，则则A A的对立事件为（的对立事件为（）甲种产品滞销，乙种产品畅销；甲种产品滞销，乙种产品畅销；甲、乙两种产品均畅销；甲、乙两种产品均畅销；甲种产品滞销；甲种产品滞销；甲种产品滞销或者乙种产品畅销。甲种产品滞销或者乙种产品畅销。4 4.设设x表示一个沿数轴做随机运动的质点位表示一个沿数轴做随机运动的质点位 置，试说明下列各对事件间的关系置，试说明下列各对事件间的关系 A=|x-a|，B=x-a（0）A=x20，B=x20 A=x

6、22，B=x19第10页，本讲稿共40页5.设设A、B、C为任意三个事件为任意三个事件,试用它们表示下列事件试用它们表示下列事件:A发生，发生，B、C不发生；不发生；A、B发生，发生，C不发生；不发生；A、B、C都发生；都发生；A、B、C都不发生；都不发生；A、B、C中恰有一个发生；中恰有一个发生；A、B、C中至少有一个发生；中至少有一个发生；第11页，本讲稿共40页1.5.2、加法公式加法公式 若若AB=,则则 P(AB)=P(A)+P(B)。例：例：一批产品共一批产品共 10 件，其中有件，其中有 2 件不合格，从中任取件不合格，从中任取 3 件，件，求求最多一个不合格品最多一个不合格品的

7、概率。的概率。第12页，本讲稿共40页知识点：知识点：P()=0，P()=1，对于任一事件，对于任一事件A，推论：推论：（1）（2）P(A-B)=P(A)-P(AB),若若 B 是是 A 的子事件的子事件,则则 P(A-B)=P(A)-P(B)；P(B)P(A)（单调性）（单调性）.例：例：一批产品共一批产品共1010件，其中两件不合格，从中任取件，其中两件不合格，从中任取3 3件，件，求求至少一个不合格品至少一个不合格品的概率。的概率。第13页，本讲稿共40页(3)加法公理加法公理 对于对于n个个或或可列个可列个互不相容事件互不相容事件 可表示可表示为：为：即即:若若 两两互不相容两两互不相

8、容,则则 若若 两两互不相容两两互不相容,则则第14页，本讲稿共40页对任何事件对任何事件 有有(加法公式加法公式)对于三事件对于三事件 有有挖挖挖挖挖挖补补(4)可能相容情形可能相容情形第15页，本讲稿共40页对于对于 个事件，有个事件，有全加全加全加全加减二减二减二减二加三加三加三加三挖补规律挖补规律挖补规律挖补规律:加奇减偶加奇减偶加奇减偶加奇减偶减四减四减四减四第16页，本讲稿共40页例题例题1.AB=，P(A)=0.6，,求求 B的逆事件的概率。的逆事件的概率。得：得：P(B)=P(A)=0.8-0.6=0.2P(B)=P(A)=0.8-0.6=0.2，所以，所以，P()=1-0.2

9、=0.8P()=1-0.2=0.8解：由解：由 P(A)+P(B)P(A)+P(B)思考：在以上条件下，思考：在以上条件下，P(A-B)=？第17页，本讲稿共40页2.设事件设事件A发生的概率是发生的概率是0.6，A与与B都发生的概率是都发生的概率是0.1，A 与与B 都都 不发生不发生 的概的概率为率为 0.15,求求 A发生发生B不发生的概率；不发生的概率；B 发生发生A不发生的概率及不发生的概率及P(AB).第18页，本讲稿共40页解：由已知得，解：由已知得，P（A）=0.6，P（AB）=0.1，P（）=0.15，则则 P（A-B）=P（A）-P（AB）=0.5 P（B-A）=P（B）-

10、P（AB）1-P（）=1-P（）=0.85又因为又因为 P（A）+P（B）-P（AB），所以，），所以，P（B）=-P（A）+P（AB）=0.85-0.6+0.1=0.35从而，从而，P（B-A）=0.35-0.1=0.252.设事件设事件A发生的概率是发生的概率是0.6，A与与B都发生的概率是都发生的概率是0.1，A 与与B 都都 不发生不发生 的概率为的概率为 0.15,求求 A发生发生B不发生的概率；不发生的概率；B 发生发生A不发生的概率及不发生的概率及P(AB).第19页，本讲稿共40页课堂练习课堂练习(901)P(A)=0.4(901)P(A)=0.4，P(B)=0.3P(B)=0

11、.3，P(AP(AB)=0.6B)=0.6，求，求P(A-B).P(A-B).(915)P(A)=0.7(915)P(A)=0.7，P(A-B)=0.3P(A-B)=0.3，求，求P(P(-AB)-AB)(921)P(A)=P(B)=P(C)=1/4(921)P(A)=P(B)=P(C)=1/4，P(AC)=P(AB)=0 P(AC)=P(AB)=0，P(BC)=1/6 P(BC)=1/6，求，求A A、B B、C C都不发生的概率。都不发生的概率。(941)A(941)A、B B都发生的概率与都发生的概率与 A A、B B 都不发生的概率相等，都不发生的概率相等，P(A)=p P(A)=p，

12、求，求P(B).P(B).第20页，本讲稿共40页解：解：(1)P(AB)=P(A)+P(B)-P(AB)=0.1,(1)P(AB)=P(A)+P(B)-P(AB)=0.1,所以所以 P(A-B)=P(A)-P(AB)=0.3 P(A-B)=P(A)-P(AB)=0.3(2)P(2)P(-AB)=1-P(AB)=1-P(A)-P(A-B)=1-0.7+0.3=0.6-AB)=1-P(AB)=1-P(A)-P(A-B)=1-0.7+0.3=0.6(3)P()=P()=1-P(A(3)P()=P()=1-P(AB BC)=5/12C)=5/12(4)P(AB)=P()=P()=1-P(A(4)P(

13、AB)=P()=P()=1-P(AB)B)=1-P(A)-P(B)+P(AB),=1-P(A)-P(B)+P(AB),所以所以,P(B)=1-P(A)=1-p,P(B)=1-P(A)=1-p第21页，本讲稿共40页 例例 有有10个人个人,其中色盲者其中色盲者3人人,从这从这10人中每次人中每次任取一人，不放回地取两次任取一人，不放回地取两次,问第二次取到色盲的问第二次取到色盲的概率是多少？概率是多少？设设A第一次取出色盲第一次取出色盲,B第二次取出色盲第二次取出色盲第第1.6节节 条件概率、全概率公式及贝叶斯公式条件概率、全概率公式及贝叶斯公式若若A发生，则第二次取到色盲的概率是发生，则第二

14、次取到色盲的概率是2/9，记为，记为P(B|A)2/9第22页，本讲稿共40页1、条件概率条件概率对任意事件对任意事件A，B，则称则称为在为在A已经发生的情况下，事件已经发生的情况下，事件B发生的发生的条件概率条件概率。第23页，本讲稿共40页例例1.1 在在10个产品中有个产品中有7个正品，个正品，3个次品，按不放回个次品，按不放回抽样，每次一个，抽取两次，抽样，每次一个，抽取两次，求：求：两次都取到次品的概率；两次都取到次品的概率；第二次才取到次品第二次才取到次品的概率；的概率；已知第一次取到次品，第二次又取到次品的已知第一次取到次品，第二次又取到次品的概率。概率。解：解：设设A=第一次取

15、到次品第一次取到次品，B=第二次取到次品第二次取到次品，(1)P（AB）=(32)/(109)=1/15 (2)P ()=(73)/(10 9)=7/30(3)P(B|A)=P(AB)/P(A)=(1/15)/(3/10)=2/9若改为有放回抽样呢？若改为有放回抽样呢？第24页，本讲稿共40页例例1.6.2 若若 P(A)=0.6,P(AB)=0.84,P(-B)|A)=0.4,则则 P(B)=().第25页，本讲稿共40页例例1.1.3.3：第26页，本讲稿共40页2 2、乘法公式、乘法公式对于两个事件对于两个事件A与与B，若若P(A)0,则有则有 P(AB)=P(A)P(B|A),若若P(

16、B)0,则有则有 P(AB)=P(B)P(A|B),若若P(A)0,P(B)0,则则 P(AB)=P(A)P(B|A)=P(B)P(A|B)第27页，本讲稿共40页例例1.6.3：某种零件由甲、乙两厂生产，甲厂生产产品的某种零件由甲、乙两厂生产，甲厂生产产品的70%，乙厂生产产品的，乙厂生产产品的30%。已知甲厂的产品中。已知甲厂的产品中90%是一等品，乙厂的产品中是一等品，乙厂的产品中80%是一等品。是一等品。某用户买了某用户买了100件该种零件，问从中任取一件，它是件该种零件，问从中任取一件，它是甲甲厂生产的一等品厂生产的一等品的概率是多少？的概率是多少？解解:以以A表示事件：表示事件：“

17、任取一件任取一件,是甲厂产品是甲厂产品”，以以B表示事件：表示事件：“任取一件任取一件,是一等品是一等品”。P(A)=0.7,P(B|A)=0.9,第28页，本讲稿共40页推广情形推广情形对于对于n个事件个事件A1,A2,An,若若P(A1A2An-1)0，则有，则有P(A1A2An)=P(A1)P(A2|A1)P(A3|A1A2)P(An|A1A2An-1)对事件对事件A，B，C，若，若P(AB)0，则有，则有 P(ABC)=P(A)P(B|A)P(C|AB)注意注意：乘法法则一般用于计算几个事件同时发生的概率：乘法法则一般用于计算几个事件同时发生的概率第29页，本讲稿共40页例例1.6.5

18、1.6.5：设袋中装有设袋中装有r只红球，只红球，t只白球，每次自袋中任取一球，只白球，每次自袋中任取一球，观察其颜色然后放回观察其颜色然后放回，并再放入，并再放入a只与所取出的那只球同色只与所取出的那只球同色的球，若在袋中连续取球的球，若在袋中连续取球4次，次，试求第一、二次取到红球试求第一、二次取到红球且且第三、四次取到白球第三、四次取到白球的概率？的概率？解解:以以Ai表示事件：表示事件：“第第i次取到红球次取到红球”，i=1,2,3,4.第30页，本讲稿共40页3、全概率公式和、全概率公式和Bayes公式公式1、全概率公式：全概率公式：A1,A2,An 是两两互斥的正概是两两互斥的正概

19、率事件组，且事件率事件组，且事件 A1A2An=。则。则 对于任何对于任何一个事件一个事件B，有，有 P(B)=P(A1)P(B|A1)+P(An)P(B|An)注意注意：（1）全概率公式中的事件组）全概率公式中的事件组A1,A2,An称为完备事件组；称为完备事件组；（2）在应用该公式时，必须先找出合适的完备事件组。）在应用该公式时，必须先找出合适的完备事件组。第31页，本讲稿共40页例例1.6.6 设甲袋中有设甲袋中有m个红球，个红球，n个白球；乙袋中有个白球；乙袋中有r个红球，个红球，s个白球。个白球。今从甲袋中任取一球放入乙袋，再从乙袋中任今从甲袋中任取一球放入乙袋，再从乙袋中任取一球取

20、一球，求该球是红球的概率？，求该球是红球的概率？解解：令：令B表示：表示：“从乙袋中任取一球为红球从乙袋中任取一球为红球”；A表示：表示：“从甲袋中取出的球为白球从甲袋中取出的球为白球”；表示：表示：“从甲袋中取出的球为红球从甲袋中取出的球为红球”；第32页，本讲稿共40页例例1.6.7 设设10件产品中有件产品中有4件不合格品，从件不合格品，从 中不放回取中不放回取两次，每次一件，求第二件为不合格品的概两次，每次一件，求第二件为不合格品的概 率为多少率为多少？解：令解：令B=第二次取得不第二次取得不 合格品合格品，A=第一次取得不合格品第一次取得不合格品，事件，事件A和和 A的对立事件的对立

21、事件构成完备事件组，构成完备事件组，由全概率公式得由全概率公式得：=（4/10）（3/9）+（6/10）（4/9）=6/15第33页，本讲稿共40页例例1.市场上某种商品由三个厂家同时供货市场上某种商品由三个厂家同时供货,其供应量为其供应量为:甲厂家是乙厂家的甲厂家是乙厂家的2倍倍,乙、丙两个厂家相等乙、丙两个厂家相等,且各厂产品的次品且各厂产品的次品率为率为2%,2%,4%,（1）求市场上买到该种商品的次品的概率）求市场上买到该种商品的次品的概率.解：解：设设B表示买到次品表示买到次品,Ai表示表示“买到第买到第i 个工厂产品个工厂产品”，i=1,2,3。由题意由题意 得得:P(A1)=0.

22、5,P(A2)=P(A3)=0.25,P(B|A1)=0.02,P(B|A2)=0.02,P(B|A3)=0.04由全概率公式得由全概率公式得:=0.025第34页，本讲稿共40页(2)(2)若从市场上的商品中随机抽取一件若从市场上的商品中随机抽取一件,发现是次发现是次品品,求它是甲厂生产的概率求它是甲厂生产的概率?分析分析:所求为条件概率所求为条件概率P(A1|B)=P(A1B)/P(B).第35页，本讲稿共40页4、贝叶斯（、贝叶斯（Bayes）公式）公式贝叶斯公式贝叶斯公式:设设正概率事件正概率事件A1，A2,.,An构成完备事件组,对于任何一个正概率事件对于任何一个正概率事件B，有，有

23、第36页，本讲稿共40页例例1.6.7 市场上某种商品由三个厂家同时供货市场上某种商品由三个厂家同时供货,它们的供应量为它们的供应量为:甲厂家是乙厂家的甲厂家是乙厂家的2倍倍;乙、丙两个厂家相等乙、丙两个厂家相等,且各厂产品的次品率且各厂产品的次品率分别为分别为2%,2%,4%,(1)求市场上买到该种商品的次品的概率求市场上买到该种商品的次品的概率.(2)若从市场上的商品中随机抽取一若从市场上的商品中随机抽取一 件件,发现是次品发现是次品,求它是甲厂求它是甲厂 生产的概率生产的概率?解：解：(2)设设B表示取到次品表示取到次品,Ai表示取到第表示取到第i 个工厂产品，个工厂产品，i=1,2,3

24、,由题意得由题意得:P(A1)=0.5,P(A2)=P(A3)=0.25 P(B|A1)=0.02,P(B|A2)=0.02,P(B|A3)=0.04 由由Bayes公式得公式得:=0.4第37页，本讲稿共40页1 1、已知男人中有已知男人中有5%5%是色盲者，女人中有是色盲者，女人中有0.25%0.25%是色盲患者，今从是色盲患者，今从男女人数相等男女人数相等的人群中随机的人群中随机挑选一人，恰好是色盲患者，问此人是男性挑选一人，恰好是色盲患者，问此人是男性的概率是多少？的概率是多少？解解：令令B表示：表示：“挑选一人是色盲挑选一人是色盲”，；A表示：表示：“挑选一人是男性挑选一人是男性”和其对立和其对立 事件事件 构成完备事件组。构成完备事件组。课堂练习课堂练习第39页，本讲稿共40页