# 計概：電腦運算的限制
## 硬體
算數上的限制
### 整數
32位元→ $-2^{31}$ ~ $2^{31}-1$

### 實數
- 精確度：可以被表示的有效位數的最大數值。

假設一個精確度為4位元，第五個位元表示指數，如：

+  +  9 1 2 3 4 為 1234 * 10^9，-  -  3 1 4 4 6 為 -1446 * 10^-3
↑  ↑  ↑
數 指 指
字 數 數
的 的 值

### 表示錯誤（捨去錯誤）
- 下溢位 underflow：表示為0。

$$
\begin{equation}\begin{split}
4412 & \times 10^{-9}\\\\
\times \ 1000 & \times 10^{-8}\\\\
= 4412000 & \times 10^{-17}\\\\
= 4412 & \times 10^{-14}\\\\
\end{split}\end{equation}
$$

>太小了無法表示

- 上溢位 overflow：以最大值表示

$$
\begin{equation}\begin{split}
4412 & \times 10^9\\\\
\times \ 1000 & \times 10^8\\\\
= 4412000 & \times 10^{17}\\\\
= 4412 & \times 10^{20}\\\\
\end{split}\end{equation}
$$

>太大了無法表示
表示為 $9999 \times 10^9$

- 相消錯誤

$$
\begin{equation}\begin{split}
1 + 0.00001234 - 1 & = 0.00001234\\\\
100000000 \times 10^{-8}&+\ 1234 \times 10^{-8}\\\\
= 100001234 \times 10^{-8} &\to 1000 \times 10^{-3}\\\\\\\\
1000 \times 10^{-3} - 1000 &\times 10^{-3}=0\\\\
\end{split}\end{equation}
$$

### 溝通的限制
#### 錯誤偵查編碼、錯誤修正編碼
- 同位元：用一個額外的位元來確保一個位元組的1的個數為基或偶數。
- 奇同位：如10001100，此時同位元為0，10111101，此時同位元為1。
- 偶同位
- 檢查位元：將所有位數加起來，存取總和的個位數，如 34376 總和為 23 ，儲存：34376-3。

---
## 軟體
### 軟體的複雜性
### 軟體工程
解決問題的步驟新增兩項，軟體需求、規格。

---
## 問題
### Big-O 分析

$$f(N) = N^4 + N^2 - 1 \to O(N^4)$$

- $O(1)$ 界線時間：如指定一個直到一個長度為N的陣列中的第i項。
- $O(logN)$ 對數時間：如二元搜尋法 BST。
- $O(N)$ 線性時間：如印出N筆資料。
- $O(NlogN)$：如快速搜尋法。
- $O(N^2)$：如簡單排序法。
- $O(2^N)$ 指數時間
- $O(N!)$ 階層時間

### 杜林機器（圖靈機器）
- 讀取紙帶上一個儲存格的符號
- 將一個符號寫入儲存格
- 向左/右移一格，或不動

任何具有可計算性的東西都可以藉由杜林機器來運算

### 演算法分類
- 多項式演算法 P 類別
- NP 類別：可以在多項式時間內完成的演算法

###### tags: `計算機概論`