從ACM/ICPC看計(jì)算機(jī)算法設(shè)計(jì)教學(xué)改革

李俊芳

（集寧師范學(xué)院 計(jì)算機(jī)系，內(nèi)蒙古 烏蘭察布 012000）

互聯(lián)網(wǎng)時(shí)代，對(duì)信息的關(guān)注與把握日益滲透在人們的日常生活中，人們?cè)絹?lái)越發(fā)現(xiàn)自己無(wú)法脫離這種信息化的生活方式，人們的生活依賴(lài)于信息的收集、處理以及傳送.

很多時(shí)候，我們需要將自己所接收的信息進(jìn)一步處理、分析，獲取信息并對(duì)它進(jìn)行加工處理，使之成為有用信息并發(fā)布出去的過(guò)程，稱(chēng)為信息處理.信息處理的過(guò)程主要包括信息的獲取、儲(chǔ)存、加工、發(fā)布和表示.人腦其實(shí)就相當(dāng)一臺(tái)計(jì)算機(jī)通過(guò)記憶力來(lái)儲(chǔ)存信息，通過(guò)四維來(lái)管理和處理信息，但是畢竟人腦的功能是有限的，處理數(shù)據(jù)能力也趕不上計(jì)算機(jī)，所以人們開(kāi)始希望能夠通過(guò)計(jì)算機(jī)來(lái)管理信息，通過(guò)一個(gè)管理軟件來(lái)幫助人們來(lái)完成工作.

另外，計(jì)算機(jī)軟件的在近幾年得到了非常大的發(fā)展，特別是在經(jīng)濟(jì)全球化的出現(xiàn)之后，自從新世紀(jì)以來(lái)，信息技術(shù)在企業(yè)中得到了越來(lái)越廣泛的應(yīng)用，無(wú)論是在企業(yè)的經(jīng)營(yíng)與生產(chǎn)中，還是在企業(yè)內(nèi)部管理以及對(duì)產(chǎn)品的設(shè)計(jì)與制造，企業(yè)信息化轉(zhuǎn)變極大地提高了企業(yè)的競(jìng)爭(zhēng)力，很多企業(yè)也逐漸認(rèn)識(shí)到計(jì)算機(jī)在企業(yè)中的作用，并且對(duì)企業(yè)的幫助等等，很多企業(yè)也逐漸增加了it部，以便對(duì)企業(yè)里的計(jì)算機(jī)軟件和硬件來(lái)進(jìn)行支撐工作，企業(yè)也注意到信息化的發(fā)展和處理信息的重要性，目前，很多企業(yè)已經(jīng)認(rèn)同了通過(guò)應(yīng)用軟件來(lái)實(shí)現(xiàn)對(duì)企業(yè)的管理.我們知道，企業(yè)信息化主要包含了廣泛利用信息技術(shù)，讓企業(yè)在生產(chǎn)與管理等方面，用以通過(guò)這些方法來(lái)實(shí)現(xiàn)信息化,這是一個(gè)十分廣泛的概念.

企業(yè)的信息化不僅運(yùn)用于內(nèi)部，企業(yè)與企業(yè)之間的合作也離不開(kāi)信息技術(shù).例如企業(yè)與其他合作對(duì)象互相交流數(shù)據(jù)，企業(yè)與客戶之間的業(yè)務(wù)往來(lái)，這些均是企業(yè)信息化發(fā)展的一部分.以上我們通過(guò)辦公軟件來(lái)揭示計(jì)算機(jī)軟件對(duì)人們生活和工作的影響，而軟件是通過(guò)算法研究開(kāi)發(fā)的，這么說(shuō)來(lái)計(jì)算機(jī)是跟這時(shí)代一同進(jìn)步的，而計(jì)算機(jī)算法設(shè)計(jì)也不斷推陳出新，要想計(jì)算機(jī)的應(yīng)用得到充分發(fā)展，計(jì)算計(jì)算法的研究和教學(xué)是非常重要的.

1 從ACM/ICPC的歷史意義和發(fā)展歷程

1.1 什么是ACM/ICPC

要想研究從ACM/ICPC看計(jì)算機(jī)算法設(shè)計(jì)教學(xué)改革，首先什么是ACM/ICPC？下面我們首先了解ACM.ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽 (英文全稱(chēng)：ACM International Collegiate Programming Contest（ACM-ICPC或ICPC）主辦方為美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM），是國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的標(biāo)志，這是一項(xiàng)旨在展示大學(xué)生團(tuán)隊(duì)精神、創(chuàng)新能力以及在壓力下編寫(xiě)程序、分析和解決問(wèn)題能力的年度競(jìng)賽.

1.2 ACM/ICPC的發(fā)展歷程

ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽由IBM公司贊助，已經(jīng)經(jīng)過(guò)了超過(guò)30年的發(fā)展，目前已經(jīng)發(fā)展成為最具影響力的大學(xué)生計(jì)算機(jī)競(jìng)賽.ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽首屆舉行在1970年，在美國(guó)德克薩斯大學(xué)，首屆賽事的主辦方是the Alpha Chapter of the UPE Computer Science Honor Society.這種方式是一種全新的培養(yǎng)計(jì)算機(jī)編程人才的方式，這種比賽不僅刺激學(xué)生們對(duì)新技術(shù)的求知欲望和學(xué)習(xí)欲望，還能培養(yǎng)對(duì)于一個(gè)軟件的更深的理解，不僅僅是停留在只要程序運(yùn)行出所要達(dá)到的結(jié)果就行了，而是對(duì)于程序而言僅僅執(zhí)行出來(lái)結(jié)果只是最淺層次的要求，而最有造詣的是如何設(shè)計(jì)這樣的程序，要時(shí)間復(fù)雜度和空間復(fù)雜度做到最小，除了可以鍛煉上述一些技能以外，我認(rèn)為最重要的是鍛煉了學(xué)生們的團(tuán)隊(duì)精神和團(tuán)隊(duì)的執(zhí)行力，如何領(lǐng)導(dǎo)一個(gè)團(tuán)隊(duì)，如何做一個(gè)稱(chēng)職的leader，如何做一好一個(gè)開(kāi)發(fā)者，總之要想完成比賽，必須分工明確，齊心協(xié)力才能夠達(dá)成.因此，美國(guó)以及加拿大各大學(xué)很快便開(kāi)始積極響應(yīng)賽事.尤其是在1977年，首次總決賽在ACM計(jì)算機(jī)科學(xué)會(huì)議期間舉辦，這也促使了競(jìng)賽演變發(fā)展成為多國(guó)參與的國(guó)際性比賽，并且一年便有一屆舉辦.相比最初的幾屆，參賽隊(duì)伍不再只有美國(guó)及加拿大的大學(xué)，競(jìng)賽逐漸發(fā)展成為一項(xiàng)世界范圍內(nèi)的競(jìng)賽.2002年美國(guó)夏威夷的第26屆、2005年上海的第29屆和2010在哈爾濱的第34屆的全球總決賽上，來(lái)自中國(guó)大陸的上海交通大學(xué)代表隊(duì)則在三奪冠軍，浙江大學(xué)參賽隊(duì)在美國(guó)當(dāng)?shù)貢r(shí)間2011年5月30下午2時(shí)結(jié)束的第35屆ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽全球總決賽榮獲全球總冠軍，成為除上海交通大學(xué)之外唯一獲得ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽全球總決賽冠軍的亞洲高校，目前，這也是來(lái)自亞洲的參賽大學(xué)取得的最佳成績(jī).如今，最初的北美大學(xué)一枝獨(dú)秀的局勢(shì)不再，已經(jīng)演變成亞歐對(duì)抗局面的競(jìng)爭(zhēng)格局.

1.3 ACM/ICPC的算法比賽流程

ACM/ICPC比賽方式是以團(tuán)隊(duì)的型式，以學(xué)校為單位，每個(gè)學(xué)校有一個(gè)隊(duì)組成，一個(gè)隊(duì)有三名學(xué)生，比賽要求是非常嚴(yán)格的，這個(gè)隊(duì)的比賽隊(duì)員必須是這個(gè)學(xué)校的，而且還是在校就讀學(xué)生，不能畢業(yè)的或者其他學(xué)校的學(xué)生，編寫(xiě)程序是這樣的，試題的規(guī)則是例如：C、D個(gè)小組如果都必須在規(guī)定時(shí)間內(nèi)完成兩道程序題，而且要運(yùn)行處結(jié)果，在編寫(xiě)程序過(guò)程中既要保證程序的編寫(xiě)質(zhì)量又要保證程序的編寫(xiě)速度，如果D隊(duì)在C隊(duì)沒(méi)有完成之前把兩道題都完成的話，那么D隊(duì)獲勝！反之C隊(duì)獲得勝利.

2 計(jì)算機(jī)算法設(shè)計(jì)教學(xué)改革

2.1 計(jì)算機(jī)算法的重要性

要想研究算法，就得知道什么是算法？算法可以簡(jiǎn)單理解成解決問(wèn)題的方法.在計(jì)算機(jī)科學(xué)中，算法是很重要的概念.它指明了問(wèn)題的處理、求解過(guò)程，是對(duì)給定問(wèn)題解決方案的準(zhǔn)確而完整的描述.其實(shí)，我們做任何事情都有相應(yīng)的算法.例如，電視機(jī)的操作說(shuō)明，就是使用電視機(jī)的算法;航模的安裝步驟示意圖，就是制作航模的算法.把算法交給計(jì)算機(jī)執(zhí)行是一件很復(fù)雜的事情，其中最大的障礙就是人類(lèi)自己的交流不暢和人機(jī)之間的語(yǔ)言不通.為了更好地合作，人們需要把算法正確、清晰、簡(jiǎn)潔地表達(dá)出來(lái).自然語(yǔ)言(漢語(yǔ)、英語(yǔ)等)、流程圖、程序設(shè)計(jì)語(yǔ)言等都可以用來(lái)描述算法.簡(jiǎn)單講述把算法交給計(jì)算機(jī)執(zhí)行的一般步驟.人們通常用自然語(yǔ)言、流程圖、程序設(shè)計(jì)語(yǔ)言來(lái)描述算法.

2.2 根據(jù)ACM/ICPC要求來(lái)了解語(yǔ)言

ACM/ICPC比賽主要是用C、C++、Pascal或Java這幾種語(yǔ)言參賽，首先是c語(yǔ)言，一個(gè)程序開(kāi)發(fā)者必須要學(xué)習(xí)C語(yǔ)言，這是為什么呢？因?yàn)镃語(yǔ)言是所有語(yǔ)言的基礎(chǔ)，另外C語(yǔ)言是一種輕量級(jí)的，很有表達(dá)力的語(yǔ)法，能很好的展現(xiàn)馮·諾曼機(jī)器的能力.馮·諾曼機(jī)器架構(gòu)就是你每天都用的計(jì)算機(jī)的架構(gòu)的標(biāo)準(zhǔn)：一個(gè)CPU、內(nèi)存、硬盤(pán)、一條總線.多核計(jì)算機(jī)并沒(méi)有帶來(lái)本質(zhì)上的變化.馮?諾曼機(jī)是一個(gè)很方便，很便宜，上世紀(jì)五十年代的實(shí)現(xiàn)圖靈機(jī)的技術(shù)，圖靈機(jī)是執(zhí)行計(jì)算的最知名的抽象模型.然后是C++，跟c比，在設(shè)計(jì)大型系統(tǒng)上面有著很大優(yōu)勢(shì),OO的思想便于建模，很方便設(shè)計(jì).執(zhí)行效率也不見(jiàn)得低c++的優(yōu)勢(shì)在哪里跟Java比，效率要高很多 (眾所周知，java程序很費(fèi)資源)c++的優(yōu)勢(shì)在學(xué)好C++，以后去任何公司都是可以的，不過(guò)現(xiàn)在中國(guó)使用C還是最多的c++的優(yōu)勢(shì)在哪里做外包的話，都用到數(shù)據(jù)庫(kù)應(yīng)用程序開(kāi)發(fā)(各種管理系統(tǒng))使用c++或者java c++的優(yōu)勢(shì)在哪里通信(qq,迅雷，華為，中信),都是C++，這個(gè)領(lǐng)域是C++的強(qiáng)項(xiàng)c++的優(yōu)勢(shì)在哪里手機(jī)，JAVA隨著GOOGLE的平臺(tái)，將有很大前途，但是NOKIA使用的平臺(tái)，還是C/C++用于開(kāi)發(fā)c++的優(yōu)勢(shì)在哪里汽車(chē)、冰箱……都是嵌入式系統(tǒng)，使用C和匯編居多c++的優(yōu)勢(shì)在哪里服務(wù)器端后臺(tái)編程，還是C++的天下.Pascal語(yǔ)言還是一種自編譯的語(yǔ)言，這就使它的可靠性大大提高了.在Pascal的各個(gè)版本中，尤以Turbo Pascal的功能最為強(qiáng)大.Pascal具有簡(jiǎn)潔的語(yǔ)法，結(jié)構(gòu)化的程序結(jié)構(gòu).它是結(jié)構(gòu)化編程語(yǔ)言，于70年代在ALGOL基礎(chǔ)上研制出來(lái)的.它具有豐富的數(shù)據(jù)類(lèi)型并提供了數(shù)據(jù)類(lèi)型定義設(shè)施，其控制結(jié)構(gòu)體現(xiàn)了結(jié)構(gòu)程序設(shè)計(jì)原則.它最初是為系統(tǒng)地教授程序設(shè)計(jì)而設(shè)計(jì)的，特點(diǎn)是簡(jiǎn)明化和結(jié)構(gòu)化，適合教學(xué)科學(xué)計(jì)算與系統(tǒng)軟件的研制.如今，在許多學(xué)校的計(jì)算機(jī)語(yǔ)言課上，學(xué)的都是Pascal語(yǔ)言，用的都是Turbo Pascal.至今，Pascal還是國(guó)際信息學(xué)奧林匹克競(jìng)賽中最受歡迎的編程語(yǔ)言之一.Pascal是最早出現(xiàn)的結(jié)構(gòu)化編程語(yǔ)言，具有豐富的數(shù)據(jù)類(lèi)型和簡(jiǎn)潔靈活的操作語(yǔ)句，適于描述數(shù)值和非數(shù)值的問(wèn)題.另外在數(shù)學(xué)領(lǐng)域，pascal異常很強(qiáng)大.java不用多說(shuō)是非常強(qiáng)大的語(yǔ)言，java不同于前三種語(yǔ)言，java語(yǔ)言是面向?qū)ο笳Z(yǔ)言，那么什么是面向?qū)ο笳Z(yǔ)言呢？通俗的說(shuō)：“如果有一輛汽車(chē)，你不需要學(xué)會(huì)制造汽車(chē)，也就是說(shuō)你不用懂得汽車(chē)的構(gòu)造，只要會(huì)駕駛會(huì)使用它，就可以開(kāi)著它上路，來(lái)為你服務(wù)”.也就是說(shuō)程序開(kāi)發(fā)者如果想實(shí)現(xiàn)一個(gè)功能，程序開(kāi)發(fā)者只要是調(diào)用公共類(lèi)里的方法，不需要知道這些方法是怎么編寫(xiě)的，只要使用它即可.所以隨著時(shí)代的發(fā)展，編程語(yǔ)言也逐漸變得容易，程序的復(fù)用性越來(lái)越高.

2.3 計(jì)算機(jī)算法設(shè)計(jì)教學(xué)改革

隨著計(jì)算機(jī)熱，各大院校都開(kāi)始開(kāi)設(shè)軟件工程專(zhuān)業(yè)，為了是讓更多的棟梁之才學(xué)習(xí)計(jì)算機(jī)編程，從事軟件開(kāi)發(fā)行業(yè)，軟降工程是計(jì)算機(jī)科學(xué)與技術(shù)系的一門(mén)專(zhuān)業(yè)課程，通過(guò)本課程的學(xué)習(xí)使學(xué)生掌握軟件工程的基本概念、基本原理、實(shí)用的開(kāi)發(fā)方法和技術(shù)；了解軟件工程各領(lǐng)域的發(fā)展動(dòng)向；如何用工程化的方法開(kāi)發(fā)軟件項(xiàng)目，以及在開(kāi)發(fā)過(guò)程中應(yīng)遵循的流程、準(zhǔn)則、標(biāo)準(zhǔn)和規(guī)范.在領(lǐng)域培養(yǎng)高級(jí)軟件開(kāi)發(fā)人員和系統(tǒng)分析員打下堅(jiān)實(shí)的基礎(chǔ).通過(guò)軟件工程課程的教學(xué)，應(yīng)使學(xué)生系統(tǒng)掌握軟件工程的基本概念，軟件設(shè)計(jì)中的過(guò)程抽象，軟件設(shè)計(jì)中的控制結(jié)構(gòu)，軟件設(shè)計(jì)中的數(shù)據(jù)類(lèi)型，軟件設(shè)計(jì)過(guò)程，軟件開(kāi)發(fā)和維護(hù)模型，抽象和信息隱藏，結(jié)構(gòu)化設(shè)計(jì)和過(guò)程設(shè)計(jì)，軟件設(shè)計(jì)的實(shí)現(xiàn)策略和語(yǔ)言，面向?qū)ο蟮姆治鲈O(shè)計(jì)方法，面向?qū)ο蠼⒛Ｐ?，軟件測(cè)試、軟件管理等.通過(guò)軟件工程課程的教學(xué),應(yīng)注意培養(yǎng)學(xué)生以下能力：進(jìn)行抽象思維和邏輯推理的理性思維能力；綜合運(yùn)用軟件工程的知識(shí)和方法進(jìn)行分析和解決問(wèn)題的能力；會(huì)應(yīng)用一些方法（Jackson、McCabe、Coad、Booch、OMT） 進(jìn)行基本問(wèn)題描述，如應(yīng)用Jackson方法進(jìn)行對(duì)算法進(jìn)行結(jié)構(gòu)化分析、OMT進(jìn)行面向?qū)ο蟪绦蚍治龅?；較強(qiáng)的自主學(xué)習(xí)能力，提高學(xué)生學(xué)習(xí)軟件工程的積極性,激發(fā)學(xué)習(xí)興趣,增強(qiáng)學(xué)習(xí)的信心；主動(dòng)探索和獨(dú)立思考的能力,提高學(xué)生的創(chuàng)新意識(shí).通過(guò)軟件工程課程教學(xué),應(yīng)注重培養(yǎng)學(xué)生以下素質(zhì)：深入理解軟件工程基本概念和基本方法，掌握用軟件工程的知識(shí)解決實(shí)際問(wèn)題的方法與手段，對(duì)各種問(wèn)題能以多角度探尋解決問(wèn)題的道路的素養(yǎng)；主動(dòng)將軟件工程原理應(yīng)用到具體的實(shí)踐中去的素養(yǎng)；善于對(duì)現(xiàn)實(shí)世界中現(xiàn)象和過(guò)程進(jìn)行合理的簡(jiǎn)化和量化，建立數(shù)學(xué)模型的素養(yǎng)；能用準(zhǔn)確、簡(jiǎn)明、規(guī)范的語(yǔ)言表達(dá)軟件工程思想的素養(yǎng)；能夠在軟件項(xiàng)目開(kāi)發(fā)中尋找新的方法與思路，并不斷地豐富軟件項(xiàng)目開(kāi)發(fā)的技術(shù)與方法的素養(yǎng).

3 結(jié)論

以上我們通過(guò)ACM/ICPC方面來(lái)分析軟件算法的教學(xué)設(shè)計(jì)，也了解了很多編程語(yǔ)言的特性優(yōu)勢(shì)以及劣勢(shì)，另外我也了解隨著社會(huì)的發(fā)展，計(jì)算機(jī)的發(fā)展，計(jì)算機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)逐漸成為我們?nèi)粘Ｉ畹谋匦杵?計(jì)算機(jī)給我們帶來(lái)工作管理上革命性質(zhì)的變化，計(jì)算機(jī)網(wǎng)絡(luò)則是把這種變化發(fā)揮到極致的技術(shù).軟件編程則是改變了我們的工作和生活的方式.

〔1〕June jam rich Parsons，Dan O ja．計(jì)算機(jī)文化.北京：機(jī)械工業(yè)出版社，2001.

〔2〕山東省教育廳組編.計(jì)算機(jī)文化基礎(chǔ).東營(yíng)：中國(guó)石油大學(xué)出版社，2006.

〔3〕Silberschatz，楊冬青，唐世渭，等．?dāng)?shù)據(jù)庫(kù)系統(tǒng)概論.北京：機(jī)械工業(yè)出版社，2000.