ブラウザよりも高速アクセス！
15 関係: 基数木、否定標準形、二分木、モデル検査、ブール関数、ヒューリスティクス、データ構造、カーネギーメロン大学、グラフ理論、充足可能性問題、真理値表、論理回路、NP困難、決定木、木構造 (データ構造)。
基数木
right 基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。.
否定標準形
否定標準形（ひていひょうじゅんけい、negation normal form, NNF）とは、否定記号 \lnot が原子論理式のみにかかり、他には選言記号 \lor と連言記号 \land のみが論理記号として用いられる形の論理式を指す。 命題論理もしくは述語論理においては、いかなる論理式も、ド・モルガンの法則を用い否定演算子を内側に押し込む操作を繰り返すことによって、論理的に等価な否定標準形に置き換えることができる。この操作の具体例を次に示す。 連言標準形(conjunctive normal form)と選言標準形(disjunctive normal form)は否定標準形の性質を満たしている。任意の否定標準形の論理式は、論理式の結合法則と分配法則による操作によって、論理的に等価な連言標準形や選言標準形に変形することができる。.
新しい！!: 二分決定図と否定標準形 · 続きを見る »
二分木
二分木（binary tree; 二進木、バイナリツリー）は、データ構造の1つである。根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。 簡単な二分木。大きさ9、深さ3、根は値2を持つ 以後、括弧の中は英語表記。.
モデル検査
モデル検査（Model Checking）とは、形式システムをアルゴリズム的に検証する手法である。ハードウェアやソフトウェアの設計から導出されたモデルが形式仕様を満足するかどうか検証する。仕様は時相論理の論理式の形式で記述することが多い。.
新しい！!: 二分決定図とモデル検査 · 続きを見る »
ブール関数
ブール関数（ブールかんすう、Boolean function）は、非負整数 k 個のブール領域 B.
新しい！!: 二分決定図とブール関数 · 続きを見る »
ヒューリスティクス
ヒューリスティック（heuristic, Heuristik）とは、必ず正しい答えを導けるわけではないが、ある程度のレベルで正解に近い解を得ることができる方法である。ヒューリスティックスでは、答えの精度が保証されない代わりに、回答に至るまでの時間が少ないという特徴がある。主に計算機科学と心理学の分野で使用される言葉であり、どちらの分野での用法も根本的な意味は同じであるが、指示対象が異なる。すなわち、計算機科学ではプログラミングの方法を指すが、心理学では人間の思考方法を指すものとして使われる。なお、論理学では仮説形成法と呼ばれている。.
新しい！!: 二分決定図とヒューリスティクス · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
新しい！!: 二分決定図とデータ構造 · 続きを見る »
カーネギーメロン大学
ーネギーメロン大学（英語: Carnegie Mellon University）は、ペンシルベニア州ピッツバーグに本部を置くアメリカ合衆国屈指の名門私立研究大学である。1900年に設立され、略称はCMU。大学のモットーは、"My heart is in the work (私の心は仕事の中にある)"（創立者アンドリュー・カーネギー）。 美術・音楽・文学・科学の最終形は、この四つが一つに成っている形である。アンドリュー・カーネギーのこの考えに沿って、アートとテクノロジーのバランスと融合を重んじた高等教育をCMUは現在も精力的に実践していると言える。日本では理工系が強い大学で知られ、CMUの名はマサチューセッツ工科大学（MIT)、カリフォルニア工科大学（CalTech)とともにアメリカの名門工科大学の御三家の一つとしてあまりにも有名。 その一方で藝術、人文・社会科学、公共政策学・情報学、経営学(MBA)の分野においても、常に全米あるいは世界のトップクラスにランキングされているという事実を認識することで、MITやCalTechのように一概に工科大学とは言えない、総合大学としてのCMUの全体像を正しく掴むことができる。著名な賞を受賞したCMU関係者の数も、この全体像を反映した結果となっている。 ノーベル賞20名、チューリング賞12名、エミー賞52名、アカデミー賞10名、トニー賞44名、等々。.
新しい！!: 二分決定図とカーネギーメロン大学 · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: 二分決定図とグラフ理論 · 続きを見る »
充足可能性問題
充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.
新しい！!: 二分決定図と充足可能性問題 · 続きを見る »
真理値表
真理値表（しんりちひょう、Truth table）は、論理関数の、入力の全てのパターンとそれに対する結果の値を、表にしたものである。 例1：命題Pの否定「\lnot P」の場合、以下のような真理値表になる。 例2：2つの命題P,Qの論理和「P \lor Q」の場合、以下のような真理値表になる。 例3：2つの命題P,Qの論理積「P \land Q」の場合、以下のような真理値表になる。 なお、この表では「真」「偽」として表記してあるが、「T(.
新しい！!: 二分決定図と真理値表 · 続きを見る »
論理回路
論理回路（ろんりかいろ、logic circuit）は、論理演算を行う電気回路及び電子回路である。真理値の「真」と「偽」、あるいは二進法の「0」と「1」を、電圧の正負や高低、電流の方向や多少、位相の差異、パルスなどの時間の長短、などで表現し、論理素子などで論理演算を実装する。電圧の高低で表現する場合それぞれを「」「」等という。基本的な演算を実装する論理ゲートがあり、それらを組み合わせて複雑な動作をする回路を構成する。状態を持たない組み合わせ回路と状態を持つ順序回路に分けられる。論理演算の結果には、「真」、「偽」の他に「不定」がある。ラッチ回路のdon't care, フリップフロップ回路の禁止が相当する。 ここでの論理は離散(digital)であるためディジタル回路を用いる。論理演算を行うアナログ回路、「アナログ論理」を扱う回路（どちらも「アナログ論理回路」）もある。 多値論理回路も量子コンピュータで注目されている。 電気（電子）的でないもの（たとえば流体素子や光コンピューティングを参照）もある。 以下では離散なデジタル回路を扱う。.
新しい！!: 二分決定図と論理回路 · 続きを見る »
NP困難
NP完全、'''NP困難'''の相関を表すベン図 NP困難（エヌピーこんなん、NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難なとき次のことが言える（以下は定義ではなく主張）。.
新しい！!: 二分決定図とNP困難 · 続きを見る »
決定木
決定木（けっていぎ、decision tree）は、（リスクマネジメントなどの）決定理論の分野において、 決定を行う為のグラフであり、計画を立案して目標に到達するために用いられる。 決定木は、意志決定を助けることを目的として作られる。 決定木は木構造の特別な形である。.
木構造 (データ構造)
親子構造 木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。.
新しい！!: 二分決定図と木構造 (データ構造) · 続きを見る »
