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

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

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

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

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

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

ここは過疎板なんだな。

過疎板・・・。

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

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

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

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

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

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

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

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

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

mod(26^61, 437) = 292

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>94
意味が分からない。

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

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

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

>>94-96
どうもです。

wikiの定義の意味が

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

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

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

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

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

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

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

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

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

のようなものを考えると

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

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

おねがいします。

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

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

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

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

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

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

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

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

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

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

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

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

おねがいします。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>108
宿題は自分でやれ

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

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

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

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

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

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

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

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

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

お助けください

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

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

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

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

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

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

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

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

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

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

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

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

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

辞書ひけ

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

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

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

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

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

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

>>120

俺だったら、

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

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

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

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

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

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

合ってるよ

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

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

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

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

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

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

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

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

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

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

ってのを思いついた。

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

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

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

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

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

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

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

助けてください

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

猛者の方教えて下さい。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16進への変換

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

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

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

>>149
別に

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

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

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

た

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

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

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

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

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

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

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

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

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

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

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

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

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

ノーベル何賞よ

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

平和賞

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

欽ドン賞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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