《资讯科学逻辑思考演算法.ppt》由会员分享，可在线阅读，更多相关《资讯科学逻辑思考演算法.ppt（33页珍藏版）》请在三一办公上搜索。
1、1,資訊科學的邏輯思考-演算法,楊昌彪 教授兼系主任中山大學資訊工程學系,2,2000年全國大專電腦軟體設計競賽(60隊),排名 隊伍編號 學校 答對題數時間1A011台灣大學 45172A027清華大學 45783A030交通大學 47424A034交通大學 47485A028清華大學 47916A010台灣大學 4 11947A013台灣大學 33678A014台灣大學 34379A025清華大學 356110A039逢甲大學 356311A047中正大學 356512A024清華大學 356813A054中山大學 376614A009台灣大學 380615A007 台灣師範大學 2230
2、16A031交通大學 226617A001長庚大學 227318A035交通大學 231719A012台灣大學 232520A015海洋大學 2361,排名 隊伍編號 學校 答對題數時間21A023 台灣科技大學 246222A006 台灣師範大學 1 5623A053中山大學 1 6224A056中山大學 111525A033交通大學 112626A032交通大學 114627A048 崑山科技大學 119427A055中山大學 119428A026清華大學 119529A008 台灣師範大學 120630A036暨南大學 122031A029清華大學 125232A037暨南大學 1269
3、33A017 台北科技大學 130434A052 和春技術學院 130835A019 台灣師範大學 134836 其餘隊伍 0 0,3,2000 ACM亞洲區台北賽區大學程式設計競賽(48隊),RankTeam NameSchool NameProblemsSolved Penalty1DoodoongSeoul National University 57352Gold MedalNational Taiwan University 4714 3Apple Car MovieNational Taiwan University 32913God of PowerNational Taiwan
4、 University 34393CUHK Mars The Chinese Univ.of Hong Kong 38174D.N.A.National Taiwan University 22634super SLPNational Taiwan University 22984eagleNational Tsing-Hua University 23025Roasted WingNational Chiao-Tung University 23035NCTU JPN LABNational Chiao-Tung University 24215CSIE DragonNational Chi
5、ao-Tung University 24606SealNational Sun Yat-sen University 24776CUHK Mercury The Chinese Univ.of Hong Kong 25977Ocean StarNational Taiwan Ocean Univ.26008CSIE SnakeNational Chiao-Tung University 1 488Funky Family IXNational Taiwan University 11368AntsNational Tsing-Hua University 11428The Seven Won
6、dersNational Taiwan University 11538ICE WorldNational Taiwan Normal Univ.11569ICE SnowNational Taiwan Normal Univ.11869cloverNational Taiwan Normal Univ.11949ICE StormNational Taiwan Normal Univ.12569CSIE TigerNational Chiao-Tung University 12789EustisNational Tsing-Hua University 12899BravesNationa
7、l Tsing-Hua University 12979ilantechNational I-Lan Institute of Tech.131610ICE 007National Taiwan Normal Univ.1359,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
8、 1153 7 Tsing 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
9、17 Moscow 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 Miss
10、ouri-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 University2 Massachusetts Institute of Technology3 University of Waterloo4 Tsinghua University5 Stanford
11、 University6 Saratov State University7 Fudan University8 Duke University9 Moscow State University10 Universidad de Buenos Aires11 Charles University Prague11 Royal Institute of Technology11 Seoul National UniversitySt Petersburg Institute of Fine Mechanics and Optics11 University of New South Wales1
12、1 University of Wisconsin-Madison11 Warsaw University18 Albert Einstein University Ulm18 Belarusian State University18 Novosibirsk State University,Place University 18 Petrozavodsk State University18 POLITEHNICA University of Bucharest18 Sharif University of Technology18 The University of Tokyo18 Un
13、iversity of Oldenburg18 University of Toronto27 California Institute of Technology27 Cornell University27 Orel State Technical University27 Queens University27 Sofia University27 The Chinese University of Hong Kong27 The University of Chicago27 University of Calgary27 University of California,San Di
14、ego27 University of Central Florida27 University of Otago27 University of Texas at AustinUniversity of the Witwatersrand,Johannesburg27 Virginia Tech,6,邏輯思考,邏輯思考乃解決所有事務之基礎(不論是否使用電腦)從小至大，每天均在累積邏輯思考的實力，但求學期間增進較多數學課程是邏輯思考的基礎,7,資訊科學(資訊工程)與數學,數學在計算上有其實用性數學在深入的研究領域上可能較抽象離散數學為資訊科學的數學基礎資訊科學是數學的一個應用領域資訊科學需設計
15、實際可行的軟硬體,8,何謂演算法,Algorithm解決問題的方法。將抽象的解法變成實際具體可行的方法或程式。利用電腦解決問題的步驟Step 1:明確定義問題（將其模式化）Step 2:設計演算法，並估計所需時間Step 3:撰寫程式，並加以測試,9,解決問題範例,問題：計算大學聯考英文之頂標明確定義：計算所有考生中前25%英文成績之平均演算法：Step 1:將所有考生英文成績排序（由高至低）Step 2:將排名在前面1/4的成績資料相加後，再除以1/4的人數撰寫程式：.,10,各種排序演算法所需時間比較,CPU:K6-2 350時間單位：秒,11,何時學習演算法,課程順序程式設計資料結構離散
16、數學演算法事實上，開始學習程式設計，即已開始學習演算法,12,演算法範例,【問題】將50元硬幣換成等值的1元、5元、10元 硬幣的方法共有多少種？【方法-1】採用窮舉法，每種硬幣可能的個數如下：i(10元):0,1,2,3,4,5j(5 元):0,1,2,10k(1 元):0,1,2,50假設 i,j,k 分別代表10元、5元、1元的個數，則我們可以嘗試各種組合，並利用下面的判斷式：i*10+j*5+k=50 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=
17、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,1,2,3,4,5j(5 元):0,1,2,10k(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
18、(i*10+j*5+k=50)number+;printf(共%d種,執行迴圈%d次n,number,loop);【執行結果】共36種,執行迴圈726次,16,【方法-3】當 i*10+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,
19、loop);【執行結果】共36種,執行迴圈491次,18,【方法-4】當 i 和 j 之值固定後，k 之值只有唯一的選擇，因此不必考慮 k 的變化情形。i=0,j可能為 0,1,2,10(50-i*10)/5=10i=1,j可能為 0,1,2,8(50-i*10)/5=8i=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+;printf(共%d種,執行迴圈
20、%d次n,number,loop);【執行結果】共36種,執行迴圈36次,20,【方法-5】由上一個方法知，當 i 的值固定後，j 的變化情形只有(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種,執行迴圈%d次n,number,loop);【執行結果】共36種,執行迴圈6次,21,【方法-6】我們計算的值其實是一個等差級數，即11+9+7+1=6*(11+1)/2=36將等差級數的公式寫成程式即可計算。main()in
21、t 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,上課教室與圖形著色,課程 ABCDE,8:00,18:00,區間圖形著色問題(interval graph coloring)：,C1,C1,C2,C3,C2,C1：第一個顏色C2：第二個顏色C3：第三的顏色,A,B,D,C,E,23,問題難易度,容易的問題：在多項式時間(polynomial time)可 解決的問題 如：排序，找最大值困難的問題：NP-complete，N
22、P-hard 如：分割問題(Partition Problem)推銷員問題(Traveling Salesperson Problem)不可解的問題：用演算法無法解決的問題 如：停止問題(Halting Problem),24,我想不出好方法，我可能太笨了！,25,我想不出好方法，因為不可能有這種好方法！,26,我想不出好方法，因為這些名人專家也不會！,27,環球旅遊與推銷員問題,平面上給予 n 個點，從某一點出發，經過每個點一次，再回到出發點，而其總長度為最短此為 NP-complete 問題,28,職棒比賽與分割問題,給予一個正整數的集合A=a1,a2,an，是否可以將其分割成兩個子集合，
23、而此兩個子集合的個別總和相等。例：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)解法：P1、P2、P3、P5 0/1 knapsack問題為NP-complete,30,生物資訊與演算法,人類DNA序列由30億(3109)個鹼基對(base pair)所組成人類DNA序列草圖於2000年5月公佈生物資訊之研究需要大量
24、計算，如字串比對、序列排列、相似度計算、演化樹,31,結論,演算法是邏輯思考的實現程式設計是演算法的實現演算法可以訓練每個人思路謹慎細密有錢人可以買快速的硬體，但良好的演算法可以節省金錢良好的演算法可以加速解決問題或解決資料量更大的問題各個領域均應善用良好的演算法,32,參考書目,較易書籍資料結構 戴顯權 著 紳藍出版社 07-3480411Computer Algorithms:Introduction to Design&Analysis,by S.Baase and A.V.Gelder 歐亞書局 02-23636141Data Structures and Algorithm Anal
25、ysis 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-23629900Computer Algorithms,by E.Horowitz,S.Sahni and S.Rajasekaran 台北圖書 02-23625376,33,The End 謝謝聽講,中山資工,
