这页要说“计算机科学理论与图论”的关系(其中的图论是狭义的组合数学。麻省理工学院SS院长Michael Sipser院士说彻底改变世界计算机第一难题P=NP?只有依靠我们的组合数学--麻省理工学院不仅续五年世界第一而且全球计算机科学家。下面也将见世界首富比尔·盖茨的成功也有他在组合数学打下基础之因。这依重组合数学的Michael Sipser院长可是依次掌管着世界第一大学的“生物部”、“大脑与认识科学部”、“化学部”、“地球,大气和行星科学部”、“数学部”、“物理部”,特别是麻省理工单就计算机AI实验室就有112个教授是哈佛CS的几倍(Sipser院士《计算理论导引》也是世界名著,而MIT计算理论组仅有26个教职员却有3个诺贝尔奖获得者还有这里说最应该获得物理诺贝尔奖的Peter Shor和他的三院院士导师等,更奇的还是有合写哈密顿图论文的Erik DemaineMartin Demaine父子教授),他的高瞻远瞩也正如这里一个领域的作用就够统治世界。此外,关于大数据已如最著名的舍恩伯格说“大数据时代已来临,而大数据分析就用到数学特别是图论、统计等,有时也会用计算机科学理论”,如此关于大数据就有信息部牵头的20多个院士部长省长等的学会、还有审计等十几的部的、计算机学会的、中国工程院的、农业的等等创办的很多学会趋之若鹜…。大数据主要通过传感器收集处理--社会网络上的也大多是基于它--琼州大学就是这里最后美国主编的传感器图论杂志编委。可见在这个已来临的信息时代--数学的作用是越来越广泛越重要,可这里首页见琼大20多个学院而数学系。下面先借得主Hopcroft的关于前后40年之说来简述本页主题:

1、数学推动的前期的“计算机科学理论与图论”关系。在网上见Umesh堪称计算机理论界的第二名师(计算机理论第一名师是他自己的导师Manuel Blum这计算机理论界第二名师Umesh就是Umesh Vazirani--在他的网见他发表了很多图论论文并且他在哈佛大学只指导一个博士Milena Mihail其博士学位论文也是做图论的。他的在普林斯顿以及麻省理工等任教授的博士都获Godel并他们当然也是做图论。这里不论Umesh的权威性。

而计算机理论界第一名师Manuel Blum(因名师应该是从大师和导师两方面考察,同时,计算机理论界第一名师,一般都是整个计算机界的第一名师。因为,计算机其它技术工程界很难集中出成堆顶级人才,这些领域不仅靠导师指导个人坚持更需在这方面的独特悟性)。关于第一名师,我想看了这个Blum指导的博士生网,再看下几行不能相提并论的理由,则全球计算机界应没有人敢站出来和他争计算机世界第一名师。如何说之?他,不仅是计算机诺贝尔奖得主,而且他的博士生Leonard AdlemanShafi GoldwasserSilvio Micali都是计算机诺贝尔奖-图灵奖得主Blum70年代就发表许多图论论文,他的这3个学生中前2个获得诺贝尔奖的工作都基于图论的哈密顿图,其第1Adleman的工作见我写的这个网,第2Goldwasser见我写的这个网最后段Blum不仅是名师,他的徒孙也利害,如刚见2008计算机理论界论文成果最高奖-Godel的全部2个获得者Daniel Spielman, Shanghua Teng(即滕尚华)分别是Blum的学生Michael SipserGary Miller的学生。看这2个获得者Daniel Spielman,滕尚华的个人网也见他们主要做图论。很巧的是,1993年第一届中有2Godel获得者Shafi GoldwasserSilvio MicaliManuel Blum的博士生并全部都获得计算机诺贝尔奖。其实Manuel Blum的导师Marvin Minsky也是计算机诺贝尔奖获得者,不过Blum的导师只有他一个学生获得诺贝尔奖。而诺贝尔奖得主Ivan Sutherland的论文虽有MinskyCoons做指导委员但导师是香农。还有一关系是Marvin Minsky的导师是图灵奖得主John McCarthy的师兄,而此君也有2个图灵奖学生Barbara LiskovRaj Reddy。诚然,在以前从事计算机研究的人员尚少、流派集中的时代,不能与现在人员广众、流派纷呈的时代相提并论,因以前计算机的发展主要集中于3个流派:即琼州大学的师祖-现代中国科学先驱黄际遇教授的师兄Oswald Veblen以及Solomon LefschetzHerbert Simon3个流派(这里简介这3人及作用:1琼州大学祖叔Veblen和他的博士Church做了许多计算机先驱性工作特别是培养出计算机之父人工智能之父图灵,(即widely considered to be the father of theoretical computer science and artificial intelligence是我们海南琼州大学师祖叔的博士图灵),Veblen的另一四色图论博士Franklin又培养出第一个计算机诺贝尔奖-图灵奖得主Perlis。其实这里见琼州大学祖叔Veblen1928年还聘请小他23岁的冯·诺依曼来普林斯顿(也就是冯·诺依曼其时仅是25岁的讲师,但后来在Veblen身边得到扶持学习研究并成为另一计算机之父·2Lefschetz的博士有第6个图灵奖得主McCarthy和培养的Tucker指导出第4个图灵奖得主Minsky纳什等大师Lefschetz的博士图论博士primprim算法是伟大的、另一博士Shaun Wylie更是出现代图论之父Tutte和图论大师Nash-Williams以及Adams指导出高度评价琼州大学工作的李显龙总统的老师Béla Bollobás3Herbert Simon本身是图灵奖得主并有两个学生也获图灵奖)

再多说点Manuel Blum。他有一个儿子Avrim Blum也已是计算机院士,其博士学位论文是做图论着色算法方面的,其导师Rivest70年代起就和图灵奖导师Robert Floyd、图灵奖师兄Robert Tarjan、以及图灵奖得主姚期智、上面Blum等合作发表许多图论论文。其中Robert Tarjan发表若干著名哈密顿图论文并其最利害的学生John Gilbert图论姚期智组合数学大师刘炯朗的学生,姚期智一共27个徒孙20个是博士学位论文做图论Joan Feigenbaum指导的有了计算机理论,计算机的其它领域就容易搞起来。如在我们的《离散数学》我们的“组合数学”以及计算机科学中就强调的“硬件跟着软件走,软件跟着模型走”,模型就是计算机理论模型,就是算法,正所谓:计算机科学--成也算法败也算法。如此,自计算机诞生至今,在计算机的其它领域--我想也就只有程序语言方面的一组诺贝尔奖得主师徒可与上面相比了:即图灵奖得主Niklaus Wirth介绍说导师只有Harry Huskey,但这个网见还有另一导师即图灵奖得主Feigenbaum,而此君的导师Herbert Simon既获得过诺贝尔经济学奖也获得过计算机领域的图灵奖。有一奇事是毕业于排名美国50以后的俄亥俄州立大学Harry Huskey仅有2个博士-但他们全获得诺贝尔奖

关于计算机诺贝尔奖-图灵奖得主对人才的培养,吹得最利害的是它的第一个获得者Alan Perlis。但看他的介绍的右边Doctoral students仅有3人够上维基网--而且没有一个人是美国国家或人文科学或工程院士-更不用说诺贝尔奖了。做为早期的人-应该容易做出更多引领性的开创工作啊-实在有点出乎想象吧?此君的导师就是1921年的博士学位论文做The Four Color Problem-图论的四色问题Philip Franklin。而这Philip Franklin的导师的导师E. H. Moore就是我的师祖-现代中国科学先驱黄际遇教授的导师(计算机之父图灵的师祖-即其导师Church的导师Veblen也是我的师祖黄际遇的师兄弟)。

总之,从上看之,可能Manuel Blum没有把握坐稳计算机理论界第一大师宝座。但由于他已指到出3个诺贝尔奖得主,而且看来他的另外一些博士今后也将获得诺贝尔奖。当然,名师也不能只看出诺贝尔奖,但Blum做为名师的其它方面也毫无逊色。因此这第一名师Manuel Blum还是够格坐稳的(当然,这里最后2个计算机之父:图灵和冯·诺依曼肯定是计算机第一大师,但从某些或可量化统计12比较都远远算不得第一名师,而其它无法量化的如你说培养多少个非直系的将帅-可你花多少时间精力这是别人无法量化的-只有随你说。不过,其他大师除了培养的诺贝尔奖获得者少之外,做为名师的其它方面都和Blum彼此彼此:如都是培养2个诺贝尔奖得主的Howard AikenHerbert SimonJohn McCarthyRobert FloydBlum的导师Marvin Minsky

这前40年最后要说IT产业界最值得一提的人物比尔·盖茨--从他的多次强调看这一定程度上决定于他的理论--如他成为全球首富之前在杂志发表的第一作者论文只有一篇,就是这里这篇在我们的《离散数学》杂志发表的组合数学论文(就是琼州大学报道说到的美国三院院士Papadimitriou和他的学生比尔·盖茨合作的这篇或见这里比尔·盖茨这篇论文最后说:Ervin Gyori也独立得到定里1的证明。看Ervin Gyori主页见研究Cycles in Graphs等全是图论,Cycles in Graphs主要包括海南琼大世界领先的是海南琼大世界领先的哈密顿圈,在网上也见Ervin Gyori教授师从匈牙利科学院院士Gyula Katona(就是多年之前高度评价海南琼州大学的工作并寄来很多重要资料的Gyula Katona主席)。关于离和组的关系,南开大学校长陈永川院士说离散数学又称组合数学。关于组合数学或离散数学的作用,比尔·盖茨说数学与电脑程序设计有着非常直接的关系。这一点也许在我心目中要远远胜过别人”)

2信息时代”的计算机科学理论与图论”关系又如何?刚看到计算机诺贝尔-图灵奖得主John Hopcroft撰写的名著《信息时代的计算机科学理论》(即“Computer Science Theory For the Information Age”,还没有见中文版)此书第一部分(2页)引言;第二部分(3~3735);第三部分(39~10163)讲图论的随机图;第四部分(103~13129);第五部分(133~17543)讲随机图的一个内容random walks;第六部分(177~20933);第七部分(211~23323)讲”Algorithms for Massive Data Problems”;第八部分(235~27743)用图论讲聚类;第九部分(279~29830图论模型;第十部分(299~31516)简介其它次要专题。(几乎其它部分也都要介入随机图用到我导师的教育部通过的全国3研究生教材中的probabilitystatisticsMarkov chains于其它专题)。

这书就有第七部分仅23页讲数据,但为本书作序的普林斯顿大学EWN院士几乎整个序言都说“Big Data-大数据。Hopcroft的这第七部分说的还是“Massive Data-是否有所差别?(因我在维基搜不到Massive Data)。EWN院士的序言说“Big Databring fundamental changes to our daily lives”,可见EWN院士“Big Data”就是家喻户晓的研究特点是“不是随机样本,而是全体数据;不是精确性,而是混杂性;不是因果关系,而是相关关系”,而人家这书的“Massive Data”虽然也可翻译为“大数据或大规模数据”-但从Hopcroft所用的方法看--尚不是海量数据--应是只有专业人员知道的研究特点是“随机样本、精确性、因果关系”(我虽看到很多国内论文也把Massive Data译为海量数据--但此海量可能不是Big Data意义上的海量吧)。若是EWN院士说的“Big Data”,可由信息时代的精神领袖《连线》杂志主编Chris Anderson所说“数据爆炸使得科学的研究方法都落伍了。大量的数据从某种程度上意味着理论的终结”,以及Kaggle的首席执行官Anthony Goldbloom说“在大数据项目竟赛平台上取得胜利的人通常不来自于他们做出成绩的领域”,特别是BD最著名的舍恩伯格更说“数据专家将消亡,数据分析师将崛起。他们把过去看成迷信和成规”。则若是此3人的“Big Data”-奖得主Hopcroft不要说用这23-就是几本书都讲不清楚怎么才可领先-反而只有“落伍”“终结”“消亡”…如此国外大数据书籍已多如牛毛-似乎没有一本是计算机相近领域的权威专家写的。当然做为诺贝尔奖得主,Hopcroft比一般人都更关注大数据,但在这基本技术等都莫衷一是-甚至可能把谬论邪道当主流-某些混沌因素暂时造成的当做长期潮流的时候-发声是不明智。就算EWN院士说的“Big Data”是第七部分的“Massive Data”,但也仅有23页啊,而就是Data这字母--在本书此外任何地方都没看到一次,怎用整个序说“Big Data”。然而,就是仅看上面目录就可知随机图不仅是大多数核心而且几乎贯穿全书。不过,“Big Data”倒是值得大书,而且拥有海量数据是BD根本,但在技术上是用这里最后说的云计算等平台呢还是其它难于名状的技术取胜?(就因数据比技术即处理平台、思维等更是第一位的如此我们的WS网络为大规模数据及处理原本重在传感器和处理器等是多分布式和并行计算设计等)

得主John Hopcroft在引言已说本书及这学科的中心就是第三部分的随机图及处理随机图的方法。可EWN院士的几乎只说是“大数据”,只用最后5行列出包括随机图及其它十几个本书讲的专题。在这5行前的最后一句是“It centers upon the probabilistic approach, rather than the traditional discrete mathematics set of ideas,而Hopcroft在引言说“.This book to cover the theory likely to be useful in the next 40 years just as automata theory, algorithms and related topics gave students an advantage in the last 40 years. One of the major changes is the switch from discrete mathematics to more of an emphasis on probability and statistics and numerical methods”。如此,我要为我们组合数学也叫discrete mathematics讨回它的地位。我想EWN院士写序言应先看本书吧,至少应看人家的第一部分仅2页的引言吧。是我的理解错吗?因我也只粗略地看一遍这几部分,这书的其它方面都没有看。

再说随机图,南开大学校长陈永川院士在这里第6我们来学随机图的有100多人Bollobás教授靠一个人就成了全世界随机图的领袖。剑桥大学Bollobás英国皇家学会院士,他独立指导的博士生获得1998年数学界诺贝尔奖-Fields奖。美国数学会的《数学评论》曾请我评论他的一篇极其重要论文,Bollobás也曾来信说感谢我的一篇论文。所有和随机图领袖Bollobás也算有几次关系。其实,随机图是Bollobás的导师Paul Erdős50年末就开创的。但70年代末起以Bollobás做为主要领袖的一代才逐渐使其发展为一个丰富重要的学科。关于图论,这里有一个信息说:‘这图论大师Paul Erdős计算机之父John von Neumann以及也做图论组合的大师Pál TuránGeorge Pólya都是Lipót Fejér的博士’。其实这Pál Turán的妻子Vera Sós也是Lipót Fejér的博士并是图论权威。

返回:琼州大学数学信息科学研究所主页