理論計算機科學

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

定義和範圍

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

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

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

       
數理邏輯 自動機理論 數論 圖論
  P = NP ? GNITIRW-TERCES  
可計算性理論 計算複雜性理論 密碼學 類型理論
       
範疇論 計算幾何 組合優化 量子計算

歷史

儘管形式化算法已經存在了數千年,例如求最大公因數歐幾里得算法至今依然在為人們所使用,但直到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). 

外部連結

參見