計概 - 電腦運算的限制

計算機概論 2018-02-13 613

硬體#

算數上的限制

整數#

32位元→ $-2^{31}$ ~ $2^{31}-1$

實數#

  • 精確度:可以被表示的有效位數的最大數值。

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

+  +  9 1 2 3 41234 * 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 類別:可以在多項式時間內完成的演算法