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

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025）

0 引言

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

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

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

1.1 課程側(cè)重點(diǎn)

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

1.2 學(xué)科側(cè)重點(diǎn)

計(jì)算機(jī)科學(xué)與技術(shù)作為最熱門(mén)的學(xué)科，新理論新技術(shù)層出不窮，新應(yīng)用遍地開(kāi)花。編程動(dòng)手能力成為評(píng)價(jià)學(xué)生的一大指標(biāo)，編程本身就容易出現(xiàn)各種問(wèn)題導(dǎo)致學(xué)生放棄，因此但凡學(xué)生能夠熟練編程，甚至做出一些直觀演示效果好的程序或應(yīng)用，教師就會(huì)給予很大鼓勵(lì)，很容易放松對(duì)理論嚴(yán)謹(jǐn)性的要求。

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

1.3 教學(xué)與考核難點(diǎn)

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

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

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

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

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

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

2.2 嚴(yán)謹(jǐn)性不足，算法“失效”情況難以預(yù)料

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

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

3 改進(jìn)對(duì)策

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

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

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

3.2 教學(xué)實(shí)操上，以學(xué)生為中心，注重正確性考察

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

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

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

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

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

4.1 劃分錯(cuò)誤類(lèi)型，逐一排除

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

4.2 劃分?jǐn)?shù)據(jù)類(lèi)型，逐一求證

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

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

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

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

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

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

5 結(jié)語(yǔ)

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