計算理論

離散數學

布林邏輯

邏輯推論

計算理論

資訊理論

圖形理論

正規語言

相關書籍

應用數學

微積分

離散數學

線性代數

機率統計

訊息

相關網站

參考文獻

最新修改

簡體版

English

簡介

計算理論是研究「電腦有沒有可能計算、要計算多久」等問題的一門學問,其內容如下:

  1. 邏輯系統:布林邏輯 (Boolean Logic)、謂詞邏輯 (Predicate Logic)、一階邏輯 (First Order Logic)、哥德爾完備定律、哥德爾不完備定律。
  2. 電腦能力極限:圖靈機(Turing Machine)、停止問題 (Halting Problem)、可計算性問題。
  3. 演算法複雜度:Big O 複雜度,多項式複雜度,指數複雜度,NP-Complete。

內容

  1. 對角證法
  2. 實數的數量為不可數無限大
  3. 羅素悖論 — 理髮師悖論
    • 有一個理髮師,他宣稱要為所有不自己剪頭髮的人剪髮,但是不為任何自己剪髮的人剪髮。
  4. 停止問題:請寫一個程式判斷另一個程式會不會停。
  5. NP-Complete:加上 Oracle (神諭) 的電腦可以在多項式時間內解決的問題。
(1)
\begin{equation} O(1), O(n), O(n^2), O(n^3), ... , O(n^k) \end{equation}

課堂錄影:計算機數學 (計算理論)

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License