理論計算機科學
理論計算機科學（英語：Theoretical computer science，縮寫為TCS）是計算機科學的一個分支，它主要研究有關計算的相對更抽象化，邏輯化和數學化的問題，例如計算理論，算法分析，以及程序設計語言的語義。儘管理論計算機科學本身並非一個單獨的研究主題，從事這個領域的研究人員在電腦科學的研究者里自成一派。
定義和範圍
根據Elesevier出版社《理論電腦科學雜誌》（Theoretical Computer Science）的解釋[1]，理論電腦科學有着數學和抽象的本質，但動機來自實踐和日常中的計算問題。它旨在理解計算的本質，並根據這種理解提供更有效率的方法。
精確地限制定義理論計算機科學的範圍並非易事；根據計算機協會(ACM)算法與計算理論興趣組（SIGACT）的表述：[2]
| “ | 理論計算機科學的領域廣泛包含算法、數據結構、計算複雜性、分布式計算、並行計算、VLSI、機器學習、計算幾何、信息論、密碼學、量子計算、計算數論、符號計算、程序語義和形式化方法，自動機理論，以及隨機方面的研究。此領域的研究常需要強調嚴格的數學。 | ” |
計算機協會（ACM）《計算理論學報》（Transactions on Computation Theory）[3]又為以上的列表添加了：編碼理論，計算學習理論，以及與數據庫、信息獲取、經濟學模型和計算機網絡中與理論計算機科學相關的方面。
|
|
| |
| 數理邏輯 | 自動機理論 | 數論 | 圖論 |
|
P = NP ? | GNITIRW-TERCES | |
| 可計算性理論 | 計算複雜性理論 | 密碼學 | 類型理論 |
|
|
|
|
| 範疇論 | 計算幾何 | 組合優化 | 量子計算 |
歷史
儘管形式化算法已經存在了數千年，例如求最大公因數的歐幾里得算法至今依然在為人們所使用，但直到1936年，艾倫·圖靈，阿隆佐·邱奇和斯蒂芬·科爾·克萊尼才給出了算法在計算理論中的形式化定義。早在1703年之前就有了二進制和數理邏輯系統，萊布尼茨建立了真假二元的形式邏輯。1931年，哥德爾證明了哥德爾不完備定理，該定理指出，任何相容的形式體系不能用於證明它本身的相容性。
這些成果引領了理論計算機科學，包括現代數理邏輯和可計算性等的研究。1948年，信息論由香農將信息的傳遞作為一種統計現象而引入。同樣在1940年代，Donald Hebb建立了一套大腦學習模式的數學模型，神經網絡和平行分布式處理等學科也建立了起來。
隨着20世紀初量子力學的發展，數學運算的概念被引入了粒子波函數，可以同時計算多重狀態上的函數。這一概念引領了20世紀後半葉量子計算機概念的產生，在1990年代彼得·秀爾（Peter Shor）提出量子質因數分解算法，可以在多項式時間內分解大數，如果得以實現，現代的公開密鑰加密系統將變得不安全。
現代理論計算機科學研究在以上的基礎上展開，同時也包含了其它數學和跨學科的問題。
參考文獻
外部連結
- （英文） SIGACT （頁面存檔備份，存於網際網路檔案館）
- （英文） Usenet comp.theory 新聞組[永久失效連結]
參見
- 計算機科學
- 計算機協會（ACM）
- 歐洲理論計算機科學協會（European Association for Theoretical Computer Science）