理論計算機科学

提供: miniwiki
移動先:案内、検索

理論計算機科学（りろんけいさんきかがく、英語：theoretical computer science）は計算機を理論的に研究する学問で、計算機科学の一分野である。計算機を数理モデル化して数学的に研究することを特徴としている。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、現実のコンピュータを扱うことも多いが、チューリングマシンなどの計算モデルを扱うことも多い。

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

範囲

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

アルゴリズム、データ構造、計算複雑性理論、並列計算、分散計算、probabilistic computation、量子計算、オートマトン理論、情報理論、暗号理論、プログラム意味論と検証、機械学習、計算生物学、computational economics、計算幾何学、computational number theory and algebra。

ACMの学術誌 Transactions on Computation Theory ではこの一覧にさらに符号理論と計算論的学習理論（English版）を加え、データベース、情報検索、経済モデル、ネットワークなどの理論計算機科学的側面をも含めている[2]。このように範囲は広いが、計算機科学の理論畑の人間は応用畑とは違うという意識を持っていることがあり、「コンピューティングを支えている（より基本的な）科学」を研究しているという意識をもっていることがある[3]。これは必ずしも対立を意味するものではなく、むしろ協力関係にあることを意味する。

[math]P\rightarrow Q[/math] 96px 96px 96px
数理論理学 オートマトン 数論 グラフ理論
[math]\Gamma \vdash x:Int[/math] 96px 96px 96px
型理論 圏論 計算幾何学 量子計算

歴史

アルゴリズムは何千年も前から存在していたが（例えば、2つの数の最大公約数を求めるユークリッドの互除法は今も使われている）、計算におけるアルゴリズムの定義を定式化したのはアラン・チューリング、アロンゾ・チャーチ、スティーヴン・クリーネで、1938年のことである。一方、二進法と数学の形式体系はそれ以前からあり、ゴットフリート・ライプニッツが17世紀に二進法を数学的に定式化し、19世紀にジョージ・ブールがブール論理/ブール代数を定式化した。論理的推論と数学的証明は古代から存在したが、1931年クルト・ゲーデルは自身の不完全性定理で、公理体系には証明できない限界が存在することを証明した。

それらの発展が論理学や計算可能性の現代的研究をもたらし、全体として理論計算機科学という分野を生み出した。1948年、クロード・シャノンによる『通信の数学的理論』から生まれた情報理論がこれに加わった。同じ頃ドナルド・ヘッブが脳における学習の数学的モデルを導入した。生物学的データがこの仮説を裏付けつつ、若干の修正が行われていき、ニューラルネットワークと並行分散処理が確立された。

20世紀初頭から始まった量子力学の発展により、量子の波動関数上で演算が可能ではないかという概念が生まれた。これはすなわち、複数の状態を同時並行的に計算できることを意味する。そこから20世紀後半に量子コンピュータの概念が生まれ、1990年代にはピーター・ショアが量子コンピュータを使えば素因数分解を多項式時間で解けることを示し、もし実現すれば公開鍵暗号システムも安全ではなくなることを示した。

理論計算機科学の研究はこれらを基盤としているが、他にも多くの数学問題や学際的問題を扱っている。

組織

脚注

  1. ↑ “SIGACT”. . 2013閲覧.
  2. ↑ “ToCT”. . 2010閲覧.
  3. ↑ “Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing”. . 2009閲覧.

参考文献

  • Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0122063821. - 計算理論を中心にプログラム意味論なども扱っている。

関連項目

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=理論計算機科学&oldid=115866」から取得