# 演算法 Algorithm (CSIE-2B)

###### tags: `courses meow` `CSIE-2B` `Algorithm` `2021 Spring`

:::info
:::spoiler click to open TOC
[TOC]
:::

> $Algorithms + Data Structures = Programs$ [name=Niklaus Emil Wirth]
:::success
## 課程資訊

- Lecturer : 江振瑞
- TA :
- 陳思翰
- 朱俊瑋
- 林彥廷
- 陳祐麟
- 作業 :
- 每週手寫6~10選2
- 線上程式作業3選1
- 助教課分組報告抽6組報告
- 分數 :
- 期中考(25%)
- 期末考(30%)
- 程式設計作業、報告、課程參與度、程式設計競賽成績(45%)
- 加分:完成一個以上的IBM Q Experience程式執行展示
- 上課時間 :
- TA課 : 2. ~ 2.30
- 休息10分鐘
- 2.40 ~ 5.30(中間會休息10分鐘)
- tectbook密碼 : algalg
:::
:::info
:::spoiler click to open syllabus
第一週:認識演算法 -- 從食譜到高階語言
第二週:演算法的正確性
第三週:演算法的複雜性分析
第四週:分治(divided-and-conquer)演算法
第五週:刪尋(prune-and-search)演算法
第六週:貪婪演算法(greedy algorithms)
第七週:動態規劃(dynamic algorithms)演算法
第八週:使用貪婪(greedy)演算法以及動態規劃(dynamic programming)演算法解決最短路徑問題
第九週:樹搜尋(tree search)與回朔(backtracking)演算法
第十週:分支定界(branch and bound)演算法
第十一週:問題下界與問題分類:P、NP、NP困難、NP完全問題
第十二週:最小成本最大流量(minuimum-cost maximum-flow)問題
第十三週:匈牙利演算法(Hungarian algorithm)
第十四週:近似演算法(approximation algorithms)
第十五週:機器學習/深度學習演算法(machine learning/deep learning alogrithm)
第十六週:量子演算法(quantum algothrims)
:::
### Alogrithm is IPO

> 演算法就是已知Input跟Output，然後希望你求出Process[name=教授]
:::success
:::

> 用演算法模擬大腦做的事情，即為類神經網路(Deep Learning)[name=教授]
<!--能否以AI進行對大腦的逆向工程，藉此對人體的大腦結構有更深入的解釋-->
> 演算法的I跟O一定要寫清楚，才能知道P對還錯[name=教授]
### 演算法的歷史

### 什麼是演算法?
> 廣義來說，一步一步解決問題的方法，就稱為演算法[name=Merriam-Webster Dictionary]

---

# Chapter 1
## *從食譜到高階語言*

- 食譜是演算法
- 食材是Input，成品是Output
- 我們要設計食譜，設計如何完成那道菜
- 這個設計的過程即為演算法
- 流程圖是演算法
- SOP是演算法

> 舉這麼多例子，只是希望你們了解，演算法就在我們的生活中[name=教授]

### 演算法的特性
- 輸入(I) : 演算法需有零個或以上的輸入
- 明確性(definiteness) : 演算法應沒有歧異，且能正確完成使用者的要求
- 有限性(finiteness) : 演算法應能以有限個的步驟(計算)完成，且步驟的執行最後會終止(terminate)
- 有效性(efficentiveness) : 演算法應能被實現
- 每個步驟即使人們拿筆跟紙算，也應在有限時間內可以被求出結果
- 像是求出根號2的準確值，不是一個演算法，因為它需要無窮的步驟去求出後面的小數
- 求出根號2的小數點第十位，即為演算法
- 輸出(O) : 演算法應有一個或以上的輸出
> 作業系統我們一般不視為演算法，因為作業系統需要不斷執行維持電腦的運作
> 但是有一個例外，那就是微軟的作業系統，因為它常常終止
> 阿不過他現在有進步，離演算法遠一點了[name=教授]

### 演算法的表示
- 一般我們使用以下方式表示演算法
- 自然語言
- 流程圖
- ==虛擬法(Psuedo code)==
- 自然語言與高階語言的結合
- EX : 歐幾里得輾轉相除法
- Psuedo code的規則
- 先給定這次題目的名稱
- 演算法(參數)
- ==一定要寫輸入與輸出==
- 用 ^ v 來表示且或
- while......do做迴圈動作
- ==用return做演算法的結束和輸出==

:::info
### 類神經網路(Artivicial Neural Network - ANN)

> $Neuron : y1 = b + \sum_{j=1}^nx_i*w_{ij}$
> 腦細胞在做這件事很輕鬆，因為對腦細胞sum只是化學物質的混和，腦細胞做這件是渾然天成的
> 

### 深度學習網路(Deep Neural Network - DNN)
> 將ANN加上更多的Hidden Layers
> 即為深度學習(DL)
> 
:::