本科算法课程建设的一些实践与思考..doc

本科算法课程建设的一些实践与思考 摘要：本文介绍了北京航空航天大学计算机学院本科算法课程建设的现状，分析了目前教学中存在的问题，总结了教学方法上的实践经验，并对算法课程的建设提出了一些思考。br　　关键词：算法；课程建设；实践br　　　　　　br　　1算法课程建设的现状br　　br　　1.1课程的定位br　　《算法与数据结构(2)》主要讲述基本的算法设计方法以及对算法的时间、空间和其他方面进行度量分析。br　　算法，是程序设计的灵魂。著名的PASCAL之父、结构化程序设计的首创者、1984年“图灵奖”获得者尼克劳斯·沃斯曾说过：“数据结构+算法=程序”。这一公式在结构化程序设计已相当成熟的今天仍被视为经典。由此可见，算法在计算机科学中具有不可替代的重要地位。br　　据统计，美国2007年综合排名前50位的大学，欧洲名校如牛津、剑桥等均开设了算法课作为计算机专业的必修课。不仅如此，美国、欧洲一些普通高校的计算机专业也均开设了算法课。中国国家211工程重点建设的100所高等院校中有多于半数院校的计算机专业开设了算法课，国内的一流高校也将算法设计与分析作为计算机专业本科生培养的重要环节。br　　算法课程是高等学校计算机专业重要的专业基础课程之一，是计算机程序设计的重要理论和实践基础，是目前国内计算机专业研究生招生考试的首选专业基础课程，其独特的应用价值也使其成为信息类专业的重要课程之一。br　　算法课的先导课为离散数学、程序设计语言基础和数据结构。br　　1.2课程的目标br　　开设算法课的目标在于使学生通过该课程的学习，能够运用课程所讲授的概念和方法更好地进行算法设计，能够对已有的算法和新设计的算法进行一般的效能和性能上的分析，并进一步提高程序设计的能力。学好该课程的主要目的是打好专业基础，提高计算机理论和应用水平。br　　因此，我们要求学生能够掌握各种基本的算法设计方法(包括归结法、分而治之法、贪心法、动态规划和概率法等)，并能够掌握基本的算法分析方法(算法的时间复杂度与空间复杂度分析)，并在学习已有知识的基础上，加强思考和实践。br　　1.3课程的主要讲授内容br　　根据北航学生的实际情况，算法课程目前分为18学时，以课堂讲授为主，辅以参考资料阅读以及每章的课后作业和练习题。授课内容分为七章，分别为：算法分析的基础知识、归结法和分而治之法、贪心算法、动态规划算法、概率算法、下界分析和求解NP完全问题的算法设计。重点讲授内容包括：算法的控制结构、算法的复杂性分析、归结法和分而治之法、贪心算法的基本思想及特点、设计动态规划算法需要具有的前提及一般设计思路、主要的下界计算方法、回溯法和局部有哪些信誉好的足球投注网站算法等。br　　1.4课程的授课效果br　　通过课堂上学生的听课情况、对问题的反应程度以及对小测验的完成情况，我们可以看出部分学生对该课的兴趣和重视程度较高、预习工作做得较好，能将老师当堂所讲的内容消化和掌握；大多数学生能够在课堂上对老师所讲解的内容加以理解，并能在课后加以复习并掌握；一些学生尽管没有在课堂上对内容理解和消化，但仍能通过下课向老师提问或课后发Email给老师的方式向老师询问未理解的问题来加以反馈。br　　从课后作业的完成质量以及期末考试的卷面成绩来看，绝大多数学生能在学完算法课之后对计算机算法有一定的理解，并具备一定的算法设计与分析能力，达到该课程的基本要求，甚至有一些学生就此对算法产生了较浓厚的兴趣，并能在以后的学习时间里继续深入学习算法。课程达到了较好的授课效果。br　　1.5教学过程中发现的问题br　　在教学过程中，学生普遍暴露出不愿深入思考、不爱动手实践的问题。尽管这些原则在平时的授课过程中再三地被强调，但能按照老师建议去做的人并不多，仅限于少数对算法有较大兴趣的学生。br　　从试卷情况来看，一些同学仍然缺乏将算法思想应用于同类问题求解中的能力，出现了同类问题不知道用同类算法求解的情况。究其原因在于未能将算法思想深入理解，做过的习题较少，对于同类问题无从下手。为应付考试而死记硬背某些算法，这是学习算法的大忌。br　　另外，部分学生对先导知识的掌握还有欠扎实，对基础知识和概念的掌握程度成了一些算法内容理解的瓶颈。br　　br　　2教学方法上的一些实践经验br　　br　　2.1提高学生学习基础课程的兴趣br　　从一定角度讲，兴趣是最好的老师，因此我们在讲述课程的过程中会经常从学生们感兴趣的问题入手，为他们创造易于理解问题、加深记忆的活跃的课堂气氛和环境。br　　我们在介绍一个算法问题时，首先介绍问题的背景，如河内塔游戏、斐波那契数列等。在教学过程中，我们将本课程学科的发展历史、前沿知识和自己从事科研实践的体会与成果贯穿于教学中，例如蒙特卡洛概率算法与SAT问题等均是两