OSを作ってみよう (534ﾚｽ)
上下前次1-新
226(3): 03/03/21 00:18 AAS
>>223
それよりあれはどういう意味なのか誰か教えてくれ。
あれは、それを証明すること自体に意味があるってことか？
定理自体は当たり前の話だよな。
227(1): 03/03/21 00:29 AAS
>>226
どうせ効果的なメモリ管理とか考えてて理論から固めようってことじゃないの？
228(2): 03/03/21 00:37 AAS
効率的アロケータの追求は結構なことですが
俺用語を乱発してはまるでK氏のよう
229(2): LightCone ◆sSJBc30S5w 03/03/21 09:19 AAS
>>226
>定理自体は当たり前の話だよな。
例えば、
>2のべき数分解定理
>『任意の非負整数nに対し、2^n未満の2のべき数の集合Aにおいて、
>Sum(A) > 2^n ならば、Aの要素のいくつかをうまく選べば、
>和を2^nに丁度等しくできる。』
が当たり前ですか？
>>228
>俺用語を乱発してはまるでK氏のよう
省1
230: 03/03/21 09:22 AAS
HSP-OS
231: 03/03/21 09:41 AAS
マジかよ・・・・。
外部ﾘﾝｸ:webplus.site.ize.org.uk
232: 03/03/21 09:43 AAS
>>229
>が当たり前ですか？
2^nはAminで割り切れるので
等式全体をAの最小要素Aminで割れば
Amin/Amin=1になるわけで
233: LightCone ◆sSJBc30S5w 03/03/21 09:53 AAS
>>23
>2等式全体をAの最小要素Aminで割れば
どの等式ですか？
>Amin/Amin=1になるわけで
この文章は、X/X = 1 と同じ内容ですね。ここから何が導けますか？
234: LightCone ◆sSJBc30S5w 03/03/21 09:55 AAS
証明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))と等しいか小さくなくてはならない。
省4
235(2): 03/03/21 10:03 AAS
『任意の非負整数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
236: LightCone ◆sSJBc30S5w 03/03/21 10:07 AAS
>>235
>(2^(n-m)) * Amin = 2^n
この式自体は正しいのですが、Sum(B)の値が左辺に等しくなるような
Aの部分集合Bを選べることが自明ではないと思いますので、これだけ
では証明になっていないと思います。
237(1): LightCone ◆sSJBc30S5w 03/03/21 10:13 AAS
#234より短い証明を見つけた方は、名前を明記して、私のBBSにでも
お書きください。
今後、ここに沢山書かれても一々コメントできないと思います。
238(1): 03/03/21 10:14 AAS
>>235
例えば、A={ 1, 2, 4, 8, 16} で、
(2^(n - 0) ) * 1 = 2^n
と言いたいんだろうが、{1]ばっかり使うのはありなの？
239: 03/03/21 10:54 AAS
>>238
いやSum(A)/Aminの不要な１を取り除いていけば良いのだから自明かと思ったけど
証明になっていないね
自明の部分をまともに書いたら余計長くなりそうだ
240(3): 03/03/21 11:38 AAS
Lさんの(ii)も
和が2^nになるB(p)が存在しなくてはならないから存在する
といっているのように見えるのは気のせいですか？
241: LightCone ◆sSJBc30S5w 03/03/21 11:44 AAS
>>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 に等しくなると言う論法です。
242: 03/03/21 11:54 AAS
>>240
＞和が2^nになるB(p)が存在しなくてはならないから存在する
数学的帰納法と背理法がまざってるだけだろ。
＞といっているのように見えるのは気のせいですか？
で、おまいは何が言いたいんだよ。証明が間違ってると言いたいのか？
それとも他に同じ証明を知ってるのか？
同じ命題に対する証明であってもより違う方法で証明することには意味があるって、
わかってるよな？
243(1): LightCone ◆sSJBc30S5w 03/03/21 12:10 AAS
>>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)) >...
及び、
省8
244(1): 03/03/21 13:19 AAS
素朴な疑問なんですが、
2のべき数を足して、2のべき数にすることは可能なのでしょうか？
245: 244 03/03/21 13:23 AAS
もしかして、
「2^n未満の2のべき数の集合Aにおいて、Sum(A) > 2^nならば」
と言ってるあたり、集合Aには重複する要素もあるということでしょうか？
それなら納得。
上下前次1-新書関写板覧索設栞歴
あと 289 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.010s