5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :名無しさん@お腹いっぱい。:2006/08/20(日) 19:36:09 ID:07TbwQ840
計算機科学全般についての疑問を投げ付けあうスレッドです。

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

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

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

        2 ゲ ッ ト


3 :名無しさん@お腹いっぱい。:2006/08/22(火) 13:14:47 ID:E6ZR+dBE0
>>1
とりあえず予想されるFAQってことで教科書一覧でも作っておくのはどう?

Hopcroft&Ullmanとか Introduction to Algorithms とか。

4 :1:2006/08/24(木) 20:25:14 ID:iZ9+UT5c0
>>3
良い考えだと思います。私は素人なので教科書を挙げられないですが。

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

5 :名無しさん@お腹いっぱい。:2006/08/25(金) 17:52:03 ID:dRAAwpnL0
パーマン。

6 :名無しさん@お腹いっぱい。:2006/08/26(土) 21:00:12 ID:KFleSFe30
計算幾何学
計算機化学
も当然ここでいいの?

7 :CS:2006/09/03(日) 14:27:05 ID:P7V1hH3n0
計算機科学者って、パソコンの自作とか得意ですか?

8 :名無しさん@お腹いっぱい。:2006/09/03(日) 15:09:58 ID:cMGWCLwU0
http://blogranking.fc2.com/in.php?id=78352

9 :名無しさん@お腹いっぱい。:2006/09/03(日) 15:40:01 ID:uwq02sGT0
>>7
長尾眞元総長はパワーポイントをろくに触ったことがなく,
真っ白で何のアニメーションも無いスライドを作っていたぞ。

10 :名無しさん@お腹いっぱい。:2006/09/03(日) 16:24:31 ID:oRmQLMDE0
>>7
理論系は基本的に数学者なので苦手な人は多い。
たとえば,論文を書く必要上TeXは使えるがTeXのインストールができる人は少ないと思う。

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

11 :名無しさん@お腹いっぱい。:2006/09/11(月) 18:58:42 ID:E48iOr/g0
IPC(Instructions per Cycle)の「I」には分岐予測ミスしたパス上で実行された命令も含まれるんですか?
その場合、せっかく分岐予測率を向上させて「C」を減らしても「I」が同時に減るから
IPCには努力の成果があまり現れないんじゃないですか?


12 :名無しさん@お腹いっぱい。:2006/09/11(月) 22:34:18 ID:n9q3zFJw0
>>9
極めるとそこに行き着くんだよ。村井純でもそういうパワポ見たことある。
俺も最近はそういう奴の方が人に訴える力があるような気がしてきた。

13 :名無しさん@お腹いっぱい。:2006/09/12(火) 00:04:11 ID:lr4vV28g0
>>12
つ[高橋メソッド]
TeXでもプレゼンが簡単に作れて便利。

14 :名無しさん@お腹いっぱい。:2006/09/15(金) 01:45:40 ID:adBWh5a50
平面上のn点が与えられて,
各点へのユークリッド距離の和を最小にする点を求めるという問題.
四分木を使う解法しか思い浮かばなかったんだけど,他にないかな?

15 :名無しさん@お腹いっぱい。:2006/09/15(金) 19:24:47 ID:6gBJ44kJ0
すみません。どうしてもここだけわからないので教えてください。

負数を2の補数で表す8ビットの数値がある。この数値を10進数で表現すると、
−99である。この値を符号なしの数値として解釈すると、10進数でいくらか。

考え方も添えて教えてください><

16 :名無しさん@お腹いっぱい。:2006/09/16(土) 06:21:38 ID:zFZyLXjA0
8ビットの数値においてxの2の補数とは256-xのことである。
-99は99の2の補数、すなわち256-99 = 157として表される。
符号なしの数値として解釈すると、この値をそのまま読むことになる。よって157。

17 :名無しさん@お腹いっぱい。:2006/09/16(土) 08:27:10 ID:9f4o96tq0
>>16
マジでありがとう御座います。助かりました!
いい人いるんだなぁと実感しました。本当にありがとう!

18 :名無しさん@お腹いっぱい。:2006/09/16(土) 21:43:19 ID:s7KuEtt+0
>>14

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

ちゃんとやってないので適当でスマソ

19 :名無しさん@お腹いっぱい。:2006/09/17(日) 08:20:11 ID:QovWuoZsO
1000x+221y=3となる整数x,yを一次不定方程式で一組もとめてください(-.-)y-~恥ずかしながら情報数学のいっちゃん最初です(笑)

20 :名無しさん@お腹いっぱい。:2006/09/17(日) 09:27:00 ID:nS/VR71U0
>>19
-120, 543

21 :名無しさん@お腹いっぱい。:2006/09/17(日) 18:59:57 ID:QovWuoZsO
ありがとうございます!

22 :14:2006/09/18(月) 02:33:19 ID:qJlR3PTs0
>>18
山登り方でできないかな〜と思ったんだよね
できればそれが一番速いし

23 :名無しさん@お腹いっぱい。:2006/09/18(月) 09:57:40 ID:buPJAok00
>>14
どう見ても凸計画だし条件も良いから,最急降下が効率よくうまく動くと思う.

24 :14:2006/09/19(火) 00:59:15 ID:lxGK4FLo0
>>23
なるほど、凸計画がキーワードなんですね
色々調べて勉強になりました
ありがとう

25 :名無しさん@お腹いっぱい。:2006/09/23(土) 10:52:02 ID:Cs2hCf370
k-tapeチューリングマシンは、1-tapeチューリングマシンと同等の能力があることは、テープ圧縮法で証明するようなのですが、実践的な部分が理解できません。
たとえば、以下の2-tapeチューリングマシンのプログラム(回文=palindromeを受容する)を1-tapeチューリングマシンで書き表すとどうなるか、わかる人いますでしょうか?

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

26 :名無しさん@お腹いっぱい。:2006/09/23(土) 10:52:34 ID:Cs2hCf370
回文(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", □, -, >, →)

27 :名無しさん@お腹いっぱい。:2006/09/23(土) 10:53:27 ID:Cs2hCf370
動作の雰囲気としては、
状態sで、入力文字列のあるテープ1の内容を、左から右に移動しながら、テープ2にコピーします。
右端(空白である□)に達したら状態qに遷移。
状態qでは、単純にテープ1のテープヘッドを左端まで移動させます(テープ2のテープヘッドは右端に置いておきます)。
左端に達したら状態pに遷移。
状態pでは、テープ1上を右方向に、テープ2上を左方向にスキャンして、互いに異なる記号があったら即座に"no"を返します。
テープ1の右端、テープ2の左端まで達することができたら、回文であるということなので、"yes"を返します。

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

28 :名無しさん@お腹いっぱい。:2006/09/23(土) 12:21:13 ID:xSlS4u2k0
>>27
宿題は自分で,と言いたいところだけど
大学の後輩だったらどうしようと思ったので一応説明してみるテスト。

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

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

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

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

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




29 :25-27:2006/09/24(日) 03:16:59 ID:uw2Mkm0J0
>>28
レスどうもです!
全部のテープのアルファベットをそれぞれの位置ごとにエンコードするってことまではわかりました。
でもちょっとまだ理解しきれないところが・・・。
それぞれのテープのカーソル位置っていうのは、任意のステップで別々の場所にあるわけですけど、それをどういう形で記憶し、実際の動作にどう反映させるのでしょうか?

30 :名無しさん@お腹いっぱい。:2006/09/24(日) 04:12:55 ID:VVNV0IIP0
>>29
カーソルの位置を表す専用のトラックを用意すると簡単。

31 :名無しさん@お腹いっぱい。:2006/09/26(火) 08:18:15 ID:/vRSNA7M0
日本語の形態素解析に、隠れマルコフモデルを利用すると、従来に比べて精度良く
形態素解析出来るとの事で、茶筅と言うプログラムが発表されてます。
次に、隠れマルコフモデルより更に精度良く、高速に形態素解析出来るCRFと言う
考え方でめかぶと言うプログラムが発表されてます。

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

32 :名無しさん@お腹いっぱい。:2006/09/26(火) 09:38:49 ID:vIVVej2C0
宿題は自分でやること。


33 :名無しさん@お腹いっぱい。:2006/09/26(火) 10:29:13 ID:/vRSNA7M0
>>32
しゅくだいじゃねーよぉーーーーーーーー!!・゚・(つД`)・゚・

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

34 :名無しさん@お腹いっぱい。:2006/09/29(金) 18:30:50 ID:z4oUp5jI0
計算量ってなに?どゆこと?

35 :名無しさん@お腹いっぱい。:2006/09/29(金) 21:41:32 ID:QZqjNtjc0
>>26
何かの絵文字に見えてしまった

36 :名無しさん@お腹いっぱい。:2006/09/30(土) 06:47:07 ID:lId/Rbue0
>>34

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

37 :名無しさん@お腹いっぱい。:2006/10/07(土) 01:40:21 ID:17T4SzBY0
ラムダ算法でチューリング機械をシミュレートできるのはわかったけど、チューリング機械でラムダ算法をシミュレートできることを、どうやって証明するんですか?

38 :名無しさん@お腹いっぱい。:2006/10/07(土) 09:18:28 ID:gh33XBEyO
>>37
前者を自分の言葉で誰かに説明してみ。2chじゃなくて、手近な人に。

ま、ここでもいいけど。

39 :名無しさん@お腹いっぱい。:2006/10/08(日) 04:48:09 ID:sGZQmW2J0
>>38
ごめんなさい。できません。

40 :名無しさん@お腹いっぱい。:2006/10/09(月) 16:59:32 ID:2Xl6HeSL0
むしろ後者のほうが証明は直感的にできると思うんだけどな.

41 :名無しさん@お腹いっぱい。:2006/10/09(月) 21:07:05 ID:08AWkT8w0
パソコンでLISP処理系が実装できるわけだしねぇ。

42 :名無しさん@お腹いっぱい。:2006/10/09(月) 21:08:12 ID:08AWkT8w0
IDがawkでちょっとうれしい。
Aho って「アホ」的な読み方が正しいらしいけどね。

43 :名無しさん@お腹いっぱい。:2006/10/09(月) 23:05:01 ID:4HxJqkyF0
Lispはatomがあるから、ラムダ計算をシミュレートしてるうちに入らないんじゃなかったっけ?

44 :名無しさん@お腹いっぱい。:2006/10/13(金) 15:50:41 ID:xDuc5z8IO
どこのスレに書けば良いかわからなかったのでスレ違いだったらすいません。

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

45 :名無しさん@お腹いっぱい。:2006/10/15(日) 19:30:31 ID:q73NaSJM0
ヘネパタ嫁

46 :名無しさん@お腹いっぱい。:2006/10/15(日) 20:48:18 ID:LUbZeQCL0
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
これじゃダメか?
浮動小数点でググって一番上にあるんだが。

47 :名無しさん@お腹いっぱい。:2006/10/15(日) 22:44:49 ID:DUffkHOR0
こんな高校生(中学生?)レベルの質問で、へね&ぱたを読め はねぇだろ。 
10進数なら 0.1 = 1/10
2進数なら 0.1 = 1/2
後は計算しな。

48 :名無しさん@お腹いっぱい。:2006/10/22(日) 21:39:00 ID:+TgPQHf00
情報幾何が日本以外であまり使われていないって本当なのですか?


49 :名無しさん@お腹いっぱい。:2006/10/23(月) 16:22:30 ID:+IJD4naX0
さあ?

50 :名無しさん@お腹いっぱい。:2006/10/24(火) 13:13:56 ID:2tqcHnlo0
情報系独特の論文スタイルってありませんか?
情報系だけは日本語と英語同時投稿OKとか

51 :名無しさん@お腹いっぱい。:2006/10/24(火) 20:05:50 ID:tL7bMwQW0
Wikipedia の姚期智について読んでたら思ったのですが、
ヤオの法則ってなん何でしょうか?簡単に説明していただけませんか?

52 :名無しさん@お腹いっぱい。:2006/10/25(水) 09:37:12 ID:SYufx8740
>51
http://en.wikipedia.org/wiki/Yao's_Principle

53 :名無しさん@お腹いっぱい。:2006/11/14(火) 20:47:53 ID:uDdlf8ow0
      ,rn           
     r「l l h 同志!       /        /
     | 、. !j 川崎と京都市南区と大阪生野区には、落とさないニダ!
     ゝ .f       ,r'⌒  ⌒ヽ、 KCIA情報教えてチョ    
     ,」  L_     f ,,r' ̄ ̄ヾ. ヽ.    / /
    ヾー‐' |     ゞ‐=H:=‐fー)r、)    /
     |   じ、     ゙iー'・・ー' i.トソ
     \    \.     l、 r==i ,; |'      ゴゴゴゴゴゴゴ
      \   ノリ^ー->==__,..-‐ヘ__   /  /| /    /
        \      |_/oヽ__/    \   /  |_
         ヽ__    |         \/  /  ヽ___
             |    |   O へ    \ /   /   /
             /   |       |\/  |   /   /
             |   |       |/| _ |  /__/
             |   |       |  「  \:"::/
             |  コ[□]ニ    |  ⌒ リ川/
            / \      /  \ ...:::/
           /    ゞ___     \/   
          /    /     \     \    
         /  ゝ /       .::\ /   |    
         |   /      ....:::::::/\<   |  
         | /      ...::::::::/  |   |  
         /      ....:::::::/    |   |  
        /   ▼ ...::::::::/     |   |   
      /   ▼ ▼..::::::/       |___|    

54 :名無しさん@お腹いっぱい。:2006/11/20(月) 11:51:39 ID:gGlK2Py20
算術関数で1.5乗と1.1乗と常用対数の示し方について教えてください。

55 :名無しさん@お腹いっぱい。:2006/11/25(土) 08:31:22 ID:ZMOY1jdj0
領域理論は何のためにあるんですか?

56 :名無しさん@お腹いっぱい。:2006/12/09(土) 20:31:37 ID:Pfl1+DBh0
あげ

57 :名無しさん@お腹いっぱい。:2006/12/09(土) 20:49:43 ID:/nR6ophT0
うん

58 :名無しさん@お腹いっぱい。:2006/12/26(火) 20:51:39 ID:QfMbYSCSO
すみません、どうしてもわからないんでみなさんに助けていただきたいです。

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

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

59 :名無しさん@お腹いっぱい。:2006/12/26(火) 22:27:29 ID:kAHY42M30

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

オナヌーねたあります


60 :名無しさん@お腹いっぱい。:2006/12/27(水) 03:26:53 ID:1fio0kHw0
>>58
宿題は自分でやれ

61 :名無しさん@お腹いっぱい。:2006/12/27(水) 18:20:45 ID:fWcAszt7O
>>58
黒澤、尾形「現代暗号の基礎数理」電子情報通信レクチャーシリーズD-8、コロナ社、2004
6.3 DH問題とElGamal暗号

に載ってる

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

62 :名無しさん@お腹いっぱい。:2007/01/12(金) 10:35:03 ID:fqx7gNFH0
収束するタイプのアルゴリズムの計算量はどのように評価すればいいでしょうか?
たとえば、解との誤差が反復回数kに対してexp(-k)となるアルゴリズムなら
その計算量はどう考えればいいですか?

63 :名無しさん@お腹いっぱい。:2007/01/12(金) 11:04:55 ID:L9rwtlVsO
>>62
テイラー展開

64 :名無しさん@お腹いっぱい。:2007/01/12(金) 11:06:10 ID:L9rwtlVsO
間違えた。スマソ

65 :名無しさん@お腹いっぱい。:2007/01/16(火) 14:44:11 ID:ZnubhSPs0
すごく基本的なことだと思うのですが、疑問に思ったので質問させてください。

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

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

66 :名無しさん@お腹いっぱい。:2007/01/16(火) 17:23:13 ID:i+FGKUhV0
>>65
(1) 万能Turing機械はテープに書かれた状態遷移関数を模倣できる。
(2) とりあえず「構文解析」が何を意味するのかわからん。
回答する前に>>65に書いてある「構文解析」の定義を与えてくれ。

67 :65:2007/01/16(火) 18:49:10 ID:ZnubhSPs0
>>66
回答ありがとうございます!

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

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

68 :名無しさん@お腹いっぱい。:2007/01/16(火) 22:11:56 ID:i+FGKUhV0
>>67
頭の中で考えようとしているだけで,ちゃんと手を動かしてないでしょ。

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

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

69 :名無しさん@お腹いっぱい。:2007/02/02(金) 14:37:20 ID:E0JXnBFwO
授業で
キーボードから3つの数値を入力して、平均値を計算して画面に表示する。
っていうプログラムを作れと言われたんですけど、誰か教えていただけませんか?お願いしますm(_._)m

70 :名無しさん@お腹いっぱい。:2007/02/02(金) 15:08:50 ID:hs0Vxbu00
>69
for i in range(0,3):
  69.叩く(テンキー)
  69.メモする(押した数字)
69.筆算する(メモ)
平均値 = 69.持つ(油性マジック)
69.書く(平均値, 画面)
end

71 :名無しさん@お腹いっぱい。:2007/02/02(金) 15:23:05 ID:cDK7vgl80
>>69
そんなことも自力でできないのなら、おとなしく単位をあきらめろ。

72 :名無しさん@お腹いっぱい。:2007/02/03(土) 03:04:32 ID:XlMlc9cb0
リードソロモン符号において
符号に含まれた誤りの数が訂正可能な数よりも多いということは
どの段階(シンドローム,オメガ,根・・・)で分かるのでしょうか?

73 :名無しさん@お腹いっぱい。:2007/02/03(土) 11:56:02 ID:DfDYFFQg0
>72
別の符号語に訂正してしまうので分からない。

74 :名無しさん@お腹いっぱい。:2007/02/04(日) 22:51:46 ID:VMBa4rF10
IPアドレス初歩質問
10進数177が2進数1011110になるわけ?
大学教授の解答なんです・・・・・

75 :名無しさん@お腹いっぱい。:2007/02/04(日) 22:57:42 ID:VMBa4rF10
IPアドレス初歩質問
10進数177が2進数1011110になるわけ?
大学教授の解答なんです・・・・・

76 :名無しさん@お腹いっぱい。:2007/02/04(日) 23:31:39 ID:/NGSGO3Z0
10進数177は2進数10110001
2進数1011110は10進数94

77 :名無しさん@お腹いっぱい。:2007/02/04(日) 23:33:15 ID:qXDZuuUt0
マルチかつスレ違いかつ社会性のない74は師ね

78 :ちばしてぃのはんたぃ:2007/02/06(火) 18:09:45 ID:tOgd3cus0
>>69

<html>
<head>
<script language="JavaScript">
<!---
function calc(C) {

window.alert((eval(C.x.value) + eval(C.y.value) + eval(C.z.value) ) / 3.0);

}
//--->
</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>

テキトーに書いたので,試してみれ >( ̄。 ̄

79 :ちばしてぃのはんたぃ:2007/02/06(火) 18:11:13 ID:tOgd3cus0
ま,この程度のコードはぴろたんにくれてやるから >( ̄。 ̄

80 :名無しさん@お腹いっぱい。:2007/02/07(水) 14:29:42 ID:jRlFVoGF0
>>79
>答え一発
ぜひ元ネタ通り6桁であってほしかったと思う。どうでもいいけど。

81 :名無しさん@お腹いっぱい。:2007/02/08(木) 01:06:50 ID:8bEH7E6p0
突然すみません。
RSA暗号法の2つの鍵を
(e,n)=(61,437)
(d,n)=(13,437)
の時、292を復号する方法を教えてください。

82 :名無しさん@お腹いっぱい。:2007/02/08(木) 03:32:59 ID:w3b3DAAA0
ここは過疎板なんだな。

過疎板・・・。



83 :名無しさん@お腹いっぱい。:2007/02/08(木) 15:26:19 ID:QZmvjyTH0
まだ出来て間もないからな。
出来たばかりで客の少ない駅舎みたいなもんだ

84 :名無しさん@お腹いっぱい。:2007/02/08(木) 17:07:23 ID:LOySh+8z0
>>81
mod(292^13, 437) = 26
かな?

85 :名無しさん@お腹いっぱい。:2007/02/08(木) 22:00:43 ID:48DlP48K0
>>81
(e,n)=(61,437)から(d,n)=(13,437)を求める方はええの?
ふつうそっちのほうが問題になるんちがうん

86 :ちばしてぃのはんたぃ:2007/02/16(金) 12:03:36 ID:fgww2w2m0
>>80
それは宿題にw みんなお家で解いてね(^ー^

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

mod(26^61, 437) = 292



87 :名無しさん@お腹いっぱい。:2007/03/21(水) 12:20:06 ID:+yFYW0470
「計算理論の基礎」をやっているのですが、分からない問題があります。

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

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

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

88 :名無しさん@お腹いっぱい。:2007/03/22(木) 00:33:58 ID:GHWio0QR0
>>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では動作しているようだけど、こんなんでいいのかな。

89 :名無しさん@お腹いっぱい。:2007/03/22(木) 17:58:32 ID:Tbpq2FlP0
>>88
ありがとうございました。

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

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

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

90 :名無しさん@お腹いっぱい。:2007/03/23(金) 00:12:55 ID:/+leQtl20
>>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を作成。
>A受理状態を非受理状態に、非受理状態を受理状態にする。
>BNFAを正規表現にする方法を使い、Aで作成したDFAを正規表現にする。
体系的な方法ですね。全く思いつかなかった。

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

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

91 :名無しさん@お腹いっぱい。:2007/06/14(木) 00:34:52 ID:T+2sleHv0
通信路符号化において0,1,2の各グループを3ビットずつ送信して多数決法で
平均誤り率を求める方法を教えて下さい。生起確率は3つとも同じとします。

92 :名無しさん@お腹いっぱい。:2007/06/21(木) 12:30:31 ID:wVtn7M9z0
クラスNPが微妙に分からないのでWIKIPEDIAで調べたんですが・・・


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

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

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


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

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

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

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

93 :age:2007/06/21(木) 12:31:21 ID:wVtn7M9z0
クラスNPが微妙に分からないのでWIKIPEDIAで調べたんですが・・・


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

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

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


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

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

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

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

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

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

95 :名無しさん@お腹いっぱい。:2007/06/21(木) 22:18:34 ID:Nv10iH4T0
>93
>クラスNPは決定問題のクラスのはずですが、
>非決定性チューリングマシンは決定問題以外も扱える為、
>「非決定性チューリングマシンによって多項式時間で解くことができる問題。」のように定義してしまうと、
>決定問題以外も扱えるクラスになってしまいます。

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

>94
意味が分からない。

96 :名無しさん@お腹いっぱい。:2007/06/21(木) 22:51:20 ID:fOHy65FI0
>>94
つ ゲーデルの不完全性定理

97 :93:2007/06/22(金) 09:36:38 ID:PJIVKFMu0
>>94-96
どうもです。


wikiの定義の意味が

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

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

98 :93:2007/06/22(金) 10:39:43 ID:PJIVKFMu0
決定問題の事でさらに疑問が出てきたので質問です。

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

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


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

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

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

のようなものを考えると

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

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

おねがいします。

99 :名無しさん@お腹いっぱい。:2007/06/23(土) 00:37:05 ID:q89b37o/0
無限とは概念であって、論理的な手法で構築される概念では
無限とは物理や科学の無限の概念と同じで、底無しの無限ではなく
極限に大きな数値で評価すれば無限と同等と見なせる無限をいいます。
つまり測定可能、数値として扱えるものが有効な無限なのです。
極限に大きなメモリや命令語で実現可能なものであれば事実上の無限と
表してもいいかもしれませんが、底が無い訳ではない点を考慮してください。

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

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

100 :93:2007/06/23(土) 09:21:41 ID:XvF40ZUO0
>>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で答えているものではないかもしれないが、
問題を解決する過程を全て決定問題にすることができる問題は、
非決定性チューリングマシンで解くことのできる決定問題と見なす事ができるかどうかということです。

おねがいします。

101 :名無しさん@お腹いっぱい。:2007/06/23(土) 09:49:51 ID:nHQsmQhb0
>>100
>非決定性チューリングマシンで解くことのできる決定問題と見なす事ができるかどうかということです。

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

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

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

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


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

103 :名無しさん@お腹いっぱい。:2007/06/23(土) 14:08:50 ID:HAeDS3BI0
>102
>私は、これは距離が0または1であるとは限らないため決定問題と言えず、NP完全と言えないということと解釈していたが、
>例えば2進数で距離を表して距離の10桁目は0であるか?
>見たいな事をyes/noで答えること繰り返す事で比較できるような決定問題と見なせるようにも思えました。

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

104 :93:2007/06/23(土) 14:41:02 ID:XvF40ZUO0
>>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'      i!ゝ.   ワ  ,r'!r‐ '~ 二.~/ i,!ヽ}.i/,!  ,.「
  ,. -‐ ''' ~ ̄ ~' 'ー '~ュ          ゙ ;r r‐,r ,r' ''"~ ̄ ヽ.\_,! ハ}_,}_,.r''~ 
  ー .、         ,.            ・ 人ゝr' ~       ,!  }ノ,,!!_/
    ~'' ー-─ ''',"/,儿.    ・     . 'ヽ .〈,   i ;;.. ,/ _,!  ,!ソ’、.  ̄~ ー;z
          /,.'〃- ' ゝ. __ ,,,.. ',; -‐ ''’  ,,! :' ,ノ  !─''’ ー -}     ,! !
            { f/,'、,.  `' ゝ/   k           ,._-‐'"_/~_ ー - .、{     〉`;
           !〉,{  \_ ,. r‘_ー- .、,Z__ ,,.. -‐ _'ソ_`\~ヽ.  ヽ. ヽ.    〈 ,´
           ヽ.!   {   〉,,       ,, __ノ  、.,!.  ヽ. \ `,.「    ,/'

105 :名無しさん@お腹いっぱい。:2007/07/03(火) 17:23:09 ID:f5WXE8B60
計算機の高速化の方法について高専の授業の課題
でまとめなければならないのですが、いったいどのような
方法があるのでしょうか?
自分で調べてみたのですが、やふってみても、ぐぐってもわかりませんでした
おねがいします



106 :名無しさん@お腹いっぱい。:2007/07/03(火) 18:10:23 ID:X6HtMMwF0
計算機が遅くなりそうな理由をとことんまでつきつめて考えろ

107 :名無しさん@お腹いっぱい。:2007/07/04(水) 03:33:30 ID:M2loPD1A0
>>106
一見不親切そうだが,高速化の技術ってボトルネックをどう解消するか,が
一番大事ではあるね。

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

108 :名無しさん@お腹いっぱい。:2007/07/06(金) 22:41:09 ID:keE9A6DV0
一組のトランプカード(ジョーカーを除く)52枚から一枚とって、
それがスペードのエースであることを知り得た情報量は何ビットか?

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

109 :名無しさん@お腹いっぱい。:2007/07/07(土) 00:01:23 ID:4c1gOrny0
>>108
宿題は自分でやれ

110 :名無しさん@お腹いっぱい。:2007/07/07(土) 12:21:56 ID:YnLGd0tFO
>>108
残念だが俺にはわからない

111 :名無しさん@お腹いっぱい。:2007/07/11(水) 00:22:49 ID:nXA2icOaO
すみません、皆さまの知恵をお貸しいただけないでしょうか。お忙しいのに恐縮です

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

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

112 :名無しさん@お腹いっぱい。:2007/07/11(水) 00:26:40 ID:nXA2icOaO
すみません、x=10のときでした。

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

お助けください

113 :名無しさん@お腹いっぱい。:2007/07/11(水) 03:37:48 ID:uEqRgl1kO
プロ野球の結果を計算で予測することは可能ですか?

114 :名無しさん@お腹いっぱい。:2007/07/11(水) 10:55:29 ID:y6bl5xLD0
>>112
x=10と訂正しておきながら何故log100と記した?

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

115 :112:2007/07/11(水) 11:03:58 ID:nXA2icOaO
すみません、log10でした。
これであっているでしょうか?

116 :名無しさん@お腹いっぱい。:2007/07/11(水) 16:14:49 ID:nXA2icOaO
誰かお願いできませんでしょうか。

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

117 :111:2007/07/12(木) 00:00:27 ID:evYeBsJM0
誰も答えてくれないので数学板でしつもんするので却下します

118 :名無しさん@お腹いっぱい。:2007/07/12(木) 00:10:42 ID:26ZoS6qg0
辞書ひけ

119 :名無しさん@お腹いっぱい。:2007/07/12(木) 02:14:11 ID:c7RIlnVd0
【参院選】民主党から、在日コリアンの期待背負った金氏(民団幹部)が立候補…在日参政権訴え
http://news22.2ch.net/test/read.cgi/newsplus/1184165873/l50

120 :名無しさん@お腹いっぱい。:2007/07/12(木) 14:02:41 ID:jk17mFN40
大学の定期試験ででこういう問題が出ました。
計算機が情報を表現する原理を400字でまとめろと出たんですが。

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

121 :名無しさん@お腹いっぱい。:2007/07/12(木) 17:27:26 ID:ApasCboM0
>>120

俺だったら、

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

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


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

122 :名無しさん@お腹いっぱい。:2007/07/12(木) 22:58:36 ID:28pPSO5S0
別スレで書いたのですがスレ違いっぽかったのでこちらで聞かせてもらいます。
¬x∨yをNand(記号|)で表すとしたら
x|(y|y)で合ってますか?

123 :名無しさん@お腹いっぱい。:2007/07/12(木) 23:19:53 ID:26ZoS6qg0
合ってるよ

124 :名無しさん@お腹いっぱい。:2007/07/13(金) 14:02:10 ID:qyJ3YcA+P
>>120-121
小論やレポートや試験で「〜だろうか」とか「〜し、」とかふつう使わない

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



125 :名無しさん@お腹いっぱい。:2007/07/13(金) 15:00:57 ID:QfZVwhLF0
情報の表現って何だろ?
オブジェクト指向で言うオブジェクトも、いちおう情報の表現か?
究極的には記号列(もしくは2進数)に符号化できる情報は全て表現できるわけだけど
ハードウェアの動作原理にも言及すべき?
何か大学ってのは訳のわからんものを問う場所なんだな

126 :名無しさん@お腹いっぱい。:2007/07/13(金) 17:49:14 ID:J2sSaute0
>>125
オブジェクト等も全て含めてコンピュータ内で扱われる情報は全て0と1で表現されている―

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

127 :名無しさん@お腹いっぱい。:2007/07/13(金) 21:59:15 ID:bQ2GydXh0
任意の大きさの自然数をビット列で表現できることを示し、
したがって可算な集合の要素をビット列で表現できることを確認した後、
現実にはビット列の長さに上限があることからどういう影響が出るか考察したうえで、
具体例としてテキストと音声と画像と二分木がどのように表現されるかを解説して終わる。

ってのを思いついた。

128 :名無しさん@お腹いっぱい。:2007/07/13(金) 22:47:49 ID:1V3WlCBu0
計算機が扱えるのは数値だけ。人間が数値に意味を付けているにすぎない、と俺は思っている。

129 :名無しさん@お腹いっぱい。:2007/07/14(土) 14:27:25 ID:ysC1J6D20
>>127
「ビット列」は自然数を2進法で書いただけのこと。
計算機方向から見たとき,どっちかというとゲーデル数の発明で,
自然数といろんなものに1対1対応がつく,って方が本質かと。

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

130 :111:2007/07/15(日) 03:58:17 ID:bZmTqcw4O
すみません。
誰か>>111をお願いします。
数学板で聞いたらシカトされました
x=10のときです

助けてください

131 :名無しさん@お腹いっぱい。:2007/07/15(日) 05:12:10 ID:bosW2Z6K0
>>129
ゲーデル数ならいいけど、自然数と言ってしまうと「順序」という性質があるから微妙な希ガス
ビット列同士の順序は計算機にとって何の意味も持たないからね

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

132 :111:2007/07/15(日) 08:36:07 ID:WTYRdQCb0
>>131
ありがとうございます。
お礼させてください。3千円くらいでいいですか?

133 :名無しさん@お腹いっぱい。:2007/07/16(月) 21:08:54 ID:sgRAz2mo0
計算機の限界って処理速度でOKですか?

134 :名無しさん@お腹いっぱい。:2007/07/16(月) 22:07:30 ID:B8F6Ap350
|A|=m, |B|=n, m>=nのときA→Bへの全射は何通りですか?

135 :名無しさん@お腹いっぱい。:2007/07/16(月) 23:49:46 ID:2/K0A4WL0
>>134
n^m - ΣnCj (n - j)^m かな?(j = 1 から n - 1 まで)
写像としてあり得る全組み合わせから、全射にならないものを引いてみたけど
もっと単純な考え方もあるかもしれん

136 :名無しさん@お腹いっぱい。:2007/07/17(火) 20:28:13 ID:kCOst1PL0
>>135
ありがとうございます。
エレガントな方法はあるのでしょうかねぇ。

137 :名無しさん@お腹いっぱい。:2007/08/08(水) 12:08:21 ID:TpBoj6st0
ttp://seo.fc2.com/keywordrate/

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

138 :名無しさん@お腹いっぱい。:2007/08/08(水) 14:24:15 ID:8BcfQbnV0
形態素解析でググれば一発で終わりそうな質問になりそうな気もするが

139 :名無しさん@お腹いっぱい。:2007/08/09(木) 20:37:04 ID:trvRFNsU0
>>138
ググったらいろいろ出てきました!
ありがとうございます!

140 :名無しさん@お腹いっぱい。:2007/08/11(土) 00:43:25 ID:O+bN/tRK0
猛者の方教えて下さい。

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

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

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

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





141 :名無しさん@お腹いっぱい。:2007/08/11(土) 11:35:19 ID:l+BnlFSEO
2進数(0.00001)×2の‐1乗を正規化表現すると何ですか!?

142 :名無しさん@お腹いっぱい。:2007/08/11(土) 12:05:50 ID:1XrYJCEa0
10進数の 0.00234×10^-5 を正規化したら 2.34×10^-8

143 :名無しさん@8周年:2007/08/15(水) 09:18:50 ID:MyoflD720
>>133
計算機の限界は細かく言うとメモリーバンド幅とかチップセットの性能とか
にも影響を受ける部分が有りますよ。

144 :名無しさん@お腹いっぱい。:2007/08/19(日) 16:10:49 ID:7bCM8ZzH0
>>136
エレガントってほどじゃないけど、
Aから、|B| 個の要素を選び出す ( mCn通り )
選び出したものから、Bへの置換を作る ( n!通り )
選ばなかったものから、Bへの写像を作る ( n^(m-n)通り )
で、mCn*n!*n^(m-n)っていう答えもありだと思う

145 :名無しさん@お腹いっぱい。:2007/08/19(日) 16:12:32 ID:7bCM8ZzH0
あっ、ごめん144だと重複があるからやっぱだめだ

146 :名無しさん@お腹いっぱい。:2007/08/21(火) 17:44:13 ID:Og+bG7fz0
ファインマン「計算機科学」の第1章の問題の模範解答をだれか・・・

147 :天才様へ:2007/08/26(日) 11:00:19 ID:gJSffyU7O
253398→7a4c395e79 になるんですが、→は何をしたかわかる人いますか??

148 :名無しさん@お腹いっぱい。:2007/08/26(日) 21:54:30 ID:Kt+66V5I0
16進への変換

149 :天才様へ:2007/08/27(月) 00:35:12 ID:AjR5MCBEO
それはもうやったんですけど無理でした(汗)
16進数に変換して、数が増えるなんておかしくないですか??

150 :名無しさん@お腹いっぱい。:2007/08/27(月) 04:03:10 ID:JZyxoveLP
>>149
別に

151 :名無しさん@お腹いっぱい。:2007/08/27(月) 07:30:32 ID:J8AEwWMp0
右と左はイコールで結ばれてないからたぶん足し算してから変換したんだな

152 ::2007/08/27(月) 09:26:47 ID:AjR5MCBEO


153 :どういうことですか??:2007/08/27(月) 09:28:16 ID:AjR5MCBEO
お願いします詳しく教えて下さい_(._.)_

154 :名無しさん@お腹いっぱい。:2007/08/28(火) 11:37:36 ID:UrzYTx0+0
3DDD6(16進)=253398(10進)
>>153
16進変換ができる電卓ならOSにも付属しているし
検索すれば、その辺のWEBサイトでできるところもあるだろ。
故に「→」は「=」以外の計算をした結果だろ。
ぱっとみて、何かのアルゴリズムを通して変換したんでしょう。
それを何かと聞かれても片っ端からアルゴリズムを試して
やってみるしかない、出題者が過去に提示したアルゴリズムや
変換の何かの1つである可能性が高いのでそれを探るべきだろう。


155 :名無しさん@お腹いっぱい。:2007/08/30(木) 18:44:36 ID:aYhxAh6Z0
もうこういうのは無視して良いのではないかな

156 :名無しさん@お腹いっぱい。:2007/10/11(木) 20:13:34 ID:Y6N0aeG90
P=NP問題解いたらフィールズ賞取れる?

157 :名無しさん@お腹いっぱい。:2007/10/11(木) 21:18:21 ID:rANzscZ40
たぶんチューリング賞だけ

158 :名無しさん@お腹いっぱい。:2007/10/17(水) 23:18:53 ID:BbqVifFS0
チューリング章、フィールズ章、ノーベル賞(肯定的にといた場合)を取れるよ

159 :名無しさん@お腹いっぱい。:2007/10/17(水) 23:44:04 ID:0ktQbLZN0
ノーベル何賞よ

160 :名無しさん@お腹いっぱい。:2007/10/18(木) 07:29:34 ID:GLZo3olj0
平和賞

161 :名無しさん@お腹いっぱい。:2007/10/26(金) 12:21:08 ID:eomKT03+O
欽ドン賞

162 :名無しさん@お腹いっぱい。:2007/12/10(月) 01:33:26 ID:Z6tIgvwZ0
>>158
一番確実なのは、まずネヴァリンナ賞だろ?
計算論関連の人が多いし。

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

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

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

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

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


163 :名無しさん@お腹いっぱい。:2008/01/23(水) 00:31:56 ID:1iHdUPzsO
情報記号系列1,0,1,1に対し、パリティ検査記号C1,C2,C3を生成せよ
って問題なんですが、わかる方教えてください。よろしくお願いします。

164 :名無しさん@お腹いっぱい。:2008/01/23(水) 17:38:17 ID:udDTkWFYO
>>163
"情報記号系列 パリティ検査記号"でぐぐったら
日本語の講義資料が山ほど出てきたぞ
おかげさんで忘れかけていた知識の復習ができた
ありがとうw

165 :名無しさん@お腹いっぱい。:2008/01/24(木) 05:13:01 ID:M1/h8yR10
>>120
「情報」と「表現」の言葉の範囲が広すぎるなあ

166 :名無しさん@お腹いっぱい。:2008/01/24(木) 19:50:20 ID:Uv3V3DnoO
>>134-136
ものすごい遅レスなんだけど
恵羅博, 土屋守正「組み合わせ論」産業図書, 1996.
ISBN4-7828-5354-8
のpp.88-94にメービウスの反転公式とそれを用いた全射の個数の数えあげ公式の説明がある

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

167 :名無しさん@お腹いっぱい。:2008/01/27(日) 00:30:06 ID:A5C+vawa0
f(x)=2cos(x)+0.5x+0.8について
newton法を用いて近似解が反復によって
1つの解に近づくことを示せ

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)
コレをどういじっていいのかわからなくて
どなたかご指南よろしくお願いします(><;)


168 :名無しさん@お腹いっぱい。:2008/01/27(日) 01:29:40 ID:8lIUPoUIO
書名間違えた>>166
「組み合わせ論」じゃなくて「組合わせ論」だ
こういうのってどっち使うか決まってるのかな?

169 :名無しさん@お腹いっぱい。:2008/01/27(日) 01:38:27 ID:kUdLXXu50
「組合せ論」って書く人もいるね

170 :名無しさん@お腹いっぱい。:2008/01/27(日) 01:39:43 ID:3OQt8kTw0
国語審議会かなんかだと、名詞として使う場合は送り仮名等は無し、
動詞として使う場合は送り仮名等有りだった希ガス

171 :名無しさん@お腹いっぱい。:2008/01/27(日) 14:38:43 ID:9u+ouNed0
学術用語として正式なのは>>169だったような

172 :名無しさん@お腹いっぱい。:2008/01/28(月) 04:37:19 ID:XpZbozAwO
>>168さらに訂正
本当に正しい書名は「組合せ論」(シリーズ/情報科学の数学)でした
この本の巻末で参考文献に挙げられてる本もみんなタイトルが「組合せ論」になってる
表記はちゃんと統一されてるんですね

173 :名無しさん@お腹いっぱい。:2008/01/31(木) 11:31:55 ID:dDG8MhXy0
うちの教授が「組み合わせ」や「組合わせ」を使ってたら、
組合せ論やってる人に「組合せ」が正解と指摘されたって言ってた。

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

174 :名無しさん@お腹いっぱい。:2008/02/02(土) 22:52:22 ID:PulwzqR80
チューリングマシンの計算能力を超えることはできますか?

175 :名無しさん@お腹いっぱい。:2008/02/03(日) 12:04:49 ID:5U+XG3+f0
>>174
オラクル付きチューリングマシン?

176 :名無しさん@お腹いっぱい。:2008/02/04(月) 11:48:42 ID:qgzTjn2R0
>>174
数式の計算以上のことができれば越えているだろう。
それは計算とは呼ばないけどな。


177 :名無しさん@お腹いっぱい。:2008/02/04(月) 16:29:00 ID:qgfiYOAe0
チューリング機械のように、数学的な表現をしたいのですが。

178 :名無しさん@お腹いっぱい。:2008/02/05(火) 00:19:18 ID:haUcQmB50
>>177
実数を使っていいなら簡単。

179 :名無しさん@お腹いっぱい。:2008/02/05(火) 11:19:16 ID:xALL6pLG0
まともな計算の定式化でチューリングマシンより強い能力を持ったモデルは提案されてない。
だけど、別に不可能って証明されてるわけじゃないから、やってみるのも面白いんじゃない。
無理だと思うけど

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

180 :名無しさん@お腹いっぱい。:2008/02/05(火) 17:54:10 ID:TpiQiHvA0
素人の自分からすると、実数を使ったモデルがチューリング機械
より強力なことは簡単に証明できるのではなかろうかと思えます。
専門の人は、これまでだれもそんなことは考えなかったのですか。

181 :名無しさん@お腹いっぱい。:2008/02/05(火) 21:10:58 ID:KTmzfjzl0
実数上の計算やもっと抽象的な構造における計算も色々考えられているけど、
今んとこ結局全部ほとんど変わらん

182 :名無しさん@お腹いっぱい。:2008/02/05(火) 22:14:37 ID:TpiQiHvA0
自分の知る範囲では、ラムダ式はいつも自然数とか自然数を扱う
関数が変数になっていると思いますが、そこに実数をあてはめる
とどうなるのでしょうか。近似をしない場合の積分の計算などは、
計算機で扱えないので、チューリング機械の計算を超えていると
思うのですが・・・。

183 :名無しさん@お腹いっぱい。:2008/02/05(火) 22:20:33 ID:bWkSitqj0
とりあえず「そこに実数をあてはめ」たラムダ式を定義してみたら?

184 :名無しさん@お腹いっぱい。:2008/02/05(火) 22:41:09 ID:TpiQiHvA0
定義だけなら簡単なんですが、はたしてそれが本当に
チューリング機械の能力を超えたものなのかどうか、
実際にそれを数学的にどうやって示したらいいのかが
難しいです。もしかすると、自然数で実数は正確には
扱えない、ということに関係あるのかもしれません。
不完全性定理そのものを証明に使えるといいのですが。



185 :名無しさん@お腹いっぱい。:2008/02/05(火) 23:00:35 ID:bWkSitqj0
どういうものを考えているのかよくわからないけど、
チューリングマシンの能力を超えてるように見えるの?

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

187 :名無しさん@お腹いっぱい。:2008/02/05(火) 23:33:59 ID:bWkSitqj0
何となく気持ちはわかるような気もするけど。
それがラムダ式とどう繋がるのかはよくわからないなあ。

188 :名無しさん@お腹いっぱい。:2008/02/06(水) 00:03:23 ID:qVScmIFz0
普通のラムダ式ではないので少し分かりにくいですね。
f(r)を実数上の関数とすると、積分を求める計算は
λf(r).Sf(r)dr(ここで、Sは積分記号)のように書けます。
運動方程式は通常微分方程式なんですが、積分の形に
書き直すこともできます。つまり場は、上のラムダ式で表さ
れるような積分を連続的に実行しているわけなんです。
毎時、連続無限個の積分計算をするということは、普通の
計算機の能力をはるかに超えていると考えられます。

189 :名無しさん@お腹いっぱい。:2008/02/06(水) 00:06:50 ID:ij7jxdP+0
それは関数のラムダ記法であってラムダ計算とはあまり関係ないように思う

190 :名無しさん@お腹いっぱい。:2008/02/06(水) 00:11:47 ID:ij7jxdP+0
つまり、「積分」は適当な空間から空間への作用素と考えられるけど、
その作用素を単にλを使って書いただけのように見えるんだよね。

191 :名無しさん@お腹いっぱい。:2008/02/06(水) 00:12:17 ID:qVScmIFz0
ラムダ計算とは関係ないですが、ラムダ計算以上の
計算が何か関係するのではないかという妄想です。

192 :名無しさん@お腹いっぱい。:2008/02/06(水) 01:31:35 ID:4Adhg7hT0
Turing機械は高々可算個しかないんだからTuring機械が受理できる数も高々可算個。
だから実数はほとんどすべてTuring機械では計算不能。

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

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


193 :名無しさん@お腹いっぱい。:2008/02/06(水) 19:18:16 ID:qVScmIFz0
ありがとうございます。
そんなふうに単純に考えればいいんですね。
場がチューリング機械を超えていいるのはいいとして、
ラムダ計算に対応するものは何かを考察してみます。

194 :名無しさん@お腹いっぱい。:2008/02/06(水) 22:07:09 ID:vC9JuQk10
>>192
超えてるってことはそんなに自明かな?
比較不能かもしれない。

195 :名無しさん@お腹いっぱい。:2008/02/06(水) 23:17:52 ID:m3Y1WBZg0
いや、任意の実数を使っていいなら、
少なくとも、その実数をオラクルに用いたオラクル付きチューリングマシンか
それ以上の性能はあるんじゃないか?

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

196 :名無しさん@お腹いっぱい。:2008/02/06(水) 23:23:40 ID:vC9JuQk10
実数を使って何をするのかがはっきりしなかったから。
オラクルつきチューリングマシンなら強くなるけど。

197 :名無しさん@お腹いっぱい。:2008/02/06(水) 23:39:20 ID:m3Y1WBZg0
まあ、確かに>>180からの書き込みの人が何をしたかったのかが正確に分からんから
オラクル付きチューリングマシンより強くなるとは言い切れないのか

198 :名無しさん@お腹いっぱい。:2008/02/07(木) 08:56:30 ID:AWXpF/oI0
ちょっと前の数学セミナーで数学者スメールの解説記事が載ったときに
近年はトポロジー以外に実数上の計算理論を研究してると読んだ記憶がある
ぐぐったらBlum Shub Smale machineとかいろいろ出てきたけど
>>181で言われてるのはそういう研究ですね

199 :名無しさん@お腹いっぱい。:2008/02/08(金) 21:49:15 ID:WhaKiMg/0
書き込むまでもないかもしれないが、実数上の計算理論なんか論文検索でいくらでも出てくるよな。

200 :名無しさん@お腹いっぱい。:2008/02/09(土) 00:02:35 ID:yeUWyLfn0
実数上で計算体系作るのは勝手だけど,それでそう簡単に面白い結果が出るわけじゃないからね。

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


201 :名無しさん@お腹いっぱい。:2008/02/09(土) 00:45:17 ID:1msGBbSE0
面白い結果が出てこないのは、計算機科学者の能力が試されてるんじゃないの?

202 :名無しさん@お腹いっぱい。:2008/02/15(金) 18:41:42 ID:XYZQPbsf0
教えてください。次の言語はチューリング完全ですか?

1)C言語の文法が使える。
2)ただしmalloc等、動的にメモリを確保する命令は使えない。
3)スタックは無限にあり、いくら再起呼び出ししてもオーバーフローしない。
4)一回の関数呼び出しでスタックに乗せられるメモリはO(1)。
5)入力はROMで与えられる。

よろしくお願いします。


203 :名無しさん@お腹いっぱい。:2008/02/15(金) 18:46:06 ID:XYZQPbsf0
すいません。考えてみたら出力サイズが大きかったらだめですね。
計算可能な決定問題は全て解けるか?にしてください。


204 :名無しさん@お腹いっぱい。:2008/02/15(金) 19:13:49 ID:XYZQPbsf0
たびたびすいません。
printf等で標準出力にいくらでもデータを出せるとすれば、チューリング完全か?という問題にできますね。
やっぱりチューリング完全かどうかにしてください。


205 :名無しさん@お腹いっぱい。:2008/02/15(金) 19:34:12 ID:13WTFOAa0
直接関係ないかもしれないけど、無限にメモリが使えるっていうのは、
ポインタが固定長であるCの仕様と相容れない気がする

206 :名無しさん@お腹いっぱい。:2008/02/15(金) 21:25:51 ID:XYZQPbsf0
すいませんが、そこらへんは題意を汲み取ってうまいこと定義してください。
よろしくお願いします。


207 :名無しさん@お腹いっぱい。:2008/02/15(金) 21:44:32 ID:XYZQPbsf0
スタックポインタだけ任意の整数を格納できる、とすれば大丈夫でしょうか?


208 :名無しさん@お腹いっぱい。:2008/02/15(金) 21:47:53 ID:XYZQPbsf0
入力のROMについても任意のアドレスにアクセスできる必要がありますね。
うーん。困った。なかなか厳密な定義ができない。


209 :名無しさん@お腹いっぱい。:2008/02/15(金) 21:49:14 ID:XYZQPbsf0
入力のROMについても任意のアドレスにアクセスできる必要がありますね。
うーん。困った。なかなか厳密な定義ができない。



210 :名無しさん@お腹いっぱい。:2008/02/15(金) 21:51:54 ID:XYZQPbsf0
2重に書き込んでしまいました。
すいません。


211 :名無しさん@お腹いっぱい。:2008/02/15(金) 21:57:52 ID:XYZQPbsf0
ポインタやintのサイズは入力のROMのサイズに依存し、ROMの任意のアドレスをアクセスするのに必要十分な大きさがある。
一度の関数呼び出しでスタックに乗せられるメモリのサイズはO(1)個のポインタやintの変数である。
でどうでしょう。

212 :名無しさん@お腹いっぱい。:2008/02/16(土) 02:34:01 ID:uQvfLbs/P
チラシにまとめてから整理してまたおいで

213 :名無しさん@お腹いっぱい。:2008/02/20(水) 18:50:04 ID:Zs6mahT60
誤り確率を持つデジタル回路で作られた電子計算機は、
チューリングマシンを越えている要素がある。

214 :名無しさん@お腹いっぱい:2008/02/20(水) 20:50:48 ID:LR/YShNz0
プログラミング言語間で記述能力の優劣を判定する明示的な方法とかは
あるのでしょうか?

あと、一応何でも記述できるもの(一般帰納的関数のレベル)と思うと
semantics の部分を綺麗に書けるという意味で、haskell とか
記述能力が高そうに見えますが、例えば、はやってないようなもので
もっとエレガント(と思われるよう)な言語とかはあるんでしょうか?

215 :名無しさん@お腹いっぱい。:2008/02/20(水) 22:26:38 ID:Ng1+A/ZD0
記述能力という言葉で、何を指しているのかが分からない。

216 :名無しさん@お腹いっぱい。::2008/02/20(水) 23:18:40 ID:LR/YShNz0
>>215
言語間で表現できる機能自体が違うものは置いておいて、
通常のアプリケーションが実装できる(一般帰納関数を取り扱い可能な)
異なる言語の間で、仕様の決まっているソフトウェアを実装するのに
必要な実装作業量 みたいな物に対して

コード量が少なくて済む <−> 言語としての記述能力が高い

という言い方をするのかと思っていましたが、そういう使い方は
しないのでしょうか?

仕様の決まっているソフトウェアを実装するのに必要な実装作業量
みたいな物に対して

コード量が少なくて済む <−> 言語としての記述能力が高い

という言い方をするのかと思っていましたが、そういう使い方は
しないのでしょうか?

217 :名無しさん@お腹いっぱい。:2008/02/20(水) 23:23:53 ID:Ng1+A/ZD0
そんなんだったら、組み込み関数等の数とか、ライブラリの量とか次第じゃないの?

218 :名無しさん@お腹いっぱい:2008/02/20(水) 23:34:37 ID:LR/YShNz0
確かに、そう言われてしまうと少し困る気もしますが・・

イメージとしては、例えば Scheme みたいな形式言語のコンパイラ
を作るような場合で、特定の言語を使って仕様を正確に記述しようと
する場合に、果たしてライブラリの量が効いてくるものでしょうか??

219 :名無しさん@お腹いっぱい。:2008/02/20(水) 23:42:24 ID:Ng1+A/ZD0
見た目のコードの量には、ライブラリは効いてくるんじゃないの?

そういう話でないとすると、多分、言語を型で分類するのと、
仕様をなんかの基準で分類して考えてみることになるのかな?

言語の型としては、手続き(オブジェクト指向を含めるか分けるかは分からない)、
関数、論理あたりが、今のところ存在してるのかな?
あぁ、意外に、正規表現を使えるかどうかも効きそうだなぁ。
仕様を分類する基準ってどんなものがあるのか分からないけど。

220 :名無しさん@お腹いっぱい。:2008/02/21(木) 02:02:58 ID:iD1Cm1dk0
たいがいの言語は記述「能力」的に同等かと。
記述「効率」の話をしたいんだろうけど、
もうちょっとつっこんで定義しないと議論にならないんじゃない?
コンパイラを作るにしてもyaccとかjavaccを使って
構文解析を楽するなんていうのはライブラリの話でしょ。

221 :名無しさん@お腹いっぱい。:2008/02/21(木) 08:57:58 ID:TkbK8Qy00
>>216
つ Kolmogorov Complexity

222 :名無しさん@お腹いっぱい:2008/02/21(木) 14:13:07 ID:QAgOE94c0
結局のところ、チョムスキー階層で言語の仕様記述を行うのに

正規言語 -> 正規表現
文脈自由文法 -> BNF記法
文脈依存文法 -> ?
帰納的可算言語 -> ?

みたいな状態になっていて、統一的な仕様記述言語が決まらないために
各言語で勝手に実装している雰囲気か

223 :名無しさん@お腹いっぱい。:2008/02/22(金) 01:24:48 ID:kDuapUhl0
>>218
Henry F. Ledgard, "The Little Book of Object-Oriented Programming", Prentice-Hall, 1996
〔Henry F. Ledgard, 神林 靖訳, 「オブジェクト指向プログラミングの考え方」, 翔泳社, 1997〕.
でやってるみたいに、いくつかのクラスの言語を定義して、その記述能力を比較するってのが
順当なのかなぁ?

記述量については、>>221が書いてるようにコルモゴロフ情報量(だっけ?)を使うのも有りだと思う。

224 :名無しさん@お腹いっぱい。:2008/02/22(金) 06:10:29 ID:Yv+kb59aO
「自己記述能力」の高さを比較するとか?
これだと簡素な言語であるほど有利になってしまいますが。

225 :名無しさん@お腹いっぱい。:2008/02/29(金) 00:57:12 ID:TFKJ+yUS0
>>213
どういう意味で超えているんですか?

226 :名無しさん@お腹いっぱい。:2008/02/29(金) 17:43:46 ID:UvuEkjVZ0
計算速度

227 :名無しさん@お腹いっぱい。:2008/02/29(金) 21:27:45 ID:TFKJ+yUS0
そういうのは超えているとは言わないんじゃ・・・

228 :名無しさん@お腹いっぱい。:2008/02/29(金) 22:23:36 ID:gL9jIT7a0
一方で指数時間かかる計算を他方で多項式時間で計算できるなら超えてるといえるだろう。

229 :名無しさん@お腹いっぱい。:2008/03/01(土) 13:39:08 ID:HTyjnAzA0
確率的チューリングマシンの概念さえ知らないの?

230 :名無しさん@お腹いっぱい。:2008/03/01(土) 15:25:33 ID:WVfaPndy0
知ってるよ

231 :名無しさん@お腹いっぱい。:2008/03/01(土) 17:40:22 ID:c6dPEgDe0
なるほどつまりハミルトン閉路求解アルゴリズムで解決できるはずじゃ

232 :名無しさん@お腹いっぱい。:2008/03/01(土) 19:09:04 ID:oOQ8brnj0
>>231
んなわけねーだろ

233 :名無しさん@お腹いっぱい。:2008/03/02(日) 19:15:17 ID:Wg8L3vhD0
計算可能関数について質問ですけど、
計算可能関数とは、アルゴリズムと同値であるため、
有限時間内に手続きが終了する保証のあるもので無ければならず、

例えば、


Σ(1/(2^k))=1+(1/2)+(1/(2^2))+(1/(2^3))+・・・・+(1/(2^∞))
k=0

という数式を実際に各kの値のケースを加算することにより求める場合の手続きは、
∞回の試行を行なわなければならないため、有限時間内に終了する保証が無く、
このような手続きを行なった場合の関数は計算可能とは言えないことになります。

ここで疑問になる事は、手続きの終了までに無限に時間を要する可能性があるが、
有限時間内に解決できる可能性がある場合は計算可能と言って良いのかという事です。

例えば、コインを投げて表が出るまでに何回投げればよいか?
という問題を解決するにあたり、実際にコインを投げて試行する手続きを考えると、
永遠にコインの裏が出続ける可能性も0とはいえないため、計算可能とは言えないかもしれません。
しかし、実際のところ量子アルゴリズムと呼ばれるものには、この例のように永遠に会が得られない可能性が0ではないものもあります。

果たしてこの場合は計算可能と言ってよいのでしょうか?
御願いします。。。

234 :名無しさん@お腹いっぱい。:2008/03/02(日) 19:38:07 ID:RYoLMf5e0
>>233
計算可能の意味を勘違いしてるっぽい。
そもそも「数式や手続きが計算可能」なんて用語がそもそも間違いで、
Aを計算する(有限の)数式や(有限の)手続きが存在するとき、Aは計算可能であるという。

(有限の)数式や(有限の)手続きが存在するってこと自体が、それが計算可能であることの証拠。

そして、例に挙げた数式はそもそも関数になっていなくて、
それを普通に関数の形に書き換えたとき、その数式は明らかに計算可能。
あと、その例題も、そもそも問題になってないよ。

235 :234:2008/03/02(日) 20:00:24 ID:RYoLMf5e0
ごめん、数式があるだけで計算可能ってのはまずい。
それは忘れてください。

236 :名無しさん@お腹いっぱい。:2008/03/02(日) 20:01:00 ID:Wg8L3vhD0
>>234
つまり何処をどう勘違いしているのですか?

なんか話がかみ合ってません。

237 :名無しさん@お腹いっぱい。:2008/03/02(日) 20:17:39 ID:pv8GQ90x0
正しい解を得られる確率がゼロ以上だったら、それは立派な手続きじゃないの?
やっぱり確率的チューリングマシンの概念さえ知らない人ばかりなのか?

238 :名無しさん@お腹いっぱい。:2008/03/02(日) 20:26:04 ID:RYoLMf5e0
>>236
たとえば、挙げている式Σ(1/(2^k))はそもそも関数でないよね?
もし、任意の入力に対しΣ(1/(2^k))を出力する関数という意味なら、それは計算可能。
あるいは入力nに対してΣ_k=0^n(1/(2^k))を計算する関数という意味でも、それは計算可能。

239 :名無しさん@お腹いっぱい。:2008/03/02(日) 20:41:39 ID:cfaaUtHyO
>237
お前、確率的チューリングマシンのこと何も知らないだろ
適当なこと言ってんなよ

240 :名無しさん@お腹いっぱい。:2008/03/02(日) 20:47:50 ID:Wg8L3vhD0
>>237
量子アルゴリズムなんかでは、ある確率で正しい解が得られるという手続き(以後手続きAと呼ぶ)があり、
その手続きAを用いて確実に正しい解を得るためには、その手続きAが正しい解を返すまで、
只管その手続きAを呼び出すという方法が考えられます。

しかし、その手続が正しい解を何度呼び出しても(有限回の場合)返さない可能性も、
確率的には存在すると思われます。
そのような場合、手続きAが正しい解を返すまで、只管手続きAを呼び出すという手続きは、
計算可能関数と言えるのでしょうか?

>>238
その数式は問題として与えたものであり、関数とはここで定義してません。
私が関数と言ったのは、その下に書いた手続きです。

その手続きが計算可能関数と言えるかどうかの話です。

つまり、
1.変数k=0を用意する。
2.変数S=0を用意する。
3.SにS+1/(2^k)を代入する。
4.kにk+1を代入する。
5.kが∞では無いならば3に戻る。
6.Sを出力する。

という手続きが計算可能関数ではないという事を記したのです。

241 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:00:10 ID:RYoLMf5e0
俺の説明が分かりにくくてすまない。
そもそも``手続きが計算可能''ってのが間違いだと言いたいんだ。

関数という場合、値を代入したら値を返すものだよな?(別に入力は無くてもいいが)
>>240の最終的なSを返す関数が計算可能かどうかというなら、
``最終的なSを計算する手続きは存在する''ので、それは計算可能だ。

242 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:00:24 ID:Wg8L3vhD0
>>234
>Aを計算する(有限の)数式や(有限の)手続きが存在するとき、Aは計算可能であるという。
ここは役に立ちました。

つまり、量子アルゴリズムなんかは有限の手続きに出来る保証が無いものもあるため、
そのようなものは計算可能関数とは言えない。

故に量子 ア ル ゴ リ ズ ム とありながらアルゴリズムではない場合もありうるのですな。

243 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:02:39 ID:Wg8L3vhD0
>>241
でも私が示した手続き(関数)は有限個に収まる保証が無いため、
計算可能関数ではなくてOKですよね。

私も言われてみると書き方がへんだったとは思います。

244 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:07:51 ID:Wg8L3vhD0
>>241

取りあえず、

問題


Σ(1/(2^k))=1+(1/2)+(1/(2^2))+(1/(2^3))+・・・・+(1/(2^∞))
k=0

は計算可能で、


私が示した関数(この手続きに沿う)

1.変数k=0を用意する。
2.変数S=0を用意する。
3.SにS+1/(2^k)を代入する。
4.kにk+1を代入する。
5.kが∞では無いならば3に戻る。
6.Sを出力する。

は計算可能関数ではない。

ということですよね?

245 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:13:53 ID:cfaaUtHyO
それって無限ループするプログラムを書いてるだけで関数になってない件

246 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:20:57 ID:mbmQ8Yef0
「計算可能である」の主語が変なんじゃないかな

247 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:22:13 ID:Wg8L3vhD0
>>245
これ関数じゃないの?
数学的には無限に時間を与えられれば解を返すため、関数と言って問題無いと個人的には思いますよ。
有限時間内に終了しなければならないのは計算可能関数のことだと思いますが・・・。

もしかすると全ての関数は、有限時間内に終了するという証明が無ければ駄目なのでしょうか?
取りあえず関数の定義(知っていたらでかまいませんが)教えていただけないでしょうか?

248 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:26:45 ID:RYoLMf5e0
別に関数は有限時間内に計算結果が出る必要はないよ。
もちろん、計算不可能関数ってものもあるから。
ただ、>>244の後半のものを関数の形に直すには、>>238と考えるしかないし、
そうすると、その関数は計算可能になってしまいます。

249 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:33:31 ID:cfaaUtHyO
>247
>244のは関数というより、ただの数

250 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:36:33 ID:Wg8L3vhD0
>>248
ですから、それは、問題に対応する計算可能関数に変換した関数の話ですよね。
>>244に示した関数は計算可能関数ではないじゃないですか?(永遠に関数が終了しない可能性があるため。)


f(x)を(1/(2^k))とおき、
この関数を無限等比級数とみなし、

初項a=1
公比r=1/2

0<r<1のためSは収束し
S=1/(1-1/2)=2となる

のような手続きをとる関数は計算可能関数だけど、

私が示した関数(この手続きに沿う)

1.変数k=0を用意する。
2.変数S=0を用意する。
3.SにS+1/(2^k)を代入する。
4.kにk+1を代入する。
5.kが∞では無いならば3に戻る。
6.Sを出力する。

は計算可能関数ではありませんよね?

251 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:38:22 ID:Wg8L3vhD0
>>249
>>244のは関数というより、ただの数
何故でしょうか?
それを数と言えるなら、
あらゆる数を返す手続きは関数では数ということになるのでは?

252 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:41:41 ID:RYoLMf5e0
>>250
いえ、たとえ一つでもAを計算する有限の手続きが存在すれば、Aは計算可能です。
「この手続きに沿う」というように手続きを固定するのは無意味です。

説明が下手ですまないが、前から言ってるように、
手続きが計算可能だの計算不可能だのというものは無いんだ。

253 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:48:07 ID:Wg8L3vhD0
>>252
>手続きが計算可能だの計算不可能だのというものは無いんだ。

計算可能関数と計算不可能関数が既に挙がっているように、
手続きが計算可能だの計算不可能だのというものは存在しているではないですか。

254 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:50:32 ID:RYoLMf5e0
計算可能関数は、それを計算する(有限の)手続きが存在するもの。
計算不可能関数は、それを計算する(有限の)手続きが存在しないもの。
断じて、手続きが計算不可能だとかそういうものではないよ。

255 :名無しさん@お腹いっぱい。:2008/03/02(日) 21:59:38 ID:Wg8L3vhD0
>>254
つまり計算可能関数及び計算不可能関数は問題の分別のための名前であり、手続きではないのですね。

つまり、私が数学板で聞いた計算可能関数=アルゴリズムというのも嘘ということですね。

こう考えれば貴方の考え方と矛盾が生じなくなりますが、残念ながらこれには賛成いたしかねます。

256 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:07:54 ID:Wg8L3vhD0
初めに自分の読み取った定義を記しておくべきだったかもしれない。

計算可能な問題:大きさが有限の場合、その問題を有限時間内に解決することが出来る保証のある問題。
計算可能関数:有限の大きさの問題を有限時間内に解決する事が可能な手続き。
計算不可能関数:有限の大きさの問題を有限時間内に解決できる保証の無い手続き。

257 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:14:16 ID:RYoLMf5e0
>>255
計算可能関数=アルゴリズム(が存在する)は本当。
fが関数とは、(∀x)(∃!y)(f(x)=y)を満たすもの。
(∀x,y)(f(x)=y⇔g(x)=y)なら外延性公理よりf=g.
たとえば、>>244の2種類は、別の定義を用いているが同値性を証明できる。
よって、計算可能関数=アルゴリズムと考えてもOK。

258 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:17:15 ID:RYoLMf5e0
>>256
f が計算可能関数とは、有限の x に対して有限時間で f(x) を求められるようなものだよ。

259 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:21:14 ID:Wg8L3vhD0
>>258
>求められるようなものだよ。

求められる(もの)というのが明確に分からない。

ここでものが指すものは「問題」のこと?「関数」のこと?

260 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:22:48 ID:RYoLMf5e0
関数のことです。

261 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:27:45 ID:Wg8L3vhD0
>>260
まず>>257に挙がっている定義を見ると、
>計算可能関数=アルゴリズム(が存在する)は本当。
つまり計算可能関数はアルゴリズムが存在する問題ということですよね。

>>258の定義とかみ合わなくて理解に苦しみます。


とりあえず>>256にある定義はあっているのですか?

262 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:36:54 ID:RYoLMf5e0
>>261
失礼しました、>>258は定義域が自然数全体の場合の話です。

正確には、(部分)関数fが計算可能とは、
「あるアルゴリズムMが存在して、任意のxに対して、
``入力xでMを実行したときyを出力する''と``f(x)=y''が同値」

>>256の計算可能関数の定義は「問題」をどういう意味で使ってるのか分からない

263 :名無しさん@お腹いっぱい。:2008/03/02(日) 22:58:26 ID:Wg8L3vhD0
>>262

>正確には、(部分)関数fが計算可能とは、
>「あるアルゴリズムMが存在して、任意のxに対して、
>``入力xでMを実行したときyを出力する''と``f(x)=y''が同値」

その定義は計算可能関数の定義ではなく計算可能な問題の定義ではありませんか。

計算可能関数の定義にて食い違いが起きているようですが、

例えば、

1.変数k=0を用意する。
2.変数S=0を用意する。
3.SにS+1/(2^k)を代入する。
4.kにk+1を代入する。
5.kが∞では無いならば3に戻る。
6.Sを出力する。

この手続きはアルゴリズムでは無いので計算可能関数では無い事は理解できますよね?



>「問題」をどういう意味で使ってるのか分からない

整列問題、ハミルトン閉路問題、巡回セールスマン問題、計算可能な問題、計算不可能な問題...

問題は問題としか言い要がないですね。。。
代名詞に置き換えても何の解決にもならないでしょう。

264 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:05:26 ID:mbmQ8Yef0
>>256 の定義は正しい間違っている以前に定義になってないように思うが

265 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:07:26 ID:Wg8L3vhD0
>>264
何故でしょうか?

266 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:10:54 ID:Wg8L3vhD0
もうそろそろ寝たいから。
もう一つ質問しておき太鼓とを今のうちに書いておきます。


クラスNP困難に属する問題は非決定性チューリングマシンにより、
多項式時間で解決できる保証が無くてはならないのでしょうか?

267 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:10:56 ID:cfaaUtHyO
お前らいつまでやってんだよw
計算可能関数の定義は>262で大体合ってるぞ

268 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:11:17 ID:RYoLMf5e0
>>263
なんか噛みあわないと思ってたら、手続きって言葉の使い方がちょっと違ってたみたい。
すまん、俺は 手続き=アルゴリズム として言葉を使ってた。
あと、計算可能関数の定義は>>262で正しいはずなので確認してください。

269 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:12:35 ID:RYoLMf5e0
>>266
NP困難ならNPである必要はないよ。

270 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:14:12 ID:Wg8L3vhD0
>>269
NPでなくてもいいけど、FNPであるかどうかです。

271 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:27:51 ID:cfaaUtHyO
FNPでなくてもいい

272 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:30:48 ID:mbmQ8Yef0
>>265
数学でいう「定義」と思った場合にだけど、
まず「問題」の定義がされていないのでどうやっても読めない。
とりあえず勝手に標準的な定義を採用するとしても、
問題の「大きさ」とは何かが示されていないのでやっぱり読めない。

あと、それとは別の話だけど計算不可能関数は手続きじゃないと思う。

273 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:31:04 ID:Wg8L3vhD0
>>271
もしもソースがあったら晒して欲しい。

274 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:34:48 ID:pv8GQ90x0
>>242
David Deutsch くらいは知ろうよ

275 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:37:00 ID:Wg8L3vhD0
>>272
それじゃあ問題の定義を、「チューリングマシン上で解法を実行することが可能なもの」とでも書いておきましょう。

>あと、それとは別の話だけど計算不可能関数は手続きじゃないと思う。
一応手続きの定義を聞かせて頂く。

276 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:38:29 ID:Vk4EIZz20
>>274
どうせなら Bernstein & Vazirani もよろしく…。
"Quantum Complexity Theory", SIAM Journal on Computing, Vol.26, No.5, pp.1411-1473, Oct 1997

277 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:38:31 ID:Vk4EIZz20
>>274
どうせなら Bernstein & Vazirani もよろしく…。
"Quantum Complexity Theory", SIAM Journal on Computing, Vol.26, No.5, pp.1411-1473, Oct 1997

278 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:42:00 ID:Wg8L3vhD0
>>274
David Deutsch のブラックボックスの話?

それはいいけど、
素因数分解とかは、無限ループに陥る可能性が0ではないのですか?
詳しいことは知りませんが。

279 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:47:31 ID:Vk4EIZz20
>>278
ShorのアルゴリズムはZQP。

280 :名無しさん@お腹いっぱい。:2008/03/02(日) 23:49:16 ID:Wg8L3vhD0
>>279
ZQPとは何でしょうか?

281 :名無しさん@お腹いっぱい。:2008/03/03(月) 00:58:35 ID:m7HLzyF40
>>275
> それじゃあ問題の定義を、「チューリングマシン上で解法を実行することが可能なもの」とでも書いておきましょう。
じゃあ、「解法」って何?という話になるんじゃないかと。

> >あと、それとは別の話だけど計算不可能関数は手続きじゃないと思う。
> 一応手続きの定義を聞かせて頂く。
そういえば手続きの定義も書いてないね。
チューリングマシンやアルゴリズムと同義と思ってたけど。
>>256 においてはそうではないということかな。

>>280
よく知らないけどここに載ってるみたいだよ
http://qwiki.stanford.edu/wiki/Complexity_Zoo

282 :名無しさん@お腹いっぱい。:2008/03/03(月) 03:10:44 ID:NHF3Ncsz0
ねえみんないったいなに難しい話してんの?
アタシ全然わかんなーい
そんなことより一緒に確率的チューリングマシンの話でもしよ

283 :名無しさん@お腹いっぱい。:2008/03/03(月) 04:07:33 ID:pQKLdIpn0
>>233からのレスを斜め読みしかしてないが、
多分、計算可能な関数に対する>>233の誤った理解が議論を複雑にしてる・・・

計算可能関数の正しい定義は>>262でほぼ正しいよ。
>>233は恒等的に f(x) = Σ(1/(2^k)) = 2 となる関数に対して、
アルゴリズム(厳密にはチューリングマシン) M(x) =``
xとは無関係に次の1-6を実行する。
1.変数k=0を用意する。
2.(変数 S=0を用意する。
3.SにS+1/(2^k)を代入する。
4.kにk+1を代入する。
5.kが∞では無いならば3に戻る。
6.Sを出力する。 ''
というアルゴリズム M を定義し、結果『Mは計算可能でない』という意味不明な主張を繰り返しているようにしか見えない。
確かに、Mはfを出力しないが、f(x)を出力するアルゴリズムは簡単に書けるからfは当然計算可能な関数。
何度も言うけど、>>262の定義で正しいからね。

じゃあ最初の疑問
『数学的に厳密に定義されたある集合 L ⊆ {0,1}^* と関数 f: L → {0,1}^* と x ∈ L に対して、
f(x) を計算するために設計された確率的(量子)アルゴリズム M(x) が停止しない場合がある。
Mはfを(有限時間で)計算できない可能性があるので、Mは計算可能ではないのではないか?』
(Lとfとしては、L={N =pq; p,qは素数},f(N) = (p,q) みたいな素因数分解問題を考えてくれ。)
を考えると、『Mは計算可能ではない』って文は意味が通らない。
『fは計算可能ではない』に読み代えると、意味は通るけど文章としては嘘を言ってる。
なぜなら、有限時間でfを計算できるアルゴリズムM'が存在するかもしれないから。
(f(N) = (p,q)とすると、N未満の整数でNを順次割るアルゴリズムM'が存在する。)

さらに言えば、確率的アルゴリズムに計算できて、決定的(非決定的)アルゴリズムに計算できないような関数はいまだに見たことがない。
もちろん計算時間が指数的に増えるから効率的ではないけど、有限時間では必ず正しい出力をして停止する。
まぁ、これは俺の経験談だから反例があったら教えてくれ。

ちなみに、アルゴリズムって言葉に厳密な定義を求めてるみたいだけど、実はアルゴリズムって言葉は日常語だから人によって捕らえ方が違っていいものだよ。
厳密なアルゴリズムの定義はチューリングマシンやラムダ計算で与えられるものだからね。
だから、量子アルゴリズムはアルゴリズムじゃない、っていう主張は変だし意味が通らない。
これを、ある量子チューリングマシンは有限時間で停止しない可能性がある、に変えれば少なくとも意味は通る。

284 :名無しさん@お腹いっぱい。:2008/03/03(月) 09:26:24 ID:TgoTi31p0
>>283

>だから、量子アルゴリズムはアルゴリズムじゃない、っていう主張は変だし意味が通らない。

それ、Deutch が証明してるし。

>ある量子チューリングマシンは有限時間で停止しない可能性がある

「ある」って何?
問題によって「量子チューリングマシンは有限時間で停止しない可能性がある」んじゃ?




285 :名無しさん@お腹いっぱい。:2008/03/03(月) 10:15:45 ID:9L6NJM130
>>281
>じゃあ、「解法」って何?という話になるんじゃないかと。
数学で、問題を解く手順。

>そういえば手続きの定義も書いてないね。
私はここで手続きは解法を構成する一連の流れという意味で書いた。

>チューリングマシンやアルゴリズムと同義と思ってたけど。
アルゴリズムの定義が対応するチューリングマシンが存在することと定義している本は少し読んだことがある。
(量子コンピュータの理論)
しかし、停止しないチューリングマシンが存在することから同義とはいえないでしょう。
なぜならば、チューリングマシンとアルゴリズムが同義ならば、停止しないチューリングマシンもアルゴリズムと同義でなければならないため。

>よく知らないけどここに載ってるみたいだよ
http://qwiki.stanford.edu/wiki/Complexity_Zoo
恥ずかしながら英語は読めない。
と書くと「だったら英語勉強して読め」とかまたキレられそうで嫌だが。

286 :名無しさん@お腹いっぱい。:2008/03/03(月) 11:07:26 ID:9L6NJM130
>>283
それでは、貴方の主張が正しいと仮定して、いくつかの疑問を提示します。

Q1
1.変数k=0を用意する。
2.(変数 S=0を用意する。
3.SにS+1/(2^k)を代入する。
4.kにk+1を代入する。
5.kが∞では無いならば3に戻る。
6.Sを出力する。

という関数はアルゴリズムと言って良いのでしょうか?
少なくともこの関数は有限時間内に終了しません。

Q2
素因数分解の話はいておくとして、
例えば、チューリングマシンに無限に擬似乱数ではないランダムな数値(∈{0,1})が記されたテープを与え、
そのテープから数値を読み取り、0か1を識別する。
そして、そのテープに1が記されていた場合に、それまでの0の個数を出力し、終了する手続きを構成した場合、

つまり、
T[i]を無限に擬似乱数ではないランダムな数値が記されたテープのi番目に記された値と定義すると、

1.変数i=0を用意する。
2.変数S=0を用意する。
3.T[i]=0ならばSにS+1を代入し3に戻る。
4.Sを出力する。

という関数は、無限に時間を与えられれば確実に終了しますが、
この関数は計算可能関数なのでしょうか?

287 :名無しさん@お腹いっぱい。:2008/03/03(月) 11:21:02 ID:9L6NJM130
>>286
1.変数S=0を用意する。
2.T[S]=0ならばSにS+1を代入し2に戻る。
3.Sを出力する。

に訂正。

288 :名無しさん@お腹いっぱい。:2008/03/03(月) 11:32:59 ID:TgoTi31p0
チューリングマシンの等価性って、最近の初学者はスルーするんですか?

289 :名無しさん@お腹いっぱい。:2008/03/03(月) 12:09:50 ID:pQKLdIpn0
>>284
>それ、Deutch が証明してるし。
これホントに?はじめて聞いた。

>「ある」って何?
>問題によって「量子チューリングマシンは有限時間で停止しない可能性がある」んじゃ?

『全ての量子チューリングマシンは有限時間で停止しない可能性がある』
と誤読しないために『ある』をつけた。誤読を招くようなら、読み飛ばしてもらって構わない。


>>286
うーん、まだ誤解が生じてる気がする。
というか、数学的な意味での『関数』と、プログラムの世界で使用される『関数』をごっちゃにしてないか?
前者は定義域から値域への単なる対応で、後者は『関数』とは言うが本来は手続きやアルゴリズムと呼ばれるもの。
前者の『関数』は同じ入力に対して必ず同じ出力がされないといけないけど、後者の『関数』は呼出しごとに出力が違っていてもいい。

その上で反論するけどQ1は数学的な『関数』ではなく、アルゴリズムの記述(つまり、後者の意味での『関数』)ではあるよ。
もちろん、有限時間で終了しないアルゴリズムだし、どんな目的のために構成されたかは不明なものだけど。

Q2は数学的な『関数』ではなく、『確率変数』を出力するためのアルゴリズムだね。


>>288
それはもしかして俺の
>まぁ、これは俺の経験談だから反例があったら教えてくれ。
への皮肉かw
流石にチューリングマシンの等価性ぐらい分かってますよ。
売り言葉に買い言葉みたいなものだ、気にしないで

290 :名無しさん@お腹いっぱい。:2008/03/03(月) 13:33:43 ID:9L6NJM130
>>289
アルゴリズムには有限時間内で終了する保証がなければならないと、私の大学の助教授が言ってました。
数学板の住人の方もそう仰っていました。

その上でアルゴリズムと言えると思いますか?

291 :名無しさん@お腹いっぱい。:2008/03/03(月) 13:37:03 ID:gHDk/FXN0
人によって「アルゴリズム」という言葉の意味を
1. 手続きと同義。プログラミング言語でいう関数。厳密にはチューリングマシン
2. ある問題を「正しく」「有限時間で」解く手続きのこと
のどっちで使っているかが違う
>>289は1.の意味で使ってるし、
「計算可能な関数とは、アルゴリズムが存在する関数のこと」というのは2.の意味で言ってる

292 :名無しさん@お腹いっぱい。:2008/03/03(月) 19:44:46 ID:9L6NJM130
>>291
チューリングマシンに無限に擬似乱数ではないランダムな数値(∈{0,1})が記されたテープを与え、
そのテープから数値を読み取り、0か1を識別する。
そして、そのテープに1が記されていた場合に、それまでの0の個数を出力し、終了する手続きを構成した場合、

つまり、
T[i]を無限に擬似乱数ではないランダムな数値が記されたテープのi番目に記された値と定義すると、

1.変数S=0を用意する。
2.T[S]=0ならばSにS+1を代入し2に戻る。
3.Sを出力する。

という関数は、無限に時間を与えられれば確実に終了しますが、
この関数は計算可能関数なのでしょうか?

という問いは、貴方のいう2の意味でアルゴリズムと言えると思う?

293 :名無しさん@お腹いっぱい。:2008/03/03(月) 23:21:15 ID:pQKLdIpn0
アルゴリズムって言葉は数学的に定義されてないし、日常語だ。
日本語の『手続き』や『方法』と同じレベルで使われる言葉。
卵焼きを作るためのアルゴリズムや、編み物をするためのアルゴリズムという使い方をしても別に問題はない。
要は文脈で意味が変わる言葉な訳だ。
ただし、計算機科学という世界だけに限定すれば、通常は>>291のどちらかの意味で使われることが多い。
まぁ、普通はアルゴリズム=チューリングマシンって考えちゃってかまわない。

1という立場を取れば、提示してくれている手続きはアルゴリズムだし、
2という立場を取れば、アルゴリズムじゃない。

でも、そんな文脈で意味が変わるアルゴリズムという言葉を使って、さも数学的命題のように
『この手続きは、アルゴリズムではない』と言われたらツッコミが入るのは当然だよね。
そもそも数学的命題じゃないんだから。

大学の先生や数学板の人は、そのときは2の立場で言ってたんだと思うけど、別に数学的命題としていってた訳じゃないはず。
それとも、『ある n に対し、n step 以内に停止している確率が 1 であるチューリングマシンをアルゴリズムと呼び、それ以外のものはアルゴリズムと呼ばない。』って定義してた?
そうだとしたら、その人たちはモグリだと思うけど・・・


あと、手続き(アルゴリズム)と関数と、さらに言えば確率変数をちゃんと使い分けようよ。
元々、計算可能な関数について聞きたかったんでしょ?なんで確率変数を出力する手続きを提示するの?
ちゃんと使い分けないと議論になんないし、あなたの主張がよく分からない。

294 :名無しさん@お腹いっぱい。:2008/03/03(月) 23:29:37 ID:pQKLdIpn0
>>それとも、『ある n に対し、n step 以内に停止している確率が 1 であるチューリングマシンをアルゴリズムと呼び、それ以外のものはアルゴリズムと呼ばない。』って定義してた?

ごめん、より正確には
『ある関数』

295 :名無しさん@お腹いっぱい。:2008/03/03(月) 23:33:51 ID:pQKLdIpn0
ミスった。正確には

『チューリングマシン M に対して、ある関数 f: {0,1}^* → N が存在し、
任意の x ∈ {0,1}^* に対して,M(x) のステップ数が f(x) 以下で抑えられるとき、
Mをアルゴリズムと呼ぶ。この条件を満たさないチューリングマシンはアルゴリズムと呼ばない。』


296 :名無しさん@お腹いっぱい。:2008/03/04(火) 00:50:37 ID:TiZ5q/D20
>>295
横からつっこむけど,Turing機械Mはある入力xを受理しない場合は無限ループに突入しても問題ないはず。

297 :名無しさん@お腹いっぱい。:2008/03/04(火) 00:59:14 ID:CJb5bihM0
>>292
>1.変数S=0を用意する。
>2.T[S]=0ならばSにS+1を代入し2に戻る。
>3.Sを出力する。
>
>という関数は、無限に時間を与えられれば確実に終了しますが、
>この関数は計算可能関数なのでしょうか?

だから、それは手続きであって関数じゃないんだって。
例えば、

1. 変数Tに入力を受け取る
2. 変数SにT+Tを代入する
3. S+2を出力する

という手続きをAとして、

1. 変数Tに入力を受け取る
2. 変数SにT+1を代入する
2. S+Sを出力する

という手続きをBとする。
AとBは異なる手続きだけど、どちらも同じ関数f(x)=2x+2を計算するアルゴリズム(2.の意味で)になってる。
アルゴリズムが存在するので、このfは計算可能な関数。
だけど、AやB自体は関数でないし、したがって計算可能関数かどうか論じることもできない。

298 :名無しさん@お腹いっぱい。:2008/03/04(火) 10:22:17 ID:UkFm1dut0
>>296
いやいや、必ず停止するアルゴリズムをご所望みたいだからこう定義しなきゃだめだろ
Turing認識可能ってことを考えると無限ループも許すけど

299 :名無しさん@お腹いっぱい。:2008/03/04(火) 10:44:08 ID:bxae2L3H0
>>293-295
大学の助教授は有限時間内に停止する保証がなければアルゴリズムではないと明言していたよ。


とりあえず、質問の仕方を変えたほうがよさそう。。。

・有限時間内に解決できる問題。
・無限に時間を与えられれば確実に解決できる保証があるが、有限時間内に解決できる場合が多いもの。
・無限に時間を与えられなければ解決できない問題。

これら問題のうち、計算可能なものはどれ?

300 :名無しさん@お腹いっぱい。:2008/03/04(火) 11:02:20 ID:dNTTDha20
そもそも、問題が計算可能って言うかな?

301 :名無しさん@お腹いっぱい。:2008/03/04(火) 16:45:07 ID:B4MGH4lc0
>>233 >>299
通りすがり&斜め読みだけど

「問題」ってのはパラメータを持つ述語で、そのパラメータを固定した述語を instance (例) と呼んで
これを解くアルゴリズムを考える
ここで解くというのは、述語を満たすような解集合の要素が存在するかどうかを判定するもの。

すると、判定の手続きには3種類あって、

・どのような instance に対しても有限時間内に判定ができる手続き
・instance が解をもては必ず有限時間で (「存在する」と) 判定できるが、解がない場合は終了しない場合がある手続き
・instance が解を持つ持たないにかかわらず、有限時間で手続きが終了する保証がない手続き

集合でいうと1つ目が帰納的集合で、2つ目が機能的に可算 (RE) な集合
決定可能というのは1つめの手続きが存在する場合。「解くアルゴリズムが存在する」という場合も同じだと思う。
「計算可能性」の側面から考えるなら、TMがかならず停止しないといけないからこれも1つ目の手続きを指してそう呼ぶ

用語定義が適当ですまんけど雰囲気としてはこうなのでは




302 :名無しさん@お腹いっぱい。:2008/03/06(木) 03:47:43 ID:+Fmuz+aB0
まぁそれ以前にまず>>233のコインの表という乱数発生がどういうアルゴリズムかが問題な気がする
コインの表などという表現を使っているから、あたかも現実の事の様に考えてしまうが、
あくまでアルゴリズムである以上、その乱数発生にもなんらかのアルゴリズムがあるわけでそれを加味しないことには停止性うんぬんは考えられないと思うんだけど・・・

計算可能性何がしに詳しくないから見当違いな意見かもしれないけど

303 :名無しさん@お腹いっぱい。:2008/03/06(木) 04:45:22 ID:PlpqN/zF0
>>302
通常の確率変数だと思えばよくないかな。
各試行は独立で、それぞれ 1/2 の確立で表か裏の値を取る、とする。

>>233のコインの例は停止しない可能性があるので、通常の意味で言えば「計算可能でない」と言えると思うけど、
確率的なアルゴリズムの場合はそれ専用の計算可能性の定義があるのではないかと思っているのだけれど、
実際どうなんだろう。例えば>>233だと

n回で終了しない確率を P(n) として、n→∞ では P(n)→0 だから、「確率的には計算可能」みたいな。

304 :303:2008/03/06(木) 04:46:18 ID:PlpqN/zF0
>>303
ひとつめ ×確立 ○確率
恥ずかしい

305 :売国マル韓:2008/03/06(木) 18:19:39 ID:NHVPaCc90
パチンコスレで遠隔、ホルコン、サクラ、マネーロンダリングなどについて書き込むと渋谷マルハン社員やマルハンに依頼された
ネット工作会社がスレ荒らしをしてスレが機能停止します。
↓↓工作員の荒らしのやり方↓↓
2008/01/10(木)ID:iA54n BU50
■■■■マルハン総合スレッド 9■■■■http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→87021165/783-784
【宮崎県都城市】パチ事情そのAhttp://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→87189246/658-659
【山と川】宮崎県児湯付近PART1【自然イパーイ】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→88235164/471-472
【基地外が大暴れ4】エスパス日拓総合スレ【18発目】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→88885488/401-410
2008/01/13(日)ID:1HLcWz UK0
【基地外が大暴れ4】エスパス日拓総合スレ【18発目】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→88885488/461-462
■■■■マルハン総合スレッド 9■■■■http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→87021165/809-810
【香川】パーラーグランドのスレ2【徳島】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→88315438/324
【延岡】宮崎県北情報PART3【日向】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→96865970/186

パチンコ産業は荒らすことでレスとレスの間を空けて読む気をなくさせたり
マネーロンダリング、さくら、ホルコン、遠隔、などの風評被害を最小限に抑えようとしてる。

新スレ→○○○マルハンパチンコタワー渋谷パート10○○○
★★★★★このスレの解説★★★★★を読んでみるとよく判る。
http://money6.2ch.net/test/read.cgi/pachij/120←左右くっつけて→1304777/559
ネット工作員については→【電通TBS】ピットクルー(株)【プロ工作員】
http://society6.2ch.net/test/read.cgi/mass/118←左右くっつけて→9187503/65
【朝鮮玉入】パチンコ廃止すれば内需増加【20兆円】
http://money6.2ch.net/test/read.cgi/eco/1204597218/1-100
◎ハンの今後の目標は売り上げ5兆円、500店舗、上場すること。


306 :名無しさん@お腹いっぱい。:2008/03/06(木) 20:53:55 ID:MItHiGTi0
ID:Wg8L3vhD0=ID:9L6NJM130=ID:bxae2L3H0さんは、
一から計算理論の勉強をし直したほうがいいと思います。

それと「関数とは何か」ということも学んだほうがいいと思います。
計算可能関数はアルゴリズムとの対応が付きますが、
計算不可能関数は決して、
「有限時間で計算できないけど無限時間で計算できるかもしれないもの」
などではありません。

そもそも「無限時間」などというものを持ち出すのが勘違いの原因なので、
次はその考えが間違いだということを意識して、再び計算理論を勉強してください。

307 :名無しさん@お腹いっぱい。:2008/03/06(木) 21:10:36 ID:B+YAxpoH0
(´・ω・`)ショボーン

308 :名無しさん@お腹いっぱい。:2008/03/07(金) 00:25:57 ID:smYDkr7q0
>>303
だからその”各試行は独立で、それぞれ 1/2 の確立で表か裏の値を取る、とする。”をどう実現するかが重要なのでは?
普通計算可能性といえば、ある条件を満たす数を計算できるかどうかで、この場合はようは表が出る事があるかどうかの判定となるわけだけど
結局その表が出るかどうかはその乱数生成のアルゴリズムに深く依存するわけでしょ?

実装を表さないのなら、そんなあいまいな確率的なものを組み込んだ関数はもはやアルゴリズムとは呼べないと思う

309 :名無しさん@お腹いっぱい。:2008/03/07(金) 18:51:54 ID:d86BuYGa0
実装できなきゃだめっていうなら、非決定性TMやオラクルTMも認めないってスタンス?


310 :名無しさん@お腹いっぱい。:2008/03/08(土) 22:43:11 ID:y2pWcxKY0
>>308
TMの定義のどこかに確率変数を入れないと、
”各試行は独立で、それぞれ 1/2 の確立で表か裏の値を取る、とする。”
なんて振る舞いは情報量的に実現できないよ。
アルゴリズムの前後でエントロピーが増えちゃってるからね。
だから、>>303みたいに定義するのが普通。


311 :名無しさん@お腹いっぱい。:2008/06/12(木) 10:57:15 ID:fv8wnW7j0
ポンピング補題の質問はここでいい?

ポンピング補題を利用して
L={10^n10^n1 | n>=0} が正規言語でないことを示せ。

これで、s=10^p10^p1 とおいてそのあとの証明の流れを教えてほしい

312 :名無しさん@お腹いっぱい。:2008/06/12(木) 10:57:49 ID:fv8wnW7j0
あげてみる

313 :名無しさん@お腹いっぱい。:2008/06/12(木) 14:16:20 ID:Ro286ddG0
s=xyzで
yが1を含む場合
yが0^kの場合
に分けて考えれば?

314 :名無しさん@お腹いっぱい。:2008/06/13(金) 09:28:44 ID:BeOHzdqt0
>>313
Lを正規言語と仮定
s=10^p10^p1とするこのときs=xyzと三分割できる

@)yが1を含むとき |xy|>pよりポンピング補題の条件を満たさず矛盾する

A)yが0^pのとき 上と同様に矛盾する

B)yが1のとき これはxyz not∈ L なのでポンピング補題の条件に矛盾

@AB全ての場合で矛盾することから、Lが正規言語という仮定が矛盾、
したがってLは正規言語でないことが証明された。

これでいいのか分からない。誰か添削お願いします。

315 :名無しさん@お腹いっぱい。:2008/06/13(金) 15:46:04 ID:mLbTPCjV0
ぜんぜんわかってねぇな

316 :名無しさん@お腹いっぱい。:2008/06/14(土) 12:48:52 ID:SnM0hXI20
>>315
どこかいけないのかワカンネ kwskお願いします

317 :名無しさん@お腹いっぱい。:2008/06/14(土) 13:33:08 ID:oTI23V3/0
たとえば
> yが1を含むとき |xy|>pよりポンピング補題の条件を満たさず矛盾する
なんでだよ。
ポンピング補題の条件っていうのを自分なりに解釈して人に説明できるか?

318 :名無しさん@お腹いっぱい。:2008/06/14(土) 15:32:25 ID:SnM0hXI20
>>317
持ってるテキストにポンピング補題の3条件として
Lが正規言語ならばある定数pが存在して、少なくとも長さがpであるような任意のs∈Lはs = xyzと分割できて、
1 全てのi>=0でxy^iz∈L
2 |y|>0
3 |xy|<=p

これが定理として与えられてるんだが、それならおkなのか?


319 :名無しさん@お腹いっぱい。:2008/06/14(土) 15:54:36 ID:oTI23V3/0
そりゃ定理そのものだろ。理解できてるのか?
理解できてるなら、なんで
> yが1を含むとき |xy|>p
だ?


320 :名無しさん@お腹いっぱい。:2008/06/14(土) 19:52:30 ID:SnM0hXI20
>>319
yが1を含む場合をs = 10^p10^p1でy = 0^p1とおいたら

1 0^p1 0^p1
~ ~~~~~ ~~~~
x  y  z

|xy|>pじゃないの?

321 :名無しさん@お腹いっぱい。:2008/06/14(土) 22:21:17 ID:oTI23V3/0
「s=10^p10^p1」のpと「少なくとも長さがp...|xy|<=p」のpとは違う。


322 :名無しさん@お腹いっぱい。:2008/06/14(土) 23:11:11 ID:SnM0hXI20
>>321
y =0^k1 としたとき
xyyz = x0^k10^k1zはx0^k10^k1がxyzと等しいためxyyz not∈L
これじゃだめ?
他の分割もxyyzのときを考えればいけそう。

323 :名無しさん@お腹いっぱい。:2008/06/15(日) 00:38:53 ID:NwqPd9ax0
> xyyz = x0^k10^k1zはx0^k10^k1がxyzと等しいためxyyz not∈L
さっぱりだめ。「等しいとLの要素でない」理由がない。

324 :名無しさん@お腹いっぱい。:2008/06/15(日) 16:53:39 ID:3WRQWZRG0
>>323
訳ワカンネ とりあえず飛ばして先に進めてみる。よければ証明例を教えて。

325 :名無しさん@お腹いっぱい。:2008/06/19(木) 20:26:55 ID:tPRSX4ar0
通りすがりです

まずxyが何になる可能性があるかを考えて、さらにyが何になる可能性があるかを考える
xは空でもいいと思ったんだがあってるかな?

(1) yが1を含む場合の「1」は、1つ目の1だと思うぞ
この場合、1がリピートしちゃうのでLに含まれない

(2) yが1を含まない、つまり0^+の場合は0の個数が合わなくなるのでアウト (だと思う確かめてない)


326 :名無しさん@お腹いっぱい。:2008/07/19(土) 11:30:02 ID:vHtH1hrg0
仮想記憶にいおいて、主記憶RAMの読み書きに100ナノsec、ハードディスクの1ページ分の読み書きに100マイクロsecを要する。
プロセッサから参照されたデータが主記憶にある確率が80%で、
主記憶のフレーム上に余裕が無い確率が80%であった場合、
参照所要時間の期待値を有効数字3桁で求めよ。

という問題なのですが、ページアウトが絡んできて混乱してます。その辺りの考えたもお願いします。


327 :名無しさん@お腹いっぱい。:2008/08/21(木) 18:44:49 ID:BAK16zVk0
>>324
あ?ほんとに分かってんのか?
「はい」ってのはな「はい、わかりました」を略して「はい」なんだよ
頭だけでわかったって言わねんだぞ?学校の勉強じゃねえんだから
社会では?お?実際に出来て初めて「わかった」言うんだ
出来もしねえ奴が軽々しくはいなんて言うんじゃねえよ
すいませんじゃねえよこら。お?申し訳ありませんじゃねえんだよ。
申し訳ありませんってのは本当に反省した奴だけが言える事だろうが。
反省してるって事は今度は必ず出来るって事だ。
お前今できんのかよ。今日のお前は出来てたのかよ?お?
出来もしねえ癖に口だけ一丁前な事言うんじゃねえよ。
お?聴こえてんのかよコラ?あ?
やる気がねえんだったら来なくていいぞ?
お前ナメてんだろコラ?
仕事中だと思って優しく口で言ってりゃ調子に乗ってんじゃねえぞコラ?お?
外で遭ってたら今頃カタワだぞお前?とっくに?あ?

328 :名無しさん@お腹いっぱい。:2008/08/21(木) 19:44:16 ID:cb55/ssS0
コピペを改変する手間を惜しむなよw

329 :名無しさん@お腹いっぱい。:2008/10/04(土) 02:05:31 ID:W26dB6tP0
2次元で、円、矩形、あるいは楕円が別の楕円に内包されているかどうかを知るにはどうすればいいですか?

すれ違いならスマソ。

330 :名無しさん@お腹いっぱい。:2008/10/04(土) 13:34:59 ID:HtkalUz20
内包する楕円とその内部を不等式で表現して
(x**2/a + y**2/b ≦ r)
矩形なら、全ての頂点がこの不等式を満たすなら内包されている。

円は...どうすればいいんだろ。

331 :名無しさん@お腹いっぱい。:2008/10/04(土) 14:58:14 ID:E2e2b00Q0
円についても不等式立てて連立させて
解なしの範囲がなければ内包されている

332 :名無しさん@お腹いっぱい。:2008/10/05(日) 16:15:58 ID:D1F+G2KL0
計算機的にできたかな?

333 :名無しさん@お腹いっぱい。:2008/10/09(木) 17:52:44 ID:ZZPuou9N0
すごく・・・ キモいです・・・
http://jp.youtube.com/watch?v=ZiRgYBHoAoU

334 :名無しさん@お腹いっぱい。:2008/10/15(水) 14:17:20 ID:xkGslT+Z0
おいら数学屋なんですが、
よくプログラミングが定理の証明とみなせるといわれるのはいかなる意味においてなのでしょうか?
知ってる人がいたら是非教えてください。

335 :名無しさん@お腹いっぱい。:2008/10/15(水) 15:00:41 ID:2P55WcSF0
UNIXのwriteがシステムコール、fwriteがライブラリコールであることをどのようにしたら示せるでしょうか?

336 :名無しさん@お腹いっぱい。:2008/10/15(水) 19:16:42 ID:NnACQPn/0
>>335
マニュアルを探して、2章に書いてあったらシステムコール、3章ならライブラリコール。
と覚えておけば実用上問題はない。

ただし、実際には、wait, waitpid, wait3はwait4を呼んでるだけみたいな、
歴史的にはシステムコールだったけど後になってより汎用的なのができて、
そっちで置き換えみたいなのがけっこうあって、
機械語レベルのソフトウェア割込みと本当に対応してるかどうかは
ソースコード読まないとわからない。

厳密に区別しようとしたら、言葉を厳密に定義しないと無理。

337 :名無しさん@お腹いっぱい。:2008/10/15(水) 21:31:49 ID:2P55WcSF0
>>336
わかりました!ありがとうございますm(__)m

338 :名無しさん@お腹いっぱい。:2008/10/15(水) 23:51:11 ID:DxiDDyYP0
>>334
Curry-Howard のことかな
それとも program extraction のことかな

339 :名無しさん@お腹いっぱい。:2008/10/21(火) 10:13:05 ID:eIklhk1W0
>>338
どうも有難うございます。
早速調べてみます。

340 :名無しさん@お腹いっぱい。:2008/11/10(月) 03:44:11 ID:iRFhg5Nz0
オマエラ何低次元な話してるんだ。
>>334
オイラ情報屋。工学修士、博士単位取得退学。学生当時専門は超並列計算。
現在は技術屋、興味方向は暗号学。「守る」のが仕事なんでね。

理論方面は歴史を見ても数学屋さんに頼るしかないんだよ、安全な暗号方式
の考案って奴は。俺ら旧帝組情報屋だって知ってる。よろしく頼む。

341 :名無しさん@お腹いっぱい。:2008/11/12(水) 23:31:36 ID:Qeu2OzEGO
http://www.tohoku.ac.jp/japanese/news/2008/07-09.htm
11/12 サイバーサイエンスセンターのSX−9がHPCCの19項目で世界一 

2008年3月から稼働しておりますサイバーサイエンスセンターのスーパーコンピュータシステムSX-9が、HPC(高性能計算)分野でのベンチマークテストであるHPCチャレンジで28項目中19項目で世界最高速を達成いたしました(2008年10月24日現在)。
HPCチャレンジベンチマークは、米国政府の援助のもと、テネシー大学のJ.ドンガラ(J.Dongarra)博士を中心にHPC関係者が参画して策定されたものです。
世界のスーパコンピュータの性能ランキングTOP500で使用されているLinpack(リンパック)ベンチマークを補完し、スーパーコンピュータの性能を多面的な観点から評価します。
 今回のベンチマーク結果は、HPCチャレンジのベンチマークプログラムを東北大学サイバーサイエンスセンタースーパーコンピュータSX-9で実行したもので、
評価28項目の中でシングル環境と多重負荷時のメモリ性能(STREAM)で8項目、
プロセス間の転送性能 (Bandwidth)で5項目、
シングル環境及び多重負荷時の行列積の演算性能(DGEMM)で2項目、FFTの演算性能の2項目とシングル環境と多重負荷時のメモリのランダムアクセスの性能(RandomAccess)で2項目において、世界最高速の記録を達成いたしました。
このたびのベンチマーク結果の詳細につきましては、以下のページをご参照ください。
 詳細
http://www.isc.tohoku.ac.jp/fig/HPCC2009_TOHOKU_UNIV.png
サイバーサイエンスセンターホームページ
http://www.isc.tohoku.ac.jp/hpcc2008


342 :名無しさん@お腹いっぱい。:2008/11/12(水) 23:35:16 ID:YmX1E3tB0
質問じゃないなら来るな

343 :sage:2008/11/14(金) 18:39:38 ID:Hvo1Ldur0
オーダ記法についての質問をしてもよろしいでしょうか?
(1) (2n^2 + log^7(n) + 10)(√n + 10n^0.1 + 5logn) のオーダを見積もれ.
(2) √(n^2 + 100n) のオーダを見積もれ.
(3) 2^(n+1) = O(2^n) は正しいか. 理由とともに答えよ.
(4) 2^(2n) = O(2n) は正しいか. 理由とともに答えよ.
(5)Σ i = Θ(n^2) は正しいか. 理由とともに答えよ.
(6) n! = O(n^n) は正しいか. 理由とともに答えよ.
(7) n! = Ω(2^n) は正しいか. 理由とともに答えよ.

課題で出てさっぱり手がつけられないので、ぜひ回答していただきたいです。

344 :名無しさん@お腹いっぱい。:2008/11/14(金) 18:41:06 ID:Hvo1Ldur0
名前欄にsageと入れてしまいました。すみませんでした。。

345 :名無しさん@お腹いっぱい。:2008/11/15(土) 08:56:27 ID:B658P9NC0
>>343
Σiは式いっぱつだから桁数考慮してO(log n)とかだろうね
n!はスターリンの公式でいいなら、同様にO(1)か、桁数を考慮してO(log n)になるね。

つうか、数式で書けるやつは、求める精度によるだろJKってレポートに書いておけばいいんじゃね?

346 :名無しさん@お腹いっぱい。:2008/11/15(土) 10:32:00 ID:+kp0AePJ0
>>345
オーダー記法はその関数を計算するための計算量を表してるんじゃねーぞ

>>343
定義は理解したか?定義理解したら後は当て嵌めていくだけだろ

347 :343:2008/11/15(土) 21:26:53 ID:WafJN3xB0
ありがとうございます。
式が正しいか正しくないかを評価するというのはわかってきましたが、オーダの見積もり方がわかりません。。。

348 :名無しさん@お腹いっぱい。:2008/11/16(日) 01:27:55 ID:tXxPkpuY0
オメガとシータも出てきてるみたいだけど、とりあえず俺はオーダーだけ教えよう
オーダー記法の定義をまずしっかり理解しろ

「関数f(x)、g(x)があるとき、 lim( f(a)/g(a) ) <= c となるような cが存在するとき
f(x)はO(g(x))であるという」(limはx→∞を省略するよ)

極限の定義もあるから別の書き方をしてる場合もあるが、言ってることは一緒だ

例えば f(n) = n^2 + n + 1 だとして、これのオーダーを求めてみよう

定義にあてはめれば

lim ( (n^2 + n + 1) / n^2 ) = 1 <= c (cは任意の定数)だから
n^2 + n + 1 は O(n^2) であると言える。

ここでオーダー記法の重要点だが、

lim( (n^2 + n + 1 ) / n^3 ) = 0 <= c だから n^2 + n + 1 はO(n^3)でもあると言える。
(これ、計算量でオーダーを理解してる人は知らない人が多い)

つまりオーダーのめちゃめちゃ高い物を指定しておけば間違いでは無いと言えるわけだ

349 :名無しさん@お腹いっぱい。:2008/11/16(日) 01:30:10 ID:tXxPkpuY0
だから、オーダーを見積もれって言う質問に答えると

O( n^n^n^n^n^n^n ) nのn乗のn乗のn乗のn乗のn乗のn乗 ですって言っても間違いでは無い!
まあ間違いなく「そういう意味じゃない」って言われるだろうけどな

350 :名無しさん@お腹いっぱい。:2008/11/16(日) 01:59:39 ID:FEKcqEjJ0
>>349
それを書くなら Ackermann 関数で書いたらかっこよくね?

>まあ間違いなく「そういう意味じゃない」
その部分の理解度を見るためにΩやΘでの評価を課題で出してるんだと思うけど。


351 :名無しさん@お腹いっぱい。:2008/11/16(日) 02:16:27 ID:tXxPkpuY0
>>350
オメガはΩ(1)ですって言っとけばええやん?
シータはどうしようもないがね

352 :名無しさん@お腹いっぱい。:2008/11/16(日) 09:28:16 ID:6zM6fviG0
ユークリッド互除法の最悪計算量をLameの定理の結果を用いずに解析せよという問題なのですが、答えていただけないでしょうか?よろしくお願いします。
問題文がこれだけなので、解析の制度まではわかりません。

353 :名無しさん@お腹いっぱい。:2008/11/17(月) 11:38:17 ID:0NHh/9b10
そらにある雲ができる仕組みというのは存在するんですよね?
それが形になる仕組みを科学的に、
めったに無いですが、動物の形に見えたりします、どうして形が特定の
ようなものになるか教えてください。
偶然になるでは答えではないですよね?
仕組みが存在するはずです。


354 :名無しさん@お腹いっぱい。:2008/11/17(月) 16:55:18 ID:BgG/empE0
形ができるのは偶然、その形が動物に見えるのはゲシュタルト心理学

355 :名無しさん@お腹いっぱい。:2008/11/30(日) 00:33:43 ID:wDn2Ahas0
ところで情報系や計算機系の学科は終焉してると聞くことがあるけど
ほんとなの?
現在、情報工学1年だけど不安だ。
他学科への転移も考えたほうがいいの?

356 :名無しさん@お腹いっぱい。:2008/11/30(日) 11:05:04 ID:g+f7RFMr0
文系卒程度の就職ならできるだろうから、無難に生きたいなら、そのままでいいんじゃない?

357 :名無しさん@お腹いっぱい。:2008/11/30(日) 14:23:51 ID:IMb1iCbk0
学科に頼って生きようしてるのなら医学部以外は終焉してると思った方がいいんじゃね。

358 :名無しさん@お腹いっぱい。:2008/11/30(日) 17:17:11 ID:SbUvp4zo0
Pred'で自然数Cn+1をβ簡約した時の過程を教えて。何度やってもCnにならね。

359 :名無しさん@お腹いっぱい。:2008/11/30(日) 21:40:40 ID:4+PeTQff0
単に Pred' とか言われても定義わかんなくね?

360 :名無しさん@お腹いっぱい。:2008/12/01(月) 00:33:02 ID:6EoovBMD0
Pred' = λnsz.n(λgh.h(gs))(λu.z)(λu.u) だった

361 :名無しさん@お腹いっぱい。:2008/12/01(月) 08:25:28 ID:zRTctcp30
うち国立の情報だけど、生徒の半数以上が、最初「ブラウザ」って何?って状態だった。ビビッた。

>>355
情報なんてまだ産業革命が始まってもいないとも聞くけど。東インド会社ができたくらいだとか

362 :名無しさん@お腹いっぱい。:2008/12/01(月) 19:59:23 ID:/z1QJtZf0
>>360
わかった。
λsz の中身が

(λgh.h(gs))^{n+1} (λu.z)
→ (λgh.h(gs))^n (λh.hz)
→ (λgh.h(gs))^{n-1} (λh.h(sz))
→ (λgh.h(gs))^{n-2} (λh.h(s(sz)))
→ (λgh.h(gs))^{n-3} (λh.h(s(s(sz))))
→ ...
→ λh.h(s^n z)

これに λu.u が適用されるから、外の λ とあわせて λsz.s^n z

363 :名無しさん@お腹いっぱい。:2008/12/01(月) 21:05:30 ID:D9eEck6U0
ここで書くことじゃないんだろうけど、いつになったら
「情報」=パソコン の誤解が解けるんだろうか・・・

364 :名無しさん@お腹いっぱい。:2008/12/02(火) 00:34:51 ID:UzZ1M7a90
誤解なのか?
パソコン≒コンピュータだとすれば、「情報」=パソコンだろ。
それ以上のことをやってるかもしれんが、大学、学部、研究室によって
やってることが違いすぎて、門外漢がイメージできるような共通項はないよ。
情報系が終わっている、と言われる理由の一つだろうね。
情報系出身者は何ができるのか?が分からない。
パソコンだけだったら派遣のお姉さんのほうが都合がよいし、
プログラミングだけだったら中国人やインド人のほうが安いしね。

365 :名無しさん@お腹いっぱい。:2008/12/02(火) 04:24:14 ID:ITDNLkyS0
すごい人やとったことないとそう言う結論になるだろうね。かわいそうに。

366 :名無しさん@お腹いっぱい。:2008/12/02(火) 13:19:44 ID:PZu+Mufj0
>>363のいってるのは
情報=PCってのは情報学科でてたらエクセルに詳しいとか思われちゃうってことかな?

>>364
やっぱ専門で学んできてるから、プログラミング技術だけみても、それなりに他の学科との差別化はできてると思うけどな。
機電の人間が書いた恐ろしい組み込みソースを良くみたからさ。

367 :名無しさん@お腹いっぱい。:2008/12/02(火) 20:07:52 ID:r/b15a+J0
ネットワークアドレス197.18.110.48/28の場合、
サブネットマスク、クラス、使用可能なサブネットワーク、
使用可能なホスト数、ブロードキャストアドレスを求めよ。

どなたか、これの解き方と答え、もしくは解き方の載っているサイト
を教えてださい。

368 :名無しさん@お腹いっぱい。:2008/12/02(火) 21:21:29 ID:UzZ1M7a90
>>365,366
申し訳ないけど、今のほとんどの企業は、プログラミングだけが「すごい人」なんて必要としてないよ。
「すごい人」がいなきゃ作れないソフトウェアなんて、ほとんどないからねぇ。
平均+αくらいのスキルで十分。つまり給料の安い中国人やインド人で十分。
それに、今は不況でプログラミングしかできない人は優先的にクビになってるよ。

369 :名無しさん@お腹いっぱい。:2008/12/02(火) 21:29:00 ID:RHRCm+9N0
>>367
IPアドレスでググって最初に出てきたページを穴があくまで読め

370 :名無しさん@お腹いっぱい。:2008/12/03(水) 02:37:51 ID:RQE8nCcz0
>>368
中国人やインド人を引き合いに出すのなら
一部のスーパーマンや既得権益を持ってる人を除いて
日本人はいらないということになるね。
日本人で且つ将来に不安を覚えるような身分に生まれたことを呪うしかない。

これマ板ネタだよな。

371 :名無しさん@お腹いっぱい。:2008/12/03(水) 04:22:21 ID:E3nFR+zf0
>>370
うーん。オフショアって言葉知ってる?
オフショアに移管できる仕事とできない仕事があるわけよ。
ソフトウェア開発は、オフショアに移管しやすい典型的な仕事だよね。
あと、サポート業務とか、人事とか経理もオフショアに移管され始めてるよね。
一方、オフショアにだせない、出さないほうが良い仕事もあるわけで、
日本人が日本で生きる限り、そういう分野に活躍の場を求めたほうが良いってこと。

情報系出身者で、最近、金融機関に就職してる人が多いけど、その理由の一つだね。


372 :名無しさん@お腹いっぱい。:2008/12/03(水) 12:45:22 ID:QNb6IX9d0
>>368
プログラミング技術「だけ」みても、ね。
あと、プログラミング「だけ」がすごい人を必要としてないなら、想定してる企業が私らの間で違うんだわ。

マ板ネタですな。スマソ

373 :名無しさん@お腹いっぱい。:2008/12/03(水) 13:38:57 ID:tDfNhWoJ0
>>371
オフショアだけを挙げているけれど
外国人労働者や移民も想定しておいた方がいいだろうし
根源的に日本企業である必要もないと考えると
日本人でなければならない仕事はほとんどないんじゃないか。

マ板で酒の肴にするには大きな話題だな。社会学あたりか。

374 :FSF@女子大製:2008/12/13(土) 19:01:22 ID:LhFqWp5C0
すみません、初めて質問します。

Verilog-HDLで8ビットマイクロプロセッサの設計して来い、
と教授に言われました。
なんのこっちゃわからなくて、
とりあえずVerilogについてだけいろいろWebを見て回ったのですが、
マイクロプロセッサに必要なモジュールをVerilogで記述・・・って
実際にはどんな感じなんでしょう・・・。

ぜんぜんマイクロプロセッサとVerilogがつながりません↓↓
詳しい方いらっしゃいませんか?
(スレ違ったら申し訳ないです・・・)

375 :名無しさん@お腹いっぱい。:2008/12/14(日) 01:30:39 ID:BkvTZx3Z0
スレ違ってます。
以下にどうぞ

【Verilog】記述言語で論理設計 Project7【VHDL】
http://science6.2ch.net/test/read.cgi/denki/1222899759/

376 :名無しさん@お腹いっぱい。:2008/12/14(日) 22:01:36 ID:IO6yaWNp0
計算機科学系の学部のある大学院で、おすすめはがあったら是非教えてください。

377 :名無しさん@お腹いっぱい。:2008/12/16(火) 18:58:22 ID:xT8sCjD80
東大
NAIST
JAIST

378 :名無しさん@お腹いっぱい。:2008/12/16(火) 22:37:48 ID:OBeffyDm0
学部のある大学院って

379 :名無しさん@お腹いっぱい。:2008/12/17(水) 02:50:13 ID:npDoyKQX0
理論計算機科学だったら東工大とか京大じゃね?

380 :名無しさん@お腹いっぱい。:2008/12/17(水) 13:23:55 ID:zigMs5+s0
>>368
「ソフトウェア開発」 を、企業の社内システム開発=SI に限れば、
確かにそのとおり。

ソフトウェア開発と聞いてSIしか思い浮かばないのはちょっと
視野が狭いといしか言いようがない。



381 :名無しさん@お腹いっぱい。:2008/12/26(金) 19:03:40 ID:dxhzUuZbO
p≦2n+3なるnを持ってきて
xyz=10^n10^n1とします(yは空文字でない)

yが1を含んだらxy^2zはLに含まれない
yが1を含まなくても同じ
よってLはポンピング補題の条件を満たさない

382 :名無しさん@お腹いっぱい。:2008/12/26(金) 21:20:51 ID:dxhzUuZbO
ポンピング自体の証明
Lは決定的オートマトンMで受理される
→pをMの状態数+1とおく
→p以上の長さのs∈Lはその受理走査の途中で同じMの状態aに二回であう
→一回目にaにならとこらから二回目になるところまでをyとすれば
そのyを任意回くりかえしても受理できる

383 :名無しさん@お腹いっぱい。:2008/12/29(月) 01:08:49 ID:dMhPFwUJ0
プログラミングができませんが、計算理論はやれますかね?

384 :名無しさん@お腹いっぱい。:2008/12/29(月) 03:14:41 ID:pMgtBWk10
やれると思うよ

385 :名無しさん@お腹いっぱい。:2008/12/29(月) 18:12:48 ID:8UcTHBfV0
計算理論というのは、ほぼ数学と考えてよいですか。
何かアイディア出したら、紙と鉛筆だけで修士論文書けるかな?


386 :名無しさん@お腹いっぱい。:2008/12/29(月) 18:21:34 ID:OfxbnLPe0
分野や内容による。
スパコンとかクラスタぶんまわして検証しなきゃかもしれんし。

387 :名無しさん@お腹いっぱい。:2008/12/30(火) 07:10:55 ID:uQTMXrdC0
>>385
計算理論は、数学。
ただ、数学だとしても、紙と鉛筆だけで修士論文かけるとは限らない

388 :名無しさん@お腹いっぱい。:2009/01/02(金) 20:52:46 ID:U991eN+70
量子コンピュータ関係の修士論文にしたいのだが、
何かよいテーマあるかな?
量子コンピュータに関する調査論文だけでは、目新しいことや
工夫した点など盛り込めないし・・。
なにかヒントをください。

389 :名無しさん@お腹いっぱい。:2009/01/03(土) 21:52:24 ID:NMp6JSLt0
量子コンピュータの新しいアルゴリズムを提案すればおk。
NP完全問題を多項式時間で解く奴きぼん。


390 :名無しさん@お腹いっぱい。:2009/01/04(日) 02:06:12 ID:nSMMOYJZ0
>>389
BQP⊆NPと思っている人って計算理論の専門家には,ほとんどいないんじゃないかな。
>>388
マジレスするが,こんなところではなく先生に相談汁。

391 :名無しさん@お腹いっぱい。:2009/01/04(日) 22:51:03 ID:LT3wuUdV0
【偽医療】AKA 関節運動学的アプローチ【インチキ医療】
http://gimpo.2ch.net/test/read.cgi/body/1211885077/

千城台クリニックのAKA療法による不正請求返金
http://gimpo.2ch.net/test/read.cgi/healing/1207056268/

【肩こり腰痛】日本関節運動学的アプローチ(AKA)医学会
http://society6.2ch.net/test/read.cgi/hosp/1229493132/

392 :名無しさん@お腹いっぱい。:2009/01/06(火) 01:39:18 ID:6KTFMcOL0
修士で研究するには

A オートマトン 言語理論 計算論 1,2 ( J.ホップクロフト、R.モトワニ J.ウルマン 著)
B 計算理論の基礎 (マイケルシプサー 著)
C 離散数学入門(守屋悦朗 著)
を習得したあと、量子コンピュータ、量子情報理論に関する書物を読んでいけばよいでしょうか。
ほかに数学的な準備というものは必要になりますでしょうか。

数学科の学ぶ数学、解析学 代数、確率論なども必要でしょうか。
(最終的には学習しますが、計算論分野で
量子コンピュータ、アルゴリズムなどを研究するのに必要な最低限の知識は、上記のA,B,Cの書物で
十分なのか足りないのか、そのあたりを教えていただければ幸いです。


393 :名無しさん@お腹いっぱい。:2009/01/06(火) 08:45:52 ID:Am+sKg9E0
指導教員が量子コンピュータのことを知らなければ、
そんな修論の指導はできないので無理。
量子コンピュータのことをやっている研究室があるんなら、そこの教員にきけ。


394 :名無しさん@お腹いっぱい。:2009/01/06(火) 13:30:49 ID:Vo/hidmz0
教授の専門外なことを好き勝手オナニーしていいのは卒論まで

395 :名無しさん@お腹いっぱい。:2009/01/06(火) 13:52:30 ID:g9CKknXT0
つうことは、だれも研究してないような新しい分野は、修士論文じゃなくて卒業論文でってことだな。

396 :名無しさん@お腹いっぱい。:2009/01/06(火) 14:13:59 ID:g9CKknXT0
>>392
マジレスすると、量子コンピュータやるなら、線積分やベクトル解析できないとダメじゃねぇの?
工学部のやる数学はひととおりおさえておく必要はあるはず。
あと、計算論方面では「アルゴリズム・デザイン」読んでおけ。

397 :名無しさん@お腹いっぱい。:2009/01/06(火) 14:34:09 ID:ZyiYt5a00
>>392
それっぽいのがあったから、一応張っとくわ。
http://www-imai.is.s.u-tokyo.ac.jp/~tokunaga/index-j.html


398 :名無しさん@お腹いっぱい。:2009/01/06(火) 17:47:10 ID:fUqqa/6p0
>>395
教官が乗り出して一緒にやらないか?ってパターンじゃないと
誰も研究してないような分野は容認してくれなくね?
教官の専門と若干分野が違うけどこんな研究流行ってるからやってみたいってのはあるけど

399 :名無しさん@お腹いっぱい。:2009/01/06(火) 18:56:16 ID:6KTFMcOL0
>>396
サンクス 物理学科でしたので、
線積分、ベクトル解析、フーリエなど工学部でやる数学は
大丈夫。 
むしろ、情報理論、ネットワークなどはまったく無知。
今は離散数学系と計算の理論(マイケル・シプサー)を読んでる。



400 :名無しさん@お腹いっぱい。:2009/01/07(水) 13:57:31 ID:zZKXNvdr0
量子計算の研究(理論)やってる人間なんだが,線形代数だけ分かっていれば
いきなり量子計算関係の教科書読んで大丈夫だと思うぞ.

Nielsen & Chuang の Quantum Computation and Quantum Information がまじおすすめ

深い知識の必要性を感じたら,その都度別のテキストにあたれ.

401 :名無しさん@お腹いっぱい。:2009/01/07(水) 20:27:26 ID:7wu8Ho3I0
日本語版だと3分冊になってるあれですね。
たしかに読みやすい。

402 :名無しさん@お腹いっぱい。:2009/01/08(木) 06:33:27 ID:JbN+PnER0
質問です
1.点数がnの完全2分木の高さhを厳密に求めよ。そのうえで、h=Θ(log(n))であることを示せ。
2.単純な無向グラフGを表現する隣接行列をAとする。また、A^k=(※)とする
※aの右下にij、右上に(k)
(1)A^2,A^3,...,A^iは何を表すか
(2)(aの右下にii、右上に(2))は何を表すか
(3)1/6Σ(aの右下にii、右上に(3)) は何を表すか。ただし、n=n(G)とする。

403 :402:2009/01/08(木) 06:34:02 ID:JbN+PnER0
できれば考え方等も教えていただけるとありがたいです。

404 :名無しさん@お腹いっぱい。:2009/01/11(日) 01:08:11 ID:sdzzxz5e0
ttp://www.senko-corp.co.jp/qcs/ja/
これってこの分野の研究に役に立ちますかね?
結構なお値段だが、販売時期が2000年だし、もっといいのが
あるかな。

405 :名無しさん@お腹いっぱい。:2009/01/11(日) 20:43:19 ID:5hWRU5jd0
量子計算の研究なら使うんじゃないの?
専門じゃないからそれ以上はわからん。

406 :名無しさん@お腹いっぱい。:2009/01/12(月) 07:19:22 ID:ikXe1nwQ0
グラフアルゴリズムと計算量の理論やってるいい先生居ませんか?
大学院でグラフアルゴリズムか計算量の理論をを研究したいのですが。
自分が見落としてるいい先生が居るかもしれないので皆さんの意見が聞きたいです。
(国内、国外どちらでもいいです)

407 :名無しさん@お腹いっぱい。:2009/01/13(火) 01:12:27 ID:A5rQlbCL0
久保さんかな?

408 :406:2009/01/13(火) 14:54:22 ID:41cZyW450
>>407
久保さんとは?

409 :名無しさん@お腹いっぱい。:2009/01/13(火) 15:51:11 ID:43Z8us760
久保 グラフ アルゴリズム で検索したら?

410 :名無しさん@お腹いっぱい。:2009/03/06(金) 05:02:52 ID:5Q9ZI9Y70
鳥取市の誘致企業リコーマイクロエレクトロニクスにアルバイトに行っていた。
勤務態度不良でリコーのアルバイトをクビ同然で辞めた。

その後、鳥取市のテスコという工場に勤め真面目に働いていた。
「真面目に働いているのはリコーに対する報復(あてつけ?)」という噂でテスコをクビになった。
直後、テスコの社長から雇用保険の書類をとりに来るよう泣きそうな声で電話があった。
噂は嘘だと知ったのだろう。

雇用保険の手続きのため職安に行った。
職安の次長と相談すると、口止めをされた。
職安と会社は連絡を取り合っていたらしい。

しかし噂は狭い鳥取市である程度広がっているようだ。

リコーマイクロエレクトロニクスに電話を掛けた。
「君はうちのような一流企業が組織ぐるみでやったとでも思っているのかね?」
「そんなことはありませんけど」
「じゃあ会社には関係ないじゃないか」

しかし公的機関(職安)も巻き込んだ組織ぐるみの人権侵害の揉み消しである。

411 :名無しさん@お腹いっぱい。:2009/03/08(日) 19:39:24 ID:Nvjg9WlS0
http://tsushima.2ch.net/test/read.cgi/korea/1231728434/781

412 :名無しさん@お腹いっぱい。:2009/03/18(水) 13:48:00 ID:/Btmg1e60
http://oshiete1.goo.ne.jp/qa1438342.html
P=NPで検索したらウィキペディアの次、つまり二つ目にこれがヒットしたんですが

一番上の回答番号5に書いてあることってあってます?NP困難とNP完全を混同してませんか?
NP困難はNPである必要はないのでNP困難が全部解けるとは思えないのですが

413 :名無しさん@お腹いっぱい。:2009/03/18(水) 18:48:25 ID:qDLr8VbU0
>>412
混同してると思いますよ。
NP困難をNP完全に置き換えたら正しい文章になると思います。

ただ、P=NPだったら、判定問題のためのアルゴリズムを繰り返し使うことで、多項式時間でとけるNP困難問題もかなりありそうですが。

414 :名無しさん@お腹いっぱい。:2009/03/19(木) 11:09:50 ID:xByYQRje0
>>413
そうですよね!安心しました、ありがとうございます

415 :名無しさん@お腹いっぱい。:2009/05/09(土) 14:12:50 ID:V8nn9+J/O
テスト

416 :名無しさん@お腹いっぱい。:2009/05/16(土) 19:08:10 ID:9l2Fp2PT0
オイラー法による近似計算
x(t+h)=x(t)+h*dx/dt(t)
による誤差は、xに関してhの周りでテーラー展開した第2項までの計算なのでo(h^2)

というのは理解できるのですが、その場合の区間hの値を大きく取ると誤差がそのオーダーに
乗らなくなってくるのは何故でしょうか?よろしくおねがいします。

417 :名無しさん@お腹いっぱい。:2009/05/16(土) 19:16:48 ID:9l2Fp2PT0
数学板に書くつもりが…orz

418 :名無しさん@お腹いっぱい。:2009/06/01(月) 20:42:36 ID:jdp/7X+S0
どなたかアルファベットの出現頻度の求め方を教えていただけないでしょうか?

419 :名無しさん@お腹いっぱい。:2009/06/01(月) 21:18:47 ID:l05H4UK/0
Aが10回出てきたら10

420 :名無しさん@お腹いっぱい。:2009/06/02(火) 08:31:08 ID:bOGnJ/e00
チラシの裏に正の字。

421 :名無しさん@お腹いっぱい。:2009/06/02(火) 09:50:01 ID:z2woBqtR0
or/and-簡略化ってどうやって証明すればいいんですか?
例えば、or-簡略化だと
E1∨(E1∧E2) = E1
(E1∨E1)∧(E1∨E2) = E1
(E1)∧(E1∨E2) = E1
E1∧(E1∨E2) = E1
と、and-簡略化になってしまいます。
and-簡略化は同様にor-簡略化になってしまいます。
真理値表で確かめるしか手がないとか言わないですよね?


422 :名無しさん@お腹いっぱい。:2009/06/02(火) 12:53:51 ID:TaaAbFPi0
そんな名前ははじめてきいたが、吸収律で調べれば?
ブール代数で、andの単位元を1とすると、
E1∨(E1∧E2) = (E1∧1)∨(E1∧E2) = E1∧(1∨E2) = E1∧1 = E1


423 :名無しさん@お腹いっぱい。:2009/06/02(火) 13:52:48 ID:u0We9ESK0
>>421
公理は証明するものではないんだが。

424 :名無しさん@お腹いっぱい。:2009/06/02(火) 15:10:19 ID:TaaAbFPi0
何をブール代数の公理とするかは、定義しだい。

425 :名無しさん@お腹いっぱい。:2009/06/02(火) 16:12:02 ID:u0We9ESK0
>>424
http://mathworld.wolfram.com/BooleanAlgebra.html
にある定義が一般的だと思うが。では他に一般的な定義を挙げてくれ。

426 :名無しさん@お腹いっぱい。:2009/06/02(火) 17:04:20 ID:TaaAbFPi0
http://www.akita-nct.ac.jp/~yamamoto/lecture/2003/5M_Exp/lecture_5M_Exp/logic_circuit/node3.html

427 :名無しさん@お腹いっぱい。:2009/06/02(火) 19:19:21 ID:LVGn5FG60
Term Rewriting Systemさわってみたいんですが
具体的なソフトウェアで有名なのって何がありますか?
適当にterm rewriting system downloadなんかでググっても
具体的なソフトウェアに行き当たりません・・
あと、無料で試せるものが良いです

428 :名無しさん@お腹いっぱい。:2009/06/02(火) 21:52:51 ID:7x/nimnh0
http://en.wikipedia.org/wiki/Rewriting のSee alsoにある
Pure とか Q とか Maude とか Tom とかはどんなぐあい?

429 :名無しさん@お腹いっぱい。:2009/06/02(火) 23:08:52 ID:LVGn5FG60
>>428 ざっと試してみました
PureはQの発展ぽいのでQを試してみたが、HaskellやOCamlをさわってるような気分でした
equational programming languageらしいサンプルプログラムがすぐには見つからなかったので
普通の関数型言語との違いがさしてわからず、期待はずれな感じ。言語自体はcoolだと思う
楽曲の自動生成とか、そっち用の環境も最初から付属

Tomはこれを試すためにだけJavaを入れるのは嫌なので断念
サンプルプログラムのファイルとユーザーズガイドをざっと見した感じ
既存のJavaやC上にTomの構文を構築するため、
サンプルプログラムが冗長でTomによる拡張部分がわかりにくく
ちょっと触るという目的にはちょっと大変
言語自体には、あまりセンスを感じない

Maudeはすごく面白そうなんですが
Windows版バイナリなんて提供されてないので
関連するツールをソースからコンパイル
本家にあるWindows用のコンパイルドキュメントは既に古くなっており
それを参考にしてコンパイルを進めたがエラーで挫折

特に、高階書き換え系のシミュレーションが出来る言語や環境があると
嬉しいんですが・・手軽に触れそうなものは意外とないですね

430 :421:2009/06/04(木) 08:34:47 ID:5JT2KmQr0
>>422
単位元というのすら知らなかったです。
ありがとうございました!

>>423
証明してから使うものではないんですか?

431 :名無しさん@お腹いっぱい。:2009/06/04(木) 09:43:30 ID:BUWMagKN0
定理は証明するもの。
公理は信じるもの。

432 :平衡3進法:2009/06/14(日) 16:20:57 ID:PL63ixph0
情報板の方々に質問があります。
現行では何故、計算機は2進法
なのですか??   
3進法では不都合なんですか? 
或いは「平衡三進法」というのが
ありますが、これが2進法と大体
同じだからなのですか?? 

433 :名無しさん@お腹いっぱい。:2009/06/14(日) 17:36:04 ID:n6LUCwnl0
平衡三進法とは関係なく、(LSI ICの中の)トランジスタに電気の流れる状態として、
3つの状態をうまいこと割り付けて、計算させるのが難しいからです。

フラッシュメモリで、4状態を利用するものが出てきているように、必ずしも、全てを
2進でやらなければいけないわけではありません。
ただ、3進の場合、既存の2進ベースのソフトやハードとのインタフェースが面倒なので
3進をあえて使うのは相当特殊な場合に限られると思います。

434 :平衡3進法:2009/06/14(日) 18:20:27 ID:PL63ixph0
お答え下さり、ありがとうございました。
実は自分でも調べたのですが、疑問点
が山のように出てきたので、新規に
スレッドを立てました。 
3進法コンピュータは現実には実現できない
ようですが、それは現代科学技術の
制約のためで、絶対的に不可能では
ないようですね・・・・・

435 :名無しさん@お腹いっぱい。:2009/06/17(水) 09:27:56 ID:HKjHDy/L0
質問です。
Prove that from p⇒(r⇒s) follows r⇒(p⇒s).

まず、これは
From p⇒(r⇒s) infer r⇒(p⇒s)
という意味でしょうか?
そうだと仮定して解いてみますと

From p⇒(r⇒s) infer r⇒(p⇒s)
1 p⇒(r⇒s) pr1
2 From r infer p⇒s
2.1 r pr1
2.2 From p infer s
2.2.1 p pr1
2.3 s ⇒-E, 2.2, 2.2.1
2.4 p⇒s ⇒-I, 2.2.1, 2.3
2.5 r⇒s ⇒-I, 2.1, 2.3
3 p⇒(r⇒s) ⇒-I, 2.2.1, 2.5

ここまでやってみたんですが、
ここまで合っているのかも分からず、
これからどうしていいのかも分かりません。
2.3の時点でp, r, sの三つとも真であるという「仮定」になってしまってます。
もし、その仮定が本当に正しいならば
(T⇒(T⇒T)) ⇒ (T⇒(T⇒T))
T ⇒ T
T
という結論になりますが、そんな解き方でいいんでしょうか?
天才な方、教えてください。

436 :435:2009/06/18(木) 07:52:31 ID:qBYuo8MN0
やはり、ここではダメですか( ´,_ゝ`)プッ
他で訊いてみます

437 :名無しさん@お腹いっぱい。:2009/06/18(木) 09:54:44 ID:Q3/jWftc0
質問者が煽ったら出る回答も出ない

438 :名無しさん@お腹いっぱい。:2009/06/29(月) 19:46:33 ID:HSG2FbrQ0
質問させてください
odコマンドでファイルのサイズを調べるのと何故そうなるかという課題が出たのですが見方が分かりません

od -tdC ファイル名.txt
0000000 116 101 116 116 116 116 101 101 101 101 101 101 101
0000020 101 101 101 101
0000024
と出ました

分かる方教えてください

439 :名無しさん@お腹いっぱい。:2009/06/29(月) 20:03:04 ID:uFUZpAMO0
想像すらできんの?
いろんなファイルodしまくってみたら?
あと出力とか省略するなよ。


440 :名無しさん@お腹いっぱい。:2009/06/30(火) 01:15:33 ID:uc+g1q+q0
スレ違いだろ。UNIX板行けよ

441 :名無しさん@お腹いっぱい。:2009/07/22(水) 17:51:43 ID:BsaZJCR+0
オートマトンの質問です。
((0+ε)1)*を受理するεNFAに変換するって問題です。
正則表現の中のεをどう捉えるのかわからないので困っています。
分かる方よろしく願いします。


442 :名無しさん@お腹いっぱい。:2009/07/22(水) 18:01:33 ID:QuHDJqOx0
εが何かってのはわかってるの?
あと、+ってのは|の意味?


443 :名無しさん@お腹いっぱい。:2009/07/22(水) 18:28:52 ID:BsaZJCR+0
イプシロンは「無し」ですか?
+は一回以上繰り返しだと思っているのですが、
それだと説明がつかないような気がしています。

444 :名無しさん@お腹いっぱい。:2009/07/22(水) 18:32:01 ID:QuHDJqOx0
正規表現の記法なんてローカルルールがいっぱいあるんで、
授業や本で最初に示された記法の「定義」を探してよく理解すべき。
特に「説明がつかない」とわかってるんなら。

445 :名無しさん@お腹いっぱい。:2009/07/22(水) 18:45:39 ID:BsaZJCR+0
では、ローカルルールの中でも一般的な解釈でイプシロンを解釈したらどのようになりますか?


446 :名無しさん@お腹いっぱい。:2009/07/22(水) 19:47:05 ID:QuHDJqOx0
教科書くらい自分でひっぱり出して読めよ。

447 :名無しさん@お腹いっぱい。:2009/07/29(水) 19:58:05 ID:azyw2OYE0
1.{a,b,c}上の言語L={cxc|x∈{ab,ba}*}を表現する正規表現を与えよ
2.Lを生成する自由文脈文法を与えよ
3.L*を生成する有言オートマトンを与えよ

3は図になるので、1.2だけでもお願いします。

448 :名無しさん@お腹いっぱい。:2009/07/29(水) 19:59:13 ID:azyw2OYE0
有言→有限 でした

449 :名無しさん@お腹いっぱい。:2009/07/29(水) 23:41:19 ID:V3AEDDuA0
{ab,ba}*って何?
L*って何?
丸投げじゃなく自分はどこまで考えた?

450 :名無しさん@お腹いっぱい。:2009/07/31(金) 02:44:46 ID:6pOqBAk80
決定性有限オートマトンをM = (Q,Σ, δ, q0, F)と書く。ここで、 Qは状態の有限集合、Σ は有限
の入力アルファベット、δ : Q × Σ → Qは状態遷移関数 q0は初期状態、Fは受理状態の集合とす
る。M によって受理される言語をL(M)と書く。このとき、次の問いに答えよ。

(1) Σ? ? L(M) = {w ∈ Σ? | w ∈ L(M)} は正則言語であることを証明せよ。
(2) 決定性有限オートマトンM = (Q,Σ, δ, q0, F)が入力として与えられるとき、L(M)= ? となっ
 ているかどうかを判定するアルゴリズムを与え、その正当性について議論せよ
(3) 2 つの決定性有限オートマトンM1 = (Q1,Σ, δ1, q1, F1) とM2 = (Q2,Σ, δ2, q2, F2)が入力とし
 て与えられるとき、L(M1) ⊆ L(M2)となっているかを判定するアルゴリズムは存在するか。
 存在するとするならば、そのアルゴリズムの概要を示せ。存在しないとするならば、そのことを証明せよ。

問1は自明だと思うのですが、どのような書き方をすればよいのでしょうか?
問2、3は手がつきません。よろしくお願いします。

451 :名無しさん@お腹いっぱい。:2009/08/02(日) 04:26:53 ID:ByHq+BXp0
>>450
北大か?その科目あきらめろよwwww

452 :名無しさん@お腹いっぱい。:2009/08/02(日) 21:35:51 ID:QVJan+Oz0
>450
1と2は?になっていて読めないので無視して(3)のヒントだけ。
正規言語は和集合、積集合、否定をとっても正規言語。あとはベン図を書いて考える。

推測すると、(2)がL(M)=空集合の判定可能性で、それが(3)の誘導。

453 :名無しさん@お腹いっぱい。:2009/08/02(日) 22:59:05 ID:JZ9Iu+eZ0
1をもつときは必ず2こ連続している記号列を表す正規表現を書け。(例001101100110)
これわかる方います?

454 :名無しさん@お腹いっぱい。:2009/08/02(日) 23:36:50 ID:ByHq+BXp0
σ⇒0σ
σ⇒11σ

<11|0>*



455 :名無しさん@お腹いっぱい。:2009/08/03(月) 00:38:15 ID:n9Fcw6yS0
文脈自由言語が連接に関して閉じている。すなわち、L1とL2がともに文脈自由言語なら、L1L2も文脈自由言語であることを証明せよ。
証明の仕方が全くわかりません。よろしくお願いします。

456 :名無しさん@お腹いっぱい。:2009/08/03(月) 11:11:19 ID:Eyqxo+hA0
Maximaを使ってやるのですが、わからない問題があるので、教えてください。
・自然数nが与えられたとき、n以下の双子素数の組の個数を求める関数を作れ。
また、827以下の双子素数の組の個数を求めよ。
・自然数nが与えられたとき、n番目の素数を求める関数を作れ。
また、1000番目の素数を求めよ。
の2問です。
お願いします。

457 :名無しさん@お腹いっぱい。:2009/08/05(水) 01:38:33 ID:3dSH9Buz0
大きい数じゃなければエラトステネスの篩で素数一覧つくっとけばいいだけじゃね?

458 :名無しさん@お腹いっぱい。:2009/08/10(月) 15:00:44 ID:/zYez4IA0
非決定性オートマトンを決定性にするには?
非決定性オートマトンを考える利点は?

この2点、どなたか教えてください。

459 :名無しさん@お腹いっぱい。:2009/08/11(火) 00:11:38 ID:Y6HZ6Wat0
以下の3つは等価です
(1)任意のNFAに対して等価なDFAが存在する
(2)任意のDFAに対して等価な正規文法が存在する
(3)正規文法が存在するなら等価なNFAが存在する


NFAはそれと等価なDFAよりも普通は簡単に構成できます。
NFAよりも普通はDFAの方が状態数が多いです。
ですから普通ある言語を受理するDFAをつくる場合は
その言語を受理する文法を構成してそこからNFAを構成して
そのNFAをDFAに変換する手法をつかいます。
この手法には簡単なアルゴリズムがあります。


460 :名無しさん@お腹いっぱい。:2009/08/15(土) 16:30:57 ID:wTSz2vrB0
>>459
ありがとうございます。アルゴリズム探してみます。

461 :名無しさん@お腹いっぱい。:2009/08/20(木) 03:12:42 ID:p8Xsqtj+0
入力として決定性有限オートマトンMが与えられたとき、L(M)=φかどうかを判定するアルゴリズムを述べて説明せよ
入力として決定性有限オートマトンMが与えられたとき、L(M)=Σ*かどうかを判定するアルゴリズムを述べて説明せよ

この2題についてどなたか教えてください

462 :名無しさん@お腹いっぱい。:2009/08/20(木) 08:36:19 ID:sF17E6vw0
問題の意味については理解してる?

463 :名無しさん@お腹いっぱい。:2009/08/20(木) 15:38:39 ID:p8Xsqtj+0
受理する言語が全くないことを判定
あらゆる言語が受理されることを判定

ですよね?

464 :名無しさん@お腹いっぱい。:2009/08/26(水) 14:59:45 ID:q/x4CZRw0
整数部8ビット(符号含む),小数部8ビットの2の補数表示で
0110 0111.1000 0100が表す10進数って-24.484375であってるんでしょうか?

また,16ビットの2進浮動小数点表現(符号部1ビット,指数部4ビットゲタ履き8,仮数部8ビット)で
0 1111 1111 0001が表す10進数は(1+241/256)*2^7=248.5であってますか?

465 :名無しさん@お腹いっぱい。:2009/08/26(水) 15:07:59 ID:oWq1UrUE0
>>464
符号が0なのになぜ負?

情報不足。全部で13ビットしかないのはなぜ?
仮数の整数は含んでるのか?指数が全部1の例外はないのか?


466 :名無しさん@お腹いっぱい。:2009/08/26(水) 15:25:38 ID:q/x4CZRw0
あ,補数表示で符号ビットが0って事は実際は正数って事ですか?
(0110 0111.1000 0100)_2→(1001 1000.0111 1100)_2=24.484375
補数表現の補数表現で符号を読んでしまったのが間違いでしょうか

浮動小数点表示は16ビットではなく問題上でも13ビットまでで表現されてました,すいません
指数が全て1の時の例外はないようです。仮数部は整数を含まずそのまま計算するようです。IEEE754と混同していた・・・
なので120.5が正解でしょうか。


467 :名無しさん@お腹いっぱい。:2009/08/26(水) 15:59:18 ID:oWq1UrUE0
>>466
> =24.484375
ちがう。符号0ならいじらない。

> 仮数部は整数を含まずそのまま計算
なんか矛盾してて意味不明。


468 :名無しさん@お腹いっぱい。:2009/08/26(水) 16:15:58 ID:q/x4CZRw0
>ちがう。符号0ならいじらない。
あ,そうでした。

>仮数部
すいません,質問の意味がよく分かっていませんでした。
ただ,問題中に特に注釈はないので,
指数→15-8=7,基数2と考え
0.1111 0001の7ビットシフト=120.5と導いたのですが。

469 :名無しさん@お腹いっぱい。:2009/08/26(水) 17:20:43 ID:oWq1UrUE0
>>468
> 0.1111 0001の7ビットシフト
なのか、
1.1111 0001の7ビットシフト
なのか、
1.111 0001の7ビットシフト
なのか、それ以外なのか、前提がどうなってるかはこっちにはわからんので、
ちゃんと確認するしかない。



470 :名無しさん@お腹いっぱい。:2009/08/26(水) 17:30:36 ID:q/x4CZRw0
>>469
なるほど,では問題に不備があるようですね。
出題者に確認してみます。

471 :名無しさん@お腹いっぱい。:2009/10/13(火) 03:55:19 ID:MBibZ6cG0
 
3値論理は解釈の統一が不可能であり
2値論理だけが完全な体系である
 
と聞いたのだがコレはどう言う事か
 
  
3値論理では第3の真理値の形式化に
各研究者の主観が入り込むという話だが
 
コレは実際に3値論理回路を組むと
自己矛盾から動作不能という事なのか
 
 
 
・・・・・もし3値論理が2値論理に比較して
不完全なら3値論理回路の実現は
工学的に出来ないハズだと思うが・・・・・ 
 



472 :名無しさん@お腹いっぱい。:2009/10/13(火) 15:16:36 ID:tEwdCDoW0
ゲーデルの完全性定理の意味で、完全とか不完全とか言ってるのかな?
論理学は専門でないので、三値論理は不完全になる、という証明があるのか
どうかは知らないが。

論理回路は3値だろうが10値だろうが、物理状態をあてはめて、論理演算に
対応する演算装置にぶち込めばいいわけで、工学的にはなんの問題もない。

どういうわけで、論理が不完全なら工学的に不可能と思うのかな?

473 :名無しさん@お腹いっぱい。:2009/10/13(火) 22:27:06 ID:MBibZ6cG0
論理が不完全なら物理的にも
自己矛盾が起こって作動しないかと
思い込んだら〜いのち〜がけ〜  
 

474 :名無しさん@お腹いっぱい。:2009/10/13(火) 23:13:56 ID:v7I6f3HE0
マルチには回答つかないよ

475 :名無しさん@お腹いっぱい。:2009/10/19(月) 09:15:56 ID:HgJg22MA0
Σ={0, 1}上の語を2進数表現とみなすとき、
2の冪乗の2進数表現の全体 -> 10*
4の冪乗の2進数表現の全体 -> 1(00)*
8の冪乗の2進数表現の全体 -> 1(000)*
...
とそれぞれ正規表現で表すことができますが、
「xの冪乗」のxが2の冪数以外のときにこのように
正規表現で表せる場合は存在するのでしょうか?

とりあえずx=3や5で小さい方から20個くらい冪数を
列挙してそれらを受理する有限オートマトンを
作ろうとしたのですが、出来ませんでした。そこで
不可能であることを証明することに方針を変えたの
ですが、そちらもまだ出来ないでおります。
どなたか証明のヒントを教えていただけないでしょうか。
どうぞよろしくお願いします。


476 :名無しさん@お腹いっぱい。:2009/10/19(月) 21:22:51 ID:Z+W1gEgzO
ε動作をもつ非決定性有限オートマトンのε動作を除去したいのですが、手法がわかりません。どうやったら除去できるのでしょうか?

477 :名無しさん@お腹いっぱい。:2009/10/19(月) 23:04:28 ID:cYVKHWwK0
オートマトンの教科書ならどれにでも載ってるかと思うけど
http://en.wikipedia.org/wiki/Powerset_construction

478 :名無しさん@お腹いっぱい。:2009/10/19(月) 23:24:32 ID:Z+W1gEgzO
>>477
教科書読んでもわからなかったので…

479 :名無しさん@お腹いっぱい。:2009/10/26(月) 12:34:12 ID:c9eAOeHz0
ハードウェアの遅延分岐の話で、
DEC
 IF,RF,EX,MEM,WB
LD
   IF,RF,EX,MEM,WB
JPM
    IF,RE,EX,MEM,WB
分岐命令
                IF,RE,EX,MEM,WB

という図があるのですが、REって何の略なんでしょうか?
RFはregister fetchだと思うのですが、REは良く分かりません。


480 :名無しさん@お腹いっぱい。:2009/10/26(月) 18:27:06 ID:c/NdL0hj0
Register Examinationかなぁ。
その図を書いた人にきくのが確実と思うけど。

481 :名無しさん@お腹いっぱい。:2009/10/26(月) 22:08:52 ID:nU+N97gD0
誤植じゃね?

482 :名無しさん@お腹いっぱい。:2009/10/27(火) 04:49:13 ID:T9AzT8Eu0
>>480
わかりました。
ありがとうございます。

483 :名無しさん@お腹いっぱい。:2009/11/05(木) 09:57:05 ID:rbaF3JwK0
将来、SEではないIT系に就きたいのですが、
この分野はどういった仕事分野に向いていますか?

484 :名無しさん@お腹いっぱい。:2009/11/08(日) 22:48:53 ID:/fdhjuKH0
2テープTuring機械についての質問です。
2テープTuring機械の状態遷移関数を
δ(s,a,b) = (s',a',b',□) とする。 sは状態、a,bは入力。□は、L,R,Sの
いずれかでそれぞれヘッドを左に動かす、右に動かす、動かさない、の意。
ここで、Sのない2テープTuring機械は、2つのヘッドの距離が常に偶になると
いう制限があるが、実際にはSのある2テープTuring機械と能力が変わらない。
Sのない2テープTuring機械でSのある2テープTuring機械をシミュレートする
方法を与えよ。
講義中に教授が考えてみてくださいと言った問題ですが、よくわかりません。
ご存じの方、教えていただけないでしょうか?

485 :名無しさん@お腹いっぱい。:2009/11/16(月) 06:12:08 ID:2c4Wj2ov0
情報工学と通信工学はどちらが歴史的に先行しているのですか?
情報工学の方が基礎的なら情報工学の方が通信工学よりも先?
計算機科学あっての情報通信だから情報の方が古いのでは?
歴史的には通信工学の方が古いって言う話もあるようですが・・・・・

486 :名無しさん@お腹いっぱい。:2009/11/16(月) 11:45:29 ID:LPu/AELN0
情報の概念がはっきりする前に、電信とか無線とかの実用化があったので、
歴史的には通信工学のほうが古い。

シャノンによる情報の形式的な定義も、通信の用語で説明されてる。

487 :名無しさん@お腹いっぱい。:2009/11/16(月) 18:04:19 ID:2c4Wj2ov0
>486 
レスありがとうです。 情報の方が新しいのですね 
それなら、情報よりも通信の方が御飯が食べられますね
より基礎的な分野ほど社会では必要ですから
極端な話、お米を作れば餓死しない・・・・・
情報通信工学に進む場合には通信の方が穴場というか
情報工学はものすごく頭が良くないと出来ないという
話を聞くので・・・・・東大京大の数学を解いた事も無い
お馬鹿な自分では正直に言えば情報工学は無理かと

488 :名無しさん@お腹いっぱい。:2009/11/17(火) 12:13:49 ID:+nrAxs3o0
高校生の進路相談だったのかな?

> ものすごく頭が良くないと出来ない

そんなことはないと思うけどね。

苦手という意識があるなら、通信も計算機もどちらにも、電磁気の方程式やら
半導体の特性やら、物理学バリバリの分野もあれば、数学バリバリの分野も
あるので、気をつけたほうがよい。そのどちらもほとんど使わない分野もある。

東大京大東工大の計算機関係は競争率がすごいけど、そこらの大学の
計算機関係ならわりと穴場のところもあるよ。東大京大東工大と対等と
見られるレベルの研究をしてる教授がいるところとかあるので。
ハズレもあるが。

489 :名無しさん@お腹いっぱい。:2009/11/17(火) 19:44:27 ID:s3ztTOFw0
 >488   レスありがとう。 数学はかなり得意ですが
その数学でさえ客観的には大して出来ません。 
個人的に得意なだけで・・・・・むしろ物理が全く・・・・・
だから数学系で行きたいのですが理学部数学科
は社会の役に立たず就職が無いので除外すると
したら残るは工学部の情報通信系かナ、と。 
大学はとりあえず東工大は無理なので中堅国立か
最悪、滑り止めで山形大や職業大にしようかと
確実合格を目指して3流大に進学したらヤバイかな
私立大学の工学部は学費が高杉だから行きません

490 :名無しさん@お腹いっぱい。:2009/11/17(火) 20:38:08 ID:bO2eYLjb0
一つ言えることは消極的な理由で進学しても
4年経っても基本のきすら危ういレベルにしかなれないってことだな
ソースはオレ

491 :名無しさん@お腹いっぱい。:2009/11/23(月) 03:49:06 ID:EffOjD2s0
シンプソン係数について教えてください。
この係数は比較するものの値の差が大きければ、関連性がなくとも高い値がでてしまうとのことですが、
具体的にこの「差」というものはどの程度の差を指すのかはっきりとしません。
100倍違うとまずいのか1000倍までは比較的良いのか等、良く機能するためのある程度の目安を経験則でも良いので、教えていただけないでしょうか。
よろしくお願いします。

492 :名無しさん@お腹いっぱい。:2009/11/23(月) 11:40:52 ID:RxSXP3Tz0
 
国敗れてマニュフェストあり。。。orz 

===============================================================================
【2009年:日本の液晶産業が韓国に追い抜かれていた理由】(日経)
http://jbpress.ismedia.jp/articles/-/2160
  誰もが予想していなかった。国産のゼロ戦液晶は敗北していた。
  技術で負けたのではない、韓国のエンタープライズプラットフォーム戦略に敗北したのだ…

【2009年:海自に衝撃・中国海軍の実力】(東洋経済)
http://jbpress.ismedia.jp/articles/-/1598

  3月14日、中国に遅れること3ヶ月。ソマリア沖の作戦海域に到着した
 海上自衛隊護衛艦くらま艦長海江田一佐は愕然とした。「もしかして、我々は負けているのか?」…
-------------------------------------------------------------------------------

蓮紡女史@人民裁判のお陰で、ごらんの有様だよ。


日本の電機が韓国勢に完敗した理由
http://business.nikkeibp.co.jp/article/world/20091109/209298/

シャープ、中国企業に亀山の第6世代液晶パネル生産設備を売却へ・・・生産技術も提供
http://unkar.jp/read/tsushima.2ch.net/newsplus/1251754672
 

493 :名無しさん@お腹いっぱい。:2009/11/23(月) 18:31:57 ID:3iUD4w1b0
>>492 巣に帰れゴミ

494 :名無しさん@お腹いっぱい。:2009/12/03(木) 16:01:46 ID:OisjDKDR0
初めて書き込みます、よろしくお願いします。

重み付き集合充填問題(weighted set packing:WSP)について
勉強したいのですが、
詳しい定義や、代表的な解法アルゴリズムなどが記載されている、
英語か日本語の書籍などご紹介いただけないでしょうか、よろしくお願いします。

495 :名無しさん@お腹いっぱい。:2009/12/08(火) 17:05:25 ID:WP1Vi6gf0
ぐぐったかね。

496 :名無しさん@お腹いっぱい。:2010/01/10(日) 02:34:44 ID:LYFf3Hul0
対象につけられた非数量の<属性,値>ペアを用いて
対象間の関係とかそういうのを分析する研究ってありませんか?
例えば次の各食べ物
リンゴ <色,赤い>,<大きさ,大きい>
イチゴ <色,赤い>,<大きさ,ちいさい>
ミカン <色,黄色い>,<大きさ,大きい>
トマト <色,赤い>,<大きさ,ちいさい>
というような<属性,値>ペアがつけられていたら
リンゴに一番近いのはトマトである、みたいな分類を行うようなイメージで。

特に商業的な応用の研究があったらお願いします

497 :名無しさん@お腹いっぱい。:2010/01/10(日) 19:01:50 ID:KjfxY76u0
いくらでもあるが?

498 :名無しさん@お腹いっぱい。:2010/01/11(月) 01:02:31 ID:tDXZu4Om0
>>497
卒論に参考論文として載せたいので
具体的に教えてもらえませんか?

499 :名無しさん@お腹いっぱい。:2010/01/11(月) 13:07:05 ID:09o5SZb20
命令コード 6450
IXRの内容 ????
EA 02A0


????がわかりません
この前は計算できたけどさっぱり仕方忘れました
お願いします

500 :名無しさん@お腹いっぱい。:2010/01/13(水) 01:18:33 ID:O1vqORHs0
>工学に分類されることがらについては別スレッドへ、
>プログラミングについてはプログラム技術板へどうぞ。
>ただし、境界上の話題は歓迎します。

これ以外にけいさんきかがくがあるのかよw




501 :名無しさん@お腹いっぱい。:2010/01/13(水) 20:38:27 ID:JxK6mXB30
しつも〜ん。
なぜ雑誌bitは廃刊になったんですか?
どうしてみんな昔からみると夢のような凄い計算機でエクセルとワードとメールと2chしかしないんですか?


502 :名無しさん@お腹いっぱい。:2010/01/14(木) 16:18:21 ID:k/k45Rev0
som_pakを用いたデータの学習をしています。
既存データから学習したマップの生成まではいけたのですが、そこから新しいデータを追入力してマップに反映させる方法が分かりません。
生成されたマップデータを元に再度学習を回せばいいんでしょうか?
どうかこの追学習の方法について教えてくださいお願いします。

503 :名無しさん@お腹いっぱい。:2010/02/03(水) 22:39:59 ID:F6dTZfqJ0
http://ja.wikipedia.org/wiki/Cray-1
質問です。クレイ1って、どのくらいの性能なんですか?
あの、たとえば、CPUが何ギガヘルツとか、物理メモリーが何メガバイトとか、
ハードディスクが何テラバイトとかという、普通の人間にも分かるような数字で
お願いします。




504 :名無しさん@お腹いっぱい。:2010/02/03(水) 22:51:22 ID:9DC8RzW70
80MHz
2命令/サイクル
160MFLOPS(理論値)
RAM 8MB


505 :名無しさん@お腹いっぱい。:2010/02/04(木) 15:35:26 ID:OQxz55jY0
画像処理について質問があります。

http://www.gifu-nct.ac.jp/elec/yamada/iwata/filter/index.html

このようにフィルタをかける処理を行いたいのですが、
上記URLだとフィルタの中心が注目画素の中心にくるようにせよとあるのですが、
注目画素が境界部分(端、上記URLだとf(0,0)、f(5,0)などの部分)のときに、
フィルタリングを行う場合はどのようにすればよいのでしょうか?

よろしくお願いします。


506 :503:2010/02/04(木) 21:54:02 ID:XcOKCpnZ0
ありがとうございます。なんとなくわかりましした。

507 :名無しさん@お腹いっぱい。:2010/02/04(木) 23:59:33 ID:OV2HSy5Y0
>>505
やることによるだろうけど、
外側を黒とか白とか灰色に固定して考えるとか、
外周の画素値がそのまま外側に延々と延びてるとみなすとか、
いろいろじゃね?


508 :名無しさん@お腹いっぱい。:2010/02/07(日) 03:24:17 ID:22RCYOM00
>>507
レスありがとうございます。
ラプラシアンフィルターをかけたいのですが、
プログラムを組む前に境界部位はどう処理をすれば良いのかわからず迷っています。
一般的には、外側を黒とか白とか灰色に固定して考える、外周の画素値がそのまま外側に延々と延びてるとみなしているのでしょうか?

509 :名無しさん@お腹いっぱい。:2010/02/08(月) 15:22:46 ID:BJwnvVnV0
ギブソンミックスの計算の公式を教えてください

510 :名無しさん@お腹いっぱい。:2010/02/09(火) 00:34:48 ID:vTWKaFs80
e-mc2

511 :名無しさん@お腹いっぱい。:2010/02/09(火) 13:07:03 ID:XiL8pvMP0
ここに比率が出てる
ttp://www.roylongbottom.org.uk/cpumix.htm

512 :名無しさん@お腹いっぱい。:2010/03/07(日) 17:26:06 ID:M+vOfXnh0
計算機科学と航空宇宙工学はどちらの方が格上ですか?

513 :名無しさん@お腹いっぱい。:2010/03/08(月) 02:24:44 ID:KeOsJaPI0
実務に携われてるなら、航空宇宙工学のほうが尊敬するな。
座学ならどっちでもいいし、実務での計算機科学のほうが座学での航空宇宙工学よりもえらい気がする

514 :名無しさん@お腹いっぱい。:2010/03/14(日) 02:54:40 ID:a8ECQLY10
スパイ養成機関・朝鮮総連に無許可で突撃してみた。
朝鮮総連に不利なものが映っている為か何度も削除されているので皆さんお早めにご覧ください。
多くの日本人拉致被害者を返さない北朝鮮に怒りの鉄槌を!
http://www.nicovideo.jp/watch/sm9987419
http://www.nicovideo.jp/watch/sm9987542
http://www.nicovideo.jp/watch/sm9987731
http://www.nicovideo.jp/watch/sm9987783
http://www.nicovideo.jp/watch/sm9999806
http://www.nicovideo.jp/watch/sm10000115
http://www.nicovideo.jp/watch/sm9974521
http://www.nicovideo.jp/watch/sm9974590
(youtube編)
http://www.youtube.com/watch?v=OJjb-Hozk1E
http://www.youtube.com/watch?v=w13PL2T3Oi8
http://www.youtube.com/watch?v=vm-qwbqtxN0
http://www.youtube.com/watch?v=R9479yht3x8
http://www.youtube.com/watch?v=Jonm2SGmu2Y
http://www.youtube.com/watch?v=y52UEKLoanM
http://www.youtube.com/watch?v=3FPGfqjacQg

515 :名無しさん@お腹いっぱい。:2010/03/16(火) 18:42:25 ID:Q9BmcVZ60
で、それのどこが計算機科学の質問なのかなアフォウヨ君?

516 :名無しさん@お腹いっぱい。:2010/04/21(水) 10:05:18 ID:4ipygpmC0
遺伝的アルゴリズム
http://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

ここに書かれてる定義長の段で
δ(H)=4ってあるけどこれ3じゃないの?

517 :名無しさん@お腹いっぱい。:2010/04/21(水) 10:48:27 ID:+IgOxY5x0
3だね。直しておいたら?

518 :名無しさん@お腹いっぱい。:2010/04/21(水) 11:01:53 ID:4ipygpmC0
専門じゃないしおそれおおい

519 :名無しさん@お腹いっぱい。:2010/04/22(木) 01:10:49 ID:o81RLCJN0
香ばしいやつがいるから見てみて

http://science6.2ch.net/test/read.cgi/infosys/1268413943/

520 :名無しさん@お腹いっぱい。:2010/04/28(水) 19:15:41 ID:7PiE6Vk70
物理演算について質問です。

物理なので当然実数を扱うと思うんですが
コンピュータ上では実数も有限桁で扱うからその誤差をどうやるのかと思ってちょっと調べたのですが
いろいろ工夫の方法はあるが結局どんな工夫をしても多少の誤差は残る、みたいな感じだったんですが、
つまり現代存在するどんなすごい物理シミュレーション機械も絶対どこかに小さい誤差はあるってことなんでしょうか?
それともピッタリ一致させる技術があるんでしょうか?
よろしくお願いします。

521 :名無しさん@お腹いっぱい。:2010/04/28(水) 19:53:07 ID:tM/cD9ZD0
コンピュータ以外では無限桁を扱えるとでも?

522 :名無しさん@お腹いっぱい。:2010/04/29(木) 09:30:21 ID:3byjUDsF0
正確な演算をする技術はないではない。数式処理とか有理数演算とか多倍長演算とか。
ただ、当然ながらπとかeとかの三角関数とかの計算はできないか、もしも
全く同じ数を比較したら永遠に終わらないか、などで、限界がある。

523 :名無しさん@お腹いっぱい。:2010/04/30(金) 02:31:20 ID:qStTViGP0
まぁ誤差のでる計算をすれば誤差はでるわな

524 :名無しさん@お腹いっぱい。:2010/05/10(月) 07:00:12 ID:ZAKJwZ690
Slide35 gif
http://www19.atpages.jp/imagelinkget/get.php?t=v&u=www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/InfoMath/2005/note/7/Slide35.gif
Turingbombebletchleypark 2
http://kumikomi.typepad.jp/jogai/images/2009/03/31/turingbombebletchleypark_2.jpg
logo png
http://brainfuck.sourceforge.net/logo.png


525 :名無しさん@お腹いっぱい。:2010/05/15(土) 01:53:04 ID:1sOTbT9j0
数学では空手踊り,物理学ではシュレディンガー音頭なるものがあるそうですが
計算機科学ではどのような踊りがあるのでしょうか?

526 :名無しさん@お腹いっぱい。:2010/05/15(土) 12:22:50 ID:Qp8e+1Sk0
アルゴリズムたいそう

527 :525:2010/05/15(土) 19:42:19 ID:1sOTbT9j0
>>526
ありがとうござます
大変勉強になりました

528 :名無しさん@お腹いっぱい。:2010/05/17(月) 06:50:37 ID:HxuWRo3q0
Slide35 gif
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/InfoMath/2005/note/7/Slide35.gif
Turingbombebletchleypark 2
http://www19.atpages.jp/imagelinkget/get.php?t=v&u=kumikomi.typepad.jp/jogai/images/2009/03/31/turingbombebletchleypark_2.jpg
logo png
http://brainfuck.sourceforge.net/logo.png


529 :名無しさん@お腹いっぱい。:2010/05/19(水) 20:10:36 ID:3A+q5fNz0
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/InfoMath/2005/note/7/Slide35.gif
http://www19.atpages.jp/imagelinkget/get.php?t=v&u=brainfuck.sourceforge.net/logo.png


530 :名無しさん@お腹いっぱい。:2010/05/20(木) 01:50:09 ID:5OTbTltn0
http://www19.atpages.jp/imagelinkget/get.php?t=v&u=www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/InfoMath/2005/note/7/Slide35.gif
http://brainfuck.sourceforge.net/logo.png


531 :名無しさん@お腹いっぱい。:2010/06/30(水) 22:29:05 ID:EqsVvvxW0
最内簡約が停止するようなλ式で、簡約順によっては簡約が止まらないものはありますか?

179 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)