理論計算機科學
理論計算機科學(英語: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)