ブラウザよりも高速アクセス！理論計算機科学と計算機科学間の類似点
理論計算機科学と計算機科学は（ユニオンペディアに）共通で27ものを持っています: Association for Computing Machinery、並列計算、圏論、チューリングマシン、ラムダ計算、プログラミング言語、プログラム意味論、データベース、データ構造、分散コンピューティング、アラン・チューリング、アルゴリズム解析、アロンゾ・チャーチ、クルト・ゲーデル、グラフ理論、コンピューティング、コンピュータ、コンピュータネットワーク、計算可能性理論、計算モデル、計算理論、暗号理論、機械学習、情報理論、数学、数理論理学、数論。
Association for Computing Machinery
Association for Computing Machinery (ACM) は、ニューヨークに本部のあるコンピュータ科学分野の国際学会。1947年設立。IEEEとともに、この分野で最も影響力の強い学会であり、IEEEがその名と由来や歴史からエレクトロニクスや通信分野の工学に強いのに対し、数学的な理論計算機科学のような分野もカバーする。日本語に訳して「計算機械学会」とされることもあるが、こんにちこの訳語が用いられることはほとんどなく、通常は単に"ACM"という略称で呼ばれるのがもっぱらである。ACMの「A」は Association (学会、団体) の頭文字であるが、アメリカ数学会 (AMS) と混同して「米国計算機学会」と誤訳されることがある。 数多くの国際会議を開催しており、人目を惹くデモ映像のSIGGRAPHやSIGMODなどはよく知られている。他の多くの学会と同様にすぐれた業績などへの表彰もおこなっているが、チューリング賞は、特にこの分野の最高の賞とみなされており、物理や化学といった分野におけるノーベル賞に匹敵するものと扱われることもある（他の賞についても時折「～のノーベル賞」といったような表現が使われることがあるが、この分野の全てを対象とした世界トップクラスの賞という位置づけにあるのはチューリング賞をおいて他にない）。.
Association for Computing Machineryと理論計算機科学 · Association for Computing Machineryと計算機科学 ·
並列計算
並列計算（へいれつけいさん、parallel computing）は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。 関連する概念に並行計算（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。 特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。.
圏論
圏論（けんろん、category theory）は、数学的構造とその間の関係を抽象的に扱う数学理論の 1 つである。 考えている種類の「構造」を持った対象とその構造を反映するような対象間の射の集まりからなる圏が基本的な考察の対象になる。 数学の多くの分野、また計算機科学や数理物理学のいくつかの分野で導入される一連の対象は、しばしば適当な圏の対象たちだと考えることができる。圏論的な定式化によって同種のほかの対象たちとの、内部の構造に言及しないような形式的な関係性や、別の種類の数学的な対象への関連づけなどが統一的に記述される。.
圏論と理論計算機科学 · 圏論と計算機科学 ·
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
チューリングマシンと理論計算機科学 · チューリングマシンと計算機科学 ·
ラムダ計算
ラムダ計算（ラムダけいさん、lambda calculus）は、計算模型のひとつで、計算の実行を関数への引数の評価（evaluation）と適用（application）としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ (λ) を使うという慣習からその名がある。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案された。1936年にチャーチはラムダ計算を用いて一階述語論理の決定可能性問題を（否定的に）解いた。ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLISP、ML、Haskellといった関数型プログラミング言語の理論的基盤として、その誕生に大きな役割を果たした。 ラムダ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな）プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算がチューリングマシンと等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。 この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「型付きラムダ計算」という体系も提唱されている。.
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
プログラミング言語と理論計算機科学 · プログラミング言語と計算機科学 ·
プログラム意味論
プログラム意味論（program semantics）とは、計算機科学（特に理論計算機科学と分類されることもある）の一分野で、プログラミング言語の意味と計算モデルに関する分野である。形式的なものは、プログラミング言語の形式意味論とも呼ばれる。標準規格等では形式的でなく意味論を与えているものも多い。.
プログラム意味論と理論計算機科学 · プログラム意味論と計算機科学 ·
データベース
データベース（database, DB）とは、検索や蓄積が容易にできるよう整理された情報の集まり。 通常はコンピュータによって実現されたものを指すが、紙の住所録などをデータベースと呼ぶ場合もある。コンピュータを使用したデータベース・システムでは、データベース管理用のソフトウェアであるデータベース管理システムを使用する場合も多い。.
データベースと理論計算機科学 · データベースと計算機科学 ·
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
分散コンピューティング
分散コンピューティング（ぶんさんコンピューティング、英: Distributed computing）とは、プログラムの個々の部分が同時並行的に複数のコンピュータ上で実行され、各々がネットワークを介して互いに通信を行いながら全体として処理が進行する計算手法のことである。複雑な計算などをネットワークを介して複数のコンピュータを利用して行うことで、一台のコンピュータで計算するよりスループットを上げようとする取り組み、またはそれを実現する為の仕組みである。分散処理（ぶんさんしょり）ともいう。並列コンピューティングの一形態に分類されるが、一般に並列コンピューティングと言えば、同時並行に実行する主体は同じコンピュータシステム内のCPU群である。ただし、どちらもプログラムの分割（同時に実行できる部分にプログラムを分けること）が必須である。分散コンピューティングではさらに、それぞれの部分が異なる環境でも動作できるようにしなければならない。例えば、2台の異なるハードウェアを使ったコンピュータで、それぞれ異なるファイルシステム構成であっても動作するよう配慮する必要がある。 問題を複数の部分問題に分けて各コンピュータに実行させるのが基本であり、素数探索や数多く試してみる以外に解決できない問題の対処として用いられているものが多い。分散コンピューティングの例としてBOINCがある。これは、大きな問題を多数の小さな問題に分割し、多数のコンピュータに分配するフレームワークである。その後、それぞれの結果を集めて大きな解を得る。一般的に処理を分散すると一台のコンピュータで計算する場合と比べ、問題データの分配、収集、集計するためのネットワークの負荷が増加し、問題解決の為のボトルネックとなるため、部分問題間の依存関係を減らすことが重要な課題となる。 分散コンピューティングは、コンピュータ同士をネットワーク接続し、効率的に通信できるよう努力した結果として自然に生まれた。しかし、分散コンピューティングはコンピュータネットワークと同義ではない。単にコンピュータネットワークと言った場合、複数のコンピュータが互いにやり取りするが、単一のプログラムの処理を共有することはない。World Wide Web はコンピュータネットワークの例であるが、分散コンピューティングの例ではない。 分散処理を構築するための様々な技術や標準が存在し、一部はその目的に特化して設計されている。例えば、遠隔手続き呼出し (RPC)、Java Remote Method Invocation (Java RMI)、.NET Remoting などがある。.
分散コンピューティングと理論計算機科学 · 分散コンピューティングと計算機科学 ·
アラン・チューリング
アラン・マシスン・チューリング（Alan Mathieson Turing、〔テュァリング〕, 1912年6月23日 - 1954年6月7日）はイギリスの数学者、論理学者、暗号解読者、コンピュータ科学者。.
アラン・チューリングと理論計算機科学 · アラン・チューリングと計算機科学 ·
アルゴリズム解析
アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。.
アルゴリズム解析と理論計算機科学 · アルゴリズム解析と計算機科学 ·
アロンゾ・チャーチ
アロンゾ・チャーチ（Alonzo Church, 1903年6月14日 - 1995年8月11日）はアメリカの論理学者、数学者。ラムダ計算の創案者、「チャーチ＝チューリングのテーゼ」の提唱者として知られる。.
アロンゾ・チャーチと理論計算機科学 · アロンゾ・チャーチと計算機科学 ·
クルト・ゲーデル
ルト・ゲーデル（Kurt Gödel, 1906年4月28日 - 1978年1月14日）は、オーストリア・ハンガリー二重帝国（現チェコ）のブルノ生まれの数学者・論理学者である。業績には、完全性定理及び不完全性定理、連続体仮説に関する研究が知られる。.
クルト・ゲーデルと理論計算機科学 · クルト・ゲーデルと計算機科学 ·
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
コンピューティング
階差機関。多項式関数の解を計算する機械 とある大学の計算機室 (2003) ウィキメディア財団のサーバ コンピューティング（computing）の古来の意味は「数えること」と「計算すること」であり、算術ないしは数学の計算を指した。現在は転じてコンピュータによる数値計算や、より広くデータ処理(data processing)や情報処理 (information processing) といったコンピュータを使う活動全般も指すことがある。 日本語ではどちらも「計算」と呼んでいるが、対応する英語にはcalculationとcomputationがある。条件分岐などを伴う複雑な計算がcalculationではなくcomputationである。.
コンピューティングと理論計算機科学 · コンピューティングと計算機科学 ·
コンピュータ
ンピュータ（Computer）とは、自動計算機、とくに計算開始後は人手を介さずに計算終了まで動作する電子式汎用計算機。実際の対象は文字の置き換えなど数値計算に限らず、情報処理やコンピューティングと呼ばれる幅広い分野で応用される。現代ではプログラム内蔵方式のディジタルコンピュータを指す場合が多く、特にパーソナルコンピュータやメインフレーム、スーパーコンピュータなどを含めた汎用的なシステムを指すことが多いが、ディジタルコンピュータは特定の機能を実現するために機械や装置等に組み込まれる組み込みシステムとしても広く用いられる。電卓・機械式計算機・アナログ計算機については各項を参照。.
コンピュータと理論計算機科学 · コンピュータと計算機科学 ·
コンピュータネットワーク
ンピュータネットワーク（computer network）は、複数のコンピュータを接続する技術。または、接続されたシステム全体。コンピュータシステムにおける「通信インフラ」自体、あるいは通信インフラによって実現される接続や通信の総体が（コンピュータ）ネットワークである、とも言える。.
コンピュータネットワークと理論計算機科学 · コンピュータネットワークと計算機科学 ·
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
理論計算機科学と計算可能性理論 · 計算可能性理論と計算機科学 ·
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
暗号理論
暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
機械学習
機械学習（きかいがくしゅう、machine learning）とは、人工知能における研究課題の一つで、人間が自然に行っている学習能力と同様の機能をコンピュータで実現しようとする技術・手法のことである。.
情報理論
情報理論（じょうほうりろん、Information theory）は、情報・通信を数学的に論じる学問である。応用数学の中でもデータの定量化に関する分野であり、可能な限り多くのデータを媒体に格納したり通信路で送ったりすることを目的としている。情報エントロピーとして知られるデータの尺度は、データの格納や通信に必要とされる平均ビット数で表現される。例えば、日々の天気が3ビットのエントロピーで表されるなら、十分な日数の観測を経て、日々の天気を表現するには「平均で」約3ビット/日（各ビットの値は 0 か 1）と言うことができる。 情報理論の基本的な応用としては、ZIP形式（可逆圧縮）、MP3（非可逆圧縮）、DSL（伝送路符号化）などがある。この分野は、数学、統計学、計算機科学、物理学、神経科学、電子工学などの交差する学際領域でもある。その影響は、ボイジャー計画の深宇宙探査の成功、CDの発明、携帯電話の実現、インターネットの開発、言語学や人間の知覚の研究、ブラックホールの理解など様々な事象に及んでいる。.
数学
数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.
数学と理論計算機科学 · 数学と計算機科学 ·
数理論理学
数理論理学（mathematische Logik、mathematical logic）は、論理学（形式論理学）の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学（とくに）における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか（逆数学のように）ということに焦点を当てている。.
数論
数論（すうろん、number theory）とは数、特に整数およびそれから派生する数の体系（代数体、局所体など）の性質について研究する数学の一分野である。整数論とも言う。ふつうは代数学の一分野とみなされることが多い。おおむね次の四つに分けられる。;初等整数論;代数的整数論;解析的整数論;数論幾何学 フェルマーの最終定理のように、数論のいくつかの問題については、他の数学の分野に比して問題そのものを理解するのは簡単である。しかし、使われる手法は多岐に渡り、また非常に高度であることが多い。 ガウスは次のような言葉を残している。.
数論と理論計算機科学 · 数論と計算機科学 ·
上記のリストは以下の質問に答えます
- 何理論計算機科学と計算機科学ことは共通しています
- 何が理論計算機科学と計算機科学間の類似点があります
理論計算機科学と計算機科学の間の比較
計算機科学が91を有している理論計算機科学は、72の関係を有しています。 彼らは一般的な27で持っているように、ジャカード指数は16.56%です = 27 / (72 + 91)。
参考文献
この記事では、理論計算機科学と計算機科学との関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください:
