0001１３２人目の素数さん2010/09/19(日) 21:27:42
有限的で離散的な構造や事象を扱う、離散数学のスレです。
この分野は情報技術やコンピューターと密接な為、情報数学も対象とします。
■離散数学に属する主な分野
・グラフ理論
・組合せ論
・マトロイド理論
・デザイン理論
・離散幾何学
■離散数学の定義（参考）
・離散数学 - Wikipedia
ttp://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E6%95%B0%E5%AD%A6
・離散数学で変わる数学教育
ttp://www.ngm.edhs.ynu.ac.jp/negami/document/discmath/discmath.html
0748１３２人目の素数さん2014/12/18(木) 23:48:46.37
差分和分
0749１３２人目の素数さん2015/03/23(月) 10:42:43.13ID:F5qddR+V
グラフの辺の種類が2種類ある場合
グラフ理論ではどうやって扱いますか？
0750１３２人目の素数さん2015/03/28(土) 17:24:38.28ID:Lfr8N1aI
代数・幾何・数論の問題にグラフの構造が見出され、しかもグラフ論的考察によって意味のある結果が得られた
という例はありませんか？
0751１３２人目の素数さん2015/03/28(土) 20:35:29.95ID:g+NJ+mow
電気回路解析かな
音楽用に色々とデジタルフィルタを設計したいと思ってこのページを読んでるんだがな(ex ローパス、ハイパス、スクリーム、コム等々)
http://www.ic.is.tohoku.ac.jp/~swk/lecture/yaruodsp/toc.html
5章まで読んでそろそろ頭が追い付かなく・・・(絶命)
やっぱこれz変換まで全部理解しないと無理ですかね？ 0753１３２人目の素数さん2015/04/18(土) 22:09:36.24ID:0P3y7//s
0754１３２人目の素数さん2015/04/22(水) 20:46:49.62ID:Cf2TBDii
離散数学の入門書、お勧めを教えて下さい。
0756１３２人目の素数さん2015/04/29(水) 02:09:25.41ID:FdMLhvpF
「離散ガール」
世界を変える魔法！ アルゴリズミ子研究所 - NHK
ttp://www4.nhk.or.jp/P3285/
カーナビ編でダイクストラ法とか出てくる？
グラフ理論って実用上無意味な数学じゃね？
圏論よりも実用じゃ使えんと思うぐらいイミフだと思う
圏論はhaskellがあるから意味があるけど
グラフ理論なんてどこで使うのって思うけど反論出来る人いる？
圏論で扱う図式はグラフだから、グラフ理論は圏論のサブセット
0762１３２人目の素数さん2015/08/21(金) 17:57:23.19ID:7xlHXt9Z
>>761
だったら圏論があればいいじゃろ
グラフ理論なんて謎サブセット誰が喜ぶの？ んじゃ、代数学があれば、群論や環論とかいらないんか？
0764１３２人目の素数さん2015/08/21(金) 18:23:23.48ID:k7dziMRV
覚える必要ないじゃろ
サブセットを調べれば役に立つこともある
0766１３２人目の素数さん2015/08/21(金) 20:10:26.44ID:7xlHXt9Z
>>763
それはいるだろw
具体的な構造特定せずに証明したり新しい構造見つけるのに必須だろ
でもグラフ理論いらんだろ？
数学の中で最も役に立たない実用性が皆無だと思うのだが？ 何を釣りたいんだろうな
グラフ「理論」として語るべきことがどれだけ多くあるかは知らんが
少なくとも様々な事柄の表現方法としてグラフが用いられている以上
その枠組みを整備することに意味がないわけはないし。
まあ、彼の「実用性」という言葉の定義が何か世間と乖離してるのだろう
0768１３２人目の素数さん2015/08/31(月) 19:09:47.70ID:xfN/nvpB
モジュラリティ処理を実装したいんだけど数学と実装が細かく書いてある本ってあるのだろうか？
昨日なピザ12枚食っただろ？
今になって腹が痛くなってきたんだけど
救急病院って腹痛でも診てくれるのか？
0770１３２人目の素数さん2015/11/11(水) 13:00:38.72ID:0vAxwl0s
nビットのすべての2進数のうち、偶数個（0個も偶数個と考える）の0を含むものは
何個あるか？
という問題について質問です。
「対称性によりnビットの2進数2^n個のうち半数が0を偶数個含み、もう半数が
0を奇数個含むということに注意すれば、この問題は直ちに解ける。」
と書かれているのですが、対称性というのがよくわかりません。
説明をお願いします。
以下の本に載っている話です：
組合せ数学入門I（共立出版）
著者：
C. L. リウ
訳者：
伊理正夫
伊理由美
0771１３２人目の素数さん2015/11/11(水) 13:10:17.54ID:0vAxwl0s
Concrete Mathematicsって面白いですねー。
H_n = 1 + 1/2 + 1/3 + ... + 1/n
とすると、
H_n = log(n) + γ + 1/(2*n) - 1/(12*n^2) + ε_n/(120*n^4)
ただし、
γ=0.57721...
0 < ε_n < 1
このすごい公式を理解するのが目標です。
0772１３２人目の素数さん2015/11/11(水) 13:16:15.81ID:0vAxwl0s
0773１３２人目の素数さん2015/11/11(水) 20:34:22.38ID:0vAxwl0s
>>770
nが奇数のときには「対称性」の意味が分かるのですが、nが偶数のときには
言っている意味が分かりません。 0774１３２人目の素数さん2015/11/11(水) 20:39:37.75ID:0vAxwl0s
>>770
自分の解答は以下です。
(1+x)^n = C(n,0)*x^0 + C(n,1)*x^1 + ... + C(n, n)*x^n
x=1とすれば、
2^n = C(n,0) + C(n,1) + ... + C(n, n)
x=-1とすれば、
0 = C(n,0) - C(n,1) + ... + (-1)^n*C(n, n)
よって、
2^n = 2 * (C(n,0) + C(n,2) + ...)
2^(n-1) = C(n,0) + C(n,2) + ... 0775１３２人目の素数さん2015/11/24(火) 03:48:10.83ID:8cFrdAuA
一次合同方程式についての質問です。
2x+31≡ 7x+4(mod 12)という問題です。
正解はx=9(mod 12)なのですが，一部計算が気になります。
自分としては与式を変形すると-5x≡-27(mod12)となると思うのですが
模範解答を見てみると5x≡-27(mod 12)となっており，考え方が良く理解出来ないです。説明をお願いしたいです。以下模範解答を載せておきます
――――――――――――――
5x=-27(mod12)=9(mod12) ここに(5,12)は互いに素であるから唯一解を持ち
12=5*2+2
5=2*2+1
上式より5x=1(mod12)の解はx=5(mod12)したがって
x=9(mod12)
0776１３２人目の素数さん2015/11/24(火) 08:36:49.05ID:6g7rXDks
単なる誤植というより盛大な間違いだな
0777１３２人目の素数さん2015/11/24(火) 16:33:39.44ID:Z5L8vrvM
0778１３２人目の素数さん2015/11/27(金) 19:44:06.37ID:k8myT3ei
圏論に詳しいなら適当な問題作って圏論を使ったモデルで説明してくれない？
最近独学で勉強し始めて大雑把な理屈はつかめているんだけれど具体的にどういう条件の問題解決に向いているの？
0780１３２人目の素数さん2015/12/24(木) 12:43:53.45ID:OP6SJ76d
>>767
グラフ理論の応用と言いながら、実態としてはグラフの考え方を使っているだけで、
純粋数学として得られたグラフの「理論」を直接的に応用する機会がないことを指しているのだろう 0781１３２人目の素数さん2015/12/30(水) 17:00:40.93ID:k5Blwscu
シュテフィ・グラフがセレシュを
ランダムグラフの質問です
ノード数n,各リンク生成が等確率pの有向ランダムグラフが与えられたとき,全てのノードが強連結する確率を見積もる公式は存在しますか?
無向グラフの連結確率はよく見かけるのですが･･･
0783１３２人目の素数さん2016/03/13(日) 07:27:05.61ID:1NkoRZjS
組み合わせ論
組合せ論
どっちが正しいの？
0785１３２人目の素数さん2016/06/09(木) 17:08:33.36ID:xIJE9U0K
ビルド自動化ツールのMakeのように、これを構築するには前もってこれとこれとこれを構築しておかなければならないといった情報を元に、全体としてどういう順番で仕事をこなしていけばいいかを返すアルゴリズムを考えたいです。
用途はTODOリスト作成システムやゲームのイベントの因果関係管理です。
そのためにグラフ理論の入門レベルは勉強しといた方が良いですか？
入門書を教えてください。理系なので数式バリバリでも泣きません。
>>796
「トポロジカルソート」について調べろ
大抵のアルゴリズムの教科書にグラフの初歩とともに書いてある