理論計算機科学

アルゴリズムとは、計算を行うための段階的な手順のことです。アルゴリズムは、計算、データ処理、自動推論などに用いられます。

アルゴリズムとは、関数を計算するための明確に定義された命令の有限リスト^{[ 3 ]}として表現される効果的な方法である^{[ 4 ]}。^{[ 5 ]} 初期状態と初期入力（おそらく空）から開始して^{[ 6 ]} 、命令は、実行されると有限個の明確に定義された連続状態を経て^、最終的に「出力」^{[ 8 ]}を生成し、最終終了状態に達する計算を記述する。^ある状態から次の状態への遷移は必ずしも決定論的ではなく、ランダム化アルゴリズムと呼ばれる一部のアルゴリズムはランダムな入力を取り入れている^{[ 9 ] 。}

オートマタ理論とは、抽象機械やオートマタ、そしてそれらを用いて解決できる計算問題を研究する学問です。これは理論計算機科学における理論の一つであり、離散数学（数学および計算機科学の一分野）に属します。オートマタという言葉は、ギリシャ語の「αὐτόματα」（自己作用）に由来します。

オートマトン理論とは、計算の中間段階の有無にかかわらず（または任意の関数／プロセスがある場合でも） 、入力および出力プロセスの論理的な理解を助けるために、自己動作する仮想マシンを研究する学問である。

符号理論とは、符号の特性と特定の用途への適合性を研究する学問です。符号は、データ圧縮、暗号化、誤り訂正、そして近年ではネットワーク符号化にも用いられています。符号は、情報理論、電気工学、 数学、コンピュータ科学など、さまざまな科学分野で研究されており、効率的で信頼性の高いデータ伝送方法を設計することを目的としています。これには通常、冗長性の除去と、伝送データの誤りの訂正（または検出）が含まれます。

計算複雑性理論は、計算理論の一分野であり、計算問題をその固有の難易度に基づいて分類し、それらの分類を相互に関連付けることに焦点を当てています。計算問題とは、原理的にはコンピュータで解決可能なタスクであり、これは、アルゴリズムなどの数学的手順を機械的に適用することで問題を解決できることを意味します。

使用するアルゴリズムに関わらず、その解決に多大なリソースを必要とする問題は、本質的に困難であるとみなされます。この理論は、こうした問題を研究するための計算の数学的モデルを導入し、時間やストレージなど、解決に必要なリソースの量を定量化することで、この直感を形式化しています。他にも、通信量（通信複雑度で使用）、回路内のゲート数（回路複雑度で使用）、プロセッサ数（並列コンピューティングで使用）など、複雑度を表す尺度が用いられています。計算複雑度理論の役割の一つは、コンピュータができることとできないことの実際的な限界を決定することです。

計算幾何学は、幾何学の観点から表現できるアルゴリズムの研究に特化したコンピュータ科学の一分野である。計算幾何学アルゴリズムの研究から純粋に幾何学的な問題が生じる場合もあり、そのような問題も計算幾何学の一部とみなされる。

計算幾何学が学問分野として発展した主な原動力は、コンピュータグラフィックスとコンピュータ支援設計・製造（CAD / CAM）の進歩であったが、計算幾何学における多くの問題は古典的な性質のものであり、数学的可視化から生じる可能性がある。

計算幾何学のその他の重要な応用分野としては、ロボット工学（動作計画や視認性の問題）、地理情報システム（GIS）（幾何学的位置特定と検索、経路計画）、集積回路設計（IC形状設計と検証）、コンピュータ支援工学（CAE）（メッシュ生成）、コンピュータビジョン（3D再構成）などが挙げられる。

機械学習における理論的な成果は、主に教師あり学習と呼ばれる帰納的学習の一種を扱っています。教師あり学習では、アルゴリズムに何らかの有用な方法でラベル付けされたサンプルが与えられます。例えば、サンプルはキノコの説明であり、ラベルはキノコが食用かどうかといったものです。アルゴリズムは、これらのラベル付けされたサンプルを用いて分類器を誘導します。この分類器は、アルゴリズムがこれまで見たことのないサンプルも含め、サンプルにラベルを割り当てる関数です。教師あり学習アルゴリズムの目標は、新しいサンプルに対する誤認識数を最小限に抑えるなど、何らかの性能指標を最適化することです。

計算数論（アルゴリズム数論とも呼ばれる）は、数論的計算を実行するためのアルゴリズムを研究する分野である。この分野で最もよく知られている問題は、整数因数分解である。

暗号学は、第三者（攻撃者と呼ばれる）が存在する状況下で安全な通信 を行うための技術の実践と研究である。 ^{[ 10 ]}より一般的には、攻撃者の影響を克服するプロトコルの構築と分析に関するものであり^{[ 11 ]} 、データの機密性、データの完全性、認証、否認防止など、情報セキュリティのさまざまな側面に関連している。^{[ 12 ]}現代の暗号学は、数学、コンピュータ科学、電気工学の分野と交差している。暗号学の応用例としては、ATMカード、コンピュータのパスワード、電子商取引などがある。

現代の暗号技術は、数学理論とコンピュータ科学の実践に大きく基づいています。暗号アルゴリズムは計算困難性の仮定に基づいて設計されているため、実際にはいかなる攻撃者も解読することが困難です。理論的にはこのようなシステムを破ることは可能ですが、既知の実用的な手段では破ることは不可能です。したがって、これらの方式は計算的に安全であると言われます。整数因数分解アルゴリズムの改良などの理論的進歩や、より高速な計算技術により、これらのソリューションは継続的に適応させる必要があります。情報理論的に安全な方式も存在し、無制限の計算能力をもってしても破られないことが証明されています（ワンタイムパッドはその一例です）が、これらの方式は、理論的には破られる可能性があるものの計算的に安全な最良のメカニズムよりも実装が困難です。

データ構造とは、コンピュータ内でデータを効率的に利用できるように整理する特定の方法のことである。^{[ 13 ] [ 14 ]}

データ構造には様々な種類があり、それぞれに適したアプリケーションが異なります。また、特定のタスクに特化したデータ構造もあります。例えば、データベースはデータ検索のごく一部にBツリーインデックスを使用し、コンパイラやデータベースはルックアップテーブルとして動的ハッシュテーブルを使用します。

データ構造は、大規模データベースやインターネットインデックスサービスなどの用途において、大量のデータを効率的に管理する手段を提供する。通常、効率的なデータ構造は、効率的なアルゴリズムを設計する上で鍵となる。一部の形式設計手法やプログラミング言語では、ソフトウェア設計における主要な構成要素として、アルゴリズムよりもデータ構造を重視している。データの格納と取得は、メインメモリと二次記憶装置の両方に格納されたデータに対して実行できる。

分散コンピューティングは分散システムを研究します。分散システムとは、ネットワーク上のコンピュータに配置されたコンポーネントがメッセージを渡すことで通信し、動作を調整するソフトウェアシステムです。^{[ 15 ]}コンポーネントは共通の目標を達成するために互いに相互作用します。分散システムの3つの重要な特徴は、コンポーネントの並行性、グローバルクロックの欠如、およびコンポーネントの独立した障害です。^{[ 15 ]}分散システムの例は、SOAベースのシステムから大規模マルチプレイヤーオンラインゲーム、ピアツーピアアプリケーション、ビットコインのようなブロックチェーンネットワークまで多岐にわたります。

分散システムで実行されるコンピュータプログラムは分散プログラムと呼ばれ、分散プログラミングとはそのようなプログラムを作成するプロセスです。^{[ 16 ]}メッセージパッシングメカニズムには、 RPC のようなコネクタやメッセージキューなど、多くの代替手段があります。分散システムの重要な目標と課題は、ロケーション透過性です。

情報ベース複雑性（IBC）は、連続問題に対する最適なアルゴリズムと計算複雑性を研究する分野です。IBCは、経路積分、偏微分方程式、常微分方程式系、非線形方程式、積分方程式、不動点、超高次元積分といった連続問題を研究してきました。

形式手法は、ソフトウェアおよびハードウェアシステムの仕様、開発、検証のための数学に基づく特定の手法です。 ^{[ 17 ]}ソフトウェアおよびハードウェア設計に形式手法を使用する動機は、他の工学分野と同様に、適切な数学的解析を行うことで設計の信頼性と堅牢性に貢献できるという期待に基づいています。^{[ 18 ]}

形式手法は、論理計算、形式言語、オートマトン理論、プログラム意味論、型システム、代数的データ型など、かなり幅広い理論計算機科学の基礎をソフトウェアおよびハードウェアの仕様と検証の問題に適用したものと最もよく説明できます。^{[ 19 ]}

情報理論は、応用数学、電気工学、コンピュータ科学の一分野で、情報の定量化を扱います。情報理論は、クロード・E・シャノンによって、データの圧縮やデータの信頼性の高い保存と通信などの信号処理操作の根本的な限界を見つけるために開発されました。その誕生以来、統計的推論、自然言語処理、暗号、神経生物学^{[ 20 ]}、分子コードの進化^{[ 21 ]}と機能^{[ 22 ]} 、統計におけるモデル選択^{[ 23 ]} 、熱力学[24]、量子コンピューティング、言語学、盗作検出^{[ 25 ]} 、パターン認識、異常検出、その他のデータ分析^{[ 26 ]など、他の多くの分野に応用されてい}ます。

情報理論の基礎的なトピックの応用例としては、可逆データ圧縮（ZIPファイルなど）、可逆データ圧縮（MP3やJPEGなど）、チャネル符号化（デジタル加入者線（DSL）など）が挙げられます。この分野は、数学、統計学、コンピュータ科学、物理学、神経生物学、電気工学の交差点に位置しています。その影響は、深宇宙探査ミッションであるボイジャー計画の成功、コンパクトディスクの発明、携帯電話の実用化、インターネットの発展、言語学や人間の知覚の研究、ブラックホールの理解、その他多くの分野に不可欠なものでした。情報理論の重要な下位分野としては、ソース符号化、チャネル符号化、アルゴリズム複雑性理論、アルゴリズム情報理論、情報理論的セキュリティ、情報尺度などが挙げられます。

機械学習は、データから学習できるアルゴリズムの構築と研究を扱う科学分野です。 ^{[ 27 ]}このようなアルゴリズムは、明示的にプログラムされた指示に従うだけでなく、入力に基づいてモデルを構築し^{[ 28 ] : 2}、それを使用して予測や決定を行うことで動作します。

機械学習は、コンピュータ科学と統計学のサブ分野とみなすことができます。人工知能と最適化との密接な関係があり、これらの分野は機械学習に手法、理論、応用領域を提供しています。機械学習は、明示的なルールベースのアルゴリズムの設計とプログラミングが不可能な、さまざまなコンピューティングタスクで利用されています。応用例としては、スパムフィルタリング、光学文字認識（OCR）^{[ 29 ]} 、検索エンジン、コンピュータビジョンなどがあります。機械学習はデータマイニング^{[ 30 ]}と混同されることがありますが、データマイニングは探索的データ分析に重点を置いています^{[ 31 ]} 。機械学習とパターン認識は「同じ分野の2つの側面」と見なすことができます^{[ 28 ] : vii}

^{[ 39 ]}

並列コンピューティングは、多くの計算を同時に実行する計算形式であり、 ^{[ 40 ]}大きな問題は多くの場合、より小さな問題に分割でき、それらを「並列に」解決できるという原理に基づいて動作します。並列コンピューティングには、ビットレベル、命令レベル、データ、タスク並列など、いくつかの異なる形式があります。並列処理は、主に高性能コンピューティングで長年使用されてきましたが、周波数スケーリングを妨げる物理的な制約のために、近年関心が高まっています。^{[ 41 ]}近年、コンピュータの消費電力（およびそれに伴う発熱）が懸念事項となっているため、^{[ 42 ]}並列コンピューティングは、主にマルチコアプロセッサの形で、コンピュータアーキテクチャの支配的なパラダイムとなっています。^{[ 43 ]}

並列コンピュータプログラムは、逐次プログラムよりも記述が難しい。^{[ 44 ]}なぜなら、並行処理によっていくつかの新しい種類の潜在的なソフトウェアバグが発生し、その中でも競合状態が最も一般的だからである。異なるサブタスク間の通信と同期は、通常、並列プログラムのパフォーマンスを向上させる上で最大の障害となる。

並列化によって単一プログラムの実行速度が最大限向上する度合いは、アムダールの法則として知られています。

プログラミング言語理論は、プログラミング言語とその個々の特徴の設計、実装、分析、特性評価、分類を扱うコンピュータ科学の一分野です。理論計算機科学の分野に属し、数学、ソフトウェア工学、言語学に依存し、またそれらに影響を与えます。数多くの専門誌が存在する、活発な研究分野です。

プログラミング言語理論において、意味論とは、プログラミング言語の意味を厳密に数学的に研究する分野です。意味論は、特定のプログラミング言語で定義された構文的に正しい文字列の意味を評価し、それに伴う計算を示します。構文的に不正な文字列を評価する場合、結果は計算が行われないことになります。意味論は、コンピュータが特定の言語でプログラムを実行する際に従うプロセスを記述します。これは、プログラムの入力と出力の関係を記述したり、特定のプラットフォーム上でプログラムがどのように実行されるかを説明したりすることで示すことができ、それによって計算モデルが作成されます。

量子コンピュータは、重ね合わせやエンタングルメントなどの量子力学的現象を直接利用してデータに対する演算を実行する計算システムです。^{[ 45 ]}量子コンピュータは、トランジスタに基づくデジタルコンピュータとは異なります。デジタルコンピュータでは、データがバイナリ数字（ビット）にエンコードされる必要があり、各ビットは常に2つの確定状態（0または1）のいずれかになりますが、量子計算では、状態の重ね合わせ状態をとることができる量子ビット（キュービット）を使用します。理論モデルとしては、ユニバーサル量子コンピュータとしても知られる量子チューリングマシンがあります。量子コンピュータは、非決定論的コンピュータや確率的コンピュータと理論的に類似点を共有しています。1つの例として、同時に複数の状態をとる能力が挙げられます。量子コンピューティングの分野は、1980年にユーリ・マニン^{[ 46 ]}、1982年にリチャード・ファインマン^{[ 47 ] [ 48 ]}によって初めて提唱されました。スピンを量子ビットとする量子コンピュータは、 1968年に量子時空として使用するためにも定式化されました^{[ 49 ]。}

ごく少数の量子ビットで量子計算操作を実行する実験が行われてきました。^{[ 50 ]}実用的および理論的な研究は継続されており、多くの国の政府や軍事資金提供機関は、暗号解読などの民間および国家安全保障目的の両方で量子コンピュータを開発するために量子コンピューティング研究を支援しています。^{[ 51 ]}

コンピュータ代数（記号計算または代数計算とも呼ばれる）は、数式やその他の数学的対象を操作するためのアルゴリズムとソフトウェアの研究と開発を指す科学分野です。厳密に言えば、コンピュータ代数は科学計算のサブ分野であるべきですが、科学計算は通常、近似浮動小数点数を用いた数値計算に基づいているのに対し、記号計算は、与えられた値を持たない変数を含む式を用いた正確な計算を重視し、それらの式は記号として操作されるため（記号計算という名前が付けられています）、一般的には別々の分野とみなされています。

記号計算を実行するソフトウェアアプリケーションは、コンピュータ代数システムと呼ばれ、システムという用語は、少なくともコンピュータで数学データを表現する方法、ユーザープログラミング言語（通常は実装に使用される言語とは異なる）、専用のメモリマネージャ、数式の入出力のためのユーザーインターフェイス、式の簡略化、連鎖律を使用した微分、多項式の因数分解、不定積分などの通常の操作を実行するための多数のルーチンを含む、主要なアプリケーションの複雑さを暗示しています。

超大規模集積回路（VLSI ）とは、数千個のトランジスタを1つのチップに集積して集積回路（IC）を作成するプロセスです。VLSIは、複雑な半導体技術や通信技術が開発されていた1970年代に始まりました。マイクロプロセッサはVLSIデバイスです。VLSI技術が導入される以前は、ほとんどのICは限られた機能しか実行できませんでした。電子回路は、 CPU、ROM、RAM、その他のロジック回路で構成されていました。VLSIにより、ICメーカーはこれらの回路すべてを1つのチップに集積できるようになりました。