# 演算法學習草記

**What is an Algorithm?**
     An algorithm is A finite, definite, effective procedure, with some output.

**演算法現實情境使用的難度:**
     釐清現在所遇到的問題, 因為現實生或中遇到的都是散亂不堪的, 要從中找到規則並釐清問題的本質不容易.

### 是從 stable matching 的題目來做開場, 題目是:
- 有 N 個男女要做配對
- 配對結果對每位是最好的
- 不會有沒有配對到的
- 每個人會各交一份依據喜愛程度作排序的清單, 沒有平局(tie)的
- 配對的結果要是穩定的, 不會有人想要離婚(divorce)

#### 一個經濟學家 Gale Shapley 提出了範例並且得到了諾貝爾獎 propose and reject:
- 設定三種狀態: 未配對(free), 訂婚(engaged), 結婚(married)
- 男向女薦舉, 女方可以同意或者拒絕.
- 整個結果出來之前, 以配對的狀態為 engaged. 如果女方遇到更好的 propose 可以換.

:::info
**Gale Shapley 算法**

initialize each person to be free

while(some man m is free and hasn't proposed to every woman) do
    w = heighest ranked woman in m's list to who m has not yet proposed
    if(w is free) then
        (m, w) become engaged
    else if (w prefers m to her fiance未婚夫 m')
        (m, w) become engaged
        m' become free

return the set S of engaged pairs

stable matching 通常運用於配對喜好上, 比如大學放榜, 醫學院學生畢業選填醫院時...
:::

### 五個代表性問題: 舉例五個問題會有相對應的演算法產生, 並且算出時間複雜度.

### Back to Stable Matching - Proof
- 通常使用兩種方式來證明: 反證法 與 數學歸納法

- formulating the problem
- Given
- M: n men
- W: n women
- M x W: 每位男女各有依據喜愛程度從 1 排到 N 的清單.
- Goal:
- 每位男女皆配對
- 每位組合揭示穩定的

- Correctness(正確性)
- Termination: G-S algorithm terminates after at most n^2 iterations.
- perfection: Everyone gets married.
- stability: The marriages are stable.

:::info
:bulb: 用程式來解決問題, 先釐清問題制定規則後用紙筆寫下 procedure, 並驗證正確性與是否能達到目標後在開始寫程式. (反過來做好像比較快? 其多數會走很多冤枉路.)
:::

#### Correctness: Termination
- 使用數學歸納法推導出最多執行幾次會終止.
Proof:
- 從 **Gale Shapley 算法** 中看出來
- 看第三行: 男生狀態可能會從 engaged 變為 free, 代表著不固定狀態不好去計算 while 最多會有幾次.
- 就改由從男生一定會 propose, 那最差的情況是到最後一位才成功. 所以迭代最多次數為 n^2

#### Correctness: Perfection
- 使用反證法來推論
- 根據算法或目標來去提出假設
Proof:
- Suppose that G-S algorithm terminates with a free man m.
- At termination, m had already proposed to every woman. Otherwise, the while loop would not have exited.