论文部分内容阅读
摘要：算法设计与分析是计算机专业的核心课程，是理论性、实践性和工程性都很强的一门专业课。本文以知识建构理论为指导，提出算法设计与分析的教学内容的设计。以探究式理论为指导，在实际教学中提出“案例教学、项目驱动、团队合作”的教学法，结合教学实践，旨在提高教学效果。实践证明，在知识构建和探究式理论的指导下，并结合教学实践，取得了良好的成效。
关键词：探究式；构建主义；算法设计与分析
中图分类号：G642.0 文献标识码：B／A 文章编号：1812-2485(2011)03-015-04
算法设计与分析是计算机科学与技术中处于核心地位的一门专业课，CC2001和CC2002都将“算法和复杂性”列为主领域。该课程是计算机程序设计的重要理论和实践基础，其独特的应用价值也使其成为信息类专业的重要课程之一。据统计，在美国、欧洲各名校均开设了算法设计与分析课程，并且国外的一些普通高校的计算机专业也都相继的开设了改课程课；在国内，国家211工程重点建设的100高等院校有多于半数院校的计算机专业开设了算法课，普通省属高校也将算法设计与分析课程作为计算机专业本科生培养的重要环节。
我们以知识建构和探究式两种现代理论为指导，并将其应用到教学实践中，改变传统教学中的教师讲、学生听的教学模式，充分发挥学生学习的主动性，注重提高学生的工程能力，培养学生的创新能力。本文将知识构建理论和探究式方法用于算法设计与分析教学，对教学内容整合，阐述算法设计与分析的构建主义教学理念，根据学生学习的认知规律和探究式教学模式，旨在提高本课程的教学质量。
1. 知识建构指导下的教学内容的设计
在认识论上，建构主义在认知主义的基础上发展了主体内部的新旧经验之间的互动。建构主义心理学认为，知识不是被动吸收的，而是由认知主体主动建构的。将建构主义学习理论较早成功应用于科学教育领域的创建人之一的杰亚夫(R.Drive)研究发现：学生的科学学习成绩与先前的经验要比通常意义上认知水平显示更大的相关性。
建构主义教学理论作为一种新的教学理论，在国内积极地向教学实践中发展。随着多媒体技术和现代网络通信技术在教学中的应用日益广泛，基于建构主义的教学也在逐渐地深入发展。比如北京师范大学何克抗教授系统地提出了建构主义的教学模式、教学方法与教学设计。
我们以建构主义为指导，学生与周围环境的交互作用，对于知识意义的建构起着关键的作用：教师应组织和引导学生讨论和交流，建立学习群体，共同对算法设计与分析课程所涉及的内容讨论。
1.1 课程的知识点及关系
本课程的知识点及相互关系如图1所示。计算机科学把问题作为自己的研究对象，对问题的研究无论是学习算法还是应用算法都是极其重要的。本课程将围绕的主要问题包括查找问题、排序问题、图问题、组合问题、几何问题；计算复杂性包括算法的空间复杂性和时间复杂性；学习的算法设计技术包括蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等；NP完全理论包括P类问题、NP类问题、NP完全问题；算法的描述语言采用C++语言。
1.2 与数据结构课程内容的衔接
本门课程的先导课程是C++语言、数据结构，这三门课程紧密相关，特别是数据结构课程与算法设计与分析课程教学内容合理安排，对提高课程教学具有重要意义，福州大学的傅清祥老师提出将数据结构课程与算法设计与分析课程这两门课程的内容整合，考虑到本校的实际情况，我们在教学计划中还是将两门课程分开讲授，如何做好这两门课程的衔接是问题的关键，
为了使这两门课做好衔接，将交叉的内容划分，使知识点不重复讲解，如表1所示，教学内容的调整，两门课程做衔接前。存在知识点的重复讲解，要用12学时左右讲解重复的内容：调整后，将同一知识点分别在两门课中讲解，不再重复，节省学时，很明显。课程如果衔接好对教学很有帮助。
1.3 教材和参考书目的选择
基于上述的知识结构和课程衔接后的教学内容，我们的教材和参考书选用清华大学出版社的三本书。将王红梅编写的“算法设计与分析”作为教材，郑宗汉编写的“算法设计与分析”和王晓东编写的“算法设计与分析”作为参考书。在教学过程中，汲取各自的精华，同时融入我们的项目实践和教学经验，形成具有教学特色的内容组织和安排。
2. 探究式指导下的教学模式设计
探究式学习是美国著名科学家、芝加哥大学教授施瓦布倡导提出的，所谓探究式的教学模式是指学生在学习概念和原理时，教师只是给他们一些事例和问题。让学生自己通过学习观察、思考、讨论、听讲等途径去独立探究，自行发现并掌握相应的原理和结论的一种方法，
2.1 对教师的要求
在“知识建构和探究”式教学中，教师除了具备一般的专业知识和教学技能外，还要注重以下的能力：
2.1.1 掌握学生的心理状态的能力，在探究过程中，从学生面部表情是严肃、凝重的，还是茫然、无所适从的，从中把握学生探究活动进行的情况，进而调整自己的教学；在知识建构中，从学生的语言表述中，“透视”学生的思维活动，从而有针对性的促进知识建构。
2.1.2 主导教学的能力，现代大学生自主性强、思维活跃，“探究——建构”式教学需要创造一个开放的、情境化的学习环境，教师若没有较强的主导教学的能力，课堂会很容易失去控制。
在“知识建构和探究式”教学中，主导教学的能力主要体现在“导学”上。要把学生的活动、思维聚集在探究和建构过程中，使学生兴致盎然地参与到各种学习活动中，这就要求教师不仅是知识的传播者，要成为学生知识建构的高级伙伴和科学探究的引导者，成为学生发展的促进者。
2.1.3 教学设计的能力在教学实践中，教师应对知识领域的新知识，新技术准确把握，比如，很多教师将ACM竞赛引入教学，培养学生自主学习能力、创新能力、团队合作能力，做到恰当的引导，给学生带来事半功倍的学习效果。
2.2 探究式的算法设计与分析教学模式
我们采用探究式的算法设计与分析教学模式时，主要从以下几个方面来改进教学。
2.2.1 将知识的传授与能力培养相结合。研究并改进的算法设计与分析教学方式，减少教学过程中的讲授教学比例。以建构主义教学学习理论、人本主义心理学理论以及发现法教学理论为依据，构建以案例为核心的探究式算法设计与分析教学模式。案例教学也有利于学生掌握理论知识，并运用知识解决工程中的实际问题。通过采用现代多媒体技术实现算法的动态演示，提高学生的学习兴趣，将复杂问题简单化。
2.2.2 引入ACM程序设计大赛题目。ACM比赛过程中最强调的：采用最优算法、最短时间、最准确的完成给出的题目答案。将ACM引入教学有两个目的：一是教师通过精心设计的启发式教学，引导学生深入理解图1所示的七种算法设 计技术，从而引导学生在遇到ACM比赛题目时选择何种算法设计方法；二是帮助学生熟悉ACM比赛，激发学生的学习兴趣。
2.2.3 自主学习模式。给学生明确的教学目标、要求，按教学计划自主浏览多媒体课件，理解教学内容，发现问题、分析问题和解决问题。比如，让学生采用“贪心算法”来完成售货员找硬币问题，使得所拿出的硬币个数最少。学生应自己分析算法、编码实现，并分析时间复杂性。
2.2.4 团队合作法教学。每个学期挑选一个较为大型的项目，模拟实际工作中的角色给同学们分工，要求学生按照要求完成指定的项目，每个项目组最后演示他们的成果，其他小组作为裁判给出评价。在实际操作中还可以将教师的科研项目让学生完成，让学生在实际工作中体会团队合作的意义。除参加ACM大赛外，还可以让学生以团队合作的方式积极参加每年一次的学校组织的“大学生挑战杯程序设计大赛”。
3. 教学实践
3.1 教学案例
基于上述原则，结合算法设计与分析课程的特点选取一些实际问题，讲解一个具体的应用实例，从而使学生掌握算法设计的一般过程，如图3所示。
传统的教学方式，本课程期末时，给学生留个大作业完成“某项目的算法设计”；而本门课程在第一次课就让学生先自选题目，然后教给老师，教师要随着课程的进展进行阶段性的检查，期末学生提交本作业。下面采用蛮力法处理组合问题的应用，对“0／1背包问题”进行处理。
3.1.1 理解问题。
3.1.2 分析问题。
3.1.3 具体应用数据。
如图4所示，一个容量为10的背包和4个物品，采用蛮力法求解0／1背包问题。
3.1.4 求解过程演示。
3.1.5 分析算法的效率。
对于一个具有n个元素的集合，其子集数量是2n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个Ω(2n)的算法。
3.1.6 算法实现。
略。
最后，总结蛮力法求解问题的过程，分析该方法的时间复杂性。
3.2 教学考核环节
课程成绩=理论考试(占总分60％)+实训项目(占总分40％)
本课程结束后，学生能独立完成软件项目的算法设计任务，并提交一份规范的算法设计说明书。
4. 结束语
建构主义的教学目的是为了让学生获得完整、深刻、能够灵活运用的知识；同时，在科学探究中也培养了学生的探究能力，包括发现问题的能力，提出假设的能力，设计实验的能力，分析数据的能力和归纳结论的能力。
本文以算法设计与分析课程为例讨论了计算机专业课程开展“知识建构和探究式”的教学方式的尝试，取得了初步的效果，一定程度上促进了学生算法设计方面能力的提高。但是仅仅本课程的改革是远远不够的，这一新的教学方法值得进一步完善和改进以及在其他计算机专业课程中的教学实践中加以推广和应用。
参考文献
1. Drive.R.Easley.puppies and paradingms：A review ofliterature to concept development in adolescent sciencestudents[J].studies in science Education，1978，(5)：61-84.
2. 何克抗，建构主义的教学模式、教学方法与教学设计[J]，北京师范大学学报(社会科学版)，1997，(5)：76.
3. 伍宏珏，由ACM看《算法设计与分析》教学改革[J]，九江学院学报，2009，(6)：120－123.
4. 王红梅，算法设计与分析[M]，北京：清华大学出版社，2006：58-70.
5. 于合龙，辩证法和认识论指导下的C++程序设计教学[J]，计算机教育，2010，(22)：60-66.，
关键词：探究式；构建主义；算法设计与分析
中图分类号：G642.0 文献标识码：B／A 文章编号：1812-2485(2011)03-015-04
算法设计与分析是计算机科学与技术中处于核心地位的一门专业课，CC2001和CC2002都将“算法和复杂性”列为主领域。该课程是计算机程序设计的重要理论和实践基础，其独特的应用价值也使其成为信息类专业的重要课程之一。据统计，在美国、欧洲各名校均开设了算法设计与分析课程，并且国外的一些普通高校的计算机专业也都相继的开设了改课程课；在国内，国家211工程重点建设的100高等院校有多于半数院校的计算机专业开设了算法课，普通省属高校也将算法设计与分析课程作为计算机专业本科生培养的重要环节。
我们以知识建构和探究式两种现代理论为指导，并将其应用到教学实践中，改变传统教学中的教师讲、学生听的教学模式，充分发挥学生学习的主动性，注重提高学生的工程能力，培养学生的创新能力。本文将知识构建理论和探究式方法用于算法设计与分析教学，对教学内容整合，阐述算法设计与分析的构建主义教学理念，根据学生学习的认知规律和探究式教学模式，旨在提高本课程的教学质量。
1. 知识建构指导下的教学内容的设计
在认识论上，建构主义在认知主义的基础上发展了主体内部的新旧经验之间的互动。建构主义心理学认为，知识不是被动吸收的，而是由认知主体主动建构的。将建构主义学习理论较早成功应用于科学教育领域的创建人之一的杰亚夫(R.Drive)研究发现：学生的科学学习成绩与先前的经验要比通常意义上认知水平显示更大的相关性。
建构主义教学理论作为一种新的教学理论，在国内积极地向教学实践中发展。随着多媒体技术和现代网络通信技术在教学中的应用日益广泛，基于建构主义的教学也在逐渐地深入发展。比如北京师范大学何克抗教授系统地提出了建构主义的教学模式、教学方法与教学设计。
我们以建构主义为指导，学生与周围环境的交互作用，对于知识意义的建构起着关键的作用：教师应组织和引导学生讨论和交流，建立学习群体，共同对算法设计与分析课程所涉及的内容讨论。
1.1 课程的知识点及关系
本课程的知识点及相互关系如图1所示。计算机科学把问题作为自己的研究对象，对问题的研究无论是学习算法还是应用算法都是极其重要的。本课程将围绕的主要问题包括查找问题、排序问题、图问题、组合问题、几何问题；计算复杂性包括算法的空间复杂性和时间复杂性；学习的算法设计技术包括蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等；NP完全理论包括P类问题、NP类问题、NP完全问题；算法的描述语言采用C++语言。
1.2 与数据结构课程内容的衔接
本门课程的先导课程是C++语言、数据结构，这三门课程紧密相关，特别是数据结构课程与算法设计与分析课程教学内容合理安排，对提高课程教学具有重要意义，福州大学的傅清祥老师提出将数据结构课程与算法设计与分析课程这两门课程的内容整合，考虑到本校的实际情况，我们在教学计划中还是将两门课程分开讲授，如何做好这两门课程的衔接是问题的关键，
为了使这两门课做好衔接，将交叉的内容划分，使知识点不重复讲解，如表1所示，教学内容的调整，两门课程做衔接前。存在知识点的重复讲解，要用12学时左右讲解重复的内容：调整后，将同一知识点分别在两门课中讲解，不再重复，节省学时，很明显。课程如果衔接好对教学很有帮助。
1.3 教材和参考书目的选择
基于上述的知识结构和课程衔接后的教学内容，我们的教材和参考书选用清华大学出版社的三本书。将王红梅编写的“算法设计与分析”作为教材，郑宗汉编写的“算法设计与分析”和王晓东编写的“算法设计与分析”作为参考书。在教学过程中，汲取各自的精华，同时融入我们的项目实践和教学经验，形成具有教学特色的内容组织和安排。
2. 探究式指导下的教学模式设计
探究式学习是美国著名科学家、芝加哥大学教授施瓦布倡导提出的，所谓探究式的教学模式是指学生在学习概念和原理时，教师只是给他们一些事例和问题。让学生自己通过学习观察、思考、讨论、听讲等途径去独立探究，自行发现并掌握相应的原理和结论的一种方法，
2.1 对教师的要求
在“知识建构和探究”式教学中，教师除了具备一般的专业知识和教学技能外，还要注重以下的能力：
2.1.1 掌握学生的心理状态的能力，在探究过程中，从学生面部表情是严肃、凝重的，还是茫然、无所适从的，从中把握学生探究活动进行的情况，进而调整自己的教学；在知识建构中，从学生的语言表述中，“透视”学生的思维活动，从而有针对性的促进知识建构。
2.1.2 主导教学的能力，现代大学生自主性强、思维活跃，“探究——建构”式教学需要创造一个开放的、情境化的学习环境，教师若没有较强的主导教学的能力，课堂会很容易失去控制。
在“知识建构和探究式”教学中，主导教学的能力主要体现在“导学”上。要把学生的活动、思维聚集在探究和建构过程中，使学生兴致盎然地参与到各种学习活动中，这就要求教师不仅是知识的传播者，要成为学生知识建构的高级伙伴和科学探究的引导者，成为学生发展的促进者。
2.1.3 教学设计的能力在教学实践中，教师应对知识领域的新知识，新技术准确把握，比如，很多教师将ACM竞赛引入教学，培养学生自主学习能力、创新能力、团队合作能力，做到恰当的引导，给学生带来事半功倍的学习效果。
2.2 探究式的算法设计与分析教学模式
我们采用探究式的算法设计与分析教学模式时，主要从以下几个方面来改进教学。
2.2.1 将知识的传授与能力培养相结合。研究并改进的算法设计与分析教学方式，减少教学过程中的讲授教学比例。以建构主义教学学习理论、人本主义心理学理论以及发现法教学理论为依据，构建以案例为核心的探究式算法设计与分析教学模式。案例教学也有利于学生掌握理论知识，并运用知识解决工程中的实际问题。通过采用现代多媒体技术实现算法的动态演示，提高学生的学习兴趣，将复杂问题简单化。
2.2.2 引入ACM程序设计大赛题目。ACM比赛过程中最强调的：采用最优算法、最短时间、最准确的完成给出的题目答案。将ACM引入教学有两个目的：一是教师通过精心设计的启发式教学，引导学生深入理解图1所示的七种算法设 计技术，从而引导学生在遇到ACM比赛题目时选择何种算法设计方法；二是帮助学生熟悉ACM比赛，激发学生的学习兴趣。
2.2.3 自主学习模式。给学生明确的教学目标、要求，按教学计划自主浏览多媒体课件，理解教学内容，发现问题、分析问题和解决问题。比如，让学生采用“贪心算法”来完成售货员找硬币问题，使得所拿出的硬币个数最少。学生应自己分析算法、编码实现，并分析时间复杂性。
2.2.4 团队合作法教学。每个学期挑选一个较为大型的项目，模拟实际工作中的角色给同学们分工，要求学生按照要求完成指定的项目，每个项目组最后演示他们的成果，其他小组作为裁判给出评价。在实际操作中还可以将教师的科研项目让学生完成，让学生在实际工作中体会团队合作的意义。除参加ACM大赛外，还可以让学生以团队合作的方式积极参加每年一次的学校组织的“大学生挑战杯程序设计大赛”。
3. 教学实践
3.1 教学案例
基于上述原则，结合算法设计与分析课程的特点选取一些实际问题，讲解一个具体的应用实例，从而使学生掌握算法设计的一般过程，如图3所示。
传统的教学方式，本课程期末时，给学生留个大作业完成“某项目的算法设计”；而本门课程在第一次课就让学生先自选题目，然后教给老师，教师要随着课程的进展进行阶段性的检查，期末学生提交本作业。下面采用蛮力法处理组合问题的应用，对“0／1背包问题”进行处理。
3.1.1 理解问题。
3.1.2 分析问题。
3.1.3 具体应用数据。
如图4所示，一个容量为10的背包和4个物品，采用蛮力法求解0／1背包问题。
3.1.4 求解过程演示。
3.1.5 分析算法的效率。
对于一个具有n个元素的集合，其子集数量是2n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个Ω(2n)的算法。
3.1.6 算法实现。
略。
最后，总结蛮力法求解问题的过程，分析该方法的时间复杂性。
3.2 教学考核环节
课程成绩=理论考试(占总分60％)+实训项目(占总分40％)
本课程结束后，学生能独立完成软件项目的算法设计任务，并提交一份规范的算法设计说明书。
4. 结束语
建构主义的教学目的是为了让学生获得完整、深刻、能够灵活运用的知识；同时，在科学探究中也培养了学生的探究能力，包括发现问题的能力，提出假设的能力，设计实验的能力，分析数据的能力和归纳结论的能力。
本文以算法设计与分析课程为例讨论了计算机专业课程开展“知识建构和探究式”的教学方式的尝试，取得了初步的效果，一定程度上促进了学生算法设计方面能力的提高。但是仅仅本课程的改革是远远不够的，这一新的教学方法值得进一步完善和改进以及在其他计算机专业课程中的教学实践中加以推广和应用。
参考文献
1. Drive.R.Easley.puppies and paradingms：A review ofliterature to concept development in adolescent sciencestudents[J].studies in science Education，1978，(5)：61-84.
2. 何克抗，建构主义的教学模式、教学方法与教学设计[J]，北京师范大学学报(社会科学版)，1997，(5)：76.
3. 伍宏珏，由ACM看《算法设计与分析》教学改革[J]，九江学院学报，2009，(6)：120－123.
4. 王红梅，算法设计与分析[M]，北京：清华大学出版社，2006：58-70.
5. 于合龙，辩证法和认识论指导下的C++程序设计教学[J]，计算机教育，2010，(22)：60-66.，