大学学部レベル質問スレ 19単位目

1 名前：１３２人目の素数さん mailto:sage [2022/08/04(木) 23:29:28.02 ID:0Ho6Owof.net] 大学で習う数学に関する質問を扱うスレ ・質問する前に教科書や参考書を読むなりググるなりして ・ただの計算は wolframalpha.com ・数式の表記法は mathmathmath.dote ra.net ・質問のマルチポストは非推奨 ・煽り、荒らしはスルー ※前スレ 大学学部レベル質問スレ 18単位目 https://rio2016.5ch.net/test/read.cgi/math/1651147986/ 705 名前：１３２人目の素数さん [2022/10/24(月) 10:59:27.70 ID:+y5g9lSl.net] 調和級数を知らなかった……お恥ずかしい…… Σ1/nは発散するので有限個の項を抜いただけのΣ1/(n+i)も発散する、と 調和級数を使わずにΣ1/(n+i)単体で証明する方法とかって他にありますかね？ コーシーもダランベールも使えないので難しいですか 706 名前：１３２人目の素数さん [2022/10/24(月) 11:04:38.27 ID:ZMzmMyLF.net] >>676 >>663がご立派な方からのご指南であることも論を俟ちませんね 707 名前：１３２人目の素数さん [2022/10/24(月) 11:05:05.66 ID:nK7uX7AC.net] >>680 >>Σ1/nは発散するので有限個の項を抜いただけのΣ1/(n+i)も発散する iは自然数であって虚数単位ではなかった？ 708 名前：１３２人目の素数さん [2022/10/24(月) 11:13:53.19 ID:+y5g9lSl.net] >>682 iは虚数単位です あれ虚数単位だと有限個の項を抜いて調和級数になるわけじゃない……？ 頭がごちゃごちゃになってきた…… 709 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 12:07:43.74 ID:GwN+2kc1.net] 気持ち悪い文末の「…」をNGにした 710 名前：１３２人目の素数さん [2022/10/24(月) 12:41:11.28 ID:+y5g9lSl.net] >>684 癖でつけてました不快にさせてすみません 711 名前：１３２人目の素数さん [2022/10/24(月) 13:12:20.23 ID:WhN3UlUK.net] …のかわりに(´・ω・`)使うとキモさがパワーアップしていいよ 712 名前：１３２人目の素数さん [2022/10/25(火) 09:30:37.43 ID:PmjaftZ2.net] 二項分布B(n, p)がnが大きいとき、正規分布で近似できるという定理を証明するのに必要な 予備知識は何ですか？ 713 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 09:39:22.89 ID:wusYNZro.net] Levyの反転公式とか 714 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 09:41:08.17 ID:wusYNZro.net] イヤ, crtではなくて2項分布限定ならstiringの公式だけでもなんとかなるか 715 名前：１３２人目の素数さん [2022/10/25(火) 10:17:52.70 ID:PmjaftZ2.net] >>688-689 ありがとうございました。 純粋に解析学の結果だと思いますが、微分積分の本で演習問題か何かで証明している本はないですか？ 716 名前：１３２人目の素数さん [2022/10/25(火) 10:36:54.58 ID:R1CUsz0D.net] >>687 個数が多いと独立に近づいていく 717 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 10:47:35.28 ID:wusYNZro.net] >>690 Levy の反転公式はちょっと高度、教科書でさがすなら数学科の専門課程で読むレベルの教科書当たらないと難しい Stiringの公式はそうでもない、般教のレベルの教科書に載ってる 具体的にと言われると俺の読んだ教科書はもう絶版してる でも今の時代なら今のキーワードでググればアホほどネットに転がってる 718 名前：１３２人目の素数さん [2022/10/25(火) 13:04:36.00 ID:PmjaftZ2.net] >>691-692 ありがとうございました。 >>692 ネットで探してみます。 719 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 16:42:04.11 ID:NushXwQu.net] 三行目の式変形がわからなくて困ってる　どうしたら1/xが出てくるんだ 初歩的な質問で申し訳ない https://imgur.com/a/99y9zEX 720 名前：１３２人目の素数さん [2022/10/25(火) 17:11:46.34 ID:PmjaftZ2.net] 甘利俊一さんの情報理論の本ですね。 721 名前：１３２人目の素数さん [2022/10/25(火) 17:16:27.43 ID:PmjaftZ2.net] f(x + ε * x) = f(1 + ε) + f(x) f(x + ε * x) - f(x) = f(1 + ε) この両辺を ε * x で割ると、 [f(x + ε * x) - f(x)] / [ε * x] = (1/x) * f(1 + ε) / ε となる。 ということだと思います。 722 名前：１３２人目の素数さん [2022/10/25(火) 18:05:16.84 ID:PmjaftZ2.net] 以下のコードが配列 A を昇順にソートすることを証明せよ。 for i in range(N): 723 名前： ■■for j in range(N): ■■■■if A[i] < A[j]: ■■■■■■swap(A[i], A[j]) [] [ここ壊れてます] 724 名前：１３２人目の素数さん [2022/10/25(火) 18:24:25.90 ID:J3r5rMEr.net] >>694 左辺の分母εxじゃん 725 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 19:35:35.09 ID:x3m7p8p/.net] for loop でi はrange(A)(だよね)の小さい方から呼ばれるのは確定してるん？ 726 名前：１３２人目の素数さん [2022/10/25(火) 19:39:56.71 ID:PmjaftZ2.net] >>699 C++風に書くと、以下のコードになります。 vector<int> A(N); for (int i = 0; i < N; ++i) { ■■cin >> A[i]; } for (int i = 0; i < N; ++i) { ■■for (int j = 0; j < N; ++j) { ■■■■if (A[i] < A[j]) { ■■■■■■swap(A[i], A[j]); ■■■■} ■■} } 727 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 20:41:41.34 ID:qRcqF8Uu.net] >>700 Aのサイズに関するinduction ♯A = 1なら自明 ♯A<Nではよいとして♯A=Nとする i = 1 で内ループが終わった状態ではA[1]に最大元が移動する ここでi:2〜N-1でのステップでj=Nとなる時点では必ずA[i]は最大元が入ることになるので事実上A[N]は動かない よってループはサイズがひとつ小さいサイズのArrayに対して行なっている操作と同じになる、ただしiが2〜しか走っていないが、仮に改めてもう一度i:1〜N-1で走らせてもA[1]に最大元が入っている状態からスタートなのでどのみちi=1の時点では何も起こらない事に注意する よってi:2〜N-1まで走らせた時点で帰納法の仮定からA[1]〜A[N-1]は昇順に並んでいる この状態で最後のi=Nのステップで全て昇順になる事は容易である□ 728 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 00:30:01.50 ID:P3jpJ7pP.net] 補題　長さNのarray A[0]〜A[N-1]においてA[0]〜A[N-2]は昇順であるとする ここに次のコードをapplyすると全体が昇順にソートされる i = N-1; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } (∵) Nについての帰納法 N=1なら自明 N<Mで成立するとしてN=Mとする j=0での処理を終えた時点でA[0]が最小元となるのは自明 またA[1]〜A[N-2]は昇順でここにi=1から始まるコードをapplyすればA[1]〜A[N-1]は帰納法の仮定により昇順にソートされる□ 729 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 00:30:40.36 ID:P3jpJ7pP.net] 主張の証明 ♯A < N で成立すると仮定して♯A = Nとする コードを次のように変更しても結果は変わらない i = 0; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } for (int i = 0; i < N-1; ++i) { 　for (int j = 0; j < N-1; ++j) { 　　if (A[i] < A[j]) { 　　　swap(A[i], A[j]); 　　} 　} } i = N-1; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } (∵ 元のコードでi=0の処理が終わった時点でA[0]には最大元が入っている 一方で各1≦i<N-1にたいしてj<N-1の処理が終わった段階ではA[i]にはA[0]〜A[N-2]の最大元が入る よってこの時点でA[i]には全体の最大元が入ることになる よって続くj=N-1のときの処理ではifの条件は常にFalseであり処理が行われる事はない よって1≦i<N-1, j=N-1の時の処理は省いても結果は変わらない) ここで帰納法の仮定により改変後のコードにおいて最後のループを始める前の時点ではA[0]〜A[N-2]は昇順になっている この状態で最後のループによって昇順になる事は既に補題で示されている□ 730 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 04:40:11.07 ID:cHlveV8v.net] >>696, 698 ありがとうございます、助かりました 731 名前：１３２人目の素数さん [2022/10/26(水) 06:56:09.62 ID:Vss1j+8B.net] >>701-703 多分正解だと思いますが、正当性を記述するのって面倒ですね。 732 名前：１３２人目の素数さん [2022/10/26(水) 10:15:21.88 ID:Vss1j+8B.net] >>697,700 著者の解答は以下です： github.com/E869120/math-algorithm-book/blob/main/editorial/chap3-6/chap3-6.pdf これって間違っていませんか？ 733 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 10:37:34.59 ID:rvp30j2k.net] まぁダメやろな i = 0〜N-2まで動く時もjは0〜N-1まで動いてしまうためにi:0〜N-2の時の動作結果は“帰納法の仮定”を適用できんからな 734 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 11:38:43.03 ID:8peJPiGV.net] >>706 735 名前： だいたい合ってるよ 細かいこと言うならこんな感じ↓ i=I-1の ”内側 j ループ終了の” 時点で、A[t−1] ≦ A[I] ”<” A[t]のとき .. . . • j=t+1,..., I−1でもswapされる。 結果は同じだが A[I]=A[j] の時は swapされない swap過程で A[1]≦A[2]≦...≦A[I-1] 順序に変化は起きないことは明らか • それ以降: A[I] の値が増える可能性はあるが、減ることはない j=I−1 直後は A[I-1] ≦ A[I] とは限らないが jループ終了後は A[I] に最大値が入ることは明らか その結果 A[1]≦A[2]≦...≦A[I-1] ≦A[I] となる. [] [ここ壊れてます] 736 名前：708 mailto:sage [2022/10/26(水) 14:06:51.89 ID:8peJPiGV.net] > j=I−1 直後は A[I-1] ≦ A[I] とは限らないが ↑ 少し訂正 I = 0 の場合: 明らかに内側 j ループ終了時点で A[I] に最大値が入る. I > 0 の場合: 内側 j ループ ”処理開始”時点で A[I-1] に最大値が入っている(※帰納法の仮定に加える)ので j=I-1 で swap が起きたら A[I-1] < A[I] , 起きなければ A[I-1] = A[I] のまま変わらない. いずれにしろ j=I-1 ”処理終了”時点で　A[I-1] ≦ A[I] が確定して A[I] に最大値が入る. j=I 以降で swap は生じない. 737 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 18:28:46.82 ID:i/+rfYjL.net] まぁ二重の帰納法で受験数学の問題だとかなり難問だよな 738 名前：１３２人目の素数さん [2022/10/26(水) 20:47:56.30 ID:KTa78anx.net] >>705 プログラムの正当性の証明を与える理論があったような気がする 帰納法で証明するなら 「内側のループ抜けた時点でそこまでのソートが終了している」 という命題にするのね 739 名前：１３２人目の素数さん [2022/10/27(木) 20:03:51.08 ID:dVXdGNpU.net] atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bi f : N → N を f(n) が n の約数の個数であるような関数とする。 1 * f(1) + 2 * f(2) + … + n * f(n) の値を O(n) で出力する方法を述べよ。 740 名前：１３２人目の素数さん [2022/10/27(木) 20:04:43.63 ID:dVXdGNpU.net] >>707-711 ありがとうございました。 741 名前：１３２人目の素数さん [2022/10/27(木) 20:06:25.53 ID:dVXdGNpU.net] リンク先を間違えました。訂正します。 atcoder.jp/contests/math-and-algorithm/tasks/abc172_d f : N → N を f(n) が n の約数の個数であるような関数とする。 1 * f(1) + 2 * f(2) + … + n * f(n) の値を O(n) で出力する方法を述べよ。 742 名前：１３２人目の素数さん [2022/10/27(木) 20:56:35.09 ID:dVXdGNpU.net] あ、分かりました。 農{d = 1}^{n} d * (floor(n/d) * (floor(n/d) + 1)) / 2 これで Θ(n) で計算できますね。 743 名前：１３２人目の素数さん mailto:sage [2022/10/27(木) 21:49:23.36 ID:TYQqpd07.net] >>715 どうしてこれで計算できるのか、誰か教えてください 744 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 01:21:30.81 ID:lv2p8O4G.net] 1 * f(1) + 2 * f(2) + … + n * f(n) = Σ[ m ≦ n ]Σ[ d ≦ n, d | m ] m = Σ[ d ≦ n ]Σ[ m ≦ n, d | m ] m = Σ[ d ≦ n ]( d + 2d + 3d + ... + ⌊n/d⌋d ) = Σ[ d ≦ n ] d⌊n/d⌋(⌊n/d⌋+1)/2 745 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 08:04:37.22 ID:7H6AX/lv.net] >>717 ありがとうございます、理解できました Σ[ m ≦ n ]Σ[ d ≦ m, d | m ] m = Σ[m ≦ n]Σ[d ≦ m] m * θ(d|m) { θ(expr) := expr ? 1 : 0 } = Σ[m ≦ n]Σ[d ≦ n ] m * θ(d|m) = Σ[d ≦ n]Σ[m ≦ n] m * θ(d|m) =Σ[d ≦ n] { d + 2d + ... + floor(n/d)*d } = ... 746 名前：１３２人目の素数さん [2022/10/28(金) 09:47:19.16 ID:Fb3X/X4M.net] 以下は、高校の教科書からの引用です。 (1) 次に、 U の中に、2つの事象 A, B がある場合を考えよう。 このとき、次のような事象を考えることが多い。 A, B がともに起こる事象 A ∩ B A, B の少なくとも一方が起こる事象 A ∪ B ----------------------------------------------------------- (2) 1枚の硬貨を投げる試行を T_1、1つのサイコロを投げる試行を T_2 とし、試行 T_1 と試行 T_2 を組み合わせた試行を考える。 この試行において、 硬貨では表が出る事象を A, サイコロでは 1 または 2 の目が出る事象を B とするとき、確率 P(A ∩ B) を求めてみよう。 ----------------------------------------------------------- (1)では、全事象 U というのがあって、 A, B はその中の事象です。 (2)では、 T_1 に対応する全事象 U_1 があり、 T_2 に対応する 全事象 U_2 があります。 A は U_1 の中の事象であり、 B は U_2 の中の事象です。それにもかかわらず、「確率 P(A ∩ B) を求めてみよう」 などと平然と書いています。 A ∩ B などというものは考えられないにもかかわらず。 747 名前：１３２人目の素数さん mailto:age [2022/10/28(金) 10:11:13.31 ID:lqOqCRZy.net] このスレを見ていると 3流の国立や私立大の理系への考えが変わったわ。 「3流大でも入学後にちゃんと勉強して単位をとってたら それなりに出来るようになるんやなぁ」 って。 であるならば、入学試験の6科目の受験勉強、 あれは何だったんだろうな。 過剰な学力の訓練・要求に思えてきた。 だって入学後にちゃんと大学レベルの数学、解析学についていけるやん？ ち、ちなみに謙虚な神戸大卒 TOEIC700です…( ; ‘ω‘) ﾊｧﾊｧ 748 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 10:25:55.37 ID:7H6AX/lv.net] >>719 高校数学は変な縛りがあるんで執筆者も雑なのは分かってて書いてると思います この場合の全事象 U は積空間の U_1 × U_2 に 事象 A は A × U_2, 事象 B は U_1 × B に読み替えるべきですね 749 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 10:30:44.97 ID:jgM6IsNM.net] >>720 三流大学や四流大学と認定される大学の学生さんが、ちゃんと学べていないのは、 入試ができない人が学ぶことができないというよりもむしろ、 「三流や四流の自分が勉強しても仕方ない」という意識を持つからだろうね 実際、日本の学力テストが素質を測れるという根拠は存在しない これは日本の人材の損失で、少子化で更に人材が減っていく以上、三流や四流みたいな固定観念を撤廃していかない限り日本が他の国々に差をつけられていくのは必定だと思う 750 名前：１３２人目の素数さん mailto:age [2022/10/28(金) 11:40:23.68 ID:lqOqCRZy.net] >>722 一般入試組が受験オタク、学力厨という事実が 明るみになってきてますし 今はAO入試・指定校推薦が 入学者の半分近くっていう大学も多いですね。 (下手したら、学力の高いはずの人々が 大学の成績でAO・指定校などの学力の低めの人に負けている場合さえある) 751 名前：１３２人目の素数さん [2022/10/28(金) 11:57:16.81 ID:FpKcJleB.net] また部外者君か 752 名前：１３２人目の素数さん [2022/10/28(金) 12:02:15.89 ID:FpKcJleB.net] >>723 AOと推薦がどうしようもないのは2流3流大の場合 1流と4流では大して違いない ていうか４流では入試機能しないからな 753 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 12:32:54.51 ID:zGG7ayBU.net] >>723 東北大、早稲田大で、AO入学者のほうが成績が良いというデータもあるしね 成績が最もいいのはAO入学者　東北大、早稲田大の内部資料で判明 https://www.asahi.com/edua/article/14540038 入試のあり方を今一度見直したほうが良いだろうな、 共通一次が1979年に導入されて以降見直しが殆どないのもどうかと思うし 754 名前：１３２人目の素数さん [2022/10/28(金) 12:36:44.59 ID:FpKcJleB.net] >>726 ここでやる話題ではないし 1流大のAOによい学生が集まるのは当然 枠が増えれば低劣になるだろうも当然 755 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 12:44:56.72 ID:zGG7ayBU.net] >>727 例えば京都大学の学生数が22,785で、 イギリスのオックスフォード 756 名前：大学が11,930 イギリスの人口が6733万人で日本の1/2しかないことを考えると、 オックスフォード大学はかなり京都大学より枠を広げてるわけだけど、 間違いなく質はオックスフォード大学のほうが京都大学より上だよね？ [] [ここ壊れてます] 757 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 12:48:20.49 ID:zGG7ayBU.net] オックスフォード大学は京都大学と同じくらいの枠だな、すまん とはいえ、同じくらいの枠でオックスフォード大学のほうが京都大学よりずっと上ということは、 やはり京都大学の学生さんに優秀な人が集まっているとは言えないと思う それはつまり、入試という物差しが優秀さを測ってはいないということだよね 758 名前：１３２人目の素数さん [2022/10/29(土) 09:18:23.92 ID:dxAYdFmh.net] K を自然数とする。 M を K の倍数の集合とする。 N を自然数の集合とする。 f : N → N を f(n) が n を10進法で表したときの各桁の和であるような関数とする。 min {f(n) | n ∈ M} を O(K * log(K)) で計算する方法を述べよ。 759 名前：１３２人目の素数さん [2022/10/29(土) 09:19:36.57 ID:dxAYdFmh.net] N を自然数の集合とする。 K ∈ N とする。 M ⊂ N を K の倍数の集合とする。 f : N → N を f(n) が n を10進法で表したときの各桁の和であるような関数とする。 min {f(n) | n ∈ M} を O(K * log(K)) で計算する方法を述べよ。 760 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 09:37:37.51 ID:vKZvh9tp.net] g(K) = min {f(n) | n ∈ M} = 1 761 名前：１３２人目の素数さん [2022/10/29(土) 10:06:22.86 ID:dxAYdFmh.net] >>732 不正解です。 762 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 10:18:10.55 ID:aLXm9oeN.net] >>732 おっと、そりゃそうだ 確認だけど四則演算はO(1)でいいんやな？ 763 名前：１３２人目の素数さん [2022/10/29(土) 11:09:16.64 ID:dxAYdFmh.net] >>734 はい。 764 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 17:33:04.91 ID:FyC0Ec0W.net] まだdebugしてないけど for(i=0; i<K; i++) A[i] = K; for(i=0; i<K; i++){ 　for(f=1; f<10; f++){ 　　A[ (10^i * f)%K ] 　　　= min ( A[ (10^i * f)%K ], f ); 　} } m = 0; while(A[0]>m){ 　i = 0; 　for(j=0; j<K; j++){ 　　if( A[j]>m && A[j]<A[i] ) i=j; 　} 　m=A[i]; 　for(f = 1; f<10; f++){ 　　for(j=0; j<K; j++]{ 　　　A[ ( i+10^j * f)%K ] 　= min(A[( i + 10^j * f )%K], A[ i ]+f ); 　　} 　} } 765 名前：１３２人目の素数さん [2022/10/29(土) 17:42:21.55 ID:dxAYdFmh.net] >>736 書きませんでしたが、 >>731 は、以下の問題です。 atcoder.jp/contests/math-and-algorithm/tasks/arc084_b 766 名前：１３２人目の素数さん [2022/10/29(土) 17:43:03.30 ID:dxAYdFmh.net] いままで見た競技プログラミングの問題の中でも、いい問題だと思いました。 767 名前：１３２人目の素数さん [2022/10/29(土) 17:49:33.11 ID:dxAYdFmh.net] >>736 コードの内容は見ていませんが、最終的に答えは A のどの要素に入っているんですか？ 768 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 17:51:14.90 ID:FyC0Ec0W.net] >>739 A[0] 769 名前：１３２人目の素数さん [2022/10/29(土) 18:07:44.42 ID:dxAYdFmh.net] ideone.com/GSFtad 間違っているようです。 770 名前：１３２人目の素数さん [2022/10/29(土) 18:11:45.06 ID:mKrwvqce.net] プログラミングの人居着いちゃったけど 出来たら別スレでやってくれないかな 771 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 18:55:32.41 ID:FyC0Ec0W.net] せやね プログラミングスレの方がいいかもね 772 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 19:12:08.74 ID:FyC0Ec0W.net] 書いてきた https://mevius.5ch.net/test/read.cgi/tech/1624028577/845 プログラミングのお題スレ Part20 773 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 02:36:16.07 ID:jzYKBiql.net] そもそもコレ本当にO(Klog(K))でできるん？ グラフのサイズV = K, E = K²だよな？ 探索アルゴリズムこのサイズのグラフでKlog(K)のやつはグクっても見つからないんだけど 774 名前：１３２人目の素数さん [2022/10/30(日) 04:55:48.16 ID:7xF2sv+k.net] どのようなグラフを考えているのか知りませんが、 #E = 10 * K のグラフを考えるのが普通ではないでしょうか？ 775 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 09:56:14.75 ID:y/CG6F55.net] >>748 イヤ、普通に V = {0,1,2,3,4,...} E = {(p,q,f) ∈ V×V | f∈{1,2,..,9 }, ∃e∈ℤ, p-q ≡ f×10ᵉ ( mod K ) } w((p,q,f)) = f で1〜9の重� 776 名前：ﾝ付き有向グラフの単経路問題 コレが1番普通だと思うけど これだとちょっと必然的に♯E = O(K²)になるよ [] [ここ壊れてます] 777 名前：１３２人目の素数さん mailto:age [2022/10/30(日) 10:08:37.85 ID:AezHc4Ib.net] 最近、スレのレベルが落ちてるんちゃうかな？ 778 名前：１３２人目の素数さん [2022/10/30(日) 10:14:02.25 ID:e4jmSuJH.net] ウィキペディアに、累次積分(逐次積分)と多重積分が違うものだと書かれているのですが、本当ですか？ > 逐次積分の概念を考えるに当たり一つ重要な点としては、これは多重積分とは原則として異なる概念であるということが挙げられる。すなわち、一般にはこの二つは異なるのであるけれども、それでも十分緩やかな条件下でこれらが一致することを主張するフビニの定理が知られている。 https://ja.m.wikipedia.org/wiki/%E9%80%90%E6%AC%A1%E7%A9%8D%E5%88%86 何が違いますか？ 779 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 10:17:10.47 ID:y/CG6F55.net] >>749 何が違うも何も明らかに定義違うやん 両方の定義書いてみればいい 780 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 10:26:31.96 ID:y/CG6F55.net] >>746 そもそもホントにO(Klog(K))のプログラム作って実証実験した？ どっかのフリーideにうpしてよ 781 名前：１３２人目の素数さん [2022/10/30(日) 10:29:00.44 ID:7xF2sv+k.net] >>747,751 github.com/E869120/math-algorithm-book/blob/main/editorial/chap4-5/chap4-5.pdf 問題5.4.8の解答を見てください。 782 名前：１３２人目の素数さん [2022/10/30(日) 10:30:05.71 ID:7xF2sv+k.net] 訂正します： >>747,751 github.com/E869120/math-algorithm-book/blob/main/editorial/chap4-5/chap4-5.pdf 問題4.5.8の解答を見てください。 783 名前：１３２人目の素数さん [2022/10/30(日) 10:31:32.58 ID:7xF2sv+k.net] #E = 10 * K - 1 ダイクストラのアルゴリズムを使います。 784 名前：１３２人目の素数さん [2022/10/30(日) 10:36:47.46 ID:7xF2sv+k.net] ダイクストラのアルゴリズムは、priority queueを使うバージョンです。 785 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 11:30:00.48 ID:pXesArml.net] 14x715=10010. 786 名前：１３２人目の素数さん [2022/10/30(日) 11:39:48.34 ID:j/LQV7BO.net] 高校数学スレの次はここを糞スレにするつもりか 787 名前：１３２人目の素数さん [2022/10/30(日) 11:56:21.17 ID:NTLeY4Kt.net] >>750 定義は同じだと思いますけど 積分記号が重なってるという風に存在論的に見るか、逐次という風に操作的に見るかという捉え方の違いなだけで 788 名前：１３２人目の素数さん [2022/10/30(日) 12:02:45.26 ID:TFu5GMWG.net] >>758 いや全然違いますけどね 重積分可能でも逐次積分できないものもありますよ 789 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 12:42:23.39 ID:4zjSqvRJ.net] >>754 イヤ、解答ざっと見る限り♯E=O(K²)なんだけど？ ♯Eはある一点から出てる辺の本数じゃないよ？ グラフ全体の辺の本数だよ？ そしてダイクストラアルゴリズムの計算量でO(√♯E)ですむアルゴリズムなんかないやろ？ 790 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 12:43:54.16 ID:4zjSqvRJ.net] >>758 じゃあ同じと思っとけばいいよ 教科書に書いてある話全部信用しなくてもいい 791 名前：１３２人目の素数さん [2022/10/30(日) 12:59:21.82 ID:7xF2sv+k.net] 各点から多くとも 10 本の辺が出ています。 そして、点の数は K です。 792 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 13:03:34.07 ID:LJk7NKkj.net] >>762 なんでやねん？ 例えば同じ3をついかするのでも 302,3002,3002,.... は全部mod Kの類は違うやん？ もし逆に「そこは0を使えばいい」だと今度は0が何個使った何桁のKの倍数がゴールか決まらないから単経路問題にならない 793 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 13:15:41.54 ID:zpQpukVT.net] 例えばK=7の場合、頂点は0₁,0₂,1,2,3,4,5,6にして 1を追加する重さ1の辺は 0ᵢ→1,0ᵢ→3,0ᵢ→2 (それぞれ1×10³ᵐ、10×10³ᵐ、100×10³ᵐを追加する事に対応) の3本を追加しないといけない コレで頂点数が8、辺が24 794 名前：本のグラフになり、この場合0₀から0₁への単経路問題になる 辺の数を10本のグラフにすると 2桁の場合の解、3桁の場合の解、4桁の場合の解、‥の各々はO(Klog(K))でもとまるけどあらかじめ何桁の解が最小なんて導出しとくとか無理やろ [] [ここ壊れてます] 795 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 13:31:52.56 ID:LSUqtQrg.net] おっと間違った 0ᵢ→1,0ᵢ→3,0ᵢ→2 ,0ᵢ→6,0ᵢ→4,0ᵢ→5 の6本 重さが1〜6の辺が各頂点から出てるから辺の数は48本ね ちなみにK=7の場合4桁の1001が最小でg(7)=2 あらかじめ4桁である事がわかっていればいいけどそうでなければより小さくなる可能性が残っている限りずっと探索を続けることになる 2が最小値の場合10のℤ/Kℤ*の位数のときの桁数になるけどそれはO(K)の大きさなのでそこまで探索を打ちきれない 796 名前：１３２人目の素数さん [2022/10/30(日) 13:50:28.19 ID:xc3srulk.net] ここまで相違点ゼロ 797 名前：１３２人目の素数さん [2022/10/30(日) 14:28:45.75 ID:A2wkNOX4.net] 0〜x の範囲における　t^(2n+2）/1-t^2 をtで積分出来る方いますか？ tは+1、-1とは異なる実数。nは0以上の整数。 -1<x<1を満たす実数xとします。 798 名前：１３２人目の素数さん [2022/10/30(日) 14:40:55.42 ID:B+/I78Ek.net] はい、います 799 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 16:04:38.18 ID:P5Rx2O31.net] はい終わり 次の方どうぞ 800 名前：１３２人目の素数さん [2022/10/30(日) 17:00:02.00 ID:jc+BtoLV.net] >>767 商と余りに分けて あまりの分は部分分数に分けて 801 名前：１３２人目の素数さん [2022/10/30(日) 17:01:56.13 ID:jc+BtoLV.net] >>758 それを定義が違うというのでは？ 802 名前：１３２人目の素数さん [2022/10/30(日) 18:40:16.11 ID:/BpMF6dC.net] >>749 そのリンク先に積分順序を変えたら逐次積分の値が変わる例が書いてあるじゃないか。 何がわからないのかわからない 803 名前：１３２人目の素数さん mailto:sage [2022/10/31(月) 12:15:14.42 ID:o9f6zkDT.net] wikiのRudinの例面白いな x止めるごとにyの関数として連続で可積分 、y止めるごとにxの関数として連続で可積分 さらに逐次積分も可能で結果は1と0 議論は全部般教の数学レベルでルベーグ積分もクソもないレベル なんなら受験で出せるレベルかも 804 名前：１３２人目の素数さん [2022/10/31(月) 19:03:35.25 ID:UHpvprLi.net] (1) ∃N s.t. ∀n > Nに対してa_n<α+ε (2) 無数の番号nに対してα-ε<a_n (1),(2)が成り立てば、αは{a_n}の上極限であることを証明せよ。 以下の解答は間違っていませんか？ 正のεを任意にとる。(1)より、∃N s.t. ∀n > Nに対してa_n<α+εが成り立つ。 n≧N+1⇒a_n<α+εが成り立つ。 ∴sup{a_{N+1}, a_{N+2},…}≦α+ε i≧N+1ならば、sup{a_i, a_{i+1},…}≦sup{a_{N+1}, a_{N+2},…}≦α+ε iを任意にとる。もしも、sup{a_i, a_{i+1},…}≦α-εが成り立てば、(2)が成り立たない。 ∴α-ε<sup{a_i, a_{i+1},…} 以上より、i≧N+1ならば、α-ε<sup{a_i, a_{i+1},…}≦α+ε ∴lim sup{a_i, a_{i+1},…} = α 805 名前：１３２人目の素数さん [2022/10/31(月) 20:27:35.34 ID:+9+7HneH.net] 数学に興味のない生徒に興味を持たせるにはどうしたらいいでしょうか？(小中高校どれでも)

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef