Date Category misc
  • "22.304584" geo_longitude:
  • "114.185295" geo_public:
  • "1" category: 工作和学习
    tags: 教育

读博士一年了,其中一个收获是学会了如何用严谨、科学、无歧义的形式化语言去描述一个问题,包括这个问题给定什么,假设什么,要干什么,以及有什么限制条件等,我们管这个过程叫Problem Formulation。只有把一个问题formulate出来之后,才去评估、解决这个问题。这文章不谈学术问题的formulation,否则就没人看了,正所谓曲高和寡,一篇Paper能被引个几百次就相当牛了,被引个几千次就是神文了,谷歌在OSDI上发表的关于MapReduce的神文也不过引了几千次。这篇文章我们来Formulate国内高等教育的问题。

自从07年毕业到高校工作,到去年出来读书为止,不知不觉也是四个年头了。期间发现了很多很多国内教育上的问题,比如老师不认真上课啦,学生不好好做研究啦,行政部门态度恶劣啦等等。但是从来没想过说去探讨解决办法,当然,探讨解决办法也不是咱应该管的事情,是教育部部长应该管的事情。今年这个夏天,我被“交换”回同济当交换生,跟一些同学聊到现在国内教育的一些问题,也从学生的角度知道了一些问题的原因,突然萌生想法,找找问题的根源是什么。

于是打开word,把一个个在学生看到的问题都按照条目列出来,一共列了几百条,然后又尝试归类汇总,删除合并重复。最后把这些问题之间的一些依赖关系标出来。只要简单的Graph Theory知识,就可以解决问题了。

接下来Problem Formulation就开始了,把每个怪现状denote成图中的一个Vertex,把它们之间的依赖denote成一个Edge。如果依赖关系能形成一颗树,只要把Tree Root抓住,一切问题迎刃而解,这个就叫Root Cause,很多程序员喜欢用这个词。整个图画完后,我仔细梳理了一下,发现问题还真不是想象的那么简单,那些依赖关系不是一颗树,而是一张图。是图也没问题,只要是Directed acyclic graph (DAG),还是可以找到只有In degree的顶点,也算是问题的根子。后来我发现,这依赖关系还能形成环路。这下子可就麻烦了。

下图只是一小部分,全都放出来的话,估计就要有人来找我麻烦了。至于说为啥能形成环路,可谓冰冻三尺非一日之寒,这个问题我们不去探讨了。

做Research还有一点,如果一个问题能够Reduce或者Transform成已有的问题,那对于解这个问题就大大地有利。这个问题可以Reduce到啥问题呢,举个通俗一点的问题,这个就是一个死锁检测问题。一堆进程,占着碗里的资源,还想要锅里的,要来要去,就锁上了。这个搞计算机的都懂,我就不重复了。

说到死锁检测,不禁想起了三年前的一段悲凉故事。话说当年微软历经多年折腾,终于发布了Windows Research Kernel。这里面包含一份Win Server 2003的内核源代码,而且还可以修改,编译和运行。微软在杭州向国内老师发布,每人发了一个小光盘,里面就有所有的代码。我当时十分兴奋,连微软在楼外楼请客吃完饭都没去,就跑到酒店研究这份代码,一边在想回去之后能够干点啥。后来跟几个学生讨论下来,觉得Windows上程序莫名挂掉是一大顽疾,当然一部分是码农技术太差导致Access Violation,这个管不了。还有一部分就是死锁引起的。我们打算开发个死锁检测的算法,放到Windows内核里,在给任何一个资源上锁前,都检测检测这个上锁操作会不会引发死锁,如果会引发死锁,就强行把资源收回。这样,就不会导致正在上网,突然就xxx失去响应,问是否强制关闭了。后来我们就改内核,增加死锁检测算法。并且想办法把消息提供给用户态。当锁上的时候,就会弹框,说,这个操作可能要死锁,要不要取消该操作。经过几个月的开发调试,当测试用的A.exe, b.exe有一天突然变成了iexplore.exe跟winword.exe的时候,成就感油然而生,觉得以后要是把这个kernel放出去,一劳永逸解决死锁问题,太牛了。后来一想不太对,这么牛的功能,几个学校的学生都能做,为啥微软的工程师们不做?这个idea又不是很难想到。后来查了一下资料,才知道,死锁检测是一个非常经典的NP-Hard问题,确切的说,是NP-Complete问题,早就被人已经证明了。微软虽然很牛,但是还没有牛到在OS内核里面挑战NP-Hard问题。不禁觉得自己年少无知,羞愧难当。

什么是NP-Hard问题呢?通俗的说,就是由于计算复杂度问题,很难有效的把解找出来的问题。那遇到这类问题怎么办呢?两种办法,一种是暴力解,需要花费大量的时间。另一种就是所谓Heuristic的解,Genetic Algorithm, Ant Colony Algorithm, Neural Networks等等都是这类方法。这类算法其实也就是跟着感觉走,或者说拍脑袋,好不好,好到什么程度都是不能被证明的,比方那个基因算法,模拟基因遗传变异,但是你能证明人就比猴子好么?某些方面可能还不如猴子呢,例如爬树。

既然这个国内高校的教育问题已经成了NP-Hard问题了,那大家也就别指望一会儿半会儿能解开了。不要指望教育部官员会像解死锁一样,解开高等教育问题上的锁。那么NPC什么时候能解呢?号称量子计算机可以解。现在还是初级阶段,大家等到量子计算机诞生的那天吧。

当然,也有可能官员们也意识到了这个问题不好解,所以整天拍脑袋做决策,现在大家看到的各种莫名的决策,都是他们想出来的各种各样启发式算法。