理论计算机初步:前言

作者: , 共 590 字 , 共阅读 0
系列:理论计算机初步

查看该系列所有文章

我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向

  • Analysis of Algorithms - 算法
  • Computational Complexity - 计算复杂性
  • Communication Complexity - 通讯复杂性
  • Cryptographic Protocols - 密码
  • Quantum Computing - 量子计算

这些概括了理论计算机的大部分内容。

在后面的系列文章中,我会对其中一些方面写一些具体的东西。因为我也才刚入门,而且这样的类科普性的东西,无论怎么写,在专业人士看来,总有不够严密的地方。所以,我只写一些最简单的东西,让大家都能看得懂为止,但又能对于这一领域能有一些最基本的了解。如果还能引发一些人的兴趣,更为妙哉。

顺便做一下广告:我所在的理论计算机研究小组,隶属于清华高等研究中心,目前有姚期智王小云两位老师坐镇,其中姚期智是 2000 年计算机界最高奖 Turing 奖获得者,而王小云教授在密码学界享有盛名,另外还有大帮讲席教授,师资力量世界上都排得上号。如果有对理论计算机感兴趣的同学,这个小组将是你的不贰选择哈。目前,此小组只接受保送直博生,而且需要你在大三下学期就提出申请。欢迎加入。

Q. E. D.

类似文章:
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分——hash 函数,以及王小云老师在这上面的工作。
相似度: 0.136
姚期智教授给清华大学新入学研究生开的一门课,课程内容:
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》
投资 » 低风险投资
我是最早从《低风险投资之路》中听到「低风险投资」这个词。这本书的作者从 2005 年开始,将所有家庭资金投入到股票市场,采用低风险投资的方式,至今总收益率已超过 10 倍。
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
这是由 CBC (加拿大广播公司)与 New York Times 等合作历时两年制作的纪录片。片子相当诚实地反映了中国的现实 。一方面,中国的变化令人眩目,另一方面,繁华的背面却是满目苍夷,问题重重。