理論計算機科學

理論計算機科學（英語：Theoretical computer science，縮寫為TCS）是計算機科學的一個分支，它主要研究有關計算的相對更抽象化，邏輯化和數學化的問題，例如計算理論，算法分析，以及程式語言的語義。儘管理論計算機科學本身並非一個單獨的研究主題，從事這個領域的研究人員在電腦科學的研究者里自成一派。

定義和範圍

根據Elesevier出版社《理論電腦科學雜誌》（Theoretical Computer Science）的解釋^[1]，理論電腦科學有着數學和抽象的本質，但動機來自實踐和日常中的計算問題。它旨在理解計算的本質，並根據這種理解提供更有效率的方法。

精確地限制定義理論計算機科學的範圍並非易事；根據計算機協會(ACM)算法與計算理論興趣組（SIGACT）的表述：^[2]

“

理論計算機科學的領域廣泛包含算法、數據結構、計算複雜性、分佈式計算、並行計算、VLSI、機器學習、計算幾何、信息論、密碼學、量子計算、計算數論、符號計算、程序語義和形式化方法，自動機理論，以及隨機方面的研究。此領域的研究常需要強調嚴格的數學。

”

計算機協會（ACM）《計算理論學報》（Transactions on Computation Theory）^[3]又為以上的列表添加了：編碼理論，計算學習理論，以及與數據庫、信息獲取、經濟學模型和計算機網絡中與理論計算機科學相關的方面。

$P\rightarrow Q\,$
數理邏輯	自動機理論	數論	圖論
	P = NP ?	GNITIRW-TERCES	$\Gamma \vdash x:Int$
可計算性理論	計算複雜性理論	密碼學	類型理論

範疇論	計算幾何	組合優化	量子計算

歷史

儘管形式化算法已經存在了數千年，例如求最大公因數的歐幾里得算法至今依然在為人們所使用，但直到1936年，艾倫·圖靈，阿隆佐·邱奇和斯蒂芬·科爾·克萊尼才給出了算法在計算理論中的形式化定義。早在1703年之前就有了二進制和數理邏輯系統，萊布尼茨建立了真假二元的形式邏輯。1931年，哥德爾證明了哥德爾不完備定理，該定理指出，任何相容的形式體系不能用於證明它本身的相容性。

這些成果引領了理論計算機科學，包括現代數理邏輯和可計算性等的研究。1948年，信息論由香農將信息的傳遞作為一種統計現象而引入。同樣在1940年代，Donald Hebb建立了一套大腦學習模式的數學模型，神經網絡和平行分佈式處理等學科也建立了起來。

隨着20世紀初量子力學的發展，數學運算的概念被引入了粒子波函數，可以同時計算多重狀態上的函數。這一概念引領了20世紀後半葉量子計算機概念的產生，在1990年代彼得·秀爾（Peter Shor）提出量子質因數分解算法，可以在多項式時間內分解大數，如果得以實現，現代的公開密鑰加密系統將變得不安全。

現代理論計算機科學研究在以上的基礎上展開，同時也包含了其它數學和跨學科的問題。

參考文獻

[1]
Theoretical Computer Science， Elsevier Journal. [2010-07-28]. （原始內容存檔於2011-10-29）.
[2]
SIGACT. [2010-07-27]. （原始內容存檔於2010-03-12）.
[3]
ToCT. [2010-07-27]. （原始內容存檔於2010-11-04）.

外部連結

（英文） SIGACT （頁面存檔備份，存於互聯網檔案館）
（英文） Usenet comp.theory 新聞組^{[永久失效連結]}

參見

計算機科學
計算機協會（ACM）
歐洲理論計算機科學協會（European Association for Theoretical Computer Science）

[elsevier-1] [1]
Theoretical Computer Science， Elsevier Journal. [2010-07-28]. （原始內容存檔於2011-10-29）.

[2] [2]
SIGACT. [2010-07-27]. （原始內容存檔於2010-03-12）.

[3] [3]
ToCT. [2010-07-27]. （原始內容存檔於2010-11-04）.

[1]

[2]

[3]