計算機科学の質問はここでしろ！

**名無しさん＠お腹いっぱい。** · 2006/08/20(日) 19:36:09

計算機科学全般についての疑問を投げ付けあうスレッドです。

ここで扱う「計算機科学」の範囲は、他のスレッドとの兼ね合いで
決めることになりますが、当面は目一杯広くとることにします。

工学に分類されることがらについては別スレッドへ、
プログラミングについてはプログラム技術板へどうぞ。
ただし、境界上の話題は歓迎します。

**名無しさん＠お腹いっぱい。** · 2006/08/22(火) 08:43:16

君が死んでからもう２年。
君は今も僕を見守ってくれているのかな？
君は、僕の生まれて初めて出来た彼女だった。
すごく嬉しくて、幸せだったなあ。
突然、白血病だって医者に宣告されてから、君は病室で日に日に弱っていった。
「病院ってひまねえ」って笑う君を見て、僕はいつも泣いていたんだ。
君の為に、僕の小汚いノートパソコンをあげたら、君はすごく喜んでくれたよね。
ネットをするようになった君がいつも見ていたサイト、それが「２チャンネル」だった。
ある日君はいつものように、笑いながら言った。「ほら、見て今日も２ゲット出来たよ。」
「あまりパソコンばっかいじってると身体に障るよ」なんて僕が注意すると、
「ごめんねえ。でもね、これ見てよ。
ほら、この３のひと、２げっとぉ！なんて言っちゃってさぁ、ふふ」
僕は黙っていた。君がすごく楽しそうで、僕は何も言えなかった。
「ほらみて、この３のひと、変な絵文字使ってくやしぃ～！だって。
かわいいねえ。ふふ。」
僕はまだ黙っていた。笑う君を見て、どうしようもなく悲しくなった。
「憶えててくれるかなあ」君がふと言った。
「…この３のひと、私がいなくなっても、あの時変な奴に２をとられたんだよなー
なんて、憶えててくれないかなあ……無理かな……憶えてて、ほしいなぁ……」
それから数ヶ月後、君は家族と僕に見守れながら息を引き取った。
君はもうこの世に居ない、なのに僕は今F5を連続でクリックしている。
君の事を、３のひとが忘れないように、いつまでも、いつまでも忘れないように。
天国にいる君と一緒に、今ここに刻み込む。

　　　　　　　　２　ゲ　ッ　ト

**名無しさん＠お腹いっぱい。** · 2006/08/22(火) 13:14:47

>>1
とりあえず予想されるFAQってことで教科書一覧でも作っておくのはどう？

Hopcroft&Ullmanとか Introduction to Algorithms とか。

1 · 2006/08/24(木) 20:25:14

>>3
良い考えだと思います。私は素人なので教科書を挙げられないですが。

技術・趣味系の板のノリで質問スレを立ててしまったのですが
あまり需要がなかったかも知れません。

**名無しさん＠お腹いっぱい。** · 2006/08/25(金) 17:52:03

パーマン。

**名無しさん＠お腹いっぱい。** · 2006/08/26(土) 21:00:12

計算幾何学
計算機化学
も当然ここでいいの？

CS · 2006/09/03(日) 14:27:05

計算機科学者って、パソコンの自作とか得意ですか?

**名無しさん＠お腹いっぱい。** · 2006/09/03(日) 15:09:58

http://blogranking.fc2.com/in.php?id=78352

**名無しさん＠お腹いっぱい。** · 2006/09/03(日) 15:40:01

>>7
長尾眞元総長はパワーポイントをろくに触ったことがなく，
真っ白で何のアニメーションも無いスライドを作っていたぞ。

**名無しさん＠お腹いっぱい。** · 2006/09/03(日) 16:24:31

>>7
理論系は基本的に数学者なので苦手な人は多い。
たとえば，論文を書く必要上TeXは使えるがTeXのインストールができる人は少ないと思う。

別の理由ではあるけどメールは読まない，電話も出ない，って先生はいる。
直接行けば会ってくれる。

**名無しさん＠お腹いっぱい。** · 2006/09/11(月) 18:58:42

IPC(Instructions per Cycle)の「I」には分岐予測ミスしたパス上で実行された命令も含まれるんですか？
その場合、せっかく分岐予測率を向上させて「C」を減らしても「I」が同時に減るから
IPCには努力の成果があまり現れないんじゃないですか？

**名無しさん＠お腹いっぱい。** · 2006/09/11(月) 22:34:18

>>9
極めるとそこに行き着くんだよ。村井純でもそういうパワポ見たことある。
俺も最近はそういう奴の方が人に訴える力があるような気がしてきた。

**名無しさん＠お腹いっぱい。** · 2006/09/12(火) 00:04:11

>>12
つ[高橋メソッド]
TeXでもプレゼンが簡単に作れて便利。

**名無しさん＠お腹いっぱい。** · 2006/09/15(金) 01:45:40

平面上のn点が与えられて，
各点へのユークリッド距離の和を最小にする点を求めるという問題．
四分木を使う解法しか思い浮かばなかったんだけど，他にないかな？

**名無しさん＠お腹いっぱい。** · 2006/09/15(金) 19:24:47

すみません。どうしてもここだけわからないので教えてください。

負数を２の補数で表す８ビットの数値がある。この数値を１０進数で表現すると、
－９９である。この値を符号なしの数値として解釈すると、１０進数でいくらか。

考え方も添えて教えてください＞＜

**名無しさん＠お腹いっぱい。** · 2006/09/16(土) 06:21:38

8ビットの数値においてxの2の補数とは256-xのことである。
-99は99の2の補数、すなわち256-99 = 157として表される。
符号なしの数値として解釈すると、この値をそのまま読むことになる。よって157。

**名無しさん＠お腹いっぱい。** · 2006/09/16(土) 08:27:10

>>16
マジでありがとう御座います。助かりました！
いい人いるんだなぁと実感しました。本当にありがとう！

**名無しさん＠お腹いっぱい。** · 2006/09/16(土) 21:43:19

>>14

基本的に四分木で出来るのだからそれでいいと思うけれども、
要はxで偏微分した値とyで偏微分した値がどちらも0になる点を求めるという観点から、
数値的な解法をしても良いかもしれないとは思う。

ちゃんとやってないので適当でｽﾏｿ

**名無しさん＠お腹いっぱい。** · 2006/09/17(日) 08:20:11

1000x+221y=3となる整数x,yを一次不定方程式で一組もとめてください(-.-)y-~恥ずかしながら情報数学のいっちゃん最初です(笑)

**名無しさん＠お腹いっぱい。** · 2006/09/17(日) 09:27:00

>>19
-120, 543

**名無しさん＠お腹いっぱい。** · 2006/09/17(日) 18:59:57

ありがとうございます！

14 · 2006/09/18(月) 02:33:19

>>18
山登り方でできないかな～と思ったんだよね
できればそれが一番速いし

**名無しさん＠お腹いっぱい。** · 2006/09/18(月) 09:57:40

>>14
どう見ても凸計画だし条件も良いから，最急降下が効率よくうまく動くと思う．

14 · 2006/09/19(火) 00:59:15

>>23
なるほど、凸計画がキーワードなんですね
色々調べて勉強になりました
ありがとう

**名無しさん＠お腹いっぱい。** · 2006/09/23(土) 10:52:02

k-tapeチューリングマシンは、1-tapeチューリングマシンと同等の能力があることは、テープ圧縮法で証明するようなのですが、実践的な部分が理解できません。
たとえば、以下の2-tapeチューリングマシンのプログラム（回文=palindromeを受容する）を1-tapeチューリングマシンで書き表すとどうなるか、わかる人いますでしょうか？

チューリングマシンM = (状態集合Q, アルファベットΣ, 遷移関数δ, 初期状態s)
Q = { s, p, q }, Σ = { a, b }とし、□は空白記号、＞は左端記号を表すものとします。
δ(状態, 入力記号1, 入力記号2) = (次の状態, 出力記号1, 方向1, 出力記号2, 方向2)
というふうに表記します。

**名無しさん＠お腹いっぱい。** · 2006/09/23(土) 10:52:34

回文（abba とか abaaaba とか、左右対称の文字列）を認識するプログラム：

δ(s, a, □) = (s, a, →, a, →)
δ(s, b, □) = (s, b, →, b, →)
δ(s, ＞, ＞) = (s, ＞, →, ＞, →)
δ(s, □, □) = (q, □, ←, □, -)
δ(q, a, □) = (q, a, ←, □, -)
δ(q, b, □) = (q, b, ←, □, -)
δ(q, ＞, □) = (p, ＞, →, □, ←)
δ(p, a, a) = (p, a, →, □, ←)
δ(p, b, b) = (p, b, →, □, ←)
δ(p, a, b) = ("no", a, -, b, -)
δ(p, b, a) = ("no", b, -, a, -)
δ(p, □, ＞) = ("yes", □, -, ＞, →)

**名無しさん＠お腹いっぱい。** · 2006/09/23(土) 10:53:27

動作の雰囲気としては、
状態sで、入力文字列のあるテープ１の内容を、左から右に移動しながら、テープ２にコピーします。
右端（空白である□）に達したら状態qに遷移。
状態qでは、単純にテープ１のテープヘッドを左端まで移動させます（テープ２のテープヘッドは右端に置いておきます）。
左端に達したら状態pに遷移。
状態pでは、テープ１上を右方向に、テープ２上を左方向にスキャンして、互いに異なる記号があったら即座に"no"を返します。
テープ１の右端、テープ２の左端まで達することができたら、回文であるということなので、"yes"を返します。

このプログラムを、テープ圧縮法の考え方を用いて1-tapeチューリングマシンのプログラムに変換するには、どうしたらよいでしょうか？

**名無しさん＠お腹いっぱい。** · 2006/09/23(土) 12:21:13

>>27
宿題は自分で，と言いたいところだけど
大学の後輩だったらどうしようと思ったので一応説明してみるテスト。

2テープTuring機械Mを元に新しい1テープ9記号Turing機械M'を作るとき
一番大事なところを説明してみる。
入力文字列の長さをn, Γ={1,2,3,4,5,6,7,8,#}としよう。
iを自然数として,M'のテープの中身は以下のように作る。

元テープ１のiマス目の記号:aaabbb###
元テープ２のiマス目の記号:ab#ab#ab#
　↓
新テープ　のiマス目の記号:12345678#

あとはMの1ステップをシミュレーションするのに
M'がnステップかけていいならシミュレーションできそうでそ。

きちんとした証明にするには最初と最後はどうするかとか
いろいろあるけど，本質的な部分はこれだけ。

結果だけ聞けばインチキくさいと思うかもしれないが，
そのインチキくさい手法は誰にでも思いつけるわけじゃないってことで。

**25-27** · 2006/09/24(日) 03:16:59

>>28
レスどうもです！
全部のテープのアルファベットをそれぞれの位置ごとにエンコードするってことまではわかりました。
でもちょっとまだ理解しきれないところが・・・。
それぞれのテープのカーソル位置っていうのは、任意のステップで別々の場所にあるわけですけど、それをどういう形で記憶し、実際の動作にどう反映させるのでしょうか？

**名無しさん＠お腹いっぱい。** · 2006/09/24(日) 04:12:55

>>29
カーソルの位置を表す専用のトラックを用意すると簡単。

**名無しさん＠お腹いっぱい。** · 2006/09/26(火) 08:18:15

日本語の形態素解析に、隠れマルコフモデルを利用すると、従来に比べて精度良く
形態素解析出来るとの事で、茶筅と言うプログラムが発表されてます。
次に、隠れマルコフモデルより更に精度良く、高速に形態素解析出来るCRFと言う
考え方でめかぶと言うプログラムが発表されてます。

隠れマルコフモデルは言葉でイメージできるのですが、CRFはなにがどういこっちゃ
まったく分かりません。CRFについて、優しく詳しく、あまり数式をもちいないで解説しなさい。

**名無しさん＠お腹いっぱい。** · 2006/09/26(火) 09:38:49

宿題は自分でやること。

**名無しさん＠お腹いっぱい。** · 2006/09/26(火) 10:29:13

>>32
しゅくだいじゃねーよぉーーーーーーーー！！･ﾟ･(つД`)･ﾟ･

わっレスついてるぅううううううううううううって喜んだじゃねーカー。

**名無しさん＠お腹いっぱい。** · 2006/09/29(金) 18:30:50

計算量ってなに？どゆこと？

**名無しさん＠お腹いっぱい。** · 2006/09/29(金) 21:41:32

>>26
何かの絵文字に見えてしまった

**名無しさん＠お腹いっぱい。** · 2006/09/30(土) 06:47:07

>>34

http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E9%87%8F

**名無しさん＠お腹いっぱい。** · 2006/10/07(土) 01:40:21

ラムダ算法でチューリング機械をシミュレートできるのはわかったけど、チューリング機械でラムダ算法をシミュレートできることを、どうやって証明するんですか？

**名無しさん＠お腹いっぱい。** · 2006/10/07(土) 09:18:28

>>37
前者を自分の言葉で誰かに説明してみ。2chじゃなくて、手近な人に。

ま、ここでもいいけど。

**名無しさん＠お腹いっぱい。** · 2006/10/08(日) 04:48:09

>>38
ごめんなさい。できません。

**名無しさん＠お腹いっぱい。** · 2006/10/09(月) 16:59:32

むしろ後者のほうが証明は直感的にできると思うんだけどな．

**名無しさん＠お腹いっぱい。** · 2006/10/09(月) 21:07:05

パソコンでLISP処理系が実装できるわけだしねぇ。

**名無しさん＠お腹いっぱい。** · 2006/10/09(月) 21:08:12

IDがawkでちょっとうれしい。
Aho って「アホ」的な読み方が正しいらしいけどね。

**名無しさん＠お腹いっぱい。** · 2006/10/09(月) 23:05:01

Lispはatomがあるから、ラムダ計算をシミュレートしてるうちに入らないんじゃなかったっけ？

**名無しさん＠お腹いっぱい。** · 2006/10/13(金) 15:50:41

どこのスレに書けば良いかわからなかったのでスレ違いだったらすいません。

10進数の0.2を2進数の浮動小数点表示にするとどうなりますか？
解き方もあるとうれしいのですm(__)m
指数部がよくわからなくて…

**名無しさん＠お腹いっぱい。** · 2006/10/15(日) 19:30:31

ヘネパタ嫁

**名無しさん＠お腹いっぱい。** · 2006/10/15(日) 20:48:18

http://ja.wikipedia.org/wiki/%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0#IEEE_754_.E3.81.A7.E8.A1.A8.E7.8F.BE.E3.81.99.E3.82.8B.E3.81.BE.E3.81.A7.E3.81.AE.E9.81.8E.E7.A8.8B
これじゃダメか？
浮動小数点でググって一番上にあるんだが。

**名無しさん＠お腹いっぱい。** · 2006/10/15(日) 22:44:49

こんな高校生（中学生？）レベルの質問で、へね＆ぱたを読め　はねぇだろ。　
10進数なら 0.1 = 1/10
2進数なら 0.1 = 1/2
後は計算しな。

**名無しさん＠お腹いっぱい。** · 2006/10/22(日) 21:39:00

情報幾何が日本以外であまり使われていないって本当なのですか？

**名無しさん＠お腹いっぱい。** · 2006/10/23(月) 16:22:30

さあ？

**名無しさん＠お腹いっぱい。** · 2006/10/24(火) 13:13:56

情報系独特の論文スタイルってありませんか？
情報系だけは日本語と英語同時投稿ＯＫとか

**名無しさん＠お腹いっぱい。** · 2006/10/24(火) 20:05:50

Wikipedia の姚期智について読んでたら思ったのですが、
ヤオの法則ってなん何でしょうか？簡単に説明していただけませんか？

**名無しさん＠お腹いっぱい。** · 2006/10/25(水) 09:37:12

>51
http://en.wikipedia.org/wiki/Yao's_Principle

**名無しさん＠お腹いっぱい。** · 2006/11/14(火) 20:47:53

　　　　　　,ｒｎ　　　　　　　　　　
　　　　　r｢l l h　同志！　　　　　　　／　　　　　　　　／
　　　　　|　､. !j　川崎と京都市南区と大阪生野区には、落とさないﾆﾀﾞ！
　　　　　ゝ　.f　　　　　　 ,r'⌒　 ⌒ヽ､　KCIA情報教えてﾁｮ　　　　
　　　　 ,｣　　L_　　　　　f ,,r'￣￣ヾ.　ヽ.　　　　／　／
　　　　ヾー‐'　|　　　　　ゞ‐=H:=‐fｰ)r､）　　　　／
　　　　 |　　　じ､　　　　ﾞiー'･･ー'　i.ﾄｿ
　　　　＼　　　＼. 　　 l､ r==i　,;　|'　　　　　ゴゴゴゴゴゴゴ
　　　　　　＼　　　ﾉﾘ^ー-＞==__,..-‐ﾍ＿＿　　　／　／|　／　　　　／
　　　　　　　＼　　　　　　|_/oヽ__／　　　　＼　　　／　 |＿
　　　　　　　　　ヽ＿＿　　　　|　　　　　　　　　＼／　　／　　ヽ_＿＿
　　　　　　　　　　　　　|　　　 |　　　Ｏ　へ　　　　＼／　　／　　　／
　　　　　　　　　　　　　/　　　|　　　　　　 |＼/　　｜　　／　　　／
　　　　　　　　　　　　　|　　　|　　　　　　　|／|　＿ |　／＿＿／
　　　　　　　　　　　　　|　　　|　　　　　　　|　　「　　＼:"::／
　　　　　　　　　　　　　|　　コ[□]ニ　　　　|　　⌒ ﾘ川／
　　　　　　　　　　　　/　＼　　　　　　／　　＼　...:::／
　　　　　　　　　　　/　　　　ゞ＿＿＿　　　　　＼／　　　
　　　　　　　　　　/　　　　／　　　　　＼　　　　　＼　　　　
　　　　　　　　　/　　ゝ／　　　　　　　.::＼　/　　　|　　　　
　　　　　　　　　|　　／　　　　　　....:::::::／＼<　　　|　　
　　　　　　　　　|　／　　　　　　...::::::::／　　｜　　　|　　
　　　　　　　　　／　　　　　　....:::::::／　　　｜　　　|　　
　　　　　　　／　　　▼　...::::::::／　　　　　｜　　　|　　　
　　　　　　／　　　▼　▼..::::::／　　　　　　　|＿＿_|　　　　

**名無しさん＠お腹いっぱい。** · 2006/11/20(月) 11:51:39

算術関数で1.5乗と1.1乗と常用対数の示し方について教えてください。

**名無しさん＠お腹いっぱい。** · 2006/11/25(土) 08:31:22

領域理論は何のためにあるんですか？

**名無しさん＠お腹いっぱい。** · 2006/12/09(土) 20:31:37

あげ

**名無しさん＠お腹いっぱい。** · 2006/12/09(土) 20:49:43

うん

**名無しさん＠お腹いっぱい。** · 2006/12/26(火) 20:51:39

すみません、どうしてもわからないんでみなさんに助けていただきたいです。

ElGamal暗号を多項式時間で解読するアルゴリズムを用いて、DH鍵計算問題を多項式時間で解くアルゴリズムが構成可能であることを、帰着技法を用いて示せ。

これがわかりません、どなたかお願いしますm(__)m

**名無しさん＠お腹いっぱい。** · 2006/12/26(火) 22:27:29

http://sports2.2ch.net/test/read.cgi/entrance2/1167135720/20

ｵﾅﾇｰねたあります

**名無しさん＠お腹いっぱい。** · 2006/12/27(水) 03:26:53

>>58
宿題は自分でやれ

**名無しさん＠お腹いっぱい。** · 2006/12/27(水) 18:20:45

>>58
黒澤、尾形「現代暗号の基礎数理」電子情報通信レクチャーシリーズD-8、コロナ社、2004
6.3 DH問題とElGamal暗号

に載ってる

使っている攻撃者は、OWの意味での安全性
（暗号文が与えられたとき、元の平文が求められない）を破る解読アルゴリズムですね

**名無しさん＠お腹いっぱい。** · 2007/01/12(金) 10:35:03

収束するタイプのアルゴリズムの計算量はどのように評価すればいいでしょうか？
たとえば、解との誤差が反復回数kに対してexp(-k)となるアルゴリズムなら
その計算量はどう考えればいいですか？

**名無しさん＠お腹いっぱい。** · 2007/01/12(金) 11:04:55

>>62
ﾃｲﾗｰ展開

**名無しさん＠お腹いっぱい。** · 2007/01/12(金) 11:06:10

間違えた。ｽﾏｿ

**名無しさん＠お腹いっぱい。** · 2007/01/16(火) 14:44:11

すごく基本的なことだと思うのですが、疑問に思ったので質問させてください。

決定可能性の議論とかでよくチューリングマシンが、入力として受け取った符号化されたチューリングマシンを内部で模倣することがありますが、
①チューリングマシンというのは「任意の」チューリングマシンを模倣することができるのですか？
②また、チューリングマシンの符号を構文解析する問題は決定可能なのですか？

計算機科学の教科書とかって、しつこいくらいに細かいことに一つ一つ証明がついているので、その勢いに倣ってこんなことにも論証を試みたいのですが、どうしてもどう論理展開したらいいのかわかりません。
証明の糸口だけでもいいので、よろしくお願いします。

**名無しさん＠お腹いっぱい。** · 2007/01/16(火) 17:23:13

>>65
(1) 万能Turing機械はテープに書かれた状態遷移関数を模倣できる。
(2) とりあえず「構文解析」が何を意味するのかわからん。
回答する前に>>65に書いてある「構文解析」の定義を与えてくれ。

65 · 2007/01/16(火) 18:49:10

>>66
回答ありがとうございます！

(1)なるほど、状態遷移関数の1ステップを模倣できればOKってことですね。
それで色々考えてはみたんですけど、どうしたら模倣できるのでしょうか・・・？
多テープTMを使うのだとは思うのですが、入力であるTM符号を受け取ってみなければ状態がいくつあるかも、遷移関数がいくつあるかもわからないにもかかわらず、いかなるTMでも模倣できるようなUTMを設計することは可能なのでしょうか？
よかったらもう少しだけヒントをもらえませんでしょうか？

(2)の構文解析なんですが、手元の教科書ではTMの符号を与えられたときに、そもそもTMの符号として正当ではないような場合、「入力を一切受理しないTM」と見なすってことになっています。
そこで、ちゃんとしたTMの符号を表す文字列かどうかを判定する構文解析のようなものが必要なのではないかと思いました。
ちょっと構文解析という言い方は、構文木でも構築するような聞こえになってしまってふさわしくなかったですね・・・。
すみません。
テープ上のTM符号がTMとして正当かどうかを判定するアルゴリズムという意味です。

**名無しさん＠お腹いっぱい。** · 2007/01/16(火) 22:11:56

>>67
頭の中で考えようとしているだけで，ちゃんと手を動かしてないでしょ。

まず，簡単なTuring機械Mを一つ作って(ひたすら0を書きまくるとか)，
Mの状態遷移関数を実際にTuring機械のテープ上に書いてみたらいい。

基本的には紙に書けるものはTuring機械のテープに書けるから。
(1) も (2) もそれをやってみたら理解が深まる。

**名無しさん＠お腹いっぱい。** · 2007/02/02(金) 14:37:20

授業で
キーボードから３つの数値を入力して、平均値を計算して画面に表示する。
っていうプログラムを作れと言われたんですけど、誰か教えていただけませんか？お願いしますm(_._)m

**名無しさん＠お腹いっぱい。** · 2007/02/02(金) 15:08:50

>69
for i in range(0,3):
　　69.叩く(テンキー)
　　69.メモする(押した数字)
69.筆算する(メモ)
平均値 = 69.持つ(油性マジック)
69.書く(平均値, 画面)
end

**名無しさん＠お腹いっぱい。** · 2007/02/02(金) 15:23:05

>>69
そんなことも自力でできないのなら、おとなしく単位をあきらめろ。

**名無しさん＠お腹いっぱい。** · 2007/02/03(土) 03:04:32

リードソロモン符号において
符号に含まれた誤りの数が訂正可能な数よりも多いということは
どの段階(シンドローム，オメガ，根・・・)で分かるのでしょうか？

**名無しさん＠お腹いっぱい。** · 2007/02/03(土) 11:56:02

>72
別の符号語に訂正してしまうので分からない。

**名無しさん＠お腹いっぱい。** · 2007/02/04(日) 22:51:46

ＩＰアドレス初歩質問
10進数177が2進数1011110になるわけ？
大学教授の解答なんです・・・・・

**名無しさん＠お腹いっぱい。** · 2007/02/04(日) 22:57:42

ＩＰアドレス初歩質問
10進数177が2進数1011110になるわけ？
大学教授の解答なんです・・・・・

**名無しさん＠お腹いっぱい。** · 2007/02/04(日) 23:31:39

10進数177は2進数10110001
2進数1011110は10進数94

**名無しさん＠お腹いっぱい。** · 2007/02/04(日) 23:33:15

ﾏﾙﾁかつｽﾚ違いかつ社会性のない74は師ね

**ちばしてぃのはんたぃ** · 2007/02/06(火) 18:09:45

>>69

<html>
<head>
<script language="JavaScript">

</script>
</head>

<body>

<form name="Calc">
<input type="text" name="x" value="0" size=10>
<input type="text" name="y" value="0" size=10>
<input type="text" name="z" value="0" size=10>
<input type="button" value="答え一発" onClick="calc(this.form)">
</form>

</body>
</html>

テキトーに書いたので，試してみれ　＞（￣。￣

**ちばしてぃのはんたぃ** · 2007/02/06(火) 18:11:13

ま，この程度のコードはぴろたんにくれてやるから　＞（￣。￣

**名無しさん＠お腹いっぱい。** · 2007/02/07(水) 14:29:42

>>79
＞答え一発
ぜひ元ネタ通り6桁であってほしかったと思う。どうでもいいけど。

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 01:06:50

突然すみません。
RSA暗号法の２つの鍵を
(e,n)=(61,437)
(d,n)=(13,437)
の時、292を復号する方法を教えてください。

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 03:32:59

ここは過疎板なんだな。

過疎板・・・。

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 15:26:19

まだ出来て間もないからな。
出来たばかりで客の少ない駅舎みたいなもんだ

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 17:07:23

>>81
mod(292^13, 437) = 26
かな？

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 22:00:43

>>81
(e,n)=(61,437)から(d,n)=(13,437)を求める方はええの？
ふつうそっちのほうが問題になるんちがうん

**ちばしてぃのはんたぃ** · 2007/02/16(金) 12:03:36

>>80
それは宿題にw　みんなお家で解いてね（＾ー＾

>>81 >>84を検算してみたら，無事戻った。

mod(26^61, 437) = 292

**名無しさん＠お腹いっぱい。** · 2007/03/21(水) 12:20:06

「計算理論の基礎」をやっているのですが、分からない問題があります。

以下の正規表現を与えよ。
{w|wは部分文字列110を含まない文字列}
※アルファベットは{0,1}。

どなたか教えていただけますか？

なお、正規表現なので使えるのは以下です。
　Σ、ε、Φ(空言語)、R1∪R2、R1R2、R1*
　　※R1、R2は任意の正規表現

**名無しさん＠お腹いっぱい。** · 2007/03/22(木) 00:33:58

>>87
-- 110を含まず、かつ1で終わらない文字列
a <- "" + c * "0"
-- 110を含まず、かつ1で終わり、かつ11で終わらない文字列
b <- a * "1"
-- 110を含まず、かつ11で終わらない文字列
c <- "" + a * ("0" + "1") + b * "0"
-- 110を含まず、かつ11で終わる文字列
d = x * "11"
-- 110を含まない文字列
x <- c * ("0" + "1") + d * "1"

これを解いて、
1?0?(01?0?)*1*
もうちょっと簡略化。
1?(01?)*1*
とりあえず手元のegrepでは動作しているようだけど、こんなんでいいのかな。

**名無しさん＠お腹いっぱい。** · 2007/03/22(木) 17:58:32

>>88
ありがとうございました。

でも私の頭では「これを解いて、」というところが理解できず。。。
このような方法は初めて見たのですが、参考になる本やサイトを紹介いただければ
ありがたいです。

とりあえず、次のように考えて答えを出しました。
①{w|wは部分文字列110を含む文字列}をあらわすDFAを作成。
②受理状態を非受理状態に、非受理状態を受理状態にする。
③NFAを正規表現にする方法を使い、②で作成したDFAを正規表現にする。

結果、「(0∪10)*((1(ε∪11*))∪ε)」を得ました。
88さんの答えよりかなり複雑になってしまいましたが、私もegrepで試したところ
うまくいっているようです。
※egrep '^(0|10)*((1(|11*))|)$'　…

**名無しさん＠お腹いっぱい。** · 2007/03/23(金) 00:12:55

>>89
>でも私の頭では「これを解いて、」というところが理解できず。。。
代入と代数操作で式を変形して、
V <- T + V * E
という形にし、再帰を消して
V <- T * many E
に書き直す、という方法を使った。
例えば、>>88の三番目の式に最初と二番目の式を代入して変形すると、
c <- "" + a * ("0" + "1") + a * "1" * "0"
c <- "" + a * ("0" + "1" + "10")
c <- "" + ("" + c * "0") * ("0" + "1" + "10")
c <- ("" + "0" + "1" + "10") + c * ("00" + "01" + "010")
だから、
c <- ("" + "0" + "1" + "10") * many ("00" + "01" + "010")
で、cの正規表現が分かった。

>このような方法は初めて見たのですが、参考になる本やサイトを紹介いただければ
>ありがたいです。
ちゃんと勉強してないので我流。馬鹿なことをやっているかも。

>①{w|wは部分文字列110を含む文字列}をあらわすDFAを作成。
>②受理状態を非受理状態に、非受理状態を受理状態にする。
>③NFAを正規表現にする方法を使い、②で作成したDFAを正規表現にする。
体系的な方法ですね。全く思いつかなかった。

>結果、「(0∪10)*((1(ε∪11*))∪ε)」を得ました。
((1(ε∪11*))∪ε) = 1*
なので、結局(0∪10)*1*になる。

答えを出してから思いついたけど、一旦11が出現するとその後は
ずっと1でなければならない、ということに着目すると、暗算で解けたかも。

**名無しさん＠お腹いっぱい。** · 2007/06/14(木) 00:34:52

通信路符号化において0,1,2の各グループを３ビットずつ送信して多数決法で
平均誤り率を求める方法を教えて下さい。生起確率は３つとも同じとします。

**名無しさん＠お腹いっぱい。** · 2007/06/21(木) 12:30:31

クラスNPが微妙に分からないのでWIKIPEDIAで調べたんですが・・・

NP の定義は次の3つである、ただしこれらはお互い同値であることが証明されている。

1.非決定性チューリングマシンによって多項式時間で解くことができる問題。
2.yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。
3.問題の探索状態を木で表したとき、yes にたどり着く最短距離が問題のサイズの多項式に比例する問題。
端的に説明するときは 2番目の定義（多項式時間で検算可能）が用いられることが多い。

なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。

このような事が書かれていました。

クラスNPは決定問題のクラスのはずですが、
非決定性チューリングマシンは決定問題以外も扱える為、
「非決定性チューリングマシンによって多項式時間で解くことができる問題。」のように定義してしまうと、
決定問題以外も扱えるクラスになってしまいます。

という事は非決定チューリングマシンは決定問題しか扱えない計算機という事なのでしょうか。

この記事見てから全体的に混乱してきたので解説お願いします。。。

**age** · 2007/06/21(木) 12:31:21

クラスNPが微妙に分からないのでWIKIPEDIAで調べたんですが・・・

NP の定義は次の3つである、ただしこれらはお互い同値であることが証明されている。

1.非決定性チューリングマシンによって多項式時間で解くことができる問題。
2.yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。
3.問題の探索状態を木で表したとき、yes にたどり着く最短距離が問題のサイズの多項式に比例する問題。
端的に説明するときは 2番目の定義（多項式時間で検算可能）が用いられることが多い。

なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。

このような事が書かれていました。

クラスNPは決定問題のクラスのはずですが、
非決定性チューリングマシンは決定問題以外も扱える為、
「非決定性チューリングマシンによって多項式時間で解くことができる問題。」のように定義してしまうと、
決定問題以外も扱えるクラスになってしまいます。

という事は非決定チューリングマシンは決定問題しか扱えない計算機という事なのでしょうか。

この記事見てから全体的に混乱してきたので解説お願いします。。。

**名無しさん＠お腹いっぱい。** · 2007/06/21(木) 21:22:29

>>93
チューリングマシンは論理的な仮装な計算機でしょ？
計算は論理的に実行され、結果も論理的に出される。
このチューリングマシンにハードウエア乱数機のような決定できない
要素がある解釈があるかもしれませんが。
それは無しと考えれば、どのような計算であっても結果は論理的な
値を示します。
これは初期条件が同じであれば何度やっても同じという意味になり
ます。
Yes/Noで答えられるという定義は何ですか？
何処かに閾値を持ちそれと比較してデジタル化したものは
全てYes/Noで良いのでしょうか？

もっと単純に考え、解ける問題と解けない問題。
解ける問題は正しい論理的な手順と仕組みで解決できる。
これはチューリングマシンで実行すれば論理的な答えがだせる。
解けない問題は仕組み上答えが曖昧であったり概念的であったり
波打つような状態やカオスのような混沌の状態を示すものでは
ないでしょうか？

**名無しさん＠お腹いっぱい。** · 2007/06/21(木) 22:18:34

>93
>クラスNPは決定問題のクラスのはずですが、
>非決定性チューリングマシンは決定問題以外も扱える為、
>「非決定性チューリングマシンによって多項式時間で解くことができる問題。」のように定義してしまうと、
>決定問題以外も扱えるクラスになってしまいます。

ならない。決定問題（判定問題）のみを考えているので、1の「多項式時間で解く」というのは「（入力長の）多項式時間で判定する」という意味。
Complexity Zooを見ると、「探索問題で非決定チューリングマシンで解けるクラスはFNPと言う」だとさ。

>94
意味が分からない。

**名無しさん＠お腹いっぱい。** · 2007/06/21(木) 22:51:20

>>94
つ　ゲーデルの不完全性定理

93 · 2007/06/22(金) 09:36:38

>>94-96
どうもです。

wikiの定義の意味が

判定問題も函数問題も、非決定チューリングマシンでは同等の計算量で
解決出来る問題であるため、判定問題であるかどうかの如何に関わらず同値として扱われる。

という意味で書かれている文だと思ってしまいました。
すみません。

93 · 2007/06/22(金) 10:39:43

決定問題の事でさらに疑問が出てきたので質問です。

私は単に問題そのものがyes又はnoで答えられる問題が決定問題であるならば、
非決定性チューリングマシンではなく非決定性有限オートマトンで十分な気がします。

わざわざ「非決定性チューリングマシン」としているということは、
メモリを無制限に使っても良いので解決できる決定問題と考えられます。

ここで私が気になった事は、例えば

関数f(i-m)：何らかの条件の下にyesとなる一つの要素を返す
　　　　　　　　(i-m内に要素がある場合は、必ずyesと判定される要素がある)

i:入力の要素の集合
m:メモリの書き込まれた要素の集合

のようなものを考えると

f(i-m)が要素を返さなくなるまで繰り返してf(i-m)を呼び出し、
メモリに存在する並び替えられた要素を読むだけで解決できる問題は、
yesまたはnoで答える決定問題の繰り返しとみなせるため、
非決定性チューリングマシンで解決できる決定問題と思えるかもしれませんが実際のところどうなのでしょうか。

※つまり、ソート見たいに一つずつ要素を決定していく事で解決できるような問題は
　非決定性チューリングマシンで解決できる決定問題といえるのでしょうか？

おねがいします。

**名無しさん＠お腹いっぱい。** · 2007/06/23(土) 00:37:05

無限とは概念であって、論理的な手法で構築される概念では
無限とは物理や科学の無限の概念と同じで、底無しの無限ではなく
極限に大きな数値で評価すれば無限と同等と見なせる無限をいいます。
つまり測定可能、数値として扱えるものが有効な無限なのです。
極限に大きなメモリや命令語で実現可能なものであれば事実上の無限と
表してもいいかもしれませんが、底が無い訳ではない点を考慮してください。

仮にでも設定できる、値として表現できる、数値として表せるものが
科学や物理界の無限です、仮にでも設定ができるのです。つまり
【計れるものです】計れなければ大小の概念も通じません。
数学の無限でも整数の中での偶数の無限個と整数全体の無限個では
数の「大小の概念が通じる」測れる概念の中に存在します。

これに対して、仏教や哲学での無限とは、【計りしえないもの】を
意味しています。これは底が無いし、それを特定もできない。
デララメに近いような概念です。これは「大小の概念すらありません」。

93 · 2007/06/23(土) 09:21:41

>>99
当然、クラスP,NP共に計算可能な問題のみを扱うクラスなので、
使用できるメモリが有限であることは改めて議論するまでも無く自明です。

ここでチューリングマシンのメモリを無限と定義されているのは、
あらゆる有限長の情報を格納できるようにするためです。

私が「メモリを無制限に使っても良いので」と表現したのは
これと同様にあらゆる計算可能関数の実行を実現できるように表現したためです。

私が気になっている問題は、決定問題を繰り返し行う事で解を求める事ができる問題は
決定問題であるか否かということです。
メモリが、無限であるかの如何はここではあまり重要ではありません。

例えばN個の要素{1,3,2,}という入力が与えられたとき、個の中で最大の要素を求める事は
・1は{1,3,2,}の中で最大の値であるか?
・2は{1,3,2,}の中で最大の値であるか?
・3は{1,3,2,}の中で最大の値であるか?
という決定問題と見なす事ができるかもしれない。

ここでyesの物である3をメモリに書き込み
残った{1,2}を同様の決定問題として計算し、2をメモリに書き込む、
また同様に1をメモリに書き込むという処理を行えば、
メモリには「1,2,3」の順に並び格納されることになる。
これは要素のソートに等しいだろう。

つまりこのように、問題の解その物はyes/noで答えているものではないかもしれないが、
問題を解決する過程を全て決定問題にすることができる問題は、
非決定性チューリングマシンで解くことのできる決定問題と見なす事ができるかどうかということです。

おねがいします。

**名無しさん＠お腹いっぱい。** · 2007/06/23(土) 09:49:51

>>100
>非決定性チューリングマシンで解くことのできる決定問題と見なす事ができるかどうかということです。

そうなんじゃないか？
例えば有名なTSPは明らかに決定問題ではないが、NP完全だと言われているのは、TSP(k)という決定問題に還元できるからだったと思う。
（還元って言葉の使い方がここで合ってるのかどうかはよく知らんが）

93 · 2007/06/23(土) 10:42:50

>>101
TSPでNP完全な物はハミルトン閉路問題見たいに最初のノードから全てのノードを通って
(同じブランチを2度以上通らず)また最初のノードに戻る経路が存在するかどうかを問う物に限定され、
その他の一般的なTSPはNP完全とは言えないらしい(久保幹雄著巡回セールスマン問題への招待より)
一般的なTSPはNP困難と呼ぶべきとの事。(NP完全クラスもNP困難クラスの部分集合だが。)

でも、何故NP完全とは言えないかの理由に距離の比較などを行わなければならないと記されており、表現が曖昧。

私は、これは距離が0または1であるとは限らないため決定問題と言えず、NP完全と言えないということと解釈していたが、
例えば2進数で距離を表して距離の10桁目は0であるか?
見たいな事をyes/noで答えること繰り返す事で比較できるような決定問題と見なせるようにも思えました。

謎は深まるばかり・・・・。

**名無しさん＠お腹いっぱい。** · 2007/06/23(土) 14:08:50

>102
>私は、これは距離が0または1であるとは限らないため決定問題と言えず、NP完全と言えないということと解釈していたが、
>例えば2進数で距離を表して距離の10桁目は0であるか?
>見たいな事をyes/noで答えること繰り返す事で比較できるような決定問題と見なせるようにも思えました。

1行目が正解。
詳しくないので細かいことは言えないが、繰り返しの話は探索版から決定版への自己帰着の話に近いと思う。

93 · 2007/06/23(土) 14:41:02

>>103
確かに数値の比較まで決定問題化できるかどうかまでをするのは、あまりよくなかったかもしれないです。。。

ということは要素の並び替えのようなものも「決定問題化できる」という理由で決定問題にするのは、
あまり良くないかもしれないですね。。。

となると、問題そのものがyes/noで答えられるか否かを問うもののみを決定問題として扱い、
P,NPクラスのものは、そのyes/noを答えるまでにメモリを有限数使用しても良いと考えるべきかも知れないですね。

　　　　　　　　　　　　 _ 　　,.'｀ｰ .､　 _r;N´, '　　　＼て_　　　　　／ .;'
　　　　　　　 r､　　!:`-/　　　ー''´　　　ヽ.　　　　＼,.'ヽ　　／　　.!
　　　　　　　　 !. ヽ　{.　!　　　　　　 _,.r;､,r‐'- ｭ ,,.　　＼,!_..'　　 . '
　　　　　　　　 !　　＼　{　　　　 ,. '",,;r;､､｀､` ､､｀ヽ　　/　　ノ　　　　　 .＿,,. -,
.　　　　　　　　　{. 　　　ヽ.'- ､ ,.／／,.'! i. }.iヽヽヽヽ. } `;/　 ,. ´　　 ,. -‐ ''~￣　　 ,. ’
　　､'' ~￣~ ''' ｰゝ.　　　｀　,;'' ,. ' ,/,' {　! .!.! .!　｝; .｝ ! } ,!　 ' ~￣ ~'' ､　　＿,,. -‐''’
　　　＼ _　,. -‐',ヽy ､ｰz　〃 f' .´{ !　!､!. l l　} ,} !.i ! ! ;ｨ　　　　　　　ヾ~　　　_,,. -‐ '';
　'､￣￣　￣~~¨ ； !.　ヽ. 　 { i　! { ,!ﾅ!_{-'{. !.i　! !ﾅ,!ﾅ,! ｛　　　　　　　　 } ,. =_'~,,. -‐ー ‐-ｭ
　　~ ー-, -─;'' ''ゝ!　　＼ヽ.N ,!{ !r'､ヽ I i { ,!ﾉ,r.'､.ヽ,! ;ゝ. 　・　　・ ,.'　　 _,,.＿ ,,,,. -─’
　　　 .'_´　_.f　　くヽ. 　　ヽゝ､ !I!ゝ.' ! 　　　! ゝ.' iI,!ﾘr,!!'' ー '''' ~ヽｰ'''" ,'　　ﾌ納得できました。
　　　　　￣z_ｰ- .､ ,. -' ｰz_　ゝ_ 儿ゝ.ノ　 ,　　　ゝ._ノ　ｧノ└=ー-､／ __／　,／　どうもっす。
.　　　　　　　~ ーz＿,,,..,ｒ'　　　　ｉ!ゝ.　　　ワ　 ,r'!r‐ '~ 二.~/　i,!ヽ｝.i/,!　　,.｢
　 ,. -‐ ''' ~￣ ~' 'ー '~ｭ　　　　　　　ﾞ　;r r‐,r ,r' ''"~￣ヽ.＼_,! ハ}_,}_,.r''~　
　ｰ .､　　　　　　　　 ,.　　　　　　・人ゝr' ~　　　　　 ,!　　｝ﾉ,,!!_/
　　　　~'' ー-─ ''',"/,儿.　　・　　　 . 'ヽ .〈,　　i　;;.. ,/ _,!　　,!ｿ’､. ￣~ ｰ;z
　　　　　　　　　 /,.'〃- ' ゝ.　_＿ ,,,.. ',; -‐ ''’　　,,! :'　,ﾉ　 !─''’ ｰ -} 　　 ,! !
　　　　　　　 { f/,'､,. 　｀' ゝ/　　 k 　　　　　 ,._-‐'"_/~_ ｰ - .､{　　　〉`;
　　　　　　　　 !〉,{ 　＼_ ,. r‘_ｰ- .､,Z_＿ ,,.. -‐ _'ソ_｀＼~ヽ.　ヽ.　ヽ.　　〈 ,´
　　　　　　　　ヽ.!　　 {　　〉,,　　　　　　 ,,　__ノ　､.,!. 　ヽ.　＼　`,.「　　 ,/'

**名無しさん＠お腹いっぱい。** · 2007/07/03(火) 17:23:09

計算機の高速化の方法について高専の授業の課題
でまとめなければならないのですが、いったいどのような
方法があるのでしょうか？
自分で調べてみたのですが、やふってみても、ぐぐってもわかりませんでした
おねがいします

**名無しさん＠お腹いっぱい。** · 2007/07/03(火) 18:10:23

計算機が遅くなりそうな理由をとことんまでつきつめて考えろ

**名無しさん＠お腹いっぱい。** · 2007/07/04(水) 03:33:30

>>106
一見不親切そうだが，高速化の技術ってボトルネックをどう解消するか，が
一番大事ではあるね。

>>105
Seymour Crayの生涯をたどってみれば？

**名無しさん＠お腹いっぱい。** · 2007/07/06(金) 22:41:09

一組のトランプカード(ジョーカーを除く)５２枚から一枚とって、
それがスペードのエースであることを知り得た情報量は何ビットか？

↑この答え分かる方おらっしゃいましたらぜひ教えて下さいませ。

**名無しさん＠お腹いっぱい。** · 2007/07/07(土) 00:01:23

>>108
宿題は自分でやれ

**名無しさん＠お腹いっぱい。** · 2007/07/07(土) 12:21:56

>>108
残念だが俺にはわからない

**名無しさん＠お腹いっぱい。** · 2007/07/11(水) 00:22:49

すみません、皆さまの知恵をお貸しいただけないでしょうか。お忙しいのに恐縮です

ある問題を解くアルゴリズムがあり計算量が入力サイズxに対してlogxである。またコンピュータは1つの命令を10＾（-6）秒で実行できる。

n=100のときの計算時間を求めよ

**名無しさん＠お腹いっぱい。** · 2007/07/11(水) 00:26:40

すみません、x=10のときでした。

計算量って単位がないから秒と計算できるんですか？
自分では(log100)×10＾(-6)かなと思ったんですが違いますか？

お助けください

**名無しさん＠お腹いっぱい。** · 2007/07/11(水) 03:37:48

プロ野球の結果を計算で予測することは可能ですか？

**名無しさん＠お腹いっぱい。** · 2007/07/11(水) 10:55:29

>>112
x=10と訂正しておきながら何故log100と記した？

>>113
結果の精度が低くてもいいなら可能でしょう。

**112** · 2007/07/11(水) 11:03:58

すみません、log10でした。
これであっているでしょうか？

**名無しさん＠お腹いっぱい。** · 2007/07/11(水) 16:14:49

誰かお願いできませんでしょうか。

答えは log10*10^(-6)であってますから？

**111** · 2007/07/12(木) 00:00:27

誰も答えてくれないので数学板でしつもんするので却下します

**名無しさん＠お腹いっぱい。** · 2007/07/12(木) 00:10:42

辞書ひけ

**名無しさん＠お腹いっぱい。** · 2007/07/12(木) 02:14:11

【参院選】民主党から、在日コリアンの期待背負った金氏（民団幹部）が立候補…在日参政権訴え
http://news22.2ch.net/test/read.cgi/newsplus/1184165873/l50

**名無しさん＠お腹いっぱい。** · 2007/07/12(木) 14:02:41

大学の定期試験ででこういう問題が出ました。
計算機が情報を表現する原理を４００字でまとめろと出たんですが。

僕の頭では正直言いまして分かりませんでした。誰かマジで教えてください。
お願いします。

**名無しさん＠お腹いっぱい。** · 2007/07/12(木) 17:27:26

>>120

俺だったら、

現在の計算機が扱える情報は大きく分けて「数値」と「文字」の二つではないだろうか。
計算機であるからには、当然数値の計算を行うことが、できなければならないし、
計算の結果を人間に分かるように出力できなければならないため、文字という情報も扱えなければならない。

見たいな感じの出だしで書き始め、
その後に2進数とか補数表現とか文字コード表とか適当に語って終わると思う。

まぁがんがれ。
俺も別な試験で死にそうなんだ。

**名無しさん＠お腹いっぱい。** · 2007/07/12(木) 22:58:36

別スレで書いたのですがスレ違いっぽかったのでこちらで聞かせてもらいます。
￢x∨yをNand（記号|)で表すとしたら
x|(y|y)で合ってますか？

**名無しさん＠お腹いっぱい。** · 2007/07/12(木) 23:19:53

合ってるよ

**名無しさん＠お腹いっぱい。** · 2007/07/13(金) 14:02:10

>>120-121
小論やレポートや試験で「～だろうか」とか「～し、」とかふつう使わない

という揚げ足取りはさておき、
ttp://science6.2ch.net/test/read.cgi/informatics/1160740645/
いっといで。

**名無しさん＠お腹いっぱい。** · 2007/07/13(金) 15:00:57

情報の表現って何だろ？
オブジェクト指向で言うオブジェクトも、いちおう情報の表現か？
究極的には記号列（もしくは２進数）に符号化できる情報は全て表現できるわけだけど
ハードウェアの動作原理にも言及すべき？
何か大学ってのは訳のわからんものを問う場所なんだな

**名無しさん＠お腹いっぱい。** · 2007/07/13(金) 17:49:14

>>125
オブジェクト等も全て含めてコンピュータ内で扱われる情報は全て0と１で表現されている―

的な回答を求めているのだろう。

**名無しさん＠お腹いっぱい。** · 2007/07/13(金) 21:59:15

任意の大きさの自然数をビット列で表現できることを示し、
したがって可算な集合の要素をビット列で表現できることを確認した後、
現実にはビット列の長さに上限があることからどういう影響が出るか考察したうえで、
具体例としてテキストと音声と画像と二分木がどのように表現されるかを解説して終わる。

ってのを思いついた。

**名無しさん＠お腹いっぱい。** · 2007/07/13(金) 22:47:49

計算機が扱えるのは数値だけ。人間が数値に意味を付けているにすぎない、と俺は思っている。

**名無しさん＠お腹いっぱい。** · 2007/07/14(土) 14:27:25

>>127
「ビット列」は自然数を2進法で書いただけのこと。
計算機方向から見たとき，どっちかというとゲーデル数の発明で，
自然数といろんなものに1対1対応がつく，って方が本質かと。

符号屋はシャノンと言うだろうがな。

**111** · 2007/07/15(日) 03:58:17

すみません。
誰か>>111をお願いします。
数学板で聞いたらシカトされました
x=10のときです

助けてください

**名無しさん＠お腹いっぱい。** · 2007/07/15(日) 05:12:10

>>129
ゲーデル数ならいいけど、自然数と言ってしまうと「順序」という性質があるから微妙な希ｶﾞｽ
ビット列同士の順序は計算機にとって何の意味も持たないからね

>>130
111に書いてある「計算量」が「命令数」だと仮定するなら、
log xの天井をとってから10＾（-6）秒をかければいいだけじゃね？

**111** · 2007/07/15(日) 08:36:07

>>131
ありがとうございます。
お礼させてください。３千円くらいでいいですか？

**名無しさん＠お腹いっぱい。** · 2007/07/16(月) 21:08:54

計算機の限界って処理速度でＯＫですか？

**名無しさん＠お腹いっぱい。** · 2007/07/16(月) 22:07:30

|A|=m, |B|=n, m>=nのときA→Bへの全射は何通りですか？

**名無しさん＠お腹いっぱい。** · 2007/07/16(月) 23:49:46

>>134
n^m - ΣnCj (n - j)^m かな？（j = 1 から n - 1 まで）
写像としてあり得る全組み合わせから、全射にならないものを引いてみたけど
もっと単純な考え方もあるかもしれん

**名無しさん＠お腹いっぱい。** · 2007/07/17(火) 20:28:13

>>135
ありがとうございます。
エレガントな方法はあるのでしょうかねぇ。

**名無しさん＠お腹いっぱい。** · 2007/08/08(水) 12:08:21

ttp://seo.fc2.com/keywordrate/

みたいな、文章から単語を抜き出して分類する、ということをやりたいんですけど、
このスレで質問していいんでしょうか

**名無しさん＠お腹いっぱい。** · 2007/08/08(水) 14:24:15

形態素解析でググれば一発で終わりそうな質問になりそうな気もするが

**名無しさん＠お腹いっぱい。** · 2007/08/09(木) 20:37:04

>>138
ググったらいろいろ出てきました！
ありがとうございます！

**名無しさん＠お腹いっぱい。** · 2007/08/11(土) 00:43:25

猛者の方教えて下さい。

２次元格子面(x_i, y_i) (i=0,...,N) 上の値 f(x_i, y_i) が判っているとき
格子上に無い(x,y)に対して f(x, y)の値を内挿するシンプルで精度のよい
方法にはどんなものがあるでしょうか？

双３次スプライン補間はそれなりにシンプルで精度がよいのですが、
x方向に補間した後、そのセットに対してもう一度スプライン曲線を計算した上で
y方向の補間に行くため計算速度の面で間に合わないです。
求めたい(x,y)がランダムにN×N程度あるので毎回スプライン曲線を計算するのが
コスト高なのです。そういう観点から双２次スプラインも使えないです。

一方で双１次平面補間ですとちょっと精度が足りないです。

そんなのねーよ、とか言われそうですが、ちょっとしたアイディアでも大助かりです

**名無しさん＠お腹いっぱい。** · 2007/08/11(土) 11:35:19

２進数（0.00001）×２の‐１乗を正規化表現すると何ですか！？

**名無しさん＠お腹いっぱい。** · 2007/08/11(土) 12:05:50

10進数の 0.00234×10^-5 を正規化したら 2.34×10^-8

**名無しさん＠8周年** · 2007/08/15(水) 09:18:50

>>133
計算機の限界は細かく言うとメモリーバンド幅とかチップセットの性能とか
にも影響を受ける部分が有りますよ。

**名無しさん＠お腹いっぱい。** · 2007/08/19(日) 16:10:49

>>136
エレガントってほどじゃないけど、
Aから、|B| 個の要素を選び出す　（ mCn通り）
選び出したものから、Bへの置換を作る　（ n!通り）
選ばなかったものから、Bへの写像を作る　（　n^(m-n)通り　）
で、mCn*n!*n^(m-n)っていう答えもありだと思う

**名無しさん＠お腹いっぱい。** · 2007/08/19(日) 16:12:32

あっ、ごめん144だと重複があるからやっぱだめだ

**名無しさん＠お腹いっぱい。** · 2007/08/21(火) 17:44:13

ファインマン「計算機科学」の第１章の問題の模範解答をだれか・・・

**天才様へ** · 2007/08/26(日) 11:00:19

253398→7a4c395e79 になるんですが、→は何をしたかわかる人いますか??

**名無しさん＠お腹いっぱい。** · 2007/08/26(日) 21:54:30

16進への変換

**天才様へ** · 2007/08/27(月) 00:35:12

それはもうやったんですけど無理でした(汗)
16進数に変換して、数が増えるなんておかしくないですか??

**名無しさん＠お腹いっぱい。** · 2007/08/27(月) 04:03:10

>>149
別に

**名無しさん＠お腹いっぱい。** · 2007/08/27(月) 07:30:32

右と左はイコールで結ばれてないからたぶん足し算してから変換したんだな

か · 2007/08/27(月) 09:26:47

た

**どういうことですか??** · 2007/08/27(月) 09:28:16

お願いします詳しく教えて下さい_(._.)_

**名無しさん＠お腹いっぱい。** · 2007/08/28(火) 11:37:36

3DDD6(16進)＝253398(10進）
>>153
１６進変換ができる電卓ならＯＳにも付属しているし
検索すれば、その辺のＷＥＢサイトでできるところもあるだろ。
故に「→」は「＝」以外の計算をした結果だろ。
ぱっとみて、何かのアルゴリズムを通して変換したんでしょう。
それを何かと聞かれても片っ端からアルゴリズムを試して
やってみるしかない、出題者が過去に提示したアルゴリズムや
変換の何かの１つである可能性が高いのでそれを探るべきだろう。

**名無しさん＠お腹いっぱい。** · 2007/08/30(木) 18:44:36

もうこういうのは無視して良いのではないかな

**名無しさん＠お腹いっぱい。** · 2007/10/11(木) 20:13:34

Ｐ＝ＮＰ問題解いたらフィールズ賞取れる？

**名無しさん＠お腹いっぱい。** · 2007/10/11(木) 21:18:21

たぶんチューリング賞だけ

**名無しさん＠お腹いっぱい。** · 2007/10/17(水) 23:18:53

チューリング章、フィールズ章、ノーベル賞（肯定的にといた場合）を取れるよ

**名無しさん＠お腹いっぱい。** · 2007/10/17(水) 23:44:04

ノーベル何賞よ

**名無しさん＠お腹いっぱい。** · 2007/10/18(木) 07:29:34

平和賞

**名無しさん＠お腹いっぱい。** · 2007/10/26(金) 12:21:08

欽ドン賞

**名無しさん＠お腹いっぱい。** · 2007/12/10(月) 01:33:26

>>158
一番確実なのは、まずネヴァリンナ賞だろ?
計算論関連の人が多いし。

次にゲーデル賞もほぼ確実

>チューリング賞
ネヴァリンナ賞より応用よりだが、これも取れそう。

>フィールズ賞
十分ありえるけど、ネヴァリンナ賞とは同時に選考が決まる賞で、
賞の趣旨も同じなので、
重複を回避される可能性もなきにしもあらず。
計算機科学の人が取った例はない。

>ノイマンメダル
チューリング賞よりさらに応用よりなので、厳しい

>ウィーナー賞
社会性を重視するのでたぶん無理

**名無しさん＠お腹いっぱい。** · 2008/01/23(水) 00:31:56

情報記号系列1,0,1,1に対し、パリティ検査記号C1,C2,C3を生成せよ
って問題なんですが、わかる方教えてください。よろしくお願いします。

**名無しさん＠お腹いっぱい。** · 2008/01/23(水) 17:38:17

>>163
"情報記号系列パリティ検査記号"でぐぐったら
日本語の講義資料が山ほど出てきたぞ
おかげさんで忘れかけていた知識の復習ができた
ありがとうｗ

**名無しさん＠お腹いっぱい。** · 2008/01/24(木) 05:13:01

>>120
「情報」と「表現」の言葉の範囲が広すぎるなあ

**名無しさん＠お腹いっぱい。** · 2008/01/24(木) 19:50:20

>>134-136
ものすごい遅レスなんだけど
恵羅博, 土屋守正「組み合わせ論」産業図書, 1996.
ISBN4-7828-5354-8
のpp.88-94にメービウスの反転公式とそれを用いた全射の個数の数えあげ公式の説明がある

|Sur(A, B)| = Σ_{i=0}^{n} [ { (-1)^(n-i) } * nCi * { i^(m) } ]
（nCiは二項係数）

**名無しさん＠お腹いっぱい。** · 2008/01/27(日) 00:30:06

f(x)=2cos(x)+0.5x+0.8について
newton法を用いて近似解が反復によって
１つの解に近づくことを示せ

sailabの問題なんですが
deff('[y]=f(x)','y=x^4-4*x^3+6*x^2-4*x+1');
deff('[dy]=g(x)','dy=4*x^3-12*x^2+12*x^2-4');
x=-5:0.05:5;
x0=-5;
xx=[x0];
for k=1:4;
f0=1;
df0=-4;
x1=x0-f0/df0;
xx=[xx x1];
x0=x1;
end
fplot2d(x,f,log=5)
fplot2d(xx,f,-2)
コレをどういじっていいのかわからなくて
どなたかご指南よろしくお願いします(><;)

**名無しさん＠お腹いっぱい。** · 2008/01/27(日) 01:29:40

書名間違えた>>166
「組み合わせ論」じゃなくて「組合わせ論」だ
こういうのってどっち使うか決まってるのかな？

**名無しさん＠お腹いっぱい。** · 2008/01/27(日) 01:38:27

「組合せ論」って書く人もいるね

**名無しさん＠お腹いっぱい。** · 2008/01/27(日) 01:39:43

国語審議会かなんかだと、名詞として使う場合は送り仮名等は無し、
動詞として使う場合は送り仮名等有りだった希ガス

**名無しさん＠お腹いっぱい。** · 2008/01/27(日) 14:38:43

学術用語として正式なのは>>169だったような

**名無しさん＠お腹いっぱい。** · 2008/01/28(月) 04:37:19

>>168さらに訂正
本当に正しい書名は「組合せ論」（シリーズ/情報科学の数学）でした
この本の巻末で参考文献に挙げられてる本もみんなタイトルが「組合せ論」になってる
表記はちゃんと統一されてるんですね

**名無しさん＠お腹いっぱい。** · 2008/01/31(木) 11:31:55

うちの教授が「組み合わせ」や「組合わせ」を使ってたら、
組合せ論やってる人に「組合せ」が正解と指摘されたって言ってた。

「組み合わせ」や「組合わせ」を使う奴は素人なんだってさ

**名無しさん＠お腹いっぱい。** · 2008/02/02(土) 22:52:22

チューリングマシンの計算能力を超えることはできますか？

**名無しさん＠お腹いっぱい。** · 2008/02/03(日) 12:04:49

>>174
オラクル付きチューリングマシン？

**名無しさん＠お腹いっぱい。** · 2008/02/04(月) 11:48:42

>>174
数式の計算以上のことができれば越えているだろう。
それは計算とは呼ばないけどな。

**名無しさん＠お腹いっぱい。** · 2008/02/04(月) 16:29:00

チューリング機械のように、数学的な表現をしたいのですが。

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 00:19:18

>>177
実数を使っていいなら簡単。

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 11:19:16

まともな計算の定式化でチューリングマシンより強い能力を持ったモデルは提案されてない。
だけど、別に不可能って証明されてるわけじゃないから、やってみるのも面白いんじゃない。
無理だと思うけど

まぁ、不完全性定理があるからどんなモデルを提案したところで、判定できない言語が出てくるけどな

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 17:54:10

素人の自分からすると、実数を使ったモデルがチューリング機械
より強力なことは簡単に証明できるのではなかろうかと思えます。
専門の人は、これまでだれもそんなことは考えなかったのですか。

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 21:10:58

実数上の計算やもっと抽象的な構造における計算も色々考えられているけど、
今んとこ結局全部ほとんど変わらん

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 22:14:37

自分の知る範囲では、ラムダ式はいつも自然数とか自然数を扱う
関数が変数になっていると思いますが、そこに実数をあてはめる
とどうなるのでしょうか。近似をしない場合の積分の計算などは、
計算機で扱えないので、チューリング機械の計算を超えていると
思うのですが・・・。

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 22:20:33

とりあえず「そこに実数をあてはめ」たラムダ式を定義してみたら？

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 22:41:09

定義だけなら簡単なんですが、はたしてそれが本当に
チューリング機械の能力を超えたものなのかどうか、
実際にそれを数学的にどうやって示したらいいのかが
難しいです。もしかすると、自然数で実数は正確には
扱えない、ということに関係あるのかもしれません。
不完全性定理そのものを証明に使えるといいのですが。

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 23:00:35

どういうものを考えているのかよくわからないけど、
チューリングマシンの能力を超えてるように見えるの？

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 23:11:48

見えます。たとえば物理などで扱う場というのがあります。
量子場まで考えなくても古典的な電場とか磁場、電子の場
でいいと思います。それらは計算機と違って離散ステップ
ではなく、時々刻々連続的に状態を変化させてゆきます。
状態の種類も離散的でなく、運動方程式に従って連続的に
変化します。このような状態の遷移も一種の計算であると
するなら、チューリング機械の計算能力を超えているよう
に、自分には思えてきます。

**名無しさん＠お腹いっぱい。** · 2008/02/05(火) 23:33:59

何となく気持ちはわかるような気もするけど。
それがラムダ式とどう繋がるのかはよくわからないなあ。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 00:03:23

普通のラムダ式ではないので少し分かりにくいですね。
ｆ（ｒ）を実数上の関数とすると、積分を求める計算は
λｆ（ｒ）．Ｓｆ（ｒ）ｄｒ（ここで、Ｓは積分記号）のように書けます。
運動方程式は通常微分方程式なんですが、積分の形に
書き直すこともできます。つまり場は、上のラムダ式で表さ
れるような積分を連続的に実行しているわけなんです。
毎時、連続無限個の積分計算をするということは、普通の
計算機の能力をはるかに超えていると考えられます。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 00:06:50

それは関数のラムダ記法であってラムダ計算とはあまり関係ないように思う

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 00:11:47

つまり、「積分」は適当な空間から空間への作用素と考えられるけど、
その作用素を単にλを使って書いただけのように見えるんだよね。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 00:12:17

ラムダ計算とは関係ないですが、ラムダ計算以上の
計算が何か関係するのではないかという妄想です。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 01:31:35

Turing機械は高々可算個しかないんだからTuring機械が受理できる数も高々可算個。
だから実数はほとんどすべてTuring機械では計算不能。

モデルのどこかに「任意の実数」を入れていいことにすれば(e.g. ニューラルネットの重み)
簡単にTuring機械の能力を超えられる。

計算不能な数をモデル内に持てるんだから当然と言えば当然だが。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 19:18:16

ありがとうございます。
そんなふうに単純に考えればいいんですね。
場がチューリング機械を超えていいるのはいいとして、
ラムダ計算に対応するものは何かを考察してみます。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 22:07:09

>>192
超えてるってことはそんなに自明かな？
比較不能かもしれない。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 23:17:52

いや、任意の実数を使っていいなら、
少なくとも、その実数をオラクルに用いたオラクル付きチューリングマシンか
それ以上の性能はあるんじゃないか？

オラクル付きチューリングマシンなら、何をオラクルに使うかによるが、
ただのチューリングマシンと同性能か真に強くなる。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 23:23:40

実数を使って何をするのかがはっきりしなかったから。
オラクルつきチューリングマシンなら強くなるけど。

**名無しさん＠お腹いっぱい。** · 2008/02/06(水) 23:39:20

まあ、確かに>>180からの書き込みの人が何をしたかったのかが正確に分からんから
オラクル付きチューリングマシンより強くなるとは言い切れないのか

**名無しさん＠お腹いっぱい。** · 2008/02/07(木) 08:56:30

ちょっと前の数学セミナーで数学者スメールの解説記事が載ったときに
近年はトポロジー以外に実数上の計算理論を研究してると読んだ記憶がある
ぐぐったらBlum Shub Smale machineとかいろいろ出てきたけど
>>181で言われてるのはそういう研究ですね

**名無しさん＠お腹いっぱい。** · 2008/02/08(金) 21:49:15

書き込むまでもないかもしれないが、実数上の計算理論なんか論文検索でいくらでも出てくるよな。

**名無しさん＠お腹いっぱい。** · 2008/02/09(土) 00:02:35

実数上で計算体系作るのは勝手だけど，それでそう簡単に面白い結果が出るわけじゃないからね。

物理的には，計算不能な数をそもそも無限精度で測定できるのかって話はあるしね。