Chapter 1 Introduction.

Presentation on theme: "Chapter 1 Introduction."— Presentation transcript:

1 Chapter 1 Introduction

2 大學程式設計競賽 臺彎與世界競賽時程 全國大專軟體設計競賽：每年10月 私立大學程式設計競賽：2011年起，每年6、7月 科技大學程式設計競賽：2016年起，每年6、7月 ACM ICPC (International Collegiate Programming Contest) 亞洲台灣區域賽：每年11月 ACM ICPC亞洲其他區域賽：每年10~12月 ACM ICPC世界總決賽：每年2~6月 年，全球共有39個區域賽(region)，其中亞洲共有16個區域域賽(台灣為其中之一)。 參賽統計：超過100國， 超過2500大學， 超過10000隊伍。

3 ACM ICPC Regional Contests (2018)
ACM: Association for Computing Machinery ICPC: International Collegiate Programming Contest Region # of contests Africa and the Middle East 2 Asia 16 Europe 5 Latin America 4 North America 11 South Pacific 1

4 ACM ICPC 緣起：1970年美國Texas A&M University大學程式設計比賽 1977年：第一次總決賽
1977~1989：參與比賽的大學主要為美國與加拿大。 1989年：開始建立區域賽(regional)的制度 1991年：亞洲首支隊伍參加世界總決賽--國立交通大學。 1995年。台灣首度舉辦亞洲區域賽 1996年以前，歷年的贊助廠商依先後順序分別為Apple、AT&T 和Microsoft 。 1997年~：IBM公司為此競賽主要贊助商。 1997年，參賽隊伍1100隊，來自560個大學 2002年，上海交大首度獲得總決賽冠軍 2010年，參賽隊伍7900隊，台灣大學獲得總決賽第三名 2013年、2014年，台灣大學獲得總決賽第四名

5 ACM ICPC World Champions
year champions 1977 Michigan State University (USA) 1978 Massachusetts Institute of Technology (USA) 1979 Washington University in St. Louis (USA) 1980 Washington University in St. Louis Louis (USA) 1981 University of Missouri–Rolla Louis (USA) 1982 Baylor University Louis (USA) 1983 University of Nebraska Louis (USA) 1984 Johns Hopkins University Louis (USA) 1985 Stanford University Louis (USA) 1986 California Institute of Technology Louis (USA) year champions 1987 Stanford University (USA) 1988 California Institute of Technology (USA) 1989 University of California, Los Angeles (USA) 1990 University of Otago (New Zealand) 1991 1992 University of Melbourne (Australia) 1993 Harvard University (USA) 1994 University of Waterloo (Canada) 1995 Albert-Ludwigs-Universitat (Germany) 1996 University of California, Berkeley (USA)

6 ACM ICPC World Champions
year place country university site team final champions 1997 San Jose 560 1100 50 Harvey Mudd College (USA) 1998 Atlanta 49 1250 54 Charles University (Czech) 1999 Eindhoven 59 839 63 1900 62 University of Waterloo (Canada) 2000 Orlando 2400 60 St. Petersburg State University (Russia) 2001 Vancouver 70 1079 2700 64 2002 Honolulu 67 1300 3082 Shanghai Jiaotong University (China) 2003 Beverly Hills 68 1329 106 3835 Warsaw University (Poland) 2004 Prague 75 1411 127 3105 73 St. Petersburg Institute of Fine Mechanics and Optics (Russia) 2005 Shanghai 78 2006 San Antonio 84 1737 183 5606 83 Saratov State University (Russia)

7 ACM ICPC World Champions
year place country university site team final champions 2007 Tokyo 82 1756 205 6099 88 Warsaw University (Poland) 2008 Banff 1821 213 6700 100 St. Petersburg State University of IT, Mechanics, and Optics (Russia) 2009 Stockholm 1838 7109 2010 Harbin 1931 242 7900 103 Shanghai Jiaotong University (China) 2011 Orlando 2070 280 8305 Zhejiang University (China) 2012 Warsaw 85 2219 8478 112 St. Petersburg National Research University of IT, Mechanics, and Optics (Russia) 2013 St. Petersburg 91  2322   9800 119 2014 Ekaterinburg 94 2286 10681 122 St. Petersburg State University (Russia)

8 ACM ICPC World Champions
year place country university site team final champions 2015 Marrakesh 102 2736 481 128 St. Petersburg National Research University of IT, Mechanics, and Optics (Russia) 2016 Phuket St. Petersburg State University (Russia) 2017 Rapid City 133

9 大學程式設計競賽組隊方式 每隊正好三人，共同使用一部電腦 基本要求(確定要求請見競賽規程) 隊員資格(確定資格請見競賽規程)，下列二者之一：
每位隊員最多可參加五年(每年最多兩個亞洲區域賽) 每位隊員最多可參加兩次世界總決賽 隊員資格(確定資格請見競賽規程)，下列二者之一： 每位隊員進入大學後，不得超過5年 不得超過24歲(例如參加2018區域賽，須1995年之後出生) 競賽評分系統PC2 (或其他評分系統)

10 計分方式 比賽時間為5小時 每個題目結果只有「對」與「錯」 答對題數較多者，排名較前 答對題數相同者，以解題時間總和決定排名
解題時間為比賽開始至解題正確所花時間，再加上罰扣時間(每送出題解錯誤一次罰加20分鐘) 答錯的題目不計時間及罰扣時間 計分範例：甲隊開賽後10分鐘答對A題，15分鐘送出B題(但錯誤)，32分答對B題。總時間為 *1=62分

11 2010年全國大專電腦軟體設計競賽(108隊) 排名 學校 題數 時間 1 台灣大學 9 1245 17 3 347 33 2 264 49
55 1376 18 399 34 50 58 8 926 19 403 35 265 51 60 4 成功大學 1394 20 429 36 268 52 65 5 7 976 21 435 37 286 53 6 交通大學 1265 22 478 38 358 54 71 1562 23 503 39 364 76 942 24 544 40 471 56 87 1032 25 627 41 546 57 94 10 1120 26 652 42 29 97 11 1158 27 689 43 59 98 12 清華大學 842 28 165 44 100 13 1022 186 45 61 101 14 中山大學 426 30 193 46 62 108 15 台灣師大 731 31 244 47 63 114 16 260 32 249 48 64 115 1 -11 11

12 2010 ACM ICPC Asia Kaohsiung Regional (70 Teams)
rank school solved time 1 National Taiwan University (Taiwan) 10 1797 25 National Tsing Hua University (Taiwan) 5 844 2 University of Tokyo (Japan) 1855 26 National Cheng Kung University (Taiwan) 877 3 1971 27 The University of Hong Kong (Hong Kong) 1195 4 Shanghai Jiaotong University (China) 9 1159 28 National Sun-Yat-Sen University (Taiwan) 1248 1200 29 National Taiwan Normal University (Taiwan) 417 6 1205 30 Soongsil University(Korea) 448 7 8 932 31 City University of Hong Kong (Hong Kong) 455 1000 32 491 1097 33 Bina Nusantara University (Indonesia) 499 1294 34 Chung Hua University (Taiwan) 554 11 1301 35 566 12 Chinese University of Hong Kong(Hong Kong) 738 36 627 13 1079 37 637 14 1082 38 650 15 1231 39 742 16 National Chiao Tung University (Taiwan) 1255 40 804 17 1358 41 969 18 849 42 Saitama University (Japan) 225 19 Hong Kong University of Science and Technology (Hong Kong) 887 43 297 20 National Central University(Taiwan) 44 Senshu University (Japan) 338 21 1035 45 443 22 University of Aizu (Japan) 584 46 462 23 671 47 National Defence University (Taiwan) 486 24 817 　48 511 1 -12 12

13 ACM ICPC World Finals

14 2002 ACM ICPC World Finals (64 Teams)
Place University 1 Shanghai JiaoTong University 2 Massachusetts Institute of Technology 3 University of Waterloo 4 Tsinghua University 5 Stanford University 6 Saratov State University 7 Fudan University 8 Duke University 9 Moscow State University 10 Universidad de Buenos Aires 11 Charles University Prague 11 Royal Institute of Technology 11 Seoul National University St Petersburg Institute of Fine Mechanics and Optics 11 University of New South Wales 11 University of Wisconsin - Madison 11 Warsaw University 18 Albert Einstein University Ulm 18 Belarusian State University 18 Novosibirsk State University Place University 18 Petrozavodsk State University 18 POLITEHNICA University of Bucharest 18 Sharif University of Technology 18 The University of Tokyo 18 University of Oldenburg 18 University of Toronto 27 California Institute of Technology 27 Cornell University 27 Orel State Technical University 27 Queen's University 27 Sofia University 27 The Chinese University of Hong Kong 27 The University of Chicago 27 University of Calgary 27 University of California, San Diego 27 University of Central Florida 27 University of Otago 27 University of Texas at Austin University of the Witwatersrand, Johannesburg 27 Virginia Tech

15 2005 ACM ICPC World Finals (78 Teams)
Place University Solved Minutes 1 Shanghai Jiaotong U 2 Moscow State U 3 St Petersburg Institute of Fine Mechanics and Optics 4 U of Waterloo 5 U of Wroclaw 6 Fudan U 7 KTH - Royal Institute of Technology 8 Norwegian U of Science & Technology 9 Izhevsk State Technical U 10 POLITEHNICA U Bucharest 11 Peking U 12 The U of Hong Kong 13 Novosibirsk State U 13 Tsinghua U 13 Ufa State Technical U of Aviation 6 13 Yonsei U 17 Amirkabir U of Technology 17 Belarusian State U 17 Information & Communications U 5 17 Perm State U Place University Solved 17 Saratov State U 17 Sharif U of Technology 17 St. Petersburg State U 17 U of British Columbia 17 U of Illinois 17 Ural State U 17 Warsaw U 17 ZhongShan (Sun Yat-sen) U 29 Altai State Technical U 29 Bangladesh U of Engineering & Technology 29 California Institute of Technology 4 29 Duke U 29 Indian Institute of Technology, Madras 29 Instituto Tecnologico de Aeronautica 4 29 Kyoto U 29 Massachusetts Institute of Technology 4 29 Nanyang Technological U 29 Seoul National U 29 Sofia U 29 U of Alberta

16 2010 ACM ICPC World Finals (103 Teams)
place university solved time 1 Shanghai Jiaotong University 7 778 14 Kyoto University 5 2 Moscow State University 940 Massachusetts Institute of Technology 3 National Taiwan University 6 779 National Technical University "Kharkiv Polytechnic Institute" 4 Taras Shevchenko Kiev National University 928 Novosibirsk State University Petrozavodsk State University 985 Peking University Tsinghua University 998 Samara State Aerospace University Saratov State University 1010 Seoul National University 8 University of Warsaw 1042 St. Petersburg State University of IT, Mechanics and Optics 9 St. Petersburg State University Stanford University 10 Zhongshan (Sun Yat-sen) University 1049 State University - Higher School of Economics 11 Fudan University 1114 Universidade Federal de Pernambuco 12 KTH - Royal Institute of Technology 1265 University of British Columbia 13 Ural State University 1312 University of Maryland Beijing University of Posts and Telecommunications University of Michigan at Ann Arbor Belarusian State University University of Tokyo Carnegie Mellon University University of Waterloo Cornell University University of Wroclaw Instituto de Matematica e Estatistica da Universidade de Sao Paulo

17 2014 ACM ICPC World Finals (122 Teams)
Place University Solved Time Last solved 1 St. Petersburg State University 7 1359 298 10 National Research University Higher School of Economics 4 428 2 Moscow State University 1398 290 11 Tsinghua University 444 3 Peking University 6 1275 297 12 Comenius University 454 National Taiwan University 1483 296 13 Belarusian State University 5 University of Warsaw 796 266 New York University Shanghai Jiao Tong University 938 289 Taras Shevchenko Kiev National University The University of Tokyo 960 287 University of Electronic Science and Technology of China 8 University of Zagreb 970 242 University of Wroclaw 9 St. Petersburg National Research University of IT, Mechanics and Optics 1000 294 Zhejiang University

18 UVA Online Judge 線上即時評分系統(電腦自動評分） 題目來源：ACM ICPC 題目總數：超過4500題

19 UVA Online Judge 統計每題被解的情形，讓學習者知道題目困難度

20 The Format of One Problem
General Description Input Format Output Format Sample Input Sample Output

21 題目難易程度分級 一顆星：學習完計算機概論之後即可解答(solved in 10 minutes
四顆星：要有特殊的演算法或是綜合多種演算法才能解答(solved in more than 100 minutes) 五顆星：超越四顆星的極特殊題目

22 何謂演算法 Algorithm 解決問題的方法。將抽象的解法變成實際具體可行的方法或程式。 利用電腦解決問題的步驟
Step 1: 明確定義問題（將其模式化） Step 2: 設計演算法，並估計所需時間 Step 3: 撰寫程式，並加以測試

23 解決問題範例 問題：計算大學聯考英文之前標 明確定義：位於75%(前25%)之考生英文成績 演算法： 撰寫程式： …...
Step 1: 將所有考生英文成績排序（由低至高） Step 2: 選出位於75%的成績 撰寫程式： …...

24 各種排序演算法所需時間比較 CPU: K 時間單位：秒

25 演算法範例 【問題】將50元硬幣換成等值的1元、5元、10元 硬幣的方法共有多少種？ 【方法-1】 採用窮舉法，每種硬幣可能的個數如下：
　　採用窮舉法，每種硬幣可能的個數如下： 　　i (10元):0,1,2,3,4,5 　　j (5 元):0,1,2,…,10 　　k (1 元):0,1,2,…,50 　　假設 i, j, k 分別代表10元、5元、1元的個數， 　　則我們可以嘗試各種組合，並利用下面的判斷式： 　　i*10 + j*5 + k = 50 　　<執行迴圈次數> 6 * 11 * 51 = 3366

26 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++; if (i*10 + j*5+ k == 50) number++; } printf("共%d種,執行迴圈%d次\n",number,loop); 【執行結果】 共36種,執行迴圈3366次

27 【方法-2】 　　若 k 不為 5 之倍數，根本不可能轉換，所以只需 　　考慮 k 為 5 之倍數的情況。 　　i (10元):0,1,2,3,4,5 　　j (5 元):0,1,2,…,10 　　k (1 元):0,5,10,…,50 　　<執行迴圈次數> 6 * 11 * 11 = 726

28 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*10 + j*5+ k == 50) number++; } printf("共%d種,執行迴圈%d次\n",number,loop); 【執行結果】 共36種,執行迴圈726次

29 【方法-3】 　　當 i*10 + j*5 + k = 50時，應立即跳出最內 　　層迴圈，因為再變化 k 之值，i*10 + j*5 + k 　　均已大於 50。 　　<執行迴圈次數> 491

30 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*10 + j*5+ k == 50) number++; break; } printf("共%d種,執行迴圈%d次\n",number,loop); 【執行結果】 共36種,執行迴圈491次

31 【方法-4】 　　當 i 和 j 之值固定後，k 之值只有唯一的選擇， 　　因此不必考慮 k 的變化情形。 　　i=0,j可能為 0,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可能為 (50-i*10)/5=0 　　<執行迴圈次數> 36

32 main() { int loop = 0, number = 0; int i, j; for (i = 0; i <= 5; i++) for (j = 0; j <= (50-i*10)/5; j++) loop++; number++; } printf("共%d種,執行迴圈%d次\n",number,loop); 【執行結果】 共36種,執行迴圈36次

33 【方法-5】 　　由上一個方法知，當 i 的值固定後，j 的變化情形 　　只有 (50-i*10)/5 種，因此只需對 i 做迴圈。 　　<執行迴圈次數> 6 main() { int loop = 0, number = 0; int i; for (i = 0; i <= 5; i++) loop++; number += (50-i*10)/5 + 1; } printf("共%d種,執行迴圈%d次\n",number,loop); 【執行結果】 共36種,執行迴圈6次

34 【方法-6】 　　我們計算的值其實是一個等差級數，即 　　 …+1=6*(11+1)/2=36 　　將等差級數的公式寫成程式即可計算。 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-b)/2+1)/2; printf("共%d種\n", number); } 【執行結果】 共36種

35 Recursion Write a recursive C function to compute the sum of the elements of the array a. Solution : int sum(int a[], int size) /*size is the number of elements in array a[] */ { if(size == 0) return 0; else return a[size-1] + sum(a, size - 1); }

36 Wrong solution : int sum(int a[], int size, int s) //size is the number of elements in array a[] // s is the sum of a[], initial value of s is 0 { if(size == 0) return s; else { s = s + a[size-1] return sum(a, size - 1 , s); }

37 Determine the maximum of the contents of all nodes in a binary tree.
Solution: sturct nodetype { int info; struct nodetype *left; struct nodetype *right; } int max(struct nodetype *p) { int a,b;

38 if(p==NULL) return(-MAXINT); //MAXINT is infinite else { a=max(p->left); b=max(p->right); if (a>=b) return (p->info >= a ? p->info : a) else return (p->info >= b ? p->info : b) } } /* end of max() */

39 Wrong solution: int max(struct nodetype *p) { if(p==NULL) return(-MAXINT); //MAXINT is infinite else { if (max(p->left) >= max(p->right) return (p->info >= max(p->left) ? p->info : max(p->left)) else return (p->info >= max(p->right) ? p->info : max(p->right)) } } /* end of max() */

40 上課教室與圖形著色 8:00 18:00 課程 A B C D E 區間圖形著色問題(interval graph coloring)： A

41 問題難易度 容易的問題：在多項式時間(polynomial time)可解決的問題 如：排序，找最大值
困難的問題：NP-complete，NP-hard 如：分割問題(Partition Problem) 推銷員問題(Traveling Salesperson Problem) 不可解的問題：用演算法無法解決的問題 如：停止問題(Halting Problem) lower bound：解題所需時間之底限

42 我想不出好方法，我可能太笨了！

43 我想不出好方法， 因為不可能有這種好方法！

44 我想不出好方法， 因為這些名人專家也不會！

45 環球旅遊與推銷員問題 平面上給予 n 個點，從某一點出發，經過每個點一次，再回到出發點，而其總長度為最短 此為 NP-complete 問題

46 職棒比賽與分割問題 給予一個正整數的集合A={a1, a2, … , an}，是否可以將其分割成兩個子集合，而此兩個子集合的個別總和相等。
可以分割：{1, 8, 4} 及 {3, 10} 此為 NP-complete 問題

47 股票投資與0/1 knapsack問題 有n個東西，每個東西有其個別價值(value)與重量(weight)另有一個袋子，其容量為M，如何選取某些東西，使其總重要不超過M，而其總價值為最高。 例： M = 14 最佳(optimal)解法：P1、P2、P3、P5 0/1 knapsack問題為NP-complete P1 P2 P3 P4 P5 P6 P7 P8 價值 10 5 1 9 3 4 11 17 重量 7 22 15

48 生物資訊與演算法 人類DNA序列由30億(3109)個鹼基對(base pair)所組成
生物資訊之研究需要大量計算，如 字串比對、序列排列、相似度計算、 演化樹