何克晶，張星明，鄭運平

（華南理工大學(xué) 計算機科學(xué)與工程學(xué)院，廣東 廣州 510641）

算法設(shè)計與分析課程全方位實踐教學(xué)改革探索

何克晶，張星明，鄭運平

（華南理工大學(xué) 計算機科學(xué)與工程學(xué)院，廣東 廣州 510641）

針對算法設(shè)計與分析課程在培養(yǎng)學(xué)生實踐能力、問題求解能力以及創(chuàng)新性方面的不足，研究國外計算機學(xué)科頂尖大學(xué)的算法設(shè)計與分析課程開設(shè)情況，分析課程目前的教學(xué)改革現(xiàn)狀，提出算法設(shè)計與分析課程的全方位實踐教學(xué)改革，從基于翻轉(zhuǎn)課堂的研討式教學(xué)結(jié)合的理論教學(xué)、ACM-ICPC競賽和在線評測系統(tǒng)結(jié)合的實驗教學(xué)、基于在線系統(tǒng)的課后作業(yè)管理、助教主導(dǎo)的課后討論以及多樣化的考核方式等方面闡述具體實施過程。

算法設(shè)計與分析；教學(xué)改革；研討式教學(xué)；ACM-ICPC競賽；考核方式多樣化

0 引 言

隨著社會對計算機技術(shù)需求的不斷增加，用計算機解決實際問題的專業(yè)人才培養(yǎng)成為計算機相關(guān)學(xué)科教育的根本目的。算法設(shè)計與分析課程（以下簡稱“算法課程”）是計算機專業(yè)的專業(yè)基礎(chǔ)課，在國內(nèi)外各大學(xué)計算機專業(yè)課中處于核心地位。在國外計算機學(xué)科最負(fù)盛名的3所大學(xué)中，卡內(nèi)基梅隆大學(xué)將“Algorithm Design and Analysis”列為必修課程[1]，斯坦福大學(xué)和麻省理工學(xué)院分別將“Design and Analysis of Algorithms”列為核心課程和先導(dǎo)課程[23]。算法設(shè)計與分析課程的主要目的是通過系統(tǒng)地學(xué)習(xí)算法設(shè)計的主要思想，培養(yǎng)算法設(shè)計和分析的能力，為學(xué)生利用算法解決計算機及其他學(xué)科實際問題奠定基礎(chǔ)。

在進入算法課程學(xué)習(xí)之前，一般要求學(xué)生具有離散數(shù)學(xué)、高級語言程序設(shè)計（C++或Java）以及數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識。在高級語言程序設(shè)計和數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)過程中，學(xué)生所接觸的是相對基礎(chǔ)的概念和局部的知識點。算法課程要求學(xué)生利用之前學(xué)到的知識，用全局思想對實際問題進行分析，并進行具體的算法實現(xiàn)，真正解決實際問題。

1 傳統(tǒng)算法課程教學(xué)的現(xiàn)狀及問題

算法課程具有理論與實踐緊密結(jié)合、相輔相成的特點，所以除了基礎(chǔ)理論性的課程教學(xué)外，還要特別注重算法設(shè)計和實踐環(huán)節(jié)。只有通過實踐環(huán)節(jié)加深鞏固課堂所學(xué)，才能通過此課程真正掌握解決實際問題的能力。

但傳統(tǒng)的算法課程教學(xué)普遍存在實踐教學(xué)不夠深入全面的問題，具體體現(xiàn)在以下幾方面。

（1）以理論為主，實踐不足

學(xué)生課后很少做練習(xí)和深入思考，大學(xué)4年下來，學(xué)生的編程量少，寫程序不熟練，碰到實際問題有種無從下手的感覺，問題分析和解決能力離社會的要求還有一定的差距。很多學(xué)生雖然考分高，但編程能力還比較弱，對于書上講的知識也是一知半解。

（2）缺乏平時考核、測評

目前絕大多數(shù)課程的考核方式是平時成績和實驗占30%～40%，期末筆試成績占60%～70%。課程的考核還是以筆試為主，操作性比較強的編程類題目所占比重比較少，這使得學(xué)生偏向于只掌握幾個考試重點。這種狀況實際上是過于強調(diào)結(jié)果而忽視過程，并非真正的素質(zhì)教育。

在國外大學(xué)的算法課程中，平時的考核和測評往往多于期末考試成績。以2016年春季課程為例，在所調(diào)研的3所頂尖大學(xué)中，期末考試成績只占30%左右，課后作業(yè)和平時成績對總成績起主要作用（見表1）。

表1 國外頂尖大學(xué)計算機學(xué)科算法課程考核方式

（3）缺乏綜合性的實踐

平時的作業(yè)題多來自于課本上的課后習(xí)題，而課后習(xí)題往往能從課本上找到現(xiàn)成的答案。這種方式不利于考查學(xué)生解決實際問題的能力，因為課本的課后習(xí)題本身就不是“實際問題”，往往針對的是課程某個知識點，數(shù)據(jù)結(jié)構(gòu)、圖論、算法設(shè)計等綜合知識沒有得到很好的串聯(lián)，而且題目與實際生活聯(lián)系不緊密，導(dǎo)致學(xué)生覺得枯燥無味。

在現(xiàn)有少量的實驗課中，缺少設(shè)計性和綜合性實驗，學(xué)生面對題目往往是上網(wǎng)或查書找答案，甚至有少部分學(xué)生會直接抄襲其他同學(xué)的答案，或者有些“精明”一點的同學(xué)會對程序中的變量名或者提示性的輸出語句進行替換式的修改，完全缺少創(chuàng)造性思維的培養(yǎng)。最后導(dǎo)致實驗變成打字和調(diào)試程序的過程，達不到預(yù)期的教學(xué)目標(biāo)。

在上述國外3所大學(xué)中，均要求完成7個左右綜合性的課后作業(yè)，配備了8～13名助教，并每周進行一次分組的課程討論。

2 現(xiàn)有的改革模式及其分析

為了解決測試及實驗內(nèi)容與實際操作能力脫鉤的問題，并方便教師檢查學(xué)生程序，包括華南理工大學(xué)在內(nèi)的國內(nèi)部分高校采用與ACMICPC（ACM 國際大學(xué)生程序設(shè)計競賽）、OJ（在線評測）系統(tǒng)結(jié)合的方式來提升學(xué)生的編程能力，自動檢驗程序的正確性、算法效率和內(nèi)存使用情況等[48]。ACM-ICPC是由ACM（美國計算機協(xié)會）主辦的程序設(shè)計比賽，至2016年已舉辦40屆，是全世界最具影響力的計算機競賽，被譽為計算機界的“奧林匹克”。OJ系統(tǒng)可完成程序設(shè)計競賽、課程實驗、平時練習(xí)等多項任務(wù)。

ACM-ICPC采用團隊參賽的形式，在不能聯(lián)網(wǎng)查詢資料的情況下，需要分析題目內(nèi)容，設(shè)計算法并實現(xiàn)。ACM-ICPC的競賽時間為5個小時，一般包含6～13道題目，程序運行不能超過允許的內(nèi)存數(shù)量和執(zhí)行時間。與傳統(tǒng)競賽相比，ACM-ICPC考查的是學(xué)生在限定的時間內(nèi)團隊合作解決問題的能力，是對學(xué)生編程能力、心理素質(zhì)、團隊協(xié)作能力的一個綜合考驗。根據(jù)往年經(jīng)驗，極少有團隊能在限定的時間內(nèi)完成所有題目。題目內(nèi)容只是問題陳述，且學(xué)生得到的只是測試數(shù)據(jù)實例，無法獲得裁判的檢驗數(shù)據(jù)和標(biāo)準(zhǔn)。而若提交的程序沒有通過檢驗，則會受到加時懲罰。所以對問題進行難度分級、推斷出要求、設(shè)計并實現(xiàn)算法就變得非常關(guān)鍵。面對實際的問題，能否在限定的時間內(nèi)求解，進行針對性的算法設(shè)計和分析尤為重要，因為算法課程與ACM-ICPC的目標(biāo)都是培養(yǎng)學(xué)生解決問題的實踐能力，兩者結(jié)合必然會取得雙贏的結(jié)果。

通過分組的方式進行競賽和教學(xué)的結(jié)合，學(xué)生之間能進行充分地合作交流并分享經(jīng)驗，有助于提高學(xué)生的團隊協(xié)作精神和解決問題的能力。通過將算法課程與ACM-ICPC結(jié)合，能提高學(xué)生的編程水平和實踐能力，同時為ACM-ICPC儲備大量優(yōu)秀的競賽隊員。在之前的教學(xué)改革中，華南理工大學(xué)已將競賽模式運用到算法課程的教學(xué)過程中，提出了一種基于ACM-ICPC的算法課程教學(xué)改革模式。該模式培養(yǎng)了學(xué)生參加ACM-ICPC的興趣，極大地提高了學(xué)生學(xué)習(xí)的主動性和積極性，加強了對團隊合作精神和創(chuàng)新能力的培養(yǎng)[9]。但實際算法課程也有與ACMICPC不同之處，主要包括：①學(xué)生水平差別較大；②斷網(wǎng)與不斷網(wǎng)的選擇；③如何在題庫中創(chuàng)建眾多新的題目。

在真正的競賽中，每個題目允許的求解時間很短。但實際教學(xué)中，學(xué)生的水平相差較大，要充分考慮優(yōu)秀學(xué)生和普通學(xué)生的不同需求[10]，且實際教學(xué)中的學(xué)生平均水平比ACM-ICPC隊員的水平要弱一些。如果嚴(yán)格按照ACM-ICPC規(guī)定禁止使用網(wǎng)絡(luò)，并限定時間，由于在線評測系統(tǒng)只檢驗最終結(jié)果，會造成眾多學(xué)生許多題目都是零分，某種程度上會打擊學(xué)生的積極性。如果允許學(xué)生使用網(wǎng)絡(luò)，在互聯(lián)網(wǎng)異常發(fā)達的情況下，大多數(shù)題庫里的題目都能在互聯(lián)網(wǎng)上找到答案。而且，如何防止學(xué)生之間互相抄襲和修改借鑒也就成了另一個不好解決的問題。2014年春季，我們在課程實驗中加入了一個在網(wǎng)上找不到答案的題目，在允許使用網(wǎng)絡(luò)，限定1個下午實驗時間的情況下，正確完成的同學(xué)不到20%。2015年春季，第39屆ACM-ICPC全球總決賽剛結(jié)束，我們馬上將全球總決賽中較難的一道題（題目K）加入了實驗。此題判定為較難的依據(jù)是因為在總決賽中此題一共只被提交了11次答案，最后只有2個隊成功求解。同樣允許使用網(wǎng)絡(luò)，限定1個下午實驗時間的情況下，結(jié)果沒有同學(xué)能求解此題。所以在允許使用網(wǎng)絡(luò)的情況下，某題目有多少同學(xué)能做出來很大程度上取決于網(wǎng)絡(luò)上是否容易找到類似的解決方案。

所以，在充分考慮學(xué)生個體之間的巨大差異性、網(wǎng)絡(luò)資源的豐富性、教學(xué)與競賽的異同之后，如何結(jié)合ACM-ICPC進行較全面的算法課程實踐教學(xué)改革就變成了一個值得深思的問題。

3 全方位實踐教學(xué)改革

3.1 理論教學(xué)——課堂講授與基于翻轉(zhuǎn)課堂的研討式教學(xué)結(jié)合

采用課堂講授與研討式課堂討論結(jié)合的理論教學(xué)形式。教學(xué)內(nèi)容以教材為基礎(chǔ)，以具體的問題和應(yīng)用為驅(qū)動，引導(dǎo)學(xué)生深入分析問題，并設(shè)計優(yōu)秀的算法，培養(yǎng)學(xué)生的創(chuàng)新能力。

除課堂講授外，部分學(xué)時基于翻轉(zhuǎn)課堂的模式進行研討式教學(xué)。給學(xué)生提供主題、視頻、在線課程及相關(guān)資料，讓學(xué)生組成小組，根據(jù)具體的問題進行調(diào)研和討論，教師進行啟發(fā)式引導(dǎo)。通過讓學(xué)生進行研討匯報，實踐能力得到提升，表達能力得到鍛煉，思維更加縝密，同時團隊協(xié)作精神得到加強。《國家中長期教育改革和發(fā)展規(guī)劃綱要（2010—2020年）》對創(chuàng)新人才培養(yǎng)也要求注重學(xué)思結(jié)合，通過研討式教學(xué)幫助學(xué)生掌握學(xué)習(xí)的能力[11]。通過在理論教學(xué)中推動學(xué)生課后的實踐活動，可以與傳統(tǒng)的講授型教學(xué)模式進行良好互補。

3.2 實驗教學(xué)——與ACM-ICPC和OJ系統(tǒng)結(jié)合

作為全方位實踐教學(xué)體系的一部分，學(xué)科競賽對提高學(xué)習(xí)興趣、激發(fā)學(xué)生潛能發(fā)揮著重要作用。在競賽和教學(xué)結(jié)合方面，將實驗環(huán)節(jié)與ACM-ICPC和OJ系統(tǒng)結(jié)合，并鼓勵學(xué)生參加其他相關(guān)競賽，如數(shù)學(xué)建模及各大IT公司舉辦的學(xué)科競賽。為了充分全面地考核不同層次的學(xué)生，題庫中除了常規(guī)OJ系統(tǒng)頻繁見到的題目之外，必須得有一定的新題。若新題能全面覆蓋不同的知識點，且難易俱備，則能對學(xué)生進行更全面的鍛煉和考核。通過與OJ系統(tǒng)結(jié)合，能減少教師批改編程題的工作量。

要真正培養(yǎng)學(xué)生的算法設(shè)計、分析和創(chuàng)新能力，只依靠課內(nèi)學(xué)時是遠(yuǎn)遠(yuǎn)不夠的。除了實驗學(xué)時之外，鼓勵學(xué)生課后參與ACM-ICPC訓(xùn)練或興趣小組，或者利用空余時間到OJ系統(tǒng)上通過做題進行鍛煉。還可利用技術(shù)講座和學(xué)生項目實踐，推動學(xué)生對技術(shù)前沿的掌握，學(xué)習(xí)前沿先進技術(shù)和創(chuàng)新理念，讓學(xué)生了解實際問題，有重點地培養(yǎng)學(xué)生的創(chuàng)新意識。

3.3 課后作業(yè)——利用在線系統(tǒng)

算法課程的目的是鍛煉學(xué)生的算法思維，并借助編程的手段，解決實際問題。現(xiàn)實中的問題很可能是未出現(xiàn)過的新問題，所以必須給予學(xué)生適當(dāng)?shù)乃伎紩r間，借助已有知識，循序漸進解決問題。因課時限制，無論是課堂教學(xué)還是實驗，都沒有條件鍛煉學(xué)生解決實際復(fù)雜問題的能力。麻省理工學(xué)院的課后作業(yè)采用問題集（Problem Set）的形式，Erik Demaine教授談到課后作業(yè)時表示：“在一個時間受限的測試中，很難期望學(xué)生具有創(chuàng)新性……所以我們用來測試的問題相對簡單，學(xué)生只要一個簡單的想法并且對相關(guān)的知識比較熟練，就可以較快地完成測試。而課后作業(yè)則更容易讓學(xué)生發(fā)揮創(chuàng)新能力，學(xué)生能有更多的時間仔細(xì)思考這些問題。因為有些問題對某些學(xué)生而言可能相對容易，而對其他學(xué)生而言較難，所以學(xué)生有一周左右的時間進行思考。并且可以相互討論，協(xié)作完成……2014年的時候，我們希望通過測試的方式來準(zhǔn)確評價學(xué)生應(yīng)用算法技術(shù)來設(shè)計一個新算法的創(chuàng)新能力，而2015年我們已經(jīng)不再這樣做，因為我們并不清楚這種評價方式的正確性……”[12]。

因此，課后作業(yè)或者問題集的形式，作為課堂以及實驗教學(xué)的補充，可由易到難逐步培養(yǎng)學(xué)生解決復(fù)雜問題的能力。學(xué)生可以自愿選擇在開放的實驗室等地點完成作業(yè)?？筛鶕?jù)作業(yè)的實際情況要求學(xué)生獨立完成或組隊完成。為減輕工作量，并綜合考慮存檔的需求，可利用智能化的評測系統(tǒng)，要求學(xué)生在規(guī)定的時間上傳課后作業(yè)的電子文檔或掃描件。課后作業(yè)也可與課后討論結(jié)合。在時間和條件允許的情況下，要求學(xué)生在課堂研討或課后討論時，向任課教師或助教對作業(yè)完成過程進行闡述。

3.4 課后討論——發(fā)揮助教的作用

因為課時限制，以及教學(xué)班的學(xué)生數(shù)目往往較多，一些學(xué)生在課堂上并沒有機會充分地參與討論和交流。因此可以將課后討論作為補充，討論分成小組形式。國外的算法課程往往安排了多個助教和多次課后討論（見表1）。根據(jù)實際情況，建議助教組織、管理和安排一些課后討論，討論內(nèi)容是對所學(xué)課堂知識的擴展。

3.5 考核方式——多樣化，結(jié)合在線考試

大多數(shù)ACM-ICPC和OJ系統(tǒng)只能考查編程試題，并且存在結(jié)果錯誤即為零分的情況。而實際課程考試中，為了更全面考核學(xué)生的掌握程度，可能需要結(jié)合選擇、填空、問答、計算及編程等題型，并且課程教學(xué)及考核與競賽存在一定區(qū)別，單純的結(jié)果錯誤即為零分的方式也值得商榷。結(jié)合高校實際情況，建立自動化的在線考試系統(tǒng)，有助于教學(xué)過程中對學(xué)生的掌握程度進行多次考核，且降低任課教師出題和改卷的工作量?？紤]到實際情況，在線考試應(yīng)對編程題、選擇題、填空題、程序理解和改錯題等均有較好的支持。

為全面考核學(xué)生學(xué)習(xí)過程，結(jié)合學(xué)校和學(xué)院的相關(guān)政策，在條件允許的情況下，可選擇綜合考慮出勤情況、上課回答問題和討論情況、課后討論情況、課后作業(yè)情況、競賽與教學(xué)結(jié)合的編程實驗成績、平時測評成績和期末考試等方面，對學(xué)生進行全面考核。

通過以上全方位實踐教學(xué)改革措施，可督促學(xué)生邊實踐邊學(xué)習(xí)，達到“以用促學(xué)，以學(xué)致用，學(xué)用結(jié)合”的目的。教學(xué)過程能激發(fā)學(xué)生的學(xué)習(xí)興趣，學(xué)生作為實際問題的解決者，對算法設(shè)計和分析不僅有較濃厚的興趣，而且能提出更符合學(xué)生思維習(xí)慣的創(chuàng)新算法。注重實踐性的算法課程能調(diào)動學(xué)生的主觀能動性，通過在課程的實踐教學(xué)環(huán)節(jié)中鍛煉解決實際問題的動手能力，同時為學(xué)生未來的求職和科研打下基礎(chǔ)。

4 結(jié) 語

經(jīng)過一段時間的教學(xué)改革，目前已初見成效。通過在算法課程中全方位推進實踐教學(xué)改革，學(xué)生解決實際問題的能力得到了培養(yǎng)，實踐能力得到了提高。學(xué)生能從實際問題出發(fā)，根據(jù)理論知識，進行算法的設(shè)計分析并實現(xiàn)，學(xué)以致用。在課程教學(xué)中，讓學(xué)生接受競賽式的思維訓(xùn)練，培養(yǎng)了學(xué)生對算法設(shè)計和ACM-ICPC的興趣。近年來，華南理工大學(xué)學(xué)生參加ACM-ICPC也取得了較好成績，2013—2016年連續(xù)4年進入全球總決賽，但要全面持續(xù)地深入改革，仍然任重而道遠(yuǎn)，主要在于深入改革需要投入大量精力和資源。比如，國外的課后作業(yè)均為綜合性的，在網(wǎng)上難以直接找到答案，且每年的課后作業(yè)都不同。課后討論和題庫建設(shè)同樣需要教師和助教投入大量的時間。今后，將進一步深入貫徹算法課程的全方位實踐教學(xué)模式，逐步培養(yǎng)學(xué)生的創(chuàng)新意識，提高其實踐能力和團隊協(xié)作能力。

[1] Carnegie Mellon University.15-451/651:Algorithms[EB/OL]. [2016-05-30]. http://www.cs.cmu.edu/～15451/.

[2] Stanford University. CS 161: Design and Analysis of Algorithms(Fall 2016) [EB/OL]. [2016-05-30].http://cs161.stanford.edu/.

[3] Massachusetts Institute of Technology. 6.046/18.410 Design and Analysis of Algorithms [EB/OL]. [2016-05-30].https://stellar.mit. edu/S/course/6/sp16/6.046/index.html.

[4] 鄭運平.“算法設(shè)計與分析”的教學(xué)模式探索[J]. 華南高等工程教育研究, 2012(2): 21-25.

[5] 李華, 趙建平, 李奇, 等. 基于ACM-ICPC的算法設(shè)計與分析課程改革[J]. 計算機教育, 2013(7): 88-91.

[6] 劉曉璐. 基于ACM-ICPC模式的算法分析與設(shè)計課程的建設(shè)與實踐[J]. 中國教育信息化, 2015(10): 65-67.

[7] 楊春明, 陳念年. 基于競賽模式的“算法分析與設(shè)計”教學(xué)探索與實踐[J]. 計算機教育, 2009(20): 146-147, 105.

[8] 吳英杰, 王一蕾, 傅仰耿, 等. 依托程序設(shè)計競賽,推進“算法與數(shù)據(jù)結(jié)構(gòu)”課程實踐教學(xué)改革[J]. 計算機教育, 2010(4): 53-55.

[9] 張星明, 鄭運平. 計算機創(chuàng)新人才培養(yǎng)模式的探索[J]. 計算機教育, 2013(18): 16-19, 40.

[10] 陳翔. 面向不同層次學(xué)生的算法設(shè)計與分析課程教學(xué)改革探索[J]. 計算機教育, 2014(18): 19-22, 26.

[11] 中華人民共和國教育部. 國家中長期教育改革和發(fā)展規(guī)劃綱要（2010－2020年）[EB/OL]. [2016-05-30]. http://www.moe. edu.cn/publicfiles/business/htmlfiles/moe/moe_838/201008/93704.html.

[12] Massachusetts Institute of Technology. Design and Analysis of Algorithms[EB/OL].[2016-05-30]. http://ocw.mit.edu/courses/ electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/.

（編輯： 史志偉 ）

1672-5913(2017)02-0045-05

G642

廣東省本科高校教學(xué)質(zhì)量與教學(xué)改革工程（粵教高函〔2014〕97 號，粵教高函〔2015〕173 號）；2014年華南理工大學(xué)校級教研教改項目“網(wǎng)絡(luò)工程專業(yè)實踐教學(xué)的研究與探索”；2014年華南理工大學(xué)探索性實驗教學(xué)項目“基于MPI/OpenMP混合編程的大規(guī)模多體問題仿真”。

何克晶，男，教授，研究方向為高性能計算、云計算與大數(shù)據(jù)，kjhe@scut.edu.cn。