理論計算機科学のソースを表示

'''理論計算機科学'''（りろんけいさんきかがく、[[英語]]：theoretical computer science）または'''理論コンピュータ科学'''は、[[計算]]の理論的基礎を研究する[[学問]]で、[[計算機科学]]の一分野である。計算を[[数理モデル]]化して[[数学]]的に研究することを特徴としている<ref>Hartmanis, A. C. D. H. J., Henzinger, T., Leighton, J. H. N. J. T., & Nivat, M. (2006). Texts in Theoretical Computer Science An EATCS Series.</ref><ref>Hartmanis, A. C. D. H. J., Henzinger, T., Leighton, J. H. N. J. T., & Nivat, M. (2006). Monographs in Theoretical Computer Science An EATCS Series.</ref><ref>Hartmanis, J. (1981). Observations about the development of theoretical computer science. Annals of the History of Computing, 3(1), 42-51.</ref>。「数学的」という言葉は広義には[[公理]]的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、[[チューリングマシン]]などの[[計算モデル]]を扱う。

この分野のテーマの例を以下に挙げる（特に意図や理由のある選出ではない）。
*[[計算理論]]：ある[[サブルーチン|関数]]に対する計算の可能性や[[複雑性]]を追求する学問。
*[[ラムダ計算]]：計算機のモデルの一つであるラムダ計算を研究する学問。
*[[アルゴリズム論]]：ある関数に対する具体的な[[アルゴリズム|算法]]の考案、あるいは既存の算法の解析を行う学問。
*[[プログラム意味論]]: [[プログラム (コンピュータ)|プログラム]]あるいは[[プログラミング言語]]の[[形式意味論]]<ref>横内寛文. (1994). プログラム意味論. 共立出版.</ref>

== 範囲 ==
正確な研究範囲を述べるのは容易ではないが、[[Association for Computing Machinery|ACM]] の {{仮リンク|ACM SIGACT|en|ACM SIGACT|label=Special Interest Group on Algorithms and Computation Theory}} (SIGACT) は同グループの目的を理論計算機科学の振興であるとしており、その対象範囲を次のように定義している<ref>{{Cite web
|title =  SIGACT
|url = http://sigact.acm.org
|accessdate = 2013-07-13
}}</ref>。

{{Quote|[[アルゴリズム]]、[[データ構造]]、[[計算複雑性理論]]、[[並列計算]]、[[分散コンピューティング|分散計算]]、probabilistic computation、[[量子コンピュータ|量子計算]]、[[オートマトン]]理論、[[情報理論]]、[[暗号理論]]、[[プログラム意味論]]と[[形式的検証|検証]]、[[機械学習]]、[[計算生物学]]、computational economics、[[計算幾何学]]、computational number theory and algebra。}}
ACMの学術誌 Transactions on Computation Theory ではこの一覧にさらに[[符号理論]]と{{仮リンク|計算論的学習理論|en|computational learning theory}}を加え、[[データベース]]、[[情報検索]]、[[経済モデル]]、[[コンピュータネットワーク|ネットワーク]]などの理論計算機科学的側面をも含めている<ref>{{Cite web
|title =  ToCT
|url = http://toct.acm.org/journal.html
|accessdate = 2010-06-09
}}</ref>。このように範囲は広いが、計算機科学の理論畑の人間は応用畑とは違うという意識を持っていることがあり、「[[コンピューティング]]を支えている（より基本的な）科学」を研究しているという意識をもっていることがある<ref>{{Cite web
|title = Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing
|url = http://www.research.att.com/%7Edsj/nsflist.html#Intro
|accessdate = 2009-03-29
}}</ref>。これは必ずしも対立を意味するものではなく、むしろ協力関係にあることを意味する。
{|style="border:1px solid #ddd;text-align:center;margin:0 auto" cellspacing="15"
|<math>P\rightarrow Q</math>
|[[画像:DFAexample.svg|96px]]
|[[画像:Elliptic curve simple.png|96px]]
|[[画像:6n-graf.svg|96px]]
|-
|[[数理論理学]]
|[[オートマトン]]
|[[数論]]
|[[グラフ理論]]
|-
|<math>\Gamma \vdash x:Int</math>
|[[画像:Commutative diagram for morphism.svg|96px]]
|[[画像:SimplexRangeSearching.png|96px]]
|[[画像:Blochsphere.svg|96px]]
|-
|[[型理論]]
|[[圏論]]
|[[計算幾何学]]
|[[量子コンピュータ|量子計算]]
|}

== 歴史 ==
アルゴリズムは何千年も前から存在していたが（例えば、2つの数の[[最大公約数]]を求める[[ユークリッドの互除法]]は今も使われている<ref>森井昌克, & 笠原正雄. (1992). ユークリッド互除法に基づく狭義 2 元 BCH 符号の復号について. 電子情報通信学会論文誌 A, 75(1), 144-147.</ref><ref>堀口敏男. (1995). ユークリッド復号法を用いたリードソロモン符号の BCH 限界以上の復号. 電子情報通信学会論文誌 A, 78(5), 626-638.</ref>）、計算におけるアルゴリズムの定義を定式化したのは[[アラン・チューリング]]、[[アロンゾ・チャーチ]]、[[スティーヴン・コール・クリーネ|スティーヴン・クリーネ]]で、[[1938年]]のことである。一方、[[二進法]]と数学の[[形式体系]]はそれ以前からあり、[[ゴットフリート・ライプニッツ]]が17世紀に二進法を数学的に定式化し、19世紀に[[ジョージ・ブール]]が[[ブール論理]]/[[ブール代数]]を定式化した。<ref>Goodstein, R. L. (2007). Boolean algebra. Courier Corporation.</ref>論理的推論と数学的証明は古代から存在したが、[[1931年]][[クルト・ゲーデル]]は自身の[[ゲーデルの不完全性定理|不完全性定理]]で、公理体系には証明できない限界が存在することを証明した。<ref>Berto, F. (2011). There's something about Gödel: the complete guide to the incompleteness theorem. John Wiley & Sons.</ref><ref>Smullyan, R. M. (1992). Gödel's incompleteness theorems. Oxford University Press on Demand.</ref><ref>不完全性定理 / 菊池誠 著 | [[共立出版]]</ref>

それらの発展が[[論理学]]や[[計算可能性]]の現代的研究をもたらし、全体として理論計算機科学という分野を生み出した。[[1948年]]、[[クロード・シャノン]]による『[[通信の数学的理論]]』から生まれた[[情報理論]]がこれに加わった。<ref>Shanon, C. (1948). A mathematical theory of communication. Bell System Technical Journal, 27, 379-623.</ref><ref>Guizzo, E. M. (2003). The essential message: Claude Shannon and the making of information theory (Doctoral dissertation, Massachusetts Institute of Technology).</ref><ref>Gappmair, W. (1999). Claude E. Shannon: The 50th anniversary of information theory. IEEE Communications Magazine, 37(4), 102-105.</ref>同じ頃[[ドナルド・ヘッブ]]が脳における学習の[[ヘッブの法則|数学的モデル]]を導入した。生物学的データがこの仮説を裏付けつつ、若干の修正が行われていき、[[ニューラルネットワーク]]と[[コネクショニズム|並行分散処理]]が確立された。

20世紀初頭から始まった[[量子力学]]の発展により、量子の[[波動関数]]上で演算が可能ではないかという概念が生まれた。これはすなわち、複数の状態を同時並行的に計算できることを意味する。そこから20世紀後半に[[量子コンピュータ]]の概念が生まれ、[[1990年代]]には[[ピーター・ショア]]が量子コンピュータを使えば素因数分解を[[多項式時間]]で解けることを示し、もし（数千万量子ビットを量子的に扱える量子コンピュータが）実現すれば[[公開鍵暗号]]システムも安全ではなくなることを示した。<ref>Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). [[IEEE]].</ref><ref>Shor, P. W. (2002, May). Introduction to quantum algorithms. In Proceedings of Symposia in Applied Mathematics (Vol. 58, pp. 143-160).</ref><ref>Rieffel, E., & Polak, W. (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR), 32(3), 300-335.</ref><ref>Pittenger, A. O. (2012). An introduction to quantum computing algorithms (Vol. 19). Springer Science & Business Media.</ref>

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

== 組織 ==
*{{仮リンク|ヨーロッパ理論計算機科学会|en|European Association for Theoretical Computer Science}}
*[[Association for Computing Machinery|ACM]] {{仮リンク|ACM SIGACT|en|ACM SIGACT|label=SIGACT}}

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist|2}}

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

== 関連項目 ==
*[[形式科学]]
*[[計算機科学の未解決問題]]
*[[科学理論]]

== 外部リンク ==
{{ウィキプロジェクトリンク|数学|[[画像:Nuvola apps edu mathematics blue-p.svg|34px|Project:数学]]}}
{{ウィキポータルリンク|数学|[[画像:Nuvola apps edu mathematics-p.svg|34px|Portal:数学]]}}
*[http://www.sigact.org/webpages.php SIGACT directory of additional theory links]
*[http://theorymatters.org/ Theory Matters Wiki] Theoretical Computer Science (TCS) Advocacy Wiki
*[news://comp.theory Usenet comp.theory]
*[http://www.confsearch.org/confsearch/faces/pages/topic.jsp?topic=Theory&sortMode=1&graphicView=1 理論計算機科学分野の学会一覧] at [http://www.confsearch.org confsearch]
*[http://cstheory.stackexchange.com/ Theoretical Computer Science - StackExchange] - 理論計算機科学分野の研究者間のQ&Aサイト
*[http://www.csanimated.com/browse.php Computer Science Animated]（音声つき）
*[http://theory.csail.mit.edu/ Theory of Computation] [[MITコンピュータ科学・人工知能研究所]]

{{Sci-stub}}
{{authority control}}
{{DEFAULTSORT:りろんけいさんきかかく}}
[[Category:理論計算機科学|*りろんけいさんきかかく]]
[[Category:形式科学]]
[[Category:数学に関する記事]]