基于ACM-ICPC 模式的《算法設計與分析》課程改革與實踐

韓麗霞，畢方明

（中國礦業大學計算機科學與技術學院，徐州221116）

0 引言

《算法設計與分析》課程是計算機科學專業的一門專業主干課程，該課程主要講授經典的算法（包括遞歸與分治算法、動態規劃算法、貪心算法、回溯算法、分支界限算法）的基本原理、實現方法和應用實例。通過該課程的學習，使學生熟悉算法復雜性分析理論和評價算法性能的標準，掌握基本的算法設計方法，培養學生的問題抽象和建模能力，能夠針對具體的問題能進行特性分析，進而提出有效的解決方法，為學生進一步分析和解決計算機科學與技術領域的復雜工程問題奠定良好的基礎。

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

1 教學中存在的主要問題

《算法設計與分析》是面向設計的一門課程，旨在培養學生具體問題具體分析、抽象建模和算法設計的能力。要學好這門課，學生需要以高級語言程序作為工具，具有較好的高等數學、離散數學和數據結構基礎。在教學過程中，我們發現，學生在學習該課程的過程中主要存在以下的問題：

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

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

（3）對于算法知識的靈活應用是全體學生都亟待提高的能力。對于課本上給定的問題和算法，大部分學生能夠理解和掌握求解算法的思路且編程實現，一旦問題模型發生變化，就很難獨立設計求解算法。

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

2 教學方法改革

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

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

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

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

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

通過三年的教學改革，《算法設計與分析》課程的教學質量有顯著的提高，學生學習該課程的信心和主動性都被明顯帶動加強，編程能力也有明顯的提升，教學改革初見成效。

3 實踐環節改革

在《算法設計與分析》課程新大綱中，添加了算法設計與分析實驗課程，共計16 學時。

所有實驗題目通過OJ 系統發布，學 生需要在規定的時間內把作業提交到OJ 系統中，由系統自動評判。在實踐方面的改革主要體現在如下四個方面。

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

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

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

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

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

4 結語

2018 年6 月和10 月，我院已成功舉辦了2018 年ACM 國際大學生程序設計競賽全國邀請賽（江蘇）和第43 屆ACM/ICPC 國際大學生程序設計競賽亞洲區域賽（徐州），獲得了邀請賽以及亞洲賽金獎和銀獎的好成績。基于ACM-ICPC 模式的《算法設計與分析》課程的教學改革，將課程教學與競賽有機地結合在一起，既激發了學生學習課程知識的興趣，也大幅提高了學生的分析能力、動手能力、團隊協作能力和創造能力，教學改革取得了良好的效果。