基于智猪博弈的数据结构课程理论与实践教学研究|数据结构与算法 c语言

　　摘要：“数据结构”作为计算机专业的一门核心基础课程，理论教学和实践教学都非常重要，但实际教学过程中两者之间存在投入和重视度不均衡的现实。通过引入智猪博弈理论分析二者相互关系，采用收益矩阵可以清楚地解释两种教学活动的失衡原因。根据博弈均衡结论有针对性地提出相应对策，可以有效促进理论教学和实践教学和谐发展，从而为推动数据结构课程的建设提供新的思路。
　　关键词：智猪博弈；数据结构；理论教学；实践教学
　　中图分类号：G642.0
　　文献标识码：A
　　文章编号：1671-6124(2012)04-0096-03
　　《数据结构》是一门具有很强的综合性和技术性的专业基础课程[1]，涉及计算机科学各领域及相关应用软件的各类数据结构，是计算机科学领域中软件基础的重要组成部份，是软件工程和计算机应用的重要基础。
　　一、数据结构理论与实践教学现状分析
　　数据结构课程的目的是让学生掌握使用计算机处理非数值运算问题的原理和方法，熟悉解决各种问题的基本思想和模型，培养运用已有的算法编写准确、清晰的程序的能力[2]。此外，通过数据结构课程理论体系的学习，学生在设计软件系统时能够合理选择数据结构，对所选算法进行初步评价，能够在实践中设计一个“好”的程序。
　　1　从理论教学的角度
　　数据结构课程的内容与计算机科学领域的其他必修课程有密切的关系，无论是编译原理还是操作系统，都必须涉及存储器中数据元素的分配问题，因此数据结构是计算机科学领域的核心课程之一。由于该课程知识点多，概念之间联系紧密，算法抽象难懂，要求学生具备较强逻辑思维能力，因此学生普遍感觉学习具有一定困难。
　　2　从实践教学的角度
　　通过上机编程练习，可以让学生进一步理解数据结构的基本理论，提高根据具体需求选择合理数据结构，控制求解算法时间和空间复杂度的能力。上机实践能进一步提高学生的软件设计和编程水平，有助于形成科学的思维方法和严谨的科学态度。虽然数据结构实践教学从某种程度上说是程序设计课程的延续，但与程序设计课程有很大不同。程序设计课程侧重于程序设计基础的理念，而数据结构课程侧重于数据的表示和存储，主要是软件设计的理念。因此，程序设计课程的上机实践主要要求学生按照程序设计规范设计一些较简单的程序，而数据结构上机实践，要求学生首先通过分析问题得到具体需求，然后在逻辑上找到问题的表示和解决方法，最后选择合适的存储结构，将数据存储在计算机中，按照逻辑上的解决思路写出算法伪代码，然后将伪代码转换成相应的程序，交由计算机编译运行。虽然看上去数据结构的实验问题是程序设计，但具体的要求和程度是不一样的，数据结构的实践较之程序设计上了一个层次。
　　一般来说，按照计算机专业对数据结构课程的重视程度，不论是理论教学还是实践教学，教与学的效果应该不错，但是，在实际教学过程中事实并非如此。究其原因，虽然理论与实践并重的客观性决定了对数据结构课程应该投入的程度，但实际上各高校的考核重心主要偏向理论教学，对实践教学没有有效的监管和考核措施，使学生并未从思想上引起对实践的重视，从而无法有效锻炼和提高动手能力。而正是由于学生动手能力的不足，又反过来制约了对数据结构理论课程的学习。
　　二、基于智猪博弈视角的理论与实践教学分析
　　是否只需要加大实践教学所占的时间比例或者只需要加重课程设计所占的学分，就可以提高学生的动手水平、增强数据结构课程的学习效果?我们试图从一个全新的角度，从智猪博弈的视角来对数据结构理论教学和实践教学的相互关系进行深入分析。
　　博弈的一个基本假设是理性的参与者选择策略时以利益最大化为目的。数据结构课程中理论教学与实践教学之间的博弈，其目的是为了使得各自利益最大化，最终使整个数据结构课程学习效果的最大化。博弈论[3]是研究参与者在给定信息结构下如何决策以最大化各自的效用，以及实现不同参与者之间决策的均衡。目前未发现采用博弈思想研究数据结构中这两种教学相互关系的成果，本文首次采用智猪博弈来分析二者关系并提出相应对策。
　　智猪博弈的主要内容是猪圈里有两头猪，一头大猪，一头小猪。一个食槽位于猪圈的一头，在另一头安装着一个按钮，控制猪食的供应，按按钮的猪必须在猪圈一头按下按钮，然后跑到另一头吃猪食，不按按钮的猪则可以一直在食槽处等待。按钮被按动一次将有10个单位的猪食进槽，但按动按钮的过程将消耗相当于2个单位猪食的能量。如果小猪按动按钮，则大猪吃到9个单位的猪食，小猪只能吃到1个单位，但由于按按钮并跑动的过程需要消耗2个单位，因此小猪的实际收益是，1单位；如果同时按按钮，大猪吃7个单位，小猪吃3个单位；如果大猪按动按钮，大猪吃6个单位，小猪吃4个单位，同样由于按按钮且跑动的过程需要消耗2个单位，大猪在此策略的实际收益是4个单位。大猪、小猪各自选择按或不按的策略组合，对应的各自的收益矩阵如表1所示。
　　每只猪都必须作出决策，是在食槽边等待吃猪食，还是跑到猪圈另一头按按钮。如表1所示，对于小猪来说，如果它等待，要么吃4个单位，要么不吃(取决于大猪的决策)；如果它按按钮，要么吃1个单位，要么吃，1个单位(也取决于大猪的决策)。根据收益矩阵，小猪的选择一定是等待。反观大猪，通过收益矩阵分析小猪不会主动按按钮，则自己亲自按按钮的收益总比大家都不按强。因此该博弈的均衡策略是大猪按、小猪等待。如果将大猪看作理论教学，小猪看作实践教学，按按钮的动作视为增大对某种教学的投入，这种投入可以是时间、精力，也可以是对某种教学的评分占总课程的比重，而等待表示维持现状。可以发现当前两种教学目前各自对应的收益趋势，符合博弈设定的收益矩阵所给出的彼此收益值的相对趋势。例如，加大对任何一方的投入(对应按按钮行为)，任何一方都必须付出相应的劳动来使用该投入，这可以类比于按按钮消耗猪食的情况，而不管是理论教学还是实践教学，在施行中都能使学生有所收获。通过上一节的分析可知，两者之间的博弈亦如现实情况所显示，已经达到了一种均衡状态，即重理论教学而轻实践教学，理论分析与现实吻合，采用智猪博弈理论分析当前两种教学工作的博弈情况是合理的。