OSを作ってみよう (534ﾚｽ)
OSを作ってみよう http://medaka.5ch.net/test/read.cgi/os/1046271176/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
226: Be名無しさん [sage] 03/03/21 00:18 >>223 それよりあれはどういう意味なのか誰か教えてくれ。 あれは、それを証明すること自体に意味があるってことか？ 定理自体は当たり前の話だよな。 http://medaka.5ch.net/test/read.cgi/os/1046271176/226
227: Be名無しさん [sage] 03/03/21 00:29 >>226 どうせ効果的なメモリ管理とか考えてて理論から固めようってことじゃないの？ http://medaka.5ch.net/test/read.cgi/os/1046271176/227
228: Be名無しさん [sage] 03/03/21 00:37 効率的アロケータの追求は結構なことですが 俺用語を乱発してはまるでK氏のよう http://medaka.5ch.net/test/read.cgi/os/1046271176/228
229: LightCone ◆sSJBc30S5w [sage] 03/03/21 09:19 >>226 >定理自体は当たり前の話だよな。 例えば、 >2のべき数分解定理 >『任意の非負整数nに対し、2^n未満の2のべき数の集合Aにおいて、 >Sum(A) > 2^n ならば、Aの要素のいくつかをうまく選べば、 >和を2^nに丁度等しくできる。』 が当たり前ですか？ >>228 >俺用語を乱発してはまるでK氏のよう あのページでは、新しい用語は定義してから用いるようにしています。 http://medaka.5ch.net/test/read.cgi/os/1046271176/229
230: Be名無しさん [] 03/03/21 09:22 HSP-OS http://medaka.5ch.net/test/read.cgi/os/1046271176/230
231: Be名無しさん [] 03/03/21 09:41 マジかよ・・・・。 http://webplus.site.ize.org.uk/pc/ http://medaka.5ch.net/test/read.cgi/os/1046271176/231
232: Be名無しさん [sage] 03/03/21 09:43 >>229 >が当たり前ですか？ 2^nはAminで割り切れるので 等式全体をAの最小要素Aminで割れば Amin/Amin=1になるわけで http://medaka.5ch.net/test/read.cgi/os/1046271176/232
233: LightCone ◆sSJBc30S5w [sage] 03/03/21 09:53 >>23 >2等式全体をAの最小要素Aminで割れば どの等式ですか？ >Amin/Amin=1になるわけで この文章は、X/X = 1 と同じ内容ですね。ここから何が導けますか？ http://medaka.5ch.net/test/read.cgi/os/1046271176/233
234: LightCone ◆sSJBc30S5w [sage] 03/03/21 09:55 証明1 (i) 今、Aの要素からm個の要素を選んだ集合をB(m)とし、Sum(B(m)) > 2^n と仮定する。 B(m)の要素のうち、最小の要素を2^kとすると、Sum(B(m))は、2^kの倍数だから、自然数Lを用いて、Sum(B(m))=L･2^kと表せる。 B(m)から、2^kを一つ取り除いた集合をB(m-1)とすると、Sum(B(m-1))=Sum(B(m))-2^k=(L-1)・2^k である。 ところで、定理の仮定より、2^k < 2^n であるから、2^n は、2^k の倍数である。 ところが、2^kの倍数であるSum(B(m))に一番近くてSum(B(m))より小さい2^kの倍数がSum(B(m-1))であるから、2^nは、Sum(B(m-1))と等しいか小さくなくてはならない。 つまり、2^n <= Sum(B(m-1)) < Sum(B(m)) という関係が成り立つ。 (ii) 今、集合Aそのものも、B(m)の条件を満たす事に注意する。 もし、Sum(B(m-1)) > 2^n であるならば、(i)のB(m)を、B(m-1)に置き換えて議論を繰り返すと、2^n <= Sum(B(m-2)) < Sum(B(m-1)) が言えて、いつか必ず、2^n=Sum(B(p)) となるような自然数pが存在しなくてはならない事が分かる。 この集合B(p)が、定理の条件を満たすAの要素の組み合わせである。(Q.E.D. by LightCone) http://medaka.5ch.net/test/read.cgi/os/1046271176/234
235: Be名無しさん [sage] 03/03/21 10:03 『任意の非負整数nに対し、2^n未満の2のべき数の集合Aにおいて、Sum(A) > 2^n ならば、Aの要素のいくつかをうまく選べば、和を2^nに丁度等しくできる。』 Aの最小値Amin = 2^mを考える 2^n>Aminよりn>m (2^(n-m)) * Amin = 2^n http://medaka.5ch.net/test/read.cgi/os/1046271176/235
236: LightCone ◆sSJBc30S5w [sage] 03/03/21 10:07 >>235 >(2^(n-m)) * Amin = 2^n この式自体は正しいのですが、Sum(B)の値が左辺に等しくなるような Aの部分集合Bを選べることが自明ではないと思いますので、これだけ では証明になっていないと思います。 http://medaka.5ch.net/test/read.cgi/os/1046271176/236
237: LightCone ◆sSJBc30S5w [sage] 03/03/21 10:13 #234より短い証明を見つけた方は、名前を明記して、私のBBSにでも お書きください。 今後、ここに沢山書かれても一々コメントできないと思います。 http://medaka.5ch.net/test/read.cgi/os/1046271176/237
238: Be名無しさん [sage] 03/03/21 10:14 >>235 例えば、A={ 1, 2, 4, 8, 16} で、 (2^(n - 0) ) * 1 = 2^n と言いたいんだろうが、{1]ばっかり使うのはありなの？ http://medaka.5ch.net/test/read.cgi/os/1046271176/238
239: Be名無しさん [sage] 03/03/21 10:54 >>238 いやSum(A)/Aminの不要な１を取り除いていけば良いのだから自明かと思ったけど 証明になっていないね 自明の部分をまともに書いたら余計長くなりそうだ http://medaka.5ch.net/test/read.cgi/os/1046271176/239
240: Be名無しさん [sage] 03/03/21 11:38 Lさんの(ii)も 和が2^nになるB(p)が存在しなくてはならないから存在する といっているのように見えるのは気のせいですか？ http://medaka.5ch.net/test/read.cgi/os/1046271176/240
241: LightCone ◆sSJBc30S5w [sage] 03/03/21 11:44 >>240 もう少し説明が必要かもしれませんが、あれで証明になっています。 B(k)には、必ず、 Sum(B(m)) > Sum(B(m-1)) > Sum(B(m-2)) > Sum(B(m-3)) >... の性質があって、さらに、 Sum(B(k)) >= 2^n なんです。 要するに、Sum(B(k))は、単調減少数列で、しかも、下限が 2^n なの です。しかも整数なので、いつか必ず 2^n に等しくなると言う論法です。 http://medaka.5ch.net/test/read.cgi/os/1046271176/241
242: Be名無しさん [sage] 03/03/21 11:54 >>240 ＞和が2^nになるB(p)が存在しなくてはならないから存在する 数学的帰納法と背理法がまざってるだけだろ。 ＞といっているのように見えるのは気のせいですか？ で、おまいは何が言いたいんだよ。証明が間違ってると言いたいのか？ それとも他に同じ証明を知ってるのか？ 同じ命題に対する証明であってもより違う方法で証明することには意味があるって、 わかってるよな？ http://medaka.5ch.net/test/read.cgi/os/1046271176/242
243: LightCone ◆sSJBc30S5w [sage] 03/03/21 12:10 >>240 飛躍を少なく直しておきましたので、ご覧下さい: (ii) 今、集合Aそのものも、B(m)の条件を満たす事に注意する。 もし、Sum(B(m-1)) > 2^n であるならば、(i)の m を、m-1 に置き換えて議論を繰り返すと、 数学的帰納法により、 Sum(B(m)) > Sum(B(m-1)) > Sum(B(m-2)) > Sum(B(m-3)) >... 及び、 Sum(B(k)) ≧ 2^n が成立する事がわかる。 つまり、Sum(B(k))は、下限が 2^n であるような整数値の強い意味での 単調減少数列である。 従って、いつか必ず、Sum(B(p)) =2^n となるような自然数pが 存在しなくてはならない。 この集合B(p)が、定理の条件を満たすAの要素の組み合わせであ る。(Q.E.D. by LightCone) http://medaka.5ch.net/test/read.cgi/os/1046271176/243
244: Be名無しさん [sage] 03/03/21 13:19 素朴な疑問なんですが、 2のべき数を足して、2のべき数にすることは可能なのでしょうか？ http://medaka.5ch.net/test/read.cgi/os/1046271176/244
245: 244 [sage] 03/03/21 13:23 もしかして、 「2^n未満の2のべき数の集合Aにおいて、Sum(A) > 2^nならば」 と言ってるあたり、集合Aには重複する要素もあるということでしょうか？ それなら納得。 http://medaka.5ch.net/test/read.cgi/os/1046271176/245
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 289 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.005s