計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 175 名前：174 mailto:age [2005/12/05(月) 16:35:59 ] 極率　ではなく　曲率　でした。 176 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 16:40:06 ] 二次回帰分析とかって話? 177 名前：174 mailto:age [2005/12/05(月) 16:58:41 ] >>176 レスありがとうございます。 二次回帰分析ですと、y=a(x^2)+bx+c のa,b,cを決定するとこになると思われます。 今やりたいことは、例えば y = exp(-3*p)+q^2 に対応する離散データから (p, q)を求めるというものです。 exp(x)は２次関数ではありませんが、例えばテイラー展開等で近似をすれば、 適応出来る物なのでしょうか？ 178 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 19:46:30 ] 最小二乗フィッティングだね． 理論的には，s_1, ..., s_n をパラメータとする関数 f(x; s_1, ..., s_n) を データ列 (x_1, y_1), ..., (x_N, y_N) にフィッティングするときは誤差の二乗和 φ(s_1, ..., s_n) = Σ(f(x_i; s_1, ..., s_n) - y_i)^2 を最小化する s_1, ..., s_n を求めてやればいい． で，それは結構難しくて，凸関数とか条件付かないと最良解が出る保証は無い． ある程度の解でいいなら，「勾配法 + アニーリング」くらいで，それなりに求まってくれるはず． 179 名前：デフォルトの名無しさん [2005/12/05(月) 19:50:09 ] 画像調整のガンマをスクロールバーで実装したいのですが、 イマイチ正確な定義が分かりません。 それか、組み込めるライブラリどこかに落ちてないでしょうか？ 180 名前：174 mailto:age [2005/12/05(月) 20:15:07 ] >>178 詳しいレスありがとうございます。 今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が 最小になる(p, q)の組を解としています。 勾配法、アニーリングを調べてみて、検討してみます。 181 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 20:17:32 ] >>179 質問の意味がわからないけど多分スレ違い。 ・言語と開発ツールは何を使ってるのか ・具体的にやりたいことは何か ・今自分は何がわからないのか この三点をはっきりさせて、適切なスレに行って聞いてください。 182 名前：デフォルトの名無しさん [2005/12/05(月) 21:10:48 ] あるデータ列に Y = (A(X^3)+B(X^2))/(CX+D) の最小自乗法を適応するばあい、 残差の２乗和 S に対して A, B, C, Dそれぞれで偏微分したもの = 0 の連立方程式を解いて、 A = Σを含む式 B = ... C = ... D = ... とすれば良いのでしょうか？ 簡単な式の最小自乗法しか使っていなかったので、 そのまま適応して良いものかどうかが分かりません。 お願いします。 183 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 21:18:39 ] >>182 OK． ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし，解けたとしても解は一般に複数存在するので 出した解が本当に良いフィッティングになってるかは十分議論する必要がある． 184 名前：182 [2005/12/05(月) 21:30:11 ] >>183 ありがとうございます。勉強になります。 185 名前：アルゴリズム mailto:fh [2005/12/06(火) 10:20:52 ] N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい 年齢が３０歳以下の人の、体重と身長の平均値を計算し表示する 186 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 10:59:37 ] select average(weight), average(height) from DATA where (age <= 30); 187 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 12:50:40 ] >185 スレタイくらい嫁。 くだ質スレか宿題スレ池や。 188 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 20:36:58 ] >177 エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。 ところでexp（）の形になると判ってるなら、logを取ったらどうなる？ 189 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 21:51:46 ] プチ統計学講座だなｗ 190 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:09:54 ] >>188 ヒント：Windowsとは限らない 191 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:28:03 ] ひんと：Excel以外にも統計処理できるソフトはあるし、そもそもMacでもExcelは動く。 192 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:34:45 ] >>190-191 ヒント：そもそも汎用機とも限らない　例：宇宙計算用スパコン だからこそのアルゴリズムスレだろ？ 193 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 23:14:51 ] だからlogとったらどうなるかと聞いてみたんだけど 194 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 23:30:44 ] だから前半にだけ突っこんだんだけど 195 名前：デフォルトの名無しさん mailto:sage [2005/12/07(水) 19:22:24 ] まぁまぁ、次のネタを待ちましょう 196 名前：デフォルトの名無しさん [2005/12/07(水) 19:55:37 ] 上にも最小自乗法の話題が出ていますが･･･ y=(A(x^3)+B(x))/(C(x^2)+D) の関数に最小自乗法を適応することは出来ますか？ 残差の２乗和が最小になる(A,B,C,D)を見つけるわけですが、 例えばCで偏微分して=0となるCは、単なる極地のCであり、 それが極小かつ最小となるわけではありませんよね？ 197 名前：196 [2005/12/07(水) 19:57:51 ] あれ！？ よく見たら>>182とまったく同じ式でした･･･。 当方、学生ではないので課題とかでもないのですが。 同じ書物を読んでいるのかしら。 >>183を参考にします。 無視してください。 198 名前：デフォルトの名無しさん mailto:sage [2005/12/07(水) 20:29:05 ] フローチャートしか知らない 199 名前：デフォルトの名無しさん [2005/12/08(木) 10:14:07 ] 二次元配列と、 その中の３つの点で定義される三角形があって、 ある点がその中か外か判定するアルゴリズム教えて下さい。 200 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 11:58:18 ] >>199 (0,0), (0,2), (2,0) という要素数3個の2次元配列が与えられた場合、 (1,1) という点がその三角形の中にあるかどうかということだよな？ 1)与えられた3点が三角形を構成するかどうかを吟味。 2)その3点から各々2点を取り出し(3通り)、2点を通る直線の式を求める。 3)その3本について、直線で座標平面を分割した場合、残りの頂点を含む領域を不等式(3通り)であらわす。 4)中か外かを判定したい点について、その3つの不等式を同時に満たせば中、そうでなければ外。 201 名前：デフォルトの名無しさん [2005/12/08(木) 12:26:41 ] そのまんまじゃん 202 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 13:04:30 ] ナップザックを背負ったバックパッカー*がいるとする。ナップザックの中は、 できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、 どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが 最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ *リュックサックに全ての荷物を入れて旅行する人のこと。 問1 0/1 ナップザック問題とは何か？ 問2 全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん な問題となるのだろうか？ 問3 アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの か？ 問4 ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか？参考 書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか 記述せよ． 203 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 15:35:02 ] >>202 ここは君が来るべきスレでは無いよ。 204 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 15:59:27 ] >>203 いいじゃんべつに。 お前の個人的な感情は出さなくてもいいよ。 そんなもの読んでいる人間には全く価値がないから。 文句があるならどのスレにいけ、ぐらいは言えよ。 あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。 205 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 18:15:33 ] >>204 つまんないﾈﾀ書くのも自由だし それを批判するのも自由。 206 名前：デフォルトの名無しさん [2005/12/08(木) 18:37:18 ] 座標３つ（どれがどの位置か不明）から、３角形の面積を計算する方法はありますか？ 207 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 18:40:49 ] >>205 自重しろよ。 自由ではないんだよ？あまりひどいとアク禁だ。 208 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 19:52:21 ] >>206 3点から辺の長さ求めてHeronの公式、とか。 209 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:01:43 ] 三点のベクトルが v1, v2, v3 のとき [v1-v2, v3-v2]/2 の絶対値が面積になるね。 [x,y] は x と y の外積ね。 210 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:02:07 ] >>206 ある点を原点に移動させるように全体を並行移動させて、 (0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを 使った方が簡単かも。 ３点が三角形が作られない位置に無いことを確かめてからね。 211 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:03:50 ] 実は （>>182の式）≠（>>196の式） である件について 212 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:55:54 ] >>206 www.tensyo.com/urame/prog/linealgo.htm の多角形の面積でやれば？ 213 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 23:07:36 ] >>199 >>99,>>107-108 >>204 >>187 てか、質問する前にスレ内くらいは読もうぜ？ 214 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 18:24:45 ] >>206 でも、3点とも座標がわかってて位置不明ってどゆこと？ 215 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 19:24:25 ] >214 「固定座標じゃない」って意味だろ。 確かに意味は解らないが、気持ちは伝わってきた。 216 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:30:04 ] ヘロンの公式のことをたずねているの？ 217 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:39:02 ] 辺の長さが与えられてるわけじゃなく、頂点座標だから ヘロンの公式をわざわざ使うより 素直に台形公式による閉曲線積分 218 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:56:04 ] >>217 頂点座標？閉曲線積分？言葉はちゃんと使おうぜ 219 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 01:18:24 ] >>214 任意の三点ってことだろ。 220 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 11:53:04 ] 三角形なんだから、3点を P, Q, R として、 2つのベクトル a ＝ PQ、b ＝ PR を定義。 (1/2) |a × b| ただし、×は3次元ベクトルの外積、|| はベクトルの絶対値。 っつーか、ぐぐれ。 homepage2.nifty.com/PAF00305/math/triangle/node3.html 221 名前：BASIC mailto:fh [2005/12/14(水) 15:57:56 ] 次のプログラムをＢＡＳＩＣで作成しなさい データを１件ずつ、ユーザ定義関数を利用して 「公共料金」を計算させることにします ＜水道料金の計算＞ 基本料金：1250円 定量制料金単価は ・使用量が10立方米以下であれば80円／立方米 ・ 〃 10立方米超20立方米以下であれば185円／立方米 ・ 〃 20立方米超50立方米以下であれば205円／立方米 ・ 〃 50立方米超100立方米以下であれば240円／立方米 ・ 〃 100立方米超200立方米以下であれば275円／立方米 ・ 〃 200立方米超であれば310円／立方米 （計算例） 使用量が8立方米であれば、1250＋8×80 使用量が15立方米であれば、1250＋10×80＋(15−10)×185 ＝2050＋(15−10)×185 使用量が40立方米であれば、1250＋10×80＋10×185＋(40−20)×205 ＝3900＋(40−20)×205 使用量が75立方米であれば、1250＋10×80＋10×185＋30×205＋ (75−50)×240＝10050＋(75−50)×240 使用量が120立方米であれば、1250＋10×80＋10×185＋30×205 ＋50×240＋(120−100)×275＝22050＋(120−100)×275 使用量が230立方米であれば、1250＋10×80＋10×185＋30×205 ＋50×240 ＋100×275＋(230−200)×310 ＝49550＋(230−200)×310 222 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 15:58:42 ] 作成しなさい、だってさ↓ 223 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 16:01:00 ] 　　　　　　　　　　　｜　　　　　∧＿∧ 　　　　　　　　　　　｜.　　　 　(･ω･` )ｽﾙｰ 　　　　　　　　　　　｜ｽｽ…　/J　　 J 　　　　　　　　　　　↓　　　,,, し―-J 224 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 16:51:10 ] アルゴリズムじゃねえな 225 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 19:15:46 ] アゴリズムだな 226 名前：デフォルトの名無しさん mailto:sage [2005/12/15(木) 00:36:36 ] アルゴリズムじゃねえって！ 227 名前：デフォルトの名無しさん mailto:sage [2005/12/15(木) 04:40:03 ] アルゴリズム体操！アルゴリズム体操！ 228 名前：デフォルトの名無しさん mailto:sage [2005/12/16(金) 15:42:28 ] 立方米って一般的なのか。 m^3と書かないの。 229 名前：デフォルトの名無しさん mailto:sage [2005/12/16(金) 15:51:32 ] >>228 メートル=米、だからね。 他にも糎とか粍とか。 でも、普通は立方米と書かずに立米(りゅうべい)と書く希ガス。 #平米は割と一般的でしょ。 230 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 12:32:02 ] 口頭ではよく「へーべー」と言うな。 俺の父親が。 231 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 12:34:10 ] なんでメートルが米なの？？その由来は？ 232 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 12:58:32 ] 亜米利加　と同じじゃないの？　メの元の漢字だと思ってたけど ttp://www.fudemojiya.com/syo/katakana.htm によると　女　らしい 233 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 13:05:23 ] 明治時代か江戸末期に「メートル(或いはメーター)」という音に似ているから当てたんじゃないの? 他にもグラムやインチなどにも当てられた漢字があることだし。 234 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 19:27:50 ] ttp://freett.com/ToshiN/kanji/kanji02.html 発案した人も途中からヤケクソになっていったのだと推測 235 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 22:42:29 ] >>234 そこまでして漢字にせんでもええやん…とおもた。 236 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 03:23:45 ] 当時ハ送リ仮名ガ片仮名デアッタタメ 外来語ヲ片仮名ニ割リ当テルトイウ 発想ハ無カッタンダロウナ 237 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:08:19 ] 質問なのですが、例えば、 1、２、３、４、５、４０、５０、６０、７０　といった代表値である数字があるとします。 で、例えばXがその代表値のどれに一番近いかを求めるとき すべてを探索すれば答えはわかると思いますが、できるだけ高速に 求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、 例えばXが6だとするとまず、5が一番近いことがわかります これをどうやって木にしたらいいのかがわかりません。 また１，２、３・・・・といっていましたが （X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう？ 一致するのを探すのではなく一番近いものを探すので苦労しています。 近さの判定としてはユークリッド距離を用います。 どうぞよろしくお願いいたします 238 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:13:08 ] 代表値の数列が整列されている前提ならバイナリサーチでいいのでは？ 239 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:32:56 ] >>238 ありがとうございます。 バイナリサーチですと完全に一致する場合は問題ありませんが 完全に一致せず一番近いものを選択するときに問題がおきます 237の例で6に一番近いものをバイナリサーチで探そうとすると 40になると思われます 240 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:46:58 ] バイナリサーチで最終的に 40 がヒットするわけだけど、 この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。 あとはどちらに近いかを計算するだけじゃないのかな。 241 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:54:28 ] >239 最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。 n次の場合は、a=f(X,Y,...)で、aの値でソート。 242 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 05:01:13 ] >>240 >>241 ありがとうございます。 ｎ次の場合はうまくいかないように感じるのですが できれば具体例を出していただけないでしょうか？ 241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか しらべて次はY、Z・・・というふうなことだと感じているのですが 例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので あまりうまくいかなようなきがします。 間違っていたらすみません 243 名前：241 mailto:sage [2005/12/18(日) 05:37:33 ] >242 スマソ、完全に寝ぼけてた。 1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね？ 244 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 05:40:16 ] >>243 ありがとうございます。 総当りですか・・・それですと時間がかかるので 何かいい方法がないかなと思いまして 245 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 07:16:28 ] >>241 ２次元（平面）ならボロノイ図・近傍で似たような問題がある ３次元以上だとできるかどうか知らない 総当りにしたら 246 名前：245 mailto:sage [2005/12/18(日) 07:17:31 ] >>245 の >>241 は >>237 の間違いです ｽﾏｿ 247 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 07:55:24 ] >>245 ありがとうございます。 ボロノイ図については知っていまして、三次元でも可能のようです。 ですが、これをどう木にすればいいのかよくわからなかったもので 何かいい方法があればと思って相談してみました、。 248 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 09:03:12 ] >>237 空間データベースって分野のお話だね． 望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな． 空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に 点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで， その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)． ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく： www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html vision.unige.ch/~moennen/publi/moennen_tech0505.pdf H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley 249 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:00:28 ] >>248 ありがとうございます 望んだ形でデータを持っていても大丈夫です。 K−ｄ　tree　についてなのですが、これでは一番近い代表値に近似することはできないと 考えられます。 例えば www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html のｋ−ｄ　ｔｒｅｅ　のところの図で説明しますと 代表地がＰと考えると、Ｐ４とＰ５の線の中に点があるのですがＰ９に 一番近い点（一番近い代表地に近似したい点）があったとすると これはＰ４かＰ５に近似されることになります。 実際はＰ９に一番近いのにこれには近似されないとおいうことです 木を作る際にＰ７からでなくＰ６からはじめたとしても同様の問題はおきると考えられます しかしＲ−ｔｒｅｅというのは使えそうな気がします ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが なんとかがんばってみます ありがとうございました 250 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:04:36 ] www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html のＲ−ｔｒｅｅを読んでみましたがこれでも正確に一番近い代表地に 近似されないように感じます。 うーんどうしよう 251 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:05:18 ] 一番近い点は一回では求まらないだろう。 　求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。 　たとえば2次元なら　x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで 　　矩形で絞り込めばいいでしょ 252 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:07:59 ] あと、この問題は、最悪の場合は、全数検索が必要になる。 たとえば円周上に点が並んでいて、中心に近似しようとした場合など 253 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:17:52 ] >>251 >>252 ありがとうございます。 自分の中で何か新しいアイデアが浮かんできそうな気がします が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです どうかおねがいします 254 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:25:28 ] データ構造として、各母点に、母点を中心に、一番遠いボロノイ点までの距離半径の円内にある 母点までのリンクを距離順に並べて持たせておいて 最初に検索した母点までの距離内にあるリンクだけ全検索する 検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする 255 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:35:34 ] >>254 ありがとうございます 私の理解力不足のためわからなかったです　すいませんが もう少し簡単な説明をしていただけないでしょうか　どうかお願いします 256 名前：248 mailto:sage [2005/12/18(日) 10:53:05 ] >>249 二つ目に挙げたテクニカルレポートも読んでね．ちゃんとそっちに作った木から kNN を絞り込む方法について コメントが入ってるから．参考文献にもそれっぽいのが沢山あるので子引き，孫引きしましょう． 257 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 09:08:38 ] 長いですが、NP完全について質問です。 アルゴリズムの本に 「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか？ "=Which of the diagrams do not contradict the current state of our knowledge about the complexity classes P, NP, and NPC (NP-complete problems)"」 という質問があってヒントに 「これらのうちの二つのみが現在の私たちの知識と矛盾している "=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。 「私たちの知識」とはその本に載っている 「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ "=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」 っぽいです。 図は五つあって、そのうち aはP=NP=NPCで、bはNPCがP=NPの部分集合になっており、dはPとNPCが重なった形でNPの部分集合になっており、 これらは明らかに矛盾しているので除外です。 eは↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。 ttp://www.jyi.org/volumes/volume10/issue2/articles/widjaja.html で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか？) これも矛盾してますよね？PでもNP完全でもないNP問題がないといけないんですから。 そうだとしたらこの本の間違いなんですが…。 ここの賢い人、どうか答えてください。せめてヒントだけでも…。 258 名前：257 mailto:ageで [2005/12/19(月) 09:19:37 ] あまりの必死さに図を描いてしまいます。m(__)m c.　　　　　　　　ＮＰ ┌─────┬─────┐ │　　　　　　　│　　　　　　　　│ │　　　Ｐ　　　│　　ＮＰＣ　　　│ │　　　　　　　│　　　　　　　　│ └─────┴─────┘ てな感じです。 259 名前：257 mailto:sage [2005/12/19(月) 09:23:48 ] 度々すみません。訳し間違えました。正しくは 「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か？」 と 「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」 です。もう後で逝ってくるつもりです。m(__)m 260 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 10:19:49 ] >>188 すみません 261 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 13:34:18 ] >>257 「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」 であって、「P≠NP」とは限らない。 262 名前：257 [2005/12/20(火) 12:17:51 ] >>261 ありがとうございます。 なるほど、「P≠NP」とは限りませんよね。 もしそうだとすれば選択肢は「P＝NP」しかない訳で その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」 と解釈してよいのでしょうか？ 友達の一人は「『P＝NP』は『現在の私たちの知識』に矛盾していないか？ 図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。 cがP=NPとするなら矛盾していると判断するべきだろう？」と問いかけてきました。うーむ。 すみません、自分、人より脳が少し足りないようです。 また説明お願いします。m(__)m 263 名前：デフォルトの名無しさん mailto:sage [2005/12/20(火) 14:31:12 ] >>262 現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。 P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、 多項式時間で解くことの出来ない問題があることを証明できていない現在、 P=NPは矛盾しているとはいえない。 264 名前：257 mailto:sage [2005/12/21(水) 12:01:14 ] >>263 なるほど、ようやく分かりました。 すべてのNP問題が(近似解とかではなく) 多項式時間で解けるようになったら面白いでしょうね。 天寿を全うするまでに見たいものです。 ありがとうございました！ 265 名前：デフォルトの名無しさん mailto:age [2006/01/09(月) 00:12:14 ] age 266 名前：BASIC mailto:fh [2006/01/09(月) 16:12:52 ] N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい 体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する 267 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:34:00 ] 宿題は自分でやれ 268 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:54:08 ] BASICなんて記憶の彼方だな 269 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 18:15:01 ] 何ベーシックかは指定していないな。 VBとかでもいいとすれば随分アレだ 270 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 19:08:23 ] >>266 www.sagami.ne.jp/tadaka/99Basic/ 271 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 03:29:11 ] ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？ (n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！ 272 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 06:49:10 ] Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない． 定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし． O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？ 273 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 10:57:45 ] >271 LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、 次回以降は演算を省くってのはどうだろう？ 辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。 274 名前：271 mailto:sage [2006/01/12(木) 12:31:26 ] >>272-273 早いレスどうもです！ >>272 やはりO(nm)回は「本質的に」避けられないわけですよねー・・・ 微分の差分近似をループでnm回やるつまらない実装なんで、 工夫できないかなと思った次第だったのですが。 ちなみに問題は非線形関数の最小値探査みたいな感じです >>273 んー、いいアイディアなんですが今回は 適用できないような気がします、ゴメンナサイ ただ、そのうち他の問題で使えそうな気がするんで、 そのネタはもらって覚えておきます！　ありがとう！ 275 名前：デフォルトの名無しさん mailto:sage [2006/01/14(土) 00:48:34 ] >>274 最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef