解決問題所依循的程序

以Dynamic Connectivity問題為例

問題的描述

輸入為一連串由一對對正整數所組成的序列，例如(2, 10), (0, 3), (4, 5)…，每個正整數代表的是某種類型的物件（可以代表社交網絡中的一個人、網絡中的一個節點等等），而一對正整數 (3, 10) 的意思是，將 3 與 10 「連在一起。

實際應用

• 網絡分析
• 程式語言中變數名稱的相等性
• 數學上的集合

開始製定Union-Find API

1
2
3
4
5
6
7
8
9
10
11

class UF:
    def __init__(self, n):
        self.id = [i for i in range(0, n)]
        
    def connected(self, a , b):
    
    # 找出位置  的元素
    def find(self, p):
    
    # 將 p 和 q 連在一起
    def union(self, p, q):

第一種實作: Quick-Find

留言與分享

Random access Machine

Pointer Machine

Python machine

更現代的Python結合以上兩種模型。

基本情況

List

Python中實作List的方式使用RAM模型，透過a_list[i]取得list中某一索引的元素，所花的時間為常數時間O(1)。

如果以linked list的方式來實作，那麼取出索引i的元素所花的時間即成為線性時間O(n)。

Object

如果一物件有適當數量的元素，那麼取出該物件屬性的執行時間也是常數時間O(1)。

幾個例子

list.append

使用 table doubling 方法（在之後的第九課將提到），使執行時間達到常數時間O(n)。

new_list = list1 + list2

上面的程式碼在底層其實是執行下方的程式碼。

1
2
3
4
5

new_list = []
for x in list1:
    new_list.append(x)
for y in list2:
    new_list.append(y)

因此可利用append()方法的執行時間來推導將兩個list相連在一起的執行時間: O(|list1| + |list2|)，即正比於兩個list的元素數量總和。

elm in a_list

線性時間O(n)，從第一個元素依序檢查到最後一個。

len(a_list)

常數時間O(1)，因為Python在底層已經先計算好並儲存每個list的長度。所以呼叫len(a_list)只是去叫出那個被儲存的值。

list.sort()

dict

以hash table實作，因此以dict[key]叫出該對應value的執行時間為常數時間O(n)。

Document distance Problem

目標

有兩份文件，想測量這兩份文件的距離，即這兩份文件的共通性。

應用

• Google index page
• Mirror of Wiki
• 檢查兩份期末報告是否互相抄襲

定義

• 文件:由words組成
• word: 為字元(a-z, A-Z, 0-9)組成的字串

概念

可以把兩份文件的共通性以兩份文件所包含字詞的共通性來思考。

主要步驟

1. 將文件分割為words
2. 算出每個word的出現頻率
3. 算兩個文件的word陣列的內積（即角度）

課程連結

MIT 6.006 Introduction to ALgorithms, Fall 2011

留言與分享

使用data宣告全新的type

與type declaration只是宣告一個「關於既存類型的同義詞」不同，使用data關鍵字可以宣告全新的類型。
在Prelude中，Bool類型即是以下列方式宣告的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

data Bool = True | False
```  
- 在``=``左邊的稱為 type constructor (上例中的``Bool``)
- 在``=``右邊的稱為 data constructor 或 value constructor (上例中的``True`` 或 ``False``)


## 使用 type parameter 的時機

> We usually use type parameters when the type that's contained inside the data type's various value constructors isn't really that important for the type to work  

f

> 名詞定義：
> concrete types, fully applied type: 像是 ``Maybe Int``, ``Maybe Char``
> 至於``Maybe``本身只是一個**type constructor**，並非具體的type。任何值都必須具有concrete type。  
> 比較 ``Maybe`` 和 ``Maybe Int``:``Maybe``是一個type constructor，``Maybe Int``則是一個 concrete type

## 好好區分 type constructor 和 data constructor
type constructor只能出現在下面用``...``表示的幾個地方:

-  ``data ... =`` 
-  ``type ... =`` 
-  ``::...``
-  ``instance Eq ... where``

# 使用``type``為現存的type宣告新的別名

稱為 type synonym。用來給一個既有type提供一個別名。什麼時候需要這樣大費周章為已經存在的type提供新的名稱？

> We introduce type synonyms either to describe what some existing type represents in our functions (and thus our type declarations become better documentation) or when something has a long-ish type that's repeated a lot (like ``[(String,String)]``) but represents something more specific in the context of our functions.
> [LYAH](http://learnyouahaskell.com/making-our-own-types-and-typeclasses)

``Char``是一個Haskell本身就定義好的type，如果要以``Char``為基礎，建立新的type，那麼就要使用``type``:

type String = [Char]

1
2

``Int``也是一個Haskell本身就有的、用以表達整數的type，如果想建立一個正整數座標的Point type，並包在tuple中，可以使用：

type Point = (Int, Int)

1
2
3
4

當然，定義好新的type之後，新的type就可以用在別的type宣告中。

也許有一系列的function都與「將一個Point轉換到另一個Point」有關，因此可以為這群函數宣告一個新的type：

type Transformation = Point -> Point

1
2

## Type synonym也可以具有type parameters

type Pair a = (a, a)
`
一個Pair可以是Pair Int (Int, Int)，可能是(Char, Char)

參考資料

• Constructor on Haskell Wiki

留言與分享

commit

分支branch

branch本質上僅僅是個指向 commit 物件的可變指標。Git 會使用 master 作為分支的預設名字。在若干次提交後，你其實已經有了一個指向最後一次提交物件的 master 分支，它在每次提交的時候都會自動向前移動。

分支其實就是從某個commit物件往回看的歷史。

建立新分支

1

$ git branch <new_branch_name>

這個指令僅僅建立了新的分支，而不會自動將所在位址切換到這個新分支上。要切換到新分支上，需透過下方的git checkout指令：

1

$ git checkout <branch_name>

執行 git checkout 就是把HEAD指標指到新的分支上。

捷徑：建立新分支，同時切換到該分支

1

$ git checkout -b <new_branch_name>

合併分支

使用merge

使用rebase

指向目前所在分支的HEAD指標

指向目前所checkout的commit。
每次執行git checkout指令，都會連帶改動HEAD所指向的reference。

例如在執行下面代碼後：

1

$ git checkout <a_commit>

HEAD就會同時指向該a_commit。

HEAD通常指向一個分支的名稱

留言與分享

-a 詞幹名詞

-a 詞幹名詞包含了陽性與中性名詞，

陽性

中性

除了 Nom, Voc, Acc 這三格之外，其他的變格皆與a-詞幹陽性名詞相同。

-ā 詞幹陰性名詞

除了 Nom, Voc, Acc 這三格之外，其他的變格皆與a-詞幹陽性名詞相同。

參考資料

• The Cambridge Introduction To Sanskrit (2016) 一書中作者 A.M.Ruppel 所整理精美文法表格
  pdf檔連結

留言與分享

初衷

生活中有大量的訊息，我們往往希望能從這些雜亂的訊息中解讀出有用的資訊甚至是預測未來的趨勢。舉例來說，政府統計全台灣各縣市的人均收入，也許按照年齡層、性別、職業別區份，可以讓人民更了解台灣的經濟現況以及不同群體之間的差異性。

名詞解釋

• 母體 Population: 宇集
• 參數 Parameter: 關於母體的描述統計量，例如母體平均數、母體標準差，或者關於母體的Data model的參數
• 樣本 Sample: 母體的子集合
• 統計值 Statistics: 關於樣本的描述統計量
• Data Model: 用以產生新Data的模型，通常是未知，因此需要透過推論來得出。
• Likelihood: 用來推論Data model時會有各種假說，透過計算各個假說的Likelihood，來找出符合現有證據最可能為真的假說

描述統計學

對於蒐集到的一組資料，要如何描述這組資料的特徵？有哪些特徵可以識別一組資料？

平均數

中數

眾數

range

Q3 - Q1

變異數

標準差

推論統計學

從蒐集到的樣本，我們希望可以推測出母體的狀態

Maximum Likelihood Estimation

Maximum likelihood estimation is a method that determines values for the parameters of a model. The parameter values are found such that they maximise the likelihood that the process described by the model produced the data that were actually observed.

Probability concepts explained: Maximum likelihood estimation

留言與分享