小土刀

计算机科学的角落

计算机科学中未解决的问题有多少?计算机科学的先锋式人物都有谁?为什么 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 最著名的奖项莫过于图灵奖,也就是计算机科学界的诺贝尔奖了,如果想了解更多,可以在参考链接中找到对应的信息。

小结

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

参考链接

捧个钱场?

热评文章