《算法设计与分析》的理论研究与教学实践

2012-08-15田翠华王伟杰许卫平

赤峰学院学报·自然科学版 2012年15期

关键词：过桥过河毛毛

田翠华,王伟杰,许卫平

（1.厦门理工学院计算机科学与技术系，福建厦门 361024；2.沈阳工业大学软件学院，辽宁沈阳 110023）

《算法设计与分析》的理论研究与教学实践

田翠华1,2,王伟杰1,许卫平1

（1.厦门理工学院计算机科学与技术系，福建厦门 361024；2.沈阳工业大学软件学院，辽宁沈阳 110023）

通过对《算法设计与分析》的理论进行深入研究，并结合自己实际的教学实践，充分地认识到这门课的重要性、了解这门课的特点.并对存在的问题进行分析，在此基础上提出了更好的教授这门课程的方法与更能促进这一学科发展的策略，形成自己的特色教学.

算法；游戏教学；特色教学

《算法设计与分析》是计算机科学的一个重要分支，是计算机科学的基础，更是程序设计的核心[1].所以，算法课程对计算机系学生来说非常重要，是计算机系软件、硬件等专业必修的基础课程.而且，算法所涉及的范围十分广泛[2]，从理论到各种实际问题的解决，无一不与算法有密切关系，都需要研究方法.同时，算法研究又是实现计算机解决问题的方法，十分的抽象与复杂，这些都导致学生对这门课的学习非常困难.

1 理论研究与教学实践

在没教《算法设计与分析》这门课程的时候，只听说它与多门课程教学紧密相连，所以，针对教这门课的教师来说，其教学理论基础必须深厚，教学实践经验必须丰富.教过之后，才知道它涉及的又何止是教学的理论基础与实践？还需要工程实践经验[3-4].幸亏在软件公司搞软件开发工作多年，有实际的编程经历.想起接这门课的时候，人们都说这门课不好讲，当时，还不能理解这句话的份量，直到现在通过实际教学亲身体验后，才明白其中的道理.

1.1 相关知识多

学这门课的学生，要求具备很多学科的知识：高等数学、离散数学、线性代数、概率论、数据结构、C语言等等.这样由于对以上某些学科有些薄弱的学生，学起这门课就会有些吃力.例如，如果数学基础不好，逻辑思维不清晰，学生往往对数学比较抽象的运用，如某些证明，就会感到难以理解.再比如，学生对数据结构的学习也不够扎实，对递归技术、堆排序、搜索等技术掌握不够牢靠，学习起来也不能顺利，例如，留作业：写出用递归技术实现两个八项式相乘的过程，其实只是规模稍微大了一点、复杂度高了一点，就没有一个能给出完全正确的答案.学生不知道递归到底是如何进行的，只知道一层一层的调用，调用到最后一层，再一层层的返回，简单的问题学生理解没问题，但复杂了就不知道具体怎么执行了，特别是每一层返回到哪里、继续执行哪里，就都不清楚了；也不知道堆是如何建立、如何排序的.这样，他们怎么能对具体问题提出算法并对算法进行很好的分析并设计呢？

1.2 学时少

安排32学时，16次课，在去掉教师节、中秋节、十一放假与运动会，作为教师除了讲些基本的理论知识内容外，就无法深入挖掘出学生的算法这方面的的天分与资质，也无法激发学生的热情而使之投入到算法的研究中去.因为，学生的时间也很紧，要修学分，要修专业课，要面对英语过级考试，要参加各种活动，要找实习工作准备毕业.所以，对于算法这门范围广、内容丰富学的学科，32学时显得很不够用.

1.3 缺少实践

这门课程没有安排上机学时，学生不能将学到的东西在机器上运行验证，以加深对某些具体算法的理解与分析，因而也难以提出新的见解与方法，更不能设计出具有突破性的优秀算法.当然，这需要良好的环境，需要有资金的投入.

2 特色教学

发现了上述所存在的问题以后，开始研究实际教学，不断寻找解决问题的方法.下面给出自己的实际操作过程中运用的方法与策略.

2.1 明确学习算法意义

首先要关心这一学科的发展，大量收集有关资料，使学生明白学习算法意义重大.在算法的发展史上，关于平面图判断问题曾经困扰人们很长时间.虽然这个问题在教学上早在1930年就由波兰数学家Kuratowshi解决，但是，实现起来确实很难.对于有100个顶点的图，用普通的算法，计算机需要1万亿步才能确定其是否为平面图.因此，寻找高效的平面图测试算法成为摆在当时计算机科学家面前的一大难题.正因为解决此难题才使John和Robert获得了1986年的图灵奖，他们创造了“深度优先搜索算法”（depth–first search algorithm）.利用这种算法对图进行搜索时，节点扩展的次序是向某一个分支纵深推进，到底后再回溯，这样就能保证所有的边在搜索过程中都经历过一次，并且只经过一次，从而大大提高了效率.新算法的运行时间是线性的，大小翻一倍，求解问题所需的时间也只翻一倍.相比之下，若用Kuratowshi判断的老算法，那么当图的大小翻一倍时，所需时间要增加60倍以上.利用他们创造的新算法，Robert用Algolw为一个包含900个节点和2694条边的图编制一个测试其平面性的程序，程序只有500行，在IBM360/67上运行，只用了12秒就得到了结果.John和Robert把他们的研究成果写成论文在《Journal of the ACM》上发表，引起学术界很大的轰动.而他们创造的深度优先算法则被推广到信息检索、国际象棋比赛程序、专家系统中的冲突消解策略等许多方面.不久，他们又提出了一种新的数据结构叫“双堆栈叠”（pile of twin stacks），这种新的数据结构被深度优先搜索算法的优点更加发扬光大.Robert的一个学生用这种新的数据结构和算法编写了一个Algolw程序，只有250行，在IBM 370/168上测试有8000个节点的图的平面性只用了8秒钟.

2.2 激发学生兴趣

引入game-to-teach理念，提出游戏教学方法，即针对教学内容知识点设计游戏.例如，在我在最后引导学生了解前沿技术平行算法的时候，为了更好地讲解为什么需要算法并行化的过程中，设计一家五口三代人夜晚提灯来到独木桥前过河回家的游戏.游戏描述：一天夜晚，毛毛一家人提着一盏油灯，来到河岸边.河面上有一个到达对岸的独木桥，只能支撑两个人提灯过河.之后，还要有人把灯送回来，使得其他人可以提灯照明继续过河.每个人过河速度不同，毛毛、爸爸、妈妈、爷爷奶奶过河的速度分别是1秒、3秒、6秒、8秒、12秒.每次过河的两个人速度以最慢的计，灯的油可以燃烧30秒.怎么安排过河，才能在有限的时间30秒内使全家安全通过呢？如果超时，灯熄灭了，没了灯光，看不见，在桥上的人则掉到河中，就会过河失败.给同学思考过河方法5分钟，其间我在黑板上画出游戏场景，没有任何思考地按顺序安排过河，先是毛毛提灯和爸爸过河，毛毛送灯回来；毛毛提灯和妈妈过河，毛毛送灯回来；毛毛提灯和爷爷过河，毛毛送灯回来；毛毛提灯和奶奶过河，时间到，毛毛和奶奶都掉河里啦，过河失败！然后问大家：为什么没成功？学生回答：没有合理搭配的不同速度的人过河.怎么搭配？马上有同学站起来说：第一步：选择1秒钟过桥的人与3秒钟过桥的人同时过桥，这样就能够将1秒钟过桥的人给并掉，时间只用了3秒钟；第二步：让3秒钟过桥的人回去，用时3秒.选择8秒钟过桥的人与12秒钟过桥的人同时过桥，这样就能够将8秒钟过桥的人给并掉，时间只用了12秒钟；第三步：让1秒钟过桥的人回去，用时1秒.选择1秒钟过桥的人与6秒钟过桥的人同时过桥，这样就能够将1秒钟过桥的人给并掉，时间只用了6秒钟；第四步：让1秒钟过桥的人回去，用时1秒.选择3秒钟过桥的人与1秒钟过桥的人同时过桥，这样就能够将1秒钟过桥的人给并掉，时间只用了3秒钟.总共用时29秒，过河才成功！游戏短小精悍，过程生动有趣.最后，我用多媒体总结：成功的关键是使用并行化设计技术！算法的并行化是非常必要的，是真正提高速度的根本，是我们非常需要的！经过这样实际演练学习，学生的兴趣极高，同时，对并行性的理解再深刻不过，达到了教与学的最佳境界.

2.3 提高学生主观能动性

不管教的有多好，关键还在于学生主动学习.所以，让学生知道当前还有很多重大问题有待解决这很重要.在讲到希尔排序所存在的问题时，结合算法目前存在的问题进行全面分析：一是有些问题跟本就没有算法；二是有算法但欠缺完善的分析，希尔问题就属于这种情况；三是有些问题尚有算法但已过时满足不了要求是针对内存小而借助外设来实现的算法，已不适合现在内存大外设更大的实际情况.所以，结论是需要大量的优秀算法.那么这些任务有谁来完成呢？当然是现在学习的学生，是正在学习算法又了解算法非常需要他们的学生.特别是，我国在这方面的发展还不够，更需要他们不断地努力以便能在这个领域中做出更大的贡献.通过这些工作，让学生了解到这一学科的重要性，激发他们的兴趣，是他们意识到自身的责任重大，促使学生能在主观上下决心学好这门课，进而才能更好地发展这一学科.

2.4 实例法

在讲到贪心法的作业调度[5-7]的时候，讲了作业的顺序选择法和最大期限选择法两种.当时，觉得前一种很简单就直接讲了选择思想及其实现算法，而后一种觉得有些难就多加了例子，结果学生非常明白后者反倒觉得前者很难.从中看出，空讲理论实效并不大，结合实例具体化更容易接受.从那以后，就多准备例题，效果很好.而且，把这些积累下来，还有每次上课的材料，就形成了自己的讲义教案与习题集.这对以后讲这门课，做多媒体课件，都方便多了；对学生，有习题集做辅导材料，学起来更轻松、学的效果也更好.

2.5 分组大作业

在讲完每一章之后，给同学们布置作业，希望他们做作业的同时能看看书，起到复习巩固强化教学效果的作用，而且要求同学们做作业的时候要相互研究交流，拓展思路，提高效率.根据作业量的不同将同学分成不同的组，多时分十几个组，每组十多个同学做同样的作业；少时则分几个组每组几十个同学做同样的作业.通常每组留1～2道题，实际上每个同学也就做一道，简单时就做两道.但当任务特别重时，因为要将布置的作业先形成答案，然后在输入计算机，运行验证，再形成文档，这样才能将收上来的作业进行仔细的评改，再发下去.而上的是大课，四个班大约一百二十人左右.所以，工作量很大.但我觉得值，虽然我很辛苦，因为在考试验收时学生通过率明显提高.