理论计算机初步：前言

作者: 张志强 , 2006-08-15 , 共 590 字 , 共阅读 0

系列：理论计算机初步

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

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

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

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

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

Q. E. D.

系列：理论计算机初步 »

后一篇：理论计算机初步：算法和计算模型

2006-08-16, 计算机科学 » 理论计算机, 理论计算机初步

下面是 wikipedia 上算法的定义：

类似文章：

理论计算机初步：算法和计算模型相似度: 0.161

2006-08-16, 计算机科学 » 理论计算机, 理论计算机初步

下面是 wikipedia 上算法的定义：

理论计算机初步：P vs NP - 问题概述相似度: 0.137

2006-08-23, 计算机科学 » NP, NP Complete, P vs NP, 理论计算机初步

P = NP?

理论计算机初步：从 hash 函数到王小云的 MD5 破解相似度: 0.136

2006-09-18, 计算机科学 » hash函数, MD5, SHA-1, 密码学, 王小云, 理论计算机初步

密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作，不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》，在媒体上又掀起了一轮宣传狂潮，但是有些报道极端弱智，错误百出，所以我趁机纠正一下，并介绍密码学的一个组成部分——hash 函数，以及王小云老师在这上面的工作。

高等理论计算机 I 相似度: 0.135

2008-09-19, 计算机科学 » 量子信息, 量子计算, 高等理论计算机

姚期智教授给清华大学新入学研究生开的一门课，课程内容：

理论计算机初步：概率算法和近似算法相似度: 0.130

2006-09-14, 计算机科学 » 概率算法, 理论计算机, 近似算法, 理论计算机初步

前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着，除非 NP=P ，它们是不可能有多项式时间算法的（而且，在这篇文章提到即使 NP=P ，人们也可能找不到一个 NP 完全问题的「有效」算法）。

通讯复杂性简单介绍相似度: 0.115

2008-09-17, 计算机科学 » 理论计算机, 通讯复杂性

英文是 communication complexity ，不知道该翻译成通信复杂性，还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域，在过去 30 年衍生了很多东西。它是我的研究的主要内容，这里简略介绍一下。

理论计算机初步：P vs NP - 历史，现状和未来相似度: 0.112

2006-08-24, 计算机科学 » P vs NP, 理论计算机初步

上篇文章已经提到， P vs NP 是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中， NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。