###### tags: `ADA 1.1` `Introduction`

# ADA 1.1 Introduction

### Why we care?

> 算力不是免費的。

本課程作業速度不到標準，也會被退件。

## 名詞定義 Definition

### 1. Problem 問題

> *會有明確的**Input**與**Output***

Ex. 冠軍問題
在n個數中，找到最大的那一個。

### 2. Problem Instance 個例

> *在問題中的其中一個例子*

Ex. 冠軍問題
今天有5個整數，分別為7, 4, 2, 9, 8

|  7  |  4  |  2  |  9  |  8  |
| A[1]| A[2]| A[3]| A[4]| A[5]|
|     |     |     | max |     |

答案為a[4]

### 3. Computation Model 計算模型

> 可以類比為，*問題的**規則(rule)***
Each problem must have its rule (遊戲規則)
Computation model(計算模型) = rule(遊戲規則)
The problems with different rules have different hardness levels.
同一個問題可以有不同的規則(rule)，而得到不同的難度。

### 4. Hardness 難易程度
How difficule to solve a problem.
> *要解決這個問題有多難*
To understand how difficult to solve a problem, after understanding how to solve a problem.
這是一個抽象的答案，因為你又該如何定義解決。

---

#### 4-1. Problem Solving 解題

怎樣算是“解決”一個問題？
> *就是給他一個 **演算法** ，讓任何 **個例(instance)** 都輸出正確的結果。*

`corner case (困難的，特別的，個例)`

#### 4-2. Algorithm 演算法

> *解決問題的 **方法**，並且把指令一步一步地寫下來*

`- 只要能夠清楚的表達出一步一步的指令，都可以叫演算法，Ex. 食譜`
`- 並不限於code or pseudo code or word`
`- 步驟要詳細，不是概略的敘述`
`- 用什麼語言是不用在意的`
`- 作業因為要比較執行速度，所以助教才會規定要用C/C++`

---
##### Solve
If an algorithm produces a correct output for any instance of the priblem
-> this algotithm "solves" the problem.

##### Hardness
How much effort the best algorithm needs to solve any problem instance.

把難度想像成防禦力，把演算法想像成攻擊力。

[to Top](#名詞定義-Definition)

## 演算法設計與分析 Algorithm Design & Analysis Process
> [name=Alvin Tseng] The study group starts here.
:::info
**Design Step**
1\. Formulate a problem 提出一個問題
2\. Develop an algorithm 開發一個演算法
- 只要會寫程式，在寫程式，都是屬於設計部分，也是大家熟悉的部分。
:::

:::info
**Analysis Step (IMPORTANT！！！！)**
3. Prove the correctness 證明他是正確的
4. Analyze running time/space requirement 分析運算需要的時間空間

- 這才是這堂課最重要的目的，因為程式大家會寫。
但要證明自己寫的好，是最不容易的事情。
:::

### 1. Problem Formaulation

要非常詳細的定義，Input and Output

### 2. Algoruthm Design

如同前面提到的，難度與規則(comparison-based)有關，所以在設計時必須確立規則

# ex. 冠軍問題
# rule.1: 不能一次看到全部數值。
# rule.2: 要請別人比大小


# Algorithm: 擂台法
var i: int = 2
var j: int = 1

for (i=2;i<=n;i++)
  if (A[i] > A[j])
    j = i;
return j;

# Q1: 有沒有符合規則?
# Q2: 有沒有合於所有個例?

### 3. Correctness of the Algorithm

Prove by contradiction (反證法)
反證法最快的方式就是直接假定演算法是錯誤的
:::info
關於反證法，記得去看上課影片，老師講解得很好
投影片 page 16
:::

#### 3.1. Hardness of The Champion Problem

Effort: 定義成花多少次數去做 *比較* ，當作評估方式

:::info
ex. 冠軍問題
使用擂台法，會比較 n-1 次比較
:::

所以使用擂台法，會有n-1次的比較，但是否存在另外一種演算法，可以有 n-2次的比較呢？

Ａ：答案是不可能的。

原因是什麼呢？

因為有n個人，但只比較 n-2次，等於永遠還是有兩個人是沒有比過輸贏的。

假設有五個數字
1️⃣ 3️⃣ 2️⃣ 4️⃣ 6️⃣
比較 n-2 次是什麼意思？ n-2(5-2 = 3)
總共有五個數字，所以我比較3次，有可能找到答案嗎？
first time:
1️⃣ vs 3️⃣,3️⃣比較大， 留下3️⃣
second time:
2️⃣ vs 3️⃣, 3️⃣比較大，留下3️⃣
third time:
3️⃣ vs 4️⃣, 4️⃣ 比較大，留下4️⃣
Answer: 這五個數字中，4️⃣ 是最大的，但事實上最大的數字是6️⃣。所以 n-2 是不可能的。
所以最理想的演算法效率是 n-1

---

##### 3.1.1 Finding Hardness

找到一個演算法的最優次數，稱為 Upper bound
證明一個問題的最優次數，稱為 Lower bound
當兩個數值吻合的時候，該數值就可以稱作是問題的難度。

但Lower bound是很難證明的，所以演算法的研究者，主要的工作就是，找到這個問題的難度。

> **hardness of the problem** <~ 研究者一生追尋的目標

---

所以找不到Lower bound 是很正常的。

但一切的目標為，找到最低的Upper bound和最高的Lower bound。

### 4. Algorithm Analysis

time vs space
時間 跟 空間 的對抗

if (upper_bound == lower_bound) 
  is optimal algorithm

[to Top](#演算法設計與分析-Algorithm-Design-amp-Analysis-Process)

---
THE END

> Andy心得：
> 找尋最高的Lower bound，就像是我們以為沒有問題的程式，
> 在進入市場後，永遠存在Bug，總是有我們沒有想過的情境存在。
> 是一生追逐的目標。

## Key Words
Algorithm 演算法
Computation Model 計算模型