基于ACM-ICPC 模式的《算法設(shè)計(jì)與分析》課程改革與實(shí)踐

韓麗霞，畢方明

（中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，徐州221116）

0 引言

《算法設(shè)計(jì)與分析》課程是計(jì)算機(jī)科學(xué)專業(yè)的一門專業(yè)主干課程，該課程主要講授經(jīng)典的算法（包括遞歸與分治算法、動態(tài)規(guī)劃算法、貪心算法、回溯算法、分支界限算法）的基本原理、實(shí)現(xiàn)方法和應(yīng)用實(shí)例。通過該課程的學(xué)習(xí)，使學(xué)生熟悉算法復(fù)雜性分析理論和評價算法性能的標(biāo)準(zhǔn)，掌握基本的算法設(shè)計(jì)方法，培養(yǎng)學(xué)生的問題抽象和建模能力，能夠針對具體的問題能進(jìn)行特性分析，進(jìn)而提出有效的解決方法，為學(xué)生進(jìn)一步分析和解決計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域的復(fù)雜工程問題奠定良好的基礎(chǔ)。

ACM 國際大學(xué)生程序設(shè)計(jì)競賽（簡稱ACM-ICPC）是由國際計(jì)算機(jī)協(xié)會（ACM）主辦的最具影響力的大學(xué)生程序設(shè)計(jì)競賽，被譽(yù)為計(jì)算機(jī)領(lǐng)域的奧林匹克競賽。其中，ACM 對算法知識點(diǎn)的考核包括分治算法、動態(tài)規(guī)劃、貪心算法、排序算法、回溯算法等，競賽的目的是使得大學(xué)生能夠通過計(jì)算機(jī)來充分展示其分析問題和解決問題的能力以及創(chuàng)新能力的培養(yǎng)。由此可見，《算法設(shè)計(jì)與分析》課程與ACM-ICPC 的目標(biāo)是不謀而合的，將ACM-ICPC 競賽模式結(jié)合到課程教學(xué)中，能有效地加深學(xué)生對知識的理解程度，增強(qiáng)學(xué)生分析問題和解決問題的能力，有利于激發(fā)學(xué)生學(xué)習(xí)和競賽的熱情。同時，基于ACM-ICPC 的課程改革對于高質(zhì)量人才的培養(yǎng)具有重要的現(xiàn)實(shí)意義。

1 教學(xué)中存在的主要問題

《算法設(shè)計(jì)與分析》是面向設(shè)計(jì)的一門課程，旨在培養(yǎng)學(xué)生具體問題具體分析、抽象建模和算法設(shè)計(jì)的能力。要學(xué)好這門課，學(xué)生需要以高級語言程序作為工具，具有較好的高等數(shù)學(xué)、離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。在教學(xué)過程中，我們發(fā)現(xiàn)，學(xué)生在學(xué)習(xí)該課程的過程中主要存在以下的問題：

（1）對于算法的基本理論知識，部分學(xué)生感覺枯燥、乏味，導(dǎo)致學(xué)習(xí)的興趣不大；有些學(xué)生甚至出現(xiàn)“畏學(xué)”“厭學(xué)”的情緒，覺得自己“學(xué)不會”、“學(xué)不好”，造成被動學(xué)習(xí)、消極學(xué)習(xí)的局面；

（2）理論與實(shí)踐脫節(jié)的問題在課程學(xué)習(xí)中是比較突出的問題，很多學(xué)生學(xué)而不能用。對于某個具體問題，能夠設(shè)計(jì)求解的算法，但如何考慮問題操作對象的存儲，編寫代碼存在不小的困難；

（3）對于算法知識的靈活應(yīng)用是全體學(xué)生都亟待提高的能力。對于課本上給定的問題和算法，大部分學(xué)生能夠理解和掌握求解算法的思路且編程實(shí)現(xiàn)，一旦問題模型發(fā)生變化，就很難獨(dú)立設(shè)計(jì)求解算法。

綜上所述，如何上好《算法設(shè)計(jì)與分析》這門課，給任課教師帶來了巨大的挑戰(zhàn)和考驗(yàn)，基于ACM-ICPC模式的教學(xué)改革將為《算法設(shè)計(jì)與分析》注入一針強(qiáng)心劑，有效地促進(jìn)教學(xué)效果和實(shí)踐水平的提高。

2 教學(xué)方法改革

針對教學(xué)過程中的諸多問題，課題組老師通過看視頻、研討會等手段對教學(xué)方法進(jìn)行了系列調(diào)整，大體總結(jié)如下：

（1）對于《算法設(shè)計(jì)與分析》課程的幾類算法，采用貼近生活的實(shí)例進(jìn)行講解，引導(dǎo)學(xué)生深入理解各類算法的基本思想、適用條件和求解步驟，從而消除學(xué)生對該課程的距離感和畏懼心，激發(fā)學(xué)生的積極性和熱情。例如在講解貪心算法時，選擇日常生活中“售貨員找零錢”作為引入，該問題尋找“找出的零錢張數(shù)最少”的找零錢方式。日常生活中，學(xué)生對該問題耳熟能詳，非常輕松就掌握了貪心算法的基本思想和基本步驟，無形中增強(qiáng)了學(xué)生學(xué)習(xí)該課程的興趣，消除了學(xué)生的“畏學(xué)之心”。

（2）在課堂教學(xué)過程中，以高級語言作為工具，采用離散數(shù)學(xué)進(jìn)行模型抽象，根據(jù)算法的思想，選擇有效的數(shù)據(jù)存儲方式，從而實(shí)現(xiàn)高級語言、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析的無縫銜接，從而將理論與實(shí)踐有機(jī)結(jié)合。算法問題需要嚴(yán)謹(jǐn)?shù)某绦蛟u判系統(tǒng)，將ACM-ICPC 的在線判別系統(tǒng)OJ 引入到《算法設(shè)計(jì)與分析》的課堂教學(xué)中來，布置OJ 系統(tǒng)在線作業(yè)，編程實(shí)現(xiàn)各類算法的經(jīng)典ACM-ICPC 題目。這樣做，將《算法設(shè)計(jì)與分析》的理論與實(shí)踐有機(jī)統(tǒng)一。同時，對每次作業(yè)設(shè)置排行榜功能，學(xué)生通過排行榜可以及時查看其他學(xué)生的做題情況，進(jìn)一步激勵了學(xué)生學(xué)習(xí)的積極性和熱情。

（3）對各類算法的基本思想、基本步驟講解清楚外，需要加強(qiáng)算法之間的比較，幫助學(xué)生把所學(xué)的知識融會貫通，加深理解的程度。為此，可以采用討論課的形式，讓學(xué)生們以小組為單位，討論回溯法和分支限界法，說明它們之間的相同點(diǎn)和不同點(diǎn)，對于同一個問題如何應(yīng)用，分析它們的時間復(fù)雜性等，將學(xué)生的被動學(xué)生改為主動學(xué)習(xí)，讓學(xué)生真正參與到課堂中來，成為課堂教學(xué)的主體。這也符合ACM 比賽中強(qiáng)調(diào)的最優(yōu)、最快的宗旨。

（4）在教學(xué)方式上，主要采用啟發(fā)式教學(xué)，引入ACM-ICPC 中“一題多解”的問題，鼓勵學(xué)生“分析問題-抽象建模-數(shù)據(jù)存儲-算法設(shè)計(jì)-復(fù)雜性分析”，進(jìn)而提出改進(jìn)的算法，達(dá)到靈活運(yùn)用各類算法，“一題多解”的教學(xué)目的。通過這些訓(xùn)練，可以提高學(xué)生靈活應(yīng)用算法的能力，培養(yǎng)學(xué)生的創(chuàng)新思維，也有助于培養(yǎng)學(xué)生之間的協(xié)作意識，增強(qiáng)學(xué)生觸類旁通、舉一反三的能力。

通過三年的教學(xué)改革，《算法設(shè)計(jì)與分析》課程的教學(xué)質(zhì)量有顯著的提高，學(xué)生學(xué)習(xí)該課程的信心和主動性都被明顯帶動加強(qiáng)，編程能力也有明顯的提升，教學(xué)改革初見成效。

3 實(shí)踐環(huán)節(jié)改革

在《算法設(shè)計(jì)與分析》課程新大綱中，添加了算法設(shè)計(jì)與分析實(shí)驗(yàn)課程，共計(jì)16 學(xué)時。

所有實(shí)驗(yàn)題目通過OJ 系統(tǒng)發(fā)布，學(xué) 生需要在規(guī)定的時間內(nèi)把作業(yè)提交到OJ 系統(tǒng)中，由系統(tǒng)自動評判。在實(shí)踐方面的改革主要體現(xiàn)在如下四個方面。

（1）從理論課中，選取各類算法中具有代表性的問題進(jìn)行驗(yàn)證性實(shí)驗(yàn)，并進(jìn)行初步的拓展，這部分實(shí)驗(yàn)內(nèi)容由每個學(xué)生獨(dú)立完成，OJ 系統(tǒng)會列出每個學(xué)生運(yùn)行程序的相關(guān)信息。這樣做，將理論教學(xué)與實(shí)踐相結(jié)合，既可以加深學(xué)生對基本理論知識的理解，也可以有效地提高學(xué)生編程的能力，也有利于教學(xué)效率和教學(xué)質(zhì)量的提高。

（2）參考ACM-ICPC 的三人小組制，將學(xué)生分為若干小組，將競賽的算法題目引入課程，對課程內(nèi)容進(jìn)行基本的引申，與實(shí)踐應(yīng)用聯(lián)系起來。通過小組討論、分析、解決問題的形式，充分調(diào)動學(xué)生的積極性和參與性，鍛煉學(xué)生獨(dú)立思考的能力。此外，通過一題多解和對復(fù)雜性的分析，起到舉一反三、觸類旁通的作用，充分展現(xiàn)了學(xué)生的思維活力，突出團(tuán)隊(duì)合作精神，也有助于學(xué)生結(jié)合實(shí)際進(jìn)行具體的應(yīng)用

（3）實(shí)驗(yàn)課中設(shè)置提高題目，采用ACM-ICPC 中部分具有挑戰(zhàn)性的算法題目作為加分題，鼓勵學(xué)生設(shè)計(jì)更優(yōu)、更快的算法進(jìn)行求解。ACM-ICPC 中的題目都是原創(chuàng)性題目，需要學(xué)生綜合運(yùn)用所學(xué)的知識，不斷通過編寫程序來進(jìn)行相應(yīng)的建模和算法設(shè)計(jì)。既具有趣味性，又可以極大地激發(fā)學(xué)生自主學(xué)習(xí)的能力以及不斷進(jìn)行探索的精神。同時，提高題目的設(shè)置也有利于高質(zhì)量人才的培養(yǎng)和選拔，為ACM-ICPC 隊(duì)員的挑選提供了可靠的依據(jù)。

（4）將OJ 系統(tǒng)作業(yè)作為實(shí)驗(yàn)教學(xué)、檢驗(yàn)學(xué)生成績的主要手段。OJ 系統(tǒng)對學(xué)生完成的題目的數(shù)量、時間等均有統(tǒng)計(jì)，教師根據(jù)系統(tǒng)信息給出的實(shí)驗(yàn)平時成績和測試成績，最終給出《算法設(shè)計(jì)與分析》的實(shí)驗(yàn)成績。值得一提的是，OJ 系統(tǒng)考慮到算法的運(yùn)行效率分析、做題數(shù)量和完成時間，是比較公平的考核方式。

通過教學(xué)改革，將課堂講授與實(shí)驗(yàn)討論有機(jī)結(jié)合、競賽與測試相結(jié)合，切實(shí)給學(xué)生提供了一個理論與實(shí)踐的學(xué)習(xí)與鍛煉平臺，既加深了學(xué)生對理論課程的理解，也有效鍛煉了學(xué)生的動手能力。從OJ 系統(tǒng)期末測試的成績也可以看出，學(xué)生能運(yùn)用所學(xué)的理論知識，對問題進(jìn)行分析和算法設(shè)計(jì)，且對算法的復(fù)雜性分析能力也有顯著的提高。通過實(shí)踐教學(xué)改革，學(xué)生能夠得到充分的實(shí)踐鍛煉，對算法設(shè)計(jì)方法的應(yīng)用掌握的更牢固，也進(jìn)一步培養(yǎng)了學(xué)生求真務(wù)實(shí)的科學(xué)態(tài)度。

4 結(jié)語

2018 年6 月和10 月，我院已成功舉辦了2018 年ACM 國際大學(xué)生程序設(shè)計(jì)競賽全國邀請賽（江蘇）和第43 屆ACM/ICPC 國際大學(xué)生程序設(shè)計(jì)競賽亞洲區(qū)域賽（徐州），獲得了邀請賽以及亞洲賽金獎和銀獎的好成績?；贏CM-ICPC 模式的《算法設(shè)計(jì)與分析》課程的教學(xué)改革，將課程教學(xué)與競賽有機(jī)地結(jié)合在一起，既激發(fā)了學(xué)生學(xué)習(xí)課程知識的興趣，也大幅提高了學(xué)生的分析能力、動手能力、團(tuán)隊(duì)協(xié)作能力和創(chuàng)造能力，教學(xué)改革取得了良好的效果。