アルゴリズム解析と計算機科学

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

アルゴリズム解析と計算機科学の違い

アルゴリズム解析 vs. 計算機科学

アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。. 計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.

チューリングマシン

チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.

アルゴリズム解析とチューリングマシン · チューリングマシンと計算機科学 · 続きを見る »

プログラミング言語

プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.

アルゴリズム解析とプログラミング言語 · プログラミング言語と計算機科学 · 続きを見る »

オペレーティングシステム

ペレーティングシステム（Operating System、OS、オーエス）とは、コンピュータのオペレーション（操作・運用・運転）のために、ソフトウェアの中でも基本的、中核的位置づけのシステムソフトウェアである。通常、OSメーカーが組み上げたコンピュータプログラムの集合として、作成され提供されている。 オペレーティングシステムは通常、ユーザーやアプリケーションプログラムとハードウェアの中間に位置し、ユーザーやアプリケーションプログラムに対して標準的なインターフェースを提供すると同時に、ハードウェアなどの各リソースに対して効率的な管理を行う。現代のオペレーティングシステムの主な機能は、ファイルシステムなどの補助記憶装置管理、仮想記憶などのメモリ管理、マルチタスクなどのプロセス管理、更にはGUIなどのユーザインタフェース、TCP/IPなどのネットワーク、などがある。オペレーティングシステムは、パーソナルコンピュータからスーパーコンピュータまでの各種のコンピュータや、更にはスマートフォンやゲーム機などを含む各種の組み込みシステムで、内部的に使用されている。 製品としてのOSには、デスクトップ環境やウィンドウシステムなど、あるいはデータベース管理システム (DBMS) などのミドルウェア、ファイル管理ソフトウェアやエディタや各種設定ツールなどのユーティリティ、基本的なアプリケーションソフトウェア（ウェブブラウザや時計などのアクセサリ）が、マーケティング上の理由などから一緒に含められていることもある。 OSの中で、タスク管理やメモリ管理など特に中核的な機能の部分をカーネル、カーネル以外の部分（シェルなど）をユーザランドと呼ぶ事もある。 現代の主なOSには、Microsoft Windows、Windows Phone、IBM z/OS、Android、macOS（OS X）、iOS、Linux、FreeBSD などがある。.

アルゴリズム解析とオペレーティングシステム · オペレーティングシステムと計算機科学 · 続きを見る »

コンピュータ

ンピュータ（Computer）とは、自動計算機、とくに計算開始後は人手を介さずに計算終了まで動作する電子式汎用計算機。実際の対象は文字の置き換えなど数値計算に限らず、情報処理やコンピューティングと呼ばれる幅広い分野で応用される。現代ではプログラム内蔵方式のディジタルコンピュータを指す場合が多く、特にパーソナルコンピュータやメインフレーム、スーパーコンピュータなどを含めた汎用的なシステムを指すことが多いが、ディジタルコンピュータは特定の機能を実現するために機械や装置等に組み込まれる組み込みシステムとしても広く用いられる。電卓・機械式計算機・アナログ計算機については各項を参照。.

アルゴリズム解析とコンピュータ · コンピュータと計算機科学 · 続きを見る »

計算モデル

計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.

アルゴリズム解析と計算モデル · 計算モデルと計算機科学 · 続きを見る »

暗号理論

暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.

アルゴリズム解析と暗号理論 · 暗号理論と計算機科学 · 続きを見る »

情報

情報（じょうほう、英語: information、ラテン語: informatio インフォルマーティオー）とは、.

アルゴリズム解析と情報 · 情報と計算機科学 · 続きを見る »

数値解析

バビロニアの粘土板 YBC 7289 （紀元前1800-1600年頃） 2の平方根の近似値は60進法で4桁、10進法では約6桁に相当する。1 + 24/60 + 51/602 + 10/603.

アルゴリズム解析と数値解析 · 数値解析と計算機科学 · 続きを見る »