---
# System prepended metadata

title: 演算法

---

# 演算法
> 這是一個關於演算法的筆記[name=簡志融111010501]

> 大部分的程式碼來自 [ccc112a/py2cs/02-演算法](https://github.com/ccc112a/py2cs/tree/master/02-%E6%BC%94%E7%AE%97%E6%B3%95)
> 其餘另標註來源

## 摘要

[TOC]

## 第一週
> 凡是程式皆是算法；算法是方法，不受限於程式
> 算法要明確到可以寫成程式

> 房子的增值率會蓋過通貨膨脹(但得考慮折舊)
> (0050 + 富邦50 + VTI) + 房子土地 = ETF + 房子土地
> 覺得自己股票看得準的時候，你就準備大爆炸了；散戶總是賠錢

### [<Hello 算法>](https://www.hello-algo.com/)

> Big(O) : 函數漸進上界；在 n 很大時，c。f(n)一定會大於 T(n)
> ![image](https://hackmd.io/_uploads/HJP1_aVrp.png =80%x)
> ![asymptotic_upper_bound](https://hackmd.io/_uploads/B1qluTVH6.png =80%x)

> 如何推算時間複雜度?
> 針對程式，從上到下，逐行計算即可。由於上操作中的各種系數、
> 常數項都可以被忽略，根據此原則，總結出以下簡化技巧。
> 1. **忽略 T(n) 中的常數項**。因為它們都與 n 無關，所以對時間覆雜度不產生影響。
> 2. **省略所有系數**。例如，循環 3n 次、2n+5 次等，都可以簡化記為 n 次，
> 因為前面的系數對時間覆雜度沒有影響。
> 3. **循環嵌套時使用乘法**。總操作數量等於外層循環和內層循環操作數量之積，
> 每一層循環依然可以分別套用**第1點**和**第2點**的技巧。(內外迴圈)

> * 常見的複雜度:
> 常數階 : 函數
> 對數階 : 二分搜尋
> 線性階 : 線性搜尋
> 線性對數階 : 合併排序(很多排序都是)
> 平方階 : 泡沫排序、快速排序(最糟情況)
> 指數階 : 遞迴費波那契數列(非常接近)
> 階乘階 : 全排列
> ![image](https://hackmd.io/_uploads/HJQ_T6NSa.png =90%x)
> ![time_complexity_common_types](https://hackmd.io/_uploads/Hk_ZeRVrT.png =90%x)

<br/>

* [2.3.1   统计时间增长趋势](https://www.hello-algo.com/chapter_computational_complexity/time_complexity/)
    ```python=
    # 算法 A 的时间复杂度：常数阶
    def algorithm_A(n: int):
        print(0)
    # 算法 B 的时间复杂度：线性阶
    def algorithm_B(n: int):
        for _ in range(n):
            print(0)
    # 算法 C 的时间复杂度：常数阶
    def algorithm_C(n: int):
        for _ in range(1000000):
            print(0)
    ```
    n 越大的情況下，algorithm_B 的時間複雜度最高，Big(O)也最大
    ![time_complexity_simple_example](https://hackmd.io/_uploads/SJyyPaNBa.png =80%x)

### 查表法
* 查表法
    * 翻譯(逐字翻譯)
    * 費氏數列(建表)
    * 組合CnK recursive查表(巴斯卡三角形)

## 第二週
> 遞迴比迴圈簡單

> Lisp、Haskell 純函數式語言(Functional programing)
沒有迴圈只有遞迴(可以用遞迴模擬迴圈)

> 列舉衍伸為暴力(全部都找一遍)
 
> 挖比特幣看雜湊值前面幾個前導0
> 比特幣來源 : 挖礦 / 維護(?
> 第一筆:0.0041USD

### 列舉 & 雜湊
* **列舉法**
    * 系統列舉法(TruthTable)
    * 隨機列舉法(快速搜尋樣本)
    * 排列法
    * 組合法
* **雜湊法** : 毫無規則可循，好的、安全的雜湊無法逆向破解
    * SHA256：固定長度，一長串２進位顯示 (因256bit而得名)

### 區塊鍊底層原理
1. SHA256 Hash
2. Block
3. Blockchain : 將區塊串起來，達到不可否認性
   ![](https://hackmd.io/_uploads/B1mvdJdk6.png)
4. Distributed Blockchain(分散性機制) : 維護人驗證其他區塊是否正確(長者優先、多數決)
5. Tokens : 實現錢能夠交易
6. [Coinbase Transaction](https://cointelegraph.com/explained/what-is-a-coinbase-transaction)

* Q.為何比特幣須要幣所
    * A.集保概念，防止實體(私鑰)丟失

(Source : [blockchain demo](https://andersbrownworth.com/blockchain/))

## 第三週
> 在程式當中
> 0.1 + 0.2  = 0.30000000000000004
![](https://hackmd.io/_uploads/ryshwWZxp.png)
> (圖片來自 [IEEE754 wiki](https://zh.wikipedia.org/zh-tw/IEEE_754))

> [LLM幻覺](https://www.unite.ai/zh-CN/what-are-llm-hallucinations-causes-ethical-concern-prevention/)

> 將「混沌理論」應用在這個複雜的系統中，一個因素的微小變化，配合背後的連鎖反應，就會對整個系統造成巨大的影響。而這樣的現象，又被稱為「蝴蝶效應（Butterfly effect）」([Source](https://medium.com/marketingdatascience/%E7%B3%BB%E7%B5%B1%E8%A7%80%E9%BB%9E%E7%9A%84%E9%87%8D%E8%A6%81%E6%80%A7-%E6%B7%B7%E6%B2%8C%E7%90%86%E8%AB%96-%E8%9D%B4%E8%9D%B6%E6%95%88%E6%87%89-%E9%95%B7%E9%9E%AD%E6%95%88%E6%87%89%E8%88%87%E7%B3%BB%E7%B5%B1%E6%80%9D%E8%80%83-9d9bca21be1a))

### 暴力 & 迭代

> 暴力法通常可行，但害怕高維指數(2的n次、k的n次)
> 不能過度仰賴，但仍是一種解法

> 迭代法() : x = f(x) 、 x = f(g(x))
> 任何函數可如此表示，便可帶入數字，進行迭代


 * 迭代最後會出現三種情況:
       1. 收斂 : f(k) 近似於 f(k+1) ([正定](https://zh.wikipedia.org/zh-tw/%E6%AD%A3%E5%AE%9A%E7%9F%A9%E9%98%B5)&負定 是收斂的充要條件)
       2. 發散 : -/+ 無限大
       3. 震盪
       4. 既不發散也不收斂([混沌理論](https://zh.wikipedia.org/zh-tw/%E6%B7%B7%E6%B2%8C%E7%90%86%E8%AE%BA)) 

## 第四週
> 巴斯卡三角形代表排列組合之數目

> 機率的最後 : [中央極限定理](https://zh.wikipedia.org/zh-tw/%E4%B8%AD%E5%BF%83%E6%9E%81%E9%99%90%E5%AE%9A%E7%90%86)

> [LeetCode](https://leetcode.com/tag/recursion/)

> lamda : python 中的[匿名函數](https://zh.wikipedia.org/zh-tw/%E5%8C%BF%E5%90%8D%E5%87%BD%E6%95%B0)

### 遞迴法
* **遞迴法 (與不遞迴比，不見得比較快)**
    * 巴斯卡三角(c n取n)
    * **gcd(輾轉相除法、歐基里德算法)**
    * 費波那契數列
    * 河內塔
    * **生成語法**
    * 函數式語言 (a-1) + (b+1) = a+b ([皮亞諾公理](https://zh.wikipedia.org/zh-tw/%E7%9A%AE%E4%BA%9A%E8%AF%BA%E5%85%AC%E7%90%86))

### 函數式編程-1
* [py2cs/02-演算法/02-方法/04b-函數式編程/01-fp/fp.py](ccc112a/py2cs/blob/master/02-演算法/02-方法/04b-函數式編程/01-fp/fp.py)
    ```python=
    from functools import reduce

    a = range(1,5) #1-4
    print(list(map(lambda x:x*x, a))) # 映射 : 1 4 9 16
    print(list(filter(lambda x:x%2==1, a))) # 過濾(符合的留下) 1 3
    print(reduce(lambda x,y:x+y, a)) # 加總 10
    ```
* [py2cs/02-演算法/02-方法/04b-函數式編程/05-if/ifLazy.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/05-if/ifLazy.py)
    ```python=
    If = lambda cond, a, b: a() if cond else b()
    # 不用lamda函式呼叫，if會忽視條件直接計算遞迴，導致程式carsh
    Fibonacci = lambda n: \
      If(n<2, lambda:n, lambda:Fibonacci(n-1)+Fibonacci(n-2))

    print('Fibonacci(8)=', Fibonacci(8))
    ```
    
## 第五週
> [柯里化](https://zh.wikipedia.org/zh-tw/%E6%9F%AF%E9%87%8C%E5%8C%96)是一種處理函數中附有多個參數的方法，並在只允許單一參數的框架中使用這些函數

> ycombinator 用 **list** 可以表示一切

> pair 可將二任意物組合成 pair(a,b)，並定義取用 head 或 tail
> pair(1,pair(2,pair(3,pair(4,pair(5,null))))) = list 1~5

> 有理數 : 可以寫成分數的數

> [Lambda Calculus](https://en.wikipedia.org/wiki/Lambda_calculus) 圖靈完備 (Picture from wiki)
> ![](https://hackmd.io/_uploads/SJqQDtQ-a.png)

> [Turing-Church Hypothesis](https://zh.wikipedia.org/zh-tw/%E9%82%B1%E5%A5%87-%E5%9B%BE%E7%81%B5%E8%AE%BA%E9%A2%98) : 機器能力 = 語言能力

> [希爾伯特的23個問題](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98)

> 哥德爾 [不完備定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E4%B8%8D%E5%AE%8C%E5%A4%87%E5%AE%9A%E7%90%86) > 邱奇 停止問題原型 > 圖靈 [停機問題](https://zh.wikipedia.org/zh-tw/%E5%81%9C%E6%9C%BA%E9%97%AE%E9%A2%98)  (Picture from wiki)
> ![](https://hackmd.io/_uploads/S1tNOKmZp.png)

> [皮亞諾算術公理](https://zh.wikipedia.org/zh-tw/%E7%9A%AE%E4%BA%9A%E8%AF%BA%E5%85%AC%E7%90%86) :
> 1. 0 是自然數； 
> 2. 每一個確定的自然數a，都有一個確定的後繼數a' ，a' 也是自然數； 
> 3. 對於每個自然數b、c，b=c若且唯若b的後繼數=c的後繼數； 
> 4. 0 不是任何自然數的後繼數； 
> 5. 任意關於自然數的命題，如果證明：它對自然數0是真的，且假定它對自然數a為真時，可以證明對a' 也真。那麼，命題對所有自然數都真。

### 函數式編程-2
* [py2cs/02-演算法/02-方法/04b-函數式編程/08-list/pair.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/08-list/pair.py)
```python=
def pair(x, y):
    return lambda m : m(x, y) # 把 (x,y) 放入閉包中

def head(z):
    return z(lambda p,q : p) # 取出頭部

def tail(z):
    return z(lambda p,q : q) # 取出尾部
```
* [py2cs/02-演算法/02-方法/04c-LambdaCalculus/04-numerial/numerial.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04c-LambdaCalculus/04-numerial/numerial.py)
```python=
...
CONS = lambda x:lambda y:lambda f:f(x)(y) #equal to pair
CAR  = lambda p:p(TRUE)
CDR  = lambda p:p(FALSE)
...
```
<br/>

### [軟體工程](https://github.com/ccc112a/py2cs/tree/master/05-%E8%BB%9F%E9%AB%94%E5%B7%A5%E7%A8%8B)
#### Github
* fork : 想**增進**or**修改**他人的專案
* pull request : 可以把**變更的內容**向母專案管理者提出合併請求
* branch : 可以產生多版本分支，而後決定分支是否合併回主版本
* merge : 開 branch 將新增 data 存成不同版本
    * git add -A 比較不好，可能會丟一堆垃圾上去，可 add 多出的部分就好
    * git commit : 將 data 存到本地倉庫
* collaborator : 可設定權限，讓其他人可以共同協作
#### 測試軟體
* 測試用 unitest、assert 等測試用語句，做程式的單元測試
* 系統、整合、壓力、可用...，等測試來測試整套程式
* web 測試可用 [Puppeteer](https://pptr.dev/)、[Selenium](https://www.selenium.dev/)
* App 測試工具，e.g.[Testim](https://www.testim.io/)

## 第六週
> 影響程式解題的條件:
> * 設備
> * 選擇的語言
> * 自身程式觀念及技巧

> 微積分是現代科學的基礎，諸如地心引力到AI
> 13世紀啟蒙 >> 15世紀文藝復興 >> 16-17世紀科學的開端

> AI = 優化 = 評分 + 搜尋
> 將**偏微分(導數)加總**就是*最斜的角度* = [*梯度*](https://zh.wikipedia.org/zh-tw/%E6%A2%AF%E5%BA%A6)
> 深度學習便是幾千億個參數的加總
> (2維函數圖，Picture from wiki)
> ![](https://hackmd.io/_uploads/Hkkrxp3Za.png =32%x)

### 評分 & 改良
* 評分法
    * 排序:排得好不好
* 改良法
    * 隨機改良法
    * 逐步改良法
        * 爬山演算法
            ```shelll=
            #不一定爬到最高的山頂，但爬到最近的山頂
            Algorithm HillClimbing(f, x)
              x = 隨意設定一個解。
              while (x 有鄰居 x' 比 x 更高)
                x = x';
              end
              return x;
            end
            ```
        * 貪婪演算法
        * 梯度下降法

## 第七週
> 世界上目前能威脅人類生存的兩件事 : **核彈 & AI**

> **梯度下降演算法** & **反傳遞演算法** 是 AI 的核心
> 將 **x方向的斜率** 跟 **y方向的斜率** 合在一起 = **梯度**
> 朝著***逆梯度***的方向走 >>> ***梯度下降***
> 梯度下降法並非都適用，通常都有最小值 (e.g.錯誤率)

> 1970s 控制領域 反傳遞前身 >>> 1986 Hiton 反傳遞語音辨識 >>>2015 LeCun、Google
> 精進的是 AI model，而非反傳遞演算法，無標記

> 演算法在於速度；AI在於正確率
> 深度學習 << 梯度引擎 << 反傳遞 << 自動微分

> scikit-learn : Classification(分類，有標記)、Clustering(分群，無標記)、Regression(回歸)
* [Hacker's guide to Neural Networks](https://karpathy.github.io/neuralnets/)
![](https://hackmd.io/_uploads/SJFCGWIM6.png =70%x)

### 梯度下降法
* 梯度下降法
    * 找最小值
    * 直/曲線擬合

* [py2cs/02-演算法/02-方法/05f-梯度下降法/04-反傳遞算法/02-梯度引擎/ccc/engine.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/05f-%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95/04-%E5%8F%8D%E5%82%B3%E9%81%9E%E7%AE%97%E6%B3%95/02-%E6%A2%AF%E5%BA%A6%E5%BC%95%E6%93%8E/ccc/engine.py)
    ```python=
    class Value: # 含有梯度的值節點
        """ stores a single scalar value and its gradient """

        def __init__(self, data, _children=(), _op=''): #建構函數
            self.data = data # 目前值
            self.grad = 0 # 梯度預設為 0
            # internal variables used for autograd graph construction
            self._backward = lambda: None # 反傳遞函數
            self._prev = set(_children) # 前面的網路節點
            self._op = _op # the op that produced this node, for graphviz / debugging / etc

        def __add__(self, other): # 加法的正向傳遞 運算子重載 正傳遞
            other = other if isinstance(other, Value) else Value(other)
            out = Value(self.data + other.data, (self, other), '+') #要做拓蹼排序 要記錄前後

            def _backward(): # 加法的反向傳遞
                self.grad += out.grad #直接將梯度回傳 並梯度是累積的
                other.grad += out.grad
            out._backward = _backward

            return out

        def __mul__(self, other): # 乘法的正向傳遞
            other = other if isinstance(other, Value) else Value(other)
            out = Value(self.data * other.data, (self, other), '*')

            def _backward(): # 乘法的反向傳遞
                self.grad += other.data * out.grad
                other.grad += self.data * out.grad
            out._backward = _backward

            return out

        def __pow__(self, other): # 次方的正向傳遞
            assert isinstance(other, (int, float)), "only supporting int/float powers for now"
            out = Value(self.data**other, (self,), f'**{other}')

            def _backward(): # 次方的反向傳遞
                self.grad += (other * self.data**(other-1)) * out.grad #nX^n-1
            out._backward = _backward

            return out

        def relu(self): # relu 的正向傳遞
            out = Value(0 if self.data < 0 else self.data, (self,), 'ReLU')

            def _backward(): # relu 的反向傳遞
                self.grad += (out.data > 0) * out.grad
            out._backward = _backward

            return out

        def backward(self): #拓蹼排序，建立拓蹼順序結構

            # topological order all of the children in the graph
            topo = []
            visited = set()
            def build_topo(v): # 建立網路拓譜結構
                if v not in visited:
                    visited.add(v)
                    for child in v._prev:
                        build_topo(child)
                    topo.append(v)
            build_topo(self)

            # go one variable at a time and apply the chain rule to get its gradient
            self.grad = 1
            for v in reversed(topo): # 反向排列
                v._backward()
        # 以下這些運算，由於 + * 已被 override ，所以反向傳遞會自動建構，不需再自己加入反向傳遞函數
        def __neg__(self): # -self
            return self * -1

        def __radd__(self, other): # other + self
            return self + other

        def __sub__(self, other): # self - other
            return self + (-other)

        def __rsub__(self, other): # other - self
            return other + (-self)

        def __rmul__(self, other): # other * self
            return self * other

        def __truediv__(self, other): # self / other
            return self * other**-1

        def __rtruediv__(self, other): # other / self
            return other * self**-1

        def __repr__(self):
            return f"Value(data={self.data}, grad={self.grad})"
    ```
## 第八週
> [**模擬退火法**](https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB) : 給演算法自由，可往上或往下，不高處可以任意往下，但到高處往下需考慮
> 為爬山演算法之變形，實際應用上除非高點很低，不然依舊卡住

> **貪婪演算法** : 每次都往最好的方向走，觀念固然簡單 但實際的使用卻千變萬化
> [貪婪法圖形化 : Graph與DFS、BFS圖形走訪演算法](https://kopu.chat/%E5%AF%A6%E4%BD%9Cgraph%E8%88%87dfs%E3%80%81bfs%E8%B5%B0%E8%A8%AA/)

> [ELIZA](https://zh.wikipedia.org/zh-tw/ELIZA) : 是約瑟夫·維森鮑姆在麻省理工學院研發的聊天機器人。
> 該程式模擬一位羅傑斯式心理治療師回答使用者提出的文字陳述或問題。
> ![](https://hackmd.io/_uploads/BJh6SVkQT.jpg =75%x)

> [漢明碼 (Hamming code)](https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E7%A0%81) : 為了解決偵錯的問題，開發了功能日益強大的偵錯演算法。
> 在1950年，他發表了今日所稱的漢明碼

### 貪婪法-1
* 貪婪演算法
    * 霍夫曼編碼
    * 最小拓展樹
        * [Prim](https://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95) : 設定起始頂點，然後逐步擴展加入
        ![](https://hackmd.io/_uploads/HJuuE4y76.gif =50%x)
        * [Kruskal](https://zh.wikipedia.org/wiki/%E5%85%8B%E9%B2%81%E6%96%AF%E5%85%8B%E5%B0%94%E6%BC%94%E7%AE%97%E6%B3%95) : 將圖中所有的邊按權值從小到大排序(不形成迴圈就繼續)![](https://hackmd.io/_uploads/ByNtXNyXT.gif =50%x)![](https://hackmd.io/_uploads/Sy430myQ6.gif =40%x)

## 第九週
> [Entropy 資訊理論](https://zh.wikipedia.org/zh-tw/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)) : 是代表接收的每條消息中包含的資訊的平均量
> 又被稱為資訊熵、信源熵、平均資訊本體量。熵的資訊是凸的(數學上的凸性)

> 霍夫曼編碼很好地代表上述特性(熵與其高度相關)
> 越平均的資訊量分配，編碼長度越長；霍夫曼編碼長度比熵大一點(已經最佳)
> 一個物件提供的資訊量 = 意外性

> [隨機變數](https://zh.wikipedia.org/zh-tw/%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F) : 隨機變數通常用大寫字母X、Y表示。在各種隨機試驗中，每一個隨機事件都可以用一個變數代替任何一個數值。(某Y出現時，某X出現的機率)
> ![image](https://hackmd.io/_uploads/SyrgRux4T.png =60%x)


> [相互資訊](https://zh.wikipedia.org/zh-tw/%E4%BA%92%E4%BF%A1%E6%81%AF) : 衡量兩個資訊場之間，用Y預測X時，相互資訊的程度有多高
> [相對熵(KL散度)](https://zh.wikipedia.org/zh-tw/%E7%9B%B8%E5%AF%B9%E7%86%B5) : X、Y分別代表一隨機機率場，皆為隨機變數，
> [交叉熵](https://zh.wikipedia.org/zh-tw/%E4%BA%A4%E5%8F%89%E7%86%B5) : 找出兩個機率到底有多不相同，如果值很小，代表兩者機率幾乎相同

> Q : 亂度越來越大，為何還會產生有組織的事物?
> A : 根據熱力學第二定律，孤立系統會朝著最大亂度變化(宇宙是孤立系統，其一小部分(地球)則不是)

> 在數學上有所謂機率的樣本空間，如果在此空間中可以隨機抽取，就代表沒有前後的關係

> 額外的搜尋 : [Alpha-beta剪枝](https://zh.wikipedia.org/zh-tw/Alpha-beta%E5%89%AA%E6%9E%9D)、[極小化極大演算法](https://zh.wikipedia.org/zh-tw/%E6%9E%81%E5%B0%8F%E5%8C%96%E6%9E%81%E5%A4%A7%E7%AE%97%E6%B3%95)

* 神經網路算法中的三類問題 : 前二者常會使用損失函數
    * **Regression(回歸)** : 為擬合直線，使用最小平方法算點與線距離
    * **Classification(分類)** : 從數種類選一類，常以 softmax + CrossEntropy 兩個函數串接，作為最後的損失函數
    * Clustering(分群)

### 貪婪法-2
* 貪婪演算法
    * [霍夫曼編碼](https://zh.wikipedia.org/zh-tw/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81) : 其編碼方式保證**編碼總長度最小**，是一種與**過去無關**的**壓縮**方法；因使用一般排序法的代價太大(n logn)，所以在編碼過程中常用[堆積排序(Heap sort)](https://zh.wikipedia.org/zh-tw/%E5%A0%86%E6%8E%92%E5%BA%8F)，目的要達到至少小於n logn的時間複雜度
![Sorting_heapsort_anim](https://hackmd.io/_uploads/rJcUD_gNT.gif =50%x) ![Huffman_algorithm](https://hackmd.io/_uploads/SkaBEdxNa.gif =40%x) 
    * [py2cs/02-演算法/02-方法/05f-貪婪法/01-huffmanCode/huffmanCode1.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/05f-%E8%B2%AA%E5%A9%AA%E6%B3%95/01-huffmanCode/huffmanCode1.py)
    ```python=47
    while len(nodes) > 1: # Heap sort (?
        (key1, c1) = nodes[-1] # 取一個
        (key2, c2) = nodes[-2] # 取另一個
        nodes = nodes[:-2]
        node = NodeTree(key1, key2)
        nodes.append((node, c1 + c2)) # 加起來塞回去

        nodes = sorted(nodes, key=lambda x: x[1], reverse=True)
    ```
### 搜尋
* 搜尋法(狀態空間、圖論的搜尋) : 相鄰矩陣、陣列或字典表示
    * 深度優先(DFS) : 一直往下，直到沒了再回來；
      用**遞迴**會很好做(遞迴呼叫隱含一個堆疊(LIFO)，用函數的一層層框架做的)
    * 廣度優先(BFS) : 搜一，再搜相鄰的，以此類推；
      也能用**遞迴**，但須加一個queue(FIFO)，否則記不住已訪問的點

## 第十週
> 數學的基礎 : 集合、邏輯、函數、關係、證明
> 數學系 : 代數(抽象的加減乘除)、幾何(空間)、分析(連續函數；微分積分)
> 資工系的數學 : 微積分、線性代數、離散數學、工程數學、機率統計、數值分析

> [泰勒展開式](http://ccckmit.wikidot.com/ca:tylor):任何函數如果可以寫成多項式，一直微分，零點的泰勒級數又稱為麥克羅林級數。
> ![image](https://hackmd.io/_uploads/BkmbjnbNp.png)

> [傅立葉轉換](https://zh.wikipedia.org/zh-tw/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2)可以濾波，在影像壓縮時，使用傅立葉轉換將高頻波濾掉再還原成圖片，
> 影像幾乎無異，但體積壓縮成1/20

> 台灣承襲德式教育體系(新教)，馬丁路德看不慣教皇賣贖罪券，寫了九十五條論綱，流亡現德國附近，傳播新教，宣揚上帝在現世沒有代理人；為反教會洗腦，教信徒識字、讀聖經和幾何原本

> 拓樸學幾何能無限拉伸、壓縮、扭曲，但不可撕破挖洞
> *咖啡杯跟甜甜圈[同胚](https://zh.wikipedia.org/zh-tw/%E5%90%8C%E8%83%9A)*
> ![Mug_and_Torus_morph](https://hackmd.io/_uploads/ByYs1abE6.gif)
> [流形](https://zh.wikipedia.org/zh-tw/%E6%B5%81%E5%BD%A2)的鄰域要與 ***歐式空間(剛硬不可彎曲)*** 同胚
> 流形是介於拓樸空間(柔)與歐式空間(剛)的東東
> ![225px-MobiusStrip-01](https://hackmd.io/_uploads/BkWkZabNT.png)

> 完備度量空間 : 沒有縫隙、不缺皮；並且柯西序列會在空間收斂

> 群論證明五次以上的多項式沒有公式解
### 狼、羊、菜問題
* [py2cs/02-演算法/02-方法/06-搜尋法/Q2-river/river.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/06-%E6%90%9C%E5%B0%8B%E6%B3%95/Q2-river/river.py)
```python=
import sys

role  = ['人','狼','羊','菜']

def isDead(state): # 確立角色條件
    if state[1]==state[2] and state[0] != state[1]:
        return True
    if state[2]==state[3] and state[0] != state[2]:
        return True
    return False

def neighbors(state): # 找出鄰居
    peopleSide = state[0]
    nbList = []

    side2 = 1 if peopleSide==0 else 0
    p2state = state.copy()
    p2state[0] = side2 # 人移動到另一邊
    nbList.append(p2state) # 要考慮只有自己移動

    for i in range(1, len(state)):
        if state[i] == peopleSide:
            nbState = state.copy()
            nbState[0], nbState[i] = side2, side2
            nbList.append(nbState)
    return nbList

def dfs(state, role, visitedMap, goal, path):
    if isDead(state):return
    
    stateStr = ''.join(str(x) for x in state)
    if visitedMap.get(stateStr): return
    visitedMap[stateStr] = True

    print(state)
    path.append(state)
    if state == goal:
        print(f'{path}')
        sys.exit(1)
        return

    for nb in neighbors(state):
        dfs(nb, role, visitedMap, goal, path)

    path.pop()


start = [0,0,0,0]
goal = [1,1,1,1]
visitedMap = {}
path = []
print('start=', start)
dfs(start,role,visitedMap, goal, path)
```
## 第十一週
> 民調無法做到真正的隨機，除非逼所有有投票權人都發表意見

### 分割擊破、動態規劃、隨機-1
* 分割擊破法(Divide & Conquer)
    * 二元搜尋法
    * 二元矩陣搜尋法
    * 矩陣相乘 : [施特拉森演算法](https://zh.wikipedia.org/zh-tw/%E6%96%BD%E7%89%B9%E6%8B%89%E6%A3%AE%E6%BC%94%E7%AE%97%E6%B3%95)運用公式讓矩陣相乘重從8次乘法減為7次，
        複雜度從 O(n^3) 到 O(n^2.8074)
* 動態規劃法
    * 組合 C(n,k) : 畫出一[帕斯卡三角形](https://zh.wikipedia.org/zh-tw/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2)的表，一一算出
    * [編輯距離](https://zh.wikipedia.org/zh-tw/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2) : 可以用在自然語言處理中拼寫檢查的編輯距離，或判斷二個DNA的類似程度
    ![image](https://hackmd.io/_uploads/H11cT1oVp.png)
        ```python=
        #py2cs/02-演算法/02-方法/08-動態規劃法/editDistance/
        editDistance(ATGATCCG,ATGCAATCCC) = 3
        ======m=========
        [0,1,2,3,4,5,6,7,8,9,10]
        [1,0,1,2,3,4,5,6,7,8,9]
        [2,1,0,1,2,3,4,5,6,7,8]
        [3,2,1,0,1,2,3,4,5,6,7]
        [4,3,2,1,1,1,2,3,4,5,6]
        [5,4,3,2,2,2,2,2,3,4,5]
        [6,5,4,3,2,3,3,3,2,3,4]
        [7,6,5,4,3,3,4,4,3,2,3]
        [8,7,6,5,4,4,4,5,4,3,3]
        ================
        bx= ATG A TCCG
        ax= ATGCAATCCC
        ```
* 隨機法
    * [UUID](https://zh.wikipedia.org/zh-tw/%E9%80%9A%E7%94%A8%E5%94%AF%E4%B8%80%E8%AF%86%E5%88%AB%E7%A0%81) / GUID (似SHA256) : 為事件產生唯一代號，有可能衝突，但機率相當的小
    * 隨機亂數 : 如果方法及SEED被知道，便可生成一樣偽亂數
        * [py2cs/02-演算法/02-方法/09a-隨機法/random1.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09a-%E9%9A%A8%E6%A9%9F%E6%B3%95/random1.py)
            ```python=
            import time
            import math

            SEED_MAX = 9999997
            seed = time.time()%SEED_MAX

            def random():
                global seed
                seed = (seed+37) % SEED_MAX
                x = math.sin(seed) * 93177
                return x - math.floor(x)

            for _ in range(10):
              print(random())
            ```
    * 蒙地卡羅法 (不一定最好，也不一定正確): 
        * 估算π值
        ![Pi_30K](https://hackmd.io/_uploads/SkMaUloNp.gif =50%x)
        * [n維球面](https://zh.wikipedia.org/zh-tw/N%E7%BB%B4%E7%90%83%E9%9D%A2)
          * [py2cs/02-演算法/02-方法/09b-蒙地卡羅法/01a-ndBall/ndBall.py](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09b-%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%B3%95/01a-ndBall/ndBall.py)
            ```python=4
            def mcBallVolume(n, r, tries=100000):
                count = 0
                for i in range(tries):
                    vector = 2*r*np.random.random_sample(n)-r # 產生一N維隨機向量，-r中心回到原點
                    if np.linalg.norm(vector, 2) <= r: # 判斷點是否落於圓的範圍內
                        count += 1
                return (count/tries)*((2*r)**n)

            def ballVolume(n, r): # N維球體公式(超球)
                return pi**(n/2)/gamma(n/2+1) * (r**n)
            ```

## 第十二週
> [布萊克-休斯模型](https://zh.wikipedia.org/zh-tw/%E5%B8%83%E8%8E%B1%E5%85%8B-%E8%88%92%E5%B0%94%E6%96%AF%E6%A8%A1%E5%9E%8B) : 隨機微積分方程式 ([次貸危機](https://zh.wikipedia.org/zh-tw/%E6%AC%A1%E8%B2%B8%E5%8D%B1%E6%A9%9F))

> [P值](https://zh.wikipedia.org/zh-tw/P%E5%80%BC) : 為假說檢定中假設虛無假說為真時觀測到的至少與實際觀測樣本相同的樣本的機率。

> 在機率的推論上，可以倒果為因，但如果機率太小，依然會被否決
> [貝氏定理](https://zh.wikipedia.org/zh-tw/%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%AE%9A%E7%90%86) : 是機率論中的一個定理，描述在已知一些條件下，某事件的發生機率。
> ![e08d4ab0386c0ebb7d87f398cd38f911440fe3da](https://hackmd.io/_uploads/SJr3E74S6.svg)
> [單純貝氏分類器](https://zh.wikipedia.org/zh-tw/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%86%E7%B1%BB%E5%99%A8) : 過於天真的分類器

> 現在的反傳遞、梯度下降演算法速度太慢，每次都移動一小步
> 而受限波茲曼機速度比前者快速

> [通用人工智慧(AGI)](https://zh.wikipedia.org/zh-tw/%E9%80%9A%E7%94%A8%E4%BA%BA%E5%B7%A5%E6%99%BA%E6%85%A7)：傳說強人工智慧可能危害人類（？
> [What Is Retrieval-Augmented Generation aka RAG?](https://blogs.nvidia.com/blog/what-is-retrieval-augmented-generation/)
> [Q*](https://en.wikipedia.org/wiki/Q*) = [Q-learning](https://en.wikipedia.org/wiki/Q-learning) + [A* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm)

### 吉布斯 & 馬可夫
* [吉布斯採樣](https://zh.wikipedia.org/zh-tw/%E5%90%89%E5%B8%83%E6%96%AF%E9%87%87%E6%A0%B7) : 不斷矩陣相乘，最後會收斂，只要轉移矩陣確定，收斂的值都一樣(粗略平衡)
* [馬可夫模型](https://en.wikipedia.org/wiki/Markov_model)：雖然算機率，但只是數字相乘，沒有隨機採樣
    * [馬可夫鏈](https://zh.wikipedia.org/zh-tw/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE)
    ![330px-Markovkate_01.svg](https://hackmd.io/_uploads/ryqkCMNHa.png =60%x)
    * [隱藏式馬可夫模型](https://zh.wikipedia.org/zh-tw/%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8B) : 描述一個含有隱含未知參數的馬可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數。
### 隨機法-2
* 隨機法
    * 拉斯維加斯算法(用隨機和Random，為求快速，一定正確)
        * 快速排序
    * 蒙地卡羅法
        * 中央極限定理 : 在隨機且前後無關的條件下，只要樣本數夠大，會無限趨近於常態分布
        * [司徒頓t檢定](https://zh.wikipedia.org/zh-tw/%E5%8F%B8%E5%BE%92%E9%A0%93t%E6%AA%A2%E5%AE%9A)
            * 虛無假設
            * 對立假設
        * [Talent Vs Luck](https://pansci.asia/archives/355950)
        * mcmc(蒙地卡羅-馬可夫) : 模擬達到要求順序的機率
        * mcmcgibbs(...-吉布斯) : 模擬平衡機率(收斂時，a、b個別機率，0.625\*0.3 = 0.375*0.5)
        * [最大期望（EM）算法](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E5%A4%A7%E6%9C%9F%E6%9C%9B%E7%AE%97%E6%B3%95)
        * [受限玻爾茲曼機](https://zh.wikipedia.org/zh-tw/%E5%8F%97%E9%99%90%E7%8E%BB%E5%B0%94%E5%85%B9%E6%9B%BC%E6%9C%BA)
        ![330px-Restricted_Boltzmann_machine.svg](https://hackmd.io/_uploads/SyZVw7NHT.png =50%x)
    * [基因(遺傳)演算法](https://zh.wikipedia.org/zh-tw/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95) : 是進化演算法的一種。進化演算法最初是借鑑了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等等。(如果有好的父/母，演算法速度會快、結果好，但通常情況下，好的條件不成立)
        ```
        * 選擇初始生命種群
        * 迴圈
            * 評價種群中的個體適應度
            * 以比例原則（分數高的挑中機率也較高）選擇產生下一個種群（輪盤法（roulette wheel selection）、
              競爭法（tournament selection）及等級輪盤法（Rank Based Wheel Selection））。不僅僅挑分數
              最高的的原因是這麼做可能收斂到局部的最佳點，而非整體的。
            * 改變該種群（交叉和變異）
        * 直到停止迴圈的條件滿足
        ```
### A\*搜尋法
* Astar : 與Dijkstra相比，可以少走一些點；算法中少去曼哈頓便是Dijkstra(h(n)=0)
    ![Astar_progress_animation](https://hackmd.io/_uploads/ByC9UVEHa.gif =50%x)![Dijkstras_progress_animation](https://hackmd.io/_uploads/S1U1dEESa.gif =50%x)
    [py2cs/02-演算法/02-方法/06-搜尋法/05a-Astar](https://github.com/ccc112a/py2cs/tree/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/06-%E6%90%9C%E5%B0%8B%E6%B3%95/05a-Astar)
        ![image](https://hackmd.io/_uploads/HkZ3rV4Sp.png   =49%x) ![image](https://hackmd.io/_uploads/ry8VBVNS6.png =49%x)

## 第十三週
> [Python](https://zh.wikipedia.org/zh-tw/Python) : 1991首次釋出，2017左右走紅強勢，科學計算乃至深度學習

> [B-tree](https://zh.wikipedia.org/zh-tw/B%E6%A0%91) : 資料儲存(e.g.SQL) 背後的高度平衡樹


### 前處理、委託、分層、化約
* 前處理
    * 排序 : 加入每次都要重排(代價大)
    * 索引
    * 雜湊 : 找順序，不用排
* 委託法 : 不知道怎麼做，尋求外部其他方式 (套件)
    * [線性規劃](https://zh.wikipedia.org/zh-tw/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92) : 找線性條件下的最大值 ([單體法](https://zh.wikipedia.org/zh-tw/%E5%8D%95%E7%BA%AF%E5%BD%A2%E6%B3%95)、橢圓法)
* 分層法 : 系統太複雜就要分層
    * [EDA](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/15b-%E5%88%86%E5%B1%A4%E6%B3%95/EDA%E8%BB%9F%E9%AB%94%E7%9A%84%E5%B1%A4%E6%AC%A1.md)
    * OS
* 化約法 ([歸約](https://zh.wikipedia.org/wiki/%E6%AD%B8%E7%B4%84)，Reduction) : 將問題轉換成另一個問題，求解然後對應回原問題之解的方法。
    * [背包問題](https://zh.wikipedia.org/zh-tw/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98)
    * 整數規劃 : 與線性規劃相比，解必須是整數
        * [0-1背包問題](https://docs.python-mip.com/en/latest/examples.html#the-0-1-knapsack-problem)
        * [2D包裝問題](https://docs.python-mip.com/en/latest/examples.html#two-dimensional-level-packing)
        * [n-皇后問題](https://docs.python-mip.com/en/latest/examples.html#n-queens)
        * [SAT問題(布林可滿足性問題)](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem)
        * [TSP問題(旅行推銷員問題)](https://docs.python-mip.com/en/latest/examples.html#the-traveling-salesman-problem)

### 計算理論-1
#### NP-Complete (NP完備) 
![Complexity_classes.svg](https://hackmd.io/_uploads/Hy35tIpB6.png =50%x)

> [亞里斯多德:三段論](https://zh.wikipedia.org/zh-tw/%E4%B8%89%E6%AE%B5%E8%AB%96) : 無法推出所有定理，即使定理是對的
> 
> [歸結原理(resolution)](https://zh.wikipedia.org/zh-tw/%E5%BD%92%E7%BB%93%E5%8E%9F%E7%90%86) : **可以**推出所有定理
>  P → Q；Q → R，所以 P → R

> [一階邏輯(謂詞邏輯)](https://zh.wikipedia.org/zh-tw/%E4%B8%80%E9%98%B6%E9%80%BB%E8%BE%91) : **不可以**把函數當參數
> [二階邏輯(命題邏輯)](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E9%9A%8E%E9%82%8F%E8%BC%AF) : **可以**把函數當參數

> 
#### 邏輯推論
* **1900**，希爾伯特提出23道最重要的數學問題--[希爾伯特的23個問題](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98)，希望做出一超級裝置，輸入問題和公理，解出任何問題，取代所有數學家；其中的第二個問題，《算術公理之相容性》對程式領域產生了重大的影響
* **1929**，[哥德爾完備性定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%AE%8C%E5%A4%87%E6%80%A7%E5%AE%9A%E7%90%86)證明ZFC&一階邏輯(+ and - only)中，**所有邏輯上有效的公式都是可以證明的**。
* **1931**，哥德爾證明並發表[哥德爾不完備定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E4%B8%8D%E5%AE%8C%E5%A4%87%E5%AE%9A%E7%90%86)的兩條定理，指出：
    1. 任何自洽的形式系統，只要蘊涵皮亞諾算術公理，就可以在其中構造在體系中不能被證明的真命題，因此通過推理演繹不能得到所有真命題（即體系是不完備的）。
    2. 任何邏輯自洽的形式系統，只要蘊涵皮亞諾算術公理，它就不能用於證明其本身的自洽性。
    ***邏輯一致，則不完備***

#### 語法推論
> [諾姆·喬姆斯基](https://zh.wikipedia.org/wiki/%E8%AF%BA%E5%A7%86%C2%B7%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA)1957年以里程碑級作品《句法結構》成為語言學界的重要人物
> [喬姆斯基譜系](https://zh.wikipedia.org/zh-tw/%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA%E8%B0%B1%E7%B3%BB) : **規則太複雜，掌握的程度又不高，語法不完全通順，無法實際運用**
> 
> ![image](https://hackmd.io/_uploads/S1t6HPpHp.png =50%x) ![285px-Chomsky-hierarchy.svg](https://hackmd.io/_uploads/rkgSPwTB6.png =40%x)


#### 機器推論
> [有限狀態機](https://zh.wikipedia.org/zh-tw/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA)
![螢幕擷取畫面 2023-12-06 115859](https://hackmd.io/_uploads/H19lG_TBT.png)

## 第十四週

### 計算理論-2
#### 邏輯推論
* **1900**，[希爾伯特的23個問題](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98)之《算術公理之相容性》對程式領域產生了重大的影響
* **1929**，[哥德爾完備性定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%AE%8C%E5%A4%87%E6%80%A7%E5%AE%9A%E7%90%86)，**所有邏輯上有效的公式都是可以證明的**。
* **1931**，哥德爾證明並發表[哥德爾不完備定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E4%B8%8D%E5%AE%8C%E5%A4%87%E5%AE%9A%E7%90%86)的兩條定理，指出***邏輯一致，則不完備***
* **1936**，邱奇把最初的λ演算系統(被證明是邏輯上不自洽)的關於計算的部分抽出獨立發表—現在這被稱為無類型[λ演算](https://zh.wikipedia.org/wiki/%CE%9B%E6%BC%94%E7%AE%97)。(當時無函數概念，用代數)
    ![image](https://hackmd.io/_uploads/ryX8X5ULa.png)
    * IF 系統 : TRUE、FALSE、AND、OR、NOT、XOR
    * 整數系統 : 加、減、乘、次方、1-10
    * Y-Combinator : 遞迴呼叫(一直叫，一直算)
    * LIST : [CONS / CAR / CDR](https://hackmd.io/@Jung217/HJ-AsTPka#%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B-2)、range、map
* **1937**，[圖靈機(Turing machine)](https://zh.wikipedia.org/zh-tw/%E5%9B%BE%E7%81%B5%E6%9C%BA)，是艾倫·圖靈提出的一種將人的計算行為抽象化的數學邏輯機，其更抽象的意義為一種計算模型，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。帶出[邱奇-圖靈論題](https://zh.wikipedia.org/wiki/%E9%82%B1%E5%A5%87-%E5%9B%BE%E7%81%B5%E8%AE%BA%E9%A2%98)
* **1956**，[有限狀態機(沒有磁帶的圖靈機)](https://zh.wikipedia.org/zh-tw/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA)，有限個狀態以及在這些狀態之間的轉移和動作等行為的數學計算模型。
* **1957**，[喬姆斯基的語法](https://github.com/ccc112a/py2cs/blob/master/06-%E8%A8%88%E7%AE%97%E7%90%86%E8%AB%96/05-%E5%96%AC%E5%A7%86%E6%96%AF%E5%9F%BA%E7%9A%84%E8%AA%9E%E6%B3%95.md)嘗試接近句法學的方式 。生成文法嘗試給出一套規則，其能正確的預測，在一個語言中，甚麼樣的詞匯組合能成為正確的句子

> [非確定型圖靈機](https://zh.wikipedia.org/wiki/%E9%9D%9E%E7%A1%AE%E5%AE%9A%E5%9E%8B%E5%9B%BE%E7%81%B5%E6%9C%BA)`可以想像成一台超級平行圖靈機，這個圖靈機會對所有可能的組合進行嘗試。當分成 n 條路時，該圖靈機可以問上帝說，哪條路有解，然後上帝會告訴你，接著你就走有解的那條路繼續試。(這種機制稱為神諭 Oracle)`

>P & NP
>* NP (Nondeterministic Polynomial time)是**非確定型圖靈機**可以在**多項式時間**內解決的問題。(NP reduce to SAT to 整數規劃)
>* P (Polynomial time)，是**確定型圖靈機**可以在**多項式時間**內解決的問題。


* **1971**，**P = NP 問題**，是庫克(Stephen Cook)提出來之後，一直沒有被解決的問題，而且很可能今後也沒有人能解決這個問題。庫克也證明了[ SAT問題 ](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem)是 NP-Complete 問題
    * [Cook-Levin理論](https://zh.wikipedia.org/zh-tw/Cook-Levin%E7%90%86%E8%AB%96)
     ![image](https://hackmd.io/_uploads/B1omh5LIp.png)
## 第十五週

### 逼近法 & 模擬法 & 轉換法
* 逼近法
    * e(微積分)
    * [史特靈公式](https://zh.wikipedia.org/zh-tw/%E5%8F%B2%E7%89%B9%E9%9D%88%E5%85%AC%E5%BC%8F) : 用來取n階乘近似值的公式(n越大，越近)
    * 內插(3D圖學)
        * 線性內插
        * B-Spline內插
    * 微分 : 程式的數值微分會出錯，高次微分最好用符號微分
    * 泰勒展開式 : 求鄰近點的值(基於某些原因無法得知多項式；e.g.逼近根號值)
        ![image](https://hackmd.io/_uploads/SyZjcpJDa.png)
    * 黎曼積分 : 用矩形的和逼進
        ![330px-Riemann](https://hackmd.io/_uploads/B1gU9TkD6.gif)
    * [單純貝氏分類器](https://zh.wikipedia.org/zh-tw/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%86%E7%B1%BB%E5%99%A8)
* 模擬法 : 模擬不一定存在的機器
    * 虛擬機
        * Docker : 翻成不同架構的指令執行
        * VMWare : 底層都一樣，OS不同
        * VirtualBox
    * 圖靈機
    * 有限狀態機
    * 電路模擬
* 轉換法
    * 傅立葉轉換
        * 一維 : 語音
        * 二維 : 影像 (去掉高頻，壓縮影像)
    * [沃爾什轉換](https://zh.wikipedia.org/zh-tw/%E6%B2%83%E7%88%BE%E4%BB%80%E8%BD%89%E6%8F%9B) : 正交編碼，在頻譜分析上作為離散傅立葉變換的替代方案(5G communication)
    * [拉普拉斯轉換](https://zh.wikipedia.org/zh-tw/%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%8F%98%E6%8D%A2) : 解微分方程式(微分>>多項式>>微分的解)
    * Z-轉換 : 離散版的拉普拉斯

## 第十六週
> 語言模型在不知道時穢亂回答，RAG就是先回去找看看再回答 ([向量資料庫](https://aws.amazon.com/tw/what-is/vector-databases/))

> 線性代數橫跨代數&幾何
### 領域-數學
* 代數
    * 複數
    * 尤拉公式
      ![image](https://hackmd.io/_uploads/By9nFbKDp.png =60%x)
    * [泛函](https://zh.wikipedia.org/zh-tw/%E6%B3%9B%E5%87%BD) : 自定義函式+ -- * / 
        * 正交
    * 矩陣
        * 行列式 : 行列式的定義和n維平行體的體積有著本質上的關聯
          ![Parallelogramme](https://hackmd.io/_uploads/rkvf2ZtwT.jpg)
        * 符號行列式
        * LU分解 : 轉成三角矩陣，可以快速算行列式
        * 特徵值、特徵向量
        * 最小平方法 : 回歸擬合；在二維平面上的點找一條擬合的線
        * [norm(範數)](https://zh.wikipedia.org/zh-tw/%E7%9F%A9%E9%99%A3%E7%AF%84%E6%95%B8)
        * [SVD(奇異值分解)](https://zh.wikipedia.org/zh-tw/%E5%A5%87%E5%BC%82%E5%80%BC%E5%88%86%E8%A7%A3)
    * 多項式
    * sympy
* 幾何
    * 向量
    * scipy
        * [ConvexHull](https://zh.wikipedia.org/zh-tw/%E5%87%B8%E5%8C%85) : 雷達，畫區域
    * graphics
        * 旋轉、平移、縮放矩陣
        * 光跡追蹤
## 第十七週
### 領域-文字
> 最好處理但沒那麼簡單
* 字串比對
    * indexOf
    * 正規表達式
    * [KMP演算法](https://zh.wikipedia.org/zh-tw/KMP%E7%AE%97%E6%B3%95) : 母字串一直前進，子字串比對
* 字串壓縮
    * 霍夫曼編碼
    * [藍波-立夫-衛曲編碼法(LZW)](https://zh.wikipedia.org/zh-tw/LZW) : 先建立一個字串編碼表，再做霍夫曼編碼
* 字串比對
    * [trie](https://zh.wikipedia.org/zh-tw/Trie) : 根據字母編的多元樹
        * [patricia](https://zh.wikipedia.org/zh-tw/%E5%9F%BA%E6%95%B0%E6%A0%91) : 加上0&1，編碼更簡潔
          ![600px-Patricia_trie.svg](https://hackmd.io/_uploads/SJggJrGO6.png =50%x)
* 全文檢索
    * [倒排索引](https://zh.wikipedia.org/zh-tw/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95) : 建索引，紀錄出現的檔案
    * [PageRank](https://zh.wikipedia.org/zh-tw/PageRank) : 算出網頁的重要性(連結數要正規化(遞迴迭代函數)，防灌水)
### 領域-影像
* 影像壓縮
    * [離散餘弦轉換](https://zh.wikipedia.org/zh-tw/%E7%A6%BB%E6%95%A3%E4%BD%99%E5%BC%A6%E5%8F%98%E6%8D%A2) : 轉頻譜
    * 傅立葉轉換
### 領域-聲音
* 聲音壓縮
    * 一維傅立葉轉換
### 領域-圖形理論
* [networkx](https://networkx.org/)
* [Dijkstra's algorithm](https://zh.wikipedia.org/zh-tw/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95)
* [Floyd-Warshall algorithm](https://zh.wikipedia.org/zh-tw/Floyd-Warshall%E7%AE%97%E6%B3%95)
* [Maximum flow problem](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E5%A4%A7%E6%B5%81%E9%97%AE%E9%A2%98)
    * [Ford–Fulkerson method](https://zh.wikipedia.org/zh-tw/%E7%A6%8F%E7%89%B9-%E5%AF%8C%E5%B0%94%E5%85%8B%E6%A3%AE%E7%AE%97%E6%B3%95) 
### 領域-密碼學
* [凱薩加密](https://zh.wikipedia.org/zh-tw/%E5%87%B1%E6%92%92%E5%AF%86%E7%A2%BC)(位移加密)
![480px-Caesar3.svg](https://hackmd.io/_uploads/Sy6horGOp.png =50%x)
* [維吉尼亞加密](https://zh.wikipedia.org/zh-tw/%E7%BB%B4%E5%90%89%E5%B0%BC%E4%BA%9A%E5%AF%86%E7%A0%81)
    ![image](https://hackmd.io/_uploads/B1mBTHMuT.png =70%x)
    ![image](https://hackmd.io/_uploads/SyeNarzua.png =30%x)
* [互斥或密碼](https://zh.wikipedia.org/zh-tw/%E5%BC%82%E6%88%96%E5%AF%86%E7%A0%81)
    ![image](https://hackmd.io/_uploads/S192pBG_T.png =50%x)
* [進階加密標準(AES)](https://zh.wikipedia.org/zh-tw/%E9%AB%98%E7%BA%A7%E5%8A%A0%E5%AF%86%E6%A0%87%E5%87%86)
    ![420px-AES-SubBytes.svg](https://hackmd.io/_uploads/S1xfILf_T.png =50%x)
* [Diffie–Hellman key exchange](https://zh.wikipedia.org/zh-tw/%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B) : 只有交換金鑰的概念，啟發RSA
* 因式分解
    * 輾轉相除
    * 2除到根號n 
* 公因數(gcd)
    * 歐基里德算法
* [Galois field](https://zh.wikipedia.org/zh-tw/%E6%9C%89%E9%99%90%E5%9F%9F) : mod一個質數，反元素就存在，並形成有限體
* [RSA](https://zh.wikipedia.org/zh-tw/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95)
    * 找大質數；產生大直數相當困難>>>費馬小定理
    ![image](https://hackmd.io/_uploads/SyHUi8GO6.png)
    * 找 mod n 乘法反元素 : 擴展歐基里德算法；相較一般，多了一些數字(?
    * 產生公私鑰的Key pair(eN、dN)