前言與心得整理 剩下兩週了，就是開始深入了解圖靈機．本週會提到多軌圖靈機的計算方式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)...

前言 其實Go 1.5的正式公布後，最吸引人的就是與其他語言的相互合作．透過的可能是編譯成c-shared library．但是其實我個人最期待的，當然就是使用go mobile． 最近他們把相關的範例跟工具都弄的差不多，並且有一了份相當詳細的教學在這裡． 簡單流程: 由於教學寫得很清楚，我這裡簡單的把事情都跑過一次．注意：你需要有Go1.5． //抓取go mobile tool go get golang.org/x/mobile/cmd/gomobile //初始化gomobile，可能會花一點時間 gomobile init //編譯gomobile裡面的範例 //這會在本地端直接編譯出 basic.app 只要透過xcode 複製到手機上即可(需要有開發者付費帳號) gomobile build -target=ios golang.org/x/mobile/example/basic //如果要把go package編譯成iOS可以用的framework //這會在本地端編譯出一個hello.framework cd $GOPATH/src/golang.org/x/mobile/example/bind gomobile bind -target=ios golang.org/x/mobile/example/bind/hello //直接在xcode拿來使用即可 open ios/bind.xcodeproj 來個iOS簡單範例 (11/17更新) 這裡提供一個簡單的範例，主要也是測試一下幾個主要的疑慮: 簡單的範例程式碼在這裡，這裡有直接的playgroud package gomobile01 import ( "fmt" ) type Goomobile struct { Data string } //記得要有constructor 不然到時候你無法自行透過 NSObject init 來建立這個物件 func New() *Goomobile { return &Goomobile{Data: "Default test"} } func (g *Goomobile) GetData() string { fmt.Println("test go ") return g.Data } 這時候建立這個iOS framework 指令是 (假設專案寫在kkdai/gomobile01) $ gomobile bind -target=ios github.com/kkdai/gomobile01 然後會產生一個gomobile01.framework 把他拉進xcode專案． 以下提供如何使用的方式: //載入該framework #import "gomobile01/Gomobile01.h" 這裡是使用的方式，切記要使用Constructor不要使用 [[xx alloc] init] GoGomobile01Goomobile *gb = GoGomobile01New(); //Default data is @"Default test" [gb setData:@"Data...."]; NSString * str = [gb GetData]; //str = @"Data..." 已知可以支援的部分 基礎的運算與簡單的資料格式當初參數 (int, string) 支援structure跟method 可以跑net/http但是記得別直接拿rpc.Client或是http.Client當作public 相關限制 目前試著編譯幾個有在使用的package發現有以下的問題，可能需要解決． []slice, map, interface{} 比較進階的資料格式不支援 (可能也不能轉換到iOS) 同理可證，一些package裡面的變數也不要放在parameter裡面．只支援基礎資料格式． 即便是簡單的string, int不支援public global variable． var TestVariable string 不被允許 但是var testVariable string 是可以允許的 const目前還不支援 (gomobile: not yet...