CH1 進入演算法的世界
1-1 運算思維
電腦(computer)具備資料處理與計算的電子設備
程式設計是電腦硬體與軟體息息相關的學科
處於物聯網(Internet Of Things IOT)與雲端運算(Cloud Computing)的時代，寫程式是全民的基本能力，唯有將創意經由設計過程與電腦結合，才能因應快速變遷的雲端世代。
雲端運算(Cloud Computing)：使用者透過網路登入遠端伺服器進行操作，就能使用運算資源。
物聯網(Internet Of Things IOT)：將各種具有裝置感測設備的物品，例如：RFID、環境感測器、全球定位系統等與網際網路結合，並透過網路技術讓各種實體物件、自動化裝置都能彼此溝通和交換資訊。
運算思維(Computational Thinking CT)：程式設計課程的目的，是分析與拆解問題能力的培養，培育AI時代必備的數位素養。
運算思維是一種利用電腦的邏輯來解決問題的思維， 就是一種能夠將問題「抽象化」與「具體化」的能力， 讓學生們能更有創意的展現出自己的想法與嘗試自行解決問題。
程式設計過程就是一種運算思維的表現，要學好運算思維，透過程式設計絕對是最佳的途徑。
Google運算思維課程提到，培養運算思維的四個面向：拆解(Decomposition)、模式識別(Pattern Recognition)、歸納與抽象化(Generalization and Abstraction)、演算法(Algorithm)，雖然這並不是建立運算思維唯一的方法 ，不過透過這四個面向我們能更有效率的發想， 利用運算方法與工具解決問題的思維能力 ，進而從中建立運算思維。
1. 拆解(Decomposition)
原本複雜的問題拆解成許多小問題，先將這些小問題各個擊破，小問題全部解決之後，原本的大問題也就迎刃而解了。
2. 模式識別(Pattern Recognition)
複雜的問題分解之後，常常能發現小問題中有共有的屬性以及相似之處，這些屬性就稱為模式pattern，模式識別是指在一堆資料中找出特徵和問題中的相似之處，用來將資料進行辨識與分類，並找出規律性，才能作為快速決策判斷。
3. 歸納與抽象化(Generalization and Abstraction)
過濾不必要特徵，讓我可以集中在重要特徵上，幫助將問題具體化，進而建立模型。
4. 演算法(Algorithm)
生活當中想辦法解決問題 ，這種計劃與考量過程就是運算思維 ，按照計劃逐步執行就是一種演算法(Algorithm)。
演算法是程式設計的第一步。
大數據(big data)在一定時效(Velocity)內進行大量(Volume)且多元性(Variety)資料的取得、分析、處理、保存等動作。
人工智慧(Artificial Intelligence AI)：使電腦具有類似人類學習解決複雜問題與展現思考等能力，舉凡模擬人類的聽、說、讀、寫、看、動作等電腦技術，都被歸類為人工智慧的可能範圍。
1-3 生活中演算法
1-3-1演算法的條件
五大特性：
輸入(Input)：可以沒有或多個輸入
輸出(Output)：至少會有一個輸出
明確性(Definiteness)
有限性(Finiteness)
有效性(Effectiveness)：能讓使用者使用紙筆推演出結果
表達方式
文字敘述、流程圖(FlowDiagram)、虛擬語言(PseudoLanguage)
1-3-2時間複雜度(Time Complexity)
要分析一個演算法的效率，是將該演算法在每個不同的輸入大小 之下，所執行的基本運算次數 設定成一個函數 (Function) T(n) ; 或稱Time function,Complexity function 。
定義一個T(n)來表示程式執行所要花費的時間，其中n代表資料輸入量， 程式的執行時間或者最大執行時間(Worse Case Executing Time)作為時間複雜度的衡量標準，一般以Big-oh表示。
O(f(n)) Big-oh of f(n) 可視為演算法在電腦中所需執行時間不會超過某一常數倍的f(n)，也就是某演算法的執行時間 T(n) 的時間複雜度(Time Complexity)為O(f(n))。
即存在兩個常數 c 與 n0，若 n>=n0 ，則 T(n) <= cf(n) ， f(n) 又稱之為執行時間的成長率 (rate of growth)，由於寧可高估不要低估的原則，所以估計出來的函數， 是真正所需執行時間的上限。
事實上，時間複雜度只是執行次數的一個概略的量度層級，並非真實的執行次數。Big-oh用來表示最壞執行時間的表現方式，它也是最常使用在描述時間複雜度的漸進式表示法。
對於 n>=16 時，時間複雜度的優劣比較關係如下：
O(1) < O(log2^n) < O(n) < O(nlog2^n) < O(n^2) < O(n^3) < O(2^n)
O(1)：陣列讀取
O(n)：簡易搜尋
O(log n)：二分搜尋
O(nlogn)：合併排序
O(n²)：選擇排序、泡沫排序、插入排序
O(2^n)：費波那契數列
1-3-3 程式設計邏輯簡介
傳統程式設計方法
由下而上法：程式設計師將整個程式需求最容易的部分先編寫，再逐步擴大來完成這個程式。由上而下法：則是將整個程式需求從上而下、由大到小逐步分解成較小的單元，或稱為模組 Module ，這樣使得程式設計師可針對各模組分別開發，不但減輕設計者的負擔、可讀性較高，對於日後為維護也容易許多。
結構化程式設計：核心精神就是「由上而下設計」與「模組化設計」。Pascal 語言中，這些模組稱為程序 Procedure，C語言中稱為函數 Function
結構化程式設計具備三種控制流程
循序結構：逐步的撰寫敘述
選擇結構：依某些條件做邏輯判斷
重複結構：依某些條件決定是否重複執行某些敘述
1-3-4 物件導向程式設計
物件導向程式 Objct Oriented Programming OOP：程式設計師以一種更生活化、可讀性更高設計觀念來進行，並且所開發出來的程式也較容易擴充、修改及維護。
透過物件的外部行為 Behavior 運作及內部狀態 State 模式，來進行詳細的描述。
行為 Behavior 代表此物件對外所顯示出來的運作方法，狀態 State 代表物件內部各種特徵的目前狀況。
每一個物件都是獨立的個體，對我們而言，無需去理解這些特定功能如何達成這個目標過程，僅須將需求告訴這個獨立個體便能獨立完成。
物件導向程式設計的重點是強調強制的可讀性 Readability 、重複使用性 Reusability 與延伸性 Extension 。本身還具備三種特性：
封裝性 Encapsulation
利用類別 class 來實作「抽象化資料型態 ADT」。類別是一種用來具體描述物件狀態與行為的資料型態，也可以看成是一個模型或藍圖，按照這個模型或藍圖所生產出來的實體 Instance ，就被稱為物件。
所謂抽象化就是將代表事物特徵的資料隱藏起來，並定義「方法 Method」作為操作這些資料的界面，讓使用者只能接觸到這些方法，而無法直接使用資料，符合資訊隱藏 Information Hiding 的意義。這種自訂的資料型態就稱為抽象化資料型態。
繼承性 Inheritance
物物件導向語言中最強大的功能，因為它允許程式碼的重複使用 Code Reusability ，及表達了樹狀結構中父代與子代的遺傳現象。
繼承，允許我們去定義一個新的類別來繼承既存的類別，進而使用或修改繼承而來的方法，並可在子列別中加入新的資料成員與函數成員。
多型 Polymorphism
按照英文字面解釋，就是一樣東西同時具有多種不同的型態。
利用類別的繼承架構，先建立一個基礎類別物件。使用者可透過物件的轉型宣告，將此物件向下轉型為衍生類別物件，進而控制所有衍生類別的「同名異式」成員方法。
就是具有繼承關係的不同類別物件，可以呼叫相同名稱的成員函數，並產生不同的反應結果。
物件 Object ：可以是抽象的概念或是一個具體的東西包括了資料 Data 以及所相應的運算 Methods ，它具有狀態 State 、行為 Behavior 與識別 Identity 。每一個物件均有其相應的屬性 Attributes 及屬性值 Attributes values 。
類別 Class ：是具有相同結構及行為的物件集合，是許多物件共同特徵的描述或物件的抽象化。類別中的一個物件有時就稱為該類別的一個實例 Instance
屬性 Attribute ：則是用來描述物件的基本特徵與其所屬的性質。
方法 Method ：則是物件導向資料庫系統裡物件的動作與行為。
CH2 地表上最常見經典演算法
2-1 分治演算法(Divide and conquer)
將一個難以直接解答的大問題依照不同概念，分割成兩個或更多的子問題，以便各個擊破，分而治之。
---------------------------------------------
def find_max(arr):
# Base case: if the list has only one element, return it
if len(arr) == 1:
return arr[0]
# Divide the list into two halves
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively find the maximum of each half
max_left = find_max(left_half)
max_right = find_max(right_half)
# Return the maximum of the two maximums
return max(max_left, max_right)
# Test the function
arr = [3, 8, 1, 5, 9, 4, 2, 7, 6]
print("Maximum number in the list:", find_max(arr))
---------------------------------------------
2-1-1 遞迴法Recursion
分治法和遞迴法很像都是將一個複雜的演算法問題的規模變得越來越小，最終使子問題容易求解。
遞迴在早期人工智慧所用的語言，如 Lisp、Prolog 幾乎都是整個語言運作的核心，現在許多程式語言，包括C、C++、Java、Python等，都具備遞迴功能。
對程式設計師而言，函數不單只是能夠被其他函數呼叫的程式單元，在某些程式語言還提供了自身引用的功能，這種功用就是所謂的遞迴。
階層Factorial
---------------------------------------------
intN=int(input("輸入一個正整數："))
fac=1
for i in range(intN,0,-1):
fac=fac*i
print("{0}!= {1}".format(intN,fac))
---------------------------------------------
def fac(n):
if n==0:
#遞迴條件終止
return 1
else:
#遞迴呼叫
return n*fac(n-1)
intN=int(input("輸入一個正整數："))
print("{0}!= {1}".format(intN,fac(intN)))
---------------------------------------------
費波那契數列Fibonacci Polynomial
---------------------------------------------
def fib(n):
if n==0:
return 0
elif n==1:
return 1
else:
return fib(n-1)+fib(n-2)
intN=int(input("輸入一個正整數："))
print("Fibonacci({0})= {1}".format(intN,fib(intN)))
#0,1,1,2,3,5,8...
#第0項：0、第1項：1、第2項：1、第3項：2、第4項：3、第5項：5、第6項：8...
---------------------------------------------
2-2 貪心法Greed Method-給我最好其餘免談
在每個解決問題步驟都採取當前狀態下最優化的選擇，不斷的改進該解答，逐步逼近給定的目標。
求圖形的最小生成樹(MST)、最短路徑與霍夫曼編碼Huffman Coding
2-3 動態規劃法 Dynamic Programming Algrithm PDA
將大問題拆解成各個小問題，其中與分治法最大不同的地方是可以讓每一個子問題的答案被儲存起來，以供下一次求解時直接取用，這樣的做法不但能減少再次需要計算的時間，並將這些解組合成大問題的解答，故使用動態規劃可以解決重複計算的缺點。
Fibonacci
---------------------------------------------
def fib(n):
if n in dic:return dic[n]
if n<=1:
return n
else:
dic[n]=fib(n-1)+fib(n-2)
return dic[n]
#預設即為public
dic={}
intN=int(input("輸入一個正整數："))
print("Fibonacci({0})= {1}".format(intN,fib(intN)))
print(dic)
---------------------------------------------
2-4 疊代法(iterative method)
無法使用公式一次求解，而須反覆運算。for 迴圈、while 迴圈
2-4-1 巴斯卡(Pascal)三角形演算法
C(r row,n column)
C(r,0)=1
C(r,n)=C(r,n-1)*(r-n+1)/n
2-5 窮舉法
根據問題要求，一一枚舉問題的解答，最終達到解決這個問題的目的。這種方法得到的結果總是正確的，唯一的缺點就是速度太慢。
如：列出1到500間的所有5的倍數的整數。枚舉法的作法就是從 1 開始到 500 逐一列出所有的整數，一邊枚舉一邊檢查該枚舉的數字是否為5的倍數，如果不是，不加以理會，如果是，則輸出。
2-6 回溯法(BackTracking)-不對就回頭
算是枚舉法中的一種，一旦發現不正確的數值，就回溯到上一層，節省時間。即是走不通就退回再走的方式。如：老鼠走迷宮。
CH3 超人氣資料結構簡介
3-1 認識資料結構
3-2 資料結構的種類
3-2-1 陣列 Array
3-2-2 鏈結串列 Linked List
3-2-3 堆疊 Stack 後進先出 Last in , First out
3-2-4 佇列 Queue 先進先出 First in , First out
3-3 樹狀結構
3-3-1 樹的基本概念
3-3-2 二元樹
3-4 圖形
3-5 雜湊表 Hash
雜湊表是一種儲存紀錄的連續記憶體，能透過雜湊涵數的應用，快速存取與搜尋資料。所謂雜湊函數 Hashing Function 就是將本身的鍵值，經由特定的數學函數運算或使用其他的方法，轉換成相對應的資料儲存位址。
CH4 最夯排序演算法
4-1 認識排序
4-2 氣泡排序法 Bubble Sort
4-3 選擇排序法 Selection Sort
4-4 插入排序法 Insert Sort
4-5 謝耳排序法 Shell Sort
4-6 合併排序法 Merge Sort
4-2 快速排序法 Quick Sort
4-2 基數排序法 Radix sort
CH5 必須學會的搜尋演算法
5-1 循序搜尋法 Sequential Search
5-2 二分搜尋法 Binary Search
5-3 內插搜尋法 Interpolation Search
5-4 費式搜尋法 Fibonacci Search
CH6 陣列與串列演算法
矩陣演算法與深度學習
矩陣相加演算法
矩陣相乘
轉置矩陣
稀疏矩陣
陣列與多項式
單向串列演算法
單向鏈結串列的連結
單向串列插入新節點
單向鏈結串列刪除節點
單向鏈結串列的反轉
CH7 安全性演算法
資訊安全 Information Security的基本功能必須具備以下四種特性：
秘密性 confidentiality
完整性 integrity
認證性 authentication
不可否認性 non-repudiation
7-1 資料加密
明文 Plain text --> 加密金鑰 Encrypt Key--> 密文 Cipher text --> 解密金鑰 Decrypt Key--> 明文
7-1-1 對稱鍵值加密系統
又稱單一鍵值加密系統 Single Key Encryption 或秘密金鑰 Secret Key
7-1-2 非對稱鍵值加密系統與RSA (Ron Rivest、Adi Shamir 和 Leonard Adleman 三人一起提出) 演算法
是目前較為普遍，也是金融界應用上最安全的加密系統，或稱為雙鍵加密系統 Double Key Encryption，這種加密系統主要運作方式，是以兩把不同的金鑰來對文件進行加解密。
7-1-3 認證
7-1-4 數位簽章 Digital Signature
屬於個人的一種數位身分證，可以用來作為對資料發送的身份進行辨別。
運作方式是以私有金鑰及雜湊函數互相搭配使用。
發文者先將明文與雜湊函數計算出雜湊值，接著再用自己的私有金鑰對雜湊值加密，加密後的內容即為數位簽章。
發送者將明文資料和數位簽章傳送給接收者，接受者再以發送者的公開金鑰解密，來驗證簽章。
7-2 雜湊演算法
雜湊法是利用雜湊函數來計算一個鍵值所對應的位址，進而建立雜湊表格，依賴雜湊函數來搜尋找到各鍵值存放在表格中的位址，搜尋速度與資料多少無關，在沒有碰撞和溢位下，一次讀取即可，更包括保密性高，因為不事先知道雜湊函數就無法搜尋的優點。
7-2-1 除法
7-2-2 中間平方法
7-2-3 折疊法
7-2-4 數位分析法
7-3 解決碰撞與溢位處理
7-3-1 線性探測法
7-3-2 平方探測法
7-3-3 再雜湊法
7-3-4 鏈結串列
CH8 堆疊與佇列演算法
陣列實作堆疊
鏈結串列實作堆疊
河內塔演算法
八皇后演算法
陣列實作佇列
鏈結串列實作佇列
雙向佇列
優先佇列
CH9 樹狀演算法
完滿二元樹 Fully Binary Tree
完整二元樹 Complete Binary Tree
歪斜樹 Skewed Binary Tree
嚴格二元樹 Strictly Binary Tree
9-1 陣列實作二元樹
9-2 鏈結串列實作二元樹
9-3 二元樹走訪
中序走訪 Inorder Traversal
前序走訪 Preorder Traversal
後序走訪 Postorder Traversal
9-4 二元樹節點搜尋
9-5 二元樹節點插入
9-6 二元樹節點刪除
9-7 堆積數排序法
堆積樹 Heap Tree可分為最大堆積樹以及最小堆積樹。
堆積樹排序法是選擇排序法的改進版，它可以減少在選擇排序法中的比較次數，進而減少排序時間。
9-8 延伸二元樹入門
9-9 霍夫曼樹
經常用於處理資料壓縮的問題，根據資料出現的頻率來建構的二元樹。
9-10 平衡術 Balanced Binary Tree
又稱AVL樹(是由 Adelson-Velskii 和 Landis兩人所發明)
9-11 決策樹 Decision Tree
CH10 圖形演算法
10-1 圖形簡介
10-1-1 尤拉環與尤拉鍊
尤拉環 Eulerian cycle 理論：所有頂點的分支度皆為偶數時，才能從某一頂點出發，經過每一邊一次，再回到起點。
10-1-2 圖形的定義
10-1-3 無向圖形
10-1-4 有向圖形
10-2 圖形的資料表示法
10-2-1 相鄰矩陣法
10-2-2 相鄰串列法
10-2-3 相鄰複合串列法
10-2-4 索引表格法
10-3 圖形的走訪
10-3-1 先深後廣走訪法
10-3-2 先廣後深 Breadth First Search 搜尋法
10-4 最小花費擴張樹-MST
10-4-1 Prim演算法
10-4-2 Kruskal演算法
10-5 圖形最短路徑法
10-5-1 Dijkstra演算法與A*演算法
10-5-2 Floyd演算法
CH11 AI高手的神級演算法
人工智慧 Artificial Intelligence 就是讓電腦能夠表現出類似人類智慧行為的科技，讓機器能夠具備人類的思考邏輯與行為模式，其原理是認定智慧源自於人類理性反應的過程而非結果，即是來自於以經驗為基礎的推理步驟與演算法。
圖靈測試 Turing Test ：如果一台機器能夠與人類展開對話，而不被看出是機器的分身，就能宣稱該機器擁有智慧。
近十年來人工智慧的應用領域越來越廣泛，關鍵因素就是圖形處理器 Graphics Processing Unit 等關鍵技術與先進演算法的高速發展。GPU 因為含有數千個小型且更高效率的 CPU，能有效平行處理 Parallel Processing，加上GPU是以向量和矩陣運算為基礎，大量的矩轉矩陣運算可以分配給眾多的核心同步進行處理 ，使得人工智慧領域正式進入實用階段，藉以加速科學、分析、遊戲、消費和人工智慧應用 。
平行處理技術是同時使用多個處理器來執行單一程式，藉以縮短運算時間。其過程為將資料以各種方式交給每一顆處理器，為了實現在多核心處理器上程式性能的提升，還必須將應用程式分成多個執行緒 Thread 來執行。
11-1 機器學習 Machine Learning 簡介
是AIi發展相當重要的一環，顧名思義就是讓電腦具備自己學習、分析並最終進行輸出的能力，主要的做法就是針對所要分析的資料進行分類 Classification ，有了這些分類才可以進一步分析與判斷這些資料的特性，最終的目的就是希望讓電腦像人類一樣具有學習能力。
11-1-1 監督式學習 Supervised learning 演算法
將輸入資料標籤化，從訓練資料截取特徵，以幫助判讀目標物，並分辨種類 。
11-1-2 半監督式學習 Semi-supervised learning演算法
11-1-3 非監督式學習 Un-supervised learning與K-平均演算法
11-1-4 增強式學習 Reinforcement learning 演算法
11-2認識深度學習 Deep Learning
讓電腦開始學會自行思考。隨著越來越強大的電腦運算功能，科學家開始採用模擬人類複雜神經架構，來實現讓電腦具備與人類相同的聽覺、視覺、理解與思考的能力。
例如：Google Deepmind 開發的AI圍棋程式 AlphaGo 接連大敗歐洲和南韓圍棋棋王。
------------------------------------------------
機器學習跟深度學習的差別是什麼?
人工智慧 Artificial Intelligence AI：讓電腦模擬人類做的事情
機器學習 (Machine Learning) 是 AI 的一個子集合，是實現 AI 的其中一種方法；讓電腦看過並「學習」大量數據，然後對問題進行推理與判斷的流程。
資料輸入 → 特徵擷取 → 訓練模型 → 輸出(判斷)
輸入資料後，機器學習需要進行「特徵擷取 (feature extraction)」，特徵是「人想出來的」；進行特徵擷取之後，將資料再輸入訓練模型中 ，最後便可以得到我們想要的答案。
深度學習 (Deep Learning) 則是機器學習的一個子集合，所以是機器學習的其中一種方法；讓電腦程式模擬人類的決策/判斷。
資料輸入 → 特徵擷取 + 訓練模型 → 輸出(判斷)
深度學習不需要再人為進行特徵擷取。只要把資料倒入訓練模型 (常常會聽到的「神經網路」) 中，訓練模型會自己進行特徵擷取，接著進行判斷，得到答案 。
當資料量越大，深度學習可以擷取的特徵可能性就越多，最後判斷的結果也會更加精準。
------------------------------------------------
11-2-1 類神經網路 Neural Network 演算法
輸入層 Input layer
隠藏層 Hidden layer
輸出層 Output layer
11-2-2 卷積神經網路 Convolutional Neural Networks CNN 演算法
11-2-3 遞迴神經網路 Recurrent Neural Network RNN 演算法
沒有留言:
張貼留言