組合數(shù)學(xué)中鏈與反鏈的教學(xué)探索及實(shí)踐

李 丹

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

0 引言

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

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

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

1 鏈與反鏈

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

鏈與反鏈定義如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 教學(xué)效果

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

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

5 結(jié)語

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

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