基于拓扑排序和边活动网的网络课程设置方案研究*

原民民，刘春霞

(1.山西水利职业技术学院信息工程系，山西运城 044000;2.太原科技大学电子信息工程学院，山西太原 030024）

基于拓扑排序和边活动网的网络课程设置方案研究*

原民民1，刘春霞2

(1.山西水利职业技术学院信息工程系，山西运城 044000;2.太原科技大学电子信息工程学院，山西太原 030024）

网络教学虽然把学习过程留给学生自主安排，但也要达到让学生系统学习知识的目的.因此，课程设置仍然是网络教育一项重要的任务.传统的课程设置以人工为主，工作效率低.通过对顶点活动网的拓扑排序算法分析，在原有排序结果不稳定的基础上，增加了学时数限制条件，提出了一种适合网络教学的课程设置方案.

网络教育;课程设置;拓扑排序;边活动网

引言

目前，网络教学正在改变传统的教学模式，已成为信息化时代人们在工作之余获得继续教育和提高自身学历的一种快捷途径，各地也建立了培训基地或者学习中心适应其发展，学习者可免受时间地域的限制来安排学习，具有很大的自主性.对于网络教学，虽然将学习过程留给学生，但也同样存在着与传统教育一样对学习者进行课程设置、教学计划安排、阶段性的检查与测试、学期末的考试、毕业论文写作与答辩等服务与管理.所以，网络教学也要求教务部门考虑学生在能力与情感方面的协调发展［1］，从而制定出合理、系统的课程设置和教学计划，甚至制定出整个学习阶段的所有课程设置和教学计划，以便于学习者学习时可直观地了解所学课程，以及课程间的关联性和系统性.

对传统教学，当制定好课程设置和教学计划后，一般可重复使用很多周期，加之教学的循环周期都比较长，因此，对于教学来说，只要专业知识体系相对完善，专业知识更新缓慢，则基本不需要对课程设置做调整，或作较少调整，不会影响整体课程设置和教学计划安排.但对于网络教育，其承载的应该是适应信息化发展并能及时更新和传授学科前沿最新技术和紧跟市场对学科的技术要求，这就要求网络课程的设置调整应相对频繁，周期较短，更新要快，进而又体现在各个教学计划的快速调整和合理安排上.在互联网的快速发展与多资源共享背景下，信息的传播和资源的获取变得快捷，促使一些知识的消化并不需要如传统教学花费很长的时间，这也使得各高等院校以及部分基础教育院校在教学上都进行了改革与实验，如小学期的开设，职业教育与理论教育的结合等.如何将这些因素考虑在课程设置并选择一个适合网络教学的课程设置方案是极其必要的.课程信息是一个巨大而复杂的数据，使用计算机代替人工处理这样的数据，就需要选择合适的数据结构，以便于存储其信息，顶点活动网(AOV网)正是这样一种数据结构［2］.

1 AOV网与拓扑排序

对AOV网，要求其逻辑结构是有向无环图，它通常被用来描述一项工程各个子过程间的制约关系［3］，并可通过一定的输出设定将这些子过程转换成一个线性序列.我们把这个序列称为拓扑序列，相应地，将得到序列的过程称为拓扑排序.

然而，采用AOV网进行拓扑排序会存在以下问题.

1.1 排序不惟一

简单的AOV网的拓扑排序序列是不惟一的，由于输出入度为0的顶点是随机的，因此，在一次输出后并不一定能得到符合问题的惟一或合理序列，这是AOV网自身的特性，是无法解决的.所以，对于教学中的某个课程体系，采用拓扑排序的方式，将各相关课程转换成在学期进行的一个先后顺序，然后根据某一学期开设的课程数在序列中进行分割选择.但是在多个排序的结果中，有一些序列对于课程学习不太合适，而有的序列则恰恰能合理地反映课程的设置.

1.2 不能体现顶点的优先关系

假如某课程AOV网如图1所示:

图1 某课程AOV网

可以看到在初始时有一个或多个入度为0的顶点，但在输出的过程中后面的顶点会逐渐变为入度为0的顶点，并且加入到前面没有输出的顶点集中，这就对某一学期课程设置带来了一个问题，在拓扑排序的过程中有的是初始度为0的顶点，有的是输出其它顶点后出现的度为0的顶点，如果课程在体系中是合理安排的，那么根据先后关系，这些初始度为0的顶点应该比输出过程中出现的度为0的顶点有优先级别，或者说在同一个学期安排课程的时候，可以安排有限制关系的两门课程同时开设，但不应该出现有限制关系的多门课程同时开设的情况［4］.那么合理的情况就应该是在有相互限制关系的两门课程输出后，另外选择一个与前面两门课程没有关系的其它度为0的顶点进行交叉输出.

那么，假定我们根据拓扑排序序列中的顶点连续选择几门课程在一个学期进行，按照上面的交叉输出，就可以保证不会把有相互限制关系的三门甚至四门课程放在一个学期内.要解决这个问题，我们可以给顶点的度为0进行条件设置(如添加编号设置，设置对应边的权值，提前设定课程开设学期等).假设以添加编号为限制条件，规定初始时度为0的顶点编号为0，而将输出过程中出现的度为0的顶点按照出现次序用自然数递增顺序编号，在输出时允许度为0且与它关联的最多一个顶点输出，并且优先输出在同一阶段出现的度为0的这些顶点，这可以认为按照图的广度优先搜索结合一次深度优先搜索顶点.比如有初始度为0的顶点K2与第三次出现的度为0的K9，这时应该优先输出K2，而不应该优先输出K9.这就使得在同一学期最多能开设两门相关联的课程，一般都为一门.此外，也可能存在这样的情况，比如第三次出现的度为0的K9正好安排在了第二学期，而它的前驱K8正好在序列中第一学期的最后一门课，与K9相连了，但实际上，用前面的交叉输出方式正好解决了这种随机出现的学期上的分割.

2 基于拓扑排序和边活动网的网络课程设置方案

边活动网(AOE网)是一种在AOV网的基础上增加一种限制关系的网.

限制课程设置和教学计划安排的约束条件很多，在制定好教学课程体系后，一般主要考虑课程间的限制关系，也就是确定先修课程是哪些，以及教学中学时数等的限制［5］，因此在课程设置的时候，在课程体系已经确定了先后关系外，我们将学时数加入课程设置方案中，把学时数作为一个权值，利用AOE网建立课程间的关系，同时为减少程序中的参数量建议将课程开设学期提前设定，然后再对其进行拓扑排序，以便于排除部分无效课程序列，最后可以得到科学合理的教学计划［5］.

2.1 基于拓扑排序和AOE网的网络课程设置思想

设有向带权图:G= ＜ V，E，W ＞ ，V={v1，v2，v3…vn}，E={e1，e2，e3…en}，W={w1，w2，w3…wn}，有向边ek= ＜vi，vj＞ 指活动 vi先于 vj完成，ek上的权值wi指完成vi活动所需时间.相应的，可以将vi，vj以及wi分别对应课程设置中的关联课程和课程所需的学时数［5］，并设定某课程建议开设的学期.

2.1.1 课程逻辑形态描述

下面以某网络教育计算机应用专业所开设的课程为例，描述课程设置的排序过程.课程关系如表1所示.表1中给出了各门课程之间的先修关系和本门课程的学时数.

表1 某计算机应用专业必修课

2.1.2 构造课程关系的AOE网

根据表1的课程关系构造其AOE网，如图2所示.

图2 课程关系AOE网

2.1.3 课程设置输出分析

在图2中，各个学期所安排的课程体现在纵列，通过这样的处理，将课程设置转成对AOE网进行拓扑排序的处理.那么对一门课程，首先要求该课的先修课程都完成，然后才能安排本课程的学习.对于AOE网的顶点，就是输出该课程所对应的图中顶点的前驱顶点.但是在AOE网中，输出一些度为0的顶点，并删除所有以它为弧尾的弧后，将会出现两种情况，一种是在同一学期的课程正好全部输出，出现度为0的顶点全部在下一学期;第二种是在同一学期的课程没有全部输出，剩余个别课程，其入度仍然为0，但同时也出现了下一学期中度为0的顶点(主要在中间学期);为了保证有先修关系的课程尽量不要出现在同一学期(也就是下一学期的课排在了上一学期)，在拓扑排序的时候通过在程序中设定一个对应学期的自增变量，判断其值是否与当前学期开设课程数相等来检测本该在这一学期开设的课程是否全部输出，如果出现前面所说的第二种情况，那么在输出顶点的时候优先设定输出前一学期还没有输出的顶点，然后才能输出下一学期的顶点，这样就能保证所开设课程同步进行.

在实际输出的时候，可用学时数和提前设定的学期作为判断条件，根据教学特点与课程难易程度，控制一个学期应该开设的课程数，同时结合这一学期开设课程的总学时数，在不同学期输出对应的开设课程，也就是将原来应该为一个完整的拓扑排序序列分拆在不同的学期，这样更能体现课程设置，同时可依据不同学期开设的课程更好的编制教学计划.

2.2 基于拓扑排序和AOE网的网络课程设置方案分析

采用学时数限制的AOE网进行的课程排序能使课程设置更加合理和高效，课程在各个学期的分布也较均匀，课程的增加与调整也变得很灵活，该方案在相邻课程关系的基础上，增加了学时数限制，将这个权值贯穿在课程排序输出中，使得在合理安排每学期课程量的同时，保证学生在工作之余的空闲时间，有类似于传统教育每周开设课程的均匀课时量，使得每门课程的教学效果都达到或者接近理想状态.

3 总结

开设课程变化大、更新较快的课程设置方案，特别适于网络教育学院，在新的教育方式和网络快速应用的辅助下，网络教学也迅猛发展起来，各地已建立了培训基地或者学习中心，已成为未来教学的一种新形式和发展趋势，网络教学在给学生提供自由学习环境的基础上，更应该从课程上为学生提供合理的设置以区别传统教学，从而给学生带来最大的价值［5］，此外，网络教学应充分发挥其快速调整课程和及时更新最新知识内容的便利性，让网络教学成为现代学生接受传统教学之外快速提升自身知识的最佳途径.

［1］陈雪芳.教学管理系统中排课算法约束条件及其实现［J］.东莞理工学院学报，2009，16(1):51 －54.

［2］严蔚敏，吴伟明.数据结构［M］.北京:清华大学出版社，1992:46－49.

［3］徐翠霞.数据结构案例教程C语言版［M］.北京:北京大学出版社，2009:178－179.

［4］魏丽丽.几种自动排课算法的比较［J］.大众科技，2009，(9):170－171.

［5］张南豫.基于加权拓扑排序的教学计划新模式研究［D］.开封:河南大学，2011:36 －37.

Research on Network Course Setting Based on the Topological Sort and Activity on Edge Network

YUAN Min－min1，LIU Chun－xia2
(1.Information Engineering Department，Shanxi Conservancy Technical College，Yuncheng Shanxi 044000，China;
2.Electronics and Information Engineering Academy，Taiyuan University of Science and Technology，Taiyuan Shanxi 030024，China)

In spite of making students themselves arrange learning process during online education，it＇s also enable students to acquire knowledge systemly.So an important task for online education is to set the course.The traditional course was setted by manual－ acting in the past，so it＇s very inefficiency.Through the analysis of topological sort algorithm based on activity on vertex network，we put forward a kind of new method to update the old’s by using a constraint condition.This method can effectively improve the work for educational department.

online education;course setting;topological sort;activity on edge network

TP 312

A

1673－2103(2012)02－0123－04

2012－03－19

山西省青年科技研究基金资助项目(2011021014－3)

原民民(1977－)，男，山西运城人，讲师，硕士，研究方向:算法分析与计算机程序设计.