《资讯科学的逻辑思考演算法.ppt》由会员分享，可在线阅读，更多相关《资讯科学的逻辑思考演算法.ppt（33页珍藏版）》请在三一文库上搜索。
1、1,資訊科學的邏輯思考-演算法,楊昌彪 教授兼系主任 中山大學資訊工程學系 http:/www.cse.nsysu.edu.tw,2,2000年全國大專電腦軟體設計競賽(60隊),排名 隊伍編號 學校 答對題數 時間 1 A011 台灣大學 4 517 2 A027 清華大學 4 578 3 A030 交通大學 4 742 4 A034 交通大學 4 748 5 A028 清華大學 4 791 6 A010 台灣大學 4 1194 7 A013 台灣大學 3 367 8 A014 台灣大學 3 437 9 A025 清華大學 3 561 10 A039 逢甲大學 3 563 11 A047 中
2、正大學 3 565 12 A024 清華大學 3 568 13 A054 中山大學 3 766 14 A009 台灣大學 3 806 15 A007 台灣師範大學 2 230 16 A031 交通大學 2 266 17 A001 長庚大學 2 273 18 A035 交通大學 2 317 19 A012 台灣大學 2 325 20 A015 海洋大學 2 361,排名 隊伍編號 學校 答對題數 時間 21 A023 台灣科技大學 2 462 22 A006 台灣師範大學 1 56 23 A053 中山大學 1 62 24 A056 中山大學 1 115 25 A033 交通大學 1 126 2
3、6 A032 交通大學 1 146 27 A048 崑山科技大學 1 194 27 A055 中山大學 1 194 28 A026 清華大學 1 195 29 A008 台灣師範大學 1 206 30 A036 暨南大學 1 220 31 A029 清華大學 1 252 32 A037 暨南大學 1 269 33 A017 台北科技大學 1 304 34 A052 和春技術學院 1 308 35 A019 台灣師範大學 1 348 36 其餘隊伍 0 0,3,2000 ACM亞洲區台北賽區大學程式設計競賽(48隊),Rank Team Name School Name Problems Sol
4、ved Penalty 1 Doodoong Seoul National University 5 735 2 Gold Medal National Taiwan University 4 714 3 Apple Car Movie National Taiwan University 3 291 3 God of Power National Taiwan University 3 439 3 CUHK Mars The Chinese Univ. of Hong Kong 3 817 4 D.N.A. National Taiwan University 2 263 4 super S
5、LP National Taiwan University 2 298 4 eagle National Tsing-Hua University 2 302 5 Roasted Wing National Chiao-Tung University 2 303 5 NCTU JPN LAB National Chiao-Tung University 2 421 5 CSIE Dragon National Chiao-Tung University 2 460 6 Seal National Sun Yat-sen University 2 477 6 CUHK Mercury The C
6、hinese Univ. of Hong Kong 2 597 7 Ocean Star National Taiwan Ocean Univ. 2 600 8 CSIE Snake National Chiao-Tung University 1 48 8 Funky Family IX National Taiwan University 1 136 8 Ants National Tsing-Hua University 1 142 8 The Seven Wonders National Taiwan University 1 153 8 ICE World National Taiw
7、an Normal Univ. 1 156 9 ICE Snow National Taiwan Normal Univ. 1 186 9 clover National Taiwan Normal Univ. 1 194 9 ICE Storm National Taiwan Normal Univ. 1 256 9 CSIE Tiger National Chiao-Tung University 1 278 9 Eustis National Tsing-Hua University 1 289 9 Braves National Tsing-Hua University 1 297 9
8、 ilantech National I-Lan Institute of Tech. 1 316 10 ICE 007 National Taiwan Normal Univ. 1 359,4,1998 ACM大學程式設計競賽世界總決賽(54隊),Place University Solved Minutes 1 Charles U - Prague 6 919 2 St. Petersburg Univ. 6 1021 3 U Waterloo 6 1026 4 U Umea - Sweden 6 1073 5 MIT 6 1145 6 Melbourne U 6 1153 7 Tsing
9、 Hua U - Beijing 5 743 8 U Alberta 5 758 9 Warsaw U 5 780 10 Politehnica U Bucharest 5 813 11 UC Berkeley 5 11 Nanyang TU - Singapore 5 11 St. Petersburg IFMO 5 11 Duke University 5 11 Virginia Tech 5 11 Shanghai Jiaotong U. 5 17 McGill Poutines 4 17 National Taiwan U 4 17 Sofia University 4 17 Mosc
10、ow State U 4 17 U Texas - Austin 4 17 Caltech 4 17 Ural State TU 4,Place University Solved 24 Case Western 3 24 BUET, Bangladesh 3 24 Stanford U 3 24 PUC Rio de Janeiro 3 24 Shanghai Univ. 3 29 Comenius U 2 29 University of Ulm 2 29 U Auckland 2 29 Harding University 2 29 Florida Tech 2 29 U Missour
11、i-Rolla 2 29 U. Minnesota - Morris 2 29 Binus U.-Indonesia 2 29 U Central Florida 2 29 Darmstadt UT 2 29 NTNU - Taiwan 2 29 ITESM 2,5,2002 ACM大學程式設計競賽世界總決賽(64隊),Place University 1 Shanghai JiaoTong University 2 Massachusetts Institute of Technology 3 University of Waterloo 4 Tsinghua University 5 St
12、anford 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
13、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 Th
14、e 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 Queens University 27 Sofia University 27 The Chinese University of Hong Kong 27 The University of Chicago 27 University of Calga
15、ry 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,6,邏輯思考,邏輯思考乃解決所有事務之基礎(不論是否使用電腦) 從小至大，每天均在累積邏輯思考的實力，但求學期間增進較多 數學課程是邏輯思考的基礎,7,資訊科學(資訊工程)與數學,數學在計算上有其實用性 數學在深
16、入的研究領域上可能較抽象 離散數學為資訊科學的數學基礎 資訊科學是數學的一個應用領域 資訊科學需設計實際可行的軟硬體,8,何謂演算法,Algorithm 解決問題的方法。將抽象的解法變成實際具體可行的方法或程式。 利用電腦解決問題的步驟 Step 1: 明確定義問題（將其模式化） Step 2: 設計演算法，並估計所需時間 Step 3: 撰寫程式，並加以測試,9,解決問題範例,問題：計算大學聯考英文之頂標 明確定義：計算所有考生中前25%英文成績之平均 演算法： Step 1: 將所有考生英文成績排序（由高至低） Step 2: 將排名在前面1/4的成績資料相加後， 再除以1/4的人數 撰寫
17、程式： .,10,各種排序演算法所需時間比較,CPU: K6-2 350 時間單位：秒,11,何時學習演算法,課程順序 程式設計 資料結構 離散數學 演算法 事實上，開始學習程式設計，即已開始學習演算法,12,演算法範例,【問題】將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
18、6 * 11 * 51 = 3366,13,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次,14,【方法-2】 若 k 不為 5 之倍數，根本不可能轉換，所以只需 考慮 k 為 5 之倍數的情況。 i (10元):0
19、,1,2,3,4,5 j (5 元):0,1,2,10 k (1 元):0,5,10,50 6 * 11 * 11 = 726,15,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次,16,【方法-3】 當 i*10
20、 + j*5 + k = 50時，應立即跳出最內 層迴圈，因為再變化 k 之值，i*10 + j*5 + k 均已大於 50。 491,17,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次,18,【方
21、法-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可能為 0 (50-i*10)/5=0 36,19,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+; print
22、f(“共%d種,執行迴圈%d次n“,number,loop); 【執行結果】 共36種,執行迴圈36次,20,【方法-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次,21,【方法-6】 我們計算的值其實是一個等差級數，即
23、 11+9+7+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種,22,上課教室與圖形著色,課程 A B C D E,8:00,18:00,區間圖形著色問題(interval graph coloring)：,C1,C1,C2,C3,C2,C1：第一個顏色 C2：第二個顏色 C
24、3：第三的顏色,A,B,D,C,E,23,問題難易度,容易的問題：在多項式時間(polynomial time)可 解決的問題 如：排序，找最大值 困難的問題：NP-complete，NP-hard 如：分割問題(Partition Problem) 推銷員問題(Traveling Salesperson Problem) 不可解的問題：用演算法無法解決的問題 如：停止問題(Halting Problem),24,我想不出好方法，我可能太笨了！,25,我想不出好方法， 因為不可能有這種好方法！,26,我想不出好方法， 因為這些名人專家也不會！,27,環球旅遊與推銷員問題,平面上給予 n 個點，
25、從某一點出發，經過每個點一次，再回到出發點，而其總長度為最短 此為 NP-complete 問題,28,職棒比賽與分割問題,給予一個正整數的集合A=a1, a2, , an，是否可以將其分割成兩個子集合，而此兩個子集合的個別總和相等。 例：A = 1, 3, 8, 4, 10 可以分割：1, 8, 4 及 3, 10 此為 NP-complete 問題,29,股票投資與0/1 knapsack問題,有n個東西，每個東西有其個別價值(value)與重量(weight)另有一個袋子，其容量為M，如何選取某些東西，使其總重要不超過M，而其總價值為最高。 例： M = 14 最佳(optimal)解法
26、：P1、P2、P3、P5 0/1 knapsack問題為NP-complete,30,生物資訊與演算法,人類DNA序列由30億(3109)個鹼基對(base pair)所組成 人類DNA序列草圖於2000年5月公佈 生物資訊之研究需要大量計算，如 字串比對、序列排列、相似度計算、 演化樹,31,結論,演算法是邏輯思考的實現 程式設計是演算法的實現 演算法可以訓練每個人思路謹慎細密 有錢人可以買快速的硬體，但良好的演算法可以節省金錢 良好的演算法可以加速解決問題或解決資料量更大的問題 各個領域均應善用良好的演算法,32,參考書目,較易書籍 資料結構 戴顯權 著 紳藍出版社 07-3480411
27、Computer Algorithms: Introduction to Design & Analysis, by S. Baase and A. V. Gelder 歐亞書局 02-23636141 Data Structures and Algorithm Analysis by M. A. Weiss, 滄海書局 04-22521013 較深入書籍 Introduction to the Design and Analysis of Algorithms by R. C. T. Lee, R. C. Chang, S. S. Tseng and Y. T. Tsai 旗標圖書 02-23963257 Introduction to Algorithms, by T. H. Cormen, C. E. Leiserson and R. L. Rivest 開發圖書 02-23629900 Computer Algorithms, by E. Horowitz, S. Sahni and S. Rajasekaran 台北圖書 02-23625376,33, The End 謝謝聽講,中山資工 http:/www.cse.nsysu.edu.tw,