理論計算機科学

理論計算機科学の最新ニュースをまとめて検索！

理論計算機科学（りろんけいさんきかがく、theoretical computer science）は計算機を理論的に研究する学問で、計算機科学の一分野である。計算機を数理モデル化して数学的に研究することを特徴としている。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、計算機はチューリング機械（もしくはそれと同等の概念）としてモデル化されている。

理論計算機科学の代表的な分野として以下のものがある。

• 計算理論：ある関数に対する計算の可能性や複雑性を追求する学問。
• ラムダ計算：計算機のモデルの一つであるラムダ計算を研究する学問。
• アルゴリズム論：ある関数に対する具体的な算法の考案、あるいは既存の算法の解析を行う学問。
• プログラム意味論: プログラムあるいはプログラミング言語の形式意味論

[編集] 範囲

正確な研究範囲を述べるのは容易ではないが、ACM の Special Interest Group on Algorithms and Computation Theory (SIGACT) は同グループの目的を理論計算機科学のプロモーションであるとしており、その対象範囲を次のように定義している。

• アルゴリズム
• データ構造
• 計算複雑性理論
• 分散コンピューティング
• 並列コンピューティング
• VLSI
• 機械学習
• 計算生物学
• 計算幾何学
• 情報理論
• 暗号理論
• 量子コンピュータ
• 計算数論
• 計算代数学
• プログラム意味論
• プログラムの形式的検証
• オートマトン理論
• 無作為性の研究

[編集] 外部リンク

• SIGACT home page
• SIGACT directory of additional theory links

この項目「理論計算機科学」は、自然科学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。