大學程式能力檢定(cpe)-國立屏東大學資訊工程學系

1、大學程式能力檢定(CPE) 與提升程式實力的方法,楊昌彪 中山大學資訊工程學系 教授,2,程式能力檢定,已有多個學校採取「程式能力檢定」為畢業(yè)門檻、碩士招生參考標準執(zhí)行時，可能困難：如何命題？評分有無一致標準？老師需花多少心力？學生有無自修管道？如何補救？利用外部資源可能可以解決部分問題參加CPE (Collegiate Programming Examination),3,大學程式能力檢定(CPE),4,,,5,A

2、CM-ICPC Contest Council for Taiwan,「臺灣國際計算機器程式競賽暨檢定學會」(ACM-ICPC Contest Council for Taiwan ，簡稱ACM-ICPC Taiwan Council) 2009非正式成立2013/11 成立大會，並向內(nèi)政部登記為社團訂定「大學程式能力檢定(CPE)辦理要點」、「大學程式能力檢定(CPE) 考試規(guī)則」學會理事長：林盈達技術(shù)委員會主席：官大智私

3、立大學競賽委員會主席：林榮彬科技大學競賽委員會主席：江季翰大學程式能力檢定委員會主席：楊昌彪,6,大學程式能力檢定(CPE),大學程式能力檢定CPE (Collegiate Programming Examination)線上程式設(shè)計、電腦自動評判，採ACM ICPC排名方式2010/6 首次辦理CPE用途：單一課程上機考試全校程式設(shè)計競賽學系畢業(yè)檢定研究所入學考、廠商徵才提升個人程式設(shè)計能力(比賽之練習)網(wǎng)址：

4、http://cpe.cse.nsysu.edu.tw,7,CPE主辦學校,主辦學校：2010 交通大學2011~2017 中山大學技術(shù)支援：交通大學黃世昆教授Domjudge (2010/6~2013/5) 銘傳大學謝育平教授「瘋狂程設(shè)」(2013/6~,8,CPE 的特色作法,有限的人力、經(jīng)費，每年舉辦四次利用外部題目資源，涵蓋難、中、易範圍，以檢測學生平均程式能力，提升學生程式設(shè)計能力客觀的分級機制，有助於瞭解自己

5、程式設(shè)計能力同步作業(yè)：數(shù)十個考場同步（每個考場容納 20-200 人）節(jié)省系統(tǒng)設(shè)計、選命題時間跨校競爭，刺激學習意願大專學生免報名費，證書每份100元考生不能攜帶任何資料進場 (封閉網(wǎng)路),9,CPE被採計情形,大學畢業(yè)檢定(21校)：大同大學、中山大學、中正大學、元智大學、臺中教育大學、臺北大學、臺北市立大學、交通大學、金門大學、東華大學、虎尾科技大學、屏東大學、高雄大學、嘉義大學、逢甲大學、雲(yún)林科技大學、彰化師範大學、

6、銘傳大學、澎湖科技大學、靜宜大學、聯(lián)合大學 (另，交通大學、東華大學、長庚大學訂為碩士班畢業(yè)門檻）碩士班甄試招生參考標準之一(11校)中山大學、中正大學、中央大學、中興大學、臺中教育大學、臺北大學、交通大學、清華大學、高雄大學、高雄第一科技大學產(chǎn)碩班、雲(yún)林科技大學,10,CPE歷次規(guī)模,11,CPE歷次答對題數(shù)分佈,12,題目難易程度分級,一顆星：學習完計算機概論之後即可解答(solved in 10 minutes)二顆星：學習

7、完資料結(jié)構(gòu)之後才能解答或是苦工題(solved in 10~30 minutes)三顆星：要有好的演算法或數(shù)學方法才能解答(solved in 30~100 minutes)四顆星：要有特殊的演算法或是綜合多種演算法才能解答(solved in more than 100 minutes)五顆星：超越四顆星的極特殊題目,13,CPE題目難易度分佈(1),14,CPE題目難易度分佈(2),15,CPE題目難易度分佈(3),16,CP

8、E 2013/3/26題目集,題一：判斷正整數(shù)是否為perfect number。例如6的因數(shù)有1,2,3(不包含自己)，而且6=1+2+3。。題二：讀入資料，將非英文字母改寫為空白題三：題目給數(shù)個cubes，計算這幾個cubes都有重疊到的體積題四：N最後一位數(shù)砍掉，形成M，再算出N-M，題目給N-M的值，求出原本N值為多少題五：計算落在某座標Lakes的大小，可用DFS來解題六：計算 edge-weighted tree的

9、直徑題七：Chinese postman problem問題：一個圖從某個點開始，走過所有邊至少一次，然後回到起點,17,CPE計分方式與排名,採取ACM ICPC排名方式考試時間為3小時每個題目結(jié)果只有「對」與「錯」答對題數(shù)較多者，排名較前答對題數(shù)相同者，以解題時間總和決定排名解題時間為比賽開始至解題正確所花時間，再加上罰扣時間(每送出題解錯誤一次罰加20分鐘)答錯的題目不計時間及罰扣時間計分範例：甲隊開賽後10分鐘答

10、對A題，15分鐘送出B題(但錯誤)，32分答對B題?？倳r間為10+32+20*1=62分,18,CPE成績計分版,,19,CPE成績證書,題採 ACM-ICPC 評分規(guī)則相對成績：ACM-ICPC 排名規(guī)則,,20,參考書籍,大學程式能力檢定—CPE秘笈作者：林盈達、黃世昆、楊昌彪、葉正聖、謝育平包含有題意、解法、程式碼作者版稅收入全數(shù)捐贈ACM-ICPC Taiwan Council作為推廣CPE之用,21,考試環(huán)境,評判系統(tǒng)

11、：瘋狂程設(shè)一顆星選集(48題)考生使用手冊(考試系統(tǒng)操作、基本I/O)線上英文字典線上查詢 C++ library等查詢Java語法、資料型態(tài)、類別成員函式等,22,與廠商簽訂合作備忘錄,工業(yè)技術(shù)研究院雲(yún)端運算行動應用科技中心日月光半導體有限公司中華數(shù)位科技股份有限公司友旺科技股份有限公司玄力科技股份有限公司合勤科技股份有限公司亞仕資訊股份有限公司佳世達科技股份有限公司居易科技旺天電子股份有限公司明泰科技股

12、份有限公司昇頻股份有限公司哈碼星科技股份有限公司威睿科技股份有限公司,財團法人國家實驗研究院國家高速網(wǎng)路與計算中心財團法人資訊工業(yè)策進會康全電訊股份有限公司晨星網(wǎng)路科技股份有限公司釩創(chuàng)科技股份有限公司智原科技股份有限公司微核科技有限公司新軟系統(tǒng)股份有限公司盟創(chuàng)科技精品科技股份有限公司網(wǎng)擎資訊軟體股份有限公司豪勉科技股份有限公司摩鉅科技股份有限公司聯(lián)發(fā)科技股份有限公司豐藝電子股份有限公司,23,CPE(學

13、生)考試規(guī)則(摘要),大專在學學生免費(非大專學生需繳費)報名後，無故缺席而未到考，將取消其後一次考試資格。 不能攜帶任何資料進場 (封閉網(wǎng)路)採 ACM-ICPC 評分規(guī)則絕對成績：根據(jù)答對題數(shù)給予不同等級相對成績：ACM-ICPC 排名規(guī)則,24,CPE 大事紀(1),2010/06/09：由交通大學與中山大學首度跨校試辦，並定名為「Graduate Programming Examination」(簡稱GPE)。由交通大

14、學黃世昆教授負責主辦與電腦評判系統(tǒng)之維運。2011/01/01：更改由中山大學楊昌彪教授負責主辦，交通大學黃世昆教授仍然負責電腦評判系統(tǒng)之維運。2011/02/23：本考試更名為大學程式能力檢定 (Collegiate Programming Examination, 簡稱 CPE)。,25,CPE 大事紀(2),2011/06/29：訂定答對題數(shù)與成績等級之對應標準。2012/05/29：開放社會人士可以參加CPE考試。201

15、2/09/25：CPE考試之後，以原題目辦理「短碼競賽」，由銘傳大學謝育平教授負責。2013/02/25：出版參考書籍：「大學程式能力檢定：CPE秘笈」(作者：林盈達、黃世昆、楊昌彪、葉正聖、謝育平；出版社：美商麥格羅?希爾)。作者版稅收入全數(shù)捐贈ACM-ICPC Taiwan Council作為推廣CPE之用。,26,CPE 大事紀(3),2013/03/26：停辦「短碼競賽」。2013/03/26：首次突破一千人到考(實際到考1

16、047人)，首次有社會人士參加考試。2013/05/30：CPE考試納入104人力銀行，為廠商徵才勾選的選項之一。2013/06：陸續(xù)與多家廠商簽訂「合作備忘錄」，廠商得採用CPE成績作為徵才的審查參考之一。2013/10/1：改用「瘋狂程設(shè)」評判系統(tǒng)，由銘傳大學謝育平教授負責。2014/6：重新給予CPE成績証明書之等級名稱，並以文字說明其程式能力。,27,CPE 大事紀(4),2016/03/22：首次突破2000人到考(實

17、際到考2044人)。2016/04/08：Sudo甄選四位臺灣學生前往美國接受國際講師訓練，食宿全免。採計CPE成績?yōu)榈谝魂P(guān)的程式能力測驗。,ACM 程式設(shè)計競賽,29,2010ACM ICPC總決賽(哈爾濱工程大學),,30,2010ACM ICPC總決賽(哈爾濱工程大學),,31,2010ACM ICPC總決賽(哈爾濱工程大學),,32,2008ACM ICPC亞洲區(qū)(馬來西亞吉隆坡),,33,2009ACM ICPC亞洲區(qū)(印尼

18、雅加達BINUS),,34,2010ACM ICPC亞洲區(qū)(越南河內(nèi)),,35,2010ACM ICPC亞洲區(qū)(高雄中山大學),,36,2014ACM ICPC總決賽(葉卡捷琳堡),,37,2014ACM ICPC總決賽(葉卡捷琳堡),,38,2015ACM ICPC亞洲區(qū)(臺灣師範大學),,大學程式設(shè)計競賽,臺彎與世界競賽時程全國大專軟體設(shè)計競賽：每年10月私立大學程式設(shè)計競賽：2011年起，每年6、7月ACM ICPC (In

19、ternational Collegiate Programming Contest) 亞洲臺灣區(qū)域賽：每年11月ACM ICPC亞洲其他區(qū)域賽：每年10~12月ACM ICPC世界總決賽：每年2~6月2014-2015年，全球共有39個區(qū)域賽(region)，其中亞洲共有16個區(qū)域域賽(臺灣為其中之一)。2014-2015參賽統(tǒng)計：102國， 2736大學， 超過10000隊伍。,39,大學程式設(shè)計競賽組隊方式,每隊正好三人，

20、共同使用一部電腦基本要求(確定要求請見競賽規(guī)程)每位隊員最多可參加五年(每年最多兩個亞洲區(qū)域賽)每位隊員最多可參加兩次世界總決賽隊員資格(確定資格請見競賽規(guī)程)，下列二者之一：每位隊員進入大學後，不得超過5年不得超過24歲(例如參加2017區(qū)域賽，須1994年之後出生)競賽評分系統(tǒng)PC2 (或其他評分系統(tǒng)),40,41,ACM ICPC,緣起：1970年美國Texas A&M University大學程式設(shè)計比賽

21、1977年：第一次總決賽1977~1989：參與比賽的大學主要為美國與加拿大。1989年：開始建立區(qū)域賽(regional)的制度1991年：亞洲首支隊伍參加世界總決賽--國立交通大學。1995年。臺灣首度舉辦亞洲區(qū)域賽1996年以前，歷年的贊助廠商依先後順序分別為Apple、AT&T 和Microsoft 。1997年~：IBM公司為此競賽主要贊助商。1997年，參賽隊伍1100隊，來自560個大學2002年

22、，上海交大首度獲得總決賽冠軍2010年，參賽隊伍7900隊，臺灣大學獲得總決賽第三名2013年、2014年，臺灣大學獲得總決賽第四名,42,ACM ICPC Regional Contests (2016),ACM: Association for Computing MachineryICPC: International Collegiate Programming Contest,ACM ICPC World Finals,

23、https://icpc.baylor.edu/welcome.icpc,1 -43,Place University 1 Shanghai JiaoTong University2 Massachusetts Institute of Technology3 University of Waterloo4 Tsinghua University5 Stanford University

24、6 Saratov State University7 Fudan University8 Duke University9 Moscow State University10 Universidad de Buenos Aires11 Charles University Prague11 Royal Institute of Technology11 Seoul National Univer

25、sitySt Petersburg Institute of Fine Mechanics and Optics11 University of New South Wales11 University of Wisconsin - Madison11 Warsaw University18 Albert Einstein University Ulm18 Belarusian State Univers

26、ity18 Novosibirsk State University,Place University 18 Petrozavodsk State University18 POLITEHNICA University of Bucharest18 Sharif University of Technology18 The University of Tokyo18 University

27、 of Oldenburg18 University of Toronto27 California Institute of Technology27 Cornell University27 Orel State Technical University27 Queen's University27 Sofia University27 The Chinese University of Hong

28、 Kong27 The University of Chicago27 University of Calgary27 University of California, San Diego27 University of Central Florida27 University of Otago27 University of Texas at AustinUniversity of the Witwater

29、srand, Johannesburg27 Virginia Tech,,2002 ACM ICPC World Finals (64 Teams),ACM ICPC World Champions,45,ACM ICPC World Champions,46,ACM ICPC World Champions,47,ACM ICPC World Champions,48,UVA Online Judge,http://uv

30、a.onlinejudge.org/,線上即時評分系統(tǒng)(電腦自動評分）題目來源：ACM ICPC題目總數(shù)：超過4500題,1 -49,UVA Online Judge,統(tǒng)計每題被解的情形，讓學習者知道題目困難度,1 -50,The Format of One Problem,General DescriptionInput FormatOutput FormatSample InputSample Output,52,「高等

31、程式設(shè)計與實作」課程,簡易演算法(二小時)、UVA題目討論(一小時)題目難易分級上機模擬比賽,http://par.cse.nsysu.edu.tw/~cbyang/course/advprog/advprog_index.htm,53,程式設(shè)計與演算法,54,電腦解決問題的步驟,解決問題的方法：將抽象的解法變成實際具體可行的方法或程式。利用電腦解決問題的步驟Step 1: 明確定義問題（將其模式化）Step 2: 設(shè)計演算法

32、，並估計所需時間Step 3: 撰寫程式，並加以測試,55,解決問題範例,問題：計算大學聯(lián)考英文之前標明確定義：位於75%(前25%)之考生英文成績演算法：Step 1: 將所有考生英文成績排序（由低至高）(還有更好的方法嗎？)Step 2: 選出位於75%的成績撰寫程式： …...,56,各種排序演算法所需時間比較,CPU: K6-2 350時間單位：秒,57,學習程式設(shè)計三部曲,核心課程程式設(shè)計(計算機概論)資

33、料結(jié)構(gòu)演算法,58,演算法範例,【問題】將50元硬幣換成等值的1元、5元、10元 硬幣的方法共有多少種？【方法-1】　　採用窮舉法，每種硬幣可能的個數(shù)如下：　　i (10元):0,1,2,3,4,5　　j (5 元):0,1,2,…,10　　k (1 元):0,1,2,…,50　　假設(shè) i, j, k 分別代表10元、5元、1元的個數(shù)，　　則我們可以嘗試各種組合，並利用下面的判斷式：　　i*10

34、+ j*5 + k = 50　　 6 * 11 * 51 = 3366,59,main(){ int loop = 0, number = 0; int i, j, k; for (i = 0; i <= 5; i++) for (j = 0; j <= 10; j++) for (k = 0; k <= 50; k++) { loop++;

35、 if (i*10 + j*5+ k == 50) number++; } printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】 共36種,執(zhí)行迴圈3366次,60,【方法-2】　　若 k 不為 5 之倍數(shù)，根本不可能轉(zhuǎn)換，所以只需　　考慮 k 為 5 之倍數(shù)的情況?！　 (10元):0,1,2,3,4,5　　j (5

36、 元):0,1,2,…,10　　k (1 元):0,5,10,…,50　　 6 * 11 * 11 = 726,61,main(){ int loop = 0, number = 0; int i, j, k; for (i = 0; i <= 5; i++) for (j = 0; j <= 10; j++) for (k = 0; k <= 50; k+=5) {

37、 loop++; if (i*10 + j*5+ k == 50) number++; } printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】 共36種,執(zhí)行迴圈726次,62,【方法-3】　　當 i*10 + j*5 + k = 50時，應立即跳出最內(nèi)　　層迴圈，因為再變化 k 之值，i*10

38、+ j*5 + k　　均已大於 50?！　?491,63,main(){ int loop = 0, number = 0; int i, j, k; for (i = 0; i <= 5; i++) for (j = 0; j <= 10; j++) for (k = 0; k <= 50; k+=5) { loop++; if (i

39、*10 + j*5+ k == 50) { number++; break; } } printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】 共36種,執(zhí)行迴圈491次,64,【方法-4】　　當 i 和 j 之值固定後，k 之值只有唯一的選擇，　　因此不必考慮 k 的變化情形?！　=0,j可能為 0

40、,1,2,…,10 (50-i*10)/5=10　　i=1,j可能為 0,1,2,…,8 (50-i*10)/5=8　　i=2,j可能為 0,1,2,…,6 (50-i*10)/5=6 . . .　　i=5,j可能為 0 (50-i*10)/5=0　　 36,65,main(){ int loop = 0, number = 0; int i, j; for (

41、i = 0; i <= 5; i++) for (j = 0; j <= (50-i*10)/5; j++) { loop++; number++; } printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行結(jié)果】 共36種,執(zhí)行迴圈36次,66,【方法-5】　　由上一個方法知，當 i 的值固定後，j 的變化情形

42、　　只有 (50-i*10)/5 種，因此只需對 i 做迴圈?！　?6main(){ int loop = 0, number = 0; int i; for (i = 0; i <= 5; i++) { loop++; number += (50-i*10)/5 + 1; } printf("共%d種,執(zhí)行迴圈%d次\n",number,loop);}【執(zhí)行

43、結(jié)果】 共36種,執(zhí)行迴圈6次,67,【方法-6】　　我們計算的值其實是一個等差級數(shù)，即　　11+9+7+…+1=6*(11+1)/2=36　　將等差級數(shù)的公式寫成程式即可計算。main(){ int number = 0, a, b, n = 50; a = n / 5 + 1; if (a % 2 == 0) b = 2; else b = 1; number = (a+b)*((a-

44、b)/2+1)/2; printf("共%d種\n", number);}【執(zhí)行結(jié)果】 共36種,68,生活上實際範例,69,路線規(guī)劃—最短路徑問題,公車、捷運最短路徑最短時間,70,Google地圖路線規(guī)劃,71,環(huán)球旅遊與推銷員問題,平面上給予 n 個點，從某一點出發(fā)，經(jīng)過每個點一次，再回到出發(fā)點，而其總長度為最短Traveling Salesperson Problem

45、(TSP)此為 NP-complete 問題,72,尤拉的七橋問題,Euler's Konigsberg's (1255) Bridges Problem (1946, Kaliningrad) 一筆劃問題,73,人際網(wǎng)路(Social Network)(1),Erd?s numberMSN, Yahoo! Messenger（即時通）FacebookWretch（無名） Twitter（推

46、特）Plurk（噗浪）,74,人際網(wǎng)路(Social Network)(2),Social Network,75,上課教室與圖形著色,,,,,,,,,,,,課程 ABCDE,8:00,18:00,區(qū)間圖形著色問題(interval graph coloring)：,,,,,,C1,C1,C2,C3,C2,C1：第一個顏色C2：第二個顏色C3：第三的顏色,,A,B,D,C,E,76,股票投資與0/1 knapsack問題,有

47、n個東西，每個東西有其個別價值(value)與重量(weight)另有一個袋子，其容量為M，如何選取某些東西，使其總重要不超過M，而其總價值為最高。 例： M = 14 最佳(optimal)解法：P1、P2、P3、P5 0/1 knapsack問題為NP-complete,77,電腦能解決所有的問題嗎？,78,問題難易度,容易的問題：在多項式時間(polynomial time)可解決的問題

48、 如：排序，找最大值困難的問題：NP-complete，NP-hard 如：分割問題(Partition Problem) 推銷員問題(Traveling Salesperson Problem)不可解的問題：用演算法無法解決的問題 如：停止問題(Halting Problem)lower bound：解題所需時間之底限,79,我想不出好方法，我可能太笨了！,80,我想不出好方法，

49、因為不可能有這種好方法！,81,我想不出好方法，因為這些名人專家也不會！,82,數(shù)學七大難題,Clay Mathematics Institute of Cambridge, Massachusetts (CMI)於 2000年提出Birch and Swinnerton-Dyer Conjecture Hodge Conjecture Navier-Stokes Equations P vs NP Poincaré

50、; Conjecture Riemann Hypothesis Yang-Mills Theory 解決一道題目，獎金一百萬美元2010，Grigoriy Perelman(俄羅斯)已經(jīng)解決Poincaré Conjecture,83,結(jié)論,學習程式設(shè)計、資料結(jié)構(gòu)之後，免費上網(wǎng)學習「高等程式設(shè)計與實作」經(jīng)常參加CPE熟悉各種I/O方式，考前練習爭取參加ACM ICPC 或其他軟體設(shè)計比賽各校辦理CPE時