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

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

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

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

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

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

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

7、完資料結(jié)構(gòu)之後才能解答或是苦工題(solved in 10~30 minutes)三顆星：要有好的演算法或數(shù)學(xué)方法才能解答(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。。題二：讀入資料，將非英文字母改寫(xiě)為空白題三：題目給數(shù)個(gè)cubes，計(jì)算這幾個(gè)cubes都有重疊到的體積題四：N最後一位數(shù)砍掉，形成M，再算出N-M，題目給N-M的值，求出原本N值為多少題五：計(jì)算落在某座標(biāo)Lakes的大小，可用DFS來(lái)解題六：計(jì)算 edge-weighted tree的

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

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

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

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

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

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

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

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

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

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

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

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

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

22、，上海交大首度獲得總決賽冠軍2010年，參賽隊(duì)伍7900隊(duì)，臺(tái)灣大學(xué)獲得總決賽第三名2013年、2014年，臺(tái)灣大學(xué)獲得總決賽第四名,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/,線上即時(shí)評(píng)分系統(tǒng)(電腦自動(dòng)評(píng)分）題目來(lái)源：ACM ICPC題目總數(shù)：超過(guò)4500題,1 -49,UVA Online Judge,統(tǒng)計(jì)每題被解的情形，讓學(xué)習(xí)者知道題目困難度,1 -50,The Format of One Problem,General DescriptionInput FormatOutput FormatSample InputSample Output,52,「高等

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

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

33、料結(jié)構(gòu)演算法,58,演算法範(fàn)例,【問(wèn)題】將50元硬幣換成等值的1元、5元、10元 硬幣的方法共有多少種？【方法-1】　　採(cǎi)用窮舉法，每種硬幣可能的個(gè)數(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元的個(gè)數(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】　　當(dāng) i*10 + j*5 + k = 50時(shí)，應(yīng)立即跳出最內(nèi)　　層迴圈，因?yàn)樵僮兓?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】　　當(dāng) i 和 j 之值固定後，k 之值只有唯一的選擇，　　因此不必考慮 k 的變化情形。　　i=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】　　由上一個(gè)方法知，當(dāng) i 的值固定後，j 的變化情形

42、　　只有 (50-i*10)/5 種，因此只需對(duì) 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】　　我們計(jì)算的值其實(shí)是一個(gè)等差級(jí)數(shù)，即　　11+9+7+…+1=6*(11+1)/2=36　　將等差級(jí)數(shù)的公式寫(xiě)成程式即可計(jì)算。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,生活上實(shí)際範(fàn)例,69,路線規(guī)劃—最短路徑問(wèn)題,公車(chē)、捷運(yùn)最短路徑最短時(shí)間,70,Google地圖路線規(guī)劃,71,環(huán)球旅遊與推銷(xiāo)員問(wèn)題,平面上給予 n 個(gè)點(diǎn)，從某一點(diǎn)出發(fā)，經(jīng)過(guò)每個(gè)點(diǎn)一次，再回到出發(fā)點(diǎn)，而其總長(zhǎng)度為最短Traveling Salesperson Problem

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

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

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

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

49、因?yàn)椴豢赡苡羞@種好方法！,81,我想不出好方法，因?yàn)檫@些名人專家也不會(huì)！,82,數(shù)學(xué)七大難題,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 解決一道題目，獎(jiǎng)金一百萬(wàn)美元2010，Grigoriy Perelman(俄羅斯)已經(jīng)解決Poincaré Conjecture,83,結(jié)論,學(xué)習(xí)程式設(shè)計(jì)、資料結(jié)構(gòu)之後，免費(fèi)上網(wǎng)學(xué)習(xí)「高等程式設(shè)計(jì)與實(shí)作」經(jīng)常參加CPE熟悉各種I/O方式，考前練習(xí)爭(zhēng)取參加ACM ICPC 或其他軟體設(shè)計(jì)比賽各校辦理CPE時(shí)