[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 的一些原理常可以提供"著手處"的提示。
"
