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

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

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

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

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

　　　　　　　　２　ゲ　ッ　ト

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

Hopcroft&Ullmanとか Introduction to Algorithms とか。

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

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

パーマン。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>14

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

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

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

>>19
-120, 543

ありがとうございます！

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

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

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

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

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

回文（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", □, -, ＞, →)

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

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

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

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

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

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

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

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

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

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

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

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

宿題は自分でやること。

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

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

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

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

>>34

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

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

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

ま、ここでもいいけど。

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

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

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

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

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

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

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

ヘネパタ嫁

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
これじゃダメか？
浮動小数点でググって一番上にあるんだが。

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

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

さあ？

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

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

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

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

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

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

あげ

うん

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

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

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

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

ｵﾅﾇｰねたあります

>>58
宿題は自分でやれ

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

に載ってる

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

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

>>62
ﾃｲﾗｰ展開

間違えた。ｽﾏｿ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>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
＞答え一発
ぜひ元ネタ通り6桁であってほしかったと思う。どうでもいいけど。

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

ここは過疎板なんだな。

過疎板・・・。

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

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

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

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

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

mod(26^61, 437) = 292

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

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

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

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

>>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では動作しているようだけど、こんなんでいいのかな。

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

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

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

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

>>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でなければならない、ということに着目すると、暗算で解けたかも。

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

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


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

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

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


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

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

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

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

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


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

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

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


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

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

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

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

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

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

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

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

>94
意味が分からない。

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

>>94-96
どうもです。


wikiの定義の意味が

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

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

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

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

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


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

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

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

のようなものを考えると

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

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

おねがいします。

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

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

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

>>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で答えているものではないかもしれないが、
問題を解決する過程を全て決定問題にすることができる問題は、
非決定性チューリングマシンで解くことのできる決定問題と見なす事ができるかどうかということです。

おねがいします。

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

>>108
宿題は自分でやれ

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

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

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

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

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

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

お助けください

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

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

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

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

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

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

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

辞書ひけ

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

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

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

>>120

俺だったら、

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

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


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

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

合ってるよ

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

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

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

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

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

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

ってのを思いついた。

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

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

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

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

助けてください

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

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

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

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

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

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

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

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

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

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

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

猛者の方教えて下さい。

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

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

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

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

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

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

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

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

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

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

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

16進への変換

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

>>149
別に

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

た

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

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

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

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

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

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

ノーベル何賞よ

平和賞

欽ドン賞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

面白い結果が出てこないのは、計算機科学者の能力が試されてるんじゃないの？

教えてください。次の言語はチューリング完全ですか？

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

よろしくお願いします。

すいません。考えてみたら出力サイズが大きかったらだめですね。
計算可能な決定問題は全て解けるか？にしてください。

たびたびすいません。
printf等で標準出力にいくらでもデータを出せるとすれば、チューリング完全か？という問題にできますね。
やっぱりチューリング完全かどうかにしてください。

直接関係ないかもしれないけど、無限にメモリが使えるっていうのは、
ポインタが固定長であるCの仕様と相容れない気がする

すいませんが、そこらへんは題意を汲み取ってうまいこと定義してください。
よろしくお願いします。

スタックポインタだけ任意の整数を格納できる、とすれば大丈夫でしょうか？

入力のROMについても任意のアドレスにアクセスできる必要がありますね。
うーん。困った。なかなか厳密な定義ができない。

入力のROMについても任意のアドレスにアクセスできる必要がありますね。
うーん。困った。なかなか厳密な定義ができない。

２重に書き込んでしまいました。
すいません。

ポインタやintのサイズは入力のROMのサイズに依存し、ROMの任意のアドレスをアクセスするのに必要十分な大きさがある。
一度の関数呼び出しでスタックに乗せられるメモリのサイズはO(1)個のポインタやintの変数である。
でどうでしょう。

チラシにまとめてから整理してまたおいで

誤り確率を持つデジタル回路で作られた電子計算機は、
チューリングマシンを越えている要素がある。

プログラミング言語間で記述能力の優劣を判定する明示的な方法とかは
あるのでしょうか？

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

記述能力という言葉で、何を指しているのかが分からない。

>>215
言語間で表現できる機能自体が違うものは置いておいて、
通常のアプリケーションが実装できる（一般帰納関数を取り扱い可能な）
異なる言語の間で、仕様の決まっているソフトウェアを実装するのに
必要な実装作業量 みたいな物に対して

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

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

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

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

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

そんなんだったら、組み込み関数等の数とか、ライブラリの量とか次第じゃないの？

確かに、そう言われてしまうと少し困る気もしますが・・

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

見た目のコードの量には、ライブラリは効いてくるんじゃないの？

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

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

たいがいの言語は記述「能力」的に同等かと。
記述「効率」の話をしたいんだろうけど、
もうちょっとつっこんで定義しないと議論にならないんじゃない？
コンパイラを作るにしてもyaccとかjavaccを使って
構文解析を楽するなんていうのはライブラリの話でしょ。

>>216
つ Kolmogorov Complexity

結局のところ、チョムスキー階層で言語の仕様記述を行うのに

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

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

>>218
Henry F. Ledgard, "The Little Book of Object-Oriented Programming", Prentice-Hall, 1996
〔Henry F. Ledgard, 神林 靖訳, 「オブジェクト指向プログラミングの考え方」, 翔泳社, 1997〕．
でやってるみたいに、いくつかのクラスの言語を定義して、その記述能力を比較するってのが
順当なのかなぁ？

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

「自己記述能力」の高さを比較するとか？
これだと簡素な言語であるほど有利になってしまいますが。

>>213
どういう意味で超えているんですか？

計算速度

そういうのは超えているとは言わないんじゃ・・・

一方で指数時間かかる計算を他方で多項式時間で計算できるなら超えてるといえるだろう。

確率的チューリングマシンの概念さえ知らないの？

知ってるよ

なるほどつまりハミルトン閉路求解アルゴリズムで解決できるはずじゃ

>>231
んなわけねーだろ

計算可能関数について質問ですけど、
計算可能関数とは、アルゴリズムと同値であるため、
有限時間内に手続きが終了する保証のあるもので無ければならず、

例えば、

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

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

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

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

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

>>233
計算可能の意味を勘違いしてるっぽい。
そもそも「数式や手続きが計算可能」なんて用語がそもそも間違いで、
Aを計算する（有限の）数式や（有限の）手続きが存在するとき、Aは計算可能であるという。

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

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

ごめん、数式があるだけで計算可能ってのはまずい。
それは忘れてください。

>>234
つまり何処をどう勘違いしているのですか？

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

正しい解を得られる確率がゼロ以上だったら、それは立派な手続きじゃないの？
やっぱり確率的チューリングマシンの概念さえ知らない人ばかりなのか？

>>236
たとえば、挙げている式Σ(1/(2^k))はそもそも関数でないよね？
もし、任意の入力に対しΣ(1/(2^k))を出力する関数という意味なら、それは計算可能。
あるいは入力nに対してΣ_k=0^n(1/(2^k))を計算する関数という意味でも、それは計算可能。

>237
お前、確率的チューリングマシンのこと何も知らないだろ
適当なこと言ってんなよ

>>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を出力する。

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

俺の説明が分かりにくくてすまない。
そもそも``手続きが計算可能''ってのが間違いだと言いたいんだ。

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

>>234
＞Aを計算する（有限の）数式や（有限の）手続きが存在するとき、Aは計算可能であるという。
ここは役に立ちました。

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

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

>>241
でも私が示した手続き(関数)は有限個に収まる保証が無いため、
計算可能関数ではなくてOKですよね。

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

>>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
これ関数じゃないの？
数学的には無限に時間を与えられれば解を返すため、関数と言って問題無いと個人的には思いますよ。
有限時間内に終了しなければならないのは計算可能関数のことだと思いますが・・・。

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

別に関数は有限時間内に計算結果が出る必要はないよ。
もちろん、計算不可能関数ってものもあるから。
ただ、>>244の後半のものを関数の形に直すには、>>238と考えるしかないし、
そうすると、その関数は計算可能になってしまいます。

>247
>244のは関数というより、ただの数

>>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を出力する。

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

>>249
＞>244のは関数というより、ただの数
何故でしょうか？
それを数と言えるなら、
あらゆる数を返す手続きは関数では数ということになるのでは？

>>250
いえ、たとえ一つでもAを計算する有限の手続きが存在すれば、Aは計算可能です。
「この手続きに沿う」というように手続きを固定するのは無意味です。

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

>>252
＞手続きが計算可能だの計算不可能だのというものは無いんだ。

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

計算可能関数は、それを計算する（有限の）手続きが存在するもの。
計算不可能関数は、それを計算する（有限の）手続きが存在しないもの。
断じて、手続きが計算不可能だとかそういうものではないよ。

>>254
つまり計算可能関数及び計算不可能関数は問題の分別のための名前であり、手続きではないのですね。

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

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

初めに自分の読み取った定義を記しておくべきだったかもしれない。

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

>>255
計算可能関数＝アルゴリズム（が存在する）は本当。
fが関数とは、(∀x)(∃!y)(f(x)=y)を満たすもの。
(∀x,y)(f(x)=y⇔g(x)=y)なら外延性公理よりf=g.
たとえば、>>244の2種類は、別の定義を用いているが同値性を証明できる。
よって、計算可能関数＝アルゴリズムと考えてもOK。

>>256
f が計算可能関数とは、有限の x に対して有限時間で f(x) を求められるようなものだよ。

>>258
＞求められるようなものだよ。

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

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

関数のことです。

>>260
まず>>257に挙がっている定義を見ると、
＞計算可能関数＝アルゴリズム（が存在する）は本当。
つまり計算可能関数はアルゴリズムが存在する問題ということですよね。

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


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

>>261
失礼しました、>>258は定義域が自然数全体の場合の話です。

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

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

>>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を出力する。

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



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

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

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

>>256 の定義は正しい間違っている以前に定義になってないように思うが

>>264
何故でしょうか？

もうそろそろ寝たいから。
もう一つ質問しておき太鼓とを今のうちに書いておきます。


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

お前らいつまでやってんだよw
計算可能関数の定義は>262で大体合ってるぞ

>>263
なんか噛みあわないと思ってたら、手続きって言葉の使い方がちょっと違ってたみたい。
すまん、俺は　手続き＝アルゴリズム　として言葉を使ってた。
あと、計算可能関数の定義は>>262で正しいはずなので確認してください。

>>266
NP困難ならNPである必要はないよ。

>>269
NPでなくてもいいけど、FNPであるかどうかです。

FNPでなくてもいい

>>265
数学でいう「定義」と思った場合にだけど、
まず「問題」の定義がされていないのでどうやっても読めない。
とりあえず勝手に標準的な定義を採用するとしても、
問題の「大きさ」とは何かが示されていないのでやっぱり読めない。

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

>>271
もしもソースがあったら晒して欲しい。

>>242
David Deutsch くらいは知ろうよ

>>272
それじゃあ問題の定義を、「チューリングマシン上で解法を実行することが可能なもの」とでも書いておきましょう。

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

>>274
どうせなら Bernstein & Vazirani もよろしく…。
"Quantum Complexity Theory", SIAM Journal on Computing, Vol.26, No.5, pp.1411-1473, Oct 1997

>>274
どうせなら Bernstein & Vazirani もよろしく…。
"Quantum Complexity Theory", SIAM Journal on Computing, Vol.26, No.5, pp.1411-1473, Oct 1997

>>274
David Deutsch のブラックボックスの話？

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

>>278
ShorのアルゴリズムはZQP。

>>279
ZQPとは何でしょうか？

>>275
> それじゃあ問題の定義を、「チューリングマシン上で解法を実行することが可能なもの」とでも書いておきましょう。
じゃあ、「解法」って何？という話になるんじゃないかと。

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

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

ねえみんないったいなに難しい話してんの？
アタシ全然わかんなーい
そんなことより一緒に確率的チューリングマシンの話でもしよ

>>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'が存在する。）

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

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

>>283

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

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

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

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

>>281
＞じゃあ、「解法」って何？という話になるんじゃないかと。
数学で、問題を解く手順。

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

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

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

>>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を出力する。

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

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

に訂正。

チューリングマシンの等価性って、最近の初学者はスルーするんですか？

>>284
＞それ、Deutch が証明してるし。
これホントに？はじめて聞いた。

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

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


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

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

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


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

>>289
アルゴリズムには有限時間内で終了する保証がなければならないと、私の大学の助教授が言ってました。
数学板の住人の方もそう仰っていました。

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

人によって「アルゴリズム」という言葉の意味を
1. 手続きと同義。プログラミング言語でいう関数。厳密にはチューリングマシン
2. ある問題を「正しく」「有限時間で」解く手続きのこと
のどっちで使っているかが違う
>>289は1.の意味で使ってるし、
「計算可能な関数とは、アルゴリズムが存在する関数のこと」というのは2.の意味で言ってる

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

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

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

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

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

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

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

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

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


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

＞＞それとも、『ある n に対し、n step 以内に停止している確率が 1 であるチューリングマシンをアルゴリズムと呼び、それ以外のものはアルゴリズムと呼ばない。』って定義してた？

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

ミスった。正確には

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

>>295
横からつっこむけど，Turing機械Mはある入力xを受理しない場合は無限ループに突入しても問題ないはず。

>>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自体は関数でないし、したがって計算可能関数かどうか論じることもできない。

>>296
いやいや、必ず停止するアルゴリズムをご所望みたいだからこう定義しなきゃだめだろ
Turing認識可能ってことを考えると無限ループも許すけど

>>293-295
大学の助教授は有限時間内に停止する保証がなければアルゴリズムではないと明言していたよ。


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

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

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

そもそも、問題が計算可能って言うかな？

>>233 >>299
通りすがり＆斜め読みだけど

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

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

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

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

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

まぁそれ以前にまず>>233のコインの表という乱数発生がどういうアルゴリズムかが問題な気がする
コインの表などという表現を使っているから、あたかも現実の事の様に考えてしまうが、
あくまでアルゴリズムである以上、その乱数発生にもなんらかのアルゴリズムがあるわけでそれを加味しないことには停止性うんぬんは考えられないと思うんだけど・・・

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

>>302
通常の確率変数だと思えばよくないかな。
各試行は独立で、それぞれ 1/2 の確立で表か裏の値を取る、とする。

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

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

>>303
ひとつめ ×確立 ○確率
恥ずかしい

パチンコスレで遠隔、ホルコン、サクラ、マネーロンダリングなどについて書き込むと渋谷マルハン社員やマルハンに依頼された
ネット工作会社がスレ荒らしをしてスレが機能停止します。
↓↓工作員の荒らしのやり方↓↓
2008/01/10(木)ID:iA54n BU50
■■■■マルハン総合スレッド ９■■■■http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→87021165/783-784
【宮崎県都城市】パチ事情その�Ahttp://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→87189246/658-659
【山と川】宮崎県児湯付近PART１【自然ｲﾊﾟｰｲ】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
■■■■マルハン総合スレッド ９■■■■http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→87021165/809-810
【香川】パーラーグランドのスレ２【徳島】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→88315438/324
【延岡】宮崎県北情報PART3【日向】http://money6.2ch.net/test/read.cgi/pachij/11←左右くっつけて→96865970/186

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

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

ID:Wg8L3vhD0=ID:9L6NJM130=ID:bxae2L3H0さんは、
一から計算理論の勉強をし直したほうがいいと思います。

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

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

（´・ω・`）ｼｮﾎﾞｰﾝ

>>303
だからその”各試行は独立で、それぞれ 1/2 の確立で表か裏の値を取る、とする。”をどう実現するかが重要なのでは？
普通計算可能性といえば、ある条件を満たす数を計算できるかどうかで、この場合はようは表が出る事があるかどうかの判定となるわけだけど
結局その表が出るかどうかはその乱数生成のアルゴリズムに深く依存するわけでしょ？

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

実装できなきゃだめっていうなら、非決定性TMやオラクルTMも認めないってスタンス？

>>308
TMの定義のどこかに確率変数を入れないと、
”各試行は独立で、それぞれ 1/2 の確立で表か裏の値を取る、とする。”
なんて振る舞いは情報量的に実現できないよ。
アルゴリズムの前後でエントロピーが増えちゃってるからね。
だから、>>303みたいに定義するのが普通。

ポンピング補題の質問はここでいい？

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

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

あげてみる

s=xyzで
yが1を含む場合
yが0^kの場合
に分けて考えれば？

>>313
Lを正規言語と仮定
s=10^p10^p1とするこのときs=xyzと三分割できる

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

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

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

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

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

ぜんぜんわかってねぇな

>>315
どこかいけないのかﾜｶﾝﾈ　ｋｗｓｋお願いします

たとえば
> yが1を含むとき　|xy|>pよりポンピング補題の条件を満たさず矛盾する
なんでだよ。
ポンピング補題の条件っていうのを自分なりに解釈して人に説明できるか？

>>317
持ってるテキストにポンピング補題の3条件として
Lが正規言語ならばある定数ｐが存在して、少なくとも長さがpであるような任意のs∈Lはs = xyzと分割できて、
1　全てのi>=0でxy^iz∈L
2　|y|>0
3　|xy|<=p

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

そりゃ定理そのものだろ。理解できてるのか？
理解できてるなら、なんで
> yが1を含むとき　|xy|>p
だ？

>>319
yが1を含む場合をs = 10^p10^p1でy = 0^p1とおいたら

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

|xy|>pじゃないの？

「s=10^p10^p1」のpと「少なくとも長さがp...|xy|<=p」のpとは違う。

>>321
y =0^k1　としたとき
xyyz = x0^k10^k1zはx0^k10^k1がxyzと等しいためxyyz not∈L
これじゃだめ？
他の分割もxyyzのときを考えればいけそう。

> xyyz = x0^k10^k1zはx0^k10^k1がxyzと等しいためxyyz not∈L
さっぱりだめ。「等しいとLの要素でない」理由がない。

>>323
訳ﾜｶﾝﾈ　とりあえず飛ばして先に進めてみる。よければ証明例を教えて。

通りすがりです

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

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

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

仮想記憶にいおいて、主記憶ＲＡＭの読み書きに１００ﾅﾉsec、ハードディスクの１ページ分の読み書きに100ﾏｲｸﾛsecを要する。
プロセッサから参照されたデータが主記憶にある確率が80％で、
主記憶のフレーム上に余裕が無い確率が８０％であった場合、
参照所要時間の期待値を有効数字3桁で求めよ。

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

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

コピペを改変する手間を惜しむなよｗ

2次元で、円、矩形、あるいは楕円が別の楕円に内包されているかどうかを知るにはどうすればいいですか？

すれ違いならスマソ。

内包する楕円とその内部を不等式で表現して
（x**2/a + y**2/b ≦ r)
矩形なら、全ての頂点がこの不等式を満たすなら内包されている。

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

円についても不等式立てて連立させて
解なしの範囲がなければ内包されている

計算機的にできたかな？

すごく・・・　キモいです・・・
http://jp.youtube.com/watch?v=ZiRgYBHoAoU

おいら数学屋なんですが、
よくプログラミングが定理の証明とみなせるといわれるのはいかなる意味においてなのでしょうか？
知ってる人がいたら是非教えてください。

UNIXのwriteがシステムコール、fwriteがライブラリコールであることをどのようにしたら示せるでしょうか？

>>335
マニュアルを探して、2章に書いてあったらシステムコール、3章ならライブラリコール。
と覚えておけば実用上問題はない。

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

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

>>336
わかりました！ありがとうございますｍ（＿＿）ｍ

>>334
Curry-Howard のことかな
それとも program extraction のことかな

>>338
どうも有難うございます。
早速調べてみます。

ｵﾏｴﾗ何低次元な話してるんだ。
>>334
オイラ情報屋。工学修士、博士単位取得退学。学生当時専門は超並列計算。
現在は技術屋、興味方向は暗号学。「守る」のが仕事なんでね。

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

http://www.tohoku.ac.jp/japanese/news/2008/07-09.htm
11/12 サイバーサイエンスセンターのＳＸ−９がＨＰＣＣの１９項目で世界一　

2008年3月から稼働しておりますサイバーサイエンスセンターのスーパーコンピュータシステムSX-9が、HPC(高性能計算)分野でのベンチマークテストであるHPCチャレンジで28項目中19項目で世界最高速を達成いたしました(2008年10月24日現在）。
HPCチャレンジベンチマークは、米国政府の援助のもと、テネシー大学のJ.ドンガラ(J.Dongarra)博士を中心にHPC関係者が参画して策定されたものです。
世界のスーパコンピュータの性能ランキングTOP500で使用されているLinpack（リンパック）ベンチマークを補完し、スーパーコンピュータの性能を多面的な観点から評価します。
　今回のベンチマーク結果は、ＨＰＣチャレンジのベンチマークプログラムを東北大学サイバーサイエンスセンタースーパーコンピュータ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

質問じゃないなら来るな

オーダ記法についての質問をしてもよろしいでしょうか？
(1) (2n^2 + log^7(n) + 10)(√n + 10n^0.1 + 5logn) のオーダを見積もれ.
(2) √(n^2 + 100n) のオーダを見積もれ.
(3) 2^(n+1) = Ｏ(2^n) は正しいか. 理由とともに答えよ.
(4) 2^(2n) = Ｏ(2n) は正しいか. 理由とともに答えよ.
(5)Σ i = Θ(n^2) は正しいか. 理由とともに答えよ.
(6) n! = Ｏ(n^n) は正しいか. 理由とともに答えよ.
(7) n! = Ω(2^n) は正しいか. 理由とともに答えよ.

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

名前欄にsageと入れてしまいました。すみませんでした。。

>>343
Σiは式いっぱつだから桁数考慮してO(log n)とかだろうね
n!はスターリンの公式でいいなら、同様にO(1)か、桁数を考慮してO(log n)になるね。

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

>>345
オーダー記法はその関数を計算するための計算量を表してるんじゃねーぞ

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

ありがとうございます。
式が正しいか正しくないかを評価するというのはわかってきましたが、オーダの見積もり方がわかりません。。。

オメガとシータも出てきてるみたいだけど、とりあえず俺はオーダーだけ教えよう
オーダー記法の定義をまずしっかり理解しろ

「関数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）でもあると言える。
（これ、計算量でオーダーを理解してる人は知らない人が多い）

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

だから、オーダーを見積もれって言う質問に答えると

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

>>349
それを書くなら Ackermann 関数で書いたらかっこよくね？

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

>>350
オメガはΩ(1)ですって言っとけばええやん？
シータはどうしようもないがね

ユークリッド互除法の最悪計算量をLameの定理の結果を用いずに解析せよという問題なのですが、答えていただけないでしょうか？よろしくお願いします。
問題文がこれだけなので、解析の制度まではわかりません。

そらにある雲ができる仕組みというのは存在するんですよね？
それが形になる仕組みを科学的に、
めったに無いですが、動物の形に見えたりします、どうして形が特定の
ようなものになるか教えてください。
偶然になるでは答えではないですよね？
仕組みが存在するはずです。

形ができるのは偶然、その形が動物に見えるのはゲシュタルト心理学

ところで情報系や計算機系の学科は終焉してると聞くことがあるけど
ほんとなの?
現在、情報工学１年だけど不安だ。
他学科への転移も考えたほうがいいの?

文系卒程度の就職ならできるだろうから、無難に生きたいなら、そのままでいいんじゃない？

学科に頼って生きようしてるのなら医学部以外は終焉してると思った方がいいんじゃね。

Pred'で自然数Cn+1をβ簡約した時の過程を教えて。何度やってもCｎにならね。

単に Pred' とか言われても定義わかんなくね？

Pred' = λnsz.n(λgh.h(gs))(λu.z)(λu.u) だった

うち国立の情報だけど、生徒の半数以上が、最初「ブラウザ」って何？って状態だった。ビビッた。

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

>>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のいってるのは
情報＝PCってのは情報学科でてたらエクセルに詳しいとか思われちゃうってことかな？

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

ネットワークアドレス197.18.110.48/28の場合、
サブネットマスク、クラス、使用可能なサブネットワーク、
使用可能なホスト数、ブロードキャストアドレスを求めよ。

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

>>365,366
申し訳ないけど、今のほとんどの企業は、プログラミングだけが「すごい人」なんて必要としてないよ。
「すごい人」がいなきゃ作れないソフトウェアなんて、ほとんどないからねぇ。
平均＋αくらいのスキルで十分。つまり給料の安い中国人やインド人で十分。
それに、今は不況でプログラミングしかできない人は優先的にクビになってるよ。

>>367
IPアドレスでググって最初に出てきたページを穴があくまで読め

>>368
中国人やインド人を引き合いに出すのなら
一部のスーパーマンや既得権益を持ってる人を除いて
日本人はいらないということになるね。
日本人で且つ将来に不安を覚えるような身分に生まれたことを呪うしかない。

これマ板ネタだよな。

>>370
うーん。オフショアって言葉知ってる？
オフショアに移管できる仕事とできない仕事があるわけよ。
ソフトウェア開発は、オフショアに移管しやすい典型的な仕事だよね。
あと、サポート業務とか、人事とか経理もオフショアに移管され始めてるよね。
一方、オフショアにだせない、出さないほうが良い仕事もあるわけで、
日本人が日本で生きる限り、そういう分野に活躍の場を求めたほうが良いってこと。

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

>>368
プログラミング技術「だけ」みても、ね。
あと、プログラミング「だけ」がすごい人を必要としてないなら、想定してる企業が私らの間で違うんだわ。

マ板ネタですな。スマソ

>>371
オフショアだけを挙げているけれど
外国人労働者や移民も想定しておいた方がいいだろうし
根源的に日本企業である必要もないと考えると
日本人でなければならない仕事はほとんどないんじゃないか。

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

すみません、初めて質問します。

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

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

スレ違ってます。
以下にどうぞ

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

計算機科学系の学部のある大学院で、おすすめはがあったら是非教えてください。

東大
NAIST
JAIST

学部のある大学院って

理論計算機科学だったら東工大とか京大じゃね？

>>368
「ソフトウェア開発」　を、企業の社内システム開発＝SI　に限れば、
確かにそのとおり。

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

p≦2n+3なるnを持ってきて
xyz=10^n10^n1とします(yは空文字でない)

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

ポンピング自体の証明
Lは決定的オートマトンMで受理される
→pをMの状態数+1とおく
→p以上の長さのs∈Lはその受理走査の途中で同じMの状態aに二回であう
→一回目にaにならとこらから二回目になるところまでをyとすれば
そのyを任意回くりかえしても受理できる

プログラミングができませんが、計算理論はやれますかね？

やれると思うよ

計算理論というのは、ほぼ数学と考えてよいですか。
何かアイディア出したら、紙と鉛筆だけで修士論文書けるかな？

分野や内容による。
スパコンとかクラスタぶんまわして検証しなきゃかもしれんし。

>>385
計算理論は、数学。
ただ、数学だとしても、紙と鉛筆だけで修士論文かけるとは限らない

量子コンピュータ関係の修士論文にしたいのだが、
何かよいテーマあるかな？
量子コンピュータに関する調査論文だけでは、目新しいことや
工夫した点など盛り込めないし・・。
なにかヒントをください。

量子コンピュータの新しいアルゴリズムを提案すればおｋ。
NP完全問題を多項式時間で解く奴きぼん。

>>389
BQP⊆NPと思っている人って計算理論の専門家には，ほとんどいないんじゃないかな。
>>388
マジレスするが，こんなところではなく先生に相談汁。

【偽医療】AKA 関節運動学的ｱﾌﾟﾛｰﾁ【ｲﾝﾁｷ医療】
http://gimpo.2ch.net/test/read.cgi/body/1211885077/

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

【肩こり腰痛】日本関節運動学的ｱﾌﾟﾛｰﾁ(AKA)医学会
http://society6.2ch.net/test/read.cgi/hosp/1229493132/

修士で研究するには

Ａ　オートマトン　言語理論　計算論　１，２　（　Ｊ．ホップクロフト、Ｒ．モトワニ　Ｊ．ウルマン　著）
Ｂ　計算理論の基礎　（マイケルシプサー　著）
Ｃ　離散数学入門（守屋悦朗　著）
を習得したあと、量子コンピュータ、量子情報理論に関する書物を読んでいけばよいでしょうか。
ほかに数学的な準備というものは必要になりますでしょうか。

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

指導教員が量子コンピュータのことを知らなければ、
そんな修論の指導はできないので無理。
量子コンピュータのことをやっている研究室があるんなら、そこの教員にきけ。

教授の専門外なことを好き勝手ｵﾅﾆｰしていいのは卒論まで

つうことは、だれも研究してないような新しい分野は、修士論文じゃなくて卒業論文でってことだな。

>>392
マジレスすると、量子コンピュータやるなら、線積分やベクトル解析できないとダメじゃねぇの？
工学部のやる数学はひととおりおさえておく必要はあるはず。
あと、計算論方面では「アルゴリズム・デザイン」読んでおけ。

>>392
それっぽいのがあったから、一応張っとくわ。
http://www-imai.is.s.u-tokyo.ac.jp/~tokunaga/index-j.html

>>395
教官が乗り出して一緒にやらないか？ってパターンじゃないと
誰も研究してないような分野は容認してくれなくね？
教官の専門と若干分野が違うけどこんな研究流行ってるからやってみたいってのはあるけど

>>396
サンクス　物理学科でしたので、
線積分、ベクトル解析、フーリエなど工学部でやる数学は
大丈夫。　
むしろ、情報理論、ネットワークなどはまったく無知。
今は離散数学系と計算の理論（マイケル・シプサー）を読んでる。

量子計算の研究（理論）やってる人間なんだが，線形代数だけ分かっていれば
いきなり量子計算関係の教科書読んで大丈夫だと思うぞ．

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

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

日本語版だと３分冊になってるあれですね。
たしかに読みやすい。

質問です
１．点数がnの完全２分木の高さhを厳密に求めよ。そのうえで、h＝Θ(log(n))であることを示せ。
２．単純な無向グラフＧを表現する隣接行列をＡとする。また、Ａ^k＝(※)とする
※aの右下にij、右上に(k)
(1)A^2,A^3,...,A^iは何を表すか
(2)(aの右下にii、右上に(2))は何を表すか
(3)1/6Σ(aの右下にii、右上に(3)) は何を表すか。ただし、n=n(G)とする。

できれば考え方等も教えていただけるとありがたいです。

ttp://www.senko-corp.co.jp/qcs/ja/
これってこの分野の研究に役に立ちますかね？
結構なお値段だが、販売時期が２０００年だし、もっといいのが
あるかな。

量子計算の研究なら使うんじゃないの？
専門じゃないからそれ以上はわからん。

グラフアルゴリズムと計算量の理論やってるいい先生居ませんか？
大学院でグラフアルゴリズムか計算量の理論をを研究したいのですが。
自分が見落としてるいい先生が居るかもしれないので皆さんの意見が聞きたいです。
（国内、国外どちらでもいいです）

久保さんかな？

>>407
久保さんとは？

久保 グラフ アルゴリズム で検索したら？

鳥取市の誘致企業リコーマイクロエレクトロニクスにアルバイトに行っていた。
勤務態度不良でリコーのアルバイトをクビ同然で辞めた。

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

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

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

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

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

http://tsushima.2ch.net/test/read.cgi/korea/1231728434/781

http://oshiete1.goo.ne.jp/qa1438342.html
P=NPで検索したらウィキペディアの次、つまり二つ目にこれがヒットしたんですが

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

>>412
混同してると思いますよ。
NP困難をNP完全に置き換えたら正しい文章になると思います。

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

>>413
そうですよね！安心しました、ありがとうございます

テスト

オイラー法による近似計算
x(t+h)=x(t)+h*dx/dt(t)
による誤差は、xに関してhの周りでテーラー展開した第2項までの計算なのでo(h^2)

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

数学板に書くつもりが…orz

どなたかアルファベットの出現頻度の求め方を教えていただけないでしょうか？

Aが10回出てきたら10

チラシの裏に正の字。

or/and-簡略化ってどうやって証明すればいいんですか？
例えば、or-簡略化だと
E1∨(E1∧E2) = E1
(E1∨E1)∧(E1∨E2) = E1
(E1)∧(E1∨E2) = E1
E1∧(E1∨E2) = E1
と、and-簡略化になってしまいます。
and-簡略化は同様にor-簡略化になってしまいます。
真理値表で確かめるしか手がないとか言わないですよね？

そんな名前ははじめてきいたが、吸収律で調べれば？
ブール代数で、andの単位元を1とすると、
E1∨(E1∧E2) = (E1∧1)∨(E1∧E2) = E1∧(1∨E2) = E1∧1 = E1

>>421
公理は証明するものではないんだが。

何をブール代数の公理とするかは、定義しだい。

>>424
http://mathworld.wolfram.com/BooleanAlgebra.html
にある定義が一般的だと思うが。では他に一般的な定義を挙げてくれ。

http://www.akita-nct.ac.jp/~yamamoto/lecture/2003/5M_Exp/lecture_5M_Exp/logic_circuit/node3.html

Term Rewriting Systemさわってみたいんですが
具体的なソフトウェアで有名なのって何がありますか？
適当にterm rewriting system downloadなんかでググっても
具体的なソフトウェアに行き当たりません・・
あと、無料で試せるものが良いです

http://en.wikipedia.org/wiki/Rewriting のSee alsoにある
Pure とか Q とか Maude とか Tom とかはどんなぐあい？

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

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

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

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

>>422
単位元というのすら知らなかったです。
ありがとうございました！

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

定理は証明するもの。
公理は信じるもの。

情報板の方々に質問があります。
現行では何故、計算機は２進法
なのですか？？　　　
３進法では不都合なんですか？　
或いは「平衡三進法」というのが
ありますが、これが２進法と大体
同じだからなのですか？？　

平衡三進法とは関係なく、（LSI ICの中の）トランジスタに電気の流れる状態として、
3つの状態をうまいこと割り付けて、計算させるのが難しいからです。

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

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

質問です。
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
という結論になりますが、そんな解き方でいいんでしょうか？
天才な方、教えてください。

やはり、ここではダメですか（ ´,_ゝ｀）ﾌﾟｯ
他で訊いてみます

質問者が煽ったら出る回答も出ない

質問させてください
odコマンドでファイルのサイズを調べるのと何故そうなるかという課題が出たのですが見方が分かりません

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

分かる方教えてください

想像すらできんの？
いろんなファイルodしまくってみたら？
あと出力とか省略するなよ。

スレ違いだろ。UNIX板行けよ

オートマトンの質問です。
((0+ε)1)*を受理するεNFAに変換するって問題です。
正則表現の中のεをどう捉えるのかわからないので困っています。
分かる方よろしく願いします。

εが何かってのはわかってるの？
あと、+ってのは|の意味？

イプシロンは「無し」ですか？
+は一回以上繰り返しだと思っているのですが、
それだと説明がつかないような気がしています。

正規表現の記法なんてローカルルールがいっぱいあるんで、
授業や本で最初に示された記法の「定義」を探してよく理解すべき。
特に「説明がつかない」とわかってるんなら。

では、ローカルルールの中でも一般的な解釈でイプシロンを解釈したらどのようになりますか？

教科書くらい自分でひっぱり出して読めよ。

１．{a,b,c}上の言語L={cxc|x∈{ab,ba}＊}を表現する正規表現を与えよ
２．Lを生成する自由文脈文法を与えよ
３．L＊を生成する有言オートマトンを与えよ

３は図になるので、１．２だけでもお願いします。

有言→有限　でした

{ab,ba}＊って何？
L＊って何？
丸投げじゃなく自分はどこまで考えた？

決定性有限オートマトンを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)となっているかを判定するアルゴリズムは存在するか。
　存在するとするならば、そのアルゴリズムの概要を示せ。存在しないとするならば、そのことを証明せよ。

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

>>450
北大か？その科目あきらめろよｗｗｗｗ

>450
1と2は?になっていて読めないので無視して(3)のヒントだけ。
正規言語は和集合、積集合、否定をとっても正規言語。あとはベン図を書いて考える。

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

１をもつときは必ず２こ連続している記号列を表す正規表現を書け。（例001101100110）
これわかる方います？

σ⇒0σ
σ⇒11σ

＜１１｜０＞*

文脈自由言語が連接に関して閉じている。すなわち、Ｌ1とＬ2がともに文脈自由言語なら、Ｌ1Ｌ2も文脈自由言語であることを証明せよ。
証明の仕方が全くわかりません。よろしくお願いします。

Maximaを使ってやるのですが、わからない問題があるので、教えてください。
・自然数ｎが与えられたとき、ｎ以下の双子素数の組の個数を求める関数を作れ。
また、８２７以下の双子素数の組の個数を求めよ。
・自然数ｎが与えられたとき、ｎ番目の素数を求める関数を作れ。
また、１０００番目の素数を求めよ。
の２問です。
お願いします。

大きい数じゃなければエラトステネスの篩で素数一覧つくっとけばいいだけじゃね？

非決定性オートマトンを決定性にするには？
非決定性オートマトンを考える利点は？

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

以下の3つは等価です
（１）任意のNFAに対して等価なDFAが存在する
（２）任意のDFAに対して等価な正規文法が存在する
（３）正規文法が存在するなら等価なNFAが存在する


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

>>459
ありがとうございます。アルゴリズム探してみます。

入力として決定性有限オートマトンMが与えられたとき、L(M)=φかどうかを判定するアルゴリズムを述べて説明せよ
入力として決定性有限オートマトンMが与えられたとき、L(M)=Σ*かどうかを判定するアルゴリズムを述べて説明せよ

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

問題の意味については理解してる？

受理する言語が全くないことを判定
あらゆる言語が受理されることを判定

ですよね？

整数部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であってますか？

>>464
符号が0なのになぜ負？

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

あ，補数表示で符号ビットが0って事は実際は正数って事ですか？
(0110 0111.1000 0100)_2→(1001 1000.0111 1100)_2=24.484375
補数表現の補数表現で符号を読んでしまったのが間違いでしょうか

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

>>466
> =24.484375
ちがう。符号0ならいじらない。

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

＞ちがう。符号0ならいじらない。
あ，そうでした。

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

>>468
> 0.1111 0001の7ビットシフト
なのか、
1.1111 0001の7ビットシフト
なのか、
1.111 0001の7ビットシフト
なのか、それ以外なのか、前提がどうなってるかはこっちにはわからんので、
ちゃんと確認するしかない。

>>469
なるほど，では問題に不備があるようですね。
出題者に確認してみます。

　
３値論理は解釈の統一が不可能であり
２値論理だけが完全な体系である
　
と聞いたのだがコレはどう言う事か
　
　　
３値論理では第３の真理値の形式化に
各研究者の主観が入り込むという話だが
　
コレは実際に３値論理回路を組むと
自己矛盾から動作不能という事なのか
　
　
　
・・・・・もし３値論理が２値論理に比較して
不完全なら３値論理回路の実現は
工学的に出来ないハズだと思うが・・・・・　
　

ゲーデルの完全性定理の意味で、完全とか不完全とか言ってるのかな？
論理学は専門でないので、三値論理は不完全になる、という証明があるのか
どうかは知らないが。

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

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

論理が不完全なら物理的にも
自己矛盾が起こって作動しないかと
思い込んだら〜いのち〜がけ〜　　
　

マルチには回答つかないよ

Σ={0, 1}上の語を2進数表現とみなすとき、
2の冪乗の2進数表現の全体　->　10*
4の冪乗の2進数表現の全体　->　1(00)*
8の冪乗の2進数表現の全体　->　1(000)*
...
とそれぞれ正規表現で表すことができますが、
「xの冪乗」のxが2の冪数以外のときにこのように
正規表現で表せる場合は存在するのでしょうか?

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

ε動作をもつ非決定性有限オートマトンのε動作を除去したいのですが、手法がわかりません。どうやったら除去できるのでしょうか?

オートマトンの教科書ならどれにでも載ってるかと思うけど
http://en.wikipedia.org/wiki/Powerset_construction

>>477
教科書読んでもわからなかったので…

ハードウェアの遅延分岐の話で、
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は良く分かりません。

Register Examinationかなぁ。
その図を書いた人にきくのが確実と思うけど。

誤植じゃね？

>>480
わかりました。
ありがとうございます。

将来、SEではないIT系に就きたいのですが、
この分野はどういった仕事分野に向いていますか？

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

情報工学と通信工学はどちらが歴史的に先行しているのですか？
情報工学の方が基礎的なら情報工学の方が通信工学よりも先？
計算機科学あっての情報通信だから情報の方が古いのでは？
歴史的には通信工学の方が古いって言う話もあるようですが・・・・・

情報の概念がはっきりする前に、電信とか無線とかの実用化があったので、
歴史的には通信工学のほうが古い。

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

>486　
レスありがとうです。　情報の方が新しいのですね　
それなら、情報よりも通信の方が御飯が食べられますね
より基礎的な分野ほど社会では必要ですから
極端な話、お米を作れば餓死しない・・・・・
情報通信工学に進む場合には通信の方が穴場というか
情報工学はものすごく頭が良くないと出来ないという
話を聞くので・・・・・東大京大の数学を解いた事も無い
お馬鹿な自分では正直に言えば情報工学は無理かと

高校生の進路相談だったのかな？

> ものすごく頭が良くないと出来ない

そんなことはないと思うけどね。

苦手という意識があるなら、通信も計算機もどちらにも、電磁気の方程式やら
半導体の特性やら、物理学バリバリの分野もあれば、数学バリバリの分野も
あるので、気をつけたほうがよい。そのどちらもほとんど使わない分野もある。

東大京大東工大の計算機関係は競争率がすごいけど、そこらの大学の
計算機関係ならわりと穴場のところもあるよ。東大京大東工大と対等と
見られるレベルの研究をしてる教授がいるところとかあるので。
ハズレもあるが。

　>488　　　レスありがとう。　数学はかなり得意ですが
その数学でさえ客観的には大して出来ません。　
個人的に得意なだけで・・・・・むしろ物理が全く・・・・・
だから数学系で行きたいのですが理学部数学科
は社会の役に立たず就職が無いので除外すると
したら残るは工学部の情報通信系かナ、と。　
大学はとりあえず東工大は無理なので中堅国立か
最悪、滑り止めで山形大や職業大にしようかと
確実合格を目指して３流大に進学したらヤバイかな
私立大学の工学部は学費が高杉だから行きません

一つ言えることは消極的な理由で進学しても
4年経っても基本のきすら危ういレベルにしかなれないってことだな
ソースはオレ

シンプソン係数について教えてください。
この係数は比較するものの値の差が大きければ、関連性がなくとも高い値がでてしまうとのことですが、
具体的にこの「差」というものはどの程度の差を指すのかはっきりとしません。
100倍違うとまずいのか1000倍までは比較的良いのか等、良く機能するためのある程度の目安を経験則でも良いので、教えていただけないでしょうか。
よろしくお願いします。

　
国敗れてマニュフェストあり。。。ｏｒｚ　

===============================================================================
【2009年：日本の液晶産業が韓国に追い抜かれていた理由】（日経）
http://jbpress.ismedia.jp/articles/-/2160
　　誰もが予想していなかった。国産のゼロ戦液晶は敗北していた。
　　技術で負けたのではない、韓国のエンタープライズプラットフォーム戦略に敗北したのだ…

【2009年：海自に衝撃・中国海軍の実力】（東洋経済）
http://jbpress.ismedia.jp/articles/-/1598

　　３月１４日、中国に遅れること３ヶ月。ソマリア沖の作戦海域に到着した
　海上自衛隊護衛艦くらま艦長海江田一佐は愕然とした。「もしかして、我々は負けているのか？」…
-------------------------------------------------------------------------------

蓮紡女史＠人民裁判のお陰で、ごらんの有様だよ。


日本の電機が韓国勢に完敗した理由
http://business.nikkeibp.co.jp/article/world/20091109/209298/

シャープ、中国企業に亀山の第６世代液晶パネル生産設備を売却へ・・・生産技術も提供
http://unkar.jp/read/tsushima.2ch.net/newsplus/1251754672
　

>>492 巣に帰れゴミ

初めて書き込みます、よろしくお願いします。

重み付き集合充填問題（weighted set packing:WSP）について
勉強したいのですが、
詳しい定義や、代表的な解法アルゴリズムなどが記載されている、
英語か日本語の書籍などご紹介いただけないでしょうか、よろしくお願いします。

ぐぐったかね。

対象につけられた非数量の<属性,値>ペアを用いて
対象間の関係とかそういうのを分析する研究ってありませんか？
例えば次の各食べ物
リンゴ　<色,赤い>,<大きさ,大きい>
イチゴ　<色,赤い>,<大きさ,ちいさい>
ミカン　<色,黄色い>,<大きさ,大きい>
トマト　<色,赤い>,<大きさ,ちいさい>
というような<属性,値>ペアがつけられていたら
リンゴに一番近いのはトマトである、みたいな分類を行うようなイメージで。

特に商業的な応用の研究があったらお願いします

いくらでもあるが？

>>497
卒論に参考論文として載せたいので
具体的に教えてもらえませんか？

命令コード　6450
IXRの内容　????
EA 02A0


？？？？がわかりません
この前は計算できたけどさっぱり仕方忘れました
お願いします

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

これ以外にけいさんきかがくがあるのかよｗ

しつも〜ん。
なぜ雑誌bitは廃刊になったんですか？
どうしてみんな昔からみると夢のような凄い計算機でエクセルとワードとメールと2chしかしないんですか？

som_pakを用いたデータの学習をしています。
既存データから学習したマップの生成まではいけたのですが、そこから新しいデータを追入力してマップに反映させる方法が分かりません。
生成されたマップデータを元に再度学習を回せばいいんでしょうか？
どうかこの追学習の方法について教えてくださいお願いします。

http://ja.wikipedia.org/wiki/Cray-1
質問です。クレイ１って、どのくらいの性能なんですか？
あの、たとえば、ＣＰＵが何ギガヘルツとか、物理メモリーが何メガバイトとか、
ハードディスクが何テラバイトとかという、普通の人間にも分かるような数字で
お願いします。

80MHz
2命令/サイクル
160MFLOPS（理論値）
RAM 8MB

画像処理について質問があります。

http://www.gifu-nct.ac.jp/elec/yamada/iwata/filter/index.html

このようにフィルタをかける処理を行いたいのですが、
上記URLだとフィルタの中心が注目画素の中心にくるようにせよとあるのですが、
注目画素が境界部分（端、上記URLだとf(0,0)、f(5,0)などの部分）のときに、
フィルタリングを行う場合はどのようにすればよいのでしょうか？

よろしくお願いします。

ありがとうございます。なんとなくわかりましした。

>>505
やることによるだろうけど、
外側を黒とか白とか灰色に固定して考えるとか、
外周の画素値がそのまま外側に延々と延びてるとみなすとか、
いろいろじゃね？

>>507
レスありがとうございます。
ラプラシアンフィルターをかけたいのですが、
プログラムを組む前に境界部位はどう処理をすれば良いのかわからず迷っています。
一般的には、外側を黒とか白とか灰色に固定して考える、外周の画素値がそのまま外側に延々と延びてるとみなしているのでしょうか？

ギブソンミックスの計算の公式を教えてください

e-mc2

ここに比率が出てる
ttp://www.roylongbottom.org.uk/cpumix.htm

計算機科学と航空宇宙工学はどちらの方が格上ですか？

実務に携われてるなら、航空宇宙工学のほうが尊敬するな。
座学ならどっちでもいいし、実務での計算機科学のほうが座学での航空宇宙工学よりもえらい気がする

スパイ養成機関・朝鮮総連に無許可で突撃してみた。
朝鮮総連に不利なものが映っている為か何度も削除されているので皆さんお早めにご覧ください。
多くの日本人拉致被害者を返さない北朝鮮に怒りの鉄槌を!
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

で、それのどこが計算機科学の質問なのかなアフォウヨ君？

遺伝的アルゴリズム
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）＝４ってあるけどこれ３じゃないの？

3だね。直しておいたら？

専門じゃないしおそれおおい

香ばしいやつがいるから見てみて

http://science6.2ch.net/test/read.cgi/infosys/1268413943/

物理演算について質問です。

物理なので当然実数を扱うと思うんですが
コンピュータ上では実数も有限桁で扱うからその誤差をどうやるのかと思ってちょっと調べたのですが
いろいろ工夫の方法はあるが結局どんな工夫をしても多少の誤差は残る、みたいな感じだったんですが、
つまり現代存在するどんなすごい物理シミュレーション機械も絶対どこかに小さい誤差はあるってことなんでしょうか？
それともピッタリ一致させる技術があるんでしょうか？
よろしくお願いします。

コンピュータ以外では無限桁を扱えるとでも？

正確な演算をする技術はないではない。数式処理とか有理数演算とか多倍長演算とか。
ただ、当然ながらπとかeとかの三角関数とかの計算はできないか、もしも
全く同じ数を比較したら永遠に終わらないか、などで、限界がある。

まぁ誤差のでる計算をすれば誤差はでるわな

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

数学では空手踊り，物理学ではシュレディンガー音頭なるものがあるそうですが
計算機科学ではどのような踊りがあるのでしょうか？

アルゴリズムたいそう

>>526
ありがとうござます
大変勉強になりました

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

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

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

最内簡約が停止するようなλ式で、簡約順によっては簡約が止まらないものはありますか？

いくつかのバイナリデータがあって
そこからそれらに共通するデータのパターンを抽出するとか
データの類似性を数値化するアルゴリズムってありますか？

よくわからないけど、データマイニングでググって自分に必要そうなキーワードを見つけてきて