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

**名無しさん＠お腹いっぱい。** · 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)という決定問題に還元できるからだったと思う。
（還元って言葉の使い方がここで合ってるのかどうかはよく知らんが）