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

演算法設計與分析 Algorithm Design & Analysis Process

Alvin Tseng The study group starts here.

Design Step
1. Formulate a problem 提出一個問題
2. Develop an algorithm 開發一個演算法

• 只要會寫程式，在寫程式，都是屬於設計部分，也是大家熟悉的部分。

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 (反證法)
反證法最快的方式就是直接假定演算法是錯誤的

關於反證法，記得去看上課影片，老師講解得很好
投影片 page 16

3.1. Hardness of The Champion Problem

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

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

---

THE END

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

Key Words

Algorithm 演算法
Computation Model 計算模型