组合数学总结

终于考完组合数学了,长舒一口气!

零散的感悟

先要自我反思一下,这门课学习不够深入,尽管各种类型的题目基本都能做一做,不会做的看看答案也能理解的差不多。对了,很多的证明过程都没有仔细看,只是停留在记住一些定理的层面。

但是对于我而言,这门课程应该是一个转折点——我开始尝试用新的态度去面对考试,面对学习啦。

想一下大学的时候,基本是以成绩为核心,理解当然最好,但是不理解也要强迫自己去死记一些题型来应付考试。往往是这样,理解最差的课程考的最好,而理解的很深的课程却考的一般。现在想想,很是愧疚。用了那么多的时间自习,那么多是时间应付考试,同一个类型的题目做了几十道,考试从来都是先看习题集再看课本。但是,不这样做就很难有很高的成绩,也就很难有保送的机会,读研就成问题了。

而现在不同,我觉得我有必要换一种心态了。把对于一门课程的理解放在第一位,争取以后的学习和工作能够复用这些学到的知识。至于成绩,成绩很重要,但是也不重要。任何事情都要落地,90+的成绩已经不是我需要的了,我更多的时间应该放在“理解+实践”的过程。如果还有一些琐碎的时间,我想做一些我喜欢的事情,好好的“生活”。

组合数学总结

刚开学学习的时候很迷茫的!一会儿排列生成,一会儿排列组合,一会儿一一对应。我开始问自己,难道这就是所谓的组合数学?感觉像大杂烩一样,什么也有,没有章法!

清华的课件帮我揭开了这神秘的面纱(点我下载),貌似这个课件在网上挺难找的,但是内容特别好,不像是常见的那种“灌输式”教学,像一种“解释式”的解读,面向用户,用户体验极好!

入门之后,剩下的就是思考和总结了。可以把组合数学看作是一种工具,它主要负责给一些实际问题提供解决方案。而组合数学主要考虑四个方面的问题:存在性、计数、构造算法、优化算法。

比如,我要做一个“钳子”手机。肯定希望待机时间超长,性能超高,内存超大,价格超低。然后,我们不免就会问这样的问题:这样的手机能做出来吗?这就是存在性问题了。

在确定可行之后,我们会想,CPU该选多少Hz的,内存该选多大的,电池呢,价格呢,定多少合适呢?这时候秘书嗲声嗲气的说道:经理,我们一共有100种方案去搭配这些电子器件。这就是计数的问题。

如果你是经理,你肯定想知道这100种具体是什么。所以,你可能会说,把这些具体的搭配给我列出来。秘书如果是闭上眼睛想的话,肯定说不全,可能还会说重了。那怎么办,她需要一种方法,来列举这些搭配。这就需要构造合适的算法了。

当然,她可能会有很多种方法去列举这些搭配。但她肯定选最优的算法,很快的列举出来,让经理一看能够满意。这就需要优化算法了。

当第二天,秘书把详单交给经理的时候,他抑或开心,抑或纠结。因为具体的方案有了,他该选哪一个呢?这个,组合数学只能帮你到这了。剩下的,可能会有一些其他的算法、模型帮你做选择。

回到本门课程,其实重点讲述的是计数和构造算法,也就是数数和列举。

对于计数,课程中讲解了基本的计数原理、排列组合、一一对应。与此相关的一些方法、公式也有涉及。当然,对于一些特殊的问题,我们可能就不必非要用计数等基本原理了,因为这些很火热的问题已经上升到了新的高度,有与此很协调的解决方案,如整数拆分、容斥等,当然也包括下图中为写出的染色问题(可能会用到Burnside、Polya)。

个人感觉把计数和列举割裂开是不太好的。因为如果要列举出所有的方案,肯定就已经知道了一种有多少种方案,计数问题已经解决。但是,因为母函数对于列举作出的贡献实在是太大了。不管是贴邮票的问题,还是整数拆分,Polya和母函数结合来解决染色问题。对了,前面计数环节没有表扬一下它,母函数在求解递推关系方面能力显著啊,没有递推关系,特种方程根本使不上劲儿啊~

OK,总结完毕。有一个古老的传说:组合数学在计算机方面的应用很广~

-- EOF --