IT牛人博客聚合

要说起RSA算法的话就不得不提欧拉这个伟大的数学家，他在数学的很多方面都有很多研究，而RSA也正是基于他在数论上的欧拉公式才建立起来的。欧拉公式稍后再说，先简单说一下公钥密钥的非对称算法的概念，平常我们用的加密算法往往都是对称的，也就是说加密密钥和解密密钥是一样的，比如凯撒密码，你把每个字母后移3位，a变成d，b变成e，这里3就是加密密钥，然后解密的时候前移3位，这时候3就是解密密钥，非对称加密顾名思义就是加密密钥和解密密钥是不同的，恩，数学就是能干很多神奇的事情啊。

数论在很长的一段时间里被认为是没用的，纯数学的，优美的理论，一直到1976年。当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人提出了公开密

查看全文: http://www.udpwork.com/item/7123.html

相对于英文而言，中文在计算机处理方面有个必须要面对的问题就是中文分词，英文的单词都是空格间隔的，而中文的词语则不同，所以用程序解决中文分词，在很多自然语言处理方面都是首要进行的步骤。

其中最简单的就是最大匹配的中文分词了，比如“今天天气不错”可以分词为“今天/天气/不错”，但是面对一些有歧义的句子时却显得捉襟见肘，于是“南京市长江大桥”就会被分成“南京市长/江/大桥”而不是“南京市/长江/大桥”，于是更好的是基于统计学原理的分词，也就是说看哪种出现的频率更高。
对于一个中文字符串“a1a2a3...an”如何正确的用词语c1,c2..cm表示就是中文分词的任务，也就是说我们要去找寻P(c1c2..cm)最大的分词，按照马尔科夫链

查看全文: http://www.udpwork.com/item/7003.html

在计算机科学里，有时间复杂度的概念，然后就有P,NP,NPC,NP-hard的概念，平常大家说的这个题是np的，只能搜了，其实是理解错了np的概念，首先要明确np并不是“不是p”的意思，p大家都清楚是指有多项式时间的算法，而np看全称是“nondeterministic polynomial time”，是说非确定多项式时间，进一步说，正如图片上说的p是属于np的，所有p问题都是np问题。

ok，下面仔细说一下，按照官方的解释呢
p是指在多项式时间能由确定型图灵机解决的问题
np是指在多项式时间能由非确定型图灵机解决的问题
确定型图灵机可以理解为就是按照某种固定的算法，一步步求出解的程序，而非确定型图灵机其实是概念上的，他的

查看全文: http://www.udpwork.com/item/6876.html

现在越来越多的网站开放api了，而且大部分都用了OAuth的认证方式，对于没接触过OAuth的人来说一开始理解起来感觉很困惑，觉得这个东西很麻烦，这篇文章就简单的从什么是OAuth，为什么要有OAuth，OAuth的认证流程，以及OAuth为什么要这样设计来谈一下。但是鉴于现在OAuth都已经有2.0了，但是2.0却不兼容1.0，而2.0主要依赖的是https，所以这里还是主要是来讲OAuth1.0的，确切的说是OAuth1.0a的。

什么是OAuth

当你进入OAuth的官网，就能看到那句最醒目的描述
An open protocol to allow secure API authorization in a simple

查看全文: http://www.udpwork.com/item/6706.html

看到网上一些对于md5的介绍还有对于当初王小云所做的破解有很多的误解，或者说不理解，然后觉得对于这些事情只要说明白还是比较好理解的说。

首先md5其实就是一种hash，或者叫散列函数，有的地方叫杂凑函数，都是一个东西啦，其实他就是一种映射，而平常最常见的就是说md5是不可逆的，为什么不可逆呢，有人就说就是像有些函数没有反函数那样了，其实还是有点抽象，考虑md5是多对一的映射，也就是说很多不同的经过md5变换之后可能会是相同的，那么既然多对一，自然是不可逆啦╮(╯▽╰)╭，你怎么会知道他到底是由哪个变换过来的呢。在密码学的应用里，说是单向函数，或者说单向变换，一种是这种多对一不可逆，还有一种是说逆工程会非常困难，举个例子吧，假设f

查看全文: http://www.udpwork.com/item/6638.html

    去年年初的时候，我曾经发布过某专业课期末作业研究过程中带来的一个有趣的副产品：汉字的字义网络图。不过，当时我是直接调用的 Mathematica 的相关函数，函数几乎不能调整参数，并且也无法处理边上权重不同的情况。最近在研究引力斥力绘图算法，突然想到把当时的数据重新画一张图。于是就有了汉字地图第二版（点击小图看大图）：

   

    还是简述一下整个图的制作方法吧。我们的基本依据就是，在全唐诗中，经常对偶的字往往都有非常密切的关系。于是，我们首先找出全唐诗中的对偶字：

   &n

查看全文: http://www.udpwork.com/item/6387.html

本文属于概率与测度系列。

在本系列的上一篇文章中，我偷偷留了一个问题：为什么具体试验所得到的频率是趋向于该事件的概率的。这个问题似乎是显而易见的，但是仔细想想似乎也并不显然，并不能一下子得出这个结论来。事实上，历史上有以这个性质作为基础来构建概率论的理论体系的尝试，不过在现在的概率论公理化体系下面，这个可以作为一个结论推导出来，具体来说，它是大数定理的一个特殊情况。不过如本文标题所说，这次只是闲扯，因为我们目前的进度还没有到大数定理那里，所以就不仔细介绍众多形式的大数定理了，下面只给一个常见的形式，并且暂时省略证明：

定理 1 (大数定理)：设 $\{X_i\}_{i=1}^n$ 是一列独立同分布的随机变量，且期望 $\mu=\

查看全文: http://www.udpwork.com/item/6111.html

    昨天和同事聊到，汉语还真是奇怪，有“四分五裂”，有“五颜六色”，也有“七上八下”，但好像从没听说过六什么七什么的。于是想到，在汉语中，“数词 + 非数词 + 数词 + 非数词”的短语是怎样分布的呢？回到家后立即用 Mathematica 做了一个柱状图，绘出了九九八十一种数词短语模式在大规模真实语料中的出现频数。注意，这里统计的是总的出现频数，重复出现也会计算在内。另外，这是一个简单而机械的统计过程，因而 “三人一组”、“七天七夜”之类的非成语也被算了进来。

      

    嗯

查看全文: http://www.udpwork.com/item/6079.html

今天，我拿到了梦寐以求的大规模中文语料库，总大小超过 1 G ，覆盖了各个时代各种文体的中文资料。有了这个语料库后，我便能完成很多早就想做的事情，比方说，统计各种文体中出现频率最高的四字词。给定一段文本后，基本的统计过程如下：

  1. 统计所有连续四字的出现频数；

  2. 按频数对所有四字组合从高到低排序；

  3. 删掉所有包含非汉字字符（比如数字、标点）的四字组合；

  4. 删掉明显不成词或者不成词组的四字组合（这一步有人为因素，因此下面的数据并不是 100% 客观的）；

  5. 列出频数最高的 10 个四字词。

查看全文: http://www.udpwork.com/item/5973.html

恩，上图就是大名鼎鼎的莫比乌斯环，估计大部分人听到莫比乌斯这个名字首先想到的是这个吧，不过和今天讲的Möbius inversion，即莫比乌斯反演没有多大关系，不过他们都是指的一个人，德国数学家、天文学家莫比乌斯。那下面我们就来说莫比乌斯反演了。

当初看到这个东西的时候，应该是在一本组合数学书上看到的吧，当时只见到公式非常的犀利，还在迷糊的情况下，套公式做了几个题，真是非常的囧啊。话说莫比乌斯怎么高深的名字是什么东西呢，浅显一点说，其实就是容斥原理！
容斥原理应该都很清楚的吧

假设我们要求P(A∪B∪C)，但是我们现在只知道P(A)，P(B)，P(c)，那么P(A∪B∪C)=P(A)+P(B)+P(C)-P(A∩B)-(B∩

查看全文: http://www.udpwork.com/item/6397.html

本文属于概率与测度系列。

系列的前面两篇大致陈述了一下测度论方面的基础，由于这个学期有去旁听《概率论》这门课，所以主要还是按照课程进度来吧，不定期地把课程里一些有意思的内容抽取出来整理在这里。这次就说概率模型。

先从一个例子开始，比如一个盒子里放了 8 个黑球和 2 个白球，从盒子里随机拿一个球，问它是白球的概率是多少，大家都会不假思索地说，1/5 。的确，这似乎是很显然的，不过，实际上我们是用了一个模型来进行概率分析，但是由于这个情况实在太简单了，我们根本就没有注意到模型的存在性，但是换一个稍微简单的例子，要忽略模型“走捷径”有时候就会一下子想不清楚了。比如两个人各掷一个骰子，问 A 得到的点数比 B 大的概率。这个问题就比刚

查看全文: http://www.udpwork.com/item/5901.html

话说你看到这幅图是不是感觉很坑爹啊，这不是连分数吗，怎么会跟期望问题有关咧，其实吧，在一些可能会出现无限步骤的求期望的问题中，他们的思想还是有些类似的。

先看这个连分数的求法，略去1+1/的那部分看剩下的，假设剩下的是x那么整个式子是=1+1/x的，那么x=2+1/x，然后解一个一元二次方程，然后这个式子显然是正的啊！所以x=1+sqrt(2)，最后求得答案是1+1/x=srqt(2)

下面来看这个期望问题，从A退出的概率是1/2，从A到B的概率是1/2，从B退出的概率是1/2，从B到A的概率是1/2，问从A到退出期望会走几步，也就是说平均走几步才能出去。
标准的做法是用每一个的步数乘以概率然后加起来，就是0*1/2+1*(1

查看全文: http://www.udpwork.com/item/6398.html

忘记了之前在哪里看到说数学其实就是同义反复而已。从某种程度上来说，这样的言论也不能说完全是乱说，比如一系列的等价的推导，其实可以说就是在说同一件事情。但是“同义反复”多少有些贬义的意思，具体来说应该是指“不必要的反复”吧，但是数学应该不是这样吧。实际上，来考虑一下什么样的“反复”是“不必要的反复”就可以了，我觉得，那些只要是“不太明显” (non-obvious) 的关系，把这样的关系建立起来，应该也都是有其意义的，而尤其重要的是其中那些“深刻”的关联。

不过“深刻”这样的词是不是太抽象了呢？实际上，最近一年一来，接触了些数学专业的人，在同他们讨论问题的时候——好吧，其实大部分时候是我在听他们讲问题的时候——“深刻”这个词便时常在

查看全文: http://www.udpwork.com/item/5781.html

Klein Bottle

参加暑期讨论班其中有一场是我讲，第一次这样子讲数学的东西，有点紧张，于是先在这里整理一下。内容大致是拓扑空间的紧性。

关于空间的紧性，我们在之前的分析中已经见过了：例如在实数轴上的有界闭区间就是典型的紧集，紧集具有很多优良的性质，比如我们知道在有界闭区间上的连续函数一定是一致连续的，并且能取到最大值和最小值。所以，在将空间的概念推广到一般的拓扑空间之后，我们也希望将紧性这一优良性质也带到拓扑空间中来。为此，我们需要找到什么是紧集最本质的东西。在实数轴上的紧集 $K$，有如下的一些等价刻画：

$K$ 是有界闭集

$K$ 的任意无限子集必存在极限点

$K$ 中的任意序列必有收敛子列

$K$ 的任意开

查看全文: http://www.udpwork.com/item/5531.html

本文属于概率与测度系列。

我又来挖坑了。因为打算抽时间（比如下学期或者下下学期）来学一下概率论，所以学习过程中的一些感想或者笔记什么的应该会不定期地整理出来。这算一个开头吧。

其实概率论似乎经常处于一个比较尴尬的地位，在历史上一度被认为并不属于数学的一部分，直到将测度论引入以建立起严格的公理体系之后，才被数学界所承认。当然，说它“不是数学”，仅仅就是字面上的意思，并没有说什么东西不是数学就一定是不好的。事实上，在被严格化之前，概率统计作为一种工具就已经被广泛应用到各个领域中了，当然，在严格的理论体系建立之后，不论从理论上还是应用上，都得到了爆炸性的发展。然而，仅从大学的教育来看，概率论似乎仍然处境尴尬。

比如在 ZJU 本科，

查看全文: http://www.udpwork.com/item/5084.html

    先给大家看两个“单词等式”：

ACT + DEAL = DONE

COIN + TRY = DIAL

    除了意义上说得通以外，从另外一个角度来看，这两个等式也是成立的。大家能猜到是什么吗？

 

    答案是：这两个等式真的就是成立的——如果把单词看作 36 进制数的话。把 ACT 转换成 10 进制就是 13421 ，把 DEAL 转换成 10 进制就是 625053 ，而 DONE 的 10 进制正好就是 638474 。类似地， COIN 加 TRY 也真的等于 DIAL ，

查看全文: http://www.udpwork.com/item/4941.html