離散数学

2013-03-20T14:58:26Z

118.8.158.28: 日本語が少しおかしいところの訂正

'''離散数学'''（りさんすうがく、[[英語]]：discrete mathematics）とは、原則として離散的な（言い換えると[[連続]]でない、とびとびの）対象をあつかう[[数学]]のことである。'''有限数学'''あるいは'''離散数理'''と呼ばれることもある。

[[グラフ理論]]、[[組合せ数学|組み合わせ理論]]、[[最適化問題]]、[[計算幾何学]]、[[プログラミング (コンピュータ)|プログラミング]]、[[アルゴリズム|アルゴリズム論]]が絡む<ref>秋山仁・R.L.Graham　『入門有限・離散の数学1　離散数学入門』、朝倉書店、1993年、「はじめに」より</ref>応用分野で、その領域を包括的・抽象的に表現する際に用いられることが多い。またもちろん離散数学には[[数論|整数論]]が含まれるが、初等整数論を超えると解析学などとも関係し（解析的整数論）、離散数学の範疇を超える。

== 離散数学の内容 ==
離散数学の中核を成す分野として次の2つが挙げられる。
* [[組合せ数学|組合せ論]]
* [[グラフ理論]]

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

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

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

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

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* [[根上生也]]　『情報数学講座3　離散構造』、[[共立出版]]、1993年
* [[秋山仁]]・R.L.Graham　『入門有限・離散の数学1　離散数学入門』、[[朝倉書店]]、1993年
* [[惠羅博，小川健次郎，土屋守正，松井泰子]] 『離散数学』、 [[横浜図書]]

== 関連項目 ==
* [[デジタル]]

{{DEFAULTSORT:りさんすうかく}}
[[Category:離散数学|*]]
[[Category:数学に関する記事]]

Wikippe - 利用者の投稿記録 [ja]

離散数学