计算机科学的角落 · 小土刀 5.0

计算机科学中未解决的问题有多少？计算机科学的先锋式人物都有谁？为什么 ACM 在计算机科学中是非常特别的缩写？这次我们就来了解一下这些平时放在角落的小知识。

未解决的问题

未解决的问题有很多，这里只列出我稍微了解的两类，真的是抛砖引玉，希望天才们来创造奇迹。

计算复杂性问题

这类问题比较抽象也偏数学，大部分是形如 P=NP 这样的问题，因为这部分我了解的不多，这里简单搬运一下维基的列表

P = NP 问题，可谓是信息论中的桂冠，但是至今无人摘下，是七个千禧年大奖(Millennium Prize Problems)难题之一（具体的问题可以在参考链接中找到）
NC = P 问题
NP = co-NP 问题
P = BPP 问题
P = PSPACE 问题
L = NL 问题
L = RL 问题
BQP 和 NP 的关系是什么
Unique Games Conjecture
指数时间假说是真的吗
单向函数存在吗（一个例子是，公钥加密算法可能吗）

算法问题

算法部分主要是跟乘法以及数论有关，这部分往往按照传统的方式计算复杂度较高，有很大的优化空间

两个 n 位数相乘速度最快的算法是什么？这个涉及到 CPU 中运算器的实现
矩阵乘法算法速度最快是什么？这个在许多图形相关以及向量相关的计算中都有涉及，但是现在想要提高一点点都很难
可以在多项式时间内做质因数分解吗
可以在多项式时间内计算离散对数吗
可以在多项式时间内解决图同构问题吗
可以在多项式时间内解决奇偶校验问题吗
快速傅里叶变换算法的复杂度的上下限是什么
可以在平方时间内解决 3SUM 问题吗
K 服务器问题
X + Y 排序能够在 $O(n^2log n)$ 时间内完成吗

计算机科学先驱

我们来考考古，看看历史上对计算机产生过深远影响的人。更多内容请查看维基百科（下面的参考链接有），这里按照个人喜好进行了筛选。

拉蒙·柳利(Ramon Llull, 1300~): 计算理论的先驱，影响了莱布尼茨等人
布莱兹·帕斯卡(Blaise Pascal, 1642): 发明了机械式计算器
戈特弗里德·莱布尼茨(Gottfried Leibniz, 1670~): 对二进制发展、符号逻辑和形式逻辑做出了贡献
查尔斯·巴贝奇(Charles Babbage, 1837): 提出差分机与分析机，被视为计算机先驱
艾达·洛夫莱斯(Ada Lovelace, 1843): 公认的第一位计算机程序员
乔治·布尔(George Boole, 1854): 在符号逻辑运算中做出突出贡献，很多计算机语言中把逻辑运算称为布尔运算，结果称为布尔值
赫尔曼·何乐礼(Herman Hollerith, 1889): 现代机械数据处理之父，随着他发明的制表机，自动数据处理的时代开启
阿兰·图灵(Alan Turing, 1936): 计算机科学与人工智能之父
克劳德·香农(Claude Shannon, 1937): 信息论、数字计算机理论和数字电路设计理论的创始人
约翰·冯·诺依曼(John von Neumann, 1945): 现代计算机与博弈论的重要创始人
诺姆·乔姆斯基(Noam Chomsky, 1956): 生成语法是理论语言学研究上的重要贡献，建立了乔姆斯基层级
道格拉斯·恩格尔巴特(Douglas Engelbart, 1963): 鼠标的发明者，所在小组是超文本系统、网络计算和图形用户界面的先驱
马文·闵斯基(Marvin Minsky, 1963): MIT 人工智能实验室的创始人之一，奠定了人工神经网络的研究基础
高德纳(Donald Knuth, 1968): 现代计算机科学先去，创造了算法分析的领域，在数个理论计算机科学的分支做出基石一般的贡献，《计算机程序设计艺术》，TEX 的发明人

计算机协会

计算机协会(Association of Computing Machinery, ACM)创立于 1947 年，是世界上第一个科学性及教育性计算机协会。下设许多特别兴趣组(Special Interest Group, SIG)，在计算机科学的各个领域起着不可忽视的作用，比方说搞图形的 SIGGRAPH，搞人工智能的 SIGAda 等等。这些小组也会举办各类会议，也就是我们常说的『顶会』，能在这上面发论文，是许多科研人员的梦想。

ACM 最著名的奖项莫过于图灵奖，也就是计算机科学界的诺贝尔奖了，如果想了解更多，可以在参考链接中找到对应的信息。

小结

这一部分实际上是为自己的新书所收集的一部分『边角料』，我觉得每一个入门，或者热爱计算机学科的同学，都应该了解一下整个学科发展的历史和著名人物，从中获取到比知识还重要的养分，那就是『勇气、创造、坚持和热爱』。不过话说回来，干什么都离不开这四点吧。