李淑琴?李寧?劉均梅

摘要：目前“算法設計與分析”課程的實驗題目主要以驗證課堂所講的理論為主，不利于培養(yǎng)學生的學習興趣、創(chuàng)新意識和能力。提出將計算機博弈競賽項目與“算法設計與分析”實驗教學題目相結合的觀點，并論述了兩者結合的意義和可行性。

關鍵詞：算法設計與分析；計算機博弈；實驗教學

作者簡介：李淑琴（1963-），女，北京人，北京信息科技大學計算機學院，教授；李寧（1964-），男，北京人，北京信息科技大學計算機學院，教授。（北京?100101）

基金項目：本文系校研究生優(yōu)質課程建設項目（項目編號：YKJ201104）、校研究生科技創(chuàng)新和實踐能力培養(yǎng)項目、校教學改革研究項目（項目編號：2010JG19）的研究成果。

中圖分類號：G642.0?????文獻標識碼：A?????文章編號：1007-0079（2012）20-0093-02

“算法設計與分析”是計算機科學的核心問題之一，是計算機科學與技術專業(yè)本科及研究生的一門重要的專業(yè)基礎課，也是計算機軟件開發(fā)人員的必修課。“算法設計與分析”課程主要針對生活中經(jīng)常遇到的實際問題，講授如何設計并實現(xiàn)計算機算法的基本原理、思想、方法與技術，從而使學生在選擇或者設計算法時可以對其進行時空耗費分析，使算法的時空復雜性最優(yōu)，進而為其編寫出高效程序、開發(fā)出優(yōu)秀軟件系統(tǒng)奠定基礎。

近年來北京信息科技大學招考的計算機專業(yè)的研究生中，本科不是計算機科學或相關專業(yè)畢業(yè)卻想攻讀計算機科學碩士學位的學生比例不斷加大，這些學生來自全國各地不同類型的學校，對應該在本科生階段掌握的計算機專業(yè)的理論深度與廣度的把握有較大差別，學生普遍編程能力較弱，遠達不到靈活運用的程度。而“算法設計與分析”課程是理論與實踐并重的課程，是一門集應用性、創(chuàng)造性及實踐性融為一體的課程。學生通過學習算法設計與分析課程可以開闊編程思路，編寫出高效程序，對學生分析問題、解決問題的能力培養(yǎng)起到非常重要的作用。

目前北京信息科技大學算法課設置為計算機專業(yè)碩士研究生的一門專業(yè)基礎課，32學時。為了提高學生的綜合能力，我們對該課程的實踐題目上下功夫，主要設計了兩個方面的題目。

第一類題目，稱為驗證型小實踐。主要是將課堂討論的理論加以驗證，一方面加深對理論的理解，另一方面鍛煉編程能力。這部分作業(yè)是實現(xiàn)算法課的最基本要求，因此要求每個學生必須獨立并保質保量地完成。

第二類題目，稱為應用型大實踐。作為研究生僅僅停留在算法的驗證上還是不夠的，要使學生能夠跟上技術發(fā)展的步伐，增強就業(yè)競爭力，就要加強創(chuàng)新能力培養(yǎng)，全面提高分析問題和解決問題的能力，提高靈活應用經(jīng)典算法和當前的新技術進行程序設計的能力。將計算機博弈競賽題目作為“算法設計與分析”課程綜合實踐題目是一個可行方案。

一、計算機博弈與“算法設計與分析”

計算機博弈，顧名思義就是讓計算機擁有人的思維去進行博弈游戲，能夠像人一樣下棋。計算機博弈是既簡單方便、經(jīng)濟實用又內涵豐富、變化無窮的思維邏輯的研究載體，它在國際上作為一個學科領域，已經(jīng)開展了半個多世紀的研究與競賽活動，經(jīng)過了波瀾壯闊的艱苦歷程。1997年5月IBM“深藍”計算機戰(zhàn)勝世界棋王卡斯帕羅夫，成為計算機博弈和人工智能的里程碑。目前，無論在國際還是國內，計算機博弈比賽每年舉辦一次，競賽項目包括六子棋、點格棋、蘇拉卡爾塔棋、亞馬遜棋、幻影圍棋、中國象棋、圍棋、九路圍棋等項目。

編寫一個好的計算機博弈程序需要涉及數(shù)據(jù)結構、編程語言、程序設計方法、軟件工程、并行計算等綜合知識，可以綜合提高學生的實踐創(chuàng)新能力。

一個完整的機器博弈系統(tǒng)主要包括棋局表示、著法生成器、搜索引擎以及評估函數(shù)四部分。

棋局表示是對比賽過程中形成的棋局的描述，涉及數(shù)據(jù)結構的選擇，其中包括棋盤、棋子、障礙、空格、棋局、走棋表示的編碼與存儲。良好的數(shù)據(jù)結構可以節(jié)省大量的存儲空間，可以提高存取的效率。為了適應博弈樹的展開與搜索，常常還要同時給出棋局的多種數(shù)據(jù)格式。如棋局狀態(tài)、棋子位置、比特棋局和比特向量，還要用到哈希變換和哈希表等。

著法生成器是在已形成的棋局下生成可行的著法，涉及對下棋規(guī)則的描述并根據(jù)規(guī)則生成所有可行著法，是搜索對象的產(chǎn)生器。

搜索引擎是如何找到最優(yōu)著法，這是計算機博弈的核心部分，是對人類思維模擬的最佳體現(xiàn)。搜索算法包括著法生成、博弈樹展開、各種剪枝搜索和各種啟發(fā)式搜索。涉及的核心問題覆蓋了常見的算法設計策略。

局面評估就是對棋局進行評估，是搜索算法的前提。棋局的靜態(tài)評估是計算機博弈的另一個難點，它不僅需要棋類對弈的基本知識，而且用到直接量化、模式量化、隨機評估、模糊評估等一系列手段。例如象棋，可以給每個棋子和棋位打分，而對于圍棋則要進行定式的抽取和模式的匹配。

以上這些問題都是算法設計課程的涉及內容，也是研究生今后研究工作涉及的主要方面之一。

（1）競賽程序的實現(xiàn)有時間、空間限制，能很好地反映算法設計與分析技巧在程序設計中的應用意義。

（2）競賽項目難度適中。計算機博弈被稱為人工智能的“果蠅”，因為它具有周期短、變化多、容易實現(xiàn)、便于檢查的特點。個把小時就可以下一盤棋，就可以對電腦的“智能”進行測試，而且可以悔棋、重試、復盤。

（3）競賽富有挑戰(zhàn)性，趣味盎然。通過編寫、調試程序，讓計算機下棋，一步步地發(fā)現(xiàn)電腦與人腦功能的差距，從而不斷提高電腦的智力水平。與所學專業(yè)知識有密切關系，有效激發(fā)學生對計算機技術的興趣。

（4）競賽要求綜合運用多種知識，有助于學生理解所學內容之間的相互關系，并創(chuàng)造性地考慮問題。

（5）競賽項目與課程題目掛鉤，一舉多得。作業(yè)完成得好的學生可以參加全國競賽，獲得獎項還能提升就業(yè)機會，同時也在一定程度上提高學校的知名度，促進良好校風的形成。

二、綜合實驗的實施與評定

實踐主要以提交課程報告形式，考核學生算法分析與設計的綜合能力。課程報告內容包括算法設計、算法實現(xiàn)、算法效率分析、程序測試等。對于小實踐作業(yè)根據(jù)學生撰寫報告內容、程序的質量綜合給分。對于大實踐作業(yè)主要通過集中匯報的方式，驗收、比較程序的運行效率。另外參考是否參加科技競賽、是否獲得獎項、是否做出不錯的科研成果以及是否發(fā)表學術論文等綜合因素給分。

目前綜合實驗作業(yè)的完成是采取3～4個學生組織成研究小組的方式進行的。分組上采取學生自由組合，選題上采用任意挑選競賽題目的方式。要求小組中每個學生都要有明確的任務分工，期末匯報自己所做的工作；每組推選一位小組長，負責整個小組的組織和協(xié)調工作。通過這種分組和匯報的形式大大提高了學生團隊合作和學術交流的能力，對他們將來從事科研工作或找工作都起到很好的幫助作用。

綜合實踐作業(yè)完成情況的評定主要由三個方面組成。一是提交課程報告。課程報告內容包括算法設計、算法實現(xiàn)、算法效率分析、程序測試等，考核學生算法分析與設計的綜合能力。二是集中匯報。每個人敘述自己所做的工作，驗收程序能否執(zhí)行、同一題目的小組之間進行比賽，比較程序的運行效率。三是提供輔助材料。參考學生是否參加科技競賽、是否獲得獎項、是否做出不錯的科研成果以及是否發(fā)表學術論文等綜合因素給分。

三、小結

近兩年來，筆者將計算機博弈競賽項目與“算法設計與分析”實驗教學題目相結合取得良好效果。作業(yè)完成得好的學生參加了兩屆全國計算機博弈大賽，取得點格棋項目組季軍、六字棋、蘇拉卡爾塔棋和亞馬遜棋二等獎的好成績。實踐表明，提出的將計算機博弈競賽和“算法設計與分析”課程教學相結合的觀點是可行的，有助于培養(yǎng)學生的學習興趣和創(chuàng)新意識，有助于學生創(chuàng)新能力、實踐能力、編程能力、自學能力、協(xié)作能力、分析和解決問題能力等多方面能力的培養(yǎng)，提高了學生在今后社會工作的素質和能力，符合21世紀計算機科學與技術專業(yè)人才培養(yǎng)的要求。

參考文獻：

[1]徐子珊.“算法設計與分析”教學中理論與技術的平衡[J].計算機教育,2008,10(2):72-73.

[2]徐心和,鄧志力,王驕,等.機器博弈研究面臨的各種挑戰(zhàn)[J].智能系統(tǒng)學報,2008,3(4):288-293.

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

[4]李淑琴,趙延,劉均梅.機器人足球仿真競賽與程序設計能力培養(yǎng)[J].計算機教育,2010,(13):31-32.

[5]張云洲,吳成東,崔建江,等.基于機器人競賽的大學生創(chuàng)新素質培養(yǎng)與實踐[J].電氣電子教學學報,2007,29(1):116-119.

（責任編輯：王祝萍）