盧 玲，曾慶森

（重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400050）

算法設(shè)計(jì)類(lèi)課程分層大案例庫(kù)設(shè)計(jì)與構(gòu)建方法研究

盧 玲，曾慶森

（重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400050）

分析算法設(shè)計(jì)類(lèi)課程實(shí)踐教學(xué)案例存在規(guī)模小、背景簡(jiǎn)化、數(shù)據(jù)形態(tài)單一、不利于觀察算法的時(shí)空效率問(wèn)題，提出以數(shù)據(jù)結(jié)構(gòu)課程為對(duì)象，建立分層大案例庫(kù)的研究目標(biāo)，闡述大案例的特點(diǎn)并結(jié)合具體教學(xué)實(shí)踐介紹大案例庫(kù)的設(shè)計(jì)與構(gòu)建方法。

算法設(shè)計(jì)；教學(xué)案例；數(shù)據(jù)形態(tài)；案例庫(kù)

1 背 景

算法設(shè)計(jì)類(lèi)課程包括程序設(shè)計(jì)基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計(jì)、面向?qū)ο蟪绦蛟O(shè)計(jì)等，是普通高校計(jì)算機(jī)各專(zhuān)業(yè)及部分信息類(lèi)非計(jì)算機(jī)專(zhuān)業(yè)重要的專(zhuān)業(yè)基礎(chǔ)課[1]。課程受眾廣泛，其受眾關(guān)系如圖1所示。從圖1可見(jiàn)，數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計(jì)課程由于具有邏輯性強(qiáng)、抽象性高[2]的特點(diǎn)，在課程體系中承上啟下，是將學(xué)生的綜合能力從實(shí)踐向理論層面提升的重要環(huán)節(jié)。

圖1 算法設(shè)計(jì)類(lèi)課程及其受眾關(guān)系圖

目前，從計(jì)算科學(xué)的應(yīng)用現(xiàn)狀看，隨著云計(jì)算等分布式計(jì)算平臺(tái)的發(fā)展，數(shù)據(jù)規(guī)模不斷擴(kuò)大，以大數(shù)據(jù)為背景的數(shù)據(jù)分析、信息檢索等應(yīng)用已成為計(jì)算科學(xué)領(lǐng)域的重要熱點(diǎn)。這類(lèi)應(yīng)用面向具有超大規(guī)模、異構(gòu)、多源、多維特征的數(shù)據(jù)，其研究往往需要較強(qiáng)的理論基礎(chǔ)和創(chuàng)新能力。這些具有大數(shù)據(jù)特征的現(xiàn)實(shí)問(wèn)題，對(duì)學(xué)生的分析能力和研究創(chuàng)新能力提出了比以往任何工程項(xiàng)目都更高的新要求。在培養(yǎng)研究創(chuàng)新能力方面，算法設(shè)計(jì)類(lèi)課程是重要的支撐。課程通過(guò)學(xué)習(xí)算法理論為學(xué)生的模型抽象能力[3]和創(chuàng)新能力的形成奠定基礎(chǔ)。為使抽象的算法具體化、形象化[4]，課程往往設(shè)計(jì)實(shí)驗(yàn)案例并輔以課程設(shè)計(jì)等綜合實(shí)踐。從教學(xué)實(shí)踐看，現(xiàn)有實(shí)驗(yàn)案例多以驗(yàn)證性、小型綜合性實(shí)驗(yàn)為主。這些實(shí)驗(yàn)多對(duì)問(wèn)題背景設(shè)置約束條件，將問(wèn)題規(guī)模限制在一定范圍之內(nèi)。實(shí)驗(yàn)使用的測(cè)試數(shù)據(jù)不是真實(shí)數(shù)據(jù)，其數(shù)據(jù)規(guī)模小、數(shù)據(jù)結(jié)構(gòu)單一。這使得學(xué)生常常對(duì)算法的應(yīng)用場(chǎng)景產(chǎn)生疑惑，難以理解算法在真實(shí)環(huán)境中的適用性及效果。由于這一階段的學(xué)生缺少工程實(shí)踐經(jīng)驗(yàn)，難以預(yù)期真實(shí)環(huán)境的數(shù)據(jù)規(guī)模及數(shù)據(jù)形態(tài)，對(duì)算法的時(shí)間、空間性能缺乏真實(shí)感受，使所學(xué)算法分析理論變成紙上談兵，無(wú)法將基礎(chǔ)算法規(guī)律化[5]，出現(xiàn)理論與實(shí)踐脫節(jié)，學(xué)生雖學(xué)而不以為然的問(wèn)題。

可見(jiàn)，傳統(tǒng)教學(xué)中基于虛擬、小型、受約束數(shù)據(jù)的案例，逐漸與大數(shù)據(jù)背景下的工程實(shí)踐問(wèn)題脫節(jié)，成為制約分析和研究能力的瓶頸，是算法設(shè)計(jì)類(lèi)課程面臨的現(xiàn)實(shí)問(wèn)題。在這樣的背景下，我們以數(shù)據(jù)結(jié)構(gòu)課程為研究對(duì)象，提出對(duì)課程的案例庫(kù)進(jìn)行梳理和更新，設(shè)計(jì)具有多種數(shù)據(jù)規(guī)模、多元數(shù)據(jù)形態(tài)的分層大案例庫(kù);并提出針對(duì)分層大案例庫(kù)的多元考核體系，使大案例庫(kù)的應(yīng)用具有可行性和良好的可操作性。

2 分層大案例庫(kù)結(jié)構(gòu)設(shè)計(jì)

1）大案例及其特點(diǎn)。

我們把大案例定義為具有一定規(guī)模、一定邏輯結(jié)構(gòu)、一定形態(tài)的數(shù)據(jù)處理實(shí)例。大案例中的“大”體現(xiàn)為數(shù)據(jù)規(guī)模、數(shù)據(jù)元素的形態(tài)是復(fù)雜的，意味著案例中將要處理數(shù)據(jù)的未知性，包括規(guī)模未知、形態(tài)未知、結(jié)構(gòu)未知。其“一定規(guī)?！笔侵笖?shù)據(jù)量小規(guī)模、數(shù)據(jù)量中規(guī)模、數(shù)據(jù)量大規(guī)模?！耙欢ㄟ壿嫿Y(jié)構(gòu)”是指數(shù)據(jù)具有線性、樹(shù)形、圖形結(jié)構(gòu)?！耙欢ㄐ螒B(tài)”是指數(shù)據(jù)元素包括簡(jiǎn)單類(lèi)型（整型、浮點(diǎn)型、字符型）、復(fù)雜類(lèi)型（文本、圖像、聲音）。結(jié)合這3個(gè)“一定”對(duì)大案例進(jìn)行定義和篩選，并將案例庫(kù)進(jìn)行組織及結(jié)構(gòu)分層，由此得到如圖2 所示的分層案例庫(kù)邏輯結(jié)構(gòu)。

如圖2所示，大案例庫(kù)是一個(gè)3維結(jié)構(gòu)，具有“數(shù)據(jù)規(guī)模層次”“數(shù)據(jù)形態(tài)層次”“邏輯結(jié)構(gòu)層次”3個(gè)維度。每個(gè)維度上分別按數(shù)據(jù)規(guī)模、數(shù)據(jù)形態(tài)、邏輯結(jié)構(gòu)進(jìn)行層次劃分?？梢?jiàn)，大案例庫(kù)中的每一個(gè)案例是3維空間中的1個(gè)點(diǎn)，如圖2所示的大案例k。

圖2 分層大案例庫(kù)示意圖

2）大案例設(shè)計(jì)的重點(diǎn)。

大案例設(shè)計(jì)的重點(diǎn)在于突出數(shù)據(jù)處理實(shí)例中數(shù)據(jù)的不可預(yù)知性、不可觀察性。以數(shù)據(jù)結(jié)構(gòu)課程的“哈夫曼樹(shù)及哈夫曼編碼”為例，傳統(tǒng)實(shí)驗(yàn)案例中，通常給定字符頻度或分布（通常為整型或浮點(diǎn)型數(shù)據(jù)），要求學(xué)生基于給定的分布進(jìn)行實(shí)驗(yàn);在測(cè)試哈夫曼編碼時(shí)，一般也以給定的文本為測(cè)試數(shù)據(jù)。這種案例設(shè)計(jì)限定了字符的范圍和分布，限定了測(cè)試數(shù)據(jù)的規(guī)模。雖然這些限定簡(jiǎn)化了問(wèn)題的復(fù)雜度，使學(xué)生能快速掌握算法原理，但從算法分析的角度，問(wèn)題數(shù)據(jù)及其規(guī)模的簡(jiǎn)化使學(xué)生難以對(duì)真實(shí)數(shù)據(jù)形成認(rèn)知。由于算法的時(shí)空指標(biāo)及算法策略的優(yōu)劣，只有在測(cè)試數(shù)據(jù)達(dá)到一定規(guī)模對(duì)計(jì)算機(jī)的存儲(chǔ)形成壓力時(shí)才能觀察到，進(jìn)而迫使學(xué)生考慮算法的適用性問(wèn)題，主動(dòng)尋求優(yōu)化方案。簡(jiǎn)化的案例背景及數(shù)據(jù)使某些算法評(píng)估指標(biāo)不易呈現(xiàn)，難以激勵(lì)學(xué)生對(duì)算法優(yōu)劣進(jìn)行主動(dòng)評(píng)價(jià)。實(shí)踐中發(fā)現(xiàn)，大多數(shù)學(xué)生對(duì)算法優(yōu)劣的理解源于書(shū)本知識(shí)，很少通過(guò)實(shí)驗(yàn)主動(dòng)觀察和體驗(yàn)到。由此，針對(duì)“哈夫曼編碼問(wèn)題”設(shè)計(jì)的大案例分為L(zhǎng)1～L3三層，描述如下：

L1：給定訓(xùn)練文本，限定字符范圍，包括大小寫(xiě)英文字符、常見(jiàn)標(biāo)點(diǎn)符號(hào)（逗號(hào)，句號(hào)）。

L2：自行搜集訓(xùn)練文本（文本數(shù)＜1 000篇），手動(dòng)整理字符，保留大小寫(xiě)英文字符、常用標(biāo)點(diǎn)符號(hào)。

L3：自行搜集訓(xùn)練文本（文本數(shù)＞1 000篇），保留全部（多種）字符、多種標(biāo)點(diǎn)符號(hào)。

在案例級(jí)別L3上，由于訓(xùn)練文本數(shù)擴(kuò)大，字符范圍未知，需要對(duì)哈夫曼樹(shù)的存儲(chǔ)設(shè)計(jì)進(jìn)行可行性分析和論證。對(duì)所生成的哈夫曼編碼，由于符號(hào)數(shù)量多，難以進(jìn)行人工觀測(cè)，只能通過(guò)編程計(jì)算哈夫曼編碼與其他（如定長(zhǎng)編碼）編碼的電文壓縮比，由此促使學(xué)生為尋求合理的解決方案，運(yùn)用多種技術(shù)對(duì)數(shù)據(jù)進(jìn)行觀察和分析，展開(kāi)研究性學(xué)習(xí)。

3 大案例庫(kù)構(gòu)建的關(guān)鍵問(wèn)題

如前所述，大案例處理的數(shù)據(jù)應(yīng)具有一定的未知性和不可觀測(cè)性?？蓪⑦@種未知性分為3個(gè)維度：規(guī)模未知、形態(tài)未知、邏輯結(jié)構(gòu)未知，基于此，建立大案例庫(kù)需解決4個(gè)關(guān)鍵問(wèn)題。

3.1 合理定義大案例數(shù)據(jù)的規(guī)模

可將大案例的數(shù)據(jù)規(guī)模定義為簡(jiǎn)化數(shù)據(jù)、中等規(guī)模數(shù)據(jù)、大（在現(xiàn)有實(shí)踐條件之內(nèi)）規(guī)模數(shù)據(jù)。實(shí)踐中可分3階段進(jìn)行案例實(shí)施：

（1）STEP 1：簡(jiǎn)化數(shù)據(jù)。使算法快速實(shí)施;形成簡(jiǎn)化數(shù)據(jù)的測(cè)試報(bào)告;屬于封閉答案的問(wèn)題，其測(cè)試結(jié)果及算法策略是確定的。

（2）STEP 2：中等規(guī)模數(shù)據(jù)。例如將排序數(shù)據(jù)規(guī)模設(shè)置為5 000～5 000 000整數(shù)，要求進(jìn)行多組數(shù)據(jù)規(guī)模、多種算法策略的測(cè)試，并以數(shù)據(jù)表的形式記錄測(cè)試的時(shí)空開(kāi)銷(xiāo)，最終形成中等規(guī)模數(shù)據(jù)的測(cè)試報(bào)告;屬于開(kāi)放答案的問(wèn)題，包括多樣的測(cè)試結(jié)果及多種算法優(yōu)化策略。

（3）STEP 3：大規(guī)模數(shù)據(jù)。例如將排序數(shù)據(jù)規(guī)模設(shè)置為5 000 000整數(shù)以上，對(duì)由此可能產(chǎn)生的存儲(chǔ)異常及時(shí)間代價(jià)問(wèn)題，要求采取合理的方法進(jìn)行解決，最終形成大規(guī)模數(shù)據(jù)的測(cè)試報(bào)告;屬于開(kāi)放答案的問(wèn)題，包括無(wú)解、多種測(cè)試結(jié)果及多種存儲(chǔ)方式、多種算法優(yōu)化策略。

由此可見(jiàn)，基于大案例展開(kāi)的實(shí)踐總是包含多數(shù)據(jù)規(guī)模、多種算法的測(cè)試?；诖诉M(jìn)行對(duì)比分析形成分析報(bào)告，有助于學(xué)生主動(dòng)發(fā)現(xiàn)和解決問(wèn)題，對(duì)其研究能力形成有針對(duì)性的引導(dǎo)。

3.2 選取具有多種形態(tài)的數(shù)據(jù)

一般數(shù)據(jù)處理問(wèn)題中的信息包括文本、圖像、聲音，這些信息的編碼可能表現(xiàn)為整型、浮點(diǎn)型，在非數(shù)值計(jì)算方面的數(shù)據(jù)則具有更為復(fù)雜的表現(xiàn)形式，如計(jì)算機(jī)人機(jī)對(duì)弈中的一次棋盤(pán)狀態(tài)。對(duì)此，可針對(duì)不同類(lèi)型的數(shù)據(jù)設(shè)置案例，具體有：①文本類(lèi)：包括中文、英文長(zhǎng)文本（如新聞文本）、短文本（如網(wǎng)絡(luò)評(píng)論性）文本;②圖像和音頻類(lèi)：包括彩色、灰度、二值圖像、各種音頻信號(hào)等;③非數(shù)值計(jì)算類(lèi)數(shù)據(jù)：如地圖、棋盤(pán)等。

上述數(shù)據(jù)具有多樣、規(guī)模各異且規(guī)模不確定的特點(diǎn)（如新聞文本的長(zhǎng)度常常是無(wú)法預(yù)知的）。在進(jìn)行案例設(shè)計(jì)時(shí)，可提供模擬（簡(jiǎn)化）數(shù)據(jù)、仿真數(shù)據(jù)、真實(shí)數(shù)據(jù)3類(lèi)。其中，真實(shí)數(shù)據(jù)可從實(shí)際工程項(xiàng)目中獲取，仿真數(shù)據(jù)可基于真實(shí)數(shù)據(jù)進(jìn)行一定的人工調(diào)整和簡(jiǎn)化。由于仿真數(shù)據(jù)和真實(shí)數(shù)據(jù)具有規(guī)模大的特點(diǎn)，難以進(jìn)行人工觀測(cè)，將促使學(xué)生運(yùn)用編程技術(shù)、算法設(shè)計(jì)方法，以尋求觀測(cè)數(shù)據(jù)的最佳途徑，從而形成啟發(fā)式的主動(dòng)學(xué)習(xí)。另外，還可要求學(xué)生自行進(jìn)行數(shù)據(jù)采集和整理，從數(shù)據(jù)采集、整理方面，對(duì)學(xué)生進(jìn)行訓(xùn)練。

3.3 選取具有多樣邏輯結(jié)構(gòu)的案例

在算法設(shè)計(jì)中，邏輯結(jié)構(gòu)通常指數(shù)據(jù)元素具有線性、樹(shù)形、圖形的邏輯關(guān)系，在大案例庫(kù)中應(yīng)包含具有這幾類(lèi)邏輯結(jié)構(gòu)的案例。當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，數(shù)據(jù)的邏輯結(jié)構(gòu)是易于觀測(cè)和判斷的;在大案例中，由于數(shù)據(jù)規(guī)模增大，數(shù)據(jù)元素間的邏輯關(guān)系變得難以感知，無(wú)法進(jìn)行主觀臆測(cè)。這一方面要求學(xué)生借助經(jīng)驗(yàn)進(jìn)行分析，例如分析認(rèn)為人機(jī)對(duì)弈的棋盤(pán)格局形成了樹(shù)形結(jié)構(gòu);另一方面，也需要通過(guò)一定的策略對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)進(jìn)行學(xué)習(xí)和挖掘，例如對(duì)數(shù)值化的圖形結(jié)構(gòu)，發(fā)現(xiàn)其是有向關(guān)系還是無(wú)向關(guān)系等。通過(guò)這種分析，也可以促使主動(dòng)學(xué)習(xí)模式的形成。

3.4 設(shè)計(jì)多元考核體系

分層大案例庫(kù)具有豐富的層次性，形成多樣化、有吸引力的實(shí)驗(yàn)內(nèi)容，可激勵(lì)學(xué)生展開(kāi)主動(dòng)學(xué)習(xí)。為便于進(jìn)行自主學(xué)習(xí)，同時(shí)對(duì)教學(xué)產(chǎn)生實(shí)時(shí)反饋，有必要設(shè)計(jì)相應(yīng)的評(píng)價(jià)機(jī)制，以保證大案例庫(kù)應(yīng)用的可行性和可操作性。針對(duì)案例庫(kù)分層、多樣的特點(diǎn)，評(píng)價(jià)體系也應(yīng)是多層次、多元化的。另外，為能有效反饋教學(xué)，評(píng)價(jià)體系應(yīng)是定量與定性評(píng)價(jià)相結(jié)合的多元系統(tǒng)，具有良好的可操作性。例如展開(kāi)形式多樣的測(cè)驗(yàn)，持續(xù)開(kāi)展算法設(shè)計(jì)系列競(jìng)賽并以此作為評(píng)價(jià)指標(biāo)等。同時(shí)也應(yīng)結(jié)合定性評(píng)價(jià)，例如以項(xiàng)目小組的方式展開(kāi)實(shí)驗(yàn)，進(jìn)行團(tuán)隊(duì)協(xié)作能力、溝通能力等評(píng)價(jià)。

我們?cè)诮虒W(xué)實(shí)踐中運(yùn)用的評(píng)價(jià)指標(biāo)，與傳統(tǒng)實(shí)驗(yàn)差別最大之處在于實(shí)驗(yàn)報(bào)告環(huán)節(jié)。由于本科教學(xué)往往更注重應(yīng)用能力培養(yǎng)，所以傳統(tǒng)的實(shí)驗(yàn)報(bào)告多以描述實(shí)驗(yàn)過(guò)程和實(shí)驗(yàn)結(jié)論為主。大案例庫(kù)的層次性及數(shù)據(jù)規(guī)模各異性，可能使實(shí)驗(yàn)結(jié)論也是各異的，這是展現(xiàn)學(xué)生分析能力的良好觀測(cè)點(diǎn)。實(shí)踐中，可啟發(fā)學(xué)生綜合運(yùn)用圖、表、偽代碼等多種手段，觀測(cè)實(shí)驗(yàn)結(jié)果，編寫(xiě)分析報(bào)告。對(duì)分析報(bào)告的質(zhì)量，尤其是分析部分的內(nèi)容進(jìn)行重點(diǎn)評(píng)價(jià)，由此將學(xué)習(xí)的注意力從單純追求實(shí)驗(yàn)結(jié)果轉(zhuǎn)移到關(guān)注實(shí)驗(yàn)過(guò)程，為培養(yǎng)研究創(chuàng)新能力打下基礎(chǔ)。

4 結(jié) 語(yǔ)

上述分層大案例庫(kù)的設(shè)計(jì)及構(gòu)建方法是結(jié)合數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)實(shí)踐提出的，是在現(xiàn)有課程建設(shè)的基礎(chǔ)上對(duì)實(shí)踐教學(xué)環(huán)節(jié)的細(xì)化和深人求精。大型、綜合型案例設(shè)計(jì)，與大數(shù)據(jù)背景下對(duì)研究型、創(chuàng)新性計(jì)算機(jī)本科人才培養(yǎng)的要求密切相關(guān)，是在計(jì)算機(jī)應(yīng)用型人才培養(yǎng)與強(qiáng)化理論研究、鼓勵(lì)思維創(chuàng)新有效結(jié)合方面進(jìn)行的一次有益探索。將大案例庫(kù)運(yùn)用于我校計(jì)算機(jī)類(lèi)各專(zhuān)業(yè)的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)，實(shí)踐中取得了顯著的效果。近3年來(lái)，我校計(jì)算機(jī)類(lèi)本科學(xué)生廣泛參與各類(lèi)學(xué)科競(jìng)賽，如CCF中文信息評(píng)測(cè)、ASC國(guó)際大學(xué)生超算競(jìng)賽、中國(guó)大數(shù)據(jù)創(chuàng)新創(chuàng)業(yè)大賽等，參與學(xué)生面逐年擴(kuò)大，這與教學(xué)中注重啟發(fā)式、研究式的學(xué)習(xí)是密切相關(guān)的，從一定程度上驗(yàn)證了數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)效果。由于數(shù)據(jù)結(jié)構(gòu)課程理論與實(shí)踐兼?zhèn)?，具有其他算法?lèi)課程的普遍特征，因此分層大案例庫(kù)的設(shè)計(jì)與構(gòu)建對(duì)其他算法設(shè)計(jì)類(lèi)課程也具有良好的借鑒意義。后續(xù)將在如何保證多種案例，尤其是較難大案例實(shí)施的有效性方面展開(kāi)進(jìn)一步的研究。

[1] 陳越, 何欽銘. 數(shù)據(jù)結(jié)構(gòu)MOOC實(shí)踐[J]. 中國(guó)大學(xué)教學(xué), 2015(12): 46-50.

[2] 霍玲玲, 王智, 孫江. 數(shù)據(jù)結(jié)構(gòu)教學(xué)方法的研究[J]. 計(jì)算機(jī)教育, 2015(2): 73-76.

[3] 陳欲強(qiáng), 周?chē)?guó)軍, 吳慶軍, 等. 非重點(diǎn)院校的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)改革[J]. 計(jì)算機(jī)教育, 2015(14): 52-55.

[4] 王丹, 付利華, 杜金蓮. 算法分析與設(shè)計(jì)課程中的”三化一體”教學(xué)方法[J]. 計(jì)算機(jī)教育, 2016(7): 120-122.

[5] 代文征, 楊勇, 蔣文娟. 數(shù)據(jù)結(jié)構(gòu)程序庫(kù)建設(shè)[J]. 計(jì)算機(jī)教育, 2016(6): 70-71.

（編輯：郭田珍）

1672-5913(2017)01-0143-04

G642

2014重慶市研究生教育教學(xué)改革項(xiàng)目（yjg143011）；2015重慶理工大學(xué)高等教育教學(xué)改革研究項(xiàng)目（2015YB23）。

盧玲，女，副教授，研究方向?yàn)闄C(jī)器學(xué)習(xí)、信息檢索、并行計(jì)算，ll@cqut．edu．cn。