# 演算法

## 定義

1. 有某啲特定嘅次序；
2. 唔具有歧義（ambiguity）嘅問題；
3. 有得攞部理想嘅運算機械－即係有圖靈完整性（Turing completeness）嘅機械－嚟行；
4. 曉自己結束運行－即係話可以係有限嘅時間之內行完，並且俾一個輸出出嚟睇，唔會有無限迴圈（infinite loop）嘅問題[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."粵文翻譯：由於受到速度、長度同大細嘅限制，冇人類能夠將一個「列舉到嘅無限集」（enumerably infinite set）包含嘅物件用某啲符號寫嗮出嚟。但對住某啲列舉到嘅無限集，人能夠做一啲同等有用嘅嘢（指演算法）：佢哋識得俾一啲指示出嚟，去搵出個集所包含嘅第 n 件物件，當中 n 可以係是但一個細過無限大嘅整數。呢啲指示都要幾明確至得，要有一個形式，令到曉計數嘅機器（電腦）或者一個淨係曉用符號嘅人能夠跟從佢哋。 」

## 表達

1. 設一個變數，叫佢做「max」，並且將佢個數值設做「0」；
2. 將收到嗰列正數逐個逐個攞嚟同 max 比較吓；
3. 如果撞到一個大過 max 嘅數（叫呢個數做「x」）嘅話，將 max 嘅數值設做 x，並且繼續將 max 同下個正數比較吓；（邏輯代數）
4. 將最後得出嗰個 max 嘅數值俾出嚟（輸出）。max 嘅數值會係成列數入面最大嗰個。

```# Input：一列冧巴，叫列冧巴做「L」。
# Output：L 入面最大嘅冧巴。

def find_max (L):
max = 0         # 設最大值做 0。
for x in L:     # 同 L 入面每個元件做以下嘅嘢...
if x > max:       # 如果 x 大過最大值...
max = x         # ... 設最大值做 x。
return max      # 做完嗮上述嘅嘢後，俾返個最大值出嚟。
```

### 三大層次

1. 高層描述（high-level description）：會描述一個演算法要做乜嘢運算，但就忽略點樣將個演算法實行落去部運算機械嗰度。一般人會睇得明，但運算機械唔會[註 1]。可以睇埋高階程式語言虛擬碼
2. 實行性描述（implementation description）：會話俾一部圖靈機知要點樣郁同要點樣將啲數據儲喺啲數據庫嗰度。喺呢個層次仲未會話到運算過程嗰啲中介狀態同埋函數嘅詳情俾人知。
3. 形式描述（formal description）：最仔細，會講明埋運算過程嗰啲中介狀態同函數。

• 一個簡單嘅異或門（XOR gate）會收兩個輸入，如果兩個輸入值一樣，個門會俾「0」，如果兩個輸入值唔同，個門會俾「1」（A XOR B）；
• 一個簡單嘅與門（AND gate）會收兩個輸入，只有當兩個輸入都係「1」嗰陣，個門先會俾「1」（A AND B）；

A B C S
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 0

``` a = 1 + 1;
```

## 出名演算法

### 搜尋演算法

#### 窮舉搜尋

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 嘅數值攞嚟做輸出。
```

#### 對分檢索

```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
```

### 排序演算法

#### 快速排序

1. 喺個數列入面是但揀個數字，設佢做基準（pivot）。
2. 重新排序數列：將個數字重新排過，數值上細過個基準嘅數字冚唪唥搬去個基準前面，而數值上大過個基準嘅數字就冚唪唥搬嗮去個基準後面；做咗呢個步驟之後，個基準會喺正佢嘅最終位置。
3. 將個數列斬做兩橛－「細過個基準嗰柞數字」同埋「大過個基準嗰柞數字」，並且分別噉對嗰兩橛做上述嗰兩個步驟。

```def sort(array=[12,4,5,6,7,3,1,15]): # 定義一個子程序，array 係要處理嗰個數列。
less = []
equal = []
greater = [] # 設三個陣列。

if len(array) > 1:
pivot = array[0] # 揀最頭個數做 pivot。
for x in array: # 將 array 當中每一個數 x...
if x < pivot: # 如果 x < pivot... 將 x 加落去 less 呢個陣列嗰度。
less.append(x)
if x == pivot: # 如果 x = pivot... 將 x 加落去 equal 呢個陣列嗰度。
equal.append(x)
if x > pivot: # 如果 x > pivot... 將 x 加落去 greater 呢個陣列嗰度。
greater.append(x)
return sort(less)+equal+sort(greater) # 喺 Python 入面，「+」可以代表「將兩個陣列拼埋一齊」；將 less、equal 同 greater 砌埋一齊做輸出。
else:
return array
# 個子程序會以 less 同 greater 做輸入再行過，行若干次，行到輸入嘅長度係 0 為止。
```

#### 冒泡排序

( 5 1 4 2 8 ) → ( 1 5 4 2 8 )，5 > 1，所以將 5 同 1 位置互換，
( 1 5 4 2 8 ) → ( 1 4 5 2 8 )，5 > 4，所以將 5 同 4 位置互換，
( 1 4 5 2 8 ) → ( 1 4 2 5 8 )，5 > 2，所以將 5 同 2 位置互換，
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )，5 < 8，所以 5 同 8 唔使郁。

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )，查實到咗呢一步，個數列經已排好咗，但段演算法要再重新睇多次個數列先至知呢一點。

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

### 輾轉相除法

``` 1599 = 650 × 2 + 299
650 = 299 × 2 + 52
299 = 52 × 5 + 39
52 = 39 × 1 + 13
39 = 13 × 3 + 0
```

1. 要搵佢哋最大公因數當中，大啲嗰個設做 ${\displaystyle a}$ ，細啲嗰個設做 ${\displaystyle b}$
2. ${\displaystyle b}$  乘大佢，睇吓要乘幾先會變到大過 ${\displaystyle a}$ ，即係話 ${\displaystyle a=qb+r}$ －喺呢條算式入面，${\displaystyle q}$  會係一個正整數，而 ${\displaystyle r}$  係一個餘數；
3. 睇吓 ${\displaystyle r}$  係唔係等如零；
4. 如果係嘅話，${\displaystyle b}$  就係要搵嗰個最大公因數；
5. 如果唔係嘅話，將 ${\displaystyle b}$ ${\displaystyle r}$  當中大啲嗰個設做 ${\displaystyle a}$ ，細啲嗰個設做 ${\displaystyle b}$
6. 跳返去步驟 2。

``` 1 [設兩個變數－L 同 S，並且將佢哋嘅數值設做 ${\displaystyle l}$  同埋 ${\displaystyle s}$  嘅]
INPUT L, S
2 [將 ${\displaystyle R}$  初始化：將個餘數嘅值設做等如 ${\displaystyle l}$  嘅]
R ← L
```

E0：確保 ${\displaystyle r\geq s}$

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

E1：搵個餘數出嚟－將 ${\displaystyle S}$ ${\displaystyle R}$  減出嚟，減到得出嘅餘數 ${\displaystyle r}$  細過 ${\displaystyle S}$  為止。

``` 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：將 ${\displaystyle S}$ ${\displaystyle r}$  對調，用 ${\displaystyle L}$  嚟做啲數字嘅中轉站。

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

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

``` 16  HALT, END, STOP.
```

```  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
```

```// 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;
}
```

### 搵路演算法

• 攞一幅圖做輸入 `input`：呢類演算法通常唔能夠直接處理一個環境，而係要靠第個演算法，`simplify`，將個環境變成一幅（graph）；圖論（graph theory）當中嘅一幅圖會有若干個節點（node），並且指明邊啲節點之間有連結，喺應用上，一個可能嘅做法係個輸入最先嗰個數字代表節點嘅數量，跟住嘅數字表示邊啲節點之間有連結（睇埋陣列），例如 `[6, 1-2, 1-5, 2-5, 2-3, 5-4, 3-4, 4-6]` 表示幅圖有 6 個節點，節點 1 同節點 2 之間有連結（可以由節點 1 行去節點 2 或者相反）、節點 1 同節點 5 之間有連結（可以由節點 1 行去節點 5 或者相反）... 如此類推；`simplify` 要做嘅嘢係攞要探索嗰個環境做輸入，輸出一個表示個環境當中有邊啲重要位置（節點）同邊啲位置之間有路能夠互通（連結）嘅圖，等搵路演算法做嘅嘢容易啲[41]
• 喺電子遊戲入面用嘅搵路演算法通常會用權重表（weighted graph），意思即係話個表每條連結都會有個數值[註 3]，表示嗰條路線嘅成本（cost）[43]：例如有一個 `simplify` 演算法會每條路都俾個權重值佢，個數值愈大表示條路愈難行（成本高）；想像其中兩個節點之間有兩條可能路線 `a``b``a` 係一條完全冇機關嘅平路，而 `b` 長過 `a` 之餘仲有十個陷阱設咗喺度，噉正路嚟講，假設 `a``b` 喺其他因素上完全相等，`b` 嘅權重值理應會大過 `a`[44]
• 最後個演算法會俾一條路線嚟做輸出 `output` [45]

```def pathfindDijkstra(graph, start, end): // 個演算法有三個 input，個圖（graph）、起點（start）同終點（end）
struct NodeRecord: // 個演算法需要三件資訊：
node // 節點
connection // 連結
costSoFar // 「目前嘅成本」

// 初始化
startRecord = new NodeRecord()
startRecord.node = start
startRecord.connection = None
startRecord.costSoFar = 0
open = PathfindingList() // 「開放表」（open list）
open += startRecord // 將起點加入開放表。
closed = PathfindingList() // 「封閉表」（closed list）

// while 開放表入面仲有嘢，做...
while length(open) > 0:
current = open.smallestElement() // 攞開放表入面最細嗰件做現時點。
if current.node == goal: break // 如果現時點係終點，break。
// 如果冇 break 到，個程式會繼續行落去...
connections = graph.getConnections(current) // 將同現時點有連結嘅節點冚唪唥搵嗮出嚟。

for connection in connections: // 同搵到嘅連結每個做以下嘅嘢...
endNode = connection.getToNode() // 設嗰條連結去嘅點做終點。
endNodeCost = current.costSoFar + connection.getCost() // 計個成本。
if closed.contains(endNode): continue // 如果嗰點係冇路走嘅，skip 去計下一條連結。
else if open.contains(endNode):
endNodeRecord = open.find(endNode)
if endNodeRecord.cost <= endNodeCost: continue // 如果呢個點嘅成本並唔細過已知嘅點嘅話，skip 去計下一條連結。
else:
endNodeRecord = new NodeRecord() // else，將呢個點加入紀錄嗰度。
endNodeRecord.node = endNode
// Update 成本同連結
endNodeRecord.cost = endNodeCost
endNodeRecord.connection = connection
// 再將呢點加入開放表嗰度。
if not open.contains(endNode):
open += endNodeRecord
// 將現時點移出開放表，並且加佢入封閉表。

open -= current
closed += current

// 做完個 while 之後...
if current.node != goal: // 如果冇去到終點嘅話，表示搵路失敗。
return None
else: // 否則，compile 一個列嗮搵到嗰條路涉及嘅連結嘅表，表示條路線。
path = []
while current.node != start:
path += current.connection
current = current.connection.getFromNode()
return reverse(path) // 將條路線俾出嚟做 output。
```

### 模擬牛頓定律

1 冇任何物理法則。
2 有重力，但冇碰撞探測
3 有重力同碰撞探測，但冇剛體動力學
4 有齊所有基本嘢。

```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;
}
```

```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
```

## 分類準則

### 有冇遞歸

```function dream()
print "Dreaming"
dream() // dream 呢個子程式當中用到自己。
```

```int gcd(int A, int B) { /* gcd 係一個子程式，攞 A 同 B 兩個數做 input */
if (B == 0) /* 如果 B = 0... */
return A; /* ... 俾 A 做輸出 */
else if (A > B)
return gcd(A-B,B); /* 用 (A-B) 同 B 做輸入，行多次 gcd */
else
return gcd(A,B-A); /* ... */
```

### 係咪近似性

1. 加減 ${\displaystyle x}$ ${\displaystyle y}$  嘅數值嚟改變個模型，即係個模型有 4（${\displaystyle +x,-x,+y,-y}$ ）個前進方向；
2. 計四個數值 ${\displaystyle z_{1},z_{2},z_{3},z_{4}}$ ，當中 ${\displaystyle z_{i}}$  係移去第 ${\displaystyle i}$  個方向會得到嘅 ${\displaystyle z}$  值；
3. 按「揀 ${\displaystyle z}$  值最小化嘅方向」呢條法則嚟改變 ${\displaystyle x}$ ${\displaystyle y}$  嘅數值；
4. 重複，直至結束條件達到為止。

### 按點樣處理複雜性

#### 分治演算法

1. 將個問題斬開若干件；
2. 睇吓每件有幾複雜（複雜度可以用多種指標量度，例如數字多嘅陣列可以當係比較複雜）；
3. 如果一件嘅複雜度仲未低到去到目標水平嘅話，重複。

#### 回溯法

1. 檢查吓搵到答案未，如果搵到（true）嘅話，終止程式；
2. 建立答案嘅一步（例：如果解嘅係數獨，是但填一個可能數字），
3. 如果目前狀態冇可能達到目的，噉就重新做過；
4. 重複。

### 按運算複雜度

• 恆定時間（constant time）：無論輸入幾大都會嘥同樣咁多時間嘅，`O(c)`，當中 ${\displaystyle c}$  係一個常數
• 線性時間（linear time）：所嘥嘅時間同輸入嘅大細（以位元計）成簡單嘅正比或者反比`O(n)`
• 對數時間（logarithmic time）：所嘥嘅時間同輸入嘅大細嘅對數成正比或者反比，`O(log n)`
• 多項式時間（polynomial time）：所嘥嘅時間同輸入嘅大細嘅若干次方成正比或者反比，`O(na)`，當中 ${\displaystyle a}$  係一個常數。
• 指數時間（exponential time）：所嘥嘅時間同輸入嘅大細嘅指數函數成正比或者反比，`O(bn)`，當中 ${\displaystyle b}$  係一個常數。

... 等等。

## 設計

1. 定義好個演算法要解決嘅問題；
2. 整返個模型嚟去描述嗰個問題；
3. 諗一個演算法出嚟；
4. 檢查吓個演算法有冇問題；
5. 分析吓個演算法嘅運算複雜度等嘅表現指標（演算法分析）；
6. 實行個演算法；
7. 程式測試
8. 做好啲文件上嘅紀錄。

## 註釋

1. 即係話抽象化嘅程度「高」。
2. ${\displaystyle \log }$  係指對數
3. 喺實際應用上，呢啲數值通常一定係 0 或者正數，因為好多常用嘅搵路演算法一撞到負數嘅權重值就會出錯。
4. 有啲演算法仲會精細到考慮埋連結之間嘅方向性：即係有啲路可能淨係可以向其中一個方向通行，又或者由一個方向行嘅成本同由第個方向行嘅唔同。
5. 不過喺現實應用上，因為電腦硬件唔係完美 100% 可靠，所以演算法行起上嚟點都會有好微細機會率（例如 0.00001%）會出錯。
6. 例如係「個模型嘅犯錯率」。
7. 每個國家地區嘅政府喺呢方面都係獨立嘅，所以如果想要喺每個國家地區都享有專利，發明者就要逐個逐個國家地區申請。

## 參考文獻

• Boolos, George; Jeffrey, Richard (1999) [1974]. Computability and Logic (4th ed.). Cambridge University Press, London. ISBN 978-0-521-20402-6.: cf. Chapter 3 Turing machines where they discuss "certain enumerable sets not effectively (mechanically) enumerable".
• Gurevich, Y. (2000). Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol. 1, no. 1, pp. 77–111.
• 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.
• Minsky, Marvin (1967). Computation: Finite and Infinite Machines (1st ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN 978-0-13-165449-5. Minsky expands his "...idea of an algorithm – an effective procedure..." in chapter 5.1 Computability, Effective Procedures and Algorithms. Infinite machines.
• Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company. ISBN 978-0-534-94728-6.
• Stone, Harold S. (1971). Introduction to Computer Organization and Data Structures. McGraw-Hill, New York. ISBN 978-0-07-061726-1. Cf. in particular the first chapter titled: Algorithms, Turing Machines, and Programs. His succinct informal definition: "...any sequence of instructions that can be obeyed by a robot, is called an algorithm" (p. 4).
• Tausworthe, Robert C (1977). Standardized Development of Computer Software, Part 1 Methods. Englewood Cliffs NJ: Prentice–Hall, Inc. ISBN 978-0-13-842195-3.
• Turing, Alan M. (1936–37). "On Computable Numbers, With An Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42: 230–265. doi:10.1112/plms/s2-42.1.230.. Corrections, ibid, vol. 43(1937) pp. 544–546.
• Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 45: 161–228.

## 攷

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. "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).
4. "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs." (Knuth, 1973:5).
5. "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).
6. Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley.
7. Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons.
8. Stone, 1971.
9. Boolos and Jeffrey, 1974,1999:19.
10. Minsky, 1967, p. 105.
11. Gurevich, 2000:1, 3.
12. Stone simply requires that "it must terminate in a finite number of steps" (Stone, 1972:7–8).
13. Boolos and Jeffrey, 1974,1999:19.
14. 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."
15. Stone, 1971: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.
16. Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press.
17. Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
18. Background: Algorithms. 互聯網檔案館歸檔，歸檔日期2018年7月3號，.
19. Sipser, 2006:157.
20. Lai, Hung Chi; Muroga, Saburo (September 1979). "Minimum Binary Parallel Adders with NOR (NAND) Gates". IEEE Transactions on Computers. IEEE. C-28 (9): 648–659.
21. Anthony J. Pansini, Electrical Distribution Engineering, p. xiv, The Fairmont Press Inc., 2006.
22. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
23. Instantly share code, notes, and snippets. GitHubGist.
24. Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603.
25. 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.
26. Sedgewick, Robert (1980), "Efficient Sorting by Computer: An Introduction", Computational Probability, New York: Academic Press, pp. 101–130.
27. Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857.
28. Dean, B. C. (2006). "A simple expected running time analysis for randomized "divide and conquer" algorithms". Discrete Applied Mathematics. 154: 1–5.
29. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.40.
30. Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF). ACM SIGCSE Bulletin. 35 (1): 1–5.
31. "Euclid's Elements, Book VII, Proposition 2". Aleph0.clarku.edu.
32. Heath, 1908:300; Hawking's Dover 2005 edition derives from Heath.
33. Euclidean Algorithm. Wolfram MathWorld.
34. 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).
35. Knuth, 1973: 2-4.
36. 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).
37. Tausworthe, 1997:294.
38. Cui, X., & Shi, H. (2011). A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security, 11(1), 125-130.
39. Boyarski, E., Felner, A., Stern, R., Sharon, G., Tolpin, D., Betzalel, O., & Shimony, E. (2015, June). ICBS: improved conflict-based search algorithm for multi-agent pathfinding. In Twenty-Fourth International Joint Conference on Artificial Intelligence.
40. Millington, I. (2019). AI for Games. CRC Press. Ch. 4.
41. Hagelback, Johan, and Stefan J. Johansson. "Dealing with fog of war in a real-time strategy game environment." In Computational Intelligence and Games, 2008. CIG'08. IEEE Symposium On, pp. 55-62. IEEE, 2008.
42. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0. "A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e."
43. Antsfeld, L., Harabor, D. D., Kilby, P., & Walsh, T. (2012, October). Transit routing on video game maps. In Eighth Artificial Intelligence and Interactive Digital Entertainment Conference.
44. Goodwin, S. D., Menon, S., & Price, R. G. (2006). Pathfinding in open terrain. In Proceedings of International Academic Conference on the Future of Game Design and Technology.
45. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601.
46. Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5.
47. Integration Basics: How to integrate the equations of motion. 互聯網檔案館歸檔，歸檔日期2018年10月26號，.. Gaffer on Games.
48. Van der Burg, John (23 June 2000). "Building an Advanced Particle System". Gamasutra.
49. Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. p. 197.
50. 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.
51. Robert W. Floyd (October 1967). "Nondeterministic Algorithms". Journal of the ACM. pp. 636–644.
52. What Is RNG in Video Games, and Why Do People Criticize It? 互聯網檔案館歸檔，歸檔日期2019年12月9號，.. How-To Geek.
53. Gary McGraw and John Viega. Make your software behave: Playing the numbers: How to cheat in online gambling.
54. Learning process of a neural network 互聯網檔案館歸檔，歸檔日期2021年2月11號，.. Towards Data Science.
55. Bernard., Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press.
56. For instance, the volume of a convex polytope (described using a membership oracle) can be approximated to high accuracy by a randomized polynomial time algorithm, but not by a deterministic one: see Dyer, Martin; Frieze, Alan; Kannan, Ravi (January 1991), "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies", J. ACM, New York, NY, USA: ACM, 38 (1): 1–17.
57. Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 111–114.
58. Carroll, Sue; Daughtrey, Taz (July 4, 2007). Fundamental Concepts for the Software Quality Engineer. American Society for Quality. pp. 282.
59. Allis, L. V. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Univ. Limburg, Maastricht, The Netherlands (1994).
60. van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Games solved: now and in the future. Artif. Intell. 134, 277–311 (2002).
61. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).
62. Blahut, Richard. Fast Algorithms for Signal Processing. Cambridge University Press. pp. 139–143.
63. Backtracking Algorithms. GeeksForGeeks.
64. Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
65. Braatz, R. P., Young, P. M., Doyle, J. C., & Morari, M. (1994). Computational complexity of/spl mu/calculation. IEEE Transactions on Automatic Control, 39(5), 1000-1002.
66. Black, Paul E. (11 March 2005). Black, Paul E. (ed.). "big-O notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology.
67. Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc.
68. Kolen, J. F., & Hutcheson, T. (2002). Reducing the time complexity of the fuzzy c-means algorithm. IEEE Transactions on Fuzzy Systems, 10(2), 263-267.
69. Mohr, Austin. "Quantum Computing in Complexity Theory and Theory of Computation". p. 2. Retrieved 7 June 2014.
70. Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, Inc.
71. Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective. Cambridge University Press.
72. Sedgewick, Robert; Flajolet, Philippe (2013). An Introduction to the Analysis of Algorithms (2nd ed.). Addison-Wesley.
73. Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser.
74. Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378.
75. Gillian Conahan (January 2013). "Better Math Makes Faster Data Networks". discovermagazine.com.
76. Bessen, James; Meurer, Michael (2008). Patent Failure. Princeton University Press.
77. Patents for computer-related inventions. IP Australia.
78. Nichols, Kenneth (1998). Inventing Software: The Rise of "computer-related" Patents. Greenwood Publishing Group. p. 15.