演算法

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search
一個用嚟解決「盞燈唔着」呢一個問題嘅演算法;演算法可以用流程圖表示。

演算法粵拼:jin2 syun3 faat3英文algorithm)係數學電腦科學上嘅一個概念,指一串能夠完全唔含糊噉教一個人或者一部電腦點樣解決某啲特定問題嘅指示。演算法又有分好多唔同種,唔同種嘅演算法可以用嚟解決唔同嘅問題,由簡單嘅算術以至自動化嘅認知等等都有演算法可以做得到。

演算法可以喺有限嘅時間、記憶空間之內,透過有精確定義形式語言嚟表達[1][2],用嚟計一啲函數[3]。噉講嘅意思係話,一個演算法會要求某啲特定嘅輸入(Input),跟住啲指示會描述一柞運算,而當呢柞運算由人或者電腦執行嗰陣,會經過一連串數量有限嘅中介狀態[4],最後產生一個輸出(Output)[5],並且喺呢個最終狀態嗰度終止執行。由一個中介狀態去到下一個嘅過程唔一定係決定性(Deterministic)嘅,有好多演算法都涉及一啲帶有隨機性喺入面嘅運算。

演算法嘅概念經已存在咗超過 2,000 年,有得一路追溯到去古希臘數學家嗰度,例如係由呢啲數學家諗出嚟嘅愛氏篩同埋係輾轉相除法呀噉[6],而「Algorithm」呢個字係由 9 世紀嘅波斯人數學家花剌子密波斯文:محمد بن موسى خوارزمی)個姓嗰度嚟嘅-佢個羅馬字係「Algoritmi」。花剌子密佢做咗啲相關嘅研究,局部噉確立咗演算法嘅概念[6]。現代嘅演算法概念係喺 1928 年由德國數學家打域囂拔(David Hibert)喺佢嘗試解決可判定性嘅問題嗰陣奠定嘅。自從嗰陣開始,演算法同相關嘅研究就喺數學同電腦科學呢兩個領域嗰度俾人廣泛噉採用。

正式定義[編輯]

籠統噉講,「演算法」呢個詞嘅定義可以係指「一串能夠精確噉定義一系列作業嘅規則」[7][8]。呢個定義包含嗮所有嘅電腦程式-就連啲唔曉做數字上嘅運算嘅程式都包含喺呢個定義之內。正話提咗嘅輾轉相除法同埋上面嗰個流程圖所描述嘅都係符合呢個定義嘅演算法。

演算法對於電腦處理數據嚟講係不可或缺嘅。電腦程式一般都會包含一大柞嘅演算法,嚟到仔細噉講明一部電腦要做啲乜嘢運算(同埋以乜嘢次序做呢啲運算)嚟到解決啲人想用嗰個程式解決嘅問題-呢啲問題可以包括咗計啲簡單嘅算術以至複雜嘅統計學作業等等都得。喺定義上,一個演算法可以當做一連串作業[9][10],並且串嘢有以下呢啲特質:

  1. 有住某啲特定嘅次序;
  2. 唔具有一詞多義嘅問題;
  3. 有得攞部理想嘅運算機器-即係有圖靈完整性(Turing completeness)嘅機器-嚟執行佢;
  4. 曉自己結束運行-所以可以係有限嘅時間之內行完,並且俾一個輸出出嚟睇[11]

當中美國邏輯學家 George Boolos 同佢嘅同事係噉樣描述「演算法」呢個概念嘅[12]

原版英文:"No human being can write fast enough, or long enough, or small enough† ( †"smaller and smaller without limit ...you'd be trying to write on molecules, on atoms, on electrons") to list all members of an enumerably infinite set by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols."

粵文翻譯:由於受到速度、長度、大細嘅限制,冇人類能夠將一個「列舉到嘅無限」(Emumerably infinite set)包含嘅物件用某啲符號寫嗮出嚟。但係對住某啲列舉到嘅無限集,人類曉做一啲同等有用嘅嘢(註:指演算法):佢哋識得俾一啲指示出嚟去揾出個集所包含嘅第 n 件物件,當中 n 可以係是但一個細過無限大嘅整數。呢啲指示都要幾明確至得,要有一個形式,令到曉計數嘅機器(例如係電腦)或者一個淨係曉用符號嘅人類能夠跟從佢哋。

上面呢段嘢當中所講嘅「列舉到嘅無限集」係數學上嘅一個概念,指一個包含咗多樣嘢嘅集,而呢個集包含嘅物件有無限噉多件,但係啲件數可以用由 1 開始嘅整數嚟數佢。所以 Boolos 同佢啲同事講緊就係話:一個演算法係一連串指令,例如係一柞好似「 代表輸出, 代表輸入」噉嘅算式;而呢柞指令能夠由是但一啲輸入嗰度計同整一啲輸出出嚟俾人睇,而且呢啲輸入-至少喺理論上-係幾大都得嘅(但係當然,實際上因為人有嘅電腦嘅運算能力有限,所以對於輸入嘅大細梗會有個上限)[13][14]

概論[編輯]

亞倫圖靈(Alan Turing)嘅相,喺 1951 年影嘅;佢係英國嘅一個數學家,做咗好多有關演算法嘅研究。

演算法嘅表達[編輯]

想像家陣有一部曉跟一啲事先指定咗嘅規則嚟到由一啲輸入當中計個輸出出嚟嘅機器,而且呢部嘢嘅記憶體係無限噉多嘅-即係所謂理想化嘅圖靈機(Turing machine)。佢計緊嘅運算嘅內容可以用多種唔同嘅圖表同語言表達-包括咗係自然語言虛擬碼(Pseudocode)、流程圖狀態轉移表控制表、同埋係多種嘅程式語言呀噉。用自然語言-即係好似廣東話普通話呢啲日常講嘢用嘅語言-寫嘅嘢(好似係虛擬碼)對一般人嚟講好易明,但係就好多時都會有一詞多義嘅問題,而且電腦唔會識睇。程式語言係專門為咗等人類有得同電腦溝通而設嘅特殊語言,電腦會睇得明,所以演算法好多時會用程式語言嚟定義。

好似係以下呢段用粵文寫嘅演算法噉[15]

要解決嘅問題:家吓俾一柞正數你,假設呢個列唔係一個空列,同我揾嗰柞數入面最大嗰個出嚟。
用嘅演算法嘅步驟:
  1. 設一個變數,叫佢做「max」,並且將佢個數值設做「0」;
  2. 將收到嗰柞正數逐個逐個攞嚟同 max 比較吓;
  3. 如果撞到一個大過 max 嘅數(叫呢個數做「x」)嘅話,將 max 嘅數值設做 x,並且繼續將 max 同下個正數比較吓;
  4. 將最後得出嗰個 max 嘅數值俾出嚟。max 嘅數值會係成柞數入面最大嗰個。

呢個演算法用 Python(1991 年出嘅一種程式語言)寫出嚟嘅話會係[15]

# 入嘅嘢:一列冧巴,叫佢做「L」。
# 出嘅嘢:L 入面最大嘅冧巴。

def find_max (L):  # 定義乜嘢係「去搵 L 嘅最大值」。
   max = 0         # 設最大值做 0。
   for x in L:     # 為咗 x 喺 L 入面。
      if x > max:       # 如果 x 大過最大值。
         max = x         # 設最大值做 x。
   return max      # 俾返個最大值出嚟。

諗演算法嘅過程係將一個作業揼散做組成佢嘅細部份[15],而每個細部份都要係一啲電腦普遍都會識做嘅簡單工作(例如係「比較兩個,睇吓邊個大啲」)-呢啲細部份可以話係組成演算法嘅元素,有咗佢哋就能夠將任何「人類會想用電腦做嘅工作」砌出嚟。

要留意嘅係,演算法係就係通常都攞電腦程式嚟實行嘅,但係都有一部份嘅個案會用其他方法嚟到實行一個演算法,例如係生物神經網絡電路、或者純機械性嘅架生呀噉。

三大描述層次[編輯]

演算法嘅表達方法大致上可以分做三大圖靈機描述層次[16]

  1. 高層嘅描述(High-level description):會描述一個演算法要做乜嘢運算,但係就忽略點樣將個演算法實行落去部運算機器嗰度。一般人會睇得明,但係運算機器唔會。
  2. 實行性嘅描述(Implementation description):會話俾一部圖靈機知要點樣郁同埋要點樣將啲數據儲喺啲數據庫嗰度。喺呢個層次仲未會話到運算過程嗰啲中介狀態同埋函數嘅詳情俾人知。
  3. 形式描述(Formal description):最仔細,會講明埋運算過程嗰啲中介狀態同函數。

上面嗰段 Python 碼屬於高層嘅描述-就算睇咗佢,一個人仲係唔會知道部電腦嗰啲邏輯門(Logic gate)做咗乜嘢運算。

演算法嘅設計[編輯]

演算法嘅設計係數學同各門嘅工程學上好緊要嘅一個課題[17]。數學家同工程師會係噉嘗試諗一啲新嘅演算法出嚟,目標係要做起嘢上嚟更加有效率,例如有好多呢啲領域嘅科學家都致力於諗一啲步驟少過現有演算法嘅新演算法出嚟-假設其他因素唔變,步驟少啲嘅演算法做起嘢上嚟會快啲[18]

演算法設計主要有以下呢啲步驟:

  1. 定義好個演算法要解決嘅問題;
  2. 整返個模型嚟去描述嗰個問題;
  3. 規範演算法;
  4. 諗一個演算法出嚟;
  5. 檢查吓個演算法有冇問題;
  6. 分析吓個演算法;
  7. 實行個演算法;
  8. 程式測試;
  9. 做好啲文件上嘅紀錄。

例子[編輯]

睇埋:演算法一覽

揾最大數值[編輯]

一個簡單嘅演算法係要揾出一列以隨機次序排嘅數字當中最大嗰個出嚟。要揾出個答案,睇嗰個人實要睇嗮個列當中嘅每一個數字,而由呢度可以推導到一個簡單嘅演算法出嚟。呢個簡單演算法用粵文寫出嚟嘅話會係[19]

  1. 如果個列入面冇數字,噉就唔會有「最大嗰個數」。
  2. 先假定個列入面第一個數字係最大嗰個。
  3. 逐個逐個噉去睇個列入面啲數字,如果撞到個數字大過而家手上嗰個「最大數字」嘅話,將新撞到呢個數字設做「最大數字」。
  4. 如果睇勻嗮個列入面啲數字嘅話,將手上嗰個「最大數字」交出嚟做答案。

上述呢個演算法用比較形式些少嘅偽代碼寫出嚟嘅話會係噉:

// Input: A list of numbers L.
// Output: The largest number in the list L.
if L.size = 0 return null;
largest  L[0];
for each item in L, do
   if item > largest, then
      largest  item;
   return largest;

// 當中 "←" 代表指定敘述-「A ← B」即係將 A 嘅數值設做 B;
// 而 "return X" 會終止個演算法,並且將 X 嘅數值攞嚟做輸出。

有好多科學家都嫌呢個演算法唔夠好,因為佢喺最壞情況嗰陣要睇嗮成個列先至搞得掂,所以又有人諗咗第啲演算法出嚟做呢樣工作-而呢啲新演算法好多時都曉淨係睇個數字列嘅一小部份就經已揾得出個最大值。

快速排序[編輯]

用快速排序將一列亂糟糟嘅數字由細到大排好嘅 GIF 圖解
內文: 快速排序

快速排序(Quicksort)係一種用嚟將一個數列入面啲數字由細至大排好嘅演算法[20][21]。步驟如下:

  1. 喺個數列入面是但揀一個數字,設佢做基準(pivot)。
  2. 重新排序數列:將個數字重新排過,令到數值上細過個基準嘅數字冚唪唥都搬去個基準前面,而數值上大過個基準嘅數字就要冚唪唥喺嗮個基準後面;做咗呢個步驟之後,個基準會喺正佢嘅最終位置。
  3. 將個數列分做兩橛-「細過個基準嗰柞數字」同埋「大過個基準嗰柞數字」,並且分別噉對嗰兩橛做上述嗰兩個步驟。

呢個演算法俾人好廣泛噉攞嚟將啲數字列嘅次序排好(一個整齊噉排好咗嘅數列可以攞嚟做第啲緊要嘅作業)。

上述呢個演算法用 Python 寫出嚟嘅話會係噉嘅[22]

def sort(array=[12,4,5,6,7,3,1,15]):
   less = []
   equal = []
   greater = []

   if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
               less.append(x)
            if x == pivot:
               equal.append(x)
            if x > pivot:
               greater.append(x)
        return sort(less)+equal+sort(greater) # 喺 Python 入面,「+」可以代表「將兩個數列拼埋一齊」。
    else:
        return array

對分檢索[編輯]

用對分檢索喺個數列當中揾「7」出嚟嘅圖解
內文: 對分檢索

對分檢索(binary search)係一種用嚟由一個預先排好咗次序嘅數列嗰度揾某一個特定數字出嚟嘅演算法[23][24]。佢嘅做法係首先將行資料拆做兩橛,再睇吓中間嗰個數係咪等如要揾嗰個數(目標),假如個數列係預先由細到大排好咗嘅話,噉就表示一樣嘢:如果數列中間嗰個數大過個目標,噉個目標實係喺中間個數前面,而如果數列中間嗰個數細過個目標,噉個目標實係喺中間個數後面,跟手段演算法就可以再重複呢個程序,將個搜索範圍縮細,最後揾到個目標嘅數字(假如個目標真係存在喺嗰行數列入面嘅話)。好似係以下呢段偽代碼噉:

function binary_search(A, n, T):
    L := 0 // 設個數做「左邊界」
    R := n &minus; 1 // 設個數做「右邊界」
    while L <= R:
        m := floor((L + R) / 2) // 將由 L 至 R 嗰段嘢砍兩橛,m 設做中間位
            if A[m] < T: // 如果第 m 個數細過目標(T)嘅話,即係話個目標應該喺第 m 個數後面。 
                L := m + 1
            else if A[m] > T: // 如果第 m 個數細過目標(T)嘅話,即係話個目標應該喺第 m 個數前面。 
                R := m - 1
            else:
                return m // 如果第 m 個數等如目標嘅話,就將嗰個數做輸出。
        return unsuccessful

對分檢索平均會快過「吓吓都將數列入面嘅數逐個逐個睇一次」:喺最壞情況之下,用對分檢索嚟搜尋一個數字要做 次比較(當中 係個數列入面有幾多個數字)[23],而「吓吓都將數列入面逐個逐個睇一次」喺最壞情況之下就要做 次比較。「由一個數列當中揾一個特定數字出嚟」係一個電腦好常要做嘅基本作業,如果(例如)喺一個程式當中部電腦要做呢個作業 100 次嘅話,噉一個用對分檢索嘅程式就會快一截,所以程式設計員會比較鍾意用對分檢索。

模擬牛頓定律[編輯]

睇埋:遊戲物理學

遊戲物理學(game physics)係指喺設計一個電子遊戲嗰陣將物理定律電腦程式嘅形式表達出嚟,等部電腦識得真實噉模擬現實世界嘅物理俾啲玩家睇[25][26],令到啲玩家能夠覺得個遊戲有返噉上下真實度,並且投入去個遊戲裏面-喺廿一世紀,大部份嘅電子遊戲都要做呢樣嘢,得少數嘅例外(例如一個模擬捉棋嘅電子遊戲)可以唔使模擬物理定律。一般嚟講,遊戲嘅物理都唔會完全跟足現實嘅物理嘅-好多時淨係會求有足夠嘅真實度。

以下呢段用 C 程式語言寫嘅源碼可以攞嚟模擬喺牛頓第二定律(Newton's second law)之下郁動嘅物體[25]

double t = 0.0;
float dt = 1.0f;

float velocity = 0.0f;
float position = 0.0f;
float force = 10.0f;
float mass = 1.0f;
// 設一大柞變數,包括咗時間點(t)、時間間隔(dt)、速度(velocity)、位置(position)、件物體受嘅力(force)、同件物體嘅[[質量]](mass)。

while ( t <= 10.0 ) // 重複噉計若干次,計到時間點係 10 為止。
{
    position = position + velocity * dt;
    velocity = velocity + ( force / mass ) * dt; // 用牛頓第二定律計吓件物體受嘅力同佢嘅質量會點影響佢嘅速度。
    t += dt;
}

呢段嘢會俾嘅輸出如下,佢列嗮佢模擬嗰件物體喺每個時間點 位置速度出嚟[25]

t=0:    position = 0      velocity = 0
t=1:    position = 0      velocity = 10
t=2:    position = 10     velocity = 20
t=3:    position = 30     velocity = 30
t=4:    position = 60     velocity = 40
t=5:    position = 100    velocity = 50
t=6:    position = 150    velocity = 60
t=7:    position = 210    velocity = 70
t=8:    position = 280    velocity = 80
t=9:    position = 360    velocity = 90
t=10:   position = 450    velocity = 100

輾轉相除法[編輯]

用輾轉相除法揾 1599 同 650 嘅最大公因數嘅圖解;
 1599 = 650 × 2 + 299
 650 = 299 × 2 + 52
 299 = 52 × 5 + 39
 52 = 39 × 1 + 13
 39 = 13 × 3 + 0
內文: 輾轉相除法

輾轉相除法,西人興叫歐幾里得嘅演算法(Euclid's algorithm),係用嚟求最大公因數嘅演算法,首次記載係喺大約公元前 300 年嘅古希臘數學家歐幾里得嗰本《幾何原本》入面[27][28][29]。歐幾里得佢係噉樣講嘅:(粵文翻譯)「家吓有兩個彼此唔係對方因數,個問題係要揾出佢哋嘅最大公因數」。佢首先諗到一點-要計佢哋最大公因數嗰兩個數相減嘅話,得出嗰個數一定係個最大公因數嘅倍數。佢諗出嗰個演算法步驟簡單啲講如下[30]

  1. 要揾佢哋最大公因數當中,大啲嗰個設做 ,細啲嗰個設做
  2. 乘大佢,睇吓要乘幾先會變到大過 ,即係話 -喺呢條算式入面, 會係一個正整數,而 係一個餘數;
  3. 睇吓 係唔係等如零;
  4. 如果係嘅話, 就係要揾嗰個最大公因數;
  5. 如果唔係嘅話,將 當中大啲嗰個設做 ,細啲嗰個設做
  6. 跳返去步驟 2。

要將呢個演算法用電腦嚟執行嘅話好簡單,淨係需要幾個種類嘅指令已經夠:條件性嘅 GOTO、無條件性嘅 GOTO、設變數、同埋基本嘅算術

實現例子之一[編輯]

呢段演算法嘅流程圖

以下呢段源碼係輾轉相除法嘅一個可能實現形式(雖然實際上係一個唔多靚嘅演算法)。佢個做法嘅基本原理係將要揾佢哋最大公因數嗰兩個數設做 (大啲嗰個)同 (細啲嗰個)兩個變數,再將 嗰度減出嚟,減到得出個數細過 為止[31]

輸入:

 1 [設兩個變數-L 同 S,並且將佢哋嘅數值設做  同埋  嘅]
  INPUT L, S
 2 [將  初始化:將個餘數嘅值設做等如  嘅]
  R ← L

E0:確保

 3 [確保  真係細過 ]
  IF R > S THEN
     真係細過 ,所以唔使做 #4、#5、同 #6 呢幾個交換步驟:
    GOTO step #6
  ELSE
     唔係細過 ,所以要做交換步驟嚟將兩個數掉轉:
 4   L ← R 
 5   R ← S
 6   S ← L

E1:揾個餘數出嚟-將 減出嚟,減到得出嘅餘數 細過 為止。

 7 IF S > R THEN
    GOTO 10
   ELSE
 8   R ← R − S
 9  GOTO 7

E2:個餘數係咪零?如果係嘅話,個程式終止得,如果唔係嘅話,個演算法要再行落去,直至得出一個係零嘅餘數。

 10 IF R = 0 THEN
    GOTO 15
   ELSE
    CONTINUE TO 11

E3:將 對調,用 嚟做啲數字嘅中轉站。

 11  L ← R
 12  R ← S
 13  S ← L
 14 [重複上面嘅程序]
    GOTO 7

輸出:

 15 [將個答案顯示出嚟俾解緊難嗰個人睇]
    PRINT S

搞掂:

 16  HALT, END, STOP.

實現例子之二[編輯]

呢段演算法嘅流程圖

以下呢個係輾轉相除法嘅第個實現例子。佢淨係使用咗 6 個核心指令,相對於第一個例子嘅 13 個,俾好多人覺得係一個「靚」啲嘅演算法-因為學界一般都認為,所謂嘅「elegant」係指「用最少嘅指令類做最多嘅嘢」。佢用嗰種程式語言係以「LET [] = []」嚟設變數嘅數值嘅。

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "唔該打兩個大過 0 嘅整數"
  10 INPUT A,B
  20 IF B = 0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B = B - A
  50 GOTO 20
  60 LET A = A - B
  70 GOTO 20
  80 PRINT A
  90 END

如果用緊嘅程式語言係比較物件導向嘅話,可以用 Java 程式語言 噉做:

// Euclid's algorithm for greatest common divisor
integer euclidAlgorithm (int A, int B){
     A = Math.abs(A);
     B = Math.abs(B);
     while (B != 0){
          if (A > B) A = A - B;
          else B = B - A;
     }
     return A;
}

以上嘅呢啲演算法由相關領域嘅研究者用好多唔同嘅數字輸入試過,證實咗係掂嘅,亦都有數學家數學歸納法(mathematical induction)嘅方法證明咗佢真係行得通嘅[32][33]

解迷宮演算法[編輯]

用跟牆行演算法解一個迷宮嘅路線圖
內文: 解迷宮演算法

解迷宮演算法(maze solving algorithm)指一啲用嚟教電腦行迷宮嘅演算法[34][35],例如係好出名嘅跟牆行演算法(wall follower)噉,如果個迷宮裏面嘅牆冚唪唥都係相連住嘅(簡單噉連住嘅;simply connected),噉呢個迷宮用以下嘅方法就包保會解到:

  1. 將是但一隻手掂住個迷宮埲牆。
  2. 一路行一路隻手要掂住埲牆-唔可以中途放手。
  3. 如果個迷宮係簡單噉連住嘅,最後會行到去出口。
  4. 如果最後隻手返到去原先嘅位置,就表示個迷宮唔係簡單噉連住嘅。

解迷宮演算法喺機械人學(robotics)等嘅領域上好有用,因為呢類演算法可以用嚟教機械人探索佢哋四周圍嘅環境。

演算法分類[編輯]

要將演算法分類有好多種方法。

遞歸[編輯]

內文: 遞歸

遞歸(recursive)演算法係指一啲係噉行,直到達到某啲條件先會停嘅演算法[36]。遞歸演算法會用到以下嘅佈局:

for [x], do // 呢段嘢係叫部電腦「只要 [x] 呢個條件仲係成立嘅,噉就一路做以下嘅嘢」,所有主要嘅程式語言都有噉樣嘅指令。
   ...
   ...
   return y; // 最後俾返個輸出出嚟睇。

河內塔(Tower of Hanoi)係一個好出名、可以用遞歸演算法輕鬆解決嘅問題。

連串、平行、分散式[編輯]

內文: 連串演算法平行演算法、 同 分散式演算法

一般嚟講,啲人都假設咗演算法嘅每一步都係做完先做下一步嘅,而唔係同時有幾步喺度做緊嘅(註:現實世界嘅電腦行得好快,所以就算佢哋真係一步一步噉做,望落都好似係同時做緊幾步噉嘅樣)。所謂嘅連串式(serial)電腦就係指緊啲吓吓都做完一步先做下一步嘅電腦,而設計嚟俾呢啲電腦做嘢嘅演算法就係所謂嘅連串式演算法;但係現代嘅電腦功能好強,有能力同時處理幾樣作業,所以就有咗所謂嘅平行式(parallel)或者分散式(distributed)演算法,呢啲演算法會預咗部電腦能夠同時做幾樣作業,並且將要做嗰樣作業細分做幾件次作業,用佢哋解難嗰陣部電腦可能幾個部份喺度各自做緊運算解決緊各自手頭上嘅次作業。

決定性定非決定性[編輯]

內文: 決定性演算法非決定性演算法

所謂嘅決定性(deterministic)演算法喺每一個步驟嗰度由輸入去輸出都好精確,冇任何隨機性喺入面嘅,俾同一個輸入佢實會出同一個輸出[37];而非決定性(non-deterministic)演算法嘅運算過程會有啲不確定性喺入面,所以就算個輸入唔變,所俾嘅輸出都可能會有所不同[38]。非決定性演算法喺好多方面都好有用,例如係一個模擬啤牌遊戲嘅程式喺洗牌嗰陣就需要用到非決定性演算法,因為啤牌遊戲一般都係唔預咗啲玩家有能力預測嗮抽到嘅牌嘅。

近似性[編輯]

內文: 近似演算法

近似演算法(approximation algorithm)係指一啲會輸出一個唔確定數值嘅演算法[39]。好多演算法都係要求佢俾一個特定嘅數值做輸出嘅,例如係頭先提到嘅模擬牛頓定律嘅演算法噉,佢每一個輸出都係一個特定嘅數值。但係又有啲演算法會俾一個間隔出嚟,一個噉嘅演算法會答嘅唔係「目標數值係幾多」而係「目標數值相信係喺幾多同幾多之間」。呢種演算法喺好多問題嘅解決上都有價值,尤其係多種統計學嘅運算。

按所用嘅邏輯[編輯]

睇埋:邏輯編程

一個演算法可以當做一個受控制嘅演繹推理噉嚟睇,即係話一個演算法等如「邏輯」加「控制」(Algorithm = logic + control[40][41]。「邏輯」嗰部份表達咗呢場運算可以用嘅公理,而「控制」嗰部份表達推理可以點樣用落去啲公理嗰度。呢個係邏輯編程(logic programming)嘅基礎。喺純粹嘅邏輯編程當中,「控制」嗰部份係定死咗冇得變嘅,而演算法淨係會提供「邏輯」嗰部份。用邏輯編程嘅程式語言會用以下嘅句法:

H :- B1, …, Bn.;呢句嘢嘅意思係
H(係真)如果 B1 同 … 同 Bn 成立。

所以演算法可以透過睇佢哋用咗啲乜嘢邏輯推理嚟分類。

演算法分析[編輯]

內文: 演算法分析

演算法分析(analysis of algorithm)係電腦科學嘅一門子領域,專門對演算法嘅各種特性作出分析,尤其係對運算複雜度(computational complexity;指一個演算法用幾多資源去解決問題)嘅分析[42]:好多時,同一個問題可以用好多個唔同嘅演算法嚟去解決;因為噉,工程師同程式設計員等嘅人員好多時都會想知唔同嘅演算法當中邊啲好用啲,而要揾出個答案,佢哋就要知道每個演算法「所嘥嘅時間」同埋「用咗幾多行指令」等嘅資訊;某啲演算法可能(例如)用咗幾十行指令就解到第啲演算法要用成幾百行指令先解到嘅問題,前者行起上嚟會快啲,而且要儲落部電腦度嗰陣又會冇噉掗碇-自然啲人員會更加鍾意用呢個演算法,例如頭先提到嘅對分檢索就俾人評定為好用過「將數列入面嘅數逐個逐個睇一次」。

喺演算法分析當中,研究者好多時會齋靠抽象嘅數學符號嚟表達啲演算法,好多時根本唔使用真嘅程式語言寫低個演算法。所以喺某種意義上嚟講,演算法分析比較似係數學嘅一門子領域,雖然係噉,絕大部份嘅演算法去到最尾都係要用某啲硬件或者軟件平台嚟到執行嘅,而啲演算法執行嗰陣嘅效率就會俾人攞嚟評估個演算法。

演算法效率[編輯]

內文: 演算法效率

演算法效率(algorithmic efficiency)係演算法分析上至關重要嘅一個概念,指緊一個演算法要用幾多資源(用咗幾多行指令、幾多款指令呀噉)嚟解決一個特定嘅問題。假設其他因素唔變,一個演算法愈係可以用少嘅資源嚟解決一個問題,佢就會俾人覺得佢愈係有效率,而工程師同科學家一般都鍾意高效率嘅演算法。高效率嘅演算法可以有用得好交關:例如係處理圖像用嘅快速傅立葉變換(Fast Fourier Transform)噉,有研究試過,快速傅立葉變換演算法方面嘅改進令到醫療上嘅圖像處理快咗成 1,000 倍噉多[43]

法律問題[編輯]

睇埋:軟件專利

一個演算法嘅專利誰屬喺法律上係一個大問題[44]。通常就噉一個演算法係冇得攞去伸請專利嘅。喺美國,一個人係唔可以齋靠玩弄抽象概念、數字、或者訊號嚟到攞專利嘅,所以發明一個演算法冇得攞專利。之但係演算法嘅實現就可能有得伸請專利,例如如果有個人諗咗個新演算法出嚟,並且用某種程式語言寫咗段源碼嚟執行呢個演算法,噉嗰個人就有可能有得為嗰段源碼伸請專利[45]。雖然係噉,「軟件係唔係一樣應該有得攞專利嘅嘢」喺法學上係一門好有爭議性嘅課題,有唔少人都批評容許人為軟件伸請專利嘅做法[46]

睇埋[編輯]

參考書[編輯]

  • Berlinski, David (2001). The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer. Harvest Books. ISBN 978-0-15-601391-8. 
  • Chabert, Jean-Luc (1999). A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. ISBN 978-3-540-63369-3. 
  • Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction To Algorithms, Third Edition. MIT Press. ISBN 978-0262033848. 
  • Harel, David, Feldman, Yishai (2004). Algorithmics: The Spirit of Computing. Addison-Wesley. ISBN 978-0-321-11784-7. 
  • Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information.
  • Knuth, Donald E. (2010). Selected Papers on Design of Algorithms. Stanford, California: Center for the Study of Language and Information.
  • Wallach, Wendell; Allen, Colin (November 2008). Moral Machines: Teaching Robots Right from Wrong. USA: Oxford University Press. ISBN 978-0-19-537404-9. 

[編輯]

  1. "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
  2. Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
  3. "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
  4. "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
  5. "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
  6. 6.0 6.1 Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons.
  7. Stone 1973:4.
  8. Boolos and Jeffrey 1974,1999:19.
  9. Minsky 1967, p. 105.
  10. Gurevich 2000:1, 3.
  11. Stone simply requires that "it must terminate in a finite number of steps" (Stone 1973:7–8).
  12. Boolos and Jeffrey 1974,1999:19.
  13. Knuth 1973:7 states: "In practice we not only want algorithms, we want good algorithms ... one criterion of goodness is the length of time taken to perform the algorithm ... other criteria are the adaptability of the algorithm to computers, its simplicity and elegance, etc."
  14. Stone 1973:7–8 states that there must be, "...a procedure that a robot [i.e., computer] can follow in order to determine precisely how to obey the instruction." Stone adds finiteness of the process, and definiteness (having no ambiguity in the instructions) to this definition.
  15. 15.0 15.1 15.2 Background: Algorithms.
  16. Sipser 2006:157.
  17. Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, Inc.
  18. Mohr, Austin. "Quantum Computing in Complexity Theory and Theory of Computation". p. 2. Retrieved 7 June 2014.
  19. Instantly share code, notes, and snippets. GitHubGist.
  20. Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857.
  21. Dean, B. C. (2006). "A simple expected running time analysis for randomized "divide and conquer" algorithms". Discrete Applied Mathematics. 154: 1–5.
  22. Quicksort with Python.
  23. 23.0 23.1 Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603.
  24. Willams, Jr., Louis F. (22 April 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM.
  25. 25.0 25.1 25.2 Integration Basics: How to integrate the equations of motion. Gaffer on Games.
  26. van der Burg, John (23 June 2000). "Building an Advanced Particle System". Gamasutra.
  27. "Euclid's Elements, Book VII, Proposition 2". Aleph0.clarku.edu.
  28. Heath 1908:300; Hawking's Dover 2005 edition derives from Heath.
  29. For modern treatments using division in the algorithm, see Hardy and Wright 1979:180, Knuth 1973:2 (Volume 1), plus more discussion of Euclid's algorithm in Knuth 1969:293–297 (Volume 2).
  30. Euclidean Algorithm. Wolfram MathWorld.
  31. Knuth 1973: 2-4.
  32. Knuth 1973:13–18. He credits "the formulation of algorithm-proving in terms of assertions and induction" to R. W. Floyd, Peter Naur, C. A. R. Hoare, H. H. Goldstine and J. von Neumann. Tausworth 1977 borrows Knuth's Euclid example and extends Knuth's method in section 9.1 Formal Proofs (pages 288–298).
  33. Tausworthe 1997:294.
  34. Mishra, S., & Bande, P. (2008, November). Maze solving algorithms for micro mouse. In Signal Image Technology and Internet Based Systems, 2008. SITIS'08. IEEE International Conference on (pp. 86-93). IEEE.
  35. Wyard-Scott, L., & Meng, Q. H. (1995, May). A potential maze solving algorithm for a micromouse robot. In Communications, Computers, and Signal Processing, 1995. Proceedings., IEEE Pacific Rim Conference on (pp. 614-618). IEEE.
  36. Recursive Algorithm.
  37. Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). Parallel Programming Must Be Deterministic by Default. USENIX Workshop on Hot Topics in Parallelism.
  38. Robert W.Floyd (October 1967). "Nondeterministic Algorithms". Journal of the ACM. pp. 636–644.
  39. Bernard., Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press.
  40. Kowalski 1979.
  41. Logic programming. Computer Hope.
  42. Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective. Cambridge University Press.
  43. Gillian Conahan (January 2013). "Better Math Makes Faster Data Networks". discovermagazine.com.
  44. Bessen, James; Meurer, Michael (2008). Patent Failure. Princeton University Press.
  45. Patents for computer-related inventions. IP Australia.
  46. Nichols, Kenneth (1998). Inventing Software: The Rise of "computer-related" Patents. Greenwood Publishing Group. p. 15.