学位论文 > 优秀研究生学位论文题录展示

缺陷幻方填充问题的NP完全性判定研究

作　者: 陈剑南
导　师: 谢涛
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 幻方 NP完全性拉丁方缺陷幻方填充均衡泛对角线幻方反对称相异代表系边色数
分类号: TN918.1
类　型: 硕士论文
年　份: 2009年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

缺陷幻方填充问题是幻方研究中发现的具有密码学意义的新问题,它是幻方数字锁原理和幻方数码防伪技术的基础,对此问题进行深入理论研究,以确认其安全强度,有着重要的理论和现实意义。同时,本文的研究对于推动幻方本身研究的发展也将有着重要的意义。针对这种需求,本文主要对缺陷幻方填充问题的NP完全性判定展开研究,取得的主要成果有:(1)在文献[18]的基础上,提出了均衡泛对角线幻方的概念,证明了均衡泛对角线幻方与正交泛对角线拉丁方对是一一对应的,同时发现了泛对角线拉丁方与正则群的联系,还从泛对角线拉丁方的缺陷填充问题出发成功归约到均衡泛对角线幻方的缺陷填充问题上,证明了素数阶均衡泛对角线幻方的缺陷填充问题是NP完全的。(2)指出泛对角线拉丁方缺陷填充问题的NP完全性证明中所存在的问题。对非线性泛对角线拉丁方的存在性问题进行了探讨,并把其难度与泛对角线拉丁方缺陷填充问题的NP完全性证明的难度进行了比较。(3)分别从主泛对角线拉丁方和对角线拉丁方(一种特殊的幻方)对幻方的缺陷填充问题的NP完全性进行了探索,并从正则图的边着色问题出发归约到反对称拉丁方的填充问题上来,从而证明了缺陷反对称拉丁方的填充问题的NP完全性。这对缺陷幻方的填充问题的NP完全性探索有重要意义。

全文目录

摘要  7-8
ABSTRACT  8-9
第一章绪论  9-15
  1.1 幻方的来源及其基本概念  9-10
  1.2 幻方研究的数学方法及其研究现状  10-12
    1.2.1 幻方的构造方法  10-11
    1.2.2 幻方的存在性及计数问题  11
    1.2.3 幻方的变形  11-12
    1.2.4 幻方现实中的一些应用  12
  1.3 课题来源及研究目的  12-13
  1.4 本文的主要工作和创新点  13
  1.5 本文的结构安排  13-15
第二章若干具有密码学意义的幻方新问题的提出  15-23
  2.1 随机幻方的快速演化构造  15
  2.2 若干具有密码学意义的幻方新问题的发现  15-22
    2.2.1 缺陷幻方填充问题  16
    2.2.2 幻方模和分解问题  16-17
    2.2.3 幻方加密  17-18
    2.2.4 幻方洗牌恢复问题  18-19
    2.2.5 幻方的一个应用实例  19-22
  2.3 本章小结  22-23
第三章一类特殊幻方缺陷填充问题的NP 完全性证明  23-40
  3.1 缺陷泛对角线幻方填充问题的描述  23
  3.2 计算机、复杂性和难解性  23-27
    3.2.1 问题、算法和复杂性  24-25
    3.2.2 图灵机模型  25-27
    3.2.3 NP 完全性理论  27
  3.3 素数阶均衡泛对角线幻方  27-35
    3.3.1 一条证明思路的设想  28
    3.3.2 均衡泛对角线幻方  28-34
    3.3.3 均衡泛对角线幻方的缺陷填充问题描述  34
    3.3.4 素数阶均衡泛对角线幻方的缺陷填充问题的NP 完全性证明  34-35
  3.4 非线性泛对角线拉丁方的存在性  35-38
    3.4.1 泛对角线拉丁方缺陷填充问题的NP 完全性证明存在的问题  35-37
    3.4.2 非线性泛对角线拉丁方的存在性问题  37-38
  3.5 本章小结  38-40
第四章缺陷幻方填充问题的NP 完全性判定研究  40-58
  4.1 缺陷幻方填充问题的描述  40
  4.2 缺陷幻方填充问题算法研究简介  40-41
  4.3 拟群、相异代表系和拉丁方嵌入式设计  41-44
    4.3.1 拟群、拉丁方与痕  41-43
    4.3.2 拉丁方的嵌入式设计和相异代表系  43-44
  4.4 主泛对角线拉丁方的缺陷填充问题的NP 完全性探索  44-49
    4.4.1 主泛对角线拉丁方的缺陷填充问题的NP 完全性探索  44-48
    4.4.2 主泛对角线拉丁方与幻方的联系  48-49
  4.5 对角线拉丁方的缺陷填充问题的NP 完全性探索  49-50
    4.5.1 对角线拉丁方的两种嵌入式理论  49-50
    4.5.2 道路的选择  50
  4.6 缺陷反对称拉丁方的填充问题的NP 完全性证明  50-57
    4.6.1 预备知识  50-51
    4.6.2 构造过程  51-55
    4.6.3 缺陷反对称拉丁方的填充问题描述  55-56
    4.6.4 问题证明  56
    4.6.5 问题的推广  56-57
  4.7 本章小结  57-58
第五章结论与展望  58-60
  5.1 工作总结  58
  5.2 展望与设想  58-60
致谢  60-61
参考文献  61-64
作者在攻读硕士学位期间取得的学术成果  64

缺陷幻方填充问题的NP完全性判定研究

内容摘要

全文目录

相似论文