admin 的部落格

"資工三甲 493511450 鄭彥暉前言

OSI模型 7個層級中網路層主要的功能是將原始點機器上的封包經過路由器,選擇一條路徑送達目的地機器,繞送演算法 (routing algorithm)為網路層軟體的一部份,主要是決定輸入封包應以哪一條輸出線傳送出去

而且這學期上到網路概論也有敎到許多的routing algorithm,剛好可以來研究一下資料在網路的路由器是如何做傳送,而最短路徑路由和距離向量路由是廣泛使用的靜態和動態路由技術

簡介一、非調整性繞送 ( Nonadaptive algorithm )

決定繞送的方式不是依據目前流量及網路分佈,而是在網路啟動時載入路由器中。這個過程稱為靜態路由(static routing) 

          

最短路徑路由

演算法的構想是建立一條通訊線路,從一對路由器之間找出最短路徑

 圖一:計算A至D之最短距離前5步驟,箭頭所指為工作點而找最短路徑的演算法最常使用Dijkstra演算法,起初演算法未找到任何路徑,因此所有節點標示的距離為無限大,然後不斷進行發現新路徑,節點標示值也隨之改變,顯示出較佳路徑,剛開始的標示值都為暫時的,直到起始點發現到某一節點的最短路徑時,該標示則為永久的標示。圖一是說明演算法的圖示,圖一(a)中邊上的數字代表距離。我們想從找尋AD的最短距離。先將A點塗黑作為永久標示,然後檢查與A相鄰的點,並且標上由A到他的距離,當我們重新設定一個節點時,同時也將他的前一個節點紀錄下來,以便重建最短路徑。藉著我們檢查所有與A相鄰的點看哪一個距離最短,就把他塗黑作為工作點,而他的標示值也變成永久的。然後我們再看B點,同樣檢查與B相鄰的節點,如果將B點到各相鄰點的距離再加上原本標示在B身上的AB的距離,經過比較便可再決定出一條較短的路徑如圖一(b)到圖一(c)的過程,A經由BC9,A經由BE4,照著這樣的方法便可以決定出一條最短路徑 Dijkstra演算法

void shortestpath ( int v , int cost[] [MAX_VERTICES], int distance[], int n , short int found[] )
  {
   int i , u , w ;
   for ( i = 0 ; i < n ; i++ ) {
     found[i] = FALSE ;
     distance[i] = cost[v][i] ;
   }
   found[v] = TRUE ;
   distance[v] = 0 ;
   for ( i =0 ; i < n - 2 ; i ++ ) {
     u = choose ( distance , n , found ) ;
     found[u] = TURE ;
     for ( w = 0 ; w < n ; w++ )
       if ( !found[w] )
        if ( distance[u]+cost[u][w] < distance[w] )
           distance[w] = distance[u] + cost[u][w] ;
   }
  }

 

比較
  1、計算單一起點最短路徑的時間複雜度為 O(n2)n為圖形中的頂點數
  2、計算任意兩點間的最短路徑,所需的時間複雜度為O(n3)n為圖形中的頂點數

   魚型問題  路由決策一般基於簡單度量(如跳數或時延) 原則,採用最短路徑演算法,這種簡化做法使路由技術獲得了很好的伸縮性,但在資源分配和優化等方面卻沒有提供足夠的支持。這可以通過著名的“魚型問題”來說明。        圖一().所示的網路拓撲形狀如一條魚,節點G代表魚頭,AB代表魚尾,數據流從AB流向G從魚尾到魚頭有CDFCEF兩條路徑。如果CDFCEF短,則路由協議將選擇CDF作為最短路由,AB的業務流都將沿著CDF走,結果造成CDF負載沉重而CEF卻被閒置的情形。從這個例子我們可以發現,路由協議實際上很“傻”。

這個問題源於IP路由協議的兩個基本特點:

 

  第一,基於目的地選路。目的地址相同的數據包在被轉發時,選擇的下一跳也相同。所以,在路由表中,到達某目的地的路徑只有一條(除非有多條成本相同的路徑存在)。這樣,網路中可用的其他鏈路就無法被利用起來,流量分布很難預測,實現均衡更不可能。

   第二,局部優化。每個節點都獨自選擇路徑,相互之間缺乏協調合作,故整個網路的路徑選擇無法得到優化。如在圖1中,很多節點都獨立地選擇CDF,結果導致最短路徑成了最擁擠的路徑。在這種情況下,較長的路徑反而可能是更好的選擇。為了優化網路總體資源利用率,路由決策應該從全局觀點出發,把整個網路視為一個對象考慮。   在極端的情況下,最短路徑演算法還可能導致路由振盪。假如某節點在某時刻根據路由協議選擇CDF作為從CF的最短路徑,當所有業務流都經過時,該路徑就變得異常擁塞,而另一條CEF則很空閒。下一次路由更新時,假如路由協議把CEF選為最短路徑,則此改變就會將原來CDF的流量轉移到CEF上。結果呢,情況倒置,CEF擁塞,而CDF卻變得空閒。每次路由更新都會引起路徑選擇的翻轉,從理論上講,該過程會持續到無窮大。 優點1.          最短路徑路由屬於靜態路由所以需要網路管理者手動輸入路徑表,這樣可以讓你高度掌握路由器用來執行路徑決定工作的確切資料2.          路由器之間不必發掘新路徑也不需要交換彼此的路徑資訊3.          可產生有效率的環境,頻寬可全部留給終端機傳送資料4.          所有路徑都已知,不必再浪費路由器CPU時間發現新路徑,不會有額外的處理成本5.          網路較安全,只定義一個網路進出點而又是防火牆就可以監視過濾網路缺點互連網路的傳輸很容易因一條線路中斷而失敗。當線路斷掉時,路由器不會去發現其他的新路徑,以致於傳輸出了問題。  維護靜態網路需要大量的管理負擔,只要網路上有任何變動,例如新增或斷掉一線路,移除一台路由器,網路管理者都要更新每部路由器的路徑表。不適合用於大型的網路環境,原因也是上面的理由如上圖所示,A路由器到C路由器的線路斷掉,然後A收到一個目的地為Net30的封包,A要把他傳送過去,但是偵測到不通所以把封包丟了,但是A不知道可以經由BC,所以就都不能傳了。我們要解決這樣的問題就必須手動來改變路由器傳送封包的路徑,如果網路有很多的路徑,線路常常出問題,網路管理者就需要常常來做變更的動作。 二、可調整性演算法 ( Adaptive algorithm ) 

繞送的途徑視網路分佈與流量改變

  距離向量路由 距離向量演算法也有其他的名稱,如分散式Bellman-Ford路由演算法及Ford-Fulkerson演算法。ARPANET最初就是利用此法進行路由,後來在網路上稱為RIP   其演算法的運作方式是每個路由器必須維護一個表格(如一個向量),表中紀     錄本身的路由器至每個目的地之已知最佳距離,與到達目的地需要使用哪    些線路。路由器定期與他的鄰居交換表格資訊。 

聲明:我們說到當一個網路到另一個網路的距離時,這裡的距離

             有很多不同的解釋,不一定是實際地理上的距離。有很多

             使用距離向量路由的繞送協定對於距離的計算有不同的單

             位。但都是要算出一個數值稱為衡量指標(metric)或稱路

             徑成本以下是幾種計算衡量指標的變數:

              

u中繼站計數:計算封包到達目的地前經過的路由器

                        數目

    u頻寬:以低頻寬為遠距離,高頻寬為近距離 

u延遲時間:指封包透過傳輸媒介傳送所花的間,有

                    可能受到兩端實際距離和線路壅塞程度

                    影響      u負載:指網路資源的使用率,如路由器CPU使用率

u可靠度:這個值要人手動設定,如線路好壞給予等

                 級   等會兒的說明距離是延遲時間    在距離向量路由法中,每個路由器會維護一個路由表,以子網路內的每個路由器做為索引,並在每個路由器建立一筆紀錄,每筆紀錄有2部分:(A)到達目的地所優先使用的輸出線,(B)到達目的地之時間或距離估算。   圖三(a)(b)說明路由資料更新的過程,圖三(a)為一個子網路,圖三(b)的前4個欄位顯示從路由器J鄰近節點所獲得的延遲向量。                  圖三(a) A宣告A本身對B的延遲是12msec,對C25msec,對D40msec。假設J預估對鄰近節點AIHK的延遲分別為8101216然後我們接著來計算JG的新路徑:1.          JèAèG = 8+18 = 26 msec (代表一個封包從JAG所須延遲時間)2.          JèIèG = 10+31 = 41 msec3.          JèHèG = 12+6 = 18 msec4.          JèKèG = 6+31 = 37 msec經過這樣的比較,我們算出新最佳路徑並且更新表格,然後照這樣的方法我們用於其他的路由器來做各路由表的更新如圖三(b)最後一欄。 問題產生:路徑迴圈(routing loop) 使用距離向量繞送協定的網路可能會發生一些問題,最有名即是路徑迴圈(routing loop)。每當網路拓樸發生改變,網路就會有一段不穩定的時期,直到路由器收斂為止。大部分的問題都是因為收斂的時間太慢,或者路由器收斂不正確的資訊。封包在兩個或兩個以上的路由器間來回不斷轉送,形成一個迴圈就稱為路徑迴圈,迴圈通常是收斂期間的問題造成,圖四即表示迴圈路徑情況。 圖四中,B路由器到Net1的連結中斷,他很快就偵測到這個問題,並且從路徑表中移除這條路徑,在下一次的路徑更新,B路由器把他的路徑表送給C路由器,C因此得知B失去了到Net1的連結,所以也移除了到Net1路徑的紀錄。而就在剛剛移除之後D送路徑更新記錄給CC看到D有一條衡量指標為2的路徑到Net1。所以計算出一條經由D且衡量指標為3的路徑到Net1。問題就產生了,CD都認為另一方可以到達Net1,所以封包就在兩路由器之間轉來轉去。C還會把他新算到的Net1路徑給B,導致B把要送給Net1的封包送給C,這樣又陷入路徑迴圈之中。 解決方法 

最大的中繼站計數:能讓封包跳出無窮路徑迴圈。封包在網路上

                                     &n"

"

一、                猜數字簡介

猜數字是一種益智的小遊戲,一般而言是兩人以上玩的遊戲,由一人構思一個四位數字,每位數字不可重複!而其他人(猜題者)每猜一個數字出題者必須給出?A?B,A代表有數字猜中且位置放對,而B代表猜中數字但位置錯誤!例如:題目為1234猜題者猜1567則為10B,因為只有猜中1且位置對;若猜題者猜5167則為01B,因為只有猜中1但位置錯誤!以此類推,直到猜題者猜到4A。

有時候會限制猜題次數以增加困難度,根據資料上表示,此遊戲若以最嚴謹的計算,人和數字皆可在7次內猜出!所以限制次數在6次或更少,難度自然增加,但有時連次數都不加以限制,以降低難度!可謂老少咸宜之益智小遊戲!

二、                人腦V.S.電腦

人腦思考猜數字遊戲已是相當花費腦力,更何況要電腦使用人腦邏輯去思考解決問題,勢必是更加的複雜,所以通常是使用Brute-Force方法去要求電腦找出解答!

    人腦可能的想法有下列兩種:

1.推理解:

假設猜題數字123400B則排除1234的可能,因為若解答中含有1234任一數字,則至少會有1B!重複嘗試之後,找出4個數字再去排列組合找出正確解!

2.代入解:

藉由推理出的可能解,把不可能含有的數字替換掉,查看查看哪些數字可能會在答案中!通常此種方法猜測次數比推理解要來的多!

 

.人腦猜電腦

    通常是採用推理解加代入解兩種方式混和使用,例如一開始先測試1234看有幾個數字落在1-4之間,在填5678,最後在測試904個數字各落在哪些區間!最差的情形可能發生在一(兩)個數字在1-4之間,兩(一)個數字在5-8之間,而測試90時使用到題目的數字,造成判斷錯誤!

 

.電腦猜人腦

    電腦比人腦具備有一個優點就是運算能力快,所以電腦可以利用推理解迅速將不可能的解刪去,留下可能的解去測試!此種方法一開始執行也許有點慢,但是會越猜越快,因為候選解越來越少!但是此種方法猜測次數可能會相當多次,

 

三、                各種演算法分析

 

.Brute-Force

01236789四位數字不重複的共有5040個,由最前一個測試到最後一個,Best Case1次就猜中,但是Worse Case卻是5040次,期間猜測的次數過於不固定,且方法笨的可以,通常可以輔以其他方法來配合!但是暴力法卻是所有解猜數字題目的基本步驟,或多或少會經歷到必須一個一個測試的情形!

 

.Brute-Force + 推理解

與暴力法相同的是一個一個猜,但是步驟卻可以精簡很多!在測試第一組數據0123與第二組0124時,若兩者的AB數目沒變動,則往後所有測試數據中有3或有4的數據皆可跳過不測試!但若A數目不動則分兩種情形:(1)B上升:代表數字4為解的其中一個數字,往後之需要將所有候選數據中含有4的取出測試即可!(2)B下降:代表數字3為解的其中一個數字,作法和B上升時相同,只需測試含有3的數據!如此一來,便把測試次數大幅縮減!

除了上述動作之外,在挑選下一個測試數據也是一門極大的學問,通常的作法是以上次猜測的數據與剩下的候選數據作比對,若AB數目相同即可,若AB數目不同則此數據絕非正解!假設猜測的數字123412B,則繼續去比較剩下的候選解,例如13461234比較也是12B,所以1346有可能是正解!相反地把13581234比較得11B,則1358絕非正解,若1358是正解,那1234絕不可能是12B!

根據以上的方法去實做,每猜一個數字就把候選解刪去一些,沒幾次正解自然就出現了!此實作之程式請見附件1

         

.BackTracking

相較於Brute-ForceBackTracking並沒有太大分別,更可以說是相同!abcd四位數字,從最小的開始填,自然是從0123->0124->0125->…如此一來就和暴力法完全相同,若真要說差別,只差在coding時的繁複程度!

 

.Other

猜數字的遊戲中,4的位元的數字依照猜對猜錯,每組數據可能有15種情形,00B到40B,而各種情形下又要去判斷是哪個數字產生A的結果,哪個數字產生B的結果,若將其建成一個Tree,可以想見這棵樹是有多雄偉壯觀!所以一般而言沒有人會使用Tree的方法去Coding猜數字的程式!

事實在上各網站討論此程式的數量不少,也有許多人整理出一些規則!大多立足於暴力法的觀念下,利用刪去法、推理解等等各種方法使候選解的集合快速縮小,以求更快猜到正解!

 

四、                若不只4位元?

在寫這分報告時,有想到過萬一這個遊戲猜的數字不是4位數,而是3位數或5位數,那難度會變成怎樣?因為數字僅僅有0-910個數字,所以在多不可能超過10位元,在少不可能低於1位元!以下我就猜測位元作些討論!

A.        1位元

這沒什麼好討論的,正解在0-9之間,使用暴力法:Worse Case = 10Best Case = 1

B.        2位元

正解在0198之間,共90種可能(以下為我個人之想法,不討論單純暴力法的解,是假設在worse case情況下)兩兩數字為一組,先將正解的數字縮小到4個數字的範圍,在就這兩組交換一位元,便可確定正解的兩個數字,最後就是兩種排列方法去測試!

其中在縮小到4個數字範圍時,假設此4個數字為abcd,則依照交換的位元會有下列幾種情形:

1.        1個是正解的數字一個不是:如此一來交換過的兩組會變成20B及00B!如此便知何者為正解的兩個數字!

2.        2個都不是正解的數字或2個都是正解的數字:如此一來交換過的兩組數字其AB值不變,只需取另外兩個沒交換的數字在測試一次便知何者是正解的數字!若是交換兩個都不是正解的數字,取其餘兩數字測試後會是20B!若交換兩個都是正解的數字,則其餘兩個數字的測試結果為00

因此,在2位元的情形下,Best Case依然是1次,但是Worse Case8次!

C.        3位元

正解在012987之間,共有720種可能數字!單純以暴力法來看,Worse Case = 720

D.        4位元

正解在01239876之間,共有5040種可能數字!如前述之情形,因此不在這裡再說明一次!

E.        5位元

正解在0123498765之間,共有30240種可能數字!單純以暴力法來看,Worse Case = 30240

F.        6位元

正解在012345987654之間,共有151200種可能數字!單純以   暴力法來看,Worse Case = 151200

G.        7位元

正解在01234569876543之間,共有604800種可能數字!單純以暴力法來看,Worse Case = 604800

H.        8位元

正解在0123456798765432之間,共有1814400種可能數字!單純以暴力法來看,Worse Case = 1814400

I.        9位元

正解在012345678987654321之間,共有3628800種可能數字!單純以暴力法來看,Worse Case = 3628800

J.        10位元

正解在01234567899876543210之間,共有3628800種可能數字!單純以暴力法來看,Worse Case = 3628800

    根據以上資料可以看到,字元數越多候選解也越多!字元數越多自然難度也越高!但是基本的規則卻是固定,依舊是先猜測數字的區間,再來是刪除被排除的值,在上述各種情形下,5位元是個分界點,位元數大於5者,在第一次猜測時最差也會有一個B,因為0910個數字,正解有5個以上的數字,則排除的數字自然在5個以下!所以在位元數大於5的情形下,與其猜測正解的數字,不如反向思考,去找出不是解的值,然後將候選解中含有該值的候選解刪除!如此會較為省力!

 

五、                總結

對 於猜數字這個遊戲,似乎只存在於暴力法的根基之上,但是暴力法有暴力法的觀點,並不是任何問題都用暴力法會比較好,同樣的,並不是說任何問題都不用暴力 法,有些情形之下,以暴制暴是免不了的手段。但是暴力歸暴力,如何讓其變得聰明點,而不是想到什麼情形就只寫出解決該情形的Code,這便是花腦力的地方了!問題也許很複雜,但是仔細觀察也不是沒有任何規則!觀察出規則,整理好思緒,寫出解決問題的程式,才是資工的精神所在!!

從小到大,我一直對這個小遊戲很沒輒,每次猜數字都猜很多次,於是我就想「既然我不會猜,不知道怎麼去猜,那換成電腦的話會怎麼猜」,所以才藉著這次Project的機會深刻認識一下這個小遊戲!電腦是個很笨的東西,他只會遵照使用者叫他做什麼就做什麼,但是他卻是很好的工具,龐大的運算功能是人腦遠遠不及!所以人腦搭配電腦,以往難以解決的問題也就都迎刃而解了!

六、                參考資料

JavaWorld@TW     http://www.javaworld.com.tw/jute/

loren.wox.org    http://loren.wox.org/product/game/aaaa/index.html

維基百科  http://zh.wikipedia.org/wiki/%E7%8C%9C%E6%95%B0%E5%AD%97

           中山美麗之島--數學討論區

http://bbs.nsysu.edu.tw/txtVersion/treasure/math/M.915200823.A.html

        誰說暴力不能解決問題 http://bsd.tscvs.ttct.edu.tw/~teach232/power.htm

 

七、                附件

1.        Program「深綠」:


import java.io.*;
public class GuessNumber
{
  private int[] answerSet = new int[10*9*8*7];
  public GuessNumber() {
    int index=0;
    for (int n1=0; n1<10; n1++)
    {
      for (int n2=0; n2<10; n2++)
      {
        if ( n2 == n1) continue;
        for (int n3=0; n3<10; n3++)
        {
          if (n3 == n2 || n3 == n1 ) continue;
          for (int n4=0; n4<10; n4++)
          {
            if ( n4==n1 || n4==n2 || n4==n3) continue;
            answerSet[index++] = n1*1000+n2*100+n3*10+n4;
          }
        }
      }
    }
    guess();
  }
  private void input(int number)
  {
    System.out.print( transform(number) + ", ?A?B = ");
    int a=0,b=0;
    try {
      BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
      String str  = br.readLine();
      while ( str.length() != 4 )
      {
        System.out.println("輸入錯誤, 格式為 ?A?B ");
        System.out.print( transform(number) + ", ?A?B = ");
        str = br.readLine();
      }
      a = str.charAt(0) - '0';
      b = str.charAt(2) - '0';
    }
    catch (IOException e)
    {
      System.out.println("輸入時發生不可預期的錯誤...");
      System.exit(0);
    }
    if (a == 4)
    {
      System.out.println("The answer is " + transform(number));  
      System.exit(0);
    }
    reduce(number,a,b);
  }
  private void guess()
  {
    for (int i=0; i< answerSet.length; i++)
    {
      if ( answerSet[i] == -1 ) continue;
      input ( answerSet[i]);
    }
    System.out.println("你騙人!! 根本沒這數字, ***!");
  }
  private void reduce(int number, int a, int b)
  {
    for (int i=0; i< answerSet.length;  i++)
    {
      if ( answerSet[i] == -1) continue;
      if (getA(number,answerSet[i]) != a || getB(number,answerSet[i]) != b )
        answerSet[i] = -1;
    }
    for (int i=0; i < answerSet.length; i++)
    {
      if ( answerSet[i] == -1) continue;
      System.out.print( transform(answerSet[i]) + " ");
    }
    System.out.println();
  }
  private int getA(int n1, int n2)
  {
    int a=0;
    String str1 = transform(n1);
    String str2 = transform(n2);
    for (int i=0; i<4; i++)
    {
      if (str1.charAt(i) == str2.charAt(i) )
        a++;
    }
    return a;
  }
  private String transform (int n)
  {
    if ( n < 1000 )
      return "0" + n;
    else
      return ""+n;
  }
  private int getB(int n1, int n2)
  {
    int b = 0;
    String str1 = transform(n1);
    String str2 = transform(n2);
    for (int i=0; i < 4; i++) {
      for (int j=0; j<4 ; j++) {
        if ( i == j) continue;
        if ( str1.charAt(i) == str2.charAt(j) )
          b++;
      }
    }
    return b;
  }
  public static void main (String [] args)
  {
    GuessNumber app = new GuessNumber();
  }
}

 


1.        「深綠」的解析:

A.        ConstructorGuessNumber()
    -> 建立候選解的answerSet[]
 
B.        MethodInput(int number)
-> 使用者輸入電腦猜的數據是幾A幾B,同時判斷若輸入為40B則顯示結束字串。
 
C.        MethodGuess()
 -> 電腦給出一組數據,並呼叫Input(),請使用者確認結果!
 
D.        Methodreduce(int number, int a, int b)
-> 與候選解比對,若幾A幾B與測試解相同則留下,否則設為-1(非正解)
 
E.        MethodgetA(int n1, int n2)
-> 利用transform()n1(測試值)n2(候選解)轉成字串,並比較出候選解和測試值比較有幾A?
 
F.        MethodgetB(int n1, int n2)
-> 利用transform()n1(測試值)n2"

"

Shortest Path

好像字數方面有限制 

只能Po出一些沒有完整

目錄第一章  前言第二章  圖論

第三章  最短路徑
3.1  
演算法具體的形式
3.2  
路徑權重問題
          3.2.1  
第一種情形

3.2.2   第二種情形

3.2.3   第三種情形

3.2.4    第四種情形

3.3   最短路徑演算法統整

第四章  Dijkstra’s algorithm

      4.1   由來與概述

      4.2   作法

      4.3   程式碼

      4.4   時間複雜度

      4.5   舉例實作

                    4.5.1最短距離

                    4.5.2最短路徑

第五章 結論

第六章 參考文獻

第一章   前言

    在演算法教課書中,有許多章節是有關於圖論、Shortest Path等演算法,教授也在課堂中多次講解,另外在上網路概論時,教授在教Open Shortest Path First(OSPF) ,在 OSPF 中, router 可以互相傳送資訊給對方,如同一個節點。在每個 router 在收集了足夠資訊之後,就可以建立起自己的「網路地圖」(事實上就是 Routing Table),就像最短路徑的圖表,進而知道要往哪個方向走才到得了目的地。由此可知OSPF有運用到Shortest Path概念,並且實際運用到網路中。因此我研究演算法的方向,朝著圖論中Shortest Path這個問題發展。

 第二章   圖論    1736年,瑞士數學家尤拉提出了知名的七座橋問題(Problem of the Seven Bridges of Konigsberg)。從此開啟圖論這一們學問。他與現在拓樸學、代數學、組合數學等學科關係極為密切。其應用也極為廣泛,延伸範圍有物理學、化學,電子學、生物學、經濟學、系統工程及計算機工程等學科領域。基於上述原因,圖論橫跨各大領域,涵蓋的範圍很廣,內容也很豐富,單就學術方面而言,已有很大的發展空間和研究價值。在日常生活中, 我們經常可以找到與圖論息息相關的內容因此引起許多人對圖論的重視與興趣。    圖論的問題基本上有兩大類,一是存在性問題,一是最佳化問題。圖論是一種較為直接明暸的演算法,當圖論與電腦做結合,發展出的演算法,讓圖論更蓬勃發展,利用圖論我們可以更有效地解決問題。     圖論中有許多的研究對象,如最小延伸樹問題minimum spanning treetransportation problemmaximum flow problemmatching assignment problem。而最短路徑問題(shortest path)則是圖論問題中最核心的問題,最短路徑(shortest path)問題是個很普遍也很實用的問題,就有如現今最實用的網路,在使用時也是加上了最短路徑的觀念,而最短路徑的觀念也更改了一些通訊協定的設定,在現今,許多研究者仍然對這個問題加以研究,因為在各個不同的限制,不同的假設下,每個最短路徑問題有許多的變化,最短路徑這個主題是有可能跟各種問題加以結合的,現今有關最短路徑問題有許多研究的種類。 第三章           最短路徑3.1   演算法具體的形式    最短路徑問題是圖論研究中的一個經典演算法問題,旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。演算法具體的形式包括:1.     確定起點的最短路徑問題:即已知起始結點,求最短路徑的問題。2.     確定終點的最短路徑問題:與確定起點的問題相反,該問題是已知終結  結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。3.     確定起點終點的最短路徑問題:即已知起點和終點,求兩結點之間的最短路徑。4.     全局最短路徑問題 - 求圖中所有的最短路徑。在不同的條件下,所發展出的最短路徑的問題也不盡相同。 3.2 路徑權重問題

    在最短路徑法的問題中,路徑權重問題也是會影響到最短路徑法,如果s,v1,v2,...,vi,..,vksvk的最短路徑,則s,v1,v2,...,visvi的最短路徑。列舉四種以下狀況:

 3.1.1   第一種情形:    所有的權重均為1。求s到其他所有點之最短路徑。利用BFS (Breadth First Search), Begin             Lable s with 0;          i ¬ 0;          if  ($ an unlabeled node adjacent to a node labeled i)  then             begin                   while ($ an unlabeled node adjacent to a node labeled i) do                          begin                                label this node i+1;                          end_of_while;                   i ¬ i+1;               go_to  if_statement;             end_of_if;end.  其複雜度:O(|E|)   // E為路徑總和的各數。 3.2.2   第二種情形:    所有的權重均為非負值(0或大於0)。求s到其他所有點之最短路徑。利用Dijstra’s algorithmnotation:   l(x)¬0,  label x with 0Begin      l(s) ¬ 0;l(v) ¬ w, "v¹s;   // w 代表無限大      T ¬ V;       // T為沒有走到的集合      P ¬ Æ;       // P為已經走過的集合      u ¬ s;      Repeat            for each vertex vÎT adjacent to u do                            l(v) ¬ min{l(v), l(u)+w(u,v)};             T ¬ T – {u};             P ¬ PÈ{u};             u ¬ a new vertex in T with min. l(u);       Until either (T = Æ) or (l(u)= w);end.其複雜度:O(|V|2)    // V為節點個數的總和。 3.2.3   第三種情形:權重可以為負,但迴路之總權重不為負值。求s到其他所有點之最短路徑。

利用Bellman and Ford algorithm


Umj = the length of a shortest path from s to j among all paths that contain at most m arcs.

       =                                      Begin                                m ¬ 0;                       U0s¬ 0;            U0j¬ w,  for all j¹s;    / / w代表無限大            repeat                   m ¬ m+1;                   Umj¬Ujm-1, "j,  1 £ j £ n;                   for each arc(K,j) in G do                         Umj = min{Ujm , UKm-1+w(K,j)};            until  (Umj = Ujm-1) or (m = n) for "jÎG;if  (m = n) and (Umj¹Ujm-1) then output(“exist negative    cycle!”)end.其複雜度:O(|V|·|E|) 3.2.4   第四種情形:任意二點之間的最短路徑。利用Floyd and Warshall algorithm   將各節點標記為1,2,3...,n

"大學入門 書面報告 學習及生涯規劃Teacher: Dr. Hsing Mei / 梅興老師           林坤建495511648資工一甲 自我介紹首先我要介紹我自己.我今年是20 (現在還是19 還年輕 XD).本來我是2005念高中畢業的.所以, 去年的9 月我已經來到台灣了.我爸爸處理所有事情因為我爸爸有工友在台灣.可是, 我進錯了!!!那時候,我不是近到大學,且來到特別班的語言中心.我在那邊念4-5個月, 然後會去印尼.2006的地7 月才來台灣真真的準備考台灣的大學.所以, 等到一年之後, 終於我可以來到輔仁大學, 當地一年級的大學生!!!我是168公分高, 54公斤重. 所以我長的廋廋矮矮的. 我覺得我很矮, 所以我很希煌還可以長高一點, 最少到175公分. 如果可以就到180公分啦!!!! 我皮膚有點黑黑的, 真可惜可是那算是代表有男生味道的!!! 男人一定要多出去, 不要留在家裡, 所以皮膚白白的!!!我喜歡做的事情就是玩電動玩具!!(進入資工的理由 XD), 我也是喜歡看漫畫, 唱歌, 聽音樂, , 花錢 XD!!!我喜歡吃的東西就是, 日本料理, 家裡自煮餐, fast-food(麥當勞什麼的). 可是我特別喜歡的東西就是日本的壽司(すし)!!!! 我超喜歡的!!! 我很希望有一天, 我可以來到日本吃日本的高級先做壽司!!剛才有說到日本吧, 所以那個算是我很想去的地方!  在那邊資訊發展的非常好,所以我希望到那邊去看看.. 可是最重要的理由就是….. 遊戲與美少女!!!!! 在日本非常多!!!! Hohohoho!!!!在我們的家庭, 有爸爸, 媽媽, 弟弟, 妹妹,  與我. 在我們家庭當中,有一個特別的東西, 就是 :我爸爸 47我媽媽 43 19我弟弟 18我妹妹 7 有沒有看到一些特別的東西?!!!!我們家裡的生肖, 4隻兔子, 一隻豬!!!          因為我是僑生, 所以我的小學, 國中, 高中生活就是不在台灣, 而是在印尼. 我當學生時候, 小學, 國中, 高中 時候, 就不再一樣的學校. 每一次都會不一樣. 為甚麼呢? 因為我們常常搬家. 因為一前工作不太好.          小學時候我在印尼的雅加達的ketapang小學(我不知道怎麼翻譯成中文, 在小學時候, 我們家庭會算是窮的家庭.我還記得, 每天媽媽會來到學校接我弟弟與我. 家庭環境也是不太好. 可是慢慢改變, 我小學六年級, 我們搬家到另外一個地方(靠近我國中學校).              國中時, 我與弟弟搬學到我們那時候離家不會很遠的學校. 那個學校名叫做IPEKA. 在那邊的生活, 我覺得很愉快因為有很多國中朋友也是住在我們家裡附近. 所一天天可以跟朋友一起去玩. 足球, 籃球, 羽毛球, 一起打電動玩具.  還記得印尼的大暴動在1998年嗎?  就是我在新家裡. 那時候, 我們的地方算是很安全的地方. 因為大部分是華人, 很少真真的印尼人, 所以他們不敢做什麼壞事. 可是我第三年級中, 我們有搬家靠近我們阿嬤的家. 因為我媽媽剛剛生了我妹妹, 所以身體一定要來照顧, 有我的妹妹當年還是很小,

"資工三甲 493511278 廖翊凱

Symmetric & Asymmetric Cryptosystem

  現今對於資料加密的演算法而言,主要可以分為兩種形式,一種是對稱式、一種是非對稱式的,這兩種有什麼差別呢?對稱式的加密演算法的加密機制只有發送方知道,而解密的機制則由接收方擁有,通常這兩個機制是相同的,所以稱為對稱式;非對稱式的則是接收方擁有解密金匙,而公開的發布加密金匙,任何人都可以傳加密的資料給他,但由於該加密演算法是不可逆的,只有接收方擁有暗門可以快速解密,所以這種演算法歸類為非對稱式的。

  優點 缺點
Symmetric .可鑑定發送方的身分.可確保資訊內容不被更   改 .收發雙方如何獲得彼此的加解密金匙.當有N個人時,每個人必須管理N-1把金匙
Asymmetric .解決Symmetric2的缺點.可做數位簽屬 .無法鑑定發送人身分

DES V.S. RSA  

RSA是由Rivest , Shamir , Adleman 這三位麻省理工學院的教授所提出的非對稱式的加密系統,雖然非對稱式的加密演算法有很多對稱式的加密演算法沒有的優點,且RSA的保密強度很高,但是這個系統的加密以及解密所耗費的時間太長,且在課程當中又有提到,所以接下來我是對DES這個對稱式加密演算法做研究。  

DES(Data Encryption Standard)是被美國國家標準局公布為資料加密標準的一種演算法,適用於敏感但非機密性資料,因為有人質疑美國安全局有後門可供快速解密,且其密鑰太短,相較於其他密鑰長的演算法,DES被用Brute Force的方式破解的機率較高,但是他能屹立二十餘年不是沒有道理的,一定有其優秀之處,而且相較於RSADES在加密與解密的過程相對的快很多。 

DES加密演算法  

在研究DES加密演算法之前,我們必須先了解下列兩種傳統式的基礎加密法

 1.   換位式(Transposition)  

簡單來說,換位式加密法就是將資料依照某種特定的規則重新排列,也就是弄亂資料排列的順序,其保密效果當然不高,但是可以搭配其他方法一起使用,仍然是一個好用的方法。

Ex: Algorithm is my favorite courseà my course Algorithm favorite is 

2.   替換式(Substitution)  

相較於換位式加密法改變排列順序,替換式加密法則是改變內容意義,他把資料中每一個字母都由另一種編碼方式取代,編碼的方式分兩種,固定長度與可變長度,固定長度的編碼方式就比如說A使用X代替、B使用Y代替,而可變長度的編碼方式就好像課本中提到的Huffman Encoding一樣。

Ex: Dr. Hsing Mei is my favorite teacherè  Es, Itjoh Nfj jt nz gbwpsjuf ufbdifs 

乘積式加密法

  單一方式的加密法的保密程度相當的有限,所以我們將多種加密方式拿來對一個資料連續使用,這種方式稱為乘積式加密法,我接下來要研究的DES就屬於乘積式加密法,他就是由換位式與替換式加密法交替使用的加密演算法,這邊要特別注意,換位式與替換式一定要交替使用,如果連續使用了兩個換位式,其保密程度其實增加不多。 

DES加密演算法

  首先將原本的資料分成64bits為一組,對每64bits進行初始換位,接著連續十六次不同的運算,再一次反初始換位,就產生加密後的資料了。  初始換位跟反初始換位就如同先前講到的換位式加密法,而中間連續十六次不同的運算則是將64bits的資料對半切割成LR各為32bits,經過每一次運算就產生新的LR,新的L就是原本的R,而新的R則是用原本的R跟密匙k作運算後再跟L作互斥得到的。

L(new) = RR(new) = L f( R , K )

密匙K在十六次的運算中都是不同的Input 64bits 的資料 M初始換位

 M à M0 (L0,R0)

加密運算 M0 à M1 (L1,R1)     ,      L1=R0  , R1= L0f(R0,K1)

加密運算 M1 à M2 (L2,R2)       ,     L2=R1  , R2= L1f(R1,K2)

                                       

                                     

                     

反初始換位 M16 à C得到密文C 

接下來來看f(R,K) 這個函數是做什麼的。

R(32bits)  à擴充換位 R’(48bits)  à R’K(48bits) à 選擇換位函數(32bits)

K1~K16 是十六個48bits的金匙對應著十六次反覆的加密運算,分別與進行擴充換位後的R作互斥運算,也就是說f()這個函數會先將R作擴充換位讓他變成48bits,再跟同樣為48bitsK作互斥,再藉由選擇換位函數變回32bits

 DES解密

  由於DES每個步驟所使用的加密方式都有其反函式可以將其復原,要解密其實只要將原本的步驟全部都反過來使用他的反函式就行了,加密跟解密都是類似的步驟,在執行上也有速度快的優點,如果我們所需保密的資料的保密度不是要求的非常嚴苛的話,可以考慮使用DES加密演算法。

 FEAL加密演算法

FEAL(Fast Data Encipherment Algorithm)快速資料加密法是一套類式DES的加密法,但是他特別強調的是每一回合的加密運算的安全度都比DES高,且每回合運算的cost都相當於DES,所以FEAL不用做到十六次就可以有跟DES相等的安全度,如果執行了十六次的運算,安全度肯定高於DES,所以在效率及安全度上都優於DESInput 64bits 的資料

 M作互斥運算 M à MK0 = M0(L0,R0)

加密運算 M0 à M1 (L1,R1)     ,      L1=R0  , R1= L0f(R0,K1)

加密運算 M1 à M2 (L2,R2)       ,     L2=R1  , R2= L1f(R1,K2) 

                                         

                           

                            

作互斥運算 M16 à M16K17 = C得到密文C

除了一開始的互斥跟結尾的互斥運算外,似乎中間的過程都一樣,其實FEALDES最大的差別就在於f(R,K)這個函數了。

"

上完通識後  我覺得人類有些自私 因為我們只顧著自己的利益   卻忽略大自然反撲的

能力,於是乎任意的使用天然資源,這導致天然資源耗盡  環境破壞  臭氧層破洞  溫室

效應   這些結果必須擔後果的不只是人類   動植物更是,所以我把通識課上的補充資料

po上來   想讓大家思考怎樣才是對環境、人類、動植物有利的生活方式

 

 

臭氧機認證標準 無人管

記者 鄭朝陽/專題報導 02/20 03:21 

    臭氧機成了家電市場的熱門產品,據本報記者查訪發現,衛生、環保和商品檢驗機關目前對這類產品既無國家標準或規範,也沒有效能認證的合格單位可供諮詢,環境品質文教基金會秘書長劉銘龍批評是「無政府狀態」,憂心消費者盲目購買,既當了冤大頭,還賠上健康;台大環工所教授於幼華更點名衛生署和環保署要挺身而出,為消費者的安全和權益把關。

    劉銘龍指出,臭氧(O3)是一種強氧化劑,法、德、瑞士等歐洲國家最早拿來處理自來水,作為自來水生飲的殺菌消毒利器,它改善了自來水加氯消毒會產生三氯甲烷致癌物的副作用,但很多人不知道,如果自來水的原水含鹵素離子過多,則可能和臭氧結合生成溴酸鹽等致癌物,因此,不是什麼水都可以用臭氧殺菌後生飲的。

    於幼華則說,生產臭氧機的業者各自吹噓自家產品有多靈光,但以時下開始流行的臭氧水龍頭來說,臭氧溶解於水的濃度要多高,臭氧水才具殺菌效果?是直接沖洗還是要浸泡才有消毒作用?時間又需多久?業者並未告知消費者,事實上,目前政府也沒有頒布相關規範可供依循,因此,若要標榜臭氧水可以分解蔬果殘留農藥,必須拿出有公信力的實證依據,可惜目前沒有標準和規範,業者的話有待商榷,消費者只能當白老鼠。

    於幼華表示,善用臭氧是很好的生活科技,政府應該訂定相關規範加以輔導、鼓勵,以造福民眾,但現在臭氧機氾濫,卻毫無把關,恐會有反效果。

    劉銘龍指出,低濃度的臭氧無色無味,高濃度時則有淡淡的魚腥味,而且當濃度過量時,不但對人體肺部有害,也汙染空氣,國內許多城市目前就有臭氧濃度過高的困擾。此外,以烘碗機為例,最好不要邊洗碗邊用烘碗機,因為當臭氧被加熱時,逸散速度快,吸進肺部有害健康。

 

『小百科』臭氧是什麼

鄭朝陽 02/20 03:21 

    臭氧分為地面臭氧和大氣臭氧兩種;前者主要來自車輛排放氮氧化物和碳氫化合物受日光的紫外線照射而產生,在0.3ppm濃度下,正常人曝露2小時會呼吸困難,達到2ppm會強烈咳嗽、體力衰退,10ppm時會發生肺水腫。

    大氣臭氧層位於地表上空約20~30公里間,濃度較高,它能阻隔對人體有害的紫外線大量照射下來。但臭氧層出現破洞,將使人類罹患皮膚癌的機率增加。市售的臭氧機則是以人為方式製造臭氧,利用其強氧化力達到殺菌效果。

 

對抗溫室效應 隨手關燈 年減3.6公斤CO2

林倖妃、黃如萍/台北報導 2005-02-17 10:12   

    京都議定書昨天生效,學者警告,民眾必須調整高耗能的生活習慣;環保署估算一天少用一小時冷氣機,一年可減少六公斤二氧化碳排放量,隨手關燈可減少三.六公斤排放量。

    義美食品總經理高志明語重心長地說,國內水價偏低,造成企業厲行節水也沒好處,缺水時卻和大家一起受苦,電價也有相同問題。企業能做的就是從水、電和廢棄物減量,國內若持續未採取有效措施降低二氧化碳排放量,整個社會都將面臨國際制裁。

    中原大學通識中心教授李河清表示,歐盟抑制二氧化碳排放量方面,不但二氧化碳排放有價化,且訂出罰則。若不遵守,二○○五年到二○○七年,每噸二氧化碳價錢四十歐元,預計二○○八年增加到一百歐元,顯見二氧化碳已成為有價商品。李河清認為,京都議定書的影響其實和每人息息相關,必須調整現今高耗能的習慣,提倡省能生活,少用電器用品、少使用電梯、多走路,給予環境善意回應。

 

    環保署估算,一天少使用一小時冷氣機,一年將減少六公斤二氧化碳排放量;若人人養成隨手關燈習慣,一年也可減少三.六公斤的二氧化碳排放。若能少開小汽車,改搭巴士或通勤電車,環保署指出,以每次一百公里計算,改搭五次巴士就可減少二六.六公斤二氧化碳排放,改搭五次電車更可以減少二九.四公斤,單人駕駛汽車比搭乘大眾運輸,每人每公里多八倍的二氧化碳排放。

 

地球暖化 烏魚游不到南台灣

本報記者汪文豪 02/17 03:21 

                                                     科學界最近證實,台灣近年烏魚漁獲量大減,是因為地球暖化,台灣海峽寒、暖洋流交會發生變化,造成烏魚游來南台灣的數量大減,漁港不再有以往豐收場面。

本報資料照片/記者謝進盛攝影

 

    俗稱「烏金」的烏魚,過去是本省西南沿海漁民冬天恭迎的財神爺;近些年烏魚捕獲數量大減到過去十分之一都不到,漁民怪罪大陸同業攔魚炸魚,除了這個原因,科學證據更發現,地球暖化、海水增溫,讓冬天南下的大陸沿岸流威力減弱,下不到西南台灣,烏魚的洄游、覓食、生殖習性都被迫改變,台灣漁民自然「烏金」黯淡。

    研究烏魚的海洋大學漁業系教授李國添說,氣象衛星資料顯示,近十年來台灣周邊海域水溫約上升攝氏一至一點五度,已達生態破壞的「巨幅」程度,影響所及,海域生物的大調整是一定的。李國添說,烏魚是洄游性的魚種,以河川出海口豐富的有機物與底泥上的藻類為食源;中國沿海的烏魚,高達九成五在長江出海口取食,是最重要的覓食地。但李國添說,海水增溫前烏魚的繁殖地在台灣海峽,冬季繁殖期,烏魚會隨著向南方流動的大陸沿岸流,從長江口南下找尋產卵地點。

    李國添表示,彰化以南的台灣海峽,不但海底地形平緩,加上東北季風較吹不到,風浪比較小,烏魚在此排卵、體外受精成功的機會較高,因此多選擇彰化以南的海域繁殖;大陸沿海則因風浪較大,產卵受精的失敗率高,不是烏魚理想的繁殖地。

    每年冬至前後,這道大陸沿岸流隨著冷氣團從長江口向南流,冷氣團威力越強,向南流得越遠,最遠可到高、屏外海,與來自南方的黑潮交會,冷、暖水交會產生豐富的營養鹽,加上有利的海床地形,吸引大批烏魚來此產卵;此時雌烏魚卵囊完全成熟,生殖品質相當好。

    李國添說,地球增溫後,大陸沿岸流勢力只能下到閩江口、馬祖一帶,無法再南下。大批烏魚群集馬祖海域,不巧碰上大陸漁民以炸魚方式捕魚,烏魚族群被大量炸死,剩下能夠游到高屏外海的成魚大減,當然影響烏魚漁獲。

 

全球暖化 台灣加害 也受害

記者薛荷玉/報導 02/16 03:17 

    面對全球暖化,台灣既是「加害者」,也是「受害者」!台灣雖為蕞爾小島,但二氧化碳的排放量卻驚人,排名全球第22,占總量1%;我國官方報告「國家通訊」指出,海平面只要上升1公尺,台南市安平區就有一半淹沒在海水中;氣溫上升也會對台灣的農漁業造成重大衝擊,年損失將超過台幣400億元,占GDP(國內生產毛額)0.6%

    環境品質文教基金會秘書長劉銘龍提出警訊,台灣過去幾年不是旱災,就是水災,溫室效應持續發威之下,未來必是旱澇頻仍,劇烈天氣也就是熱得半死或冷得要命的天氣,也將成為常態;因此,台灣現下最重要的是發展防災、救災、保險體系,削減二氧化碳排放量是必須做的事,但遠水恐救不了近火。

    「國家通訊」是我國政府有關溫室氣體管制的正式報告,其中有一章特別描述溫室效應的衝擊,文中指出,台灣是亞熱帶的海島型環境,對氣候變化產生的影響特別敏感、脆弱。根據目前海平面上升的速率計算,只要再過66年,台灣周圍的海平面就會上升1公尺;按「國家通訊」估算,屆時台南市安平區就有50%土地要消失,宜蘭的五結鄉也有27.2%的土地將淹沒在海平面之下;屆時,嘉南平原將有171公頃土地被海水淹沒,等到海平面上升4公尺,嘉南沿海更有374公頃土地消失。

    值得注意的是,台灣「陸沈」比其他國家來得更快。除了溫室效應外,台灣西海岸還有超抽地下水等問題造生的地層下陷,以台南及宜蘭為例,每年的地層下陷本來就有1公分,再加上溫室效應導致的海平面上升因素,海平面每年相對於陸地就會上升約1.5公分

    國家通訊指出,溫室效應還會導致水資源減少,50年後,台灣的年逕流量將減少4%,梅雨及颱風帶來的降雨都會明顯減少。此外,氣溫上升也將對農漁業帶來重大衝擊,稻米、玉米的產量都會減少,疫病也會增加。研究顯示,氣溫每上升攝氏1度,豬隻的食量就會降低5%;在雞、鴨等家禽部分,氣溫上升將造成肉雞重量減輕、蛋雞不下蛋。

 

防地球暖化 盯緊六大元凶

記者 黃玉珍、何佩儒 02/15 04:39 

    「北半球氣溫急速下降,避難人潮正往南半球移,溫度要降到氣候達到平衡為止.... 」這是電影「明天過後」中,科學家對政客提出警告的一幕,不久前,南亞發生的大海嘯,更讓「明天過後」的虛擬景況,深深刻劃在人們心中。

    其實,早就有許多科學家觀察到地球的溫度已發生變化,可能導致氣溫失序、冰山融化、海平面上升、小島滅頂等嚴重後果。

 

1997年,聯合國氣候變化綱要公約締約國在日本制定出京都議定書,管制讓地球溫暖化的主要六種氣體,包括:二氧化碳、甲烷、氧化亞氮、氟化烴、全氟化碳及六氟化硫。

 

台灣排放PFC 將冠全球

    其中,多數人不瞭解的全氟化碳(PFC),正是半導體產業及面板業在鉛洗製程所使用的主要氣體,雖然其排放量相當低,但對地球溫暖化的效應,是二氧化碳的數千倍。目前台灣光電產業正迎頭趕上南韓,預估今年會成為全球最大生產國,也意味著台灣的PFC排放量,也將居全球首位。

    環保署官員表示,國內光電業者已與日本、南韓業者簽定PFC減量排放協定。而半導體產業方面,台灣半導體業者加入全球半導體協會時,即被要求要進行PFC減量。目前半導體業者主要是透過回收、裂解,降低對地球溫暖化的影響。

    而中鋼在加入世界鋼鐵協會時,也被要求要進行二氧化碳的削減計畫。也就是說,台灣廠商要進入國際市場,不必等到各國政府的要求,自然要接受相關產業的共同規範,進行溫室氣體的排放減量。

    京都議定書於2005216生效,各締約國的減量目標是,20082012年,上述六種溫室氣體排放量平均削減到比1990年排放量低5.2%的水準。

    美國至今尚未簽訂京都議定書,一度曾使不少國家抱持觀望態度。但在去年11月俄羅斯簽約後,由於俄國的溫室氣體排放量占全球排放量的17.4%,俄國加入後,讓實際簽約國(超過120國)和排放量(55%)都達到實施議定書的門檻,即使美國(占全球排放量的36%)沒有加入,仍然可以生效,大部分國家才開始正視這個問題。

 

京都議定書實施後,影響經濟層面最大的是高耗能產業的投資生產,將受到限制。

 

鋼鐵石化電機 衝擊大

    根據工業局資料顯示,目前我國溫室氣體排放量占全球總排放量1%左右,排名第22名。京都議定書實施後受到衝擊的產業中,以鋼鐵、石化和電機電子最大;其次是人纖、水泥和造紙。其中電機電子產業中,以發電廠影響最大,民間電子業的溫室氣體排放量並不多。

    目前我國在水泥、造紙和人纖的新增投資案已明顯減少;至於鋼鐵和石化方面,最近以台塑籌設大煉鋼廠和中油設置石化專區,最為顯著。兩家公司同時看上雲林離島工業區的新興區,主要是新興區開發時已做好二氧化碳排放的總量管制,不必再做環境影響評估,可以節省設廠時間。

    工業局表示,個別建廠仍要再做環評。鋼鐵和石化業的二氧化碳排放量大致相同,而且以台灣島內的氣體排放總量管制來看,廠區設在那裡都一樣。

    但官員也強調,不會以京都議定書的規定,限制新的投資案。畢竟台灣不是京都議定書的優先管制對象,而且近年來排放量較大的產業中,新增投資案不多,僅一、二個大型投資案,只要管制得當,對整體排放量影響不大。

    官員說:「近年來產業外移嚴重,政府鼓勵投資都來不及,為控制氣體排放因素而限制投資,機率非常低。」

    但是在京都議定書生效的壓力下,鋼鐵和石化等二氧化碳排放量大的產業,面臨的環評壓力相對較大。從台塑和中油都要搶進新興區投資的案例,讓人納悶。和歐盟、日、韓等國相較,可以看出我政府和企業界對京都議定書的陌生及觀望程度,等到即將實施,才急著要找出兩大投資案都可進駐、又不需做環評的兩全其美方案。

    台灣科大教授顧洋不久前到阿根廷參加京都議定書工作會報,他直言點出政府和產業界面對京都議定書實施的盲點是:「政府多頭馬車、企業弄不清楚國際規範」。

 

做好總量管制 度難關

    顧洋說,日本政府已支持不少財團法人,針對京都議定書實施內容展開宣導、教育,並設立全國網站,輔導產業改善製程,南韓也由政府積極向企業界宣導,但反觀台灣,目前與京都議定書相關的單位有工業局、環保署、能源局等,大家各做各的,力量分散,沒有統合的情況下,使企業界也不知道要怎麼辦。

    日前,石化業即曾為此要求政府,不可以因為京都議定書的實施,而限制產業投資。政府雖強調不會因京都議定書而限制產業投資,但已可看出,京都議定書生效後,實質上已成為新投資案的重要影響因素。

 

生技辭典》京都議定書

    各國簽署京都議定書是為了抑制人為溫室氣體排放,以防制地球氣候惡化,主要內容是1997年「聯合國氣候變化綱要公約(UN-FCCC)遞約國」,於日本京都召開第三次締約國大會時所擬定。

    京都議定書列入管制的氣體計有六種,分別是二氧化碳、甲烷等,並訂定六種溫室氣體排放減量目標。依據京都議定書的減量目標,六溫室氣體排放量應於2008年至2012年之期限內,平均應減少到比1990年排放量低5.2%的水平。

 

   

"

資工三甲  493511199  葉思妤  

原則上我的Lab3與Lab2的差別並不大,都是用Backtracking的方法來實作......只有做一些小部分的細部修改(其中包括矩陣印出的美化與傳入值的修改)。
以下就是我Lab3的演算法說明與分析:
首先用i/o讀檔將數讀題目的矩陣依序填入一個size81array裡,然後開始尋找空格處,一旦找到就與此空格所在之那一列、行或小九宮格做數字比對。如果已有相同的數字了,就再加一,以此類推……直到找到一個在既有數字中都沒有出現的值就可以將它暫填入此空格中,並將此格的位置存入堆疊,然後繼續下一個空格處的測試;如測試數字已超出範圍,則須從堆疊中找出上一次填入數字的位置再次重新測試。 另外,我是以執行時間來作為效能的評估


大致上的寫法:

OpenFile(filename);                     //讀取檔案
     array[col] = (int)read.charAt(current) - 48 ;//存進陣列
getSpace(int position)   //尋找空格
compare(int position)   //進行 行,列,小九宮格的數字比對
push(int sp)                //把取得的位置放入堆疊中
pop()                        //取出堆疊中的位置
position = pop() ;           //回去上一個位置
ToltalTime=EndTime-StartTime;   //計算執行時間

結果:


Answer

 - - - - - - - - - - - - -

 | 7 8 1 | 6 3 2 | 9 4 5 |

 | 9 5 2 | 7 1 4 | 6 3 8 |

 | 4 3 6 | 8 9 5 | 7 1 2 |

 - - - - - - - - - - - - -

 | 2 4 9 | 3 7 6 | 8 5 1 |

 | 6 7 3 | 5 8 1 | 2 9 4 |

 | 5 1 8 | 4 2 9 | 3 6 7 |

 - - - - - - - - - - - - -

 | 1 9 4 | 2 6 7 | 5 8 3 |

 | 8 6 7 | 1 5 3 | 4 2 9 |

 | 3 2 5 | 9 4 8 | 1 7 6 |

 - - - - - - - - - - - - -

共花費:1633524 nano seconds

Answer

 - - - - - - - - - - - - -

 | 9 8 2 | 5 4 7 | 3 6 1 |

 | 4 6 5 | 1 8 3 | 9 2 7 |

 | 7 3 1 | 9 2 6 | 8 4 5 |

 - - - - - - - - - - - - -

 | 3 2 6 | 8 1 5 | 4 7 9 |

 | 8 7 9 | 3 6 4 | 5 1 2 |

 | 5 1 4 | 2 7 9 | 6 8 3 |

 - - - - - - - - - - - - -

 | 1 5 7 | 4 9 8 | 2 3 6 |

 | 2 4 3 | 6 5 1 | 7 9 8 |

 | 6 9 8 | 7 3 2 | 1 5 4 |

 - - - - - - - - - - - - -

共花費:2230179 nano seconds

Answer

 - - - - - - - - - - - - -

 | 4 6 5 | 8 9 3 | 2 7 1 |

 | 8 2 7 | 1 5 4 | 6 3 9 |

 | 1 9 3 | 7 2 6 | 4 8 5 |

 - - - - - - - - - - - - -

 | 6 1 8 | 2 7 9 | 3 5 4 |

 | 9 5 4 | 3 6 1 | 7 2 8 |

 | 3 7 2 | 4 8 5 | 1 9 6 |

 - - - - - - - - - - - - -

 | 5 3 9 | 6 4 2 | 8 1 7 |

 | 2 8 6 | 9 1 7 | 5 4 3 |

 | 7 4 1 | 5 3 8 | 9 6 2 |

 - - - - - - - - - - - - -

共花費:1785117 nano seconds

Answer

 - - - - - - - - - - - - -

 | 8 1 7 | 2 6 4 | 5 3 9 |

 | 9 5 2 | 7 8 3 | 1 4 6 |

 | 3 6 4 | 9 1 5 | 2 8 7 |

 - - - - - - - - - - - - -

 | 1 7 6 | 3 9 8 | 4 2 5 |

 | 4 2 8 | 5 7 6 | 9 1 3 |

 | 5 3 9 | 1 4 2 | 7 6 8 |

 - - - - - - - - - - - - -

 | 6 9 3 | 4 5 1 | 8 7 2 |

 | 2 4 5 | 8 3 7 | 6 9 1 |

 | 7 8 1 | 6 2 9 | 3 5 4 |

 - - - - - - - - - - - - -

共花費:2799174 nano seconds

Answer

 - - - - - - - - - - - - -

 | 5 7 8 | 9 6 2 | 3 1 4 |

 | 6 1 9 | 4 5 3 | 8 7 2 |

 | 3 2 4 | 1 8 7 | 5 6 9 |

 - - - - - - - - - - - - -

 | 1 9 6 | 7 3 5 | 2 4 8 |

 | 2 5 3 | 6 4 8 | 1 9 7 |

 | 8 4 7 | 2 9 1 | 6 5 3 |

 - - - - - - - - - - - - -

 | 7 8 5 | 3 1 9 | 4 2 6 |

 | 9 6 1 | 8 2 4 | 7 3 5 |

 | 4 3 2 | 5 7 6 | 9 8 1 |

 - - - - - - - - - - - - -

共花費:199882790 nano seconds

Answer

 - - - - - - - - - - - - -

 | 6 8 2 | 1 3 7 | 4 9 5 |

 | 5 4 7 | 8 2 9 | 3 6 1 |

 | 3 9 1 | 4 5 6 | 7 2 8 |

 - - - - - - - - - - - - -

 | 8 1 6 | 7 9 4 | 5 3 2 |

 | 9 3 5 | 2 8 1 | 6 7 4 |

 | 2 7 4 | 5 6 3 | 8 1 9 |

 - - - - - - - - - - - - -

 | 4 2 9 | 6 7 8 | 1 5 3 |

 | 1 6 3 | 9 4 5 | 2 8 7 |

 | 7 5 8 | 3 1 2 | 9 4 6 |

 - - - - - - - - - - - - -

共花費:10661939 nano seconds

Answer

 - - - - - - - - - - - - -

 | 3 1 4 | 7 9 5 | 6 8 2 |

 | 9 2 7 | 8 3 6 | 4 5 1 |

 | 8 6 5 | 2 4 1 | 7 3 9 |

 - - - - - - - - - - - - -

 | 1 9 8 | 3 6 2 | 5 4 7 |

 | 7 5 6 | 4 8 9 | 2 1 3 |

 | 4 3 2 | 5 1 7 | 8 9 6 |

 - - - - - - - - - - - - -

 | 6 4 3 | 9 7 8 | 1 2 5 |

 | 5 8 1 | 6 2 3 | 9 7 4 |

 | 2 7 9 | 1 5 4 | 3 6 8 |

 - - - - - - - - - - - - -

共花費:98162101 nano seconds

Answer

 - - - - - - - - - - - - -

 | 3 8 2 | 6 5 1 | 4 7 9 |

 | 7 9 5 | 3 8 4 | 1 2 6 |

 | 4 1 6 | 9 2 7 | 8 3 5 |

 - - - - - - - - - - - - -

 | 6 2 9 | 1 7 5 | 3 4 8 |

 | 1 7 4 | 8 6 3 | 9 5 2 |

 | 8 5 3 | 4 9 2 | 7 6 1 |

 - - - - - - - - - - - - -

 | 9 3 8 | 2 4 6 | 5 1 7 |

 | 5 6 1 | 7 3 8 | 2 9 4 |

 | 2 4 7 | 5 1 9 | 6 8 3 |

 - - - - - - - - - - - - -

共花費:33093204 nano seconds

Answer

 - - - - - - - - - - - - -

 | 7 2 8 | 1 4 5 | 3 9 6 |

 | 9 6 5 | 7 8 3 | 4 2 1 |

 | 3 4 1 | 9 6 2 | 7 5 8 |

 - - - - - - - - - - - - -

 | 6 1 9 | 3 2 4 | 8 7 5 |

 | 8 5 2 | 6 9 7 | 1 4 3 |

 | 4 7 3 | 5 1 8 | 9 6 2 |

 - - - - - - - - - - - - -

 | 1 9 4 | 8 5 6 | 2 3 7 |

 | 2 3 6 | 4 7 1 | 5 8 9 |

 | 5 8 7 | 2 3 9 | 6 1 4 |

 - - - - - - - - - - - - -

共花費:2866798 nano seconds

Answer

 - - - - - - - - - - - - -

 | 4 5 7 | 1 2 3 | 6 8 9 |

 | 3 2 8 | 5 9 6 | 7 4 1 |

 | 1 9 6 | 7 4 8 | 2 3 5 |

 - - - - - - - - - - - - -

 | 8 3 9 | 4 6 1 | 5 2 7 |

 | 2 4 5 | 9 3 7 | 1 6 8 |

 | 7 6 1 | 2 8 5 | 3 9 4 |

 - - - - - - - - - - - - -

 | 5 8 2 | 3 1 9 | 4 7 6 |

 | 9 1 4 | 6 7 2 | 8 5 3 |

 | 6 7 3 | 8 5 4 | 9 1 2 |

 - - - - - - - - - - - - -

共花費:16663373 nano seconds

Answer

 - - - - - - - - - - - - -

 | 6 2 5 | 8 3 7 | 9 1 4 |

 | 3 1 9 | 4 2 6 | 5 8 7 |

 | 7 4 8 | 9 5 1 | 6 3 2 |

 - - - - - - - - - - - - -

 | 2 7 6 | 1 9 4 | 3 5 8 |

 | 8 9 4 | 3 7 5 | 1 2 6 |

 | 5 3 1 | 6 8 2 | 7 4 9 |

 - - - - - - - - - - - - -

 | 1 8 7 | 2 6 3 | 4 9 5 |

 | 4 6 2 | 5 1 9 | 8 7 3 |

 | 9 5 3 | 7 4 8 | 2 6 1 |

 - - - - - - - - - - - - -

共花費:15162864 nano seconds

Answer

 - - - - - - - - - - - - -

 | 5 9 4 | 7 3 6 | 2 8 1 |

 | 6 7 1 | 2 9 8 | 4 3 5 |

 | 2 3 8 | 4 1 5 | 7 6 9 |

 - - - - - - - - - - - - -

 | 3 4 6 | 8 7 1 | 5 9 2 |

 | 1 2 5 | 6 4 9 | 8 7 3 |

 | 7 8 9 | 5 2 3 | 1 4 6 |

 - - - - - - - - - - - - -

 | 8 6 2 | 3 5 7 | 9 1 4 |

 | 9 5 7 | 1 6 4 | 3 2 8 |

 | 4 1 3 | 9 8 2 | 6 5 7 |

 - - - - - - - - - - - - -

共花費:36265058 nano seconds

"

剛好專題的主題Peer to Peer media stream跟網路相關~分享一下

...............................................................................................

P2P的發展歷史來看,從第一個P2P分享軟體Napster

接者Gnutella的出現,一直到KazzaGrokstereDonkey

還有國內的KuroezPeer,還有目前最熱門以BitTorrent為基礎的 

P2P檔案分享軟體,都顯示P2P是一個不斷發展的趨勢,使用的

人數越多,威力越是強大,相信在各種方面的應用也會越來越廣

泛。下面我們將選出三個最具代表性的P2P軟體,簡單介紹並分

別敘述他們的架構。


2.1 Napster

 

                第一個P2P分享軟體,1999年由波士頓的Northeatern大學

的學生Shawn Fanning所創造,讓宿舍裡的同學們,可以交換硬碟

裡所有願意跟其他人分享的檔案,這個軟體在大學生圈裡迅速地

廣泛流傳開來,P2P熱潮也開始蔓延到全世界。

Figure 01. Napster架構圖

架構及運作方式:

 i. 連線

安裝Napster軟體,做為Napster P2P網路的Peer(Client)

然後連上「事先設定」的伺服器。Napster Client端會將使

                     用者端的相關資料以及分享檔案列表傳送給Server端。

ii. 搜尋

當你想搜尋檔案時,會將查詢要求傳送給Server,然後 

Server會尋找本身的資料庫的檔案列表,並將結果回傳回

                     去。

iii. 下載

收到Server的結果後,你可以選擇想下載的檔案,並直接

連線至對方(Peer),進行Peer-to-Peer的傳送,而無須透過 

                     Server的介入。

 2.2. Gnutella

 

AOL的子公司NullSoft開發出來的程式,與Napster不同

的地方在於,不需要中央伺服器就可以與其他peer作檔案

                    交換。

 架構及運作方式

 i. 連線

安裝Gnutella軟體,做為Gnutella P2P網路的Peer( 

Server 也是Client),沒有任何事先設定的伺服器來連結,因

此對Gnutella網路可以說一無所知。因此,需要知道至少

一台PeerIP 位址和Port,做為第一個連線(起始點)。接

                    著有三件事會發生:

                     i 你宣布你的存在

    

                     ii. 他會告知其他Peers

                    iii. 每個Peer回訊息給你

                   藉由和其他交換資訊以瞭解整個Gnutella P2P 網路。

ii. 搜尋

當你想搜尋檔案時,會將查詢要求傳送給你有直接連線

Peer(s),這些Peer(s)會繼續將你的要求傳送給他們有直

接連線的其他Peer(s),然後繼續反覆下去。在這散佈過

程的每一台Peer也都會尋找本身的檔案列表,並將結果

                      回傳回去,如果找不到符合結果,無須回報。

iii. 下載

陸續收到Peer(s)的結果後,你可以選擇想下載的檔案,

並直接連線至對(Peer),進行P2P 的傳送,而無須透過

網路上其他Peer(s)的介入。如  果連線失敗,則很有

可能是對方在防火牆之後,Gnutella會重新發送一個下載

要求(Push 下載),並以Step 2的方式散佈此要求, 對方 

(擁有你想下載的檔案)會嘗試從他那邊直接連線回來,進

                     P2P傳送。 

2.3 Bittorrent

            

    Bram Cohen所創造的新一代P2P技術,比起其他P2P protocol

 有更多p2p的優點,當越多人下載時,速度越快。Figure 03. BitTorrent架構圖

架構及運作方式

i. 作種

正在下載還沒完成的用戶稱之為下載者 (Peer)是已經

 完成的用戶則稱之上載者或種子 (Seed)發佈檔案的方

式是由發佈者根據要發佈的檔案,產生一個副檔名

"torrent" 的檔案,"torrent” 檔中包含 Tracker 位置、要發

佈的檔案之名稱、大小與片斷細值等,由發佈者 

web ftp 的站台將 "torrent" 檔散佈給想要抓檔案的

                    使用者

ii. 連接

想要下載檔案的人,經由 bbsweb上的論壇或是搜尋檔

案的名稱拿到所要下載檔案的"torrent” 檔,再根據torrent 

檔連接到tracker伺服器

Tracker 與下載者之間是使用

"Abstract
ZigBee
是在 2002 8 月由多家無線傳輸業者及網路、通訊業者共同發起的 ZigBee Alliance 所提出,
這項技術建構在 IEEE 802.15.4 之上,希望提供一項低用電、低成本、
高可靠度的無線傳輸技術。
[
註一] ZigBee Alliance 成員包含 MotorolaSamsungPhilipsMaxStream 等,詳請可參考 [1]
值得一提的是,成員中還包括了中華民國工研院和資策會!

What is ZigBee
ZigBee
一詞源自工蜂在發現哪裡有花粉時,會轉圈跳舞告知其他伙伴,
這種舞蹈叫 Zigzag,混合代表蜜蜂的 Bee 後,就創造出了 ZigBee 這個名詞。
[
註二]ZigBee 在正式定名之前曾被稱做:PURLnetRF-EasyLinkRF-LiteHomeRFLiteFirefly 等等,
在早期的文件及 Paper 中可能會看到這些稱呼。 

Why ZigBee
ZigBee
是取 IEEE 802.15.4 Physical LayerMAC Layer 的基礎,
再由 ZigBee Alliance 自行定義 Network/Security LayerApplication Layer 所完成的。
目標是提供低用電、低成本、高可靠度的無線傳輸技術,並充份利用於 WPAN (Wireless Personal Area Network) 中,
[
註三]也有部份文件稱 WHAN (Wireless Home Area Network),但我們以 IEEE 定義的為準。
ZigBee
的用途主要用在短距離的 data 無線傳輸,為與 BluetoothWiFi 做區隔,
ZigBee
的頻寬僅有最高 250KB/s,所以並不合適做 voiceimage、甚至 video 的傳輸,
也正因如此,ZigBee 要比其他的無線傳輸標準要來的省電、低廉許多。
ZigBee frame architecture

fig1. ZigBee protocol stack #reference: ZigBee Alliance Manual

Infrastructure
ZigBee
的節點架構中,共分 FFD (Full Function Device;稱全配)RFD (Reduced Function Device;稱簡配)
以及 Coordinator (調協節點;扮演 RepeaterRouter 等角色),其中 FFD RFD 的功能主要差別在於:
1. FFD
可用任何 topology 連接,RFD 只能採 Star 拓樸做連接。
2. FFD
可當 coodinatorRFD 則只能當單純的 node
3. FFD
可與網路中任何 node connecting,但 RFD 只能與 coodinator 溝通。
那為什麼會有 FFD RFD 這兩種角色的分別?主要還是為了降低成本!
以節點的 protocol stack 所需的記憶體為例,FFD 需要 32KB 的空間容納 (其實已經非常省成本了)
RFD 僅需 4KB!運算上也都只需要 8bit 的處理器 ( 8051) 即可,所以 ZigBee 可以達到非常低成本的目要!

Main applications of ZigBee
ZigBee
主要應用於家庭個人網路中,取代紅外線遙控器是目前最可能第一個被廣泛使用的,
其他如家庭數位化、安全監控、物流追蹤、居家照護等,都是 ZigBee 想涉獵的範疇,
在台灣,2005 7 月,國家科學博物館利用 ZigBee 建立了一套定位導覽系統,
他們在每個需要導覽的參觀者中,配戴一個 Badge (標記),透過 Badge 傳送目前參觀者的位置給 Sensor node
並經由 RouterGateway 等傳送至 ServerServer 再回傳目前參觀者面前的展覽品資訊給播放器,
如此的架構中總共用了 150 Sensor node Router6 Gateway,可提供 8000 的服務範圍
梅老師和各位同學有機會可以去使用看看這套導覽系統,處理據說速度非常快,且有 99% 以上的正確率。
ZigBee Alliance
所提供的應用示意圖:
fig2. Applications in ZigBee network # reference: ZigBee Alliance Manuel

Features of ZigBee
如同前述的,ZigBee 僅需簡單的處理單元和 4-32KB 的系統記憶體,除此之外,
ZigBee network
中最多可使用 16-bit 的節點數,也就是有 65,536 個節點數,
不過這還是 ZigBee Alliance 濃縮過的個數 (稱為 Short address),在 IEEE 802.15.4 的標準定義中,
其實是允許 64-bit 的節點數,這已經是接近無限大的節點數了!
而在頻寬部份,前面也有提到,由於屬性定位不同的關係,所以 ZigBee 僅有 20-250 KB/s 的頻寬,
傳輸距離部份則是跟 BluetoothWiFi 旗鼓相當,約 100m 內皆可。
另外一個與眾不同的特色是,無線傳輸基本上是沒有發射角度的,如 BluetoothWiFi 都是無方向性的,
ZigBee 也提供方位性功能來供選用,這對於一些特殊的應用上 (如槍靶?) 確實滿有用處的。
最後是頻段的部份,ZigBee 可使用的頻段有 868MHz915MHz2.4GHz 三個頻段:
1. 868MHz
:僅 1 channel20KB/s,目前為歐洲地區採用,使用 BPSK 調變
2. 915MHz
:共10 channel40KB/s,目前為美國地區採用,使用 BPSK 調變
3. 2.4GHz
:共16 channel250KB/s,全球皆適用,使用 QPSK 調變
而為了降低與同頻段的其他無線應用的互相干擾,ZigBee DSSS (Direct Sequence Spread Spectrum;直接展頻法)

Topology Model
ZigBee
常見的拓樸型態有 Star (星狀)Mesh (網狀)Hybrid (混合)Cluster Tree (叢集樹)Cluster Start (叢集星)
P2P (Peer-to-Peer;點對點連接,如電視配電視機遙控器) 幾種。

Transfer
ZigBee
提供了三種傳輸方法:
1.
反覆性傳輸:如溫度每增減一度就回報一次
2.
間歇性傳輸:如照明開關,為不定期使用的
3.
週期性傳輸:如滑鼠每秒都必須回報目前的座標對應位址

Rreliability
ZigBee 網路中有一個以上的 node 需要傳輸時,ZigBee 採用無線傳輸常用的 CSMA/CA
(Carrier Sense Multiple Access with Collision Avoidance)
TDMA (Time Division Multiple Acess) 兩種技術,
CSMA/CD
TDMA 技術因為屬比較基本的觀念,本文在此就不多做敘述,有興趣的同學可以參考 [2][3]
另外為提高 ZigBee 傳輸的可靠性,ZigBee 採交握式傳輸 (Handshaking),意即 receiver 收到資料後,
會回送 ACK frame (Acknowledgement) Sender,以表示已收到訊息,否則 Sender 會一直重發,
直到收到 ACK frame 為止。
最後是安全性部份,ZigBee 採用 128bits  AES (Advanced Encryption Standard),詳細介紹可參考 [4]

Comparing with other wireless techniques

  ZigBee 802.15.4 GSM/GPRS CDMA/1xRTT Wi-Fi 802.11b Bluetooth "

"

BILL GATES: Well, it's great to be here. As you heard from some of your alums, Waterloo has contributed an amazing amount to Microsoft. But what I really want to focus on today is the future. How the software industry is going to make more breakthroughs in these next 10 years than it's made in the last 30, and how that software is really going to transform not just what we think about as the computer industry, but the way that everything is done. The way people design products, the way they communicate, the way they collaborate, the way they understand their business activities, and even extending out into education and the things we do as consumers, film, music, creativity all reshaped because the software is becoming a lot better.

Now, this dream of software as a tool of empowerment certainly goes back to the very beginning of Microsoft. That's a long time ago. We're celebrating our 30th anniversary this year. That means Microsoft has been in business longer than most of you are old. So, a long time. Big computers back then were very large and expensive, and there were very few of them. And there was no software industry. And it was actually a wild idea that the technology of the microprocessor would change the character of computing, and that the software would be the key element to bring that to life. Even Intel, which is an unbelievable company that was driving forward to actually create the engine that would make this possible, didn't see how it would be used. And so, myself and my fellow student, Paul Allen, had an idea that we could come in and provide the software. And, in fact, instead of the hardware and software being designed together by one company, that we'd allow all the different companies that wanted to make the hardware to match up, and have our software then provide a common interface, so we could really get a software industry going.

The idea of the software industry is really a pretty simple thing. You need to have enough volume of machines out there so that somebody can invest literally tens of millions in building a piece of software, and yet sell it for only a few hundred dollars and still make a profit doing that. And that means you've got to have millions of machines, particularly if you want people to be able to do very specialized software for different types of businesses, different types of activities. So, that did not exist, the computer industry rewrote its software all the time, there weren't this breadth of applications. And, in fact, it wasn't an industry that employs a lot of people, or existed in most countries.

The idea of the PC as an individual tool changed that, and we started a cycle, which was the more software we got, the more attractive the machine was, that sold more. The more we sold, the more the price could come down because these things are very volume sensitive, and as the price came down that further made it make sense to write more variety of software. And so that cycle got going. In fact, today for every dollar at the sort of platform level that Microsoft or anyone else does, there's over $10 that are done at the applications and services level, the variety there is pretty unbelievable, and that exists in every country around the world.

At the hardware level, the improvement that we were holding for and that reduction in price has really come true. The miracle has been delivered. It starts with this idea of exponential improvement. Gordon Moore, the chairman of Intel, made the prediction that twice as many transistors could be put on a chip every two years. He knew that would end at some point, but it's continued from the time he made that statement in the '60s up to now. And it looks as though that will be able to continue at least another 15 years or so. That's why if we compare the original machine that I did the basic interpreter for to a powerful personal computer today we see a lot of difference.

That early machine has 4k bytes of memory, not 4 megabytes or 4 gigabytes, but 4k bytes of memory. And a real early feat that we did was actually write a floating point interpreter that ran 3,100 bytes, so that in that 4k machine you'd still have room for the programs that you typed in, the variable table, your arrays and all those values in that nice little 4k machine. I won't say that you could do some huge type of software program there, but that was exactly what the hardware made available.

And so going from 4k to 4 megs to 4 gigs, that's a factor of a million change. In fact, these exponential improvements lead to that kind of dramatic difference. The difference is there in almost every aspect. It's not just the memory capacity, it's the disk capacity also, growing more than 5 million, networking bandwidth is almost infinite, because we just couldn't connect the machines together back then, and now broadband is not only available to businesses, but even to consumers, as well.

So the constant improvements in the platform allow us to be more ambitious in terms of what software does. We need to graphics chips to deliver better images, because certainly we want to create 3D virtual spaces that are either imaginary, entertainment, or reflect the real world. Where you can look at a product, what will it be like, or you can look at an image of downtown and see the traffic, and see what different things are going on, what's nearby, see that not in the sort of text-oriented way we do it today, but rather in an immersive, fully representational environment. So the graphics chips are going to let us do that.

We need screens with higher resolutions. There are, again, breakthroughs in LCDs in that we can do reading off the screen that's as good, or in the future even better than reading off of paper. That' letting us have portable devices, devices that are small that we can carry around, devices that are a variety of sizes. All these devices will be software driven. They'll all connect to the single network, the Internet, the Internet will take over not just for data, but for voice, for video. TV won't be something separate, it will simply be a straightforward data application that happens to run on the Internet.

As we think about the devices, in some ways they'll almost just appear in the environment, because we'll have lots of different cameras, and microphones, and displays that can project onto the floor or walls, or kitchen desktops. You won't think of the computer being in a single place. The environment will see that you're there. You can give spoken commands. It will be quite responsive, and so storage, and computing and the screen and the input will be disaggregated. Software will give us that type of flexibility.

You'll have some type of computer in your wristwatch, so you can just glance at information. You'll have the device that you can take out of your pocket. Of course, today's phones have improved very radically. We can think of them now as cameras, as well as phones. In the future they'll be kind of a digital wallet, they'll show us that map, not just a 2-D map, but a 3-D environment map. You'll be able to take the camera and, say, take a photo of sign in a foreign country and have that translated for you. You take a photo of a receipt that you get, say, at a restaurant, and it will see what it is, file that away, ask for reimbursement, get your expenses right without your having to do a single thing. Take a photo of a bar code or a product and your phone will tell you where you might get that at a lower price, what the competitive products are, what you might want to buy that's different. All of that will be kind of common sense. And that will be because we're bringing the richness of software into all of these devices.

Moving up from the pocket device, we have the next level, which is the Tablet. That's the vision that Microsoft has had for a long time. When we think about a Tablet we think about something that will replace textbooks. You'll be able to call up on the screen through the Internet the textual information, and interact with it, have videos, audios, have it customized by the teacher in a way that today's printed textbooks don't allow. And yet this Tablet will come down in price so that eventually it costs less than textbooks used to cost. So it's one little light thing that you carry around when you're in the classroom, and there is software that lets the teacher have some control over what you're doing, over what you're looking at.

As you leave the classroom it's your device of empowerment to pursue things, and look into anything you want. It's a device where the reading capability is so good that of course the idea of how you look at the daily newspaper, or those what would have been weekly printed magazines of course you're doing that off the screen because you can annotate, you can share it with friends, you can search. It's just far richer than it would have been if that had to be a paper-type piece of information.

Already in some areas, like the encyclopedia everyone would acknowledge that the digital form, either something like Encarta on a CD, or something like Wikipedia out of the Internet itself, is way richer than print-based encyclopedias. When I was young I read the World Book. I started with A, then B, then C, then D, and went all the way to the end, and it's not a very good way to learn things, because you're kind of jumping around between centuries and subjects, and you're trying to remember how things related to each other. The equivalent right now where you can do that on the Internet would let you do it in a far more ordered fashion. Let you test your knowledge, let you find things that are more in depth. So the way we can take people's curiosity and satisfy it is far, far better.

The Tablet concept will also change the desktop computer. You won't have a phone that's separate from your PC. Your desktop surface you'll be able to write things on and have that be recognized. So the input will be voice, it will be ink, it will be the keyboard, all really brought together. And the machine will have a sense of your schedule for the day, the context you're in.

When people want to contact you it won't be a phone number, multiple e-mail addresses. It will simply be one identifier, and based on who it is trying to do the contacting, you'll have software that runs on your behalf that you've set up to decide should you be interrupted right where you are, is it important enough, should a message be kept. What do you say to that person about your status for future availability, depending on who they are.

So you'll have an agent working on your behalf, and we'll laugh at the days when we had phone numbers, or we had multiple e-mail accounts, and we were being interrupted when we didn't want to be, or we didn't get the information that we needed that was urgent for us that the system didn't understand to bring that to us. No matter which device you're working on, that information should absolutely be made available to us.

So it's a period of dramatic change, not in the overnight sense during the dot com craziness, where people had said banking would change overnight, retailing would change overnight, but in a more gradual way. The dreams that existed then were valid, it was just the timeframe was a little wrong, because it takes time to get people to change behavior, it takes time to get these software systems to be simple enough, secure enough, rich enough, connecting together so that all the information is there, so that these things can be delivered on. And yet every one of those dreams we'll be able to pull together within the next 10 years, so a dramatic change in every sector.

One place we can see this very vividly, and I'm sure all of you are essentially avant garde practicers of the so-called digital lifestyle, is that already music, photos, some videos, the accessibility to have a device in your pocket, the accessibility to call these things up when you want, already many people are just taking that for granted. And with what we call Internet TV it goes to a point where even that, the medium that requires the most bits, the most bandwidth will be utterly different and ideas like channels will be a thing of the past. The idea that when you watch a news show everybody would see the same subjects in the same depth, we'll look back on that as a very inefficient thing. If you care about certain sports you want to see a lot more of those. If you care about the weather in certain places you want that in depth. If it's certain topics in politics or international affairs you care about, great, that should brought to you. Even the advertising should be targeted so that it's more interesting to you, and more effective for the advertiser, as well.

So the digital work style, digital lifestyle are moving ahead are moving ahead at full bore. And the one thing that will determine how quickly this happens is the software, the software presenting these capabilities in a fairly straightforward way.

Now, for Microsoft it's key that we get great people to help us drive this. In fact, everybody in the company gets involved in recruiting from time to time. And I made a little video of one of my recruiting experiences. So let's go ahead and take a look at that.

( Video Segment.)

(Cheers, applause.)

BILL GATES: We had a lot of fun making that; he's a good guy. (Laughter.)

Well, let me quickly give you a glimpse of some of these things that I've been talking about. This is an example of a next generation phone that comes out. You can see the thinness is getting a lot better, the ability to have keyboard capabilities, and it's got that camera built-in, and so really the magic now is going to be next generations of software: speech recognition, image recognition, the model of the user and their communications needs and wants.

I've got another quick thing here on a PC that just gives you an idea of steps forward in visualization. I've got a set of photos, I can pick any set of those. I can say that I want to select a subset of these things, I can go in and out in terms of what's available here. And there's different views that we can have. For example, if we want to have an album view, it will take and put them there, I can organize them however I want. Or I can take and have a view which I'll call a mantle view where it puts them in a little bit of 3-D. I can play that to show how it would look on my, say, living room display, and anything that's interesting I can zoom in on that. Of course, I'd have data about when this was taken, who I was.

And so very quickly the idea of organizing all the photos you're going to have, which will be a big number, throughout your life you'll take a lot, you'll want to do different cuts on those and present it, having it dropped in and be easy to view, nicely accessible, that's going to be a very, very important thing.

Next let me shift to this little device here. This is the Xbox 360, which will be coming out next month. It's our second generation of videogames, and this is the generation that's really about high definition. We'll have our 360, Sony will have the PlayStation 3, and we'll have a generation of games that are far better than what's come before.

But it won't just be the games and entertainment, these will also be devices that will enhance this digital entertainment idea that we've been talking about, so that the power is here that all of our digital media you can get at, getting at, say, video on the Internet or even things that you carry around.

A good example is let's say I've got a portable music player and I want to have that music in my living room, I ought to be able to just take and use the standard USB connector here, plug this in, works with any kind of music player, even a little iPod can connect up here. (Laughter.)

As I plug in, I see the interface I have on the Xbox here. There's different screens that let you control the games that you play in, what you do with those. So here we have our system profile. Here's this media screen and so now with this one let me step down and say, oh, what do I want here, we actually have music, select that. And as I go in, you can see it's recognized that particular device I had, which is an iRiver device. I can select that and then just immediately it's going out, looking at all the different music that's there. We can just go in here and it's connecting to the device, pulling up the complete directory, and then I just go ahead and play whatever songs I have.

But it's not just music. Let's say I have a camera that I've gone and taken some photos on that just happens to be a Canon camera. Again, I've got this nice standard connector so I can take the USB and plug that in. And then as I go back up here, you probably saw we had pictures as another thing I can connect to, so here's pictures. And you can see again it's recognized that my device is out there, so I'll take that, select it, go over, see all my photos come up, and then I've just played a slideshow.

So pretty quickly without knowing a lot of complex commands you've got the power of this device with your music and you can play that music while you're playing a game, you can have this slideshow, you can have special effects coming out of the music, and so it's more than simply a game machine that you might have thought about videogames just being in the past.

With that, let's switch to this machine, turn the volume down low. This has got one of the games that will ship when the 360 comes out. This is called Project Gotham. Some of you may have seen it, it's a racing game that was available for the previous Xbox. But you'll see here it's dramatically changed because of this graphics power that's been made available.

So I'm not that great at this, I'll pick easy -- (laughter) -- and then it's going out and loading it in. It's got rich models of all the different cars. We're actually going to be racing here in downtown Las Vegas. We'll have lots of different cities, lots of different levels, you can race against different people. We actually have a lot of artificial intelligence in here in terms of how it's done.

So here we go, my guy is in fourth. It's actually the corners that get hard here. (Applause.) These spectators are good; whenever I race into the wall, they just fly everywhere, very realistic. I can also turn the driving over to the computer. All the detail is very, very different.

Also it's of course connected up to broadband and so if I want to find friends to play with, if I want to get into contests, if I want to be a spectator, all of that makes it a far deeper experience than you would have ever had in the past.

And, in fact, the whole player thing opens up these genres, so we'll have role-playing games, virtual reality. We'll also have very lightweight games, we have Xbox Arcade where you can come in and in just a few minutes be playing a fairly simple game. We'll have the old classics brought down with a little better graphics, and so it's easy to get into, it's not just the games that take a long time to learn how to use.

We even connect the Xbox up to the PC so if anywhere in your home you've got a Media Center you can project out on through the Xbox onto that living room device everything that's going on with the PC; so really taking the idea of that home network and broadband and bringing TV, gaming, PC, music, photos together.

The last demo I'll show is a little bit more futuristic. Here I've got a setup that let's say it's a table in an airport lounge, and I'm on a flight and I've got just my phone with me, I didn't happen to take my Tablet this time. Well, the phone has got a limited screen size, and so if I want to do a lot of rich interaction, it's not quite that productive.

So here I'll just take my phone, put it down and actually what's going on is there's a camera here and a little infrared light that lights this up and so it's recognizing that there's a phone and then talking to it and saying, OK, that's my phone. Then to open it up on this full table and let me get at the information, it forces me to use my fingerprint here and actually authorize and say exactly who I am. And now I have a bigger service area. I can annotate with ink, I can read large documents, that kind of thing.

Somebody gave me a business card that I want to follow up on, so I just put that down on the table and again the camera scans that, sees the text that's there. I'll flip this over because I actually wrote some notes on the back, that gets recognized. Then I'll take it and say, okay, I'd like it to be up in this phone, so it shows me that it's taking that data and putting it in my contact list. Obviously it will go and synch that up to the contacts I have, so it's on all my devices; the software is working cross-device, not just on one device.

It notifies me I've got a fairly urgent message about a press release that I need to approve, asks me to verify that I really do authorize this to go out because that's a very important thing. So again I simply use my fingerprint and that goes off.

So I could interact, view mail, browse the Web, things like this just with this device. Then when I'm done, I pick it up and it will recognize that it's gone. And so I'm logged off and all my information is simply on this device, so I'm not leaving anything behind.

This may seem pretty far out in a way, but, in fact, the componentry involved here is very inexpensive. These digital cameras are getting down to be very, very inexpensive; the actual projection display, the technology there is more and more based on single chip digital light projectors, so we can expect that to be cheap. So not just in the business environment will you have these intelligent type tables but even in the home as well. And so we can think of a play table and a business table and this type of recognition becoming actually kind of pervasive in the environment.

So where will software be used? Well, it's almost hard to think about where it won't be used. In fact, if we think about the sciences and the frontier in all the different sciences, every one of them is dealing with lots and lots of data. And how does the world deal with the fact that when you want to find patterns in data that humans aren't very good at that? Well, in fact, we take state of the art software, data mining software and machine learning type software and we apply that to the problem.

A good example is astronomy where you have different observatories, different locations, different wavelengths, different timeframes. If you want to say something about astronomy, you really need to check with all those databases. And so being able to think of that as one virtual database, that's a tough software problem. One of our top researchers, Jim Gray, brought the astronomers together, got them to do that, and it's made a huge difference in terms of that field moving forward very quickly.

The same thing is happening in all the sciences, biology is probably the most interesting, although the complexity there means that it's a much tougher challenge. You have, of course, lots of complexity in terms of privacy, you have people who have proprietary data there, but the big advances will come because the genomic data, the proteonomic data, all of those things will be combined into databases that people will sit down at workstations and navigate those things, look for patterns and try out different ideas.

And so software is driving the sciences forward. In the same way that math has always been a common tool, now software is a necessary part of that toolbox and so breakthroughs in software and people who understand software are very necessary for that interdisciplinary activity.

So when we think about computers and software, we often think about the richer countries and how they're doing a good job of taking advantage of these things, but we can also see this as a tool for equality, that as soon as a student in any country has a connection to the Internet, they don't need that huge library with extensive books. If they're connected up, they're on an equal footing, they can get the latest research and latest information.

Now, to really make that true, we have to have machine translation. That's another one of those Holy Grails of computer science where as we've made progress, our respect for human intelligence just goes up and up. And yet the progress is good enough now that in many domains, including text about science and computers, automatic translation is nearly as good as human translation.

We test this out by taking some of our online support articles in things like Japanese, Korean, and Spanish, and do half of them by hand, half by the computer, and then look at the satisfaction, the pattern of usage and see now that we've driven that to the point where it's equally acceptable to have those articles be machine translated. So that means a student, no matter what their language is, could go out and browse most of the Internet.

Now, when it comes to things like poetry, translating that automatically, that's still well out into the future, plenty more to be done there.

But the Internet is a leveler, it's a leveler of making information available, so it's certainly been a factor in driving towards more democracy, not letting political restriction limit the flow of information. It's also been a great enabler in terms of education, letting people try out their ideas, pursue their curiosity. Even in areas where people have disability, the blind now through software that we and others have done can get at and get all of that Internet material, not just be restricted to the Braille books that were very limited and not very available. Likewise for people with disabilities, the idea of the computer and special software allowing them to get involved in jobs that simply wouldn't have been available to them.

And so software is the place where the action is. It's a fascinating area. It is an area that will continue to generate jobs. The growth in Microsoft's employment here in North America is continuing to be very strong, also very strong on a global basis. We know that for the next decade there will be a shortage of great software engineers, and so we'll be scouring everywhere we can to find those people. And these are jobs where you get to come in and very quickly work on tough problems, very quickly find out that when you ship software to millions of people, as soon as it gets out there they're going to tell you what they like, what they don't like, you're going to have that feedback and an opportunity to take the software to the next level.

More and more we'll have different kinds of cycle times. We'll have things we improve literally automatically on an almost daily basis, things that improve monthly, things like, say, the browser or the Media Player that are more like the ones here, and things like the file system or the scheduler that are on more of a two or three year type cycle. By layering the software, having very provable component boundaries, we can make the efficiency, the ability to release separately, the depth of the security far better. And that's requiring very state of the art techniques in computer science to define interfaces and do proofs around those interfaces. In fact, these are things that were talked about over 20 years ago, but now because they're necessary, now because of the advances we're really doing those things.

They're very interesting problems in computer science that are now very practical. For example, the chips that are coming along, the clock speeds won't be going up as much, so we'll have lots of parallel execution, and so there we need new programming languages, we need new ways of looking at dataflow so that we can take advantage of that.

So this is the golden age of software. We can say that all the 30 years of work up until now is just to get the platform, just to get that we have the connectivity of the Internet, we have the great hardware that allows us to be more ambitious, and I'd say the thing that will be the most fun for me is over these next 10 or even 20 years seeing how your generation comes into the software industry and takes your creativity, your open-mindedness and takes software to a whole new level, so that's going to be very, very exciting.

Thank you. (Applause.)

TOM COLEMAN: I'm Tom Coleman, the Dean of the Faculty of Mathematics, and it's my pleasure to deal with the next session of this show, which is the Q&A session.

Before we get started, I just want to say, Bill, that as you know, this is a very mathematical university and just in case some of the questions get a bit rough we have a little aid for you here. (Laughter.) This is a t-shirt from the math society with a few formulae, just in case.

BILL GATES: Excellent. Thank you. (Applause.)

TOM COLEMAN: OK, so we'd like to do it the following way. If you have a question, of course, on the bottom floor here raise your hand, I'll try to pick you out, and I'll repeat the question, maybe paraphrase it. On the top floor there are mikes set up, so just queue up there, I won't repeat those questions. I really can't see up there; oh yeah, there you are.

Okay, so why don't we begin? Raise your hand if you have a question for Bill. Yes, right in the front row here.

QUESTION: (Off mike).

TOM COLEMAN: So the question is the balance between theory and practice with regard to looking for a job in the future of software.

BILL GATES: Well, the key thing about a university education is to have a fairly deep understanding of the kind of tradeoffs that you want, understand algorithms, understand data structures. And it's not so important whether you know that in the context of compilers or graphics or operating systems, but rather that in some areas in a fairly deep way you've seen how programming works and the importance of very, very good design.

You know, the field of computer science today is very broad, and so some of those things will be very attractive to you, will be fun areas for you to exercise those skills, but as you move out and are doing work, the specifics will be available out there, and so the particular language, the particular way that you've learned it will be less important.

You know, when somebody comes to Microsoft we typically say to them, OK, what's the most complex piece of software you've worked on, whatever it is, get a sense of were they interested in the different choices that were available there and as they evolved over time did they see new ways that that could be done.

And so I'd put a strong emphasis on the basic theory of algorithms and how those things go on, but with at least one area that you get by hands on.

QUESTION: (Off mike).

TOM COLEMAN: So the question is, how do you see Microsoft changing the way you do business with such changes in all the software and tools that are coming out.

BILL GAT"

頁面