理论计算机初步:前言

作者: , 共 620 字
系列:理论计算机初步

查看该系列所有文章

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

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

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

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

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

Q. E. D.

类似文章:
相似度: 0.133
姚期智教授给清华大学新入学研究生开的一门课,课程内容:
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分 ——hash 函数,以及王小云老师在这上面的工作。
前面 已经提到了显示中大多数难解问题问题最后都被证明是 NP- 完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在 这篇文章 提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
这是由 CBC (加拿大广播公司)与 New York Times 等合作历时两年制作的纪录片。片子相当诚实地反映了中国的现实 。一方面,中国的变化令人眩目,另一方面,繁华的背面却是满目苍夷,问题重重。