(Translated by https://www.hiragana.jp/)
理論計算機科学 - Wikipedia コンテンツにスキップ

理論りろん計算けいさん機き科学かがく

出典しゅってん: フリー百科ひゃっか事典じてん『ウィキペディア（Wikipedia）』

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

この分野ぶんやのテーマの例れいを以下いかに挙あげる（特とくに意図いとや理由りゆうのある選出せんしゅつではない）。

範囲はんい

[編集へんしゅう]

正確せいかくな研究けんきゅう範囲はんいを述のべるのは容易よういではないが、ACM の Special Interest Group on Algorithms and Computation Theory（英語えいご版ばん） (SIGACT) は同どうグループの目的もくてきを理論りろん計算けいさん機き科学かがくの振興しんこうであるとしており、その対象たいしょう範囲はんいを次つぎのように定義ていぎしている[5]。

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

数理すうり論ろん理学りがく オートマトン 数かず論ろん グラフ理論りろん
型かた理論りろん 圏けん論ろん 計算けいさん幾何きか学がく 量子りょうし計算けいさん

歴史れきし

[編集へんしゅう]

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

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

20世紀せいき初頭しょとうから始はじまった量子力学りょうしりきがくの発展はってんにより、量子りょうしの波動はどう関数かんすう上うえで演算えんざんが可能かのうではないかという概念がいねんが生うまれた。これはすなわち、複数ふくすうの状態じょうたいを同時どうじ並行へいこう的てきに計算けいさんできることを意味いみする。そこから20世紀せいき後半こうはんに量子りょうしコンピュータの概念がいねんが生うまれ、1990年代ねんだいにはピーター・ショアが量子りょうしコンピュータを使つかえば素因数そいんすう分解ぶんかいを多項式たこうしき時間じかんで解とけることを示しめし、もし（数すう千せん万まん量子りょうしビットを量子りょうし的てきに扱あつかえる量子りょうしコンピュータが）実現じつげんすれば公開こうかい鍵かぎ暗号あんごうシステムも安全あんぜんではなくなることを示しめした。[17][18][19][20]

理論りろん計算けいさん機き科学かがくの研究けんきゅうはこれらを基盤きばんとしているが、他ほかにも多おおくの数学すうがく問題もんだいや学際がくさい的てき問題もんだいを扱あつかっている。

組織そしき

[編集へんしゅう]

脚注きゃくちゅう

[編集へんしゅう]
[脚注きゃくちゅうの使つかい方かた]
  1. ^ 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.
  2. ^ 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.
  3. ^ Hartmanis, J. (1981). Observations about the development of theoretical computer science. Annals of the History of Computing, 3(1), 42-51.
  4. ^ 横内よこうち寛文ひろふみ. (1994). プログラム意味いみ論ろん. 共立きょうりつ出版しゅっぱん.
  5. ^ “SIGACT”. 2013年ねん7月がつ13日にち閲覧えつらん。
  6. ^ “ToCT”. 2010年ねん6月がつ9日にち閲覧えつらん。
  7. ^ “Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing”. 2009年ねん3月がつ29日にち閲覧えつらん。
  8. ^ 森井もりい昌克まさよし, & 笠原かさはら正雄まさお. (1992). ユークリッド互除法ほうに基もとづく狭義きょうぎ 2 元げん BCH 符号ふごうの復号ふくごうについて. 電子でんし情報じょうほう通信つうしん学会がっかい論文ろんぶん誌し A, 75(1), 144-147.
  9. ^ 堀口ほりぐち敏男としお. (1995). ユークリッド復号ふくごう法ほうを用もちいたリードソロモン符号ふごうの BCH 限界げんかい以上いじょうの復号ふくごう. 電子でんし情報じょうほう通信つうしん学会がっかい論文ろんぶん誌し A, 78(5), 626-638.
  10. ^ Goodstein, R. L. (2007). Boolean algebra. Courier Corporation.
  11. ^ Berto, F. (2011). There's something about Gödel: the complete guide to the incompleteness theorem. John Wiley & Sons.
  12. ^ Smullyan, R. M. (1992). Gödel's incompleteness theorems. Oxford University Press on Demand.
  13. ^ 不完全性ふかんぜんせい定理ていり / 菊池きくち誠まこと 著ちょ | 共立きょうりつ出版しゅっぱん
  14. ^ Shanon, C. (1948). A mathematical theory of communication. Bell System Technical Journal, 27, 379-623.
  15. ^ Guizzo, E. M. (2003). The essential message: Claude Shannon and the making of information theory (Doctoral dissertation, Massachusetts Institute of Technology).
  16. ^ Gappmair, W. (1999). Claude E. Shannon: The 50th anniversary of information theory. IEEE Communications Magazine, 37(4), 102-105.
  17. ^ 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.
  18. ^ Shor, P. W. (2002, May). Introduction to quantum algorithms. In Proceedings of Symposia in Applied Mathematics (Vol. 58, pp. 143-160).
  19. ^ Rieffel, E., & Polak, W. (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR), 32(3), 300-335.
  20. ^ Pittenger, A. O. (2012). An introduction to quantum computing algorithms (Vol. 19). Springer Science & Business Media.

参考さんこう文献ぶんけん

[編集へんしゅう]

関連かんれん項目こうもく

[編集へんしゅう]

外部がいぶリンク

[編集へんしゅう]
Project:数学
プロジェクト 数学すうがく
Portal:数学
ポータル 数学すうがく
スタブアイコン

この項目こうもくは、自然しぜん科学かがくに関連かんれんした書かきかけの項目こうもくです。この項目こうもくを加筆かひつ・訂正ていせいなどしてくださる協力きょうりょく者しゃを求もとめています（Portal:自然しぜん科学かがく）。

「https://ja.wikipedia.org/w/index.php?title=理論りろん計算けいさん機き科学かがく&oldid=94566773」から取得しゅとく