前言 其實一直以來有寫iOS的code，不過由於習慣上的因素．一直沒有使用Cocoapods． 不過最近想說弄個小iPhone App搭著Golang的專案． 所以開始玩，不過Cocoapods其實一開始沒有那麼容易入手，所以又看了些plugin希望能讓使用上更簡單． 原本CocoaPods使用方式: 原本使用方式，需要如下表: 安裝CocoaPods sudo gem install cocoapods 撰寫 Podfile (相關細節) 打上 pod install來建立相關必要檔案 打開產生的workspace 這其實還挺繁瑣的，所以去找了plugin 安裝XCode Plugin ###先安裝 Plugin Package Manager - Alcatraz 這個Package Manager在安裝的時候，會跳出一個plugin 沒有經過授權的警告，不過就跳過去吧． 安裝Alcatraz: curl -fsSL https://raw.githubusercontent.com/supermarin/Alcatraz/deploy/Scripts/install.sh | sh 重新開啟XCode就可以． ###安裝CocoaPods Plugin for Xcode 安裝好Alcatraz重開之後，打開XCode [Windows] -> [Package Manager] 裡面選取，CocoaPods Plugin 就可以． 安裝好之後，要設定一下GEM_PATH，先確認一下你安裝Pod的位置，在Console打上: dirname `which pod` 把結果填入 XCode -> [Product] -> [CocoaPods] -> [GEM_PATH] 就可以直接在XCode上面更新與修改Podfile． 如果還有出現相關問題，可以看這裡The command path could not be resolved 相關鏈結: Cocoapods XCode Package Manager: Alcatraz CocoaPods Plugin

前言: 主要是紀錄一下一些在命令列(console mode)下的快捷鍵，希望以後有需要用到可以給自己紀錄一下． Console的快捷鍵列表 參考這裡來的． 以下兩個主要是一次移動一個字 alt ⌥+F to jump Forward by a word alt ⌥+B to jump Backward by a word 這邊有其他的部分，移動字元，或是移動到一開始． ctrl+A to jump to start of the line ctrl+E to jump to end of the line ctrl+K to kill the line starting from the cursor position ctrl+Y to paste text from the kill buffer ctrl+R to reverse search for commands you typed in the past from your history ctrl+S to forward search (works in zsh for me but not bash) ctrl+F to move forward by a char ctrl+B to move backward by a char 在iTerm2 裡面編輯快捷鍵來使用一次跳一個字 參考這裡 按下 cmd + , 選取 Profile -> Keys 加入以下: 使用 Alt+ <-來向左跳一個字 Keyboard Shortcut: ⌥← Action: Send Escape Sequence Esc+: b 加入以下: 使用 Alt+ ->來向右跳一個字 - Keyboard Shortcut: ⌥→ Action: Send Escape Sequence Esc+: f

前言 主要是因為Twitter上面有人提出來想寫一個小遊戲 idea: fetch twitter timeline，隨便抽幾個tweet出來然後叫user猜這個tweet是誰發的遊戲— bちゃん (@b123400) October 28, 2015 當然，這時候就給了正在愁不知道要怎麼讓自己Project52新的專案的我有了想法來寫． 所以我的目標是寫一個Golang的Package可以去做server-side oauth，並且讀取一些Twitter上面的資訊． 關於Twitter的Three-legged Authentication 上面這張圖清楚的顯示該如何做Twitter的OAuth Login，這裡講的主要都是Server-side的部分．簡單來說步驟主要分為以下數個: 透過你在Twittter Dev App申請的App Consumer Key 跟 Consumer Secret連線到oauth/request_token 開始認證 Twitter Server會給你另外一個 token URL 會連線到另外一個網址(該網址為Twitter擁有)去輸入帳號密碼或是同意該App使用你的帳戶資料． Twitter確認完畢後，會自動轉移到當初App設定好的Callback URL 你所架設Callback URL會收到Twitter Server呼叫，並且給你以下三個資料確認你登入的狀況． oauth_token oauth_token_secret oauth_callback_confirmed 只要oauth_callback_confirmed是正確的，你就可以透過oauth_token與oauth_token_secret去連接到該使用者的一些資訊． 設定正確的App資訊 只要到Twitter的Dev App 申請頁面，就會看到以下的幾個欄位． 不過最重要的欄位還是 Callback URL Callback URL Callback URL 很重要要講三次，因為很容易讓你卡很久就是這裡． 如果你要寫server-side的oauth的話，你必須要填入可以被接受的網址． 這裡定義可以被接受網址如下: 必須不是 localhost 必須有 https:// 如果你沒有填入資料到Callback URL的話，你就會被當成是Desktop App而無法進行Three-legged Authentication． 填好這一切的資訊，就可以拿到consumer key跟consumer secret來繼續以下的部分． 開始架設本地端測試流程 等等！ 你剛剛不是說不能把Callback URL寫成 localhost嗎？ 這邊就是要教導各位，如何在本地端測試與撰寫關於Server-side OAuth的流程． 修改你的hosts，並且將localhost改成比較有意義的． (ex: 個人改成 testgoserver.com) 記得testgoserver.com 填入Callback URL 這邊建議各位，直接參考這一段Twitter Server Go． 跑起來後，記得在瀏覽器打上 http://testgoserver.com就可以了． 常見的錯誤 Desktop applications only support the oauth_callback value ‘oob’ 詳細討論看這裡 表示App被認為是Desktop App，這時候需要去 https://apps.twitter.com/app/YOUAPPID/settings 設定Callback URL 此外，這邊的網址還不能使用localhost．所以你可能得寫成某個真正的網址． 不過建議不要lock，不然會出現以下錯誤 This client application's callback url has been locked 小專案 最後，我還是整理整個架構與將幾個我馬上會用到的API成一個packagey．放在https://github.com/kkdai/twitter 參考鏈結 Twitter API authentication in Go https://github.com/mrjones/oauth Twitter:sign-in Doc Twitter: Browser sign in flow Overview

前言與心得整理 我把第六週的部分拆成上跟下，上半部主要解釋P與NP之間的定義與關係．下半部就是要介紹一些證明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 第六週後半部分的課程內容: 問題難度的排序 根據前一個章節的整理，我們可以把問題依照困難度排列(難->簡單)如下: (假設 P不等於NP) 無解的問題 需要Exponatial Time才能解決的問題 多項式時間，還不能決定的問題 (所謂的 NP類問題) 裡面可以再分成 NP Complete(較難) -> NP (較簡單) 多項式時間，可以決定的問題 (所謂的 P類問題) 先回過頭看 Polynomial Reduction 在繼續看Cook’s Theorem定義之前，根據NPTEL的影片，其實有很多詳細的介紹．不過針對許多名詞有不同的定義: 首先先回過頭來看polynomial time reducibility定義如下: 假設一個可判定圖靈機(DTM)，從輸入為x處理並且輸出y的處理時間為Polynomial time-bond．如果x屬於L2，我們可以寫L2從L1polynomial time reducible過來的如果滿足以下條件: L2 屬於NP類問題，如果L原本是NP類問題 L2 屬於P類問題，如果原本L是屬於P類問題 這邊也就是解釋，我們可以透過reduction把不同的問題經過歸約(reduction)後到可以處理(或是判斷)為哪一類問題． 就可以回過頭來判斷轉換錢的問題是屬於那一類的問題． 再來，根據原有的plynomial time reducibility，我們會引入另外一個名詞定義polynomially transformable如下: A language L1 is polynomially transformable to L2, if there is a deterministic polynomial-time-bounded Turing machine M which will convert each string w1 in the alphabet of L1 into a string w2 in the alphabet of L2, such that w1 is in L1 if and only if w2 is in L2 L1 is NP-Complete and L1 polynomially transformable L2. To prove NP...

前言與心得整理 由於第六週的內容牽扯到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,...