理論計算機科学の一分野であるオートマトン理論における有限状態オートマトン

理論計算機科学は計算機科学と数学のサブフィールドであり、計算の抽象的かつ数学的な基礎に焦点を当てています。

理論領域を正確に限定することは困難である。ACMのアルゴリズムと計算理論に関する特別利益団体（SIGACT）は、以下のように説明している。[1]

TCSは、アルゴリズム、データ構造、計算複雑性、並列・分散計算、確率計算、量子計算、オートマトン理論、情報理論、暗号理論、プログラム意味論と検証、アルゴリズムゲーム理論、機械学習、計算生物学、計算経済学、計算幾何学、計算数論と代数など、幅広いトピックをカバーしています。この分野の研究は、数学的手法と厳密さを重視する点が特徴です。

歴史

論理的推論と数学的証明は以前にも存在していましたが、1931 年にクルト ゲーデルは不完全性定理によって、証明または反証できる命題には根本的な制限があることを証明しました。

情報理論は、1948年にクロード・シャノンが発表したコミュニケーションの数学的理論によってこの分野に加わりました。同時期にドナルド・ヘブは脳における学習の数学的モデルを発表しました。この仮説を多少の修正を加えて裏付ける生物学的データが蓄積されるにつれ、ニューラルネットワークと並列分散処理の分野が確立されました。1971年には、スティーブン・クックとレオニード・レビンが独立して、NP完全である実用的な問題が存在することを証明しました。これは計算複雑性理論における画期的な成果です。[2]

現代の理論コンピュータサイエンスの研究はこれらの基本的な発展に基づいていますが、以下に示すように、提起された他の多くの数学的および学際的な問題も含まれています。

トピック

アルゴリズム

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

アルゴリズムとは、関数[ 5 ]を計算するための、明確に定義された命令[4]の有限リスト[3]として表現される効果的な手法である。 初期状態と初期入力（おそらく空）[6]から始まり、命令は計算を記述する。計算が実行されると、明確に定義された有限個の連続状態[7]を経て、最終的に「出力」 [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 

自然計算

自然コンピューティング[ 32] [33]は、自然計算とも呼ばれ、3つのクラスの手法を包含するために導入された用語である。1) 自然からヒントを得て新たな問題解決手法を開発するもの、2) コンピュータを使って自然現象を合成するもの、3) 自然素材（分子など）を使って計算するもの。これら3つの分野を構成する主な研究分野には、人工ニューラルネットワーク、進化アルゴリズム、群知能、人工免疫システム、フラクタル幾何学、人工生命、DNAコンピューティング、量子コンピューティングなどがある。しかし、この分野は生物学的計算との関連性が強い。

自然コンピューティングによって研究される計算パラダイムは、自己複製、脳の機能、ダーウィンの進化論、集団行動、免疫システム、生命体の定義特性、細胞膜、形態形成など、多様な自然現象から抽象化されます。これらの計算パラダイムは、従来の電子ハードウェアに加えて、生体分子（DNA、RNA）やイオントラップ量子コンピューティングデバイスなどの代替物理媒体上に実装することもできます。

二重の見方をすれば、自然界で起きる過程を情報処理と見なすこともできる。そのような過程には、自己組織化、 発生過程、遺伝子調節ネットワーク、タンパク質間相互作用ネットワーク、生物輸送（能動輸送、受動輸送）ネットワーク、単細胞生物における遺伝子集合などがある。生物系を理解するための取り組みには、半合成生物の工学や、情報処理の観点から宇宙そのものを理解することも含まれる。実際、情報は物質やエネルギーよりも根源的であるという考えさえ提唱されていた。1960年代に遡るツーゼ＝フレドキンのテーゼは、宇宙全体が巨大なセルオートマトンであり、そのルールを絶えず更新しているという。[34] [35]最近では、宇宙全体が自身の動作を計算する量子コンピュータ であるという説もある。 [36]

計算メカニズムとしての宇宙/自然は、[37]計算可能性の考え方を活用して自然を探求し、[38]自然プロセスを計算（情報処理）として研究することによって扱われます。

[39]

並列計算

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

並列コンピュータプログラムは、逐次的なプログラムよりも記述が困難です。[44]並行性によっていくつかの新しい種類の潜在的なソフトウェアバグが発生し、その中で最もよくあるのは競合状態です。異なるサブタスク間の通信と同期は、並列プログラムの優れたパフォーマンスを得る上で最も大きな障害となることがよくあります。

並列化の結果として単一プログラムが最大限に高速化されるという法則は、アムダールの法則として知られています。

プログラミング言語理論とプログラム意味論

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

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

量子計算

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

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

記号計算

コンピュータ代数は、記号計算または代数計算とも呼ばれ、数式やその他の数学的オブジェクトを操作するためのアルゴリズムとソフトウェアの研究と開発を指す科学分野です。厳密に言えば、コンピュータ代数は科学計算のサブフィールドであるべきですが、科学計算は通常、近似浮動小数点数を用いた数値計算に基づくのに対し、記号計算は特定の値を持たず、記号として操作される変数を含む式を用いた正確な計算に重点を置くため、一般的には異なる分野と見なされています（そのため、記号計算と呼ばれます）。

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

超大規模統合

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

組織

ジャーナルとニュースレター

会議

参照

注記

  1. ^ "SIGACT" . 2017年1月19日閲覧。
  2. ^ Cook, Stephen A. (1971). 「定理証明手続きの複雑さ」.第3回ACM計算理論シンポジウム議事録 - STOC '71 . pp.  151– 158. doi :10.1145/800157.805047. ISBN 978-1-4503-7464-4。
  3. ^ 「例えば、あらゆる古典的な数学アルゴリズムは、有限個の英語の単語で記述できる」ロジャース、ハートリー・ジュニア(1967). 『再帰関数の理論と実効計算可能性』 マグロウヒル.2ページ目。
  4. ^ アルゴリズムを実行するエージェントに関しては明確に定義されています。「通常は人間である計算エージェントが存在し、命令に反応して計算を実行できます」(Rogers 1967、p. 2)。
  5. ^ 「アルゴリズムとは（整数の選択された表記法に関して）関数を計算する手順である...この（数値関数への）制限によって一般性が失われることはない」（Rogers 1967、p. 1）。
  6. ^ 「アルゴリズムには0 個以上の入力、つまりアルゴリズムが開始する前に最初に与えられる量があります」(Knuth 1973:5)。
  7. ^ 「有限性がない可能性があることを除いてアルゴリズムのすべての特性を持つ手順は、「計算方法」と呼ばれることがあります」（Knuth 1973:5）。
  8. ^ 「アルゴリズムには 1 つ以上の出力、つまり入力と特定の関係にある量があります」(Knuth 1973:5)。
  9. ^ ランダムな内部プロセス（入力を含まない）を持つプロセスがアルゴリズムであるかどうかは議論の余地がある。ロジャーズは次のように述べている。「計算は、連続的な手法やアナログデバイスを用いることなく、離散的な段階的な方法で実行される。…サイコロなどのランダムな手法やデバイスに頼ることなく、決定論的に進められる」（Rogers 1967, p. 2）。
  10. ^ Rivest, Ronald L. (1990). 「暗号学」. J. Van Leeuwen (編).理論計算機科学ハンドブック. 第1巻. Elsevier.
  11. ^ ベッラーレ、ミヒル;フィリップ・ロガウェイ (2005 年 9 月 21 日) "導入"。最新の暗号化の概要。 p. 10.
  12. ^ Menezes, AJ; van Oorschot, PC; Vanstone, SA (1997). 応用暗号ハンドブック. Taylor & Francis. ISBN 978-0-8493-8523-0。
  13. ^ Paul E. Black (編)、「アルゴリズムとデータ構造辞書」のデータ構造の項目。米国国立標準技術研究所。2004年12月15日。オンライン版は2009年5月21日にアクセス。
  14. ^ ブリタニカ百科事典(2009)のエントリデータ構造。2009年 5 月 21 日にアクセスしたオンラインエントリ。
  15. ^ ab Coulouris, George; Jean Dollimore; Tim Kindberg; Gordon Blair (2011). 『分散システム：概念と設計』（第5版）ボストン：Addison-Wesley. ISBN 978-0-132-14301-1。
  16. ^ Ghosh, Sukumar (2007).分散システム – アルゴリズム的アプローチ. Chapman & Hall/CRC. p. 10. ISBN 978-1-58488-564-1。
  17. ^ RW Butler (2001-08-06). 「形式手法とは何か？」2006年11月16日閲覧。
  18. ^ C. Michael Holloway. 「エンジニアが形式手法を検討すべき理由」(PDF) . 第16回デジタル航空電子工学システム会議 (1997年10月27～30日). 2006年11月16日時点のオリジナル(PDF)からアーカイブ。 2006年11月16日閲覧。
  19. ^ モナン、3～4ページ
  20. ^ F. リーケ; D.ウォーランド。 R・ロイテル・ファン・スティーブニンク。 W ビアレク (1997)。スパイク: ニューラル コードの探索。 MITの報道陣。ISBN 978-0262681087。
  21. ^ Huelsenbeck, JP; Ronquist, F.; Nielsen, R.; Bollback, JP (2001-12-14). 「ベイズ推定による系統発生と進化生物学への影響」. Science . 294 (5550). アメリカ科学振興協会 (AAAS): 2310– 2314. Bibcode :2001Sci...294.2310H. doi :10.1126/science.1065889. ISSN  0036-8075. PMID  11743192. S2CID  2138288.
  22. ^ Rando Allikmets、Wyeth W. Wasserman、Amy Hutchinson、Philip Smallwood、Jeremy Nathans、Peter K. Rogan、Thomas D. Schneider、Michael Dean (1998) ABCR遺伝子の構成：プロモーターとスプライスジャンクション配列の解析、Gene 215 :1、111–122
  23. ^ Burnham, KPとAnderson DR (2002)モデル選択とマルチモデル推論：実践的な情報理論的アプローチ、第2版（Springer Science、ニューヨーク） ISBN 978-0-387-95364-9。
  24. ^ Jaynes, ET (1957-05-15). 「情報理論と統計力学」. Physical Review . 106 (4). アメリカ物理学会 (APS): 620– 630. Bibcode :1957PhRv..106..620J. doi :10.1103/physrev.106.620. ISSN  0031-899X. S2CID  17870175.
  25. ^ Charles H. Bennett, Ming Li, Bin Ma (2003) Chain Letters and Evolutionary Histories Archived 2007-10-07 at the Wayback Machine , Scientific American 288 :6, 76–81
  26. ^ David R. Anderson (2003年11月1日). 「経験科学の分野における人々が情報理論的手法をより深く理解したいと考える理由についての背景」(PDF) . 2011年7月23日時点のオリジナル(PDF)からアーカイブ。 2010年6月23日閲覧。
  27. ^ Ron Kovahi; Foster Provost (1998). 「用語集」.機械学習. 30 : 271–274 . doi : 10.1023/A:1007411609915 .
  28. ^ ab CM Bishop (2006).パターン認識と機械学習. Springer. ISBN 978-0-387-31073-2。
  29. ^ Wernick, Yang, Brankov, Yourganov, Strother, 医用画像における機械学習, IEEE Signal Processing Magazine , vol. 27, no. 4, 2010年7月, pp. 25–38
  30. ^ Mannila, Heikki (1996). 「データマイニング：機械学習、統計、データベース」国際会議「科学および統計データベース管理」IEEEコンピュータ協会.
  31. ^ フリードマン、ジェローム・H. (1998). 「データマイニングと統計：その関連性とは？」『コンピューティングサイエンスと統計』29 (1): 3–9 .
  32. ^ G.Rozenberg、T.Back、J.Kok編『Handbook of Natural Computing』Springer Verlag、2012年
  33. ^ A.Brabazon、MO'Neill、S.McGarraghy著『自然計算アルゴリズム』Springer Verlag、2015年
  34. ^ Fredkin, F. デジタルメカニクス：可逆的普遍CAに基づく情報処理. Physica D 45 (1990) 254-270
  35. ^ Zuse、K. Rechnender Raum. Elektronische Datenverarbeitung 8 (1967) 336-344
  36. ^ ロイド、S. 『宇宙のプログラミング：量子コンピュータ科学者が宇宙に挑戦』クノップフ、2006年
  37. ^ ゼニル、H.『計算可能な宇宙：計算としての自然の理解と探究』ワールドサイエンティフィック出版社、2012年
  38. ^ Dodig-Crnkovic, G. および Giovagnoli, R. COMPUTING NATURE. Springer, 2013
  39. ^ Rozenberg, Grzegorz (2001). 「ナチュラルコンピューティング」.理論計算機科学の最新動向. pp.  543– 690. doi :10.1142/9789812810403_0005. ISBN 978-981-02-4473-6。
  40. ^ ゴットリーブ, アラン; アルマシ, ジョージ・S. (1989). 高度並列コンピューティング. レッドウッドシティ, カリフォルニア州: ベンジャミン/カミングス. ISBN 978-0-8053-0177-9。
  41. ^ SV Adve他 (2008年11月). 「イリノイ大学における並列コンピューティング研究：UPCRCアジェンダ」Wayback Machineに2008年12月9日にアーカイブ(PDF). Parallel@Illinois, イリノイ大学アーバナ・シャンペーン校. 「これらのパフォーマンス向上の主な手法、すなわちクロック周波数の向上と、よりスマートだがますます複雑化するアーキテクチャは、現在、いわゆるパワーウォールにぶつかりつつあります。コンピュータ業界は、将来のパフォーマンス向上は、単一のコアを高速化するのではなく、ダイ上のプロセッサ（またはコア）の数を増やすことによって主に達成される必要があることを認識しています。」
  42. ^ Asanovic et al. 古い[常識]：電力は無料だが、トランジスタは高価。新しい[常識]：電力は高価だが、トランジスタは「無料」。
  43. ^ Asanovic, Krste他 (2006年12月18日). 「並列コンピューティング研究の現状：バークレーからの視点」(PDF). カリフォルニア大学バークレー校. 技術報告書 No. UCB/EECS-2006-183. 「従来の[常識]：プロセッサ性能を向上させる主な方法はクロック周波数を上げることである。新しい[常識]：プロセッサ性能を向上させる主な方法は並列性を高めることである…一般的に「クロック周波数が高いほど良い」という立場をとっているIntelの代表者でさえ、クロック周波数を最大化することで性能を最大化する従来のアプローチは限界に達していると警告している。」
  44. ^ ヘネシー, ジョン・L.; パターソン, デイビッド・A.; ララス, ジェームズ・R. (1999). 『コンピュータの構成と設計：ハードウェア／ソフトウェア・インターフェース』（第2版、第3刷）サンフランシスコ：カウフマン. ISBN 978-1-55860-428-5。
  45. ^ 「分子による量子コンピューティング」Scientific American誌、 Neil GershenfeldとIsaac L. Chuangによる記事
  46. ^ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [ Computable and Noncomputable ] (ロシア語). Sov.Radio. pp.  13– 15. 2013年5月10日時点のオリジナルよりアーカイブ。 2013年3月4日閲覧。
  47. ^ ファインマン, RP (1982). 「コンピュータによる物理学のシミュレーション」.国際理論物理学ジャーナル. 21 (6): 467– 488. Bibcode :1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310 . doi :10.1007/BF02650179. S2CID  124545445. 
  48. ^ Deutsch, David (1992-01-06). 「量子計算」. Physics World . 5 (6): 57– 61. doi :10.1088/2058-7058/5/6/38.
  49. ^ フィンケルスタイン、デイヴィッド (1968). 「高エネルギー相互作用における時空構造」. グデハス、T.、カイザー、G. (編). 『高エネルギーにおける基礎的相互作用』 . ニューヨーク: ゴードン＆ブリーチ.
  50. ^ 「新たな量子ビット制御は量子コンピューティングの未来に明るい兆し」 。 2014年10月26日閲覧。
  51. ^ 研究の方向性を知るには、量子情報科学技術ロードマップを参照してください。
  52. ^ abcde 2007 年オーストラリア ICT カンファレンスランキング Archived 2009-10-02 at the Wayback Machine : tier A+。
  53. ^ “MFCS 2017”. 2018年1月10日時点のオリジナルよりアーカイブ。2018年1月9日閲覧。
  54. ^ CSR 2018
  55. ^ abcdefghij 2007 年オーストラリア ICT カンファレンスランキング Archived 2009-10-02 at the Wayback Machine : tier A。
  56. ^ SOFSEMウェブページ（2024年9月3日取得）
  57. ^ FCT 2011（2013年6月3日閲覧）

さらに読む

  • SIGACT 追加理論リンクディレクトリ（2017年7月15日アーカイブ）
  • 理論が重要 Wiki 理論計算機科学 (TCS) 推進 Wiki
  • confsearchにおける理論計算機科学分野の学術会議一覧
  • 理論計算機科学 – StackExchange、理論計算機科学の研究者のためのQ&Aサイト
  • コンピュータサイエンスアニメーション
  • マサチューセッツ工科大学における計算理論