李 丹

（南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇南京 211106）

0 引言

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

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

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

1 鏈與反鏈

鏈與反鏈?zhǔn)墙M合數(shù)學(xué)中的一個重要知識點，但其內(nèi)容比較抽象，是組合數(shù)學(xué)教學(xué)中的一個難點。

鏈與反鏈定義如下：

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

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

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

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

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

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

2 鏈與反鏈長度與個數(shù)關(guān)系的教學(xué)方法

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

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

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

接下來，引出關(guān)于鏈與反鏈長度與個數(shù)的關(guān)系，有如下兩個定理。

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

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

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

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

因此，筆者在教學(xué)中采取了以下教學(xué)方法，形象地解釋了鏈與反鏈長度與個數(shù)的關(guān)系。

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

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

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

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

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

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

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

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

3 反鏈在計算機學(xué)科中的應(yīng)用

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

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

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

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

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

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

筆者在教學(xué)中通過Sperner 定理的實際案例及應(yīng)用前景，充分調(diào)動學(xué)生的學(xué)習(xí)興趣，既幫助學(xué)生理解Sperner 定理，又啟發(fā)學(xué)生將其應(yīng)用于自己的研究過程中。

4 教學(xué)效果

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

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

5 結(jié)語

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

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