列印此頁 列印此頁

學院動態

ACM國際大學生程式競賽

文/傅楸善(資訊工程學系教授)

 

前言

“I have a dream.” 是美國人權運動家 Martin Luther King, Jr. 的名言, 他夢想美國的黑人與白人平等而且和平相處。我 (傅楸善) 也有個夢,我夢想台大的隊伍在美國計算機學會 (ACM: Association for Computing Machinery) 的國際大學生程式競賽 (ICPC: International Collegiate Programming Contest) 中拿到全世界第一名。

 

國際大學生程式競賽的重要性

    台大電機資訊學院的隊伍自從1996年參賽以來,最好的成績是1997年的全世界1,000隊中第4名,顯示我們有世界第一的潛力,如何將它化為實力,則是我們努力的方向。

    目前全世界軟體巿場佔有率美國佔80%以上。台灣因為人工與土地等成本的上漲,不僅傳統的紡織與機械工業早已出走到大陸,連高附加價值的主機板與筆記型電腦工業早在數年前也已出走到大陸了,因此大陸已超越台灣成為資訊硬體第三大國,僅次於美國與日本。台灣要成為綠色的高科技島,軟體工業是一個方向。

    很不幸地,軟體業的特性和硬體業有很大的不同。當初 IBM 要發展個人電腦時就強勢地要求 Intel 將 8088 微處理器的製程一定要授權給超微半導體,使 IBM 有第二個供應商,不必擔心萬一 Intel 廠房出了意外,微處理器會有斷貨的危險,而且也可以用超微半導體來威脅 Intel 降價。軟體業則截然不同,有老大則沒有老二,例如:有了微軟的視窗作業系統,則 IBM 的OS/2就只好收攤,有了微軟的 Internet Explorer,Netscape只好躲到 Unix 或 Linux 平台上了。換句話說,台灣今天軟體外銷的冠軍是趨勢科技的PCCillin,一年營業額約新台幣40億,但是趨勢科技不能以台灣第一或亞洲第一為滿足,十年後趨勢科技要不是世界第一就是關門大吉。而軟體廠商的唯一競爭利器就是優秀的軟體工程師,而國際大學生程式競賽是資訊系學生軟體功力最佳的展示場所。

 

比賽內容

    三個選手使用一部電腦在5個小時內要解8個題目,最後以解出題目數最多的為冠軍,若解題數相同時以最早解出者也就是所用的解題時間最短者為優先,程式寫好後將它送給裁判,裁判用測試資料測試程式的正確性,若正確則計入已解出題目數並懸掛一個彩色氣球以示鼓勵,若錯誤則加計解題時間以示懲罰。題目主要在測驗解題能力,因此,資料結構、演算法、計算幾何、圖形理論等是主軸。例如:給定一個三角形如下圖,請寫一個程式找出一條路徑其總和是最小:

                    5

                  /   \

                12    13

               /   \   /   \

             15     8     7

           /   \   /   \   /   \

        14      2      6     22

       /   \   /   \   /   \   /   \

     26     30     25     24      1

    輸出:最小和的路徑是5+13+7+22+1=48;在http://acm.uva.es/problemset 網站有廣泛收集各區域的比賽題目與線上裁判程式,只要將程式用電子郵件送出,線上裁判程式就會自動測試你的程式並在五分鐘內用電子郵件告訴你程式是否正確,而且把你放在全世界的排行榜,目前全世界共有8,000人註冊,台灣排在前25名的好手有5位。此網站是優秀軟體工程師名揚世界的好地方。

    國際大學生程式競賽和高中生的國際資訊奧林匹亞 (IOI: International Olympiad on Informatics) 有很大的不同。國際資訊奧林匹亞是一個人用一部電腦在四小時內解三題,考慮到高中生的語言問題,原始題目雖然是用英文,教練需在前一晚翻譯題目成該國語言;雖然題目的類型大致類似,但是因為人手一部電腦,選手隨時可以用除錯工具與環境,選手之間不可以交談,而且是以個人評分,不計團體分數。國際大學生程式競賽則只有隊伍排名,沒有個人分數,因為任何時候三個人只有一部電腦可用,分工合作是非常重要的,題目一發下來之後立刻判斷題目的類型與難易程度,找出最簡單的題目立刻指定一個最熟悉的隊員上電腦寫程式。

    此時另外兩個隊員因為沒有電腦可用,必須詳細讀其他題目,排定由簡單到難的解題順序並且在紙上寫程式。因為國際大學生程式競賽的發源地是美國,而且假設大學生沒有語言障礙,因此直接用英文命題沒有翻譯,這也是我們非英語系國家競爭較吃虧的地方,往往我們的題目還沒看完,別人的第一個氣球已經掛起來了。這時也要注意觀察別人氣球的顏色,因為不同的顏色正好對應不同的題號,別人這麼早解出的題目想必是簡單的題目,我們也要趕快跟進。每次換人用電腦時一定要將剛才寫的程式印出來,對了固然可以留存作記錄;錯了則在紙上由寫該程式的人逐行解釋給另一個沒有正在用電腦的隊友幫忙偵錯,因為可能是誤解題意或迴圈沒有重設變數等,有時隊友能幫忙找出錯誤,往往自己由於這樣的反省的程序,自己能找出錯誤。

    一般而言各個國家都有國內的程式競賽,台大自1996年至今全國大學生程式競賽都穩居第一名。國際大學生程式競賽分成數個區域先做區域賽,例如: 亞洲區就有台北、上海、香港、漢城、新加坡等站,在亞洲區台北站台大也大部份是第一名。全世界的決賽也曾在1999年拿到全世界第10名,數度擊敗Stanford, MIT, UC Berkeley…等世界名校。要知道更詳細的細節可以上網 http://www.acm.org/contest.

    大陸是一個新興而值得重視的敵人,雖然台大在1999年打敗大陸清華大學,但是從14億人選出來的精英的確厲害。我國參加高中生的國際資訊奧林匹亞六年來只得到一面金牌,而大陸年年拿到兩、三面金牌,換句話說,光金牌數大陸就是台灣的十倍以上,而這些好手大部分到大陸清華大學。大陸的學生都有旺盛的鬥志,因為能出國為校爭光是莫大的光榮,能到外國旅行更是難得的機會,得到好成績將來申請歐美的大學入學許可及獎學金更有莫大的幫助。

    反觀台灣的學生生活富裕,出國旅行是家常便飯,沒什麼了不起。台灣的大學或研究所也不錯在台灣念書學費低,即便要到國外念書,反正家人會付學費,獎學金可有可無。這個現象是刀子的兩面是好也是壞,我在1983年自本系畢業時班上51個同學有30多人在國外拿碩士或博士學位,前年本系碩士班甄試,有資格報名的30名學生中只有3位放棄,這當然對我們的教學和研究是一種肯定,但是到外國學習他們科技和文化新知的人太少了,這會造成夜郎自大的心理也容易造成學術上的近親繁殖的不良現象。

    現在的學生也太短視了,尤其台大的學生身處於台北花花大城巿之中,真正優秀的軟體人才又十分短缺,打工的機會太多了。整天忙於打工的結果,就是老師比學生用功,學生比老師忙。竟有大三的學生已是兩億資本額的公司的技術總監;比爾蓋茲先生固然沒有完成哈佛的大學學位就成就了微軟的大片江山,但那要絕佳的機運、過人的聰明才智及超乎常人的努力才做得到。

    國際大學生程式競賽就像練武的人蹲馬步的基本功夫,它是成功的軟體公司的必要條件,有了它再加上產品創意、國際行銷與靈活的財務管理才能成就世界第一的軟體公司。

展望

 今年 (2001) 的決賽將在3月7日至11日在加拿大溫哥華 (Vancouver) 舉行,由全世界2200隊篩選出的最後65隊好手將參與比賽,台大今年將由我指導資訊系四年級李務誠及電機系三年級李務熙及廖健溢參賽,另外有資訊系二年級吳光哲為教練,鐘楷閔及江盈宏為預備選手,現在正在加緊練習。感謝教育部計算機中心、台大校長、趨勢科技及廣達電腦長期以來資助我們的旅費。在我65歲退休前還有25次實現我的夢想的機會,希望今年就能實現我的夢想拿到全世界第一名。

發表迴響

你可以使用 HTML標簽

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>