Final 日期

Pervasive Computing, 1/2放假, 所以應該是 1/9

1. Apriori

2. Prefix-Span

3. Decision Tree

4. Session06_SpatialData.pdf (pages 104~130)

5. Session07_MobileSpatial.pdf (all)

Formal Language, 1/12
全範圍

Algorithm, 1/11
全範圍

Algorithm hw#14

Prob. 26-1
Ex. 35.1-4

2016/12/15 Formal Language

• 有一個Assignment 2 , 老師說上課會講解, 不知道要不要交? 目前沒說要交
• 複習ch11
• 上ch12

-----------------------------------------------

• The Chomsky Hierarchy [ pdf ]
• Assignment 2 [ pdf ]
• Chap 12  Limits of Algorithmic Computation
• Some problems that cannot be solved by TMs [ pdf ]

-----------------------------------------------

以下是自己錄的重點提示

雖說是重點提示, 但其實已經涵蓋了今天3小時的上課內容
其實幾分鐘就可以講完的東西....
有時真是由衷希望老師可以好好備一下課....@@

ch11.4

ch12

Algorithm hw#13

Prob. 25-1
Transitive Closure: 參考 http://acm.nudt.edu.cn/~twcourse/TransitiveClosure.html
簡言之就是走得到的所有連結, 所構成的一張圖

a. 當加進一條邊時,要怎樣更新Transitive Closure的boolean matrix, 在O(V^2)時間內
b. 舉例說明當加入一條邊到一張圖裡時, 不管用什麼演算法, update Transitive Closure的時間下限是V^2
c. 針對更新Transitive Closure給一個有效的演算法, 對一系列的n個insertion來說, 證明時間可以維持在O(V^3)

Prob. 31-1
大部分的電腦實施減法操作來驗證一個二進位整數是奇數或偶數, 且比"算餘數"的方法還快了一倍(時間減半)
此問題牽涉到binary gcd algorithm, 避免了在Euclid’s algorithm裡的餘數計算
a. 證明當a,b都是偶數時, (a,b)的gcd是(a/2,b/2) gcd的兩倍
b. 證明當a是奇數,b是偶數時, (a,b)的gcd是(a,b/2) 的gcd
c. 證明當a,b都是奇數時, (a,b)的gcd是((a-b)/2,b) 的gcd
d. 設計一個有效的binary gcd algorithm, 滿足a>=b, O(lg a)

2016/12/14 Meeting

11/30
串媒體(Transmedia)時代的遊戲學習

• Pro-consumer
• Convergence(匯流)
• 串媒體巡航: 主題明確,動機強烈,線索清楚 ->學習效果好
• 讓學生做自己感興趣的主題, 就可以主動學習
• 數位時代: muititasking

12/14  

• AppInventor: 視覺化程式設計工具
• Computational thinking 運算思維  歐巴馬
• Digital literacy
• 
  

2016/12/14 Algorithm (Flow&Cut)

今天續上ch26

內容參考:
http://www.csie.ntnu.edu.tw/~u91029/Flow.html
http://www.csie.ntnu.edu.tw/~u91029/Cut.html

發了期末考考古題, 該找個時間來做做看

2016/12/13 TOEFL

1.      http://toefl.kmf.com/question/9a4dc1205a2706e606ad3c84f19c52ff/c72y1k.html

2.      http://toefl.kmf.com/question/ce08636670cf49a83fbf0c441ff70101/652y2k.html

3.      http://toefl.kmf.com/question/1a9ea9dddb2a2c913ac674d09f71bdaf/6b2y3k.html

2016/12/12 Pervasive Computing

同學報告

2016/12/11 EngNovels

有感於練托福的時候一直覺得沒什麼進步, 

最近又把Gone with the wind的英文小說拿出來看

裡面有些段落寫得非常棒, 完全讓我感受到英文構句之美

很想把那些段落拿出來當作材料, 好好拆解練習一下

開始EngNovels這一系列, (不定期更新)

基本上是把喜歡的段落念過一次然後嘗試中翻英

我英文並沒有太好, 但就只是練習~

- - - 

Gone with the wind

Ch1

https://drive.google.com/open?id=0B57k_NHxboqhMGN5azJlNGNuQzA

這一段是在形容女主角郝思嘉的長相, 用了非常生動的文學修辭

看完這段很有回到中學寫作課的fu

Delicate   KK[ˋdɛləkət] 脆的，易碎的；嬌貴的

Aristocrat  KK[æˋrɪstə͵kræt] 貴族

Descent   KK[dɪˋsɛnt]  世系，血統[U]

florid /fl'ɔrəd/  (a.)華麗的,紅潤的

Irish   KK[ˋaɪrɪʃ]  愛爾蘭人

Chin  KK[tʃɪn] 頦，下巴

Jaw   KK[dʒɔ]  下頜，下巴[C]

chin 通常是指最下方的那一小個特定區塊  而 jaw  大多是指兩側及整個區塊

hazel   KK[ˋhez!]  n.名詞 2. 淡褐色（尤指眼睛的顏色）[U]

bristly   1. 有鬃毛（如剛毛）的2. 林立的

starred  vt.及物動詞  用星形物裝飾用星號標出

tilted IPA[ˈtɪltɪd] 傾斜的

thick KK[θɪk] 

slanted KK[ˋslæntɪd] 1. 有傾向的，有偏向的

startling KK[ˋstɑrt!ɪŋ]  1. 令人吃驚的

oblique  KK[əbˋlik] 斜的；傾斜的[Z]

magnolia KK[mægˋnolɪə] 1. 【植】木蘭；木蘭花[C]

women KK[ˋwɪmɪn]

bonnet KK[ˋbɑnɪt] n.[C] 可數名詞 （有帶子的）女帽，童帽

veil KK[vel]  面紗，面罩[C]

mitten n.[C] 可數名詞1. 連指手套

----

這一段是郝思嘉向衛希禮告白的經典橋段
(然而衛希禮即將要娶她的表妹了)
郝思嘉是個富有生命活力.驕傲.個性鮮明的女性,
她喜歡衛希禮, 也以為衛希禮一定同樣喜歡她(畢竟她這麼受歡迎)
衛希禮是個不切實際.充滿詩歌與幻夢的理想派
但她沒有任何靈性與慧根可以了解衛希禮的想法
但她不在乎----她只想要得到她要的, 像個任性的小孩
衛希禮能夠欣賞郝思嘉那與他截然不同的個性
但他也知道, 郝思嘉不是他想要共度一生的對象,
假如他們真的結婚, 雙方都不會開心的

2016/12/9 Machine Learning

7.1.5 Computational Learning
7.2 Relevance Vector Machine(RVM)
參考:

•  http://vbie.eic.nctu.edu.tw/technical.php?index=41
• http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/RVM.pdf

2016/12/9 Algorithm (Floyd-Warshall)

Ch25. All-Pairs Shortest Paths 結束
參考: http://www.csie.ntnu.edu.tw/~u91029/Path2.html

另從11:10開始有一堂助教講解 midterm考題

---
以下改寫自wikipedia:

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖中兩結點之間的最短路徑。算法具體的形式包括：(前三個是Single Source(ch24), 最後一個是All Pairs(ch25))

• 確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。適合使用Dijkstra算法。
• 確定終點的最短路徑問題 - 該問題等同於把所有路徑方向反轉的確定起點的問題。
• 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
• 全局(All Pairs)最短路徑問題 - 求圖中所有的最短路徑。適合使用Floyd-Warshall算法。

最常用的演算法有：

• Dijkstra算法  (Ch24.3)
• A*算法
• Bellman-Ford算法  (Ch24.1)
• SPFA算法（Bellman-Ford算法的改進版本）
• Floyd-Warshall算法  (Ch25.2)  Time: O(n^3) Space:O(n^2)

---
以下改寫自 http://www.csie.ntnu.edu.tw/~u91029/Path2.html和wikipedia:

Floyd-Warshall是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權（但不可存在負權迴路)的最短路徑問題。

2016/12/11 TOEFL

4. http://toefl.kmf.com/question/kaomanfen/b12xyk.html

5. http://toefl.kmf.com/question/ee656c94b90a92cfde6d0fbdd9f7abaa/ac2xzk.html

6. http://toefl.kmf.com/question/da9bd8ff9b5a6c0850bcca95bf6521c4/382y0k.html

2016/12/8 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

• Chap 11 A Hierarchy of Formal Languages and Automata
• Recursive and Recursively Enumerable Languages [ pdf ]
• Unrestricted Grammars [ pdf ]

Algorithm hw#12

複習一下: 最小生成樹 (MST)

唯一性
最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。
如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。
proof:

1. 假設有兩個MST A,B, 有一條edge屬於A而不屬於B, 令為ek, 
2. (ek聯集B)必會形成一個cycle C, 此環C中, 任意取走一條邊, 仍然兩兩連通
3. C中必存在一個邊em,權重大於ek, 
4. 表示B如果用ek取代em, 會形成一個更小的生成樹, 但這跟一開始的assumption相矛盾

環定理cycle property

對於連通圖中的任意一個環 C：如果  C中有邊  e的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊

hw1	hw2	hw3	hw4	hw5	hw6
70	100	100	100	85	100

hw7	hw8	hw9	hw10	hw11	hw12
95*0.7 =67	100	100	80	87

2016/12/7 Algorithm (Bellman-Ford & Dijkstra's Algorithm)

Ch24.3 Bellman–Ford algorithm
參考: 
https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95

它的原理是對圖進行V-1次鬆弛操作，得到所有可能的最短路徑。其優於Dijkstra's Algorithm的方面是邊的權值可以為負數、實作簡單，缺點是時間複雜度過高，高達${\displaystyle O(VE)}$。

以鬆弛操作為基礎，估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。
在兩個演算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。 

然而，Dijkstra's演算法以Greedy策略選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而Bellman–Ford 演算法簡單地對所有邊進行鬆弛操作，共|V | − 1次，其中 |V |是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得Bellman–Ford 演算法比Dijkstra's演算法適用於更多種類的輸入。

Ch24.3 Dijkstra's Algorithm
參考: 

• http://www.csie.ntnu.edu.tw/~u91029/Path.html#4
• https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95

已知起始點, 由起始點慢慢長出最小生成樹
這個演算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。
對於不含負權的有向圖，這是目前已知的最快的單源最短路徑演算法。

演算法維護兩個頂點集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的頂點 v ，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，演算法對 u 的每條外接邊 (u, v) 進行拓展。

2016/12/6 TOEFL

聊了很多，都沒練到題目啊啊啊。

聊完得到一個結論:

「菩提本無樹，明鏡亦非台，本來無一物，何處惹塵埃。」

所有的煩惱都是自找的。

我們不需要菩提樹，去證明菩提的存在。
也不需要明鏡台，當然更不需要滿滿的大平台。
因為明鏡就在我們的心中。

「空」的境界，物我兩忘。

放下我執。

張懸的歌詞裡有一句:  「其實你擔心是你自己」
生命自有它的去處，其實真正令我們放不下的，
都不是別人，而是我們自己的執念。

2016/12/4 TOEFL

TOEFL TPO 02  Q6

1.     Narrow: Coins and bills

2.     Board: Make purchases

TPO-22

http://toefl.kmf.com/speaking/tpo

1.

http://toefl.kmf.com/question/7298b1da52761b14f27781f9bb372664/3d2xvk.html

2.

http://toefl.kmf.com/question/3437b97f0b4bf578146af3d061ac3af4/0d2xwk.html

3.

http://toefl.kmf.com/question/dd8ece7962e71a1832f4ab875746745b/8c2xxk.html

反省

我覺得在學校念書， 其實沒有什麼太花俏的技巧，就是能夠靜下心來， 不問結果的踏實準備。

我自己其實是有感覺到，隨著年紀增長，人其實是很難像年輕的時候那樣專心的。隨著年齡， 腦力有變差嗎? 我覺得沒有， 至少就我現在這個歲數沒有，但專注度絕對有差。

為了應付社會以及周遭人事的複雜，我們必須眼觀四面、耳聽八方， 思考變得比較周全(複雜)。而思考的複雜，會變得很難專心吞下接收到的東西。

對知識的功利心，讓我們去想：「學這個我可以賺到多少錢，可以獲得多少讚美? 有沒有更容易拿分的方法?」而不是想: 「不管我考幾分，理解這些真的很有趣」。

樂在其中的重點就是"無我"。

拿掉自我批判，只享受當下。

在這個沒有過去也沒有未來的當下，在這個斷面所產生的心流，

就是專注力的泉源。

這學期，我忘記了這些我早就知道的事。

以上是我的反省。

生命是長期而持續的累積。

2016/12/1 Formal Language

概略的講完11章
話說我好久沒有錄hw講解了

2016/12/2 Machine Learning

今天上到7.1.4的部分,
講完SVM的數學, 再講到SVM和logistic regression的error function有很高的相似性
SVM是minitor那些分錯的點, 落在margin內的點, 讓他們最少化
logistic regression則是用現有數據點算一個迴歸線, 基本上概念是很像的,
因為迴歸線周圍的點也不會剛好在迴歸線上, 也可以視為, 迴歸線周圍有一個margin

2016/12/2 Algorithm

今天睡過頭...orz

看完ilms上的"期中教學調查建議與回覆"真的快被嚇死了
這個老師到底有多認真啊....讓我好慚愧@@
你寫一句他回3句...我覺得老師比我還要認真....
不拿出國高中時的念書態度真的不行了

machine learning...就先放著等興趣自然回復好了
本人玻璃心, 經不起低分的打擊啊~~!!