基于選課案例學(xué)習(xí)偏序集中的極小元

摘要：文章針對離散數(shù)學(xué)中偏序集極小元概念的抽象性，提出了一種基于選課案例和C++編程相結(jié)合的教學(xué)方法。該方法探討如何將數(shù)學(xué)定義轉(zhuǎn)化為程序代碼，實現(xiàn)了極小元的計算和選課方案的生成，有效地提升了學(xué)生的理解和應(yīng)用能力，為類似數(shù)學(xué)課程的教學(xué)提供借鑒。

關(guān)鍵詞：離散數(shù)學(xué)；偏序關(guān)系；極小元；拓?fù)渑判?；選課

中圖分類號：G642

文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2025）13-0171-04

0引言

離散數(shù)學(xué)是計算機(jī)及其相關(guān)專業(yè)的一門必修課，涵蓋數(shù)理邏輯、集合論、圖論等多個分支，廣泛應(yīng)用于計算機(jī)相關(guān)領(lǐng)域工程問題的建模與分析。但該課程概念抽象，理論性強(qiáng)，導(dǎo)致學(xué)生學(xué)習(xí)困難，偏序集中的極小元便是其中一個具有代表性的例子。本文借助選課案例，結(jié)合C++程序代碼來學(xué)習(xí)極小元的概念及應(yīng)用。

1偏序集與極小元

定義1設(shè)A是一個集合，如果A上的一個關(guān)系R，滿足自反性，反對稱性和傳遞性，則稱R是A上的一個偏序關(guān)系，并把它記為“≤”。序偶lt;A，≤gt;稱作偏序集[1]。

定義2如果A上的關(guān)系R是偏序關(guān)系，那么可以按照下面的方式簡化它的關(guān)系圖。

（1）用小圓圈或點表示A中的元素，省掉關(guān)系圖中所有的環(huán)。（因自反性）

（2）對任意x，y∈A（x≠y），若x≤y，則將x畫在y的下方，可省掉關(guān)系圖中所有邊的箭頭。（因反對稱性）

（3）對任意x，y∈A（x≠y），若x≤y，且不存在z∈A，使得x≤z，z≤y，則x與y之間用一條線相連，否則無線相連。（因傳遞性）按照（1）（2）和（2）作成的圖被稱為R的哈斯圖[2]。

定義3設(shè)lt;A，≤gt;是一個偏序集合，且B是A的子集，對于B中的一個元素b，如果B中沒有任何元素x，滿足b≠x且x≤b，則稱b為B的極小元[1]。b是B的極小元?在B的哈斯圖中，b的下方?jīng)]有其他元素[2]。

2基于選課案例學(xué)習(xí)偏序集中的極小元

2.1案例描述

在大學(xué)各專業(yè)開設(shè)的課程中，有些課是基礎(chǔ)課，可獨(dú)立開設(shè)。有些課必須先學(xué)完一些基礎(chǔ)課后才能開設(shè)。表1描述了某計算機(jī)專業(yè)部分課程之間的先修關(guān)系。如何找到一個課程學(xué)習(xí)的先后序列？

在課程的集合A上定義關(guān)系R={lt;a，bgt;|a，b∈A，a是b的先修課}。如果規(guī)定課程a是自身的先修課，則R具有自反性。若a是b的先修課，且a≠b，則b不可能是a的先修課，故R具有反對稱性。如果a是b的先修課，并且b是c的先修課，則a一定是c的先修課，因此，R具有傳遞性。根據(jù)定義1，課程之間的先修關(guān)系R是一個偏序關(guān)系。

2.2案例分析

表1所示的課程之間的先修關(guān)系如圖1所示。對給定的課程及其先導(dǎo)、后繼關(guān)系，學(xué)生據(jù)此制定選課計劃及學(xué)習(xí)順序，是拓?fù)渑判虻囊粋€典型應(yīng)用。大多文獻(xiàn)[3-5]將圖1所示的有向圖視為AOV網(wǎng)，用鄰接表或鄰接矩陣存儲課程之間的先修關(guān)系，用隊列或棧存儲入度為0的結(jié)點，從而得到一個合理的學(xué)習(xí)序列。該方法要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)課程中圖、隊列及棧等相關(guān)概念，不適合大一學(xué)生。另外，該方法需保存所有的先修關(guān)系，如果問題規(guī)模較大，會占用大量的存儲空間。

本文采用求偏序集極小元的方法進(jìn)行問題求解。一則不需要學(xué)生有數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，滿足學(xué)情要求；二則，該方法會對關(guān)系圖進(jìn)行預(yù)處理，去掉明顯的先修關(guān)系，從而節(jié)省存儲空間。

根據(jù)定義2，去掉圖1中滿足傳遞性的邊lt;2，5gt;和lt;2，4gt;并忽略箭頭的方向，得到圖2所示的哈斯圖。

根據(jù)定義3，用求極小元法得到拓?fù)湫蛄锌砂慈缦虏襟E進(jìn)行。假設(shè)集合A={1，2，3...8}。

（1）k=1。

（2）若A≠?，求出集合A中的極小元ak，輸出ak，A＝A-{ak}，k=k+1，循環(huán)執(zhí)行第（2）步。

a1，a2，...an就是所求的學(xué)習(xí)課程的合理次序。

具體操作：先求出初始集合A對應(yīng)的極小元1和2元為第一元素的序偶。之后，將其從A中刪除。對更新后的集合，并在關(guān)系R中刪除以極小A和關(guān)系R重復(fù)相同的操作，直到集合A為空集。

按照上述步驟，從圖2的哈斯圖得到拓?fù)湫蛄械倪^程如表2所示。初始情況：A={1，2，3...8}，R={lt;1，3gt;，lt;1，6gt;，lt;2，3gt;，lt;3，4gt;，lt;4，5gt;，lt;4，8gt;，lt;6，7gt;，lt;7，8gt;}。

由表2知，最終的一個學(xué)習(xí)序列為：12364758。

2.3案例實現(xiàn)

1）所需數(shù)據(jù)結(jié)構(gòu)及主要變量

通過上述分析可知，主要數(shù)據(jù)結(jié)構(gòu)有關(guān)系R、集合A及極小元。根據(jù)各自的定義，可以用C++中的集合等容器來實現(xiàn)。具體為：

的集合setlt;pairlt;int，intgt;gt;R;//定義關(guān)系R，即序偶setlt;intgt;subset;

vectorlt;intgt;minimalElement//定義集合;//存儲極小元A，整數(shù)的集合上述算法中，構(gòu)建初始關(guān)系R及集合A可以調(diào)用set的insert方法，集合的差運(yùn)算，可以采用set的erase方法來實現(xiàn)。

2）核心代碼

實現(xiàn)算法的關(guān)鍵代碼是求極小元。根據(jù)定義3，可以將其設(shè)計為一個函數(shù)，形參包括偏序關(guān)系R、子集B及B中一個元素b。如何將定義3轉(zhuǎn)化為編程語言的描述方式又是重中之重。定義中“對于B中的一個元素b，如果B中沒有任何元素x，滿足b≠x且x≤b”可以寫成謂詞公式：

如果公式（2）為真，則b為B的極小元。根據(jù)全稱量詞與程序的轉(zhuǎn)化關(guān)系，可以理解為遍歷子集B中的每個元素x，如果某個x使?（b≠x∧xRb）為假，即b≠x∧xRb為真，則返回1。如果遍歷結(jié)束仍未找到使?（b≠x∧xRb）為假的x，則返回true。

據(jù)以上分析，可寫出下面的代碼來判斷b是否為極小元。

boolisMinimalElement（setlt;intgt;amp;subset，intb，setlt;

pairlt;int，intgt;gt;amp;R）{

for（intx：subset）{

if（（x！=b）amp;amp;

（find（R.begin（），R.end（），make_pair（x，b））！=R.end

（）））{//在關(guān)系R中找到了序偶lt;x，bgt;

return1;

}

}

returntrue;

}

2.4案例測試

1）編程作業(yè)題目描述

本學(xué)期的離散數(shù)學(xué)編程作業(yè)部署在HUSTOJ系統(tǒng)上。案例的題目描述如表3所示。

2）完整程序

程序首先讀入課程數(shù)n和關(guān)系中的序偶數(shù)m并判斷二者的輸入是否合理，如果不合理，輸出error，程序結(jié)束。否則，讀入m個表示課程之間先修關(guān)系的整數(shù)對，同樣進(jìn)行有效性驗證，合理的數(shù)據(jù)以序偶的形式插入關(guān)系R中，完成R的初始化。將集合A初始化為1...n的整數(shù)。

當(dāng)集合A不為空集時，反復(fù)執(zhí)行下列操作：遍歷A中的元素，判斷其是否為偏序關(guān)系R的極小元，如果是極小元，則加入到存儲極小元的向量minimalEle?ment中，同時也存入最終拓?fù)湫蛄衦esult。遍歷A中的元素一輪結(jié)束后，如果minimalElement向量為空，說明此時的偏序集不存在極小元，即關(guān)系圖中存在環(huán)，退出最外層循環(huán)，程序輸出“不存在合理的學(xué)習(xí)順序”。如果minimalElement向量不為空，則分別從集合A中刪除已經(jīng)找到的極小元、從關(guān)系R中刪除與極小元相關(guān)聯(lián)的序偶，清空minimalElement之后，繼續(xù)基于新的集合A及新的關(guān)系R求極小元。

當(dāng)result的長度等于課程數(shù)n時，輸出result中的元素即為最終的學(xué)習(xí)順序序列。

#includelt;iostreamgt;

#includelt;setgt;

#includelt;vectorgt;

#includelt;algorithmgt;

usingnamespacestd;

intmain（）{

intn，m;

cingt;gt;ngt;gt;m;

if（nlt;=0||mlt;=0）{

coutlt;lt;\"error\";

return0;

}

setlt;pairlt;int，intgt;gt;R;

for（inti=0;ilt;m;i++）{

intu，v;

cingt;gt;ugt;gt;v;

if（ult;1||ugt;n||vlt;1||vgt;n）{

coutlt;lt;\"error\";

return0;

}

R.insert（{u，v}）;//初始化關(guān)系R

}

setlt;intgt;subset;

for（inti=1;ilt;=n;i++）{

subset.insert（i）;

//初始化子集為集合A

}

vectorlt;intgt;result;

//存儲最終的學(xué)習(xí)序列

vectorlt;intgt;minimalElement;

while（！subset.empty（））{//集合A不空

forif（isMinimalElement（intb：subset）{（subset，b，R））{

//如果b是子

集subset中的極小元

minimalElement.push_back（b）;

result.push_back（b）;

}

}

if（minimalElement.empty（））{//如果子集沒有極小元

break;

}

for（intnum：minimalElement）{

//從子集中刪除極小元

subset.erase（num）;

setlt;pairlt;int，intgt;gt;：：iteratorit=R.begin（）;

while（it！=R.end（））{

//找到關(guān)系中以極小元為第一元素的序偶，將其

從關(guān)系中刪除

if（（*it）.first==num）

it=R.erase（it）;

else

it++;

}

}

minimalElement.clear（）;

}

ifcoutlt;lt;\"（result.size不存在合理的學(xué)習(xí)順序（）！=n）{\";

}

else{

for（intnum：result）{

coutlt;lt;numlt;lt;\"\";

}

}

return0;

}

3）OJ系統(tǒng)提交

在OJ系統(tǒng)中提交上述代碼，運(yùn)行結(jié)果如圖3，所有測試用例全部通過，表明程序正確。具體測試情況如下。

表3中給出的樣例輸入881316233445486778，其中第一個“8”表示課程數(shù)，第二個“8”表示圖2所示哈斯圖的邊數(shù)。后面數(shù)字序列兩兩一組，代表具體的結(jié)點對。將其輸入程序，運(yùn)行結(jié)果如圖4，第二行即為一個合理的學(xué)習(xí)順序，與表3中的樣例輸出一致。

此外，題目還設(shè)計了3組處理異常的測試用例，其一為測試存在環(huán)的情況。輸入8111316232425344548677843。前兩個數(shù)分別表示課程數(shù)及邊數(shù)。后面數(shù)字序列中存在34及43構(gòu)成了回路（環(huán)），課程3與課程4互為先修課程，顯然是不合理的。此數(shù)據(jù)的測試結(jié)果如圖5。

另外兩組分別測試輸入的結(jié)點數(shù)和邊數(shù)是否合理以及對課程序號整數(shù)對進(jìn)行有效性驗證。測試結(jié)果如圖6所示。

3結(jié)束語

研究結(jié)合實際選課案例，將離散數(shù)學(xué)中諸如極小元等較為抽象的概念用C++中的程序代碼來實現(xiàn)，有助于學(xué)生理清數(shù)學(xué)中的定義、定理等數(shù)學(xué)語言描述與計算機(jī)編程語言描述之間的對應(yīng)關(guān)系，而且還可培養(yǎng)學(xué)生的建模及應(yīng)用能力。但是，目前的選課程序還有局限性，未來研究將考慮課程學(xué)分、學(xué)期限制等因素，進(jìn)一步完善選課方案生成算法。

參考文獻(xiàn)：

[1]左孝凌，李為鑑，李永才.離散數(shù)學(xué)：理論·分析·題解[M].上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社，1988.

[2]王慶先，顧小豐，王麗杰.離散數(shù)學(xué)：微課版[M].北京：人民郵電出版社，2021.

[3]馬娟.利用拓?fù)渑判蜻M(jìn)行專業(yè)主干課程序列優(yōu)化研究：以高職高專測繪地理信息技術(shù)專業(yè)為例[J].測繪與空間地理信息，2018，41（10）：46-47，52.

[4]王淑芬.基于拓?fù)渑判虻慕虒W(xué)計劃編制系統(tǒng)的研究與實現(xiàn)[D].長春：吉林大學(xué)，2015.

[5]袁和金“.數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中的案例設(shè)計及應(yīng)用[J].計算機(jī)教育，2013（16）：90-94.

【通聯(lián)編輯：王力】