アルゴリズムの概念 ～ オーダーと計算量 ～ ・ コンピュータの基礎 ・ アルゴリズムの概念 ・ オーダーの定義と計算量 ・ NP完全問題 簡単に自己紹介 名前： 宇野 毅明 所属： 国立情報学研究所 & 総合研究大学院大学 年齢・職種： ３８歳、准教授 研究分野： アルゴリズム理論 － コンピュータプログラムの設計手法の理論 － 速いコンピュータを作ったり、プログラミングの腕を競うの ではなく、「設計方法の違いによる性能の向上」を目指す 最近の研究： ゲノム情報学やデータマイングで出てくる巨大なデー タベースの基礎的（とはいっても非常に時間のかかる）な解析を超 高速で行うアルゴリズムの開発 日課： 子供と遊ぶこと 目的・成績評価・参考書 ・ アルゴリズム理論による設計は、大規模なデータを高速で処理 する際に特に有効 ・ データの処理、プログラミングを、アルゴリズム的な視点から考 察し、必要な技法を調査・開発できるようにするセンスを育てたい ・ 成績評価はレポート ・ 参考書：「アルゴリズム」「データ構造」と名の付く教科書の中で、 自分が面白いと思うもの ・ メール： [email protected] ホームページ： http://research.nii.ac.jp/~uno/index-j.html （授業の資料があります） 授業の内容 ・ コンピュータの仕組み、プログラムの仕組み CPU、メモリ、OS、メモリ管理、命令、変数 ・ データ構造（データの記憶方法） スタック、キュー、ヒープ、２分木、ハッシュ ・ 基本的なアルゴリズム 再帰呼び出し、分割統治、列挙、動的計画法、ソート、文字列マ ッチング ・ グラフアルゴリズム マッチング、最短路．．． 最先端の研究とのつながり ・ アルゴリズムは、多くの分野で、先端科学とつながっている （アルゴリズムが使われている、その分野で研究されている） ・ 特に、大きなデータがあって、データやモデルが数理的にシンプ ルなところ － 分子生物学 ヒトゲノムの大きさは30億文字なので、ヒトが扱うのは困難。 ATGCの4文字でコンピュータには有利。遺伝子や、ゲノムの変異 などはある程度の規則性を持つ。 － 情報化学 分子は基本的に原子の繋がりなので、同じくコンピュータで扱い やすいが、立体と距離を含めた取り扱いが難しい。今後発展か？ 最先端の研究とのつながり (2) － 天文学 望遠鏡のコンピュータ化により、データが電子的に蓄積されてい る。統合データベースもできつつある。今後は、データを総合的に 使った研究が始まるだろう。 － 物理学（素粒子、量子力学） 加速器から得られる情報の大きさは天文学的。今のところ、処理 して蓄積するだけで手いっぱい。 － 社会科学 シミュレーションによるミクロ的な要因を含む人間（社会）のシステ ムを理解が進んできている 最先端の研究とのつながり (3) － 建築学 構造計算による強度の計算だけでなく、最適化による、強度を保 ったまま部材を減らし軽量化する手法の研究など － 文学 膨大な文献情報（古典を含む）のコンピュータ処理による知見の 発見 － その他全般 シミュレーションにより、現実世界のシステム的理解をする、シミ ュレーション科学の進展 日本の最先端研究 ・ アルゴリズムの分野は、日本の研究レベルは世界の中でも比較 的高い － 最適化に対する内点法アルゴリズム、世界標準 － 離散数学と組合せ最適化アルゴリズム － 圧縮アルゴリズムと簡潔索引 － データベース高速検索 － データマイニングアルゴリズム － 計算幾何学アルゴリズム ．．． ・ 現在は理論中心であるが、将来的には工学のほうに成果が応 用されていくものと思われる コンピュータの基礎 コンピュータの基礎 ・ コンピュータはいくつかの部品で成り立っているが、メインの 部分はCPUとよばれる演算装置 ・ 車でいえばエンジンのようなもので、これがあるかないかが、 コンピュータであるかどうかの境目のようなもの ・ CPUの他にメモリという、数値を複数記録できる装置がある CPU メモリ 外部入出力機器 ・ CPUとメモリはわかった ・ 他のもの（ディスプレイ、キーボードなど）はどう管理しているの か？ ・ メモリの一部が、ディスプレイ用に割当てられている （どこどこに何を書くと、どこどこのドットの色が赤になる、といった ことがハードウェア的に決められている） ・ IOポートとよばれる、メモリのようなものがあり、キーボードの キーの押されている／押されていない、の状態によって、値が 変わるようになっている ・ これらの機能を使って、外部とのやり取りをする プログラム ・ コンピュータができることは、 － メモリから数値を読むこと、および書くこと － 足す引く掛けるなどの算術演算をすること － 数の大小の判定をして、行う処理を変えること ・ これらの操作のことを命令という ・ 命令をどのように行うかは、やはりメモリに記録する。これを プログラム と言う ・ プログラムに書かれたとおりに処理を行わせることを、プロ グラムを 実行する という CPU メモリ プログラムの実行 ・ プログラムは、メモリに書いてある命令を順次実行する ・ 命令は数値になっていて、それぞれの数値に機能が割当て られている ・ 処理中に、次から行う処理の場所を変更することができる ・ 条件によって処理を変える場合には、この機能を使って、条 件を満たす場合のみ次から実行する命令を変える（条件 分岐という） CPU メモリ プログラミング言語 ・ CPUの命令は数値。しかも、１つ１つの処理は非常に単純（これ をマシン語、あるいは機械語という） ・ これを組合せてプログラムを作るのは、かなり大変 ・ そこで、通常はもう少し抽象化して、人間に見やすくした「高級 言語」とよばれるものを使う （C，JAVA，Perl, Basic, シェルスクリプトなど） ・ 高級言語で書かれたプログラムを、CPUに実行させるには、プ ログラムをいったんマシン語に翻訳する（この作業をコンパイ ルという）か、プログラムどおりの処理をするプログラム（インタ ープリタという）を使う 概念的な例 １： 場所 15 に 0 を書き込む ２： 場所 16 に 2 を書き込む ３： 場所 15 と 16 の値を足し、それを場所 15 に書き込む ４： 場所 17 の値が 10 以上ならば、８へいく ５： ３へ行く ８： ．．． ・ ２－４のように局所的に繰り返して実行される部分をループ という CPU メモリ メモリのアクセス ・ メモリは1バイトずつ数値が記憶されている ・ メモリには、記憶場所に0から始まる番号がついていて、好きな 場所のデータに一手でアクセス（書き込み／読み出し）できる ・ このように、好きな場所に一手でアクセスできるメモリをランダ ムアクセスメモリという ・ ランダムアクセスでない記憶装置は、例えばCDとかハードディ スクとか、テープ １ ０ １ １ ０ １ ０ １ 数値の表現（バイト） ・ メモリは数値を覚えられるが、実は 0 と 1 しか覚えられない （ビットという） ・ しかし、大量に 01 の数値を記憶できる ・ 実際は、01しか記憶できないのでは用をなさないので、01 の数値を8個セットにして、それを2進数とみなす。（0-255が 表現できる） － これを １バイトという ・ 足す引くかけるの算術演算の結果、 2進数9桁目に繰り上 がったとき、あるいはマイナスになったときは、その部分は 無視して計算する １ ０ １ １ ０ １ ０ １ 128+32+16+4+1 = 181 16進数 ・ コンピュータに記憶された数を扱うときは、当然、２進数で話 をしたほうがわかりやすい （例えば、1バイトに入る数の最大は 11111111 とか。直感的 になる） ・ 01 だけで表記すると場所をとる、桁が大きくなる ・ そこで、4桁ずつひとまとめにして、24 ＝ 16 進数で表記する ことが多い ・ 10-15 は、abcdef で表記する。例えば、14=d、255=ff データの記憶 ・ メモリには、記録されている数値が整数か、文字か、といった、 データの種類を覚えておく機能はないので（数値として付加的 に記録することはできるが）、自分（プログラム）が何を書いた か管理する ・ つまり、「何のデータはどこに書いた」ということを決めておく。プ ログラムでは、データの計算をする際には、場所を決めて書く ・ 常に0か1の値が書いてあるので、「書き込まれていない」という ことも検出できない 点数 点数 20 点数 20 20 １ ０ １ １ ０ １ ０ １ 整数小数文字 － 整数： 01の数値をいくつかセットにして、それを2進数とみなす。 通常、32ビット ＝ 4バイト。 (0-40億くらい) － 実数： 整数と小数点の位置をセットで記憶。小数点は2進数の 位置で記憶。通常、整数が56ビット、小数点が8ビット（256桁分） － 文字： 文字と整数値を対応させたコード表があり、それを使っ て整数値として記憶する １ ０ １ １ ０ １ ０ １ + ０ １ ０ １ 128+32+16+4+1 = 181 4+1 + (16+4+1)/32 = 5.65625 負の数の表現（バイト） － 負の数： 最上位のビットが1になった数は、256を引いて、 負の数とみなす。通常の数と思って計算したときと、負の 数と思って計算したときの結果が同じなので、結果を変換 する必要がない 例： 255 は-1 になる。1を足すと、 1111111 + 1 = 100000000。9桁目は無視するので、0 これは、実際の -1 +1 の答えと一致する 例： -2 は 254、-5 は 251。両者を足すと、505。256の剰余を 求めると249。これは-7に対応。両者を掛けると 63754。剰 余を求めると 10。 文字コード表 (ASCII) － 0-255の整数と文字の1対1対応を表したコードをASCIIコード、 そのコードに基づいて書かれた文字をASCII文字という （だい たい世界標準） － コンピュータに文字が記憶されるときは、このテーブルにした がって数値に変換され、1文字1バイトで記録される（大小の比 較ができる） | 20 sp | 21 ! | 22 " | 23 # | 24 $ | 25 % | 26 & | 27 ' | | 28 ( | 29 ) | 2a * | 2b + | 2c , | 2d - | 2e . | 2f / | | 30 0 | 31 1 | 32 2 | 33 3 | 34 4 | 35 5 | 36 6 | 37 7 | | 38 8 | 39 9 | 3a : | 3b ; | 3c < | 3d = | 3e > | 3f ? | | 40 @ | 41 A | 42 B | 43 C | 44 D | 45 E | 46 F | 47 G | | 48 H | 49 I | 4a J | 4b K | 4c L | 4d M | 4e N | 4f O | | 50 P | 51 Q | 52 R | 53 S | 54 T | 55 U | 56 V | 57 W | | 58 X | 59 Y | 5a Z | 5b [ | 5c \ | 5d ] | 5e ^ | 5f _ | | 60 ` | 61 a | 62 b | 63 c | 64 d | 65 e | 66 f | 67 g | 日本語の文字コード ・ 日本語については、日本語独自のコード表がある（世界規格と して使われているので、外国でも日本語の文章が読める） ・ 歴史的な事情で、いくつかのコードがある － JIS コード － shift JIS コード － EUC コード － unicode JISコード ・ 英語は0-127しか定められていないので、128-255の部分にかな と記号が入っている JIS漢字コード ・ 漢字については、制御コードという、特別の文字2つが入ったら、 日本語のモードになる。漢字は、2バイト1文字。もう一度制御コ ードが来たら、以後は英数字に戻る 16区（S-JIS第一バイト＝0x88） 0 1 9 A 唖 娃 B 芦 鯵 C 安 庵 D 威 尉 2 3 4 5 6 7 8 9 A B C D E F 亜 阿 哀 愛 挨 姶 逢 葵 茜 穐 悪 握 渥 旭 葦 梓 圧 斡 扱 宛 姐 虻 飴 絢 綾 鮎 或 粟 袷 按 暗 案 闇 鞍 杏 以 伊 位 依 偉 囲 夷 委 惟 意 慰 易 椅 為 畏 異 移 維 緯 胃 萎 衣 E 謂 違 遺 医 井 亥 域 育 郁 磯 一 壱 溢 逸 稲 茨 F 芋 鰯 允 印 咽 員 因 姻 引 飲 淫 胤 蔭 Shift-JISコード ・ Windows で使われているコード ・ 制御文字を使わず、2バイトの文字をあらわしている ・ 1文字目が記号だと、次の 1バイトとあわせて記号だと みなすので、記号が使えな くなる ・ 2バイト目は、改行コード など、通常の文字になること もあるので、日本語対応して いないソフトで見ると、 ぐちゃぐちゃになる EUCコード ・ 主にUNIX で使われているコード ・ 制御文字を使わず、2バイトの文字をあらわしている ・ 1文字目が記号、かななら、 2文字目とあわせて、 漢字コードとみなす ・ 2文字目も、かな記号なの で、漢字の一部ならかな記号、 と判断できる ・ 記号、かなが出せない UNICODE ・ 世界の全ての言語の文字を１つのコードで表す、というもの ・ 2バイト1文字を使わず、2バイトの文字をあらわしている ・ 漢字など、地域で字体が 違うものも１つとして扱うため 事実上はその国固有の フォントが必要 ・ 最近は4バイトで表すようだ キャッシュメモリ ・ コンピュータのメモリのアクセス速度は、演算速度よりかなり遅 い（10倍以上） ・ そのため、メモリを読み出すときは、しばらく演算をとめて待つこ とになる。次の命令を読むときもそう。 ・ そこで、メモリを読むときはまとめてたくさん読む ・ 読んだメモリは、CPUに直結した速いメモリにしばらく取っておく （この操作をキャッシュ、キャッシュに使うメモリをキャッシュメモ リという） キャッシュ CPU メモリ メモリ ディスク キャッシュによる高速化 ・ メモリアクセスが、キャッシュに入っている場所ばかりだと計算は 大幅に速くなる キャッシュの効率を高めるような保存法が重要 引き続いて、キャッシュの中を見ることが多い計算をさせると、 高速化できる ・ ディスクのアクセスにも、同じようにキャッシュを使う CPU直結メモリの代わりに、通常のメモリを使う。メモリのほうが ディスクよりアクセス速度が速いので、高速化できる CPU メモリ HDD 変数 ・ 高級言語では、数値を記憶する際に変数というものを使う ・ 変数には、何か値が１つ入る ・ コンパイルして実行するときに、各変数にメモリの場所が割当て られる。以後、変数をアクセスするときには、その場所にアクセ スするようになる 配列 ・ 大量のデータを扱う場合、全てのデータに直接変数を割当てる のは、大変。プログラムを書くのも大変 ・ そこで、配列を使う ・ 配列を使うと、変数＋添え字、という形でデータにアクセスでき る。添え字のところは変数を入れられるので、例えば、100個の 変数を0にする、といった作業も、ループを使って楽にできる １ ０ １ １ ０ １ ０ １ OS ・ コンピュータは、機種によって、入出力の方法が違う ・ ディスプレイに文字を書くためには、文字の形になるよう、デー タを書き込まなければいけない ・ こういった、ハードウェアによる違いを吸収する、低レベルの処 理を行う、実行するプログラムの管理、などをするプログラム がある ・ これをOSという （Windows、UNIXなど） ・ 固有の接続機器を、標準的な入出力方法を用いて扱うプログラ ムをデバイスドライバという ・ メモリの管理もOSが行う メモリの確保 ・ 普通、コンピュータでは、複数のプログラムが同時に実行されて いる（含むデバイスドライバ） ・ そのため、メモリの適当な場所に適当に数値を書き込むと、他の プログラムの実行を阻害する（下手をすると動きが止まる） ・ そのため、メモリを使いたいときには、OSにお願いして、必要な 分だけ使える場所をあてがってもらう（これをメモリを確保すると いう） アルゴリズムの概念とオーダー 問題の解き方 ・ 問題の解き方と、問題の答えは違う － カレーとカレーの作り方 － 知恵の輪のはずし方 － ハノイの塔の解き方 － １元２次方程式の解 x2 - 2x + 1 = 0 ・ 抽象的な解き方は、問題が変化しても対応できるので、単 に答えを教えるのとは違う ・ 「問題の解き方」を考えよう 計算機アルゴリズム アルゴリズム： 物事をするときの、手順のこと 普通は、コンピューターに計算をさせる（プログラムの）手順 コンピュータの、効率の良いプログラムを書くにはどうするか、と いうプログラム設計の理論と考えても良い １から１００の数字を足したい： ・1+2+,...,+100 ‥‥ 99回の足し算 ・(1+100) * (100/2) ‥ 演算3回 にんじんを星型の輪切りに切りたい ・輪切りにしてから、それぞれを星型に切る ・ まず星型の切込みを入れてから、輪切りにする 身近なアルゴリズム ・ 料理の作り方 ・ ひっ算の仕方 ・ 車の運転の仕方 ・ 企業面接の仕方、問答集 ．．． （どれも、場合分けが完全ではないですが） アルゴリズムの評価 ・ アルゴリズムのよさは、何ではかるか？ ・ 身近な場面なら、どれだけ簡単か （単純さ） プログラムの単純さ ・ あと、効率も（速さ、場所・コストなど） 速さとメモリの使用量 ・ どれくらい単純か、は測定しにくいが、速さやメモリの使用 量は数値として評価できる 計算時間の評価 ・ プログラムの計算時間を測るのは簡単。実行が始まってか ら終わるまでを測定すれば良い ・ 当然、プログラムのできばえで速度が変わる ・ しかし、これはプログラムの評価であって、アルゴリズムの 評価ではない 同じアルゴリズムでも、コンピュータの性能やプログラマ ーの腕前で速度が変わる ・ うまく、アルゴリズムの速度を測るモデルが必要 チューリングマシン ・ アルゴリズムのモデルを作るということは、コンピュータのモデ ルを作る、ということ ・ 何か、至極単純な事をするものを考えないと ・ コンピュータの基本は、CPUとメモリ。これをモデル化したのが チューリングマシン ・ チューリングマシンは情報（０１データ）を記録するテープと、そ れを読み書きするヘッド、テープを動かす駆動装置からなる ・ チューリングマシンができる操作は、テープを動かすこと、読み 書きすること、読み込んだデータによって、自身の内部状態を 変更すること 計算時間の評価モデル ・ チューリングマシンの実行速度は、状態が受理状態とよばれる 終了状態になるまでに必要な、処理の回数で評価できる ・ 基本的に、コンピュータの演算１つは、チューリングマシンの操作 数手でできる。これは処理の大きさ／時間などには関係ない ・ 両者は、同じモデルで評価できる 基本的な演算（算術演算、メモリの読み書き）の回数で、速度 を評価しよう 大域的な評価 ・ 基本的な演算の回数、というアイディアはいいが、やはりプログ ラマーの腕前で、それも変わる ・ そういうものにふりまわされない、大域的な評価がほしい ・ そもそも、どういうことの時間を計るのか？ ・ 例えば、何かの処理を決めて、それの時間を計るのか？ ならば、究極的には、腕前がきいてしまう 入力の大きさに対する評価 ・ 計算は、入力して、出力するのが基本。入力するデータが大きく なると、当然時間がかかる ・ では、入力したデータの大きさに対して、どういう風に計算時間 が増加するかを評価しよう ・ 入力の大きさ（正確にはビット数）n に対して、必要な基本演算の 回数を、関数の形で、10n2+5n+2 のように表す ・ 同じ大きさの入力でも、必要な回数は変わる。どのようにする？ 平均？ 保証をする意味で、最悪を考える 係数の無視 ・ 基本演算の回数の、増加の仕方が知りたい 10n2+5n+2 のような場合、n が大きくなれば、最も次数の大き いところしか関係しない 10n2 だけに注目して、残りは無視しよう ・ プログラマーの腕前は、単純な作業をより単純に、きれいにする 10n2+5n+2 のような場合、各項の係数の部分に影響する n2 だけに注目しよう ・ このような、最高次数の部分だけを評価する方法をオーダーによ る評価と言う 数学的な定義 ・ 関数 f(n) が O(g(n)) であることの定義を以下のように行う lim n＋∞ f(n) g(n) < +∞ ・ アルゴリズムのオーダーが O(g(n)) であるとは、入力した問題の 大きさ n 基本演算の回数の最大値が O(g(n)) であることをいう ・ アルゴリズムの計算時間のオーダーを、時間計算量、あるいは 単に計算量という オーダー、まとめると、 計算時間オーダー： O(f(n)) 入力した問題の大きさに対して、最悪で、どの程度の時間がか かるかを、問題の大きさの関数（多項式）であらわしたもの ※ 係数は、機械やプログラマーによるので無視。 ※ 最大次数のところのみに着目する （入力が大きくなると、最大次数しか効いてこない） n項目ある辞書を引く： ・ 最初から順に調べる O(n) ・ 2分探索する O(log n) n 個の数字をソートする ・ 普通に挿入、クイックソート O(n2) ・ マージソート・ヒープソート O(n log n) オーダーが小さければ、 機械やプログラマーが 多少悪くても、設計の良 さで圧倒的に速い 計算量による評価の利点・欠点 ・ アルゴリズム理論による高速化は、問題の大きさに対する計算 時間の増加を抑える ・ 問題が小さいと、低い次数、係数の違いにひっぱられて、実用 上のパフォーマンスが悪くなる ・ 最悪を評価するため、平均が見えない 100項目 100万項目 2-3倍 10000倍 メモリ使用量の評価 ・ アルゴリズムのメモリ使用量の評価も、オーダーで行う ・ 腕前の違いを無視できる ・ メモリに関しては、足りなくなると計算ができなくなるので、最悪を 評価するのはより妥当 計算量理論の基礎 うまい設計 ・ アルゴリズムの評価は、オーダー、つまり計算時間の最高次数 で評価することになった ・ つまり、うまくやれば、小さいオーダーとなる ・ するとですね、どの辺から、「うまくやってる」といえるんでしょう か？ ・ １つのアイディアは、最も簡単なものと比べてどれくらい速くなっ ているか？ ・ まずは、最も簡単な方法、が何かを見てみよう 素朴な方法 ・ うまくやっていない方法 ＝＞素朴な方法、とよぶことにしましょう ・ ここでは、素朴な方法は、解の全ての可能性を、つぶさに調べる こととしよう － a1,…,an の中で、値が b より小さいものを全部出力する場合： a1,…,an を２つに分ける組合せを全て調べ、 b より大きいものと 小さいものに分かれていたら、その場合に出力する － ソートの場合： 全ての並べ方を調べて、小さい順（大きい順）になっているもの を見つけたら出力する － a1,…,an の列の中で、最長部分降順列を求める場合： a1,…,an の組合せを全て調べ、 大きい順になっているものの中 で最も長いものを出力する 素朴な方法の時間 － a1,…,an の中で、値が b より小さいものを全部出力する場合： － a1,…,an の列の中で、最長部分降順列を求める場合： 計算時間は O(n2n) － ソートの場合： 計算時間は O(n n!) ≒ O(n2n logn) － こういった、入力の大きさに対して、計算時間が指数的に大きく なるものを、指数時間といい、計算時間が指数時間であるアル ゴリズムを指数時間アルゴリズムという 実際、うまくやると － a1,…,an の中で、値が b より小さいものを全部出力する： 頭から１つずつ調べて、 b より小さいものだけ出力する 計算時間は O(n) － a1,…,an の列の中で、最長部分降順列を求める場合： 昇順で各 ai について、 ai が最後になるような a1,…,ai の最長 部分降順列を求める。その後、全てのai の中から最大のものを 求める。 計算時間は O(n2) － ソートの場合： 列をスキャンして、となりあう２つが逆順になっていたら入れ替 える、という作業を n 回すれば、ソートされる。 計算時間は O(n2) 実際、うまくやると 計算時間は O(n) 計算時間は O(n2) 計算時間は O(n2) ・ 指数時間になっていない ・ このように、計算時間が入力の多項式であるとき、多項式時間と いい、多項式時間で計算が終了するアルゴリズムを多項式時 間アルゴリズムという ・ どんなに次数の大きな多項式でも、指数よりは小さいので、本質 的に両者の間には差がある つまり、ある程度は、「多項式時間なら、うまくやっている」と 思っていいだろう 問題の難しさ ・ うまいアルゴリズムがあれば、例えば多項式時間のアルゴリズ ムがあれば、問題は短時間で解ける ・ つまり、（多項式時間）アルゴリズムの存在性は、問題の難しさ の指標になる 難しさがわかれば、アルゴリズム開発の見通しがよくなる 多項式アルゴリズムがあれば、問題は（ある意味で）易しい 多項式アルゴリズムがなければ、問題は難しいだろう（必ず とはいえない。多項式アルゴリズムがあるかもしれないから） ・ すると、問題を２つ持ってきて、どちらが難しいのか、という議論 ができるようになる 厳密な比較 ・ 問題の難しさの比較をするには、比較する問題を解くアルゴリ ズムの計算時間を、オーダーの意味で比較すればよい ・ しかし、厳密には、これでは不十分 もっとよいアルゴリズムが作れるかも知れない ・ では、万能ではないが、 「こうなれば、確実に比較できる」という特殊ケースを考えよう 問題の帰着 ・ 問題 A と問題 B があり、問題 B を変換すると、問題 A になる、あ るいは、問題 A を解くと、＋αの時間で問題 B が解けるとする ・ n 個の数の中から、k 番目に大きな要素を見つける問題 ソートすると、O(n) 時間で見つかる この問題は、ソートをつかって解ける ・ こういった、問題 B を問題 A に変換すること、あるいは問題 A を 解くことで解く方法を、「問題 B を問題 A に帰着する」という ・ このとき、問題 B のほうが、＋α以上の時間がかかる限り、問題 A より易しい ・ 入出力に必ず O(n) 時間かかるので、上の例だと、ソートのほうが 難しい 難しい問題は ・ 速く解ける問題は、アルゴリズムを示すことで、簡単に示せる ・ では、難しい問題はどうやって示せばいいだろう ・ 「必ず指数時間かかる問題」を見つけるのは難しい ・ では、多項式時間、指数時間かかりそうな問題の中で、最も難 しい問題を見つけよう 先の問題の比較方法を使って、「これらの任意の問題は、 多項式時間で帰着できる」という問題を作る ・ こんな都合のいい問題があるだろうか？ 充足可能性問題 ・ こんな都合のいい問題があるだろうか？ 実はある。充足可能性問題 ・ 充足可能性問題とは、変数 x1,…,xn からなる論理式を満たす解があ るかどうかを判定する問題 変形して、連言標準形にしてあると思ってよい ・ トリックは、コンピュータの回路を、論理式で記述できる、ということ ・非決定性チューリングマシンといって、簡単に言えば指数個の可能性 を平行して調べられるコンピュータの動作を論理式でシミュレートでき る ・ 組合せ的な難しい問題が、このマシンなら多項式時間で解ける ・ その解ける問題の中で、充足可能性問題は一番難しいことになる （通常のコンピュータなら、指数時間かかりそう） 難しさの証拠 ・ 充足可能性問題は、難しい問題のランドマーク この問題より難しければ、難しそう ・ 充足可能性問題より難しい問題を、NP困難問題とよぶ ・ 非決定性チューリングマシンで、多項式時間で解ける問題をNP 問題とよぶ ・ NPの問題で、 NP困難問題であるものをNP完全問題とよぶ ・ NP問題の中で、最も難しい問題の部分がNP完全問題 SAT 3SAT ・ 充足可能性問題は、各節にちょうど３つ変数が入っている、という 条件をつけても、NP完全 SAT問題は、3SAT問題に帰着できるから （充足可能性問題をSAT、ちょうど３つ、のを3SATとよぶ） ・ 各節に対して、 －その節の大きさが１～２なら、人工変数を導入して、その人工 変数の任意の値のとり方に対して節を用意する (x) (x∨y∨z) ∧ (x∨￢y∨z) ∧ (x∨y∨ ￢z) ∧ (x∨￢y∨￢z) －その節の大きさが４以上なら、各変数に対して節を用意して、 人工変数で２つをつなぐ (a∨b∨c∨d∨e∨f) (a∨b∨x)∧ (￢x∨c∨y)∧ (￢y∨d∨z)∧ (￢z∨e∨f) SAT kクリーク ・ グラフの頂点集合が、全ての頂点の組の間に枝がある、という ようになっているとき、それをクリークという グラフが大きさ k のクリークを含むかどうか判定する問題にも、 SATが帰着できる ・ 各節の各変数に対して、頂点を１つ用意する ・ 違う節の、変数に対応する頂点の間に枝を張る。ただし、片方 が、片方の否定になっているときはそうしない ・ kクリークがある 問題の中で、最も難しい問題の部分が NP 困難問題 独立集合問題 独立集合： グラフ G の頂点部分集合で、任意の頂点間に枝のないもの ・ 与えられたグラフが大きさ k の独立集合を持つかどうかを判定 する問題が、k-独立集合問題 ・ 排他制約の親分のような問題 （排他制約のみからなる問題） ・ どうやってNP困難性を 証明しようか？ ・ SATを帰着してみよう 排他条件を使った選択肢 ・ SATの、「リテラル xiか￢xi のどちらしか選べない」という条件は 比較的簡単に実現できる xi に対応する頂点と ￢xi に対応する頂点を作り、両者の間 に枝を張る ＋ これらの頂点から n 個選ばせるようにすると、 xi と ￢xi のど ちらかを必ず選ぶことになる ・ 各節が充足されるという 条件はどうしようか xi ￢xi ・ 各節に頂点を対応させて、その節のリテラルどれかが選ばれて いれば、節の頂点が選べる、としたいが、排他条件でこういう セッティングをどうやって作ろうか？ 節の表現 ・ 単純に各節に頂点を対応させて、その節に含まれるリテラルと 辺でつなげてみる x4 Ci ・ 節が充足されている（リテラルを どれか選んでいる）と、Ci は選べない x1 ￢x3 ・ 節が充足されていない（リテラルを どれも選んでいない）と、Ci は選んでも選ばなくてもいい ・ やりたいことと逆だ 条件が逆ならば、個数の制限をつけるだけで帰着ができる 選択肢の逆転 ・ 選択肢を逆にする、逆転の発想をしてみよう 割当てとして選択するリテラルの否定を、独立集合の頂点と して選ぶ。つまり、各リテラルの否定を選ぶ ・ 節が充足されている（リテラルの どれか選ばれていない）と、Ci は選べない ・ 節が充足されていない（リテラルを 全て選んでいる）と、Ci は選べない x4 Ci x1 ￢x3 ・ 今度は、どちらの状況でも節が選べなくなった ・ もう一工夫して、リテラルどれかが選ばれてなければ節が選べ る、としたい 節の変形 ・ リテラルが１つ選ばれていないときに節の頂点を選べるようにし たいのだから、各リテラルに対して頂点を用意しよう ・ 節に対応する頂点が複数になるので、それらのうちから１つだ けしか選べないようにしよう これは、独立集合の状況では簡単 x4 Ci 節に対応する頂点たちをクリークにして Ci x1 しまえばよい Ci ￢x3 ・ リテラルどれかが選ばれていなければ、節を選ぶことができる 帰着のまとめ ・ 帰着する問題は SAT 入力： 変数 x1,…,xn、節 C1,…,Cm、節はリテラル（xi,￢xi）の集合 ・ 以下のグラフを作成する 頂点集合： リテラル xi,￢xi の集合と、節 Ci と Ci に含まれるリテ ラル xj の組 (Ci, xj) の集合 枝集合： 任意の Ci を共有する頂点対 (Ck, xi) と (Ci, xj) の間に 枝を張る。任意のリテラル xj と xj を含む節頂点 (Ci, xj) の間に 枝を張る ・ 作ったグラフに大きさ n+m の独立 集合がある 入力した SAT に 充足可能解がある （頂点被覆で作ったグラフと同じ。。。） Ci x4 Ci x1 Ci ￢x3 他の帰着 ・ 各節からリテラルを１つだけ選ぶ、という考え方もある 相補的なリテラルは選べないよう、枝を張っておく 入力： 変数 x1,…,xn、節 C1,…,Cm、節はリテラル（xi,￢xi）の集合 ・ 以下のグラフを作成する 頂点集合： 節 Ci と Ci に含まれるリテラル xj の組 (Ci, xj) の集合 枝集合： x = ￢y 、あるいは、C = C' が成り立つ (C, x) と (C', y) の間に枝を張る ・ 作ったグラフに大きさ m の独立 集合がある 入力した SAT に 充足可能解がある x4 ￢x1 x1 ￢x1 ￢x3 x3 SAT kクリーク ・ グラフの頂点集合が、全ての頂点の組の間に枝がある、という ようになっているとき、それをクリークという グラフが大きさ k のクリークを含むかどうか判定する問題にも、 SATが帰着できる ・ 各項の各変数に対して、頂点を１つ用意する ・ 違う項の、変数に対応する頂点の間に枝を張る。ただし、片方 が、片方の否定になっているときはそうしない ・ kクリークがある 問題の中で、最も難しい問題の部分が NP 困難問題 どこまでうまくできるか ・ うまくアルゴリズムを作ると、指数時間を多項式時間にできる ・ しかし、多項式には次数がある 次数が小さくなれば、それだけ速くなる ・ では、どこまで「うまく」できるのだろうか つまりは、どこまで次数を下げられるのだろうか？ ・ つまり、問題の本質的な難しさ、というものがあるはず ・ 例えば、問題を入力するのにかかる時間、O(n) は自明な下界 モデルを決める ・ まずは、計算機の能力を決め（モデル化し）ないといけない 問題専用のコンピュータを作れば、いくらでも速くできる ・ 例えば、n 個の要素の中から最大のものを見つける、という問 題を考える ・ 普通に考えれば、問題を入力するのにかかる時間、O(n) は自 明な下界だが、並列計算機を使うと、この限りではない ・ 変な例だと、人間は定数時間で数を２倍に増やせるので、 O(log n) 時間で O(n) 人に増えた後、トーナメント方式で最大 を求めると、 O(log n) 時間で見つけられる 演算の１単位 ・ コンピュータの基本動作は、メモリの読み書きと判定による条 件分岐 では、この操作を演算の１単位としよう ・ この条件で、問題が「最低」1単位の演算を、オーダーの意味で 何回する必要があるか、考えてみる － 検索： n 個の中から、最大、最小、ある値 k に最も近いものを 選ぶ － ソート： n 個の数の列を、大きい順に並び替える 演算の１単位 ・ 考え方はいろいろとあると思うが、観察として、 「条件分岐は一回で２つにしか枝分かれしないので、 n 種類の答 えを出すアルゴリズムは、少なくとも O(n) 回の分岐があるはず バランスをとって、最悪の場合が最小になるようにしても、log2 n 回 の条件分岐は避けられない ・ 検索： n 個の中から、ある値 k に最も近いものを選ぶ 答えの可能性は n 通りなので log2 n 以上かかる － ソート： n 個の数の列を、大きい順に並び替える 答えの可能性は n! 通りなので nlog2 n 以上かかる まとめ ・ コンピュータの基礎： CPUとメモリに、I/Oがついたもの。外部 記憶が階層的になっている ・ アルゴリズムの基礎： 手続きを順番に記述したもの ・ オーダーの定義： 係数を無視して、計算時間増大の、傾きの 大きさに注目 ・ 計算量理論の基礎： 多項式時間、NP 完全と計算時間の下界
© Copyright 2024 ExpyDoc
