请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 11709|回复: 78

2015数学中国认证杯赛题点评 B题

[复制链接]
字体大小: 正常 放大
magic2728 实名认证    中国数模人才认证   

61

主题

470

听众

4857

积分

升级  95.23%

  • TA的每日心情
    慵懒
    2014-9-29 19:37
  • 签到天数: 409 天

    [LV.9]以坛为家II

    群组数学中国 2015美赛护航

    群组数模专题强化培训

    群组建模思维养成培训

    群组2015美赛护航(强化)

    群组2013年数学建模国赛备

    发表于 2015-4-19 18:41 |显示全部楼层
    |招呼Ta 关注Ta
    大家好,我是magic2728,欢迎来到B题,这题也是我在本次挑战赛四个题目中比较欣赏的,题目思路清晰,既考功底,也需要源于技能积累的创新能力,能反映水平,也能拉开差距,望大家认真品评。
    (文章中用到我在数学中国课程中常用的信息标注法和函数建模法,不影响阅读,也欢迎同学们关注magic2728在数学中国开设的课程,助各位在建模学习之路上一臂之力。); @6 h) u- U& m: i
    历史上有许多密码的编制方法。较为简单的是替换式密码,也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言,最简单的形式是单字母替换加密,也就是以每个字母为一个单位,将每个字母替换成另外的字母或者另外的符号。较为复杂的形式是以多个字母为一个单元,整体替换成其它的字符。这个映射方法被称为密码表,拿到密码表的人就能够将密文破译成明文。单字母替换加密是在古代就使用过的一种加密方法,但由于其容易被破解,所以在现代需要加密的场合已经很少使用。(bk1)
    单字母替换加密的破译方法有频率分析等。这种密码和破译方法在小说中也经常提到,例如爱伦·坡的«金甲虫»和柯南·道尔在福尔摩斯系列故事«归来记»中的跳舞小人。但当获取的密文篇幅不是很大时,光凭借频率分析是不足以破译全部密文的。往往还要熟知该种语言的人,经过对可能出现的词汇及字母组合进行分析,才能完整地破译密码。(bk2)
    第一阶段问题:假设明文是由现代通常使用的英语写成的。(rsc1)现在我们获取了一些由单字母加密方法加密的密文。请你建立合理的数学模型,设计一个算法,来自动化地破译密文。并设计一个衡量破译能力的标准,来评价破译算法的破译能力。(spm1)为了问题简单起见,我们假设密码表仅是针对26 个字母的,每个单词之间的空格,以及标点符号仍然会保留。(rsc2)在设计算法时,如果需要,可以参考英文语料库的数据,例如免费的COCA1等相关资料。(imp1)
    密码学背景,实际是一个自然语言处理问题,让我回忆起了一些这个领域用以数学建模,尤其是统计建模为核心设计的优美解决方案:机器翻译,语音识别,拼音输入法,当然还包括此处的加密,再一次赞叹数学建模在现代科学技术引领的社会里的伟大作用!
    回到此题,前第一段背景介绍了替换式密码,用数学语言描述就是,对于字母表全集A,由以其为象和原象的一一映射C,使得b = C(a),a,b 均含于AC就是所谓的替换式密码。后一段介绍频率破译法,模型本质是,每一个字母表的字母映射到一个属性出现频率,这一频率也是该字母对应象值的频率值,根据这种穿透力,破译原来的映射。
    按照函数建模法的思路,我们挖掘出本题的函数关系:
    自变量:破译算法
    因变量:破译算法的破译能力,比如量化为期望错误率;
    参数:语料库大小,加密方式,语种等等;
    函数关系:依据统计模型推断在给定样本容量的情况下期望错误率的大小。
    本题表面上是评价模型评价算法好坏,单一评价指标错误率就足矣(算法的复杂度,语言什么的显然不在评价范围之内),没什么难度,又好像是优化模型,而求解更没有难度,无非是对方案的评价结果值比较大小而已,因此,本题重点在于自变量的找寻(即算法设计),辅之以基于统计学的函数关系表达式建立,就像眼科病床问题重点在于设计出安排方案作为自变量,而方案比较绝非难事一样。
    下面简单谈谈破译算法设计:
    可以看作破译是对应映射C的获得,等价于字母表的一个特定排列,我们要做的就是把排列当做参数,估计最优者。估计参数必然要找损失函数,比如频率法中,损失函数可以是各自变量字母频率与对应因变量频率的残差平方和最小,或推导下似然性的最大,即:
    C = arg min sumS)(lossQs cp - QCs), cp)))
    s为某语言结构S(字母表A集合的函数)中的元素(比如字母S = AA ^ 2等),Q为所选择的性质的基于语料cp的估计,则为整个训练语料库,而除了字母频率这一性质,基于语料库还有多该信息的种理解方式以挖掘出一些性质来作为破译的标的,下面简述之。
    基本语料库给出了按国家,风格划分的文章的内容,如果不利用任何周边信息,假设每一个有序出现的字母都是独立重复事件,S = A, Q(scp) = p(s)est,此即为频率破译法的本质。
    这里,可以提几个其他的几个简单想法:
    S:
    1. A ^ n, An阶笛卡尔积,这样,元素个数会迅速指数式扩展,在语料库里也可以直接理解为有序的横向排列。在保证每个元素样本数量仍然足够的情况下,可以挖掘出更高层次的信息;当然也可以是其他模糊匹配模式。
    2. 构成以空格或者标点分割的单词,其实可以发现,单词的频率在某类文章才会更体现其特点,也会越不一样,因为我们是先想到要表达的意思,再想到逻辑结构,再想到要填的单词,最后才把字母拼上去,所以单词的特性更能够有区分力,信息熵更大;(当然以句号分割的句子,以逗号分割的单句,或者意群(能充当句子成分的多个单词)等等也可以作为S,但那要大量语料库才行);当然,一个词以不同词性出现时归为一个词考虑,还是有所区分,建立更高阶网络,也是需要考量的问题,题目网站里前两个数据库结论就是给的以词为独立元素和词性划分的信息的。
    Q
    我们很难去想清楚一个句子的生成有什么物理机理,而且我们对推断出一个特定的结果也没有兴趣,做解密不需要深入到这个层次。我们写出一个领域的文章,段落,句子,单词,字母,难以象F = ma那样挖掘出精确的等式关系,因为那需要知道该事件发生的一切信息,而这更像我们研究一个性质稳定的色子,大概不可能去获得所有信息,然后计算数值,找阈值判别最后的点数结果(虽然理想地来看这个结果是个确定的数),而应当是做些实验去得到一个稳定的统计规律即可,这就是统计建模相比于机理建模的优势,一方面便于实践操作,另一方面抓住本质而不浪费更多资源地解决了要解决的问题,难怪统计学“难度不大,应用甚广”的特点。
    这里提几个简单的统计模型。
    1. psest = freq(s),不考虑上下文对s出现的影响(或假设没有影响),把s的出现看作是独立重复事件,直接用频率作为估计概率的极大似然估计值,当S = A, 此即频率分析法;
    2. p(s1 | s2)est = freq(s1s2) / freq(s2),假设仅上文的一个s2对下一个s1有影响而构成有用的先验知识,估计一组条件概率的值(|S ^2 个参数),这就是马尔可夫链了。
    3. p(s1 | s2, s3)est = freq(s1, s2, s3) / freq(s2, s3),假设上文的两个元素s2s3有影响,没错,这是二阶马尔可夫链!
    (也可以注意,p(s1, s2 | s2, s3) = p(s1 | s2, s3),二阶马尔可夫链等价于一阶链但是对应字母集变成自身平方。)
    当前大部分对序列的建模方式就是这些了,包括提到的机器翻译,语音识别,手写识别,染色体拷贝数判别,拼音输入识别等方法大部分都是基于马尔可夫链或隐含马尔可夫链,其它或许还有更好的分词方式和统计模型,但就抓住模型本质来说,马尔可夫链无疑是当前广为接受的最佳的一个了。
    0 x  c9 y% x# [
    好了好了,不影响大家自己的思路了,就说到这里,各位加油!
    3 k' j5 a# P8 `. K5 K/ h, }$ C. K" T. r, Z

    . S( G1 f% w+ g; Q4 u# F$ n2 C* E) g% Y9 q6 K, [6 v1 y
    zan

    0

    主题

    13

    听众

    107

    积分

    升级  3.5%

    该用户从未签到

    国际赛参赛者

    邮箱绑定达人 社区QQ达人

    群组2015SAS数据分析大赛

    回复

    使用道具 举报

    湮栎 实名认证      会长俱乐部认证 

    1

    主题

    7

    听众

    215

    积分

    升级  57.5%

  • TA的每日心情
    无聊
    2017-3-18 22:30
  • 签到天数: 51 天

    [LV.5]常住居民I

    网络挑战赛参赛者

    邮箱绑定达人 社区QQ达人

    群组全国大学生数学建模竞

    群组2015年数学中国“建模

    回复

    使用道具 举报

    4

    主题

    12

    听众

    357

    积分

    升级  19%

  • TA的每日心情
    郁闷
    2017-9-15 08:24
  • 签到天数: 191 天

    [LV.7]常住居民III

    社区QQ达人

    群组2015年数学中国“建模

    群组西藏大学数学建模协会

    回复

    使用道具 举报

    7

    主题

    10

    听众

    715

    积分

    升级  28.75%

  • TA的每日心情
    奋斗
    2017-7-31 22:33
  • 签到天数: 129 天

    [LV.7]常住居民III

    自我介绍
    xiao白

    社区QQ达人

    群组2016美赛交流群组

    回复

    使用道具 举报

    wlz123        

    21

    主题

    11

    听众

    184

    积分

    升级  42%

  • TA的每日心情

    2017-5-21 00:06
  • 签到天数: 84 天

    [LV.6]常住居民II

    社区QQ达人

    回复

    使用道具 举报

    843134767 实名认证       

    0

    主题

    12

    听众

    141

    积分

    升级  20.5%

  • TA的每日心情
    擦汗
    2016-5-13 10:02
  • 签到天数: 27 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    社区QQ达人

    回复

    使用道具 举报

    383250890        

    1

    主题

    3

    听众

    112

    积分

    升级  6%

  • TA的每日心情
    开心
    2017-11-1 10:36
  • 签到天数: 32 天

    [LV.5]常住居民I

    新人进步奖

    群组2017himcm交流群组

    群组D题讨论群

    群组C题讨论群

    群组2014美国中学生数学建

    写得真好,不错啊写得真好,不错啊写得真好,不错啊写得真好,不错啊4 X6 n7 U* m' Z9 Q3 L
    回复

    使用道具 举报

    miss张        

    1

    主题

    8

    听众

    28

    积分

    升级  24.21%

  • TA的每日心情
    奋斗
    2016-9-5 18:49
  • 签到天数: 5 天

    [LV.2]偶尔看看I

    自我介绍
    爱数学

    社区QQ达人

    写得真好,不错啊写得真好,不错啊写得真好,不错啊写得真好,不错啊
    ! P) v8 M, |0 q" t- E! r- E
    回复

    使用道具 举报

    刘永强        

    0

    主题

    13

    听众

    23

    积分

    升级  18.95%

  • TA的每日心情
    开心
    2016-11-26 16:41
  • 签到天数: 25 天

    [LV.4]偶尔看看III

    社区QQ达人

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2021-9-28 15:39 , Processed in 1.018111 second(s), 109 queries .

    回顶部