硬體#
算數上的限制
整數#
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 類別：可以在多項式時間內完成的演算法