組合數學中鏈與反鏈的教學探索及實踐

李 丹

（南京航空航天大學計算機科學與技術學院，江蘇南京 211106）

0 引言

計算機科學的核心內容是使用算法處理離散數據，而組合數學主要研究離散對象的存在、計數以及構造等方面問題。計算機科學與技術的興起帶動了組合數學的發展。因此，組合數學［1-3］不僅在基礎數學研究中具有極其重要的地位，而且在計算機科學、編碼和密碼學等學科中也得到了廣泛應用［4-5］。

雖然有很多同行認識到了這個問題，并進行了數學類課程教學相關研究工作［6-21］，提出了不同學科滲透、引入學科前沿話題、弱化證明、注重應用分析、理論與實踐相結合等教學新思路，并結合當前人工智能、雙語教學、網絡教學等背景，探討如何進行教學改革。但總體而言，教學改革還停留在理論上，未進行廣泛、深入地實踐。

南京航空航天大學的組合數學由計算機學院教師進行授課，為各學科之間的滲透打下了基礎。筆者以一線教師的視角，在實踐中探索組合數學與計算機科學的交叉融合。本文以組合數學中鏈與反鏈的知識點為例，探索如何將數學類課程講解得更加通俗易懂，并發掘數學與計算機學科的結合點，提升數學類課程的應用性。

1 鏈與反鏈

鏈與反鏈是組合數學中的一個重要知識點，但其內容比較抽象，是組合數學教學中的一個難點。

鏈與反鏈定義如下：

定義1 設(X,≤)是有限偏序集，反鏈是X的一個子集A，它的每一對元素都不可比。

例1：S={a,b,c,d}是一個集合，S的子集構成的集合是一個有限偏序集，則A={{a,b},{b,c,d},{a,d},{a,c}}是該有序偏序集的一個反鏈。

傳統工藝傳承、振興的實踐和學術專著的編撰可以培養新一代的傳統工藝專家學者。他們必須有扎實的理論基礎,較強的獨立工作能力,較高的傳統工藝學術造詣，人類學、民族學、民俗學等相關學科的學術素養,較高的外語水平,能參與國際交流和合作。

定義2 設(X,≤)是有限偏序集，鏈是X的一個子集C，它的每一對元素都可比。

例2：S={a,b,c,d}是一個集合，S的子集構成的集合是一個有限偏序集，則φ?{b}?{b,c}?{a,b,c}?{a,b,c,d}是該有限偏序集的一個鏈。

在以上內容教學中，首先給出定義，隨即給出一個具體案例，幫助學生理解基本概念。

2 鏈與反鏈長度與個數關系的教學方法

然后，介紹關于鏈與反鏈之間關系的一系列重要定理。

定理1 如果A是一個反鏈，而C是一個鏈，則|A?C|=1。

該定理比較容易理解，即鏈與反鏈的交集最多只有一個元素，否則鏈中兩個元素處于同一個反鏈中，將與反鏈的定義矛盾。

接下來，引出關于鏈與反鏈長度與個數的關系，有如下兩個定理。

定理2 設(X,≤)是有限偏序集，設r是鏈的最大長度，則X可被劃分成r個反鏈，但不能劃分成少于r個反鏈。

定理3 設(X,≤)是有限偏序集，設m是反鏈的最大長度，則X可被劃分成m個鏈，但不能劃分成少于m個鏈。

數學定理中，一部分定理的證明實則是對定理的解釋，通過證明，可以深入解釋定理。但還有一部分定理的證明也無法幫助讀者理解定理，如上述的定理2 和定理3。

這兩個定理將鏈的最大長度與反鏈的最小個數，反鏈的最大長度與鏈的最小個數聯系起來。但定理證明非常復雜，即便進行了嚴格證明，學生也無法深入理解定理，更無法將其應用于計算機學科中。

因此，筆者在教學中采取了以下教學方法，形象地解釋了鏈與反鏈長度與個數的關系。

首先，將整個偏序集的所有元素排列到一個m×r的矩陣中，即：

該矩陣每一行中的元素構成一個鏈，每一列中的元素構成一個反鏈。當然，實際中可能有一些位置為空，沒有元素填充。

從該矩陣中可以看出，該偏序集X中鏈的最大長度為r，設最長鏈為x11≤x12≤x13… ≤x1r，將矩陣中每一列作為一個反鏈，則X可被劃分成r個反鏈，且最少為r個，否則會出現最長鏈中的元素未被劃分到任何一條反鏈中的情況。但X可被劃分為更多反鏈，如將該矩陣重新表示為如下形式：

此時，仍然將矩陣中每一列作為一個反鏈，則X可被劃分成r+1 個反鏈，從而解釋了定理2。

定理3 中也有類似解釋，該偏序集X中反鏈的最大長度為m，設最長反鏈為{x11,x12,…,xm1}，將矩陣中每一行作為一個鏈，則X可被劃分成m個鏈，且最少為m個，否則會出現最長反鏈中的元素未被劃分到任何一條鏈中的情況。但X可被劃分為更多鏈，如將該矩陣重新表示為如下形式：

此時仍然將矩陣中每一行作為一個鏈，則X可被劃分成m+1 個鏈，從而解釋了定理3。

值得強調的是，這種排列集合元素的方法，針對每個定理是成立的，但同一個排列無法同時適用于兩個定理。

這種解釋方法雖然不如教材中的定理證明過程嚴謹，但采用較為通俗的方法進行解釋，作為定理證明的補充，可幫助學生深入理解定理。

3 反鏈在計算機學科中的應用

關于反鏈有一個有名的定理，即Sperner 定理。具體定理如下：

定理4 設S是n個元素的集合，則S上的一個反鏈至多包含個集合。

該定理在計算機領域有著廣泛應用。筆者在授課過程中給出了如下實例，要求學生從反鏈角度進行思考。

例3：愛爾蘭銀行的密碼系統并非像國內一樣要求每次輸入6 位密碼，而是每次由銀行的電腦系統隨機選擇3位密碼要求客戶輸入。

為何每次銀行的電腦系統選出3 位而不是2 位，或者4位呢？由Sperner 定理可知，集合S={1,2,3,4,5,6}作為一個6 元素集合，S上的最長反鏈包含=20 個集合，且唯一的最長反鏈為S的所有3 元素子集。所以銀行的電腦系統每次選擇3 位數字要求客戶輸入，可在最大程度上減少重復。

同時，在人機交互中，雖然電腦和手機的屏幕越來越大，但智能手表卻基本固定為手腕大小。在手腕大小的智能手表上，輸入6 位密碼是一個較為復雜的操作。為了減少操作的復雜性，輸入更短位數的密碼則是一個選擇。但密碼長度縮短勢必影響安全性，因此輸入6 位密碼中的隨機3 位，則是一個更優的選擇。

筆者在教學中通過Sperner 定理的實際案例及應用前景，充分調動學生的學習興趣，既幫助學生理解Sperner 定理，又啟發學生將其應用于自己的研究過程中。

4 教學效果

通過本模塊的教學，學生不僅學習到組合數學中鏈與反鏈的知識，并且對該知識點在計算機學科的應用有了新的了解。與此同時，還進一步了解了其它國家的銀行密碼系統，拓寬了視野。

更重要的是，通過多學科融合的教學方式，激發了計算機專業學生對于組合數學的學習熱情。學習組合數學不再僅是為了獲得學分，還是其研究工作的助手。

5 結語

組合數學作為計算機科學的基礎課程，如何將數學類課程講解得通俗易懂，又能真正得到實踐應用，是一個非常值得探討的課題。本文探索了一“講”二“應用”的方法，以組合數學中鏈與反鏈的知識點為例。一是講得清晰，便于學生理解。將集合中的元素重排列到一個矩陣中，形象地解釋了鏈和反鏈長度與個數的關系，幫助學生更好地理解相關定理；二是尋求數學與計算機學科的結合點，將理論知識應用于實際中。通過給出反鏈在計算機領域的一個應用實例及其應用前景，將理論知識與實際應用聯系起來，極大地調動了學生學習興趣，加深了學生對相關知識的理解。

筆者采用一“講”二“應用”的方法將數學理論講解得深入淺出，并與實際應用相結合，應用于組合數學中鏈與反鏈的教學過程中，形成了數學教學過程中的一個經典案例。作為數學類課程教學改革的一個應用實例，實現了多學科融合、引入學科前沿話題、注重應用分析等教學改革思路，非常值得借鑒和推廣。該教學方法也非常適用于所有數學類課程，能幫助將數學類課程講“活”，真正起到理論促進實踐的作用。