[Introduction To Algorithms] 第四堂: Divide-and-Conquer(3)

這堂課講 Divide and Conquer 的第二種方法，和第三中方法(講一部分)。 The tree-recursion method and The master method。


The tree-recursion method 基本上就是先畫圖把時間估算一下，然後再用 substitution 證明。

第三種方法在大部分的 Divide and Conquer 都可以用，以前對於 master 的解釋有點模糊，現在知道是 leaf 層和其他層的總和誰是老大的問題 (master)


接下來就是有三種情況討論

• 小於
• 等於
• 大於

老師把觀念講出來，詳細證明自己要看教科書。




降~

[Head First JavaScript] Chap1: 互動性網站

這一章利用簡單的動性 iRock 程式介紹 JavaScript，當滑鼠移到石頭後，會出現一彈跳視窗叫你輸入名字。


跟一般 C/C++ 程式不同的是，JavaScript 是以直譯形式跑在瀏覽器上，因此要嵌入在 HTML 的語法裡。




這時候理解 HTML、CSS、JavaScript 三者的分工關西就很重要。
HTML: 程式的骨架。
CSS: 程式的外觀。
JavaScript: 讓程式有互動性。




程式很小，我就把程式碼都貼上來。

• JavaScript 應該要嵌入在 HTML 的哪裡。
• onload 直接寫在 body 裡面... (JavaScript 的另外一種放法??) 這段我就不適很了解，是CSS還是JavaScript的功能。

[Introduction To Algorithms] 第四堂: Divide-and-Conquer(2)

第一堂課去台北參加 VS2010 C++ 開發日，聽錄音檔後再補，今天講的主要介紹，估算 asymptotic notation 的方法 -- The substitution method 。


這方法有兩個步驟，
1. Guess the solution  (猜)
2. Use induction to find constants and show the solution works (建構式歸納法)

觀念上和數學歸納法一樣，只是因為是 asymptotic notation 所以像是 boundary case 就不是那麼重要(immaterial) (時間函數是單調遞增)。
base case 也不用證明，只要
對 ο: c 挑足夠大
對 Ω: c 挑足夠小
這樣就可以蓋過 base case

在推導的過程中，若是遇到天花板、地板的證明就很惱人，要多一些調整的式子。

Big-O 的證明還好，但是Ω 的證明就很麻煩(tedious)了。


所以老師補充了 smooth 的 Lemma 最後推導出只要是 poly 和 對數函數，都可以省略天花板和地板
但是，指數函數就不能夠省略。

證明過程請參考 p.21 ~ p.27 。
p.26 頁說明如何估算指數函數有天花板地板的 T(n)

注意 smooth 的條件
1. 單調遞增
2. f(cn) = O(n)
因為是單調遞增，且 smooth，所以  b^k 和 b^k+1 看起來是 smooth，不會像上一張圖有跳 tone 的感覺。

這張投影片說明如果是用 asymptotic notation 表示 recurrence ，有何差異，結論是沒甚麼差， θ(n)=cn 這時的 c 是已知，推導下來只要 d 夠大就沒問題了。下張投影片是簡潔的寫法，不過要寫的精確也是要沒問題的啦!

[Distributed Algorithms] 第二堂: Mutual exclusion (2)

今天上 chap 10，開始講 modelling 的觀念，進入一堆證明，不過還是屬於 mutual exclusion 的範疇內，沒想到有這麼多種的 mutual exclusion。


花了最多時間講 Dijkstra’s Mutual Exclusion Algorithm

屬要證明三個部分:

• well-formedness   
• mutual exclusion
• progress

well-formedness 老師說不用甚麼證明，但我對於這個概念還是很模糊，mutual exclusion 用上禮拜的反證法概念。

老師還有特別證明，像是任兩個 process 甚麼情況有可能同時到達 flag(i):= 2 這行，但同一情況不可能一直發生。

對於 Mutual Exclusion 三位大師都有證明:

Dijkstra  : 有 starvation 發生

Knuth     :  (忘記了)

E-M       : 最好

上面的演算法，沒有 atomic，以 

  while turn != i do

     if flag(turn)=0 then turn:=i 

為例這兩個 turn 支間可以相隔很久，而且第二個 turn 沒有多讀的必要，這是因為 psuedo code 太高階了，課本範例有介紹用 pc counter 來達到 atomic 的寫法。

eq.  (此 action 利用 precondition 當 pc counter 等於 set-flag-1 時就執行)

    set-flag-1

    Precondition:

       pc=set-flag-1

    Effect:

接下來證明複雜的 Progress...

課本用了很多 lemma 來說明，比較容易的想法是，CS 是空的時，很多人想進去，那最後 turn 一定會進入穩定狀態，而那個拿到 turn 的 process 也就勢如破竹的進入 CS 了。

課本上還用了比較學理的證明，但是那個太邏輯了，老師說沒甚麼必要(跳過)... XD

•  Lockout-freedom : 不會餓死 (something good will eventually happened)
• Number of bypass a: 其他人最多執行 a 次 (something bad can not happened)

老師說這兩種狀況要注意，證明的方法很不一樣 

接下來介紹 Peterson2P 和 PertersonNP 

2P 比較好懂，NP 的證明就比較難，老師舉了想像 N-1 階樓梯，有 N 個老鼠想進去，每個階梯會黏住一個老鼠，所以最後會只有一隻能進去。

這些擰人化的想法只是幫主想像，學理上的證明還是要學院派一點 -= =

最後提到 BurnsMe Algorithm

這個觀念就用長幼有序的方式去想，

尊敬一次後，舉手，在尊敬一次，等後輩執行完後就不客氣了。

舒服!!

    

Virtualbox Ubuntu Linux 更新後共享資料夾不能用的問題

之前也遇過這樣的問題，網路上找了很久，有找到一篇文章要用 modprob 之類的指令，
後來發現只要重新安裝 guest additions 就可以了，也花了一些時間查詢怎麼重新安裝 guest additions
後來用大絕招，在 win 7 virtualbox 的安裝目錄下把 VBoxGuestAdditions.iso 改名然後再從網路更新，就完畢了!!


舒服~ 

[Distributed Algorithms] 第二堂: Mutual exclusion

今天講了三個主題:
 Asynchronous shared memory model,
 Mutual exclusion problem definition,
 Dijkstra's mutual exclusion algorithm　
老師花了很長的時間再講 OS 的 Mutual Exclusion，
old-hw1.pdf 是 mutual exclusion 的 algorithm，
http://en.wikipedia.org/wiki/Eisenberg_McGuire_algorithm 不過 wiki 的這個版本就講得蠻清楚的了。


old-hw1_ans.pdf 裡面是解答。


證明要證明三件事:

• Safety
• Progress (Liveness)
• bound waiting of (n-1) turn

這演算法基本上是講你要進入 CS ，第一要聲明想進去，第二要拿到權杖 (turn)...

好像以前補 OS 的時候有講到這個演算法 (遙遠的回憶啊~~)

我自己的問題是 turn := i 這行需不需要 atomic ...

這次還不習慣老師講解的方式，筆記做的很糟糕~~

我抓的 pdf 和課本好像也不太對 = =

XD 再加油

[Introduction To Algorithms] 第二堂: Growth of Functions(3)

asymptotic notation 的運算也就是集合的運算。


老師補充了 

• Rule of Sum
• Rule of Product

當作範例說明。注意這兩個 theorem 在程式中的應用。(時間和 vs 巢狀迴圈)

這裡要注意一下，為什麼第一個式子成立，但第二個式子卻不成立。答:係數的問題。第一個式子 c 可以從 θ 拿過來。但第二個式子因為是加法，最高項的係數固定是 1 。 所以會有問題。

接下來老師花了一些時間證明 Rule of sum
這裡用三個單向來證明，舉例來說要證明 A=B=C ，用三個單向就是

• A ≦ B
• B ≦ C
• C ≦ A

這樣就證明出 A=B=C 了。 三個單向證明都很簡單參考 p.26~p.28。

值得注意的是， for sufficient large n 這裡有三個 n₀ 要 n 要大於他們。但為了方便起見，用足夠大寫比較簡潔。

下面是一個 Rule of Sum 亂用的例子。
記住: 要用 asymptotically nonnegative function，而 max 的第二個 function 不管你 n 多大都無法是正數。

這張投影片才是正確的示範，不要亂用證明。

這個證明很有用，也很常用到，但注意不要亂用(等下會有投影片說明)，Cormen 教科書上直接用，老師補充 Rule of Sum (什麼是θ相加)對於這個定理的證明推倒之理解比較有幫助。

這張也是講亂用的例子，這裡錯的原因是因為，這錯誤的式子用到多個 n₀ 個與 c₀ ，記住要合併的話必須要找出共用的 n₀ 與 c。
p.32~p33 有舉例說明這個問題，可以參考。

接下來兩張投影片的 Theorem 比較少用，但是還是要注意一下，這張講的是 -1 在次方向時 ο與 Ω 要互換。這跟分數的比較大小很像。

這裡要注意，式子左邊代表的不是集合的集合。
而是要再 Union 起來。跟一般的不太依樣，要注意。

• 3.2 Standard notations and common functions

p.38 ~ p.43 介紹了常用的 function 指數、對數、階層等等。微積分的基礎就很重要 (我忘得差不多了 = =) 概念性的像是 polynomials 代表的是上限為 poly 而不一定是指多項式函式。 Logarithms 再怎麼強都沒有poly 快。Logarithms的底沒有這麼重要 (用換底公式弄完後只是一個係數)。


     階層的話要注意 Stirling's formula，講義舉了三種方式證明，Summation 的證明方式很重要!!
     Harmonic number 也蠻常用的。


有用到再複習吧!! 我的微積分阿~~