LightCone様をお慕い申し上げるスレ

>>893
むしろ逆さまに、適用の方はすぐわかる人も多いと思うんですが、
でも#893さんの言う事も一理あって、あの定理群で唯一、発明的な
のは、「分散無効区間集結定理」だけなんですよね。

つまり、あの定理があの文章で言いたい事で、他の定理は非常に簡単なもの、
あるいは常識的なものばかりなんです。

>>893
どうやら、あの定理群が単純明快で、簡単すぎると思われているようなので、
こちらからお願いしたいことがあります。

それは、最後の結論に情報エントロピーと同形式が出てくることを、
熱力学、統計力学と関連した概念的な意味や理由を説明して頂きたい
ということです。

ご存知の通り、エントロピーは、状態の個数に対数を取ったもので、
系の複雑さに関係しているといわれています。

あの結論は、長さの分割が複雑な程、転送量が増えることを意味して
いるような気がするのですが、それを厳密に証明してみてください。

質問。
＞(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とするとSum(B(m))は2^kの倍数になるの？
B={2,3}だったとして最小の要素が2^1でもSum(B)=5は2^1の倍数にならないような。
漏れの勘違いはどこだろう・・・・。

>>897
>B={2,3}だったとして最小の要素が2^1でもSum(B)=5は2^1の倍数にならないような。
>漏れの勘違いはどこだろう・・・・。

集合Ａが2のべきの集合なので、部分集合であるＢも2のべきの集合です。
ですので、B={2, 3}ということはありえません。
例えば、B={2, 4, 8, 8, 8, 16, 32, 32} みたいになります。

「帰納的2のべき分割区間」の意味がわからん。
「帰納的2のべき分割区間」の具体例と、
「帰納的2のべき分割区間」ではない「2のべき分割区間」の具体例をくれ。

Aは2のべき集合だったのね。2chのレスだけ読んでも分からんはずだわ。

>>899

16バイトアライン領域の中に、

8バイトアライン領域,4バイトアライン領域,2バイトアライン領域,2バイトアライン領域

が隙間無く入っているようなものです。

>>900
＞Aは2のべき集合だったのね。2chのレスだけ読んでも分からんはずだわ。
Ａは2の「べき*の*集合」で、「べき集合」というつもりで使われていないと思われ。
注意されたし。

>>891
定理4について
|---------------| -+
|-------|-------| |同じ空間( | は「２のべき分割空間」の区切り)
|---|---|---|---| |
|-|-|-|-|-|-|-|-| -+

ここで
F..Free
U..Used
|F|U|U|F|U|F|U|F| の時、無効な2のべき区間の長さの合計は4 = 2^2
また、それぞれの無効な2のべき区間の長さは1 = 2^0
2^n = 2^(n - 1) + 2^(n - 1)より4-3(i)は明らか
|F|U|U|F|U|F|U|F| -> |F|F|U|U|U|F|U|F| -> |F|F|U|U|F|F|U|U| -> |F|F|F|F|U|U|U|U|
これはボトムアップ版クイックソートと言うのが妥当

>>903
これは、
＞ただのニ分木で、*実用的*で*効率的*なごみ集め可能ファイルバッファが
＞実装できるとは知らなかったな。
＞参考に汁から実装して見せてくれよ。
の部分に対するカキコかな。だったら、ご説ごもっともと言いたいところだが、
クイックソートとガーベジコレクションの関連性を説明してくれんか。
それと、
＞ 2^n = 2^(n - 1) + 2^(n - 1)より4-3(i)は明らか
は、あいかわらず誤解してないか？ >>898-901 を見てくれ。

>>903
私にはあなたの文章は意味不明なので、すみませんが、議論に入る前に、
却下せざるを得ません。

失礼かもしれませんが、あなたの文章は、証明、論証として全く成立して
いないと思います。

>>905
誰が見ても見下して偉そうに見えるだろ

>>906
スレタイご存知？神なんだよ？

(証明4-3)
2進数演算で考えて、ふたつの2べき数の加算で桁上がりが発生するのは二つが同値の場合のみ
したがって2^n未満2べき数の集合の和が2^nを超えるなら
（その和が2^(n-1)となる排他的部分集合が少なくとも二つ存在するはずであり）
その和が2^nとなる部分集合は必ず存在する

これ間違ってますか？
別にLightConeさんの証明に文句があるわけではなく
自分の当たり前という感覚の曖昧さに困惑気味なわけですが

神ｷﾀ━━━━━━━(ﾟ∀ﾟ)━━━━━━━ ！！！！

>>908

自明に成り立つと考えられる命題に対する対処には、2種類あります。

対処1:「公理」にしてしまう。
対処2:基本公理の組み合わせで証明をする。

もし、当たり前だと思うなら、公理にできるかどうかご自分でご判断
してください。

公理に出来そうに無いと思うなら、基本公理だけを用いて、論理的に
証明しなければなりません。

果たして、#908が証明になってますか？

どうみても、#908の第一行目と第二行目の間に論理的飛躍があります。

括弧書きになってるのは、自信がないからですか？

証明は、自信の無さを解消してくれるもので無ければならないと思い
ますよ。自信が無いままウヤムヤに成ってしまうのは、証明になって
無い可能性が高いです。

まず、#908は、定理「3-1」への疑問ですよね。

#908が、飛躍している原因の一つは、
最終的な総和が、2^nに成っているからといって、その直前も、2のべき
になっている事が自明でないことです。

もし、2^n になる直前の二つの数が、必ず2のべきに取れることを
証明できるならば、#908で証明が成立するでしょう。

しかし、今言った事が成り立つ事には証明が必要です。

もしそれを探す場合は、定理3-1の証明より、短く簡単になる方法を
探してくださいね。(^_^;)

>>912 修正

>最終的な総和が、2^nに成っているからといって、その直前も、2のべき
>になっている事が自明でないことです。

----->

「途中の和の計算課程が全て2のべきになっているとは限らない。」

なお、そういう方針でも証明できないわけではないですよ。

桁上がりがある--->同じ大きさの2のべきが少なくとも2つ以上存在する。
--->それらの二つの和を取れば、再び2のべきになっている。

これを、数学的帰納法で繰り返すとこの方針でも証明できると思います。

>>912
飛躍だとは思いません
括弧書きはむしろ蛇足だと思ったからです

２進数演算では同値以外の加算が桁上がりに寄与しないので無視できる以上
二つの値の加算で2^nに桁上がりする条件は2^(n-1)+2^(n-1)のみであり
集合の総和が2^nを超えているなら当然桁上がり条件を再帰的に満たしています

>>914
>二つの値の加算で2^nに桁上がりする条件は2^(n-1)+2^(n-1)のみであり
>集合の総和が2^nを超えているなら当然桁上がり条件を再帰的に満たしています

「再帰的に満たす」部分を丁寧に書いてくださいませんか。

>>914
なお、もし、整数論の帰結や群論の帰結や常識を使ってらっしゃるなら、
定理名を書いてください。

もし、そんなに自信がおありなら、#908の最後で、どうして私に確認を
とるんですか？

「証明」というのは、他人に確認を取らなくても納得できるような
ものだと信じています。

「a を任意の整数、bを任意の自然数とする。このとき、
　a = qb + r, 0 <= r < b
　となる、整数のq,r がただ一組存在する。」

こんなものでも証明できますよね。「当然」「当たり前」という言葉で
済ますのはよくないと思います。


「自分の当たり前という感覚の曖昧さに困惑気味」になってしまう
のは、数学ではないです。

いや>>904さんが>>903さんの
> 2^n = 2^(n - 1) + 2^(n - 1)より4-3(i)は明らか
に不満があるようなので
>>908の最後の文は蛇足でしたか

>> 「自分の当たり前という感覚の曖昧さに困惑気味」
これはいままで特に証明もせずに使っていたなというだけの話です

2進数演算では同ビット位置以外の加算が桁上がりに寄与しないとして無視できる以上
2^n未満の2べき数の集合の総和が2^nを超えているなら桁上がりに寄与しない集合要素は取り除いて
総和が2^nとなる部分集合を得る事が可能である

表現を変えてみましたがこれは二進数の加算からの性質から
「当然」「当たり前」という言葉で済ましてもよいと思います

>2進数演算では同ビット位置以外の加算が桁上がりに寄与しないとして無視できる以上
>2^n未満の2べき数の集合の総和が2^nを超えているなら桁上がりに寄与しない集合要素は取り除いて
>総和が2^nとなる部分集合を得る事が可能である

今は証明なので、桁上がりに寄与しない集合要素を具体的に示す必要があるで
しょう。

数学の世界では、定理3-1は、当たり前の言葉ではすまないと思います。

>>919
お願いですから、ハンドル名を書いてください。

匿名では話になりません。

ある意味門前払いです。

2chは怖い所で、数学オリンピックでメダル取るような人も実際に
来てます。私は凡才なので、そういう人には歯が立ちません。
#919さんがそういう人だったら、私が馬鹿なので許してください
と誤ります。
そういう人にとっては、コンピューターなど馬鹿らしくてやってられ
ないと思います。こんなところで油を売らず、与えられた才能
を存分に「本当の研究」に注いでください。

いや、919さんがそういう人だったら、
むしろそういう人を追い返してどうするのだ。
別にあんたの事をいじめている訳でもなし。
どこが正しくてどこが間違ってるか指摘してもらえばいいだけでないの？
取り敢えず落ち着け。

　本音を言うと、物凄く頭のいい人の多くは、コンピュータそのものの
研究はやりません。通常は、東大または京大の数学科または、物理学科
に行きます。

　そういう人たちが、コンピュータソフトを開発すれば、世の中がひっ
くり換えるほど凄いソフトが作れると思います。

　しかし、世の中は変なもので、超頭のいい人は、超頭が必要な分野
にしか興味を持たないか、または、時間が勿体無いので「下層な分野」
には来ません。

　そういう状況が通常保たれていますが（笑）、時に自分の才能に
限界を感じ、または、あまりの競争に恐怖を感じ、「下層な分野」に
下りて来る人が少しいます。数学をやりたかったが化学をやって、
賞を貰った人の例は何例かありますね。

　偏見と思われても仕方が有りませんが、これが現実だと思います。

　人工知能などでも、京大数学科のトップの人がやれば、実現したり
して（私にはあの人たちの目に世界がどのように理解されているか
想像がつかないので、人工知能など簡単すぎてやる気が沸かないと
思っていないとも限らないと思えます。）。

>>923
追い返そうとしているのではなく、私の才能では、難しく感じることが、
そういう人にとっては当たり前だったりするだけなんです。

はっきり言って、凡人には必要な証明も、彼らには一笑にふして終わり
なのかもしれません。

中には、数学オリンピックなど、子供だましなものなんてや
らないと思ってる人もいるような気もしますし、私には想像を絶する
世界です。

多分、彼らにとっては、アルゴリズム教本など読むものではなく、
書くもの、データ構造は学ぶものではなく、作るものでしょう。

私が1年かかって作るソフトを、彼らは一週間で作るかもしれません。

はっきり言うと、物を生み出す観点からは、彼ら以外は存在意義が
ないと言っても過言ではないくらいでしょう。

本当は、全て彼らがやればいい事なんですが、それだと自分が
やることがなく暇なので、凡人の私は時間をつぶしてるだけです。

もっと言うと、私が一ヶ月かかって読み切る専門書を彼らは、3日で読破
するかもしれません。

はっきり言ってこれだけ差があると、努力ではどうにも成らないものを
感じてしまいます。

でも、日本が変なのは、基礎科学を軽視しているので、彼らの居場所
が少ない事です。

というか、実際意味があるのは東大1000人中1人いるかどうかの世界
なんですが、それでも、上位100人は他の大学のトップより遥かに
上にあるのに、他の大学の人たちが何故か起用され、トップ大学から
吐き出された人たちが腐っていくのが現実だと思います。

まあ、意味があるのは確かに、東大でも0.1%だとしても、いくらなんでも
人材の使い方が勿体無い国だなあ、というのが本音です。

でも、どうしても言いたいのは、#919さん自信が直観力に優れている
人であっても、#919, #908 さんが論述した文章は、「証明」には
なっていないと思うということです。

凡才な私も、一応、数学の定理の証明はそこそこ見てきましたが、
あのような論述の証明は見たことが有りません。
飛躍と推測が多すぎるのです。

多分私の推測では、数学科の人ではないと思えます。

#904=#908=#918ということ？

また、鬱病の被害妄想が出たかもしれない。ｽﾏｿ >ALL

>>928
＞#904=#908=#918ということ？
>>891 >>894 >>902 >>904 は漏れ。
#908 = #918 は知らぬ。

Lﾀﾝと、#908ﾀﾝの立場の違いに#908は気づけよ。
科学、工学、応用技術をない交ぜにしてはいかん。
数学が科学であるかというとそれはそれで難しいテーマではあると思うが、
少なくともLﾀﾝはファイルバッファの構造について、
応用技術から科学としての数学までを横断的に論じている、と思う。
しかもLﾀﾝはある一定レベル以上の実装技術を持っている品。
今は数学的側面から、エントロピーのアナロジーについて議論したいのだろう。

#908他は、証明自体を自明だといくら主張しても「証明」ができていない。
証明ができなくても、それを応用技術に用いること自体は一向に構わない。
しかし科学にはそれ自体を成り立たせるためのルールがある。
工学屋は少なくともルールを知っているので証明無しで新理論？を
確信犯的に使うことがある。
応用技術屋はルールがなぜ必要なのかさえ分かっていないことがある。

どの立場も必要で、一人で兼ねることもできる。
別の立場を批判するのは不毛。

919と言いたかったのか？
918は本人だし。

>>928
まあ、馬鹿な事繰り返してる内に多少はマシになるもんで。
いわゆる「自明の事」を数学の証明の作法にとって
行儀良いよう表現する、という話自体は理解出来る。

で、何だ。
情報エントロピーだっけ？

>>1 よ。そろそろ次スレ立てなくていいのか？

>>930
＞情報エントロピーだっけ？
そう。自己情報量と同じ値になる不思議な量。
ある系に対するある操作(確率論では試行か？)の前後で増えたり減ったりする。
ファイルバッファでは、バッファの確保と、開放で、
確率論では、さいころを振る前と後で系の情報エントロピーが変化する。
>>896
＞それは、最後の結論に情報エントロピーと同形式が出てくることを、
＞熱力学、統計力学と関連した概念的な意味や理由を説明して頂きたい
＞ということです。
漏れにはできない。だからこのカキコは糞カキコだ。すまぬ。

情報　エントロピー　でググると山ほどあるね｡

提唱者のシャノン頃（通信）で言うと，
　情報量の多い信号ほどノイズ（エントロピー大）に近くなるとかだったような?

http://www.gms-jp.com/MemCalc_HP/5-1.htm

Lﾀﾝ、そんなに自分を追いつめなくても。

とはいえ、漏れも個人的に
> 2^n = 2^(n - 1) + 2^(n - 1)より4-3(i)は明らか
で十分すぎてお釣りが来ると考えている人間だな。

この辺ってブール代数とかですでに証明されてたりしないの？

>>936
確認しますが、例えば、

A = { 2,2,2,4,4,4 }

だと、Sum(A)=18 ですが、n=4として、Sum(B)=2^4=16 を満たす、
Aの部分集合Bを見つけることを例にして、その論理を説明してみてく
ださい。

929嫁。

>>931
トリップ忘れちゃった（ｗ

新規に追加する関連スレって何があったっけ？
とりあえず気付いた範囲内で挙げてみるけど...

os：OS［スレッド削除］
http://qb.2ch.net/test/read.cgi/saku/1027998169/

OSを作ってみよう
http://pc.2ch.net/test/read.cgi/os/1046271176/

OSを作ろうpart5
http://pc2.2ch.net/test/read.cgi/tech/1042375466/

>>939
あきれた、よくのこのこと出てこれたもんだ
正直に言えよ
「LightCone様の才能に嫉妬して糞スレを建てますた」って
さっさと死ねよ、基地外

>>940
というような内的葛藤を抱えているわけで
これ以上ここに留まる元気はありません。
そこで次スレはブラウザ製作快調の
NWSOS信者 ◆HX8gJR.Gyw氏に一任して、
私はこれを以て逝かせていただきます。
御機嫌よう〜

つーか、コーンたんは議論なんてしたくない人だからな。
そんな人がなぜ証明などに拘るのかは謎としか言いようがないのだが。

ディベートの類いと証明は全然違うだろ

os：OS［スレッド削除］ﾜﾗﾀ