離散数学

出典: フリー百科事典『ウィキペディア（Wikipedia）』

離散数学（りさんすうがく、discrete mathematics）とは、原則として離散的な（言い換えると連続でない、とびとびの）対象をあつかう数学のことである。有限数学と呼ばれることもある。ただし、整数は離散的なものだが、整数論を離散数学に含めることはあまりない。

連続的な対象は、離散的なものの近似であることが多いが、このような近似が有効なのは連続的なものとして扱うことで問題に適用できる手法が増えるからである。つまり、離散数学には固有の難しさが存在しているということである。

[編集] 離散数学の内容

離散数学の中核を成す分野として次の2つが挙げられる。

組合せ論とは「ひたすら数える」数学である。より一般的にいって、それは有限の数（とはいっても星の数ほど大きな数のときもあるが・・・）について考えるということである。その考え方の基本は

解決法は存在するか？
どれくらいの数の解決法があるか？
最適の解決法があるか？

ということについてである。

グラフ理論は、(大まかに言うと)点と線の数学である。頂点(点)とそれらの接続(辺)を調べるという単純な考え方が基本となるが、現在、とても勢いのある分野へとなった。グラフ理論の中の多くの問題は、組合せ論に関係がある。例えば、グラフで２頂点の間の路に関する問題がある。この問題は、

路は存在するか？
どれくらいの数の路があるか？
最適の路があるか？

ということになる。他にもグラフの彩色に関する問題など組合せ論との関りは深い。

他には、学校教育の中で教えられているものには行列，集合，順列・組合せ，論理と証明，帰納法と漸化式，数列などがある。それ以外にも、経済や産業の分野で応用されているものにゲーム理論、マルコフ連鎖、投票理論、ビンパッキング問題、記号論などがある。

[編集] 離散数学で使われる解決方法

離散数学でよく使われる共通の問題解決法がある。それはアルゴリズムによる解決法である。問題の構造をアルゴリズムに置換え、分析することで問題を解決する。アルゴリズムの理論は帰納的な考えを含む。つまり、アルゴリズムの理論自体も離散数学の一角を成しているといえる。アルゴリズムの理論の対象を成すのが実証論である。実証論は整数論やトポロジーなどの伝統的な数学の顕著な特徴を持っている。数学的には実証論的な証明の方が綺麗だといわれる。