蔡文能 CC++ 程式設(shè)計 1課件

1、Games, Random NumbersandIntroduction to simple statisticsPRNGPseudo Random Number Generator蔡文能tsaiwn.tw蔡文能 C/C+ 程式設(shè)計1AgendaWhat is random number(亂數(shù)) ?How the random numbers generated ?rand( ) in C languages: Linear Congruential Why call “Pseudo random” ? (P不發(fā)音)How to do “true random” ?Application of

2、 Rrandom number ?Other topics related to Random numbersIntroduction to simple statistics (統(tǒng)計簡介)蔡文能 C/C+ 程式設(shè)計2BATNUM game/basicgames/showpage.php?page=14An ancient game of two playersOne pile of match sticks (or stones)Takes turn to remove 1, maxTake(至少拿 1, 至多拿 maxTake)可規(guī)定拿到最後一個贏或輸 !Winning strategy

3、? Games 須用到 Random Number! Why?蔡文能 C/C+ 程式設(shè)計3Bulls and Cows Game http:/5ko.free.fr/en/bk.html /wiki/Bulls_and_cows/zh-hant/%E7%8C%9C%E6%95%B0%E5%AD%97/od/paperpencil/a/bulls_and_cows.htm/eng/play/bk.html/index.php/online-games/bulls-and-cows/index.phpGames 須用到 Random Number! Why?蔡文能 C/C+ 程式設(shè)計4What i

4、s random number ?Sequence of independent random numbers with a specified distribution such as uniform distribution (equally probable)Actually, the sequence generated is not random, but it appears to be. Sequences generated in a deterministic way are usually called Pseudo-Random sequences.參考 /softwar

5、e/gsl/manual/gsl-ref_19.htmlNormal distribution? exponential, gamma, Poisson, 蔡文能 C/C+ 程式設(shè)計6Turbo C+ 的 rand( )與srand( ) #define RAND_MAX 0 x7fffu static unsigned long seed=0; int rand( ) seed = seed * 1103515245 + 12345; return seed % (RAND_MAX+1); void srand(int newseed) seed = newseed; static glob

6、al 變數(shù)請參考K&R課本4.6節(jié)Pseudo random number就是15個 1的binary注意 C 語言的 rand( ) 生出的不是 Normal Distribution!static 使其它file裡的function 看不見這 seed蔡文能 C/C+ 程式設(shè)計7Random Number Generating AlgorithmsLinear Congruential GeneratorsSimple way to generate pseudo-random numbersEasily crackedProduce finite sequences of numbers

7、Each number is tied to the othersSome sequences of numbers will not ever be generatedCryptographic random number generatorsEntropy sensors (i.e., extracted randomness)蔡文能 C/C+ 程式設(shè)計9Linear Congruential Generator (LCG) for Uniform Random DigitsPreferred method: begin with a seed, x0, and successively

8、generate the next pseudo-random number by xi+1 = (axi + c) mod m, for i = 0,1,2, wherem is the largest prime less than largest integer computer can storea is relatively prime to mc is arbitraryLet A be largest integer less than A (就是只取整數(shù)部份), then N mod m = N N/T*TAccept LCG with m, a, and c which pa

9、sses tests which are also passed by know uniform digitsmod 在C/C+/Java 用 %蔡文能 C/C+ 程式設(shè)計10The use of random numbers1. Simulation2. Recreation (game programming)3. Sampling4. Numerical analysis5. Decision making randomness an essential part of optimal strategies( in the game theory)6. Game program, . .

10、 .蔡文能 C/C+ 程式設(shè)計11Uniform Distribution(齊一分配 )在 發(fā)生的機(jī)率皆相同蔡文能 C/C+ 程式設(shè)計12Normal Distribution (常態(tài)分配 )蔡文能 C/C+ 程式設(shè)計13Standard Normal Distribution(標(biāo)準(zhǔn)常態(tài)分配)N(0, 1)平均是 0標(biāo)準(zhǔn)差 1蔡文能 C/C+ 程式設(shè)計14Central Limit Theorem (CLT)(中央極限定理 )如果觀察值數(shù)目 n 增加，則 n 個獨(dú)立且具有相同分配(independent and identically distributed, I.I.D.)的隨機(jī)變數(shù)(Ran

11、dom variable)之平均數(shù)向常態(tài)分配收斂。 樣本大小n30時， 趨近於常態(tài)分配。 蔡文能 C/C+ 程式設(shè)計16如何用 C 生出常態(tài)分配的亂數(shù)?#include double randNormal( ) / 標(biāo)準(zhǔn)常態(tài)分配產(chǎn)生器 int i; double ans =0.0; for(i=1; i =30 observations are drawn from the same population where X ?(,), then 蔡文能 C/C+ 程式設(shè)計38 Central Limit Theorem （中央極限定理）For a population with a mean a

12、nd a variance , the sampling distribution of the means of all possible samples of size n generated from the population will be approximately normally distributed - with the mean of the sampling distribution equal to and the variance equal to assuming that the sample size is sufficiently large.蔡文能 C/

13、C+ 程式設(shè)計39The Normal DistributionDescribed by (mean) (standard deviation; 標(biāo)準(zhǔn)差)Variance 變異數(shù) = 標(biāo)準(zhǔn)差的平方Write as N( , ) 或 N( , 2) Area under the curve is equal to 1Standard Normal Distribution 蔡文能 C/C+ 程式設(shè)計40Why is the Normal Distribution important?It can be a good mathematical model for some distribution

14、s of real dataACT ScoresRepeated careful measurements of the same quantityIt is a good approximation for different types of chance outcomes (like tossing a coin)It is very useful distribution to use to model roughly symmetric distributionsMany statistical inference procedures are based on the normal

15、 distributionSampling Distributions are roughly normal (TBC)蔡文能 C/C+ 程式設(shè)計41Normal Distributions and the Standard DeviationNormal DistributionBlack line - MeanRed lines - 1 Std. Dev. from the mean (68.26% Interval)Green lines 2 Std. Dev. from the mean (95.44% Interval)What about 3 Std. Dev. from the

16、mean?95% Confidence interval 1.96 Std. Dev.蔡文能 C/C+ 程式設(shè)計4268-95-99.7 Rule for Normal Curves68.26%+-+3-399.74%+2-295.44%68.26% of the observations fall within of the mean 99.74% of the observations fall within 3 of the mean 95.44% of the observations fall within 2 of the mean 蔡文能 C/C+ 程式設(shè)計43Notations

17、It is important to distinguish between empirical and theoretical distributionsDifferent notation for each distribution蔡文能 C/C+ 程式設(shè)計44Density function of Normal DistributionThe exact density curve for a particular normal distribution is described by giving its mean () and its standard deviation ()den

18、sity at x = f(x) =蔡文能 C/C+ 程式設(shè)計45Confidence Intervals (CI) for ,from a single sample mean 蔡文能 C/C+ 程式設(shè)計46Confidence Interval? (1/2)當(dāng)我們使用軟體去模擬真實(shí)環(huán)境時，通常會用亂數(shù)(random number)模擬很多次，假設(shè)第一次模擬的結(jié)果數(shù)據(jù)是X1，第二次是X2，重覆了n次後，就有X1、X2Xn共n個數(shù)據(jù)，這n個數(shù)據(jù)不盡相同，到底那個才是正確的? 直覺上，把得到的n個結(jié)果加總求平均，所得到的值應(yīng)該比較能相信。但是我們可以有多少程度的去相信這個平均值(sample m

19、ean)呢? 這個問題討論的就是所謂的Confidence Interval (信賴區(qū)間)與顯著水準(zhǔn)(significance level)。蔡文能 C/C+ 程式設(shè)計47Confidence Interval? (2/2)在實(shí)務(wù)上，想要在有限個模擬數(shù)據(jù)結(jié)果中得到一個較完美接近真實(shí)結(jié)果的數(shù)據(jù)，其實(shí)是不可能的。因此我們能做的就是去求得一個機(jī)率範(fàn)圍(probability bound)。若我們可以得到一個機(jī)率範(fàn)圍的上限c1和一個範(fàn)圍的下限c2，則就有一個很高的機(jī)率1 ，會使得每次所得到的模擬結(jié)果平均值(sample mean)都落在c1到c2的範(fàn)圍之間。Probability c1 = = c2

20、= 1 我們把(c1, c2)這個範(fàn)圍稱為信賴區(qū)間(confidence interval)；稱為顯著水準(zhǔn)(significance level)；100(1-)%稱為信心水準(zhǔn)(confidence level)，用百分比表示；1-稱為信心係數(shù)(confidence coefficient)。蔡文能 C/C+ 程式設(shè)計48為何簡單隨機(jī)抽樣是個合理的抽樣方法？ 試想抽取16所醫(yī)院來預(yù)測393所醫(yī)院的平均出院病人數(shù)的例子，共有約1033種的不同樣本。依據(jù)中央極限定理，所得到的平均出院病人數(shù)分佈像個鐘形曲線，其中心位於所有醫(yī)院的平均出院病人數(shù)，且大多數(shù)的16所醫(yī)院平均出院病人數(shù)都離中心(大數(shù)法則)不

21、遠(yuǎn)。 較有保障的抽樣辦法，被選取的樣本應(yīng)使用隨機(jī)的原理取得。蔡文能 C/C+ 程式設(shè)計49Hypothesis Testing假設(shè)之檢定The null hypothesis for the test is that all population means (level means) are the same. (H0)The alternative hypothesis is that one or more population means differ from the others. (H1)蔡文能 C/C+ 程式設(shè)計50PRNG 相關(guān)補(bǔ)充請用 打 “PRNG” 查看ANSI X9.

22、17 PRNG (PRNG = Pseudo Random Number Generator)Von Neumann 想出的 middle square methodVon Neumann architecture ?PRNG in RC4 (RC4用於 802.11 無線網(wǎng)路加解密)http:/www.wisdom.weizmann.ac.il/itsik/RC4/rc4.htmlWEP : RC4 Stream cipher蔡文能 C/C+ 程式設(shè)計51ANSI X9.17 PRNGUse 3DES and a key KTi = Ek(current timestamp)outputi

23、= Ek(Ti seedi)seedi+1 = Ek(Ti outputi)WeaknessesOnly 64 bits are used for Tiseedi+1 can be easily predicted if state compromise蔡文能 C/C+ 程式設(shè)計52Jon von Neumann 1946 suggested the production of random number using arithmetic operations of a computer, middle square, square a previousrandom number and ex

24、tract the middle digits, Example generate 10-digit numbers, was 5772156649, square 33317792380594909201the next number is 7923805949Middle squaremiddle square has proved to be a comparatively poor source of random numbers. If zero appear as a number of the sequence, it will continually perpetuate itself.蔡文能 C/C+ 程式設(shè)計53Von Neumann architecture (/)The term von Neumann architecture refers to a computer design model that uses a single storage structure to hold both programs and data. The term von Neumann machine can be used to descr