你忘了你学的算法吗

学习计算机应该学什么, 应该怎么学, 什么内容应该学多深入, 是一个很复杂的问题. 按照我现在的菜鸟水平来猜测, 按照菜鸟到高手容易忽略的问题进行排列, 大致是如下一个列表.
 
  1. 初学太多语言
  2. 学习语言不懂本质
  3. 轻视算法
  4. 学习算法不重视证明
  5. 重视证明却不知道证明的来源
  6. 忽视了算法以外的同样具有核心竞争力的编程知识
  7. 忽视了计算机以外的科学
  8. 忽视了科学以外的世界
其中第1, 3, 4 点由于太多资料已经进行阐述, 我也赞同他们的观点, 就不再重复说一遍了;
其中第7, 8点, 自觉我的水平无法说出有一丁点意义的话来, 所以我也不敢多说
而其他方面, 我稍微有点想法. 心痒痒, 我想写一写我的一点想法.
[ 学习语言不懂本质 ]
 
首先是语言的分类. 对于什么高级语言低级语言机器代码这种分类就不用说了.
而高级语言从面相过程到面相对象的转变是一个值得思考的问题, 如果没办法抽象出两种过程和对象的本质, 那么会造成初期的重复学习, 例如学了c++然后来java然后来.net等等.
除了这些还有函数式编程. 由List衍生出的几种著名语言例如scheme.
他们是为什么被发明的? 为了解决什么样的瓶颈而诞生的?
这些问题如果能研究清楚, 那么对学习是相当有帮助的.

[ 学习算法重视证明却不知道证明的来源 ]

 

这个问题是我大一以来一直在思考的问题. 勾起我思考这个问题的导火索是我们学校的ACM队开始招人, 这件事让我非常兴奋, 但是兴奋过后, 而我对ACM刷题的训练方式产生了质疑.

我联系了ACM教练姜老师, 可惜他比较忙, 没有给我答复, 于是我在网上搜索了国内几位acm牛人的感想, 也和Iguanodon同学通了很多电话, 同时也看了一些Knuth的文章, 还有一些知乎网上人们对数学竞赛的讨论, 然后写了这个博文.

又过了一小段时间, 想了不少回有关算法应该如何学习的问题, 同时有幸看到了mindhacks的几篇文章, 有了新的想法, 于是写下来.

我的新想法是这么来的:

  1. 我通过看算法书, 理解然后记忆了一些算法, 可是我会很快忘掉, 怎么办?
  2. 理解了算法的证明, 对第一点的问题有所改善, 因为算法的证明中涉及了算法的核心部分, 让人印象更深. 问题是如果我把这个算法的证明也忘了怎么办?
如果思考一下, 你会发现上面第二点提出了 理解了算法的证明对第一点的问题是有所改善的 这样一个很棒的结论. 这个结论的原理是什么呢? 我们知道证明过程大多时候是环环相扣的, 只要记住最关键的那一点, 那么整个证明过程都能照着逻辑步骤写出来, 而证明过程又抓住了算法当中最核心的部分, 因此算法也就不难想到了.
所以不难想到, 我们之所以容易忘记这一切, 是因为证明过程中最关键的那一点往往就是我们最容易遗忘的地方. 这个现象说明了一个问题, 就是我们的算法教育出错了, 教育模式不正确, 或者教科书写的不够好. 足够好的教科书是不会让人们大规模普遍出现这样的问题的.
一般书上的证明遇到最关键的地方, 就是这样一句话开头的: "考虑到....我们...". 例如"考虑到直接证明比较困难, 我们添加一条辅助线AE".  然后后面的所有问题迎刃而解. "考虑到"后面的话一眼看过去好像很简单, 但是如果他没有指出来, 没有提示我们, 可能我们耗费非常大的力气也没办法想出来他是怎么得出来的这一步骤. 所以这里的核心问题就是这个关键的步骤到底是怎么来的? 如果把这个弄清楚了, 那么算法学习也就找到了正确的道路.
根据刘未鹏的博客, 他的思考结果是
  1. 选择一本好的算法教材( 例如<<算法引论>> )
  2. 遇到"考虑到"这个关键字的时候要非常小心, 因为这里就是一般人阅读一晃而过, 而你却需要仔细分析为什么作者想到这一步的地方. 当然对证明步骤的来源的分析是一件难度很大的事情.


大多情况我们无法得出很好的结论( 阅读这个算法的提出者提出这个算法的历史故事会有所帮助 ), 但是这样一个思考过程不仅是上面第二点问题的一个改善方法, 同时也提高了我们寻找为什么的为什么的能力.

算法教学的发展和数学教学的发展是有些类似的，不过如今数学教学要比算法成熟. 我们不妨看看数学当中的一些事情.

有时候我会发现有的老师喜欢把简单的地方讲的比较详细，复杂难理解的地方反而没有那么详细. 本来我不理解这是为什么，最近想着算法学习的问题去听数学课才发现我们高数老师讲课的节奏是挺有道理的. 例如讲到常微分方程的伯努利方程，最核心的部分非常简单，就是方程两边同时除以一个东西然后变形一下就完事了，其他问题迎刃而解，好简单！
不过老师花了比我想象的要多的时间来让我们在知道这个方法之前去想怎么样处理能够计算出结果，怎么把这样新的形式的方程转换成已经学过的方程的形式，这个思考方式立马让我想到了算法也应该这么学.
如果我们能够在学习一个算法之前，考虑如何用已有的算法组合，变换，得出新的算法，即使我们想不出，但是这个过程会让我们看到书上给出的方法时恍然大悟，而不是轻易就"理解"过去了. 而且我们能够更容易想到为什么作者能够想到，更容易明白证明过程中最关键那几步是怎么得来的. 看书之前的考虑让我们和算法发明者有了类似的思考过程（发明者通常在这个思考过程上花的时间更多），能够训练我们根据现有定理推出新定理的能力，也就是根据现有算法组合变换出新算法的能力.

[ 忽视了算法以外的同样具有核心竞争力的编程知识 ]

中国科学院院士怀进鹏在一次会议上说的话引起了我的思考:
在过去的五十年中是什么状况？一直是以算法为研究基础. 七十年代单纯算法研究. 到七十年代之后发现了多项时间算法，所以不是所有计算都能解决问题. 到八十年代又发现了随机算法，因为能加速. 到九十年代所谓的近似算法，因为找不到最优解.


如果用50年这样一个时间标尺来看问题, 不难发现算法研究的演变速度也是挺快的.

这里有的一个问题就是新的算法是向什么方向发展的，因为如果不知道这一点，我们就不知道我们应该在有了较好的基础上往哪一方面继续研究.

算法的发展和计算机的发展和人们的需求是是密切相关的，这方面院士的上面几句话讲得非常好，我们变换一下他的话的顺序, 可以更清晰的看到:

  1. 因为不是所有计算都能解决问题, 所以到七十年代之后发现了多项时间算法;
  2. 因为需要加速, 所以到八十年代又发现了随机算法;
  3. 因为找不到最优解, 所以到九十年代所谓的近似算法应运而生.
我们暂且不管他的话是否非常严谨正确, 重要的是按照他的思路顺推下去,
  • 因为今天数据的增长已经使得原有可用的算法变成了不可用算法, 所以适应大数据的算法诞生了, 云计算技术开始发展.
  • 因为云时代的到来以及多线程多核心处理器乃至多服务器并行计算的流行, 所以并行计算的算法开始越来越受到重视.
  • ......
可以看到, 算法的研究方向是可以根据一些非算法的事件进行判断的. 在MIT算法导论公开课的一名助教讲到, 算法的思维是数学思维和工程思维的结合, 而算法以外的一些编程知识, 例如面向过程到面向对象的转变, 高低级语言混合编程技术, git版本控制系统的使用, 并行开发技术等等, 将他们当中的算法去掉, 剩下的就是可以很明显看到的为了适应当前工业发展阶段而产生的一些非算法解决方案. 旧的算法运用在这些新的解决方案上面能够使这些新的解决方案加速发展, 而新的解决方案反过来作用于算法, 对算法的发展方向起到导向作用. 因此当我们的算法训练已经比较可观的时候, 追求本时代的艰难晦涩的深度算法研究, 还是追求对算法以外的同样重要的编程知识的了解以明确下一时代的算法研究方向, 就是一个值得我们仔细考虑的问题了.
说了这么一段抽象的东西, 我们不妨凑近现在发生的事情看一下具体的情况是怎样的.
有关大数据:
  • 大数据背景下, 传统可近似算法理论存在局限性:
    • 可近似问题不在可近似;
    • 仅追求时间复杂度更低的算法, 已不是最优选择.
  • 不同于传统近似算法理论, 大数据的近似算法理论, 需要研究数据量, 算法效率, 计算结果精确性之间的均衡.
[ 结束语 ]
上面写了一点想法, 自觉不是很满意, 而且因为时间问题匆匆收尾.
因为各方面水平实在是太垃圾.
这次写完全是心痒痒想说点浅薄的想法. 说完这点, 我打算去学一段时间算法. 希望下回写的时候能有新的东西出现.