原民民，劉春霞

(1.山西水利職業(yè)技術學院信息工程系，山西運城 044000;2.太原科技大學電子信息工程學院，山西太原 030024）

基于拓撲排序和邊活動網的網絡課程設置方案研究*

原民民1，劉春霞2

(1.山西水利職業(yè)技術學院信息工程系，山西運城 044000;2.太原科技大學電子信息工程學院，山西太原 030024）

網絡教學雖然把學習過程留給學生自主安排，但也要達到讓學生系統(tǒng)學習知識的目的.因此，課程設置仍然是網絡教育一項重要的任務.傳統(tǒng)的課程設置以人工為主，工作效率低.通過對頂點活動網的拓撲排序算法分析，在原有排序結果不穩(wěn)定的基礎上，增加了學時數(shù)限制條件，提出了一種適合網絡教學的課程設置方案.

網絡教育;課程設置;拓撲排序;邊活動網

引言

目前，網絡教學正在改變傳統(tǒng)的教學模式，已成為信息化時代人們在工作之余獲得繼續(xù)教育和提高自身學歷的一種快捷途徑，各地也建立了培訓基地或者學習中心適應其發(fā)展，學習者可免受時間地域的限制來安排學習，具有很大的自主性.對于網絡教學，雖然將學習過程留給學生，但也同樣存在著與傳統(tǒng)教育一樣對學習者進行課程設置、教學計劃安排、階段性的檢查與測試、學期末的考試、畢業(yè)論文寫作與答辯等服務與管理.所以，網絡教學也要求教務部門考慮學生在能力與情感方面的協(xié)調發(fā)展［1］，從而制定出合理、系統(tǒng)的課程設置和教學計劃，甚至制定出整個學習階段的所有課程設置和教學計劃，以便于學習者學習時可直觀地了解所學課程，以及課程間的關聯(lián)性和系統(tǒng)性.

對傳統(tǒng)教學，當制定好課程設置和教學計劃后，一般可重復使用很多周期，加之教學的循環(huán)周期都比較長，因此，對于教學來說，只要專業(yè)知識體系相對完善，專業(yè)知識更新緩慢，則基本不需要對課程設置做調整，或作較少調整，不會影響整體課程設置和教學計劃安排.但對于網絡教育，其承載的應該是適應信息化發(fā)展并能及時更新和傳授學科前沿最新技術和緊跟市場對學科的技術要求，這就要求網絡課程的設置調整應相對頻繁，周期較短，更新要快，進而又體現(xiàn)在各個教學計劃的快速調整和合理安排上.在互聯(lián)網的快速發(fā)展與多資源共享背景下，信息的傳播和資源的獲取變得快捷，促使一些知識的消化并不需要如傳統(tǒng)教學花費很長的時間，這也使得各高等院校以及部分基礎教育院校在教學上都進行了改革與實驗，如小學期的開設，職業(yè)教育與理論教育的結合等.如何將這些因素考慮在課程設置并選擇一個適合網絡教學的課程設置方案是極其必要的.課程信息是一個巨大而復雜的數(shù)據，使用計算機代替人工處理這樣的數(shù)據，就需要選擇合適的數(shù)據結構，以便于存儲其信息，頂點活動網(AOV網)正是這樣一種數(shù)據結構［2］.

1 AOV網與拓撲排序

對AOV網，要求其邏輯結構是有向無環(huán)圖，它通常被用來描述一項工程各個子過程間的制約關系［3］，并可通過一定的輸出設定將這些子過程轉換成一個線性序列.我們把這個序列稱為拓撲序列，相應地，將得到序列的過程稱為拓撲排序.

然而，采用AOV網進行拓撲排序會存在以下問題.

1.1 排序不惟一

簡單的AOV網的拓撲排序序列是不惟一的，由于輸出入度為0的頂點是隨機的，因此，在一次輸出后并不一定能得到符合問題的惟一或合理序列，這是AOV網自身的特性，是無法解決的.所以，對于教學中的某個課程體系，采用拓撲排序的方式，將各相關課程轉換成在學期進行的一個先后順序，然后根據某一學期開設的課程數(shù)在序列中進行分割選擇.但是在多個排序的結果中，有一些序列對于課程學習不太合適，而有的序列則恰恰能合理地反映課程的設置.

1.2 不能體現(xiàn)頂點的優(yōu)先關系

假如某課程AOV網如圖1所示:

圖1 某課程AOV網

可以看到在初始時有一個或多個入度為0的頂點，但在輸出的過程中后面的頂點會逐漸變?yōu)槿攵葹?的頂點，并且加入到前面沒有輸出的頂點集中，這就對某一學期課程設置帶來了一個問題，在拓撲排序的過程中有的是初始度為0的頂點，有的是輸出其它頂點后出現(xiàn)的度為0的頂點，如果課程在體系中是合理安排的，那么根據先后關系，這些初始度為0的頂點應該比輸出過程中出現(xiàn)的度為0的頂點有優(yōu)先級別，或者說在同一個學期安排課程的時候，可以安排有限制關系的兩門課程同時開設，但不應該出現(xiàn)有限制關系的多門課程同時開設的情況［4］.那么合理的情況就應該是在有相互限制關系的兩門課程輸出后，另外選擇一個與前面兩門課程沒有關系的其它度為0的頂點進行交叉輸出.

那么，假定我們根據拓撲排序序列中的頂點連續(xù)選擇幾門課程在一個學期進行，按照上面的交叉輸出，就可以保證不會把有相互限制關系的三門甚至四門課程放在一個學期內.要解決這個問題，我們可以給頂點的度為0進行條件設置(如添加編號設置，設置對應邊的權值，提前設定課程開設學期等).假設以添加編號為限制條件，規(guī)定初始時度為0的頂點編號為0，而將輸出過程中出現(xiàn)的度為0的頂點按照出現(xiàn)次序用自然數(shù)遞增順序編號，在輸出時允許度為0且與它關聯(lián)的最多一個頂點輸出，并且優(yōu)先輸出在同一階段出現(xiàn)的度為0的這些頂點，這可以認為按照圖的廣度優(yōu)先搜索結合一次深度優(yōu)先搜索頂點.比如有初始度為0的頂點K2與第三次出現(xiàn)的度為0的K9，這時應該優(yōu)先輸出K2，而不應該優(yōu)先輸出K9.這就使得在同一學期最多能開設兩門相關聯(lián)的課程，一般都為一門.此外，也可能存在這樣的情況，比如第三次出現(xiàn)的度為0的K9正好安排在了第二學期，而它的前驅K8正好在序列中第一學期的最后一門課，與K9相連了，但實際上，用前面的交叉輸出方式正好解決了這種隨機出現(xiàn)的學期上的分割.

2 基于拓撲排序和邊活動網的網絡課程設置方案

邊活動網(AOE網)是一種在AOV網的基礎上增加一種限制關系的網.

限制課程設置和教學計劃安排的約束條件很多，在制定好教學課程體系后，一般主要考慮課程間的限制關系，也就是確定先修課程是哪些，以及教學中學時數(shù)等的限制［5］，因此在課程設置的時候，在課程體系已經確定了先后關系外，我們將學時數(shù)加入課程設置方案中，把學時數(shù)作為一個權值，利用AOE網建立課程間的關系，同時為減少程序中的參數(shù)量建議將課程開設學期提前設定，然后再對其進行拓撲排序，以便于排除部分無效課程序列，最后可以得到科學合理的教學計劃［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分別對應課程設置中的關聯(lián)課程和課程所需的學時數(shù)［5］，并設定某課程建議開設的學期.

2.1.1 課程邏輯形態(tài)描述

下面以某網絡教育計算機應用專業(yè)所開設的課程為例，描述課程設置的排序過程.課程關系如表1所示.表1中給出了各門課程之間的先修關系和本門課程的學時數(shù).

表1 某計算機應用專業(yè)必修課

2.1.2 構造課程關系的AOE網

根據表1的課程關系構造其AOE網，如圖2所示.

圖2 課程關系AOE網

2.1.3 課程設置輸出分析

在圖2中，各個學期所安排的課程體現(xiàn)在縱列，通過這樣的處理，將課程設置轉成對AOE網進行拓撲排序的處理.那么對一門課程，首先要求該課的先修課程都完成，然后才能安排本課程的學習.對于AOE網的頂點，就是輸出該課程所對應的圖中頂點的前驅頂點.但是在AOE網中，輸出一些度為0的頂點，并刪除所有以它為弧尾的弧后，將會出現(xiàn)兩種情況，一種是在同一學期的課程正好全部輸出，出現(xiàn)度為0的頂點全部在下一學期;第二種是在同一學期的課程沒有全部輸出，剩余個別課程，其入度仍然為0，但同時也出現(xiàn)了下一學期中度為0的頂點(主要在中間學期);為了保證有先修關系的課程盡量不要出現(xiàn)在同一學期(也就是下一學期的課排在了上一學期)，在拓撲排序的時候通過在程序中設定一個對應學期的自增變量，判斷其值是否與當前學期開設課程數(shù)相等來檢測本該在這一學期開設的課程是否全部輸出，如果出現(xiàn)前面所說的第二種情況，那么在輸出頂點的時候優(yōu)先設定輸出前一學期還沒有輸出的頂點，然后才能輸出下一學期的頂點，這樣就能保證所開設課程同步進行.

在實際輸出的時候，可用學時數(shù)和提前設定的學期作為判斷條件，根據教學特點與課程難易程度，控制一個學期應該開設的課程數(shù)，同時結合這一學期開設課程的總學時數(shù)，在不同學期輸出對應的開設課程，也就是將原來應該為一個完整的拓撲排序序列分拆在不同的學期，這樣更能體現(xiàn)課程設置，同時可依據不同學期開設的課程更好的編制教學計劃.

2.2 基于拓撲排序和AOE網的網絡課程設置方案分析

采用學時數(shù)限制的AOE網進行的課程排序能使課程設置更加合理和高效，課程在各個學期的分布也較均勻，課程的增加與調整也變得很靈活，該方案在相鄰課程關系的基礎上，增加了學時數(shù)限制，將這個權值貫穿在課程排序輸出中，使得在合理安排每學期課程量的同時，保證學生在工作之余的空閑時間，有類似于傳統(tǒng)教育每周開設課程的均勻課時量，使得每門課程的教學效果都達到或者接近理想狀態(tài).

3 總結

開設課程變化大、更新較快的課程設置方案，特別適于網絡教育學院，在新的教育方式和網絡快速應用的輔助下，網絡教學也迅猛發(fā)展起來，各地已建立了培訓基地或者學習中心，已成為未來教學的一種新形式和發(fā)展趨勢，網絡教學在給學生提供自由學習環(huán)境的基礎上，更應該從課程上為學生提供合理的設置以區(qū)別傳統(tǒng)教學，從而給學生帶來最大的價值［5］，此外，網絡教學應充分發(fā)揮其快速調整課程和及時更新最新知識內容的便利性，讓網絡教學成為現(xiàn)代學生接受傳統(tǒng)教學之外快速提升自身知識的最佳途徑.

［1］陳雪芳.教學管理系統(tǒng)中排課算法約束條件及其實現(xiàn)［J］.東莞理工學院學報，2009，16(1):51 －54.

［2］嚴蔚敏，吳偉明.數(shù)據結構［M］.北京:清華大學出版社，1992:46－49.

［3］徐翠霞.數(shù)據結構案例教程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－)，男，山西運城人，講師，碩士，研究方向:算法分析與計算機程序設計.