數(shù)據(jù)結(jié)構(gòu)課程中理論證明的不足及加強策略

程欣宇，張 麗，汪 健，葉 晨

（貴州大學 計算機科學與技術(shù)學院，貴州 貴陽 550025）

0 引言

數(shù)據(jù)結(jié)構(gòu)課作為計算機專業(yè)的核心課程，既有理論分析數(shù)據(jù)之間的邏輯關(guān)系、存儲效率和算法執(zhí)行效率，又有解決實際問題的案例。但目前的教材、教學案例、考核中，幾乎沒有各種經(jīng)典案例的理論證明［1-2］。例如：為什么最小生成樹的Kruskal算法每次選擇兩個聯(lián)通代價最小的連通分量進行連通？Dijkstra算法為什么選擇離源頂點直接路徑最短的頂點？Huffman樹為什么選擇權(quán)值和最小的兩個根結(jié)點合并？匹配字符串的KMP、BM算法效率高，但會漏配錯配嗎？通過教學，學生學會了這些算法的操作步驟，能通過畫圖、填表和分析復雜度，完成相應的作業(yè)和考試，也能編寫程序?qū)斎氲膯栴}實例進行求解。但是，學生大概率并不知道，也未曾思考過：這些數(shù)據(jù)結(jié)構(gòu)的操作算法在任何情況下都能保證正確性嗎？如何證明這些算法的正確性？更進一步地，這些算法是如何被前人設計出來的？有沒有更統(tǒng)一的規(guī)律存在，以指導人們獲得更廣泛的問題求解能力？“道技關(guān)系”是教書育人者應該思考的［3］。若不引導學生思考這些問題，當出現(xiàn)的實際問題需要學生設計數(shù)據(jù)結(jié)構(gòu)和算法時，學生即便能夠設計出高性能的數(shù)據(jù)結(jié)構(gòu)和算法，也很難去證明或者證偽一個算法的正確性。本文重點討論形成這種現(xiàn)象的原因、可能產(chǎn)生的危害以及相應的改進對策。

1 數(shù)據(jù)結(jié)構(gòu)課程不重視算法理論證明的原因

數(shù)據(jù)結(jié)構(gòu)算法的理論證明包括性能、性質(zhì)和正確性的證明。定量分析在教學中有大量討論，如二叉樹的度為2的結(jié)點數(shù)量是多少？合并排序最壞情況的比較次數(shù)是多少？但是，性質(zhì)和正確性的證明鮮有討論，如搜索匹配的錯配漏配問題、最優(yōu)化目標是否能夠保證的問題，本文歸納原因如下：

1.1 課程側(cè)重點

數(shù)據(jù)結(jié)構(gòu)課程信息量大，各種邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的組合繁多，對應可以解決的問題案例也非常多。需要講授大量概念、方法和案例分析，又要強調(diào)掌握計算步驟，要能夠上機實踐，還要做性能分析，再加上學時數(shù)有限，導致教學中很容易放棄對理論證明的要求。雖然實驗驗證僅僅是證明了相關(guān)算法在少量的典型數(shù)據(jù)上有效，但其并不能像理論證明一樣，能夠更全面地證明算法的正確性，后者仍然被擠占掉。

1.2 學科側(cè)重點

計算機科學與技術(shù)作為最熱門的學科，新理論新技術(shù)層出不窮，新應用遍地開花。編程動手能力成為評價學生的一大指標，編程本身就容易出現(xiàn)各種問題導致學生放棄，因此但凡學生能夠熟練編程，甚至做出一些直觀演示效果好的程序或應用，教師就會給予很大鼓勵，很容易放松對理論嚴謹性的要求。

計算機科學與技術(shù)作為可以授予理科或者工科的一級學科，一流學科建設中的大多數(shù)學校選擇了授予工科學位，也導致了對理論深度要求的欠缺。

1.3 教學與考核難點

教學和考核數(shù)據(jù)結(jié)構(gòu)的基本概念、基本性質(zhì)、基本運算方法，如記住什么叫穩(wěn)定的排序、學會將插入結(jié)點后的AVL樹調(diào)整平衡、分析一個數(shù)據(jù)操作最壞情況下的復雜度相對容易。但是理論證明或者證偽一個算法，就如同考核一個現(xiàn)實問題的算法設計到程序設計一樣難。由于涉及到不同的算法規(guī)模、底層邏輯，因此解題思路靈活，非常難以判卷給分，出題難度和靈活性也不好控制，一不小心就難住大部分學生。

本文舉一個真實的教學案例，用以反映OJ測試可能存在的不嚴謹性。在某大學的OJ系統(tǒng)中，為了考察學生對字符串快速匹配算法的掌握情況，有這么一道題：輸入為兩個字符串A和B，要求設計程序判斷A是否為B循環(huán)左移的結(jié)果。命題者希望學生能夠?qū)復制拼接成AA后，判斷B是否在AA中出現(xiàn)。但在給測試用例時，沒有考慮到：如果A和B滿足循環(huán)左移后的相等關(guān)系，A、B循環(huán)相鄰字符的共生矩陣也必然相等，而計算共生矩陣只需要線性時間［4］。因此，用很短的代碼，只檢查了必要性，未真正用高性能字符串匹配算法檢查充分性，也能欺騙過OJ，拿到此題的滿分，運行耗時還比嚴謹正確的算法快不少。

2 數(shù)據(jù)結(jié)構(gòu)課程中理論性證明不足的危害性

從本科生到工程師或者研究生，總會面臨一些數(shù)據(jù)結(jié)構(gòu)和算法設計，如果對正確性證明認知不足［5］，遲早會暴露以下問題：

2.1 理論支撐欠缺，學生理論水平難獲提升

即便所設計的算法高效可靠，但是因為缺乏理論證明方法，哪怕通過大量測試，也無法在根本上保證算法程序的正確性［6］，客戶和團隊也擔心關(guān)鍵時刻失效。面對重大項目就不敢上馬，不能承擔重任，難以獲得技術(shù)創(chuàng)新的紅利。這在教學時不能立即感受到，需要持續(xù)和重點關(guān)注一定量的學生工作后的長期發(fā)展，具有豐富項目經(jīng)驗的教師越能體會到這點。如一個動手能力較強的學生，參與了實戰(zhàn)型的畢業(yè)設計，他采用鄰接矩陣存儲3 000個道路卡口的連接情況。答辯時提問：“你用鄰接矩陣存儲，難道不考慮存儲的代價是n2嗎？”，學生回答是：“我用了json存儲，比較緊湊?！逼鋵崳还苁莏son還是yml、bson，都是一種緊湊的數(shù)據(jù)交換格式，僅僅能夠?qū)⑾禂?shù)的存儲空間優(yōu)化，并不能解決稀疏矩陣的存儲和高效檢索。這個案例很典型，反映了不少學生和教師，一旦重視動手能力培養(yǎng)，就容易放松理論水平的修煉。

2.2 嚴謹性不足，算法“失效”情況難以預料

與上述難以證明導致無法上馬的情況不同，市場講究競爭、業(yè)績和“快魚吃慢魚”，更多算法的理論正確性證明會以各種測試進行代替，繼而上線。如上文所舉例子，測試用例本身是難以全面覆蓋的，稍有疏忽，系統(tǒng)就會出現(xiàn)漏洞，繼而導致數(shù)據(jù)完整性、一致性和計算結(jié)果可靠性降低。

再以數(shù)據(jù)結(jié)構(gòu)循環(huán)隊列的一個應用教學案例為例。循環(huán)隊列的應用很多，一個抽象但能夠映射很多現(xiàn)實問題的案例［7］是這樣的：已知一個集合A中有n個元素及其沖突關(guān)系矩陣R，希望將A劃分為若干個子集，使得相同子集中的元素不沖突。此案例充分利用了循環(huán)隊列：將A中元素所有入隊，循環(huán)從A中取出隊首元素，若該元素與當前子集中的元素不沖突，就放入當前子集，否則就放回隊尾。隊列中的元素出隊一遍前，創(chuàng)建一個當前子集，直到隊列空。案例中9個元素的沖突關(guān)系為：R=｛（2，8），（9，4），（2，9），（2，1），（2，5），（6，2），（5，9），（5，6），（5，4），（7，5），（7，6），（3，7），（6，3）｝。按方法操作下來劃分的子集為：｛1，3，4，8｝、｛2，7｝、｛5｝、｛6，9｝。但更好的劃分方案為：｛1，3，5，8｝、｛2，4，7｝、｛6，9｝。如果不講清楚這個算法的不足，學生會默認這是一個高效且完全正確的算法。

3 改進對策

針對數(shù)據(jù)結(jié)構(gòu)課程中理論性證明不足的原因及危害，提出以下改進對策：

3.1 指導思想上，“術(shù)”“道”兼?zhèn)?/h3>

在學科指定培養(yǎng)方案時，要有理工兼?zhèn)涞闹笇枷?，既傳授“術(shù)”，也探討“道”。具體到數(shù)據(jù)結(jié)構(gòu)課程中，除強調(diào)數(shù)據(jù)的邏輯關(guān)系、存儲結(jié)構(gòu)、訪問效率，也應當注重數(shù)據(jù)訪問算法的正確性。

3.2 教學實操上，以學生為中心，注重正確性考察

（1）充分相信學生，空出教學時間。作為專業(yè)核心基礎(chǔ)課，學生學習數(shù)據(jù)結(jié)構(gòu)課程的熱情本身很高，授課教師不需要大量重復演算一些案例。如果每個案例從第一個步驟重復操作到最后一個步驟，會占據(jù)課堂大量時間，要相信學生有舉一反三的能力，可以通過習題和復習掌握好要求的概念和操作方法。在總學時有限的情況下，只有優(yōu)化好教學時間，才能更好地引導學生思考諸如理論正確這樣的深入內(nèi)容。

（2）啟發(fā)和尊重學生的求知欲。讓學生認為自己不是“工具人”，不只會按規(guī)定動作操作數(shù)據(jù)，編寫代碼。教師可以通過收集一定的案例，讓學生知道：一個算法碰巧能對，是很不嚴謹?shù)囊患?，甚至教科書直接講授而未證明的算法，都是可以質(zhì)疑的。而質(zhì)疑的最好武器，就是掌握證明技術(shù)。

（3）在考核環(huán)節(jié)加入正確性考察。對于數(shù)據(jù)結(jié)構(gòu)課程而言，選擇題、填空題可以出現(xiàn)考察算法和數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，比如某種排序的穩(wěn)定性、某個算法最壞情況下的運算次數(shù)，自然也可以考察某個算法是否一定會得到正確結(jié)果。至于簡答題，直接可以加入證明題，給出某個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)算法，或者類似的算法，讓學生證明或者證偽。

4 啟發(fā)式證明及證偽的教學方法

如同數(shù)據(jù)結(jié)構(gòu)和算法有設計思路，證明也是有思路的。證明方法是如何想到的，往往比證明文本更重要。除使用的針對特定語言操作數(shù)據(jù)結(jié)構(gòu)［8］的形式化證明，本文提出一些更適用于教學的證明方式，并在實際教學中進行了實踐。

4.1 劃分錯誤類型，逐一排除

第一種教學方法是劃分錯誤類型，受PBL教學模式［9］啟發(fā)，以KMP為例，首先拋出疑問：“KMP算法比每次失配都重新對比的蠻力匹配算法高效，那如何證明其正確性？”，該問題很籠統(tǒng)，只能將學生注意力吸引過來。接著啟發(fā)：“換一種提法，如果一個字符串匹配算法運行結(jié)果不正確，可以分為哪些類型的錯誤？”多數(shù)學生仍然可能無法對答。教師再進行啟發(fā)：“一種情況是該匹配的沒匹配上，另外一種情況是？”學生必然能夠回答“不該匹配的給匹配上了”。教師約定第一種情況叫漏配，然后又與學生討論漏配是不是只發(fā)生在滑動過快了？KMP在滑動時，有沒有可能漏配？最后形成一個比較嚴密的證明。

4.2 劃分數(shù)據(jù)類型，逐一求證

一個算法面對各種輸入的組合，如何證明其都能夠正確處理？同樣需要抽象和歸類的方法。其中，數(shù)學歸納法能夠?qū)⒁?guī)模不同的數(shù)據(jù)，歸為一類情況統(tǒng)一證明，包括各種排序、最小生成樹、最短路徑、Huffman樹等貪心選擇算法，均可以采用此技術(shù)。

4.3 反例構(gòu)造技術(shù)

證偽一個算法，難在構(gòu)造一個實例。如何攻擊一個算法的軟肋？首先需要暴露這個軟肋。本文方法有如下3種：①反例的實例規(guī)模不必大；②識別哪些數(shù)據(jù)無關(guān)緊要，盡量取一些較小的值即可；③從錯誤結(jié)果逆操作，可以幫助構(gòu)造導致算法錯誤的合理輸入。該思想與對抗神經(jīng)網(wǎng)絡訓練攻擊樣本［10］一致。

以證明希爾排序不是穩(wěn)定的為例，只考慮2趟，結(jié)果為有序的4個數(shù)（1b，1a，2，3），其中1a和1b均為1的兩個實例，1b在輸入序列中處于1a之后，被希爾排序交換到1a前面，由此取增量序列為｛3，1｝，輸入序列為（3，1a，2，1b），就能證明希爾排序不穩(wěn)定。

這種反例的構(gòu)造，在不同案例中反復使用，同樣通過啟發(fā)的方法，讓學生先于教師構(gòu)造出來，學生自然就容易掌握其中的規(guī)律。

在實際教學實踐中，本文對貴州大學計算機科學與技術(shù)學院2019級計科專業(yè)3個班的學生講授KMP、最短路徑兩個算法后進行了對比。實驗班級采用了質(zhì)疑+啟發(fā)教學方法，對比班級為傳統(tǒng)的算法步驟，演示操作數(shù)據(jù)的方法。在實驗班級講解了構(gòu)造反證的思路后，給足10min的理解思考時間，要求對擴展問題自行思考構(gòu)造反例，實驗班級成功了81%，對比班級僅成功了38%，并且實驗班級構(gòu)造的用例明顯簡潔。

5 結(jié)語

數(shù)據(jù)結(jié)構(gòu)課程是計算機專業(yè)的一門重要核心課程，現(xiàn)有的教材、授課及考核中，幾乎不涉及各種經(jīng)典案例的理論證明。本文從不重視算法正確性證明的原因、相應危害性、改進策略等方面進行了闡述。總而言之，教師應對所授課程不斷進行研究，立足理論，深入實踐，探索教學改革新思路，引導學生更進一步提高自己的基礎(chǔ)理論能力和持續(xù)創(chuàng)新能力。