系列： 理论计算机初步

这是我在读博士期间（ 2005 年 9 月到 2009 年 7 月）写的对理论计算机的介绍文章，当初雄心勃勃地想对这个领域做一个全面的介绍，后来受到水平和时间的限制，只写了少数几篇，只介绍了一些 P/NP 和算法的最基本的概念。

  1. 计算机科学 » hash函数, MD5, SHA-1, 密码学, 王小云, 理论计算机初步
    密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作，不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》，在媒体上又掀起了一轮宣传狂潮，但是有些报道极端弱智，错误百出，所以我趁机纠正一下，并介绍密码学的一个组成部分——hash 函数，以及王小云老师在这上面的工作。
  2. 计算机科学 » 概率算法, 理论计算机, 近似算法, 理论计算机初步
    前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着，除非 NP=P ，它们是不可能有多项式时间算法的（而且，在这篇文章提到即使 NP=P ，人们也可能找不到一个 NP 完全问题的「有效」算法）。
  3. 计算机科学 » P vs NP, 理论计算机初步
    上篇文章已经提到， P vs NP 是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中， NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。
  4. 计算机科学 » NP, NP Complete, P vs NP, 理论计算机初步
    P = NP?
  5. 计算机科学 » 理论计算机, 理论计算机初步
    下面是 wikipedia 上算法的定义：
  6. 计算机科学 » 姚期智, 王小云, 理论计算机初步
    我所学的专业英文名是 Theoretical Computer Science ，理论计算机科学，在这里我就简化成理论计算机了。具体研究些什么呢，下面是Andrew Yao的研究方向