前言與心得整理 由於第六週的內容牽扯到P=NP相關理論還有NP-Complete的證明．所以我把內容拆成兩個禮拜，希望能夠更仔細地來了解這個部分． 相關文章 [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness 第六週前半部分的課程內容: ###Intractable Problems P類問題 接下來會介紹一些需要耗費相當多的時間(指的是處理時間超過指數時間(polynomial-time)的問題． 回過頭來先要定義如何指出圖靈機的時間限制: T(n): 指的是輸入w長度為n的時候，該圖靈機一定會停止的 這時候就會帶出第一個名詞: P 也就是如何定義一個問題是屬於P類的問題 (Class P problem) Class P: 指的是在DTM(Deterministic Turing Machine)下，其T(n)= polynomial-time (指數時間) 關於”P類”問題的範例 DTM可以被來當成是否可以用DFA(Deterministic Finite Automata_來表示其狀態的TM(Turing Machine)． 所以其實要尋找類似的範例其實不難，只是該問題必須要是在指數時間才能解決的，課堂上提供的範例如下: 在CFG的 L(G) 給予一個字串w．判斷w in L(G) 之前有提過要快的話，必須使用CYK演算法．然後其時間複雜度為O(n^3) NP類問題 在介紹NP類問題前，雖然課堂上老師直接透過背包問題(Knapsack Problem)來引導NP類問題．不過我個人認為，還是需要簡單的瞭解一下`NP類問題｀的定義: Class NP: 指在NTM(Nondeterministic Turing Machine)下，其T(n)為指數時間(polynomial-time) 沒有錯，P類問題與NP類問題最大的差異是TM讀入一個輸入的時候．其反應是唯一的(DFA)或是多重的(NFA)． 接下來就可以將背包問題(Knapsack Problem)開始帶入: 什麼是背包問題(Knapsack Problem) 關於背包問題的定義，種類與範例．其實這一篇台師大的文章講得非常好．這裡僅僅簡單的帶過: 背包問題: 將一堆東西放進背包，每一件物品有它的重量與價值，透過有限制重量的背包來取得放入價值的最大化． 解法與時間複雜度: 對於背包問題的解法，一般而言就是透過動態規劃(Dynamic Programming)的方式來找．如此一來: 如果有n個物件，就必須要找出該物件放進背包與不放進背包的價值．所以時間複雜度為O(n * 2^n) (2是因為要計算 出現與不出現．必須要反覆計算n回) P = NP ? 接下來就帶入大家都了解的P=NP這個被稱為史上七大難解問題之一． 究竟P是不是相同於NP？ 其實課堂上也有一些簡單的討論． 以上的圖是來是Wiki，主要是講解如果認為P不等於NP的時候．他的概念是以這樣的方式作為出發來討論． NP-Complete Problem 首先要討論P是否相同於NP，可以透過一個面向來探討．就是透過NP完全(NP-Complete Problem)． A decision problem C is NP-complete if: C is in NP, and Every problem in NP is reducible to C in polynomial time 這是從NP-Completeness看到比較formal的定義．也就是說，如果我們能夠透過polytime reductions的方式來朝向證明NP-Completeness Polytime Reductions Polytime Reductions 又稱為Polynomial-time reduction，以下會解釋這種reduction 的目標與方法: 目標: 如果可以找到一個方式將所有的NP問題歸約(reduction)成語言L，並且能夠找到多項式的解決時間(Polytime)．那麼就可以找到多項式的演算法(deterministic polytime algorithm)來計算所有的NP問題． 簡單的來說:...

前言與心得整理 剩下兩週了，就是開始深入了解圖靈機．本週會提到多軌圖靈機的計算方式PCP問題． 此外，本週也開始更多了對於無法判定(undecidable)的問題(problem)的探討．這一系列需要更多的證明，其實如果光看老師課堂上的講義跟講解，其實不是很好了解． 需要相當多的輔助學習跟查詢，我只能就我自己了解的部分．希望能幫助大家，也能給自己做些紀錄． 相關文章 [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness 第五週課程內容: ###Extensions and properties of Turing machines 一開始繼續來探討圖靈機，順便看看有沒有一些衍伸的部分可以加以討論． Multiple Tape Track 一開始我們都只有定義一個圖靈機是擁有: 一個狀態，一個輸入tape跟相關的動作． 但是如果有多個tape track的話，圖靈機該如何處理呢？ 最常見的就是類似上面圖形的圖形機，上面 BXB 代表的是 data tape(track)，而下方WYZ代表的是marker tape．也就是說下方的資料是用來紀錄目前執行到哪個地方，以便後來做相對應的處理之用． 範例: 首先要注意的是，這個範例僅僅是在課堂上提出來的．並不代表所有的Turing Machine都應該這樣處理．主要還是看如何去處理transition functio與資料輸入的時候該如何查表． 首先要先來解釋一下，幾個transition function的動作說明．再來看δ()之前，我們需要知道幾個符號的定義： B, X: 代表是輸入的符號B是空白，X某些資料． a, b: 代表是0, 1(都可以，這裡只是代表數字) p, q, r: 代表的是狀態(state) R, L :代表的是要向左移動或是向右移動． tape指的是資料帶，裡面通常有兩個track，一個是輸入，一個是紀錄marker(或是給TM紀錄輸出) 1 tape = 2 tracks 基礎符號複習好之後，我們就可以開始來看transition function: δ()的意思． δ([q, B], [B, a]) = ([p, a], [X, a], R): 先從一開始來看 δ([q, B], [B, a]) 裡面的 [q, B]: 代表的是目前圖靈機的狀態與cache，其中q是狀態，B是cache． [B, a]: 代表的是輸入的tape(其中B為第一個tape, a為第二個type-可以是0或是1) 接下來看到等式的右方 ([p,a], [X,a], R): [p,a] 這個代表執行過後的狀態為p，cache變成了a．(注意: 因為a等式左方的a是相同，所以原先是0就是0, 如果是1就取出1) [X,a] 這代表執行過後的tape的變化，變成了[X,a] R 就是代表要繼續向右移動一個來讀取新的數值． 其他幾個就不詳述，只是先列出來等等查表需要用到： δ([q, B], [B, a]) = ([p, a], [X, a], R)(上面的式子，我只是放在一起方便參考) δ([p, a], [B, b]) = ([p, a], [B,...

前言與心得整理 進入到第四週，這個章節會透過深入了解PDA(Pushdown Automata)來導入CYK演算法與計算機的基礎- 圖靈機(Turing Machine)． 算是我一開始就相當期待的課程． 相關文章 [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness 第四週課程內容: Equivalence of PDA’s and CFG’s 主要這個章節是會提到如何將CFG(Context-Free Grammar)轉換成 PDA(Pushdown Automata)， 首先先來符號介紹: L(G): 屬於CFG G所以符合的Language L 我們想要透過 PDA P來找出一個轉換方式可以產生 N(P) = L 在這個 PDA(P)裡面有: start node q 所有的輸入symbol 屬於 G 相同的stack會存入的就是symbol所以也是從G挑出來 一開始的symbol也是從G挑出來． 範例: CFG: S->Aa ; A->cc Stack start symbol: S Input: acc 以下分開成δ()與stack狀態 δ(q, a, S), stack: [S], input: cc (輸入a 進去了) 這時候會從input 移除a, S 可以轉換成 Aa 去除掉a stack剩下 [A] δ(q, c, A), stack: [A], input: c 這時候轉換A->cc 並且一個c 被input 修除 δ(q, c, c), stack: [c], input: ε δ(q, ε, ε), stack: [ε], input: ε 於是結果為Stack變更的流程為: [S]->[aA]->[A]->[cc]->[c]->ε Convert PDA to CFG 接下來要來將PDA的轉換式，轉換成CFG．根據定義我們會從 L = N(P) 來建立相同L的 CFG G，並且滿足 L(G) = L =...

前言與心得整理 進入到第三週，前兩個章節都是在介紹可以透過RE(Regular Expression)來表示的語言．這一次就是無法透過RE來表示的語言(CFG: Content-Free Grammar)還有相關的定義與運算． 相關文章 [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness 第三週課程內容: Context-Free Grammar Content-Free Grammar(以下簡稱CFG) 是一種可以透過符號來敘述語言，可以表達比RE更多的語言(但是不是全部)．特別是在表現巢狀結構的語言． 以下只介紹正式的定義: Terminals: 定義好的符號，類似語言中的alphabet． Variables: 又稱為non-terminals，有限集合的符號，另一種表示語言的方式． Start Symbol:類似於RE中的start state． Production(投射): 也就一種對應的關係，通常表示為 ->． 其中左邊是 variables 右邊是 terminals跟variables的字串． ex: S-> {0, 1} Derivations(推導): 主要就是將CFG由start symbol開始，並且開始將variable投射出相對應的variables或是terminals其中的代表符號是=>． S->01 S->0S1 則 S=>0S1(將S->0S1)=>00SS11(將一個S->0, 另一個S->1)=>000111 Iterated Derivation: 符號為 =>* 如同Kleene Star定義一樣，這個代表推導為0或是更多． a =>* a (就是代表任意個a) a =>* b and b=> c 則 a=>* c Sentential Forms (句型): 指的是字串可以由Start Symbol加上 terminal 或是 variables． S =>* a 那麼 a就可以被稱為 sentential form (因為a是一start symbol，而且加上variable a組合而成．) 以下是一個簡單的範例: CFG : { 0^n 1^n | n >=1 } terminals: {0, 1} variables: {S} start symbol: S product: S -> {01} S -> 0S1 關於Iterated Derivation範例: S -> 01; S->0S1 則 S=>...

##前言 這次的Golang Taipei Gathering #15 我有參與閃電秀． ###Gobot 講者: kerkerj slide: Golang Taipei Gathering #15 - 進擊的 Gobot! from kerkerj 主要是講姐Gobot的一些指令，Gobot提供相當好的介面可以直接去控制GPIO跟一些相關的機器． RPI/Ardurino甚至提供指令直接控制Sphero． Gobot 提供直接的方式可以控制COM port 與RS232直接對Ardurino與其他設備來溝通． 閃電秀： Project 52 不好意思～～我的閃電秀…. Project52 from Evan Lin ###Go Microserver Use Case 講者: David Hernandez 針對Microservice 講者注重的是: How to handle big request in short time What if some service down –> circuit breaker 有展示Goconvey的測試，感覺很酷．

前言與心得整理 進入到第二週，不知道會不會有更困難的主題出現．寫筆記寫著寫著，發現自己筆記內容比原本老師講的還要多，代表自己不懂得真的太多，需要不斷的補充資料來讓自己更清楚． 相關文章 [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness 第二週課程內容: Regular Express 基本定義 與 運算 符號定義: 通常顯示E來表達一個regular expression，而L(E) 就表示一個regular expression 能表達出來的語言(language)． Language的運算: (Union/Concatenation/Kleene Star) Union (U): 就是把兩個language做一個簡單的聯集． ex: {01, 11, 101} U {10, 11, 101} = {01, 10, 11, 101} Concatenaion (LM): 把兩個language做一個連接，但是注意這裡跟字串的concatenation是不同的．基本定義而顏，把語言L跟語言M連接在一起就稱為LM． LM = wx | w in L and x in M． ex: L = { 01, 11} M = { 10, 11} LM = { 0110, 0111, 1110, 1111} 也就是 第一個L元素配上第一個M元素，第二個L元素配上第一個M元素．繼續類推． Kleene Star (*): 就是regex裡面的*，表達任何子集合在L中與空集合或是一個以上的子集合的聯集． L* = {ε} U L U LL ... ex: L = {01, 11} L*= {} or {01, 11} or {0101, 0111, 1101, 1111} .... Regular Expression定義 a是一個symbol, 如果a是一個regular express(記作RE)，則 L(A) = {a} L{ε} = {ε} L(empty set)...