組合せ数学と組合せ爆発

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

組合せ数学と組合せ爆発の違い

組合せ数学 vs. 組合せ爆発

組合せ数学（くみあわせすうがく、combinatorics）や組合せ論（くみあわせろん）とは、特定の条件を満たす（普通は有限の）対象からなる集まりを研究する数学の分野。特に問題とされることとして、集合に入っている対象を数えたり（数え上げ的組合せ論）、いつ条件が満たされるのかを判定し、その条件を満たしている対象を構成したり解析したり（組合せデザインやマトロイド理論）、「最大」「最小」「最適」な対象をみつけたり（極値組合せ論や組合せ最適化）、それらの対象が持ちうる代数的構造をみつけたり（代数的組合せ論）することが挙げられる。. 組合せ爆発（くみあわせばくはつ、Combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。.

アルゴリズム

フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.

アルゴリズムと組合せ数学 · アルゴリズムと組合せ爆発 · 続きを見る »

グラフ理論

ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.

グラフ理論と組合せ数学 · グラフ理論と組合せ爆発 · 続きを見る »

素因数分解

素因数分解 (そいんすうぶんかい、prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。 素因数分解には次のような性質がある。.

素因数分解と組合せ数学 · 素因数分解と組合せ爆発 · 続きを見る »

組合せ (数学)

数学において、組合せ（くみあわせ、combination, choose）とは、相異なる（あるいは区別可能な）いくつかの要素の集まりからいくつかの要素を（重複無く）選び出す方法である。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである。組合せは組合せ論と呼ばれる数学の分野で研究される。卑近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。.

組合せ (数学)と組合せ数学 · 組合せ (数学)と組合せ爆発 · 続きを見る »

階乗

数学において非負整数 の階乗（かいじょう、factorial） は、1 から までのすべての整数の積である。例えば、 である。空積の規約のもと と定義する。 階乗は数学の様々な場面に出現するが、特に組合せ論、代数学、解析学などが著しい。階乗の最も基本的な出自は 個の相異なる対象を一列に並べる方法（対象の置換）の総数が 通りであるという事実である。この事実は少なくとも12世紀にはインドの学者によって知られていた。は1677年にへの応用として階乗を記述した。再帰的な手法による記述の後、Stedman は（独自の言葉を用いて）階乗に関しての記述を与えている: 感嘆符(!)を用いた、この "" という表記は1808年にによって発明された。 階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。.

組合せ数学と階乗 · 組合せ爆発と階乗 · 続きを見る »