演算法-93甲94乙
[About]演算法的常見問題
" 這學期下來學到了不少不同演算法的觀念與技巧,不過對於演算法最基本的概念我們卻不一定完全了解,這裡有關於演算法基本概念的幾個常見問題Q&A 一. Algorithm 與 Program 有什麼不同?一個Program是用某種電腦語言所寫一組明確的指令(Statement)組成, 用於處理一特定的問題。Algorithm 是一組明確的規則(rules), 可在有限步驟內解一特定的問題。所以由某一種電腦語言所寫的program 也可稱為一Algorithm, 但Algorithm 的表示方式不限於電腦語言, 它可以文字描述, 也可以半文字半符號的方式(pseudo-code)。有人說:「好的Algorithms 就如同computation 的好詩篇, 它不因所採用的語言文字而遜色」。 [@more@]
二. Algorithm 與數值分析(Numerical Analysis) 有什麼不同?
當電腦發明之後, 很多的數學計算也就依賴電腦協助, 因而有Numerical Analysis 課程, Numerical Analysis 主要是學習"數值問題"的解法與計算如: 多項式的根, 非線性等式的根, 聯立方程式的解, 微分式與積分式, 微分方程式的解, 還有許多數學運算。 雖然許多數學運算可以用簡潔的數學式表示(如微分式、積分式、特殊函數, 例如π, e , gamma function等), 但電腦只能處裡有限數位的運算, 所以這些數學式並不適合在電腦內部用運算, 而且用於工程與科學應用的數學計算, 不只要算得快, 也要算得精確知道解的精確度, 以滿足實務的需要, 所以須要一套有系統的方法, 也就是"數值分析"這門課所要學的。
"數值分析"是學習一些傳統解"數值問題"的方法; 而Algorithms 是以較宏觀(Macro)的方式探討解問題的方法與其原理(如recursive algorithm, dynamic programming, backtracking, branch and bound, . . . ), 這些解法原理可以應用到各種領域, 解各式各樣各樣的問題, 當然也適用於解"數值問題",學習Algorithms 的目的就是要能靈活應用它來解可能遭遇到的各種問題。
當Algorithms 研究領域興起後,許多學者也警覺到傳統數值分析的方法有許多改善的空間, 轉而以較宏觀的方式來觀察其解法如何改善, 如二矩陣相乘, Straussen應用Divide-and-Conquer 的解法原理, 就提出更快的方法, 而且由於 Divide-and-Conquer方法的啟發, 陸續又有學者提出一些改進的方法; 又如求Discrete Fourier Transformation、求多項式的值也找到方法較傳統方法為快(計算步驟減少), 這些年來數值計算方法已有很大改進, 這些方法也都漸漸載入進階的專書內, 進一步瞭解一些例子請參考(例如):
Borodin, A. and Munro, I, The Computational Complexity of Algebraic and Numeric Problems, University Microfilm International, A Bell & Howell Information Company, 1989.
三. Algorithm 與作業研究(Operations Research) 有什麼不同?
基本上說, Operations Research (OR)是研究一些特定的數學模式(如Linear Programming, Integer Programming, Nonlinear Programming, Markov Chain, Queuing Theory, Inventory Models, Location Models, Network Model, Game Theory等), 探究它的性質,並利用這些性質設計解法, 而這些模式的來源, 多是由實務問題的啟發, 再經許多學者多年專研, 終建立起一套理論架構, 一個實務問題由於強調的關點不同, 有可能由幾種不同的OR模式協助解決, 例如一存貨問題可採用的模式有可能是傳統存貨模式、線性(或整數)規劃模式或等候線模式等。毫無疑問的, 作業研究的模式必定愈來愈多, 每一種模式的理論會愈完整, 解法也會愈完善, 但畢竟現有的作業研究模式還是相當有限, 確實有很多實務問題無法經由作業研究模式得到適當之解法, 而Algorithms更宏觀的思考方式, 至少可彌補一些作業研究解題技巧的不足。
在作業研究內容中唯一的例外是Dynamic Programming (DP), 其實它不是一種數學模式, 更恰當的說, 它是解問題的一種解問題的原理、技巧, 它可以應用到解各式各樣的問題, 但 DP 本身並沒有什麼數學理論, 它只是根據 "Principle of Optimality" 這個原理來解問題。
四.Algorithm 與人工智慧 (Artificial Intelligence AI) 有什麼不同?
Artificial Intelligence也是探討如何解問題, 尤其要解的問題須要相當多資訊協助或問題的定義並不很明確, 所以它不只須演算法還要具備知識庫、學習系統、特殊邏輯表達方式 (人工智慧電腦語言), AI 處理問題的方式也可能是未來Algorithms 發展的方向。
五.Algorithm 的重要性
學數學的目的之一是思考的訓練, 希望在解數學問題的過程中, 增進思考能力。 Algorithms 用宏觀(Macro)的方式探討各種解問題的方法與其原理, 其實對處理問題的思考有很大幫助, 俗語說「萬事起頭難」, 而Algorithms 的一些原理常可以提供"著手處"的提示。
"
[About]旅行業務員的問題
"
關於老師上課也有講解過的旅行業務員問題,其實還有其他的解法,在這裡就一次說明清楚.
旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題，旅行業務員要到 n 個城市推展業務，n 個城市以 1,2,…,n 表示，從 1 出發，經過每個城市恰只一次，再回到 1，令 Cij 表城市 i 到城市 j 的旅行成本，問題為找出一個最小成本的路徑。在工廠的組合線上，以機器人上緊螺絲帽，機器人從起始的位置出發，做連續的移動，上緊每一個螺絲帽，再回到起始的位置，如何找到一個最短的路徑？這亦是旅行業務員問題。這個問題難在哪裏？我們看以下的四種解法。
[@more@]"
[re-class] Huffman coding
"In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper ""A Method for the Construction of Minimum-Redundancy Codes."" Huffman became a member of the MIT faculty upon graduation and was later the founding member of the Computer Science Department at the University of California, Santa Cruz, now a part of the Baskin School of Engineering. Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix-free code (sometimes called ""prefix codes"") (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. A method was later found to do this in linear time if input probabilities (also known as weights) are sorted. For a set of symbols with a uniform probability distribution and a number of members which is a power of two, Huffman coding is equivalent to simple binary block encoding, e.g., ASCII coding. Huffman coding is such a widespread method for creating prefix-free codes that the term ""Huffman code"" is widely used as a synonym for ""prefix-free code"" even when such a code is not produced by Huffman's algorithm. Although Huffman coding is optimal for a symbol-by-symbol coding with a known input probability distribution, its optimality can sometimes accidentally be over-stated. For example, arithmetic coding and LZW coding often have better compression capability. Both these methods can combine an arbitrary number of symbols for more efficient coding, and generally adapt to the actual input statistics, the latter of which is useful when input probabilities are not precisely known[@more@]"
[About] 機器人
"人工智慧真空吸塵器 今天收到一封廣告信，是 iRobot 公司出的 Roomba 智慧吸塵機器的廣告。先前讀到一些這方面的產品，就趁這個機會介紹一下好了，希望對於懶得打掃家裡地板的人有幫助 :p Roomba 和一般的智慧吸塵機器一樣，都是做成圓餅的形狀，主要還是為了在探索地型時撞到牆仍能順利轉彎。這類產品最基本的技術還是在於如何建立環境地圖，以及避開危險的地形；更進階的是要辨認什麼是需要清潔的，而什麼又是不能清理的(試想家中的博美狗被吸塵器抓住的樣子…) Roomba 用的概念很單純；它會先利用螺旋狀的路徑擴大自己的虛擬視野，試著找出房間的邊界在哪裡，同時記住自己走過的距離。當撞到東西時，它會先向後退一點點，轉一點點彎，再向前進。找到邊界之後，它會開始利用直線前進，並清掃記憶中還沒有打掃的區域。 在 Roomba 中比較有趣的是它還提供一個""虛擬牆""(Virtual Wall)的裝置；由於 Roomba 會儘量找出牆的範圍，所以如果門開著它搞不好就會跑出去了，若是我們希望門可以不要關，又不要它跑出房間，就可以把 Virtual Wall 放在門口，這樣它就不會跑出去了。Virtual Wall 其實是一個會發出不可見光的裝置，Roomba 感應到它的光線，就會當作那是禁區而轉彎了。 Roomba 這台能夠感測到樓梯之類的危險區域，而不會摔下去；當它在進行清掃的時候，會放音樂來降低它的噪音(還真貼心啊…-_-)，它的聲音大約是 80dB左右。 同樣的智慧型吸塵器是瑞典的 Electrolux 公司所做的 trilobite；這台紅色的小圓餅功能和 Roomba 類似，不過它不會避樓梯，而需要用鋪在地上磁毯來畫出禁區。不過它有個有趣的功能，就是會自己跑回去固定的""家""充電，真是很可愛的功能 :p 看完這個，有沒有想去買一個來玩看看丫xd[@more@]"
[Pre-class]RSA Network Security
"
之前上葉老師的資料結構時
就有聽過 現在網路上大部分的加密都是用RSA去做
而RSA的原理是將兩個質數做相乘
[@more@]
所以如果有人可以找到一套方法可以輕鬆看出一個數如何分解
那RSA就沒有用處囉~
補個維基的連結分享
"
心得---人工智慧
不知在某時 剛好跟小胖小聊到人工智慧的東西
小胖說 現在的AI 也不過是去學習人的模樣
說的好呀 或許 因為我們還跳不出一個格局
更或者 是我們不敢想像跳出格局的模樣
人好像就有個怪毛病 在地球都還沒有搞懂下 就急著想觀賞月球
月球也還沒明瞭 又急著去探索更遼闊的外太空
對於AI 我總覺得 我們對於"感覺"都還是很抽象
在人類醫學中 還是有神祕的死角
我們該如何突破 還是一昧的模仿人
其實 真的有AI的話 我還真想問問
記憶體在你肚子內 感覺如何XDDDD
[@more@]
心得---對於演算法VS資結
垮
第一次發覺 資結對於程式的重要性
尤其在演算法裡頭 如何在最有效的空間中
取得一個最佳的方式去利用我已知的儲存架構
在動態規劃中 被龐大的資料嚇到
如果要把整個樹求出 可是要花上一輩子的時間
再細部去觀察 才發現那箇中訣竅
好的演算法配上好的資料結構
是我還沒學會的東西
經過這幾次的程式
也不敢輕忽了 以為知道演算法的用法就OK了
[@more@]
心得---我印象中的密碼學
如果沒有記錯 最早的密碼是由凱薩大帝創造的
在戰爭之中為了確保機密不被間諜偷取
而發明的一種演算法
是將原本的字母往後移3個
將原本的A變成D 讓人猜不著本意
在福爾摩斯小說裡頭 更是有許多不同的演算法
在電腦上更是如此
不過 比凱薩的還複雜的多囉
利用質數去製造更不容易破解的演算法
[@more@]
心得 B&B演算法 implement TSP
"
從幾天前就開始著手寫TPS using B&B
有聽說會比上一次的using DP簡單
實際上 好像也沒有簡單到哪裡
B&B雖然有學過 也比DP直觀很多 但是真的用程式去trace
我也寫了超過20,30個小時吧
實做這幾個演算法花好幾個小時 那發明這個演算法的人就更厲害了
[@more@]"
[After-class]Dynamic Programming
"Dynamic Programming主要是用在最佳化(optimization)問題上,當我們需要找到最好的方式來做某件事情時.通常用不同方法來做某件事情的數目是指數的,所以用暴力搜尋來找最佳解除了在較小的問題大小之外,再計算上是不可行的.然而,我們可以將Dynamic Programming應用在當問題有著我們可以利用的特定數量的結構的這樣情況中.[@more@]
簡單的子問題:一定有某種方式可以將全域最佳化問題切割成子問題,每一個子問題都
和原始問題有類似的結構.另外,應該要有一個簡單的方式以少量的索引
(像是i j k 依此類推)來定義子問題.
子問題最佳化性質:一個全域問題的最佳解必須能夠使用一些相對簡單的組合運算,由
子問題的最佳解組合而成.我們不應該能夠找出包含子問題的次最
佳解的全域最佳解.
子問題重疊:一般來講對於不相關子問題的最佳解也可以包含子問題.確實,這樣的重疊
增進了儲存有對於子問題的解的動態規劃演算法的效率.
"
Huffman’s Encode
"
霍夫曼編碼法（Huffman’s Encode）是霍夫曼在1952年所提出的一種無失真壓縮技術，其原理是將欲壓縮之字串，先讀一遍，將字串中的每一相異單字元（Single Character）的出現頻率，做成統計，依此建構霍夫曼樹（Huffman’s Tree）。每一相異單字元，用0與1予以編碼，出現次數逾多者，給予較少的位元編碼，最後將這些位元串組合起來，並加上Huffman’s tree ，就成為壓縮檔案。Huffman編碼法為依資訊源符號出現機率，在對資訊源符號逐一編碼條件下(The symbols be coded one at a time)，最佳之編碼方法。
Huffman編碼法的特點在於所編碼出來的檔案具有唯一碼性質的即時碼。也就是各個相異字元所編碼出所位元串並不相同，解碼時能立即解出。也就是說，Huffman編碼法之解碼過程為即時(Instantaneous) 且為唯一(Uniquely Decodable) 之解碼。
參考來源：http://www.cc.chu.edu.tw/~u8702640/Huffman%BDs%BDX%AAk.htm
其實霍夫曼編碼法不算是個效率很好的壓縮，一般不會拿來單獨使用，而常與其他的壓縮演算法配合使用。
不一定每種東西都適合用同一種壓縮的演算法，要視情況而定，「不可逆壓縮模式」來做壓縮，有效提高壓縮效率，但也犧牲了原來檔案，「可逆壓縮模式」卻無法得到相當好的壓縮效率，所以要如何取捨就看使用著了。
[@more@]"
Hamiltonian Circuit Problem
"
通過每一頂點且只通過一次的路徑稱為漢米爾頓路徑;若是要求必須再回到起始頂點的迴路，則稱為漢米爾頓迴路。
由於漢米爾頓路徑及漢米爾頓迴路，到目前還沒有找到一個簡單又可快速判斷的充要條件，因此，我們只能利用這類路徑或迴路的基本特性來做判斷。首先，我們可以從下列之必要條件來判斷一個圖是否有漢米爾頓迴路：
漢米爾頓迴路通過圖中除起點外之任一頂點最多一次。
若一圖有漢米爾頓迴路，則該必具連通性。因為在非連通性的圖中，不可能有通過每一頂點之迴路。
若一圖有漢米爾頓迴路，則圖中任一頂點之進出次數至少是2。因為若有一頂點，其進出次數少於2(即進出次數為0或1)，即至多有一個邊連接該頂點，則要通過該頂點的任一迴路務必沿著同一邊回去才能通過其他頂點，如此一來必有一頂點重複通過，此乃不可能也。
若一圖存在漢米爾頓迴路，則任一條漢米爾頓迴路必經由那些次數為2的頂點之兩個邊。
若一頂點，其次數大於2，在建造一條漢米爾頓迴路時，一旦路過該頂點，則其他與該頂點相連接而尚未使用過的邊都不能再考慮使用。
在一個具有n個頂點的圖G=(V,E)中，任一漢米爾頓路徑必恰好經過n-1個邊;而任一漢米爾頓迴路必恰好經過n個邊。
若一圖有漢米爾頓迴路存在，則只要去掉該迴路上的任一個邊，及可得到此圖的漢米爾頓路徑。
參考資料：http://www.cis.nctu.edu.tw/~is83039/discret/discrete6.html
[@more@]"
Prim演算法
"
Prim演算法用於解決最小生成樹問題，基本步驟如下：
1.任選一頂點作為一子樹的根節點
2.將所有的邊依照權重放入優先權佇列
3.在佇列中尋找能與子樹中頂點連接的最輕邊並加入之
4.重覆前一步直到所有頂點皆包含在此子樹中
這個網站有一個簡單的例子。
可以讓大家參考。希望對大家有幫助了解Prim演算法。
http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/prim.html
[@more@]"
心得 演算法@@
說真的 課本中的每篇演算法 其實都算是當時被研發出來的論文
要在短時間內了解他 還有一定的難度
再加上 只有虛擬碼
實在很難去瞧出原始碼
寫程式會寫到想砸電腦
這是一們要多想的課
[@more@]
資料採礦演算法
料採礦演算法是建立採礦模型的機制。若要建立模型，演算法首先會分析一組資料，尋找特定模式和趨勢。接著，演算法會使用此分析結果來定義採礦模型的參數。
演算法建立的採礦模型可以有各種形式，包括：
- 一組規則，描述交易中的產品如何群組在一起。
- 決策樹，預測特定客戶是否會購買產品。
- 預測銷售的數學模型。
- 一組叢集，描述資料集的案例如何相關。
詳細內容:http://msdn2.microsoft.com/zh-tw/library/ms175595.aspx
[@more@]
Huffman編碼法
"
它的編碼方式是依據字母頻率出現的高低來編碼，可改進Run-Length的缺點，在資料中字母不需連續只要出現多次，一樣可達到壓縮的目的，但由於必須將檔案從頭讀到尾，所以相當浪費時間，而FGK演算法可改進這缺點。
參考:課本[@more@]"
Run-Length編碼法
"
它的編碼方式是根據連續出現字母的個數來編碼，譬如:AAAABBBCCC
我們可用4A3B3C將其編碼，但是若單獨出現或連續出現兩次則沒必要用Run-Length編碼，因為無好處，由此可知，若要效率好，必須在資料中”連續”出現相同的字母。
參考:課本
[@more@]"
[After-Class]Divide-and-Conquer
"
Divide-and-Conquer這章裡有我以前沒有嘗試去寫的quicksort
所以為了衝最後一篇文章 我選擇了寫這個章節的心得
Divide-and-Conquer可以當做一個滿不錯的寫程式概念 他可以讓問題很容易被解決
雖然說實際寫大程式時不應該像課本都用遞迴直接寫
因為遞迴會佔用大量的stack空間
所以可以先寫好遞迴版本的在把他改進成其他型式，這樣可以做出效能更好的程式
[@more@]"
Alpha-beta pruning
常使用於minMax game tree中，來增加search的效率，在Max node中的value稱為
alpha，在min node中的value稱為beta，透過alpha以及beta來修剪tree以減少訪
問的node，因為game tree通常很大，因此能夠有效的增加效率。[@more@]參考資料 http://en.wikipedia.org/wiki/Alpha-beta_pruning
[Pre Class]RSA
"
Public-key cryptosystem
a set of participants such that each participant has a public key and a secret key.
a network for sending messages among the participants.
RSA cryptosystem
can find large primes fairly readily, but have no efficient method for factoring a large number.
[@more@]"
