數據結構課程中理論證明的不足及加強策略

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

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

0 引言

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

1 數據結構課程不重視算法理論證明的原因

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

1.1 課程側重點

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

1.2 學科側重點

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

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

1.3 教學與考核難點

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

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

2 數據結構課程中理論性證明不足的危害性

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

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

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

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

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

再以數據結構循環隊列的一個應用教學案例為例。循環隊列的應用很多，一個抽象但能夠映射很多現實問題的案例［7］是這樣的：已知一個集合A中有n個元素及其沖突關系矩陣R，希望將A劃分為若干個子集，使得相同子集中的元素不沖突。此案例充分利用了循環隊列：將A中元素所有入隊，循環從A中取出隊首元素，若該元素與當前子集中的元素不沖突，就放入當前子集，否則就放回隊尾。隊列中的元素出隊一遍前，創建一個當前子集，直到隊列空。案例中9個元素的沖突關系為：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 改進對策

針對數據結構課程中理論性證明不足的原因及危害，提出以下改進對策：

3.1 指導思想上，“術”“道”兼備

在學科指定培養方案時，要有理工兼備的指導思想，既傳授“術”，也探討“道”。具體到數據結構課程中，除強調數據的邏輯關系、存儲結構、訪問效率，也應當注重數據訪問算法的正確性。

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

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

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

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

4 啟發式證明及證偽的教學方法

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

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

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

4.2 劃分數據類型，逐一求證

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

4.3 反例構造技術

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

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

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

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

5 結語

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