当前课程知识点:组合数学 > 神奇的序列 > 大家谈组合数学(3) > 采访郭家宝(BYVoid)
提起郭家宝这个名字
可能大家并不熟悉
如果我说BYVoid
可能大家就有所耳闻了
确实
其实郭家宝同学在
网上还是颇有名气的
那么他不仅仅是
清华大学计算机系
2010级的本科生
同时他也是NOI金牌的获得者
而且他在本科期间还
编写了《NodeJS 开发指南》
这本书
所以说他在编程以及相关的
算法研究上都有颇深的造诣
那么今天我们就想请郭家堡
同学来和大家一起分享一下
组合数学在编程以及编程爱好者中
有什么样的影响
郭家宝
我想了解一下你是什么时候
开始接触到组合数学的呢
要说组合数学
我觉得最早接触应该是在
小学参加奥数的时候
不过那个时候我
并不知道什么是组合数学
只知道像什么一笔划问题
什么数路径的问题
但是我真正知道组合数学这个词
应该是在初中和高中的
时候参加信息学竞赛的时候
这个时候我才意识到
小学时候碰到的那些题
原来都是有一些抽象的模型的
譬如欧拉回路
或者加法原理乘法原理
以及一些组合计数的方法
那这么说来其实你会觉得
真正领悟到组合数学的
用处就是在信息学竞赛中啊
我觉得在信息学竞赛中组合数学
是一个相当重要的一个知识点
许多问题其实都是基于组合数学的
在我们当初学信息学竞赛的时候
很多题的第一反应看到的想法
应该就是枚举或者是搜索
但是当你学了组合数学之后
你就会发现其实很多题
是有更好更快的解法的
譬如动态规划问题
或者很多问题可以用
图论这种方式来建模
对
抽象之后就会觉得
其实茅塞顿开的感觉
就会发现其实枚举并不是必须的
郭家宝:是这样的
是吧
郭家宝:是这样的
是吧
马老师:如果我们去GitHub看一下呢
会发现其实郭家宝同学
有很多的项目在上面
其实有一个OpenCC 的项目
还是有一定的知名度的
那么他现在OpenCC已经被
嵌入到所有的Linux中文预装库中
那么我们就很想知道
郭家宝做了那么多编程的项目
那么组合数学在实际的编程中
会有什么样的作用和影响呢
我觉得在实际的编程中
譬如就说我的
那个OpenCC那个项目
它其实是用到了
很多自然语言处理的算法的
而这些算法它的分析的
基础就是组合数学
当你学了组合数学之后
才能对这些算法就更深一步的了解
此外我觉得组合数学实际上
传达的是一种抽象的思想
学了组学数学以后你面对一个
具体的问题就不再会像以前那样
只通过它的表现来对它
进行枚举这样的方法
然后你会更多的意识到
它的背后的东西
这种抽象的思想在实际的
编程中其实是至关重要的
当你构建大型工程的时候
如果没有合理的抽象那么
这个工作是几乎不可能完成的
比如说就你刚才说的
一笔划的问题
实际上是最典型的枚举和
抽象的对比
所以你会发现枚举实际上
有时候是根本不能完成的任务
但是如果你有抽象的
思维思想事半功倍
没错
所以我们就特别想知道
如果作为一个编程爱好者来说
到底要不要学组合数学
尤其大家会想知道
到底什么时候去学
组合数学才比较合适呢
我觉得如果从一个
编程爱好者的角度来说
组合数学的确不是必要的
对于编程来说你即使
不会组合数学也可以编程
但是
如果你想把编程作为
一项更深的爱好
或者是一项事业的话
那么学习组合数学会
能让你的编程做得更好
能让你的程序写得更清晰
抽象层次更好
效率更高
所以我觉得学习组合数学
对于编程来说还是有一定的必要的
那你觉得什么时候学比较合适呢
至少小学的时候学那就是奥数了
那你觉得现在我们实际上
是放在研究生课程中的
那你觉得如果是你自己
是一个编程爱好者
你觉得什么时候更合适一些
我觉得既然是编程爱好者
那么一定是兴趣驱动的
对于兴趣驱动的学习方式
我觉得其实是效率
最高最好的一种方式
那么这个时候我建议是那你
当你学编程学到一定瓶颈的时候
当你觉得学到很多工具
学到很多方法
但是对于自己编程好像
没有什么实际的提高的时候
那么这个时候很可能你
就要学习一些背后的东西了
譬如组合数学
譬如算法等等
然后这个时候你学完
组合数学再反馈到你的编程中
你会发现自己编程水平已经和
原来不在一个天地了
然后这个时候你可以
再继续的学习编程
然后等到以后遇到一些更深的算法
更深的知识以后
还可以重新回去学习组合数学
我觉得它这个和编程应该是
一个同时学习
相互学习
相互反馈的一个过程
所以非常感谢郭家堡同学的分享
确实我觉得作为一个编程大牛来说
组合数学应该是你的
算法的基础和你编程的基础
所以非常感谢郭家宝同学
给我们这样一个分享
那么同时我们也会觉得确实是
组合数学和编程有什么关系呢
大家会觉得我们上了
这么多堂组合数学课以后
我们基本上就在数数
但是正是这种数数的思维
才指导着编程能够从
暴力枚举像抽象进行转换
这这就是高效的算法
和高效程序设计的
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验