演算法初探

演算法(Algrothm)

當演算法改變世界時，認識演算法就是義務

引自鄭國威先生

演算法探討研究課題

什麼是演算法?在日常生活中哪個地方可以看見演算法?
什麼是演算法思維?
如何傳達演算法?
什麼是演算法的重要屬性(特徵)?
為什麼演算法很重要?
有哪些重要的演算法及如何創造一個演算法?
演算法有何應用-人工智慧.機器學習

活動設計1-觀看動畫.說看看何謂演算法?

日常生活演算法動畫影片

Q1:思考一下:何謂演算法?日常生活還有哪些演算法的例子呢?

1.演算法定義

圖片引用https://shouzo.github.io/2017/07/20/Data_Structure_Book/

電腦科學演算法動畫影片

(1)廣義

根據韋伯字典的定義，凡是為解決某一特定問題的一步一步程序(a step-by-step procedure for solving a problem)均可以稱為演算法。

根據演算法的廣義定義，我們可以說一本食譜書籍中包含許多演算法，因為每一個單一食譜(recipe) 都是一步一步解決烹調出某一種美食(例如，咖哩雞肉) 的程序。

範例1-食譜

參考網站及資料引用

http://www.bookask.com/find/2590.html

:https://read01.com/j7LADx.html

Q2:思考一下:如何評斷一個食譜的好壞呢?是不是所有人拿到這個食譜都可做出來像大廚一樣煮出來的美味呢?

好的食譜譜正是優秀的演算法

參考網站及資料引用

http://www.bookask.com/find/2590.html

:https://read01.com/j7LADx.html

範例2-企業組織的標準作業程序(Standard Operating Procedure, SOP)

(2)狹義

演算法是一個由一些步驟所構成的集合，依循這些步驟得以解決數學問題或完成計算機過程(a set of steps that are followed in order to solve a mathematical problem or to complete a computer process)。

以下，我們參照狹義的演算法定義，從計算的角度給定演算法的嚴謹定義，以方便將演算法的概念應用於計算機中。從這裡，我們開始闡述一個有關於演算法的一門學科(a discipline of algorithms) 演算法學(Algorithmics)。從計算的角度給定演算法的嚴謹定義如下：

由有限(finite) 步驟(step) 所構成的集合，依照給定輸入(input) 依序執行每個明確(definite) 且有效(effective) 的步驟，以便能夠解決特定的問題；而步驟的執行必定會終止(terminate)，並產生輸出(output)

(3)小結

A.演算法是用來解決問題

B.演算法將解法切割成不同步驟

C.演算法的解決問題的步驟是精確的，不靠人類的直覺與猜測

因為上面的幾個特性，我們才能夠藉由將演算法編寫成程式利用電腦做運行計算，來解決我們生活上的問題

2.演算法思維

演算法的思維想是理解，執行，評估和創造的能力算法

想要成為演算法的思想家，你必須能夠理解和執行演算法。有些人發現很容易遵循一系列精確的指令，而其他人覺得很有挑戰性。有些人似乎缺乏耐心和勤奮需要遵循分步計畫。然而，它是所有人都應該都掌握有價值的技能。演算法思想需要耐心，因為每個指令必須執行其正確的順序沒有跳到前面或"粉飾"部分說明。此外，演算法思想需要勤奮和毅力。它往往是單調乏味的一種複雜的演算法步驟和人們有時無法完成的演算法，因為他們只是"放棄。

我們生活在"資訊時代"，很多人工作需要透過電腦才能完成。然而，電腦目前有沒有真正的理解或認識 — — 他們只能執行人已開發出演算法解決的任務。因此，若要創建電腦可以執行的演算法，您必須瞭解什麼是電腦能夠執行的和能夠寫一系列的電腦可以成功執行的明確指示。

活動設計2-古老遊戲演算法

古老的遊戲:河內塔動畫下載

說明http://simonsays-tw.com/web/Recursion/Iteration&Recursion.html

http://simonsays-tw.com/web/Recursion/TowerOfHanoi.html

Q3:思考一下:在遊戲中，你是如何解決問題(過關)?

解說

依照密技所指示的步驟來操作，無論誰每次都可以過關。這種為遊戲通關設計的密技(定式)，也算是不錯的演算法

更多遊戲

古老的童玩

http://simonsays-tw.com/web/Recursion/Iteration&Recursion.html

PC man

http://jspacman.bitbucket.io/

說明

https://bitbucket.org/8tentaculos/jspacman

Lode Runner

http://loderunnerwebgame.com/game

2048

PLAY

開放原始碼
https://github.com/gabrielecirulli/2048

https://ifun01.com/N8LXXFB.html

http://m.guokr.com/post/572289

《2048》走紅：手機遊戲最嚴重的抄襲
https://www.cool3c.com/article/80718

http://www.chinatimes.com/realtimenews/20140514003026-260412

http://ruikye.com/2015/04/10/2048-algorithm/

2048超進化-2147483648

http://cyberzhg.github.io/2048/

THREES!
https://www.inside.com.tw/2014/02/10/threes-mobile-game

http://www.playpcesor.com/2014/03/threes-android.html

http://threesjs.com/

https://gnn.gamer.com.tw/0/95940.html

3.演算法的表示

自然語言(文字)
虛擬碼
流程圖

4.演算法特性(徵)

根據上述演算法的嚴謹定義，演算法是由解決某一特定問題的一些步驟所組成，具有以下特性：

(1) 指定輸入(input)：演算法必須指定輸入，可以由外界輸入0 個、1 個或多個資料。

(2) 具有輸出(output)：演算法必定有至少1 個以上的輸出。

(3) 有限性(finiteness)：演算法步驟的個數必須是有限的，而且步驟的執行最後會終止(terminate) 。

(4) 明確性(definiteness)：演算法的每個步驟都必須是明確(definite) 而不含糊的(unambiguous) 。

(5) 有效性(effectiveness)：演算法的每個步驟必須是有效的(effective) 或說是可行的(feasible) 。

範例

5.演算法的重要性

軟體設計的思想最重要是演算法，而演算法是建立在數學思維上的，其實說白了，程式只是一件衣服，演算法才是它的靈魂，演算法就來自於數學，沒有深厚的數學思維功底，是弄不懂演算法的。所以，如果你想從事軟體設計，那麼就認真的培養自己的數學思維吧！

6.重要的演算法及如何創建演算法

參考網站及資料引用

http://www.bookask.com/find/2590.html

:https://read01.com/j7LADx.html

活動設計3-體驗演算法動畫

活動設計4-如何創建演算法

問題:兩個人在同一家公司工作，有W的美元合計總工資，而是一個人賺 Q美元，比其他人多。他們每人賺多少錢？

原則 1︰使用鉛筆和紙手工解決問題的特定實例

特定實例的一個問題是當所有的"變數"給出一個具體的值。假如我們讓 W= 57.00美元，讓 Q=5.00美元。

具體問題實例︰兩人工作為相同公司，總共的薪酬為美元 57.00，其中一個人賺比其他人多$5.00 美元。請問每個人賺多少美元？

有多種方法來思考這個問題。兩個可能的解決辦法是︰

算術推理：

代數推理：

全部賺$ 57，Person1比Person2 多賺$ 5 。
因此2人平均 $ 57 - $ 5 = $ 52

$ 52/2為$ 26 ，所以每人至少賺$ 26

Person1 賺得 $ 31（$ 26 + $ 5）

Person22 賺得$ 26

設X = Person1的薪酬

設Y = Person2的薪酬。

因此，我們從問題知道：               X = Y + 5和               X + Y = 57。

使用替代求解這兩個方程：

              （Y + 5）+ Y = 57               Y = 26

因此               X = Y + 5 = 31

請注意：如果你不能手動解決這個問題，那你也不可能寫一個演算法來解決這個問題！

原則 2︰使用變數解決問題的特定實例

算術推理：

代數推理：

設工資總額 W， Person1比Person2多賺Q。
兩人共享工資（W - Q）。每個人至少獲得（W - Q）/ 2。

Person1得到（W - Q）/ 2 + Q

Person2得到（W - Q）/ 2

讓X = Person1的薪水
讓Y = Person2的薪水。
因此，我們從問題知道：
              X = Y + Q 和
              X + Y = W。
使用替代求解這兩個方程：
              （Y + Q）+ Y = W
              Y =（W-Q）/ 2
因此               X =（W - Q）/ 2 + Q

原則3:用幾個測試案例並手動執行您的演算法，來驗證它會產生正確的答案。這就是所謂的desk checking (桌面檢查)

實例1：               W = 100，Q = 10

              Person1 =（100-10）/ 2 + 10 = 55

              Person2 =（100-10）/ 2 = 45

（這是正確的，因為55 + 45 = 100，Person1比Person2賺10美元）

原則 4：在知道任務的一般解決方案之後，編寫正確的程式語言在計算機上實現您的解決方案

延伸學習(有興趣同學可自行閱讀)

演算法相關書籍及新聞：

(1)書籍

How to Solve It（張憶壽教授的譯本)

(2)新聞

Google 的人工智慧系統AlphaGo 阿爾法狗打敗人類圍棋冠軍，在三月九日到十五日的五戰圍棋對弈中取得首勝，為人工智慧發展寫下重要里程碑。中國圍棋（西方稱為Go）的歷史悠久且複雜無比，南韓棋王李世是全球最佳棋士之一，他自十二歲成為職業棋士以來，已拿下十八個世界冠軍頭銜。他表示，因為人有犯錯的風險，所以可能無法打敗AlphaGo。現年三十三歲的他在第一場對弈登場前說：「人之所以為人，是因為他們會犯錯。」

人為錯誤不僅是他唯一的弱點。李世表示，人類棋手對弈時可揣摩對方的反應與心理，但這次看不到這些線索，讓他頗不習慣。反觀AlphaGo這個機器棋手則有許多優勢。它從十萬多場圍棋比賽中模仿高手的棋譜，然後和自己下棋，從錯誤中「學習」。Google 的DeepMind 團隊也設計一套程式，讓AlphaGo可以預測每一步棋對比賽的長遠影響，從而判斷哪步落子會必勝。

用30分鐘深入瞭解《AlphaGo圍棋程式的設計原理》簡報

用30分鐘深入瞭解《AlphaGo圍棋程式的設計原理》錄影檔 from 鍾誠陳鍾誠

用十分鐘學會《資料結構、演算法和計算理論》

引自金門大學資工系陳教授

演算法相關學習資源

動畫

文字網站電子書

影片

程式設計專案展現

http://peanut.lkjh.tyc.edu.tw/moodle/mod/url/view.php?id=77

不插電學演算法

https://code.org/curriculum/unplugged

演算法之應用-機器學習