西西河

主题:【翻译】概率随机及编程 (一) -- 东方射日

共:💬21 🌺99 新:
全看分页树展 · 主题
家园 【翻译】概率随机及编程 (一)

十月底被公司裁员,还算幸运吧,十一月中就拿到一个offer,谁说是contract的,但毕竟是有工作了,而且公司还是一个巨型的软件公司,应该对以后找工作有帮助吧。不过俗话说“骑驴找马”,这不,就继续找看看有没有permanent的职位,同时多找一些算法题做做,题海题海,说实在,还是题海最管用。

这不,找到一个好网站:Topcoder.com,上面有大量的算法的编程题,同时还有一些很不错的文章,推荐给大家看看。同时想自不量力,翻译一些文章给不喜欢(本人就是一个)看英文的人参考参考。对你有帮助呢,那就算我为大家在经济危机中多一条生路做一点自己的微薄贡献(当然鲜花是一定欢迎的)。如果有错误或不妥呢,也请高手不吝赐教,鲜花是一定会有的。

原文的链接在外链出处。看了一下,好像没有提到这些文章的版权问题,就先自作主张认为没有关系吧,如果大家发现有版权问题就请尽快来消息告知。

不过里面的很多例题都是有版权的,我们只能大致描述一下,具体的内容还是请大家注册一个帐号到上面去看吧。相信我,如果你是软件工程师,而且对算法感兴趣,这一定是值得的。

翻译中才发现翻译的困难,有的明明看起来很好理解的,用中文表达的话,还真就有点绕口。雅是不敢求的,不过翻完后,自己又都读了一篇,应该理解是不会有太大的困难吧,只希望“信”上不要有太大的差距。

在上述链接中有很多文章,我不敢保证有时间都翻译出来,有一篇算一篇吧。希望有人也愿意翻译其他一些文章。好吧,就随机地从这篇文章开始吧:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities

概率随机及编程

作者:supernova

前言

有种说法,生活是概率的学校。概率论让我们的每一天都生活在风险评估中。假设有一个考试,总共有20门可能要考科目,而你只有时间准备其中15门。那么考了两门你都准备过了的科目的可能性是多少?这是我们生活的世界会带给你的一个简单的问题。生活是一个非常复杂的事件链,其中几乎每件事都可以想象成一定的概率。

赌博已经是我们生活的一部分,这其中显而易见牵涉到了概率。虽然赌博的历史可以追溯到史前时代,但是直到17世纪,随着近代数学基础的建立,才开始被研究。这始于一个Chevalier de M(一个经常通过赌博增加财富的贵族)向Blaise Pascal提出的一个简单问题:扔24轮骰子是否可以得到两个6点?

一些编程问题是由现实问题引申来的,通常我们会描述一些状态,并解释一些运行的规则。但你会发现如果这是一个概率相关的问题时,解决的方法就并不那么显而易见。这可能是因为在编程学习、竞赛中,概率经常被忽视而没有作为主要的研究点和考察点。

在采用一些必要的算法解决这类问题前,你必须有一些数学的准备知识。下一章将介绍概率的基本原理。如果你已经在这方面有点经验的话,也许你可以跳到下一章:概率计算。在那以后我们会对随机算法进行简单的讨论,随后列出了一些练习的题目。这最后一章也许是最重要的:练习!关键就是多练习。

基础

解决概率问题很像是在做实验,输出就是一个实验的结果,这包含其他一些不确定的因素。对于一个概率实验所有可能的输出,我们称为采样空间。每种可能的结果在采样空间中占且仅占据一个单位,通常用符号S代表。让我们考察如下实验:

扔骰子一次:

采样空间 S={1,2,3,4,5,6}

抛两个硬币:

采样空间 S=({正,正},{正,反},{反,正},{反,反})

我们定义我们实验一次为一个事件。这样,一个事件就是采样空间S的一个子集。如果我们用E来代表一个事件,那么有E S。如果一个事件仅包含一次采样空间的结果收集,那么我们称为简单事件。对超过一个结果的收集,我们称为复合事件。

事实上我们通常仅对某一特定事件的概率感兴趣,记为P(E)。我们定义P(E)是0到1间的一个实数。0表示这是不可能的事件,而1则表示确定事件。

我们前面说过任何一种结果都是采样空间中的一个单位,那么我们可以有如下公式:

P(E) = |E| / |S|

一种事件发生的概率是该类事件(特定结果发生)的次数除以各种可能事件(各种结果发生)的总次数。要理清事件之间的关系,我们可以应用集合的知识。例如考察扔骰子的实验,我们前面说到这实验的采样空间 S={1,2,3,4,5,6}

现在我们考察如下事件:

事件 A = '点数 > 3' = {4, 5, 6}

事件 B = '点数为奇数' = {1, 3, 5}

事件 C = '点数为7' =

A∪B ='点数大于3或为奇数' = {1, 3, 4, 5, 6}

A∩B ='点数大于3或为奇数' = {5}

A' = '事件A没有发生' = {1, 2, 3}

那么我们有:

P(A∪B) = 5/6

P(A∩B) = 1/6

P(A') = 1 - P(A) = 1 - 1/2 = 1/2

P(C) = 0

解决概率问题的第一步是定出采样空间,然后你就需要确定期望结果的数目。这就是传统的解决办法,但是具体的解决方法是多种多样的。例如在”Quiz Show”(例题都是有版权的,请自己登录网站看)问题中,解决的关键是考虑所有的可能性,这数目并不多。通过简单的分析,我们可以定义一下样本空间

S = { (wager 1 is wrong, wager 2 is wrong, you are wrong),

(wager 1 is wrong, wager 2 is wrong, you are right),

(wager 1 is wrong, wager 2 is right, you are wrong),

(wager 1 is wrong, wager 2 is right, you are right),

(wager 1 is right, wager 2 is wrong, you are wrong),

(wager 1 is right, wager 2 is wrong, you are right),

(wager 1 is right, wager 2 is right, you are wrong),

(wager 1 is right, wager 2 is right, you are right) }

该问题要求你找到你最有可能获胜的下注额,为了计算一定下注额的获胜概率,我们可以分别计算8种情况下各人的最后得分。以下程序可以进行这个计算:

int wager (vector scores, int wager1, int wager2)

{

int best, bet, odds, wage, I, J, K;

best = 0; bet = -1;

for (wage = 0; wage ≤ scores[0]; wage++)

{

odds = 0;

// in 'odds' we keep the number of favorable outcomes

for (I = -1; I ≤ 1; I += 2)

for (J = -1; J ≤ 1; J += 2)

for (K = -1; K ≤ 1; K += 2)

if ( scores[0] + I * wage > scores[1] + J * wager1

&& scores[0] + I * wage > scores[2] + K * wager2) { odds++; }

if (odds > best) { bet = wage ; best = odds; }

// a better wager has been found

}

return bet;

}

另外一个很好的例子是“Pipe Cuts” 。这也可以用类似的方法解决。对这类只有有限可能(且数目不是太大)的情况,我们可以利用这种穷举法计算。

对于一系列独立事件:E1,E2......EN,有两个经常会提到的问题(应该你们也已经遇见过):

一:所有事件发生的概率是多少?

二:至少一事件发生的概率是多少?

要回答第一个问题,我们可以先考虑第一事件E1发生的概率,如果E1不发生,上述一将永远不会满足。那么我们可以确定必须有E1以P(E1)的概率发生了——即有P(E1)的可能性——我们才需要继续检查下一事件(E2)。而E2发生的概率是P(E2),接着我们就可以重复这一步骤。正如我们上面说到概率是用0到1间的实数定义的,那么显然我们可以用以下公式计算所有事件发生的概率:

P(all events) = P(E1) * P(E2) * …... * P(EN)

对于第二个问题,更容易的方法是计算任一事件都不发生的概率。(也就是说有反事件发生的概率)我们可以有:

P(at least one event) = 1 - P(E1') *P(E2`)*......* P(EN')

这两个公式非常重要,请在继续下一章前理解他们。

关键词(Tags): #算法#随机#概率#编程元宝推荐:爱莲,

本帖一共被 2 帖 引用 (帖内工具实现)
全看分页树展 · 主题


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河