白菜的博客

作者：郑凯
版权声明：可以任意转载，转载时请务必以超链接形式标明文章原始出处和作者信息
http://soulogic.com/archives/400

阅读剩余部分...

恰逢一童鞋跟我提到数学学习的话题，让我绘一副思维导图。
下手才知数学的博大精深，自己的浅薄。
花了三个多小时，才绘制出这么一副简陋的导图，希望读者能从中了解到数学的一个基本轮廓，以及计算机和数学是怎么结合的。
由于本人所知有限，定有很多重要知识点的遗漏，不过可以管中窥豹，举一反三~~
不过这图画着画着就偏离本意了，导向图不像导向图，将就着看吧，就当头脑风暴图看吧，哈哈
图片很大，请另存到本地再看（主要由于水平和精力有限，无法补全，所以图形很不对称，呵呵）。

我看到了它，却不敢相信它^[1]。

康托尔

计算机是数学家一次失败思考的产物。

——

哥德尔的不完备性定理震撼了20世纪数学界的天空，其数学意义颠覆了希尔伯特的形式化数学的宏伟计划，其哲学意义直到21世纪的今天仍然不断被延伸到各个自然学科，深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型，进而作出了可计算理论和现代计算机的奠基性工作，著名的停机问题给出了机械计算模型的能力极限，其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐，跟图灵同时代的天才，则从另一个抽象角度提出了lambda算子的思想，与图灵机抽象的倾向于硬件性不同，丘齐的lambda算子理论是从数学的角度进行抽象，不关心运算的机械过程而只关心运算的抽象性质，只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型，其体现出来的数学抽象美开出了函数式编程语言这朵奇葩，Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界，虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言^[2]，然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…

阅读剩余部分...

概率论只不过是把常识用数学公式表达了出来。

——拉普拉斯

记得读本科的时候，最喜欢到城里的计算机书店里面去闲逛，一逛就是好几个小时；有一次，在书店看到一本书，名叫贝叶斯方法。当时数学系的课程还没有学到概率统计。我心想，一个方法能够专门写出一本书来，肯定很牛逼。后来，我发现当初的那个朴素归纳推理成立了——这果然是个牛逼的方法。

——题记

目录

0. 前言
1. 历史
    1.1 一个例子：自然语言的二义性
    1.2 贝叶斯公式
2. 拼写纠正
3. 模型比较与贝叶斯奥卡姆剃刀
    3.1 再访拼写纠正
    3.2 模型比较理论（Model Comparasion）与贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor）
    3.3 最小描述长度原则
    3.4 最优贝叶斯推理
4. 无处不在的贝叶斯
    4.1 中文分词
    4.2 统计机器翻译
    4.3 贝叶斯图像识别，Analysis by Synthesis   
    4.4 EM 算法与基于模型的聚类
    4.5 最大似然与最小二乘
5. 朴素贝叶斯方法（又名“愚蠢者的贝叶斯（idiot’s bayes）”）
    5.1 垃圾邮件过滤器
    5.2 为什么朴素贝叶斯方法令人诧异地好——一个理论解释
6. 层级贝叶斯模型
    6.1 隐马可夫模型（HMM）
7. 贝叶斯网络

阅读剩余部分...

    昨天晚上半夜三更，一个PHP群里有人问起大数阶乘的计算。我忙于看书，再者我一向秉持大晚上的讨论技术不吉利的观念，也就没有回答了。对于比较小的数，可以用定义计算
$num=range(1,100);
echo array_product($num);
这个谁都会，但是当N比较大的时候，就是DOUBLE类型也无法保存计算结果了。有人说。拆开来，一段一段的算，这是错的。你想过没，你即使拆成了很多段，但是到最后，还是不得不把中间结果相乘，又卡在了超大数相乘的地方了。
在你要计算大数阶乘的时候，我先介绍一个数学公式
①n!=10^{^}m(^表示幂，这一步大家应该都能理解，我就只是个把阶乘表示成幂指数的一个等式，这里我要算M的值)
②对两边取10为底的对数。log₁₀n!=log₁₀ 10^{^}m=m，这一步我们就把M求出来了。
③左边利用对数的积化和公式，有
log₁₀n!=log₁₀n*(n-1)*(n-2)*(n-3)...*2*1=log₁₀n+log₁₀(n-1)+....log₁₀3+og₁₀2=M
到这里，我们就把M求出来了，那M有啥用呢？M实际上就是n!的精确位数，对于强类型语言，可以用M来开辟内存空间，对于弱类型语言，不像C那样数组大小必须指定，但是我们可以判断大概多大的数运算后位数是多少，如果位数不超过其所能表示的最大数值范围，就用内置的函数或定义来直接计算。就如PHP，直接用array_product来计算成乘积。（我看到群里的那个同学用的range(1,172)做例子，我估计他是一步一步测出来的，到了172的阶乘就溢出无法表示了）N比较大了，就只能模拟乘法了。
在小学的时候，我们都学过乘法，149*7，我们是这么做的：
①9*7=63 进6写3，7*9/10=6,7*9%10=3
②4*7=28，加6等于34，进3写4；
③1*7=7,7+3=10，进1写0
最终结果就是1043
小学生都会吧，反正我们小学就是教我们这么做的，口诀也是这么背的。
你让小学生计算465768233434545*1112574233，小学生都会计算，只是比较耗时间而已。
对的，我们就是要做一回小学生，来模拟这个过程。
a*b%10 就是我们每一步乘法的个位，而a*b/10就是每一步的进位，也就是10位（每一位对于数相乘结果最大为9*9=81，不超过两位）
下一位的结果加上进位，求出个位，求出进位。。。循环执行。
只不过这个阶乘比较麻烦，两个乘数都大一1位，149*7我们会了，那149*34567，运用小学数学的思维，先149*7，再149*6.。。嵌套循环而已。1000！那最大的运算也不过1000*999，其中真正最大的无非是999*998，最大的乘法是999*9，太小了，10000000！最大的乘法单步骤也不过是9999999*9，太小了！还有什么我们计算不出来的。只不过循环次数多了，慢一点而已。
这就是大数相乘，模拟成单步相乘，那就简单了。其实也就是模拟成字符串。我们把所有的数字都放在数组里，一个一个取出来运算。如果你还看不懂，那就先直接去看看大数相乘的原理吧。
代码我就不贴了，百度一对堆，不过原理你得清楚。比如说把C语言写的转成PHP，我看好你。

1.一个机器洗牌时总是以相同的方式打乱牌的顺序。把

   A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K

放进去，用机器连续洗两次牌之后，顺序变为了

   10, 9, Q, 8, K, 3, 4, A, 5, J, 6, 2, 7

求机器第一次洗牌之后的顺序。

2.假设 P(x) 是一个 8 次多项式，且 P(1)=1, P(2)=1/2, P(3)=1/3, ..., P(9)=1/9 。求 P(10) 。

3.已知一个数列的前7项，请写出完整的14项。
1, 2, 4, 6, 3, 9, 12.。。。

阅读剩余部分...

刚才看到这个很漂亮的无理数 e 的近似表达，它恰好用到了 1 到 9 这 9 个数字。
    猜猜看它能精确到 e 的小数点后多少位？ 10 位？ 100 位？ 1000 位？ 10000 位？

    远比想象中的牛 B —— 它能精确到小数点后 18, 457, 734, 525, 360, 901, 453, 873, 570 位！显然，这绝对不是一个巧合。它的秘密就在于， e 事实上等于 lim(n→∞) (1 + 1/n)^n ，而 9^(4^(7·6)) 恰好就等于 3^(2^85) 。这个指数相当大， Mathematica 直接就报 Overflow 了，难怪它能精确到 e 的小数点后那么多位。

    据说，这个神一般的近似表达最早来源于这里。

这两个题网上都有，我只是整理了下，顺便提出了自己的一些思路

小题目1：
现有长为144cm的铁丝，要截成n小段(n>2),每段的长度不小于1cm,
如果其中任意三小段都不能拼成三角形，则n的最大值为?

小题目2：
对于给定的三个正整数a,b,c，计算a的b次方除以C的余数。
a=452，b=23166，c=29875

对于题目1，关键是临界条件就是两边之和等于第三边。

两边之和等于第三边,可以理解为f(n-2)+f(n-1)=f(n)[n>=3].
斐波那契数列出来了，然后此题解答完毕。
由于斐波那契数列存在黄金分割，1.618^10~=144.
答案是10.
echo  floor(log(144)/log(1.618)); 

阅读剩余部分...