Theory of computation

ウィキペディア

計算理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/10 07:42 UTC 版)

計算理論（けいさんりろん、Theory Of Computation）または計算論は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算（Computation）とは、数学的に表現できる、あらゆる種類の情報処理のこと。

計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る^[1]。

計算可能性理論

詳細は「計算可能性理論」を参照

計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における、ある意味で最も重要な成果である。定式化しやすく、かつチューリングマシンで解けない問題の具体例であり、数学基礎論との関係もある。同時に、静的に無限ループの検出を確実に行う方法は無いことを示している、といったように実応用的な意義もある。

計算複雑性理論

詳細は「計算複雑性理論」を参照

計算複雑性理論は、問題がコンピュータで解けるかどうかだけでなく、その問題の困難さを扱う。時間計算量と空間計算量という2つの観点がある。時間計算量とは計算にかかるステップ数、空間計算量は計算に必要とされるメモリ量に相当する。

あるアルゴリズムが必要とする時間と空間を分析するため、時間や空間を問題の入力量の関数として表現する。例えば、長い数列から特定の数を見つけ出すという問題は、数列が長くなればなるほど難しくなる。数列に ${\displaystyle n}$ 概要（英語版）

カテゴリ

ブック

コモンズ

表 話 編 歴 数学
主要分野	数理論理学 集合論 圏論 代数学 初等 線型 多重線型 抽象 算術/数論 解析学/微分積分学 関数解析学 行列解析 幾何学 代数 微分 有限 離散 位相 代数的位相 表現論 リー理論（英語版） 微分方程式 線型微分方程式 複素微分方程式 常微分方程式 偏微分方程式 積分微分方程式 力学系 組合せ数学 数理物理学 ゲーム理論 グラフ理論 最適化問題 数理最適化 計算理論 確率論 数理統計学（英語版） 制御理論 三角法
トピックス	数学史 和算 算道 数理哲学 美 未解決問題 算数・数学教育 算数 教科
賞	ボッチャー記念賞 コール賞 フィールズ賞 ヴェブレン賞 サレム賞 スティール賞 ウルフ賞 クラフォード賞 クレイ研究賞 ガウス賞 アーベル賞 ラマヌジャン賞 SASTRAラマヌジャン賞 チャーン賞 数学ブレイクスルー賞
応用	情報理論 折紙の数学 囲碁と数学 数値解析 精度保証付き数値計算 計算機援用証明 数値線形代数 常微分方程式の数値解法 偏微分方程式の数値解法
学会・団体	国際数学者会議 国際数学連合 国際産業数理・応用数理会議 国際産業数理・応用数理評議会（英語版） アメリカ数学会 SIAM ヨーロッパ数学会 ロンドン数学会 日本応用数理学会 日本数学会 数学教育協議会
競技	国際数学オリンピック 日本数学オリンピック 日本ジュニア数学オリンピック 広中杯 近畿大学数学コンテスト 人の最大の力を競う算数・数学の大会
研究所	京都大学数理解析研究所 統計数理研究所 アンリ・ポアンカレ研究所 オーバーヴォルファッハ数学研究所 クレイ研究所 CIMAT数学研究センター ステクロフ数学研究所
一覧 数学定数 数 関数 図形 数学記号 数学者 エポニム カテゴリ ポータル