演算法筆記

範例：Peak finding

Unit2

1. RAM(Random access machine): Random access memory, modeled by big array...
2. Pointer machine

Document distance

1. Algorithmic thinking, peak finding

讀書筆記

範圍1, 3, D.1

Chapter1 The role of algorithms in computing

1. 何為演算法？
2. 為什麼要研讀這門學問？
3. 演算法跟其他電腦運算相關技術的關係？ ### 1.1

• 演算法(algorithm)為 well-defined computational procedure, 有input, output 例如一個排序sorting的演算法，有一串數字輸入，跟數字輸出。可以用英文，程式，硬體設計，任何有詳述計算流程的speciation來呈現。
• instance, 一個需要算出結果的實例
• sorting因為被其他程式當成模組來用，在計算機科學中是個基本功。
• correct, 演算法如果能停下，並給出正確答案，就是correct。（能給出正確答案卻不會停是哪招啊？） 當然也有一些演算法是有一定“機率”成功，善加運用也可以得到正確結果，見31章。 ### Exercise 先跳過讀第三章，覺得廢話太多＝ ＝

快速複習矩陣跟矩陣運算方法

D.1 Matrices and matrix operations

$一個m乘n的矩陣A{m,n} = \begin{bmatrix} a{1,1} & a{1,2} & \cdots & a{1,n} \ a{2,1} & a{2,2} & \cdots & a{2,n} \ \vdots & \vdots & \ddots & \vdots \ a{m,1} & a{m,2} & \cdots & a{m,n}

\end{bmatrix}

\begin{bmatrix} 1 & 2 & \cdots \\ 3 & 4 & \cdots \\ \vdots & \vdots & \ddots \end{bmatrix} $

其中$a_{1,1}=1, a_{1,2}=2$，以此類推。

• Transpose 矩陣$A^T$則是$\forall a_{i,j} \in A都mapping到A^{T}裡的a_{j,i}$
• Vector 則是one-dimentional的矩陣, column vector是$n\times 1$, row vector則是$1\times n$, 可用transpose作轉換。
• unit vector $e_i是i_{th}為1，其他都是0的vector$
• zero matrix 是元素全為0的矩陣 ## Square matrix 方陣

1. Diagonal matrix $\forall i \neq j, a_{i,j}=0$
2. Identity matrix is a diagonal matrix and $\forall a_{i,j}=1$
3. Tridigonal matrix, $T \text{ is}\forall |i-j|>1, a_{i,j}=0 $
4. upper-triangle matrix $U \text{ is} \forall i>j, a_{i,j}=0 $
5. lower-triangle matrix $L \text{ is} \forall i<j, a_{i,j}=0 $
6. permutation matrix $P$, there is exact one 1 in each column or row, and 0 elsewhere
7. symmetric matrix $A=A^T$ ## BASIC Matrix operations 基本矩陣運算
8. add
9. scalar multiple
10. compatible is matrix $A,B$ where $A=(a_{i,j})\text{ is }m*n\text{ matrix }$, $B=(b_{i,j})\text{ is }n*p\text{ matrix }$
11. multiplication $C = AB$ where $C_{i,j}=\displaystyle\sum_{k=1}^{n} a_{i,k}*b_{k,j}$, 計算n方陣需要左列的n次乘法，n－1次加法再乘元素數量＝$n^2$所以各是$n^3, n^2(n-1)$是$\Theta (n^3)$ ## 運算性質
12. compatiable matrix的乘法 distrubutes or addirion: $A(B+C) = AB+AC$
13. for n>1, 乘法沒有commutative， ex: $ A = \bigl(\begin{smallmatrix}0&1 \\ 0&0\end{smallmatrix} \bigr), B = \bigl(\begin{smallmatrix}0&0 \\ 1&0\end{smallmatrix} \bigr), AB\neq BA$

Exercises

• D.1-1 Show that if A and B are symmetric $n\times n$ matrices, then so are A+B and A-B.

if $A$ and $B$ are symmetric, then $a_{i,j} = a_{j,i} ,for \forall i,j,0<=i<n, 0<=j<n$ $C = A+B, c_{i,j} = a_{i,j}+b_{i,j}\text{, since A,B are symmetric,} a_{i,j} = a_{j,i} ,for \forall i,j,0<=i<n, 0<=j<n $

thus, $c_{i,j} = a_{j,i}+b_{j,i}= c_{j,i}, C$ is symmetric

• D.1-2 Prove that $(AB)^T= B^TA^T$ and that $A^TA$ is always a symmetric matrix.
• D.1-3 Prove that the product of two lower-triangular matrices is lower-triangular.
• D.1-4 Prove that $P$ is a $n\times n$permutation matrix and $A$ is a $n\times n$matrix,then the matrix product $PA$ is $A$ with its rows permuted, and the matrix product $AP$ is $A$ with its columns permuted. Prove that the product of two permutation matrices is a permutation matrix.

2. Models of computation, Python cost model, document distance

Homework

參考資料

1. 課程網頁
2. Python Cost Model
3. Latex參考資料
4. solutions to part C
5. 另外一門進階課程

Chapter 3 Growth of Functions

Asymptotic Notation 漸進符號

這裡我們要定義一些以後常用的工具，方便我們釐清演算法效能。

• $\Theta$ -notation: the set of functions

  $\Theta (g(n)) = \{f(n): \text{ there exist positive constants } c_1, c_2\text{, and }n_0\text{ s.t.} 0\leq c_1g(n)\leq f(n) \leq c_2g(n) \text{for all} n \geq n_0\}$

$\Omega = $

$\omega = $ $O = $

$o = $

Theorem 3.1

任何兩個function f, g, $f = \Theta(g) \iff f = O(g) and f =\Omega (g)$

課本中有拿實數的比較當例子來跟漸進符號做類比。值得一提的是實數有Trichotomy（一定是$=,\lt,\gt$三種之一的性質）但是有一些像是$n^{1+sin(n)}$之類在0跟2之間跳舞的函數會讓Trichotomy破功。（讓我想起$sin\frac{1}{x}$這個調皮的小鬼） **

進度 有48個lecture，每個1～2小時以上計算，需要100小時學習時數。