大學程式能力檢定：CPE祕笈[Da Xue Cheng Shi Neng Li Jian Ding ：Cpe Mi Ji]＊電腦資訊類＊～新書推薦！

作者：林盈達、黃世昆、楊昌彪、葉正聖、謝育平
出版社：美商麥格羅‧希爾
出版日期：2013/02/25
語言：繁體中文

ISBN：9789861579412
叢書系列：資訊科學叢書
規格：平裝/336頁/16k/19x26cm/普通級/單色印刷/初版
出版地：台灣
本書分類：電腦資訊>認證檢定>其他認證檢定

【Preview】內容預覽/連載/試閱PDF下載

CHAPTER1程式能力檢定簡介
1.1 ACM國際大學程式競賽

ACM ICPC（International Collegiate Programming Contest，國際大學程式競賽）是由 ACM（Association for Computing Machinery，國際計算機器協會）主辦的一年一次程式設計競賽。藉由競賽方式來展現大學生創新能力、團隊精神，以及在壓力下編寫程式、分析和解決問題的能力。自從1970年代開創以來，經過三十多年的發展，ACM ICPC已成為全球電腦界中歷史最悠久且最具影響力的程式競賽。以2011至2012年為例，參加各地區域賽的隊伍超過8000隊，涵蓋88個國家及超過2000所大學。區域賽優勝隊伍會再集中於一處參與世界總決賽的競逐。以下列舉ACM ICPC的重要里程碑：

• 1970年：美國Texas A&M University大學程式設計比賽。
• 1977年：第一次舉辦世界總決賽。
• 1977至1989年：參與比賽的大學主要來自美國與加拿大。
• 1989年：建立區域賽(regional)制度，優勝隊伍才能參加世界總決賽。
• 1991年：亞洲首支隊伍（台灣交通大學）參加世界總決賽。
• 1995年：首度舉辦亞洲區域，並在台灣舉行，由國立政治大學辦理。
• 1996年以前：歷年贊助廠商依序為Apple、AT&T和Microsoft。
• 1997年之後：IBM公司為此競賽的主要贊助商。
• 1997年：參賽隊伍1100隊，來自560個大學。總決賽地點在美國聖荷西，代表台灣的台灣大學榮獲總決賽第4名，這是台灣隊伍首次進入前十名。
• 2002年：中國的隊伍首度獲得總決賽冠軍——上海交通大學。
• 2010年：參賽隊伍7900隊，台灣的隊伍獲得有史以來最好的成績，為總決賽第三名——台灣大學。
• 2011年：世界總決賽原訂於埃及沙姆沙伊赫舉行，但由於埃及當時發生暴動，因而將總決賽地點更換為美國奧蘭多。

自1997年以來的參賽隊伍數量與冠軍隊伍，詳列於表1.1。
表1.2、表1.3與表1.4分別列出2010年、2011年與2012年世界總決賽排名較為前面的隊伍。2010年前13名的隊伍，俄羅斯與中國合計佔了9個；2011年前12名的隊伍，俄羅斯與中國合計佔了7個；2012年前12名的隊伍，俄羅斯與中國合計佔了6個。由此可以看出世界頂尖的優秀隊伍超過半數集中於俄羅斯與中國，代表這兩個國家對於程式設計的能力非常重視。

1.2 ACM ICPC題目庫
ACM ICPC舉行三十餘年，所累積的寶貴資源，就是歷次的比賽題目。有些題目已經收錄於UVa線上評審網站（UVa online judge，網址為http://uva.onlinejudge.org/，其中UVa乃指西班牙瓦拉多利大學(Universidad de Valladolid)），目前累積已經超過3600題。全世界各地有許多人士在其上註冊帳號，進行練習，以提升程式設計能力。

該網站也會列出各題被解決的情形，以便讓人區分難易程度，如圖 1.1所示。中間的部分代表所有送出的程式碼被線上評審伺服器認可為正確的比例。由於線上評審伺服器可隨時評審程式碼，故使用者對於尚未被評審認可的程式碼可以再次遞送，直到正確為止。圖的最右側代表該題最後遞送出正確程式碼的使用者比例。

所有ACM ICPC題目均有固定格式，每題包含General Description（一般描述）、Input Format（輸入格式）、Output Format（輸出格式）、Sample Input（輸入範例）、Sample Output（輸出範例）共五大部分。每題長度大約一至三頁左右。圖1.2為題目範例。

雖然收錄於UVa網站的ACM ICPC題目庫，對於每一題均有遞送正確程式碼的百分比，以及正確解題的使用者百分比，但仍不足以完全分辨其難易程度。我們為了讓學習者可以瞭解適合練習的題目，並讓教師可以配合授課課程內容做為學生之實作或測驗題目，乃將題目區分為五個等級，如下所示：

• 一顆星(level 1)：學習完計算機概論之後即可解答（專家級設計師大約可於10分鐘撰寫完畢）。
• 兩顆星(level 2)：學習完資料結構之後才能解答或是苦工題（專家級設計師大約可於10至30分鐘撰寫完畢）。
• 三顆星(level 3)：需良好的演算法或數學方法才能解答（專家級設計師大約可於30至100分鐘撰寫完畢）。
• 四顆星(level 4)：需要特殊的演算法或是綜合多種演算法才能解答（專家級設計師需要超過100分鐘才能撰寫完畢）。
• 五顆星(level 5)：超越四顆星的極特殊題目。

1.3 大學程式能力檢定(CPE)
「ACM亞洲區台灣賽區大專程式設計競賽」自1995年起，每年在台灣各大學輪流舉行。為了提升國內大學生的程式設計能力，各大學相關科系的教授於2008年組織了「國際計算機器協會程式競賽台灣協會」（ACM-ICPC Contest Council for Taiwan，簡稱ACM-ICPC Taiwan Council），做為跨校交流與合作的平台。該協會下設三個委員會如下：

1. 推動委員會：負責資源與庶務之整合，原則上由參與學校之計算機中心（或等同單位）主任或資訊系系主任組成。

2. 技術委員會：由教練與命題老師組成，負責培訓與命題事務，原則上成員須具備程式培訓與命題之能力與經驗。

3. 大學程式能力檢定委員會（Collegiate Programming Examination Committee，簡稱CPE Committee）：共同舉辦CPE程式檢定考試，由已參與及即將參與舉辦CPE檢定考試之學校代表參加，該學校代表原則上為該校考場負責人。

大學程式能力檢定（Collegiate Programming Examination，簡稱CPE）旨在提升全台灣學生的程式設計能力，由學生透過線上程式設計，利用電腦自動評判，以檢測程式設計能力。CPE每年辦理四次，大約為每年的3、6、9、12月。CPE採電腦現場上機考試，以電腦自動評判，並由各校派員監考。考試時，會封閉與考試無關的網路。考生除紙本字典外，不能攜帶任何資料。考生若為大專學生，可免費報名。CPE的標誌如圖1.3所示。