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.
（编辑：叶 露）
总结：上文是一篇大学硕士与教学方法本科教学方法毕业论文开题报告范文和相关优秀学术职称论文参考文献资料，关于免费教你怎么写教学方法和教学方法探讨和难解方面论文范文.
高中数学教学方法与实施策略
盛华山如何引导高中生进行有效的数学学习、掌握科学合理的学习方法、形成端正的学习态度,一直以来都是众多教师所共同关注的问题 众所周知,高中数学这门学科具有较强的抽象性和逻辑性,因此很多学生的学习效率一直.
小学低年级数学的趣味性教学方法
【摘要】小学低年级学生正处在数学意识发展的初期阶段,各方面的能力素质还处在较低层次,那么低年级的数学教学就要认真分析并且遵循学生的认知规律,启迪学生的数学意识,初步发展学生的数学思维,利用趣味性的教学.
小学语文识字写字教学方法探究
高小燕对于小学生而言,他们还处在一个好玩爱动的年龄,让他们一节课45分钟,坐在课堂上认真的听讲是完全不可能的一件事情 因此,教师在进行小学语文课程教学的时候,应当注重孩子们兴趣的培养 识字、写字是小学.
耶路撒冷：和平之城难解纷争
耶路撒冷在希伯来语中意为“和平之城” 可是,千百年来“和平之城”难见和平,而是冲突不断,纷争难解 上世纪40 年代以来,更是成为巴以冲突地、中东&ldq.