当前课程知识点:组合数学 > 漫谈组合数学 > 你的手机密码安全吗 > 你的手机密码安全吗
我们先看一幅照片
这位白发苍苍的老先生
他的名字叫做Thomas Tutte
他是一位加拿大非常有名的组合数学家
但是他不仅仅是一位组合界的泰斗
最近有关二战的解密信息发现
他实际上在二战的历史上有重重的一笔
我们都知道在二战的时候
德国人在机械工艺和加密技术上处于领先地位
他设计了一个叫做The Tunny machine的东西
这个Tunny machine里面它有十二个机械轮子
进行精密的加密
所以德国人认为他们这个机械
绝对是坚不可摧的
但是没有想到在Tutte教授年轻的时候
做了一个惊天动地的事情
他仅仅根据德国人发出了两条信息
就成功的破译了Tunny machine
所以我们可以看到
既然像德军这样精密的仪器
都可以用组合数学来破解
那么我们手中的手机
也经常遇到要开锁的问题呀
它是不是安全呢
这是我们大家都非常熟悉的iphone手机
那么它的开机密码可以很简单只有四个数字
那么是不是这样的格式
是不是有点不太靠谱呢
那换作安卓的是不是就会更好一些呢
下面我们来看一段视频
看样子都教授都没有搞定嘛
那么是不是Tutte教授
就能用组合数学来帮我们搞定手机密码呢
你的手机安全不安全真是算了才知道
下面呢我们就来看一下
怎么去算一共会有多少种密码的组合呢
这里是安卓系统的手机密码设置界面
我们可以看到
我们可以通过不同的路径来设置不同的密码
简单来说我们实际上
是要从这九个数字中选择若干个
如果你只设一两位实在太简单了
所以安卓系统要求至少要设四位以上
那么最多能连几个呢
只有九个数字 最多连九个
如果不考虑这些点的位置的话
我们先算算一共有多少种方式呢
如果我们设置四位的密码
也就是从九个数字中选出四个就是A(9,4)
如果选出5个呢A(9,5) A(9,6) A(9,7)一直到A(9,8) A(9,9)
所有这些数字加起来答案是985824
但是这样的计算方法我们并没有考虑
它在划的时候有顺序的因素
比如我们来看一下
由于在这样一个界面下
我们从1划到3的时候必须要经过2
那么如果我设置的时候是说选择1 3
那么这是一个不合理的划分方法
所以我们会看到在刚才的计算方法里面
没有考虑到任何位置的约束
所以我里面会有一些不合理的密码
那么如果我们想找到所有合理的密码的个数呢
有一种思路
我们可以把所有不合理的密码挑出来
把它们的个数减掉不就是合理的密码个数了吗
所以从这里面我们可以看到
我们可以通过计算一个全局
刨掉那些不合理的解
最终算出一共有多少种合理的密码
那么在这样一个约束下
我们再重申什么样的是合法的密码
如果选择两个点连成了线段穿越了第三个点
这第三个点之前没有被连过则不合法
如果连过了那就合法
这是一个相对有点复杂的规则
我们很难用一般的思路来解决
所以呢我们可以通过编写代码
写一个相应的枚举程序
就可以计算出一共有多少种合理的解了
这时候我们回头看通过计算机的程序跑出来
它的方案数一共有389112种
这么一看非常多呀
方案数很多嘛
对比原来我们刚看的iphone手机
如果只有4位的话
每一位只有十种选择
所以是10乘以10再乘10再乘10
iphone手机4位密码只能有10000种结果
但是安卓这样划来划去的密码
似乎能够达到38万多种选择
安卓果然牛啊
再看看 同学们你们设密码的时候
一般设几位呢
我想大多数同学怕自己记不住
基本上也是划了个4个就不错了
这时候我们回头再看
如果大部分人的密码只有4位数字的话
实际上它的合理组合数只有1624个
只有一千多个可行的密码
如果让Tutte教授来做的话
分分钟就可以帮您搞定了
那么到底得设多少位才安全呢
如果我们认为至少得达到iphone的水平吧
那么我们加一下四位密码是1624个
五位密码是7152个
如果我们说不能太多了 太多我记不住
我们不到六位的话
它的可能个数是1624加7152 是8776个
所以我们可以看到如果你的安卓手机上
密码设置小于六位的话
它的的安全系数远比iphone的还要低呢
刚才我们用手机密码
给大家演示了一下怎么计数
我们会发现计数实际上有很多种不同的策略
我们可能用到乘法 可能用到加法
甚至我们还可以用到减法
但是无论用何种方式
其实我们都是要达到一个目的
就是在合理的范围内无重复无遗漏地
把所有的方案全部都囊括其中
所以计数的最根本的原则就是
要无重复无遗漏
这个目标实际上并不那么容易实现
那么下节课呢我们跟大家一起去分享一下
学习组合数学做好计数需要什么样的根本思想
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验