论文NP难解问题的教学方法，本文是教学方法类论文写作技巧范文和教学方法和教学方法探讨和难解方面毕业论文题目范文.
（上海工程技术大学电子电气工程学院,上海201620）
摘 要：NP难解问题,由于其理解起来的难度,加之目前本科生中普遍存在的学习和思想误区,实际教学难以取得理想的效果.有鉴于此,讨论了两种教学方法,旨在使难于理解的抽象问题转换为具体的有趣问题,降低初学者理解NP难解问题的难度,唤起学生的学习热情,提升教学效果.
关键词：理论计算机科学；NP难解问题；多项式时间归约；整数规划问题；可满足性问题
中图分类号：G434
文献标识码：A
文章编号：1672-7800(2018)04-0082-02
1 现状分析
NP难解问题是一类理论上可解,但为了获取其解需要耗费大量的时间和空间的计算问题.该章节的教学是离散数学中最难的部分,在当前教学中存在急功近利、代码为王、数据为王、程序不思其解只要运行结果的思想,学生对理论的学习缺乏学习积极性,望而生畏.要想改变这一部分教学内容的教学现状、提升教学效果,需要从以下几方面改进.
2 教学方法探讨
2.1 利用启发式教学引导学生体会难解问题的“难”之所在
难解问题的传统教学模式是,首先介绍图灵机数学概念,尤其是确定性图灵机和非确定性图灵机的概念,然后介绍P类问题和NP类问题,并通过引入归约的概念,证明在NP类问题中存在一个子类,所有的NP类问题都可以在多项式时间内转化为此类问题,即,NP完全问题.这些知识点,充斥着大量的概念和严格符号化的证明,要想获得良好的教学效果,必须转换教学理念,使抽象的理论具体化,让学生通过实例去理解和体会为什么有些问题比另一些问题“难”,而有些问题甚至对计算机都是“难解”的.
比如,四则运算中加法更简单,因为两个一位数相加,至多是两位数,两个n位数相加,至多是n+1位数,两个n位数相加的算法复杂度为O(n),这里以一位数的加法为基本操作.继续考虑乘法,类似的,两个一位数相乘需要背一次乘法口诀,两个n位数相乘,需要乘数的每一位去乘被乘数的每一位,因此,需要背.’次乘法口诀,之后还要把得到n行数加起来,这又起码是n-l次n位的一位数加法,因此,不难理解两个n位数相乘的算法复杂度为O(n’),即,乘法比加法更复杂.
进一步,可以让学生思考乘法的反方向问题,分解因子.对于很小的合数,我们利用较小的素数因子2、3、5等去除它可以很快的进行分解.但是对于较大的数,比如,这个129位的整数,114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541．人类无法完成分解.事实上,这个大数也正是1977年RSA加密算法的创始人向全世界提出的挑战,当时估计四万兆年后人类才能完成它的分解.当然,借助于计算机的帮助,17年后的1994年,研究人员总共动用1 600部电脑花了8个月的时间得到了分解的结果.通过这一组简单易懂的实例的讲解,学生可以很好的体会高复杂度的计算对计算机而言也是难解的.在此基础上,再给学生引入多项式时间复杂度和指数时间复杂度的分类,学生也就更易理解.
更进一步,虽然对129位整数进行因子分解是一个很难的问题,但如果让它除以3490529510847650949147849619903898133417764638493387843990820577这个64位整数,虽然除起来也很花时间,但只要有足够的耐心和细心,哪怕是小学生也能算出来结果,因为除法是一个多项式时间复杂度的算法.事实上,它的确是那个129位数的一个因子.那么,如果某人灵机一动,猜到了这个数,只需除一下检验猜测的是否正确即可.到这里,学生就可以体会出,有那么一类问题,虽然直接求结果,哪怕对计算机而言也是很难的,但是,如果可以猜测结果的话,则可以在多项式时间内验证猜测.这里就引入了NP类问题,即,先猜测一个结果,再利用多项式时间复杂度的算法进行检验.
2.2 灵活运用实例降低难解证明的理解难度
虽然有很多问题可能都是NP类问题,也都很难,但怎么衡量它们之间的难易程度,这就需要引入多项式时间归约和NP完全性的概念.
传统的NP完全性归约的证明讲解,首先是介绍Cook定理证明合取范式的可满足性问题SAT的完全性,然后引入一些经典的问题,设计一个由SAT传递归约的路线,同时总结证明NP完全性的一些技巧.比如,在Garey＆Johnson的经典名著《计算机与难解性》一书中,作者先给出了SAT问题的特例3SAT、“三维匹配问题”(3DM)、“顶点覆盖问题”( VC)等6个问题,然后通过将SAT归约为3SAT、将3SAT分别归约为3DM和VC等证明它们的NP完全性,并总结了限制、局部代换和组件设计等证明技巧.这些证明中的某些技巧,从SAT到3SAT相对比较容易理解,但多数证明中用到的技巧,只能让初学NP完全性证明的人叹为观止但敬而远之.其它书籍中用到的证明思路,也大体类似,所不同的就是选择的典型问题或者是归约证明的路线.
事实上,相对容易理解且更能吸引学生兴趣的是一类特殊的优化问题——线性规划,尤其是整数线性规划问题.一般地,线性规划问题,是对形如以下形式的问题
寻找满足约束条件的目标函数的最优值,可以是最大值或最小值,其中c、X均为.维列向量,A为mXfl的矩阵,B为m维列向量.而整数线性规划,不仅需要约束条件矩阵A、向量B和c中各值为整数外,还进一步要求X中的值也得为整数.正是这个为整数的要求,使得整数线性规划问题成为一个经典的NP难解问题.为此,在课堂教学中,可以将某些经典NP难解问题作为教学案例,通过将它们归约为整数规划问题,从而说明这些难解问题并不比整数规划更难,也可以大大降低学生理解的难度.
的整数规划问题.其中,约束条件保证了2：等于1当且仅当析取项F,可满足.由于SAT问题是由Cook证明了的第一个NP完全问题,它的优化版本最大可满足性问题可归约为整数规划问题,所以,SAT问题不比整数规划更难,利用将其他难解问题归约为整数规划问题,就可以证明更多的NP完全问题.
3 结语
可以看出,通过启发学生思考问题的难解程度以及基于整数线性规划讨论难解问题归约的教学策略,相比着传统的讲解,其理解的难度大大降低,有助于学生理解难解问题.尤其是在学生解决实际算法问题时,当设计求解某些问题的高效算法而百思不得其解时,可能就需要换种思路,证明这个问题是NP难解的,进而说明这类问题不大可能存在高效的算法.而对于一个NP难解问题,就可以引导学生通过考虑特殊情形、概率分析、近似算法或启发式算法等策略求解.当然,这些教学策略的不足是减少了学生欣赏原始证明中的那些奇妙构造的机会.可在学生理解NP完全问题及其归约的基础上,介绍更多的例子加以补充,以达到既降低了理解难度,又开阔学生视野的效果.参考文献：
[1] GAREY M, JOHNSON D.Computer and Intractability[Ml.
New York: W. H. Freeman and Company,1979:46-74.
[2] JURAJ H. Algorithmics for hard problems[M]. Springer,
2：211-218．
[3] SANJOY D,CHRISTOS P,UMESH V．算法概论[M].北
京：机械工业出版社,2009：247-263．
[4] 姚雪梅,“编译原理”课程的教学探索[J].重庆交通学院学报：
社科版,2003(6)：85-86.
[5] 谭永基,离散型数学模型问题的计算复杂性简介[J].数学的
实践与认识数学的实践与认识,1997(2)：141-147.
（编辑：叶 露）
评论：这篇文章为适合教学方法和教学方法探讨和难解论文写作的大学硕士及关于教学方法本科毕业论文，相关教学方法开题报告范文和学术职称论文参考文献.
参考文献：
1、 高中语文开放式作文教学方法探究 摘要阅读能力和写作能力是高中生必备的能力,对学生学习其他学科甚至未来走上工作岗位都有着极其重要的意义 培养良好的阅读和写作素养不仅可以使学生有好的文笔,而且能锻炼学生的逻辑思维能力,对学生的长期发展有.
2、 关于小学古诗教学方法的探究 【摘要】古诗词教学是传承中华文化精髓,弘扬中华传统美德,熏陶学生精神的必要手段,在2000年颁发的九年义务教育全日制小学语文教学大纲中明确指出小学阶段古诗词的教学目标是背诵优秀诗文不少于150篇,低年.
3、 高中生物教学中探究性教学方法应用分析 【摘要】为了开拓学生的视“,培养学生发散式解题思维方式,要求我们要改变传统的教学方式,实行探究性教学……新式教学方法 教师要利用探究性教学方法提高学生的综合学习和接收知识的能力 为了让教师.
4、 小学高年级语文作文教学方法探析 【摘要】小学高年级作文教学过程中,教师要加强引导作用,鼓励学生进行素材的积累,为学生素材积累提供多种方式,为学生素材量变引起质变打下坚实的基础,同时在写作技巧、写作情感表达方面做好具体的设计工作,提升.
5、 低年段词语理解教学方法 摘要词语教学是小学语文教学中不能缺少的一个环节,亦是小学低年段语文教学的重点 教师需要根据学生各方面的差异选择适合的教学方法,如联系上下文来理解词语、联系生活体会词语及创设情境理解词语…… 教师从课文.
6、 特朗普怒怼马克龙，美欧分歧难解 美国总统特朗普和法国总统马克龙之间的友好情谊似乎遭遇了瓶颈 在“美国优先”政策下,随着美国和欧洲之间因为贸易、北约经费……的分歧日渐加剧,特朗普和马克龙之前看似亲密无间的关系也.