Skip to main content

離散数学 目次 離散数学の内容 離散数学で使われる解決方法 脚注 参考文献 関連項目 案内メニュー落合 秀也 離散数学

離散数学数学に関する記事


英語連続数学グラフ理論組み合わせ理論最適化問題計算幾何学プログラミングアルゴリズム論整数論点線辺グラフの彩色行列集合順列組合せ論理証明帰納法漸化式数列ゲーム理論マルコフ連鎖社会選択理論投票理論ビンパッキング問題記号論アルゴリズムトポロジー












離散数学




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






ナビゲーションに移動
検索に移動


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


グラフ理論、組み合わせ理論、最適化問題、計算幾何学、プログラミング、アルゴリズム論が絡む[1]応用分野で、その領域を包括的・抽象的に表現する際に用いられることが多い。またもちろん離散数学には整数論が含まれるが、初等整数論を超えると解析学などとも関係し（解析的整数論）、離散数学の範疇を超える。




目次





  • 1 離散数学の内容


  • 2 離散数学で使われる解決方法


  • 3 脚注


  • 4 参考文献


  • 5 関連項目




離散数学の内容


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


  • 組合せ論

  • グラフ理論

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


  • 解決法は存在するか？

  • どれくらいの数の解決法があるか？

  • 最適の解決法があるか？

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


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


  • 路は存在するか？

  • どれくらいの数の路があるか？

  • 最適の路を見つけられるか？

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


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



離散数学で使われる解決方法


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



脚注




  1. ^ 秋山仁・R.L.Graham　『入門 有限・離散の数学1　離散数学入門』、朝倉書店、1993年、「はじめに」より



参考文献



  • 根上生也　『情報数学講座3　離散構造』、共立出版、1993年


  • 秋山仁・R.L.Graham　『入門 有限・離散の数学1　離散数学入門』、朝倉書店、1993年


  • 惠羅博，小川健次郎，土屋守正，松井泰子 『離散数学』 、 横浜図書

  • 落合 秀也 離散数学


関連項目


  • デジタル



「https://ja.wikipedia.org/w/index.php?title=離散数学&oldid=72551427」から取得













案内メニュー



























(RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.028","walltime":"0.033","ppvisitednodes":"value":101,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":146,"limit":2097152,"templateargumentsize":"value":0,"limit":2097152,"expansiondepth":"value":5,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":347,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 4.561 1 Template:Reflist","100.00% 4.561 1 -total"],"cachereport":"origin":"mw1262","timestamp":"20190825003739","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"u96e2u6563u6570u5b66","url":"https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E6%95%B0%E5%AD%A6","sameAs":"http://www.wikidata.org/entity/Q121416","mainEntity":"http://www.wikidata.org/entity/Q121416","author":"@type":"Organization","name":"Contributors to Wikimedia projects","publisher":"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2003-06-12T14:56:45Z","dateModified":"2019-04-29T01:39:52Z"(RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":134,"wgHostname":"mw1249"););
-