当前课程知识点:组合数学 > 漫谈组合数学 > 大家谈组合数学(1) > 采访武永卫老师
各位同学大家好
今天很高兴我们请到了
计算机系的武永卫教授
给我们来分享一下有关
组合数学以及算法方面有什么关系
因为我们都知道永卫老师在
清华大学教授了一门
课程是研究生的精品课
也就是算法设计
那么今天呢
我们来和他来一起分享一下
组合数学算法以及数学修养方面
会有什么样不同的感觉呢
武老师
我们都知道你已经培养了
很多非常优秀的学生了
那么组合数学在计算机
专业人才的培养上
你觉得有什么作用呢
武永卫 从我个人而言呢
我觉得组合数学在整个计算机的
专业培养当中应该说是处于
基础和核心的一个地位
也是在为我们后续的各个课程
起到了一个理论支撑和数学基础的
支撑的这样一个作用
比如说拿我教的这些算法课而言
学生必须先修了组合数学再
学习算法的过程当中呢
他的数学的使用才会得心应手
才能够更容易或者说更快捷的
学习和使用算法
整个这个我个人的一个
更随意一点的理解
我觉得组合数学和算法的
一个关系呀
我觉得更像一个数学分析和
计算方法的一个关系一样
也就是说一个要提供说我在
算法过程当中数学分析和
使用的过程当中
分析的基础
而整个分析的流程和
过程是由算法来控制的
大概这是我一个简单的理解
所以我想各位同学分享的就是
从我教这个算法这个课程以及
在科研过程当中
我认为组合数学的学习对
我们终生应该是很受益
特别是在自己以后从事科学研究
或者说解决计算机实际工程问题
当中会遇到各种各样的问题
但这些问题最终落实到基础的
数学问题的时候
都会用到组合数学相关的知识
那武老师
您在教授整个算法过程的时候
有没有比较印象深刻的和
组合数学特别相关的例子呢
这个我有一个
特别印象深刻的例子就是卡塔兰数
我们在讲动态规划
这是算法里面一个非常重要和
核心的一个算法的问题
那动态规划问题里面呢
有很多问题我们在求解的过程当中
需要分析这个问题的算法的复杂性
那么这些很多的问题应该它涉及
到了一个卡塔兰公式才能够帮
我们把这个算法的这一个问题的
复杂性求解出来
所以我个人觉得像卡塔兰数
这样子的一些组合数学的支撑
为我们后续的这样的算法的
课程的教授提供了非常大的
便利的条件和基础
所以也非常感谢马老师在
我们算法课程之间就开设了
这个组合数学这样一门课
作为我们的先修课程
为我们后面的课程提供了
非常便利的条件
特别我其实想补充一点的就是
说在我们系的研究生
培养方案里面呢
组合数学是作为一个
基础理论课的一个核心定位
它是研究生首选的入学的
第一个学期就需要学习的一门课程
而且作为我们系的研究生呢
基本上是全员选了这门课
所以马老师受欢迎的程度
因为选课是自愿的
受欢迎的程度而且其他老师应该要
实用到这一门课的相关的基础知识
所以大家都会或多或少的
提到马老师的组合数学课
这是我的一个感受
所以我在课堂上也老会问
同学们这个马老师给你们讲了吗
那个是应该讲了
我们只是说马老师应该给你讲了
所以我们就继续往下走
这个过程就略了
所以我想组合数学总之来说
是非常重要和关键的
在我们计算机系的研究生培养当中
当然我们也从这个课程当中的
受益或者说得到的益处不少
也谢谢马老师
开这门课程
非常感谢武老师给我们的分享
我想其实大家在选组合数学之前
都会有这样一个想法
为什么要学组合数学
大家都听说过计算机就是
一门算法的艺术
那么组合数学和算法又有什么关系
我想通过武老师的这一番解答
大家心里面都会有了答案
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验