高等理论计算机 I

作者: , 共 703 字

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

在经典计算复杂性方面: NP 完全性 ,多项式空间复杂性,对数空间复杂性,交互式证明系统, 随机复杂性 ,去随机化,概率检验证明系统,电路复杂性, 通信复杂性 ,判定树复杂性等。在量子计算复杂性方面将包括:量子计算模型,量子电路,量子 Fourier 变换算法, Shor 算法, Grover 量子搜索算法,量子纠错码,冯诺依曼墒等。

从这里可以看出理论计算机的一些主要的方向。按照姚先生的说法,这些是做理论的学生,多少都应该知道一点的东西,这样跟别人讨论的时候才不会 embarrass。Researcher 不应该局限于自己所专注的领域,眼界要开阔 ; 这也是开这门课的主要原因。

参考教材

[1] Complexity Theory: A Modern Approach, Sanjeev Arora and Boaz Barak.
[2] Quantum Computation and Quantum Information, Michael Nielsen and Isaac Chuang.
[3] Lecture nots: Quantum Computation , instructor Umesh Vazirani

这门课有 I , II 两个学期。这个学期主要讲量子计算和量子信息的一些东西吧。我恰好跟着写一些关于量子的东西放到这里,当然都是简单介绍性质的,目的是大家看了之后,对一些 NC 的东西有简单的辨别力,比如新浪科技的这篇 瑞士实验显示量子信息传输速度远超光速

Q. E. D.

类似文章:
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是 Andrew Yao 的研究方向
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了 NP 问题 一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
编程 » 算法, 算法分析
下面这个求 \( 1/\sqrt{x}\) 的函数号称比直接调用 sqrt 库函数快 4 倍,来自游戏 Quake III 的源代码。