コンピュータアルゴリズム2 0. イントロダクション田浦 http://www.logos.ic.i.u-tokyo.ac.jp /~tau/lecture/computer_software/ 講義の主題  ソフトウェア・プログラム・アルゴリズムの「基礎」  ...の「基礎」とは何か?  いわゆる「プログラミングの基本」(Cの構文, 配列, 構造体, ポインタ, etc.)のみのことにあらず  もう少し「科学的・数学的な基礎」アルゴリズムって何? (=プログラムのこと ??)   両者の厳密な線引きにさほど意味はない強いて区別すると，アルゴリズムとは，  明確に定義された問題を解くための「決まった計算手順」     最大公約数を求めるユークリッド互除法筆算連立一次方程式の解き方だがその「決まった手順」を実際に曖昧さなく表現するにはプログラムを用いる   その意味でアルゴリズムとプログラムの違いに神経質になる必要はない「スクリーンセーバ」のように, アルゴリズムとは言えないプログラム(きちんと定義された問題を解いているとは言い難い)もある要するに, 「問題をきちんと定義して, それを解くプログラムを考える」のがアルゴリズムの勉強基本的な問題の例     [探索]  スペルチェッカー：間違った単語(辞書にない単語)を見つける  検索エンジン：与えられた単語を含むページを見つける [整列]  表計算ソフト：データの昇順・降順の並び替え  検索エンジン：スコアの順にページを並べる [文字列]  grep：ファイル中の文字列やパターン(正規表現)を見つける  コンパイラ：プログラムの構文チェック(文法規則にあわない文字列を見つける) [グラフ]  路線検索：出発点から到着点までの最短路を見つける  インターネットのパケット配送：目的ホストまでの正しい道(最短路)を見つけるアルゴリズムの基礎とは? (1)      正しさを議論・証明できること計算量(速度，メモリ消費量)を議論できることいくつかの「基本的・常識的な」アルゴリズムを知ること  探索，整列，グラフ，文字列  何にどのくらいのコストがかかるかを知り, 新しい問題を効率よく(速く, 少ないメモリで)解く材料とするそれらの応用を知る，現実の問題解決へ役立てること未知の問題を解く際の有用な発想法(パターン)をいくつか体得すること  分割統治法，動的計画法，分枝限定法アルゴリズムの基礎とは? (2)  アルゴリズム(コンピュータ)の「根本的な限界」を知ること  問題の「クラス」 P, NP, 決定不能     「決して解けない問題」がある実用的な計算時間では解けないだろうと信じられている数多くの問題 = NP困難 P=NP? という計算機科学最大の未解決問題を知ることそれら(実用的な計算時間 etc.)の概念がどのように定式化されているか?  Pentium Proでは実用的でなかったreal time MPEG encodingがXeonだと...という話とは違うアルゴリズムの基礎とは? (3)  そうはいってもやはりプログラミング  いくつかのアルゴリズムを題材にプログラミングの実践      アルゴリズムを教えられたらコーディングできるようになる速いアルゴリズムと遅いアルゴリズムの差の体感出来合いの「ライブラリ」(Java, C, C++ STL, Python, etc.)を知るそれらとの勝負理論的な計算量(速度)予測と実際の比較アルゴリズム序論   アルゴリズムの「正しさ」「計算量」を正確に議論するための問題設定講義で扱う話題用語定義(1)  「アルゴリズム」  計算手順をあいまいさなく記述したもの     実際にはプログラムのことだと思えばよいさしあたってCの基本的な部分を想像すればよい「問題」  プログラムの初期状態(入力)において成立している関係  プログラムの最終状態(出力)が満たすべき関係「問題の実例(インスタンス)」  プログラムに対する特定の初期状態(入力) 用語定義(2)  ある問題を解く(正しい)アルゴリズム  その問題のすべてのインスタンスについて，    有限時間(ステップ数)で終了し，指定された関係を満たす出力を与えるプログラムのこと「問題」は「すべてのインスタンス」を含んでいることに注意  「すべての入力」に対して正解して初めて「正しいアルゴリズム」と呼ばれるプログラムPが「正しい」とは，初期状態プログラムの変数に関するある条件式(A) プログラム(P)：ある規則(プログラミング言語)に従ったプログラムの変数の書き換え最終状態プログラムの変数に関するある条件式(B) プログラムの変数が条件Aを満たす状態で Pを実行すると， 1. 必ず有限時間で停止し， 2. そのとき条件Bを満たすこと問題例：2数の最大公約数  日本語での問題記述：与えられた2整数(a, b)の最大公約数を求める  初期状態： a = a, b = b, a > 0, b > 0  最終状態： g = aとbの最大公約数 “P, Q” は “PかつQ” の意味とする問題例：整数列を整列する  日本語での問題記述：整数nとn要素の配列aが与えられたとき，aを昇順に並び替える  初期状態： n = n, a[0] = a0, a[1] = a1, ..., a[n – 1] = an – 1  最終状態：マルチ集合(重複を区別)とする { a[0], a[1], ..., a[n – 1] } = {a0, a1, ..., an – 1 }, a[0]  a[1]  ...  a[n – 1] 問題例：文字列の検索  日本語での問題記述：文字列(配列)aの中で，部分文字列bがあるか判定し，あればその場所を見つけよ  初期状態： n = n, a[0] = a0, ..., a[n – 1] = an – 1 , m = m, b[0] = b0, ..., b[m – 1] = bm – 1  最終状態： (i = n  P(i))  (x < i P(x)) ただし P(x)  ax = b0, ax+1 = b1, …, ax+m–1 = bm–1   以降，「プログラムの正しさ」に関する議論を厳密に展開するならば， 1. プログラミング言語の文法の定義 2. その言語の意味(ある文を実行するとプログラム変数の状態がどう変わるか)の厳密な定義 3. それに基づいたアルゴリズムの正しさの厳密な証明を展開することになるが，本講義では1. 2. に時間をとることはせず，CやJavaの基本的な部分と，すでにおおよそ知っている(はずの)意味にしたがって3.の議論を準フォーマルに行う  プログラムは正しいことが重要だが，正しければ言いというものではないという話  計算量計算量(Complexity)    アルゴリズムの性能(良し悪し)を論ずる尺度時間計算量(time complexity)   プログラムの実行時間空間計算量(space complexity)   プログラムの使用メモリ量   プログラムが使用する変数・配列の要素の数(だいぶ不正確な言い方) しかし...    明らかに実際の実行時間(○○.○○秒)などが，アルゴリズムの記述(だけ)からわかるはずがない  計算機そのものの速度・癖に依存する  プログラム言語にも依存する  そして実際，同じプログラムですらもわずかにばらつく仮に特定の計算機上での実行時間を細かく予測できたとしても，その計算機上でしか通用しない結論であれば「アルゴリズムの」良し悪しを決める尺度とはいえないであろう  思い切った(解析に都合のよい)簡単化を行う簡単化(1)    プログラムに現れる「基本操作」はすべて単位時間かかるものとみなす  足し算，掛け算，比較，if文条件判定, etc.  実行「時間」というよりは実行「ステップ数」「演算数」この上で実行ステップ数を「入力の大きさの関数」として求める  例: 入力の大きさn (n個の変数)に対して実行時間 = n2 + 3n + 4  注：入力の大きさが決まっても実行時間が一意に決まるとは限らないので不正確な言い方(後述) これなら個々の計算機によらない尺度になりうるが... 簡単化(2)    このようにして求めた計算量の「係数」にさしたる意味はない  5n2 ステップと 34n2 ステップのどちらが実際の計算機で速いかが信頼度よく判定できるわけではない一方， 5n2 と 5n4の違いは係数によらず決定的に重要  十分大きなnに対しては「常に」前者が「圧倒的に」速いであろう良いアルゴリズムと悪いアルゴリズムの差は得てしてこのような決定的な違い(オーダーの違い)であって，これを捕らえることで満足する  5n2 と 34n2は同じもの簡単化(3)    どこまでを「基本操作」とみなすかも所詮は係数に影響を与えるに過ぎず，ほとんどの場合重要ではない「単一の演算」や「それらを一定個数組み合わせた操作」は適宜基本操作とみなしてもアルゴリズムの比較に影響しない  例: z = 3 * x + 4 * y; 「特定の演算や文の実行回数のみに注目し残りは無視する」こともしばしば行われる  例: 浮動小数点演算に単位時間，残りの演算には0時間  浮動小数点演算と残りの演算が一定範囲内の割合でmix されていれば，これも係数に影響を与えるに過ぎない時間計算量の議論の仕方(まとめ)    入力の関数として実行時間を上から押さえることに興味がある多くの場合，簡単のため入力の「大きさ」 (n : 入力のバイト数， bit数, etc.)の関数で，上から押さえることに興味があるその際，細かい係数に興味はなく，したがって個々の基本操作にどのくらい時間がかかるかも問わずに大雑把な議論ができる  log n, n, n log n, n2, 2n, ... という「オーダーの違い」だけを捕らえる  f(n)はg(n)よりオーダーが大きい  n  のとき f (n) / g(n) が有界でない  入力の大きさが決まっても実行時間が一意に決まるとは限らない．目的によって主に以下の二つを使い分ける  最悪計算量：大きさnの最悪の入力に対する計算量  平均計算量：大きさnの入力に対する平均の計算量  断りなく用いるときは「最悪」をさすことが多い「オーダー」を表す記法    O(g(n)) : g(n)の定数倍で上から抑えられる関数の集合  ある定数 cが存在し，十分大きなnに対し常に f (n)  c g(n) となる関数f の集合  (g(n)) : g(n)の定数倍で下から抑えられる関数の集合  ある定数 cが存在し，十分大きなnに対し常に f (n)  c g(n) となる関数f の集合 (g(n)) : 両者の共通部分．つまり「g(n)のオーダー」の関数の集合  ある定数 c, c’ が存在し，十分大きな n に対し常に c g(n)  f (n)  c’ g(n) となる関数f の集合記号の正しい・間違った使い方        O(…), (…), (…)は関数の「集合」を表す 5n  O(n) 5n = O(n) O(5n) = O(n) 5n  O(n2) O(n2+n) = O(n2) O(n2) + O(n) = O(n2)   今後議論する多くの場合において，中心的な問いは，あるアルゴリズムの時間計算量が，どんな関数 f に対して  O(f(n)) となっているかという問いになる  高々 n の定数倍か?  高々 n log n の定数倍か?  高々 n2 の定数倍か?  高々 n3 の定数倍か?  高々 2nの定数倍か?  … 講義ではいくつかのアルゴリズムについて計算量の解析を行い，必要な数学の技法についても紹介する「よく出る」計算量     O(n) : 線形時間．例: 配列の和を求める O(n log n) : 例: マージソート，FFT O(n2) : 例: バブルソート O(2n) : 多くの組み合わせ最適化問題決定不能(計算不能)な問題・計算困難な問題   決定不能(計算不能)な問題  いかなるアルゴリズムでも正しく解くことはできない計算困難な問題  解けはするが，「時間がかかりすぎる」問題決定不能問題   いかなるアルゴリズムでも正しく解くことはできないいくつもの例が知られている  停止性判定：プログラムと入力(初期状態)が与えられ，実行が停止するかを判定する  整数係数多項式の整数解(ディオファンティン方程式)：多項式の係数 (整数)が与えられ，それが整数解を持つかを判定する  ポストの対応問題：文字列ペアの集合 S = { (a0, b0), (a1, b1), …, (an – 1 , bn – 1) } 対を任意個(同じのを何回選んでもよい)選んで，aの方，bの方それぞれ連結する．両者を一致させることができるかを判定する注：正確な理解(間違った拡大解釈をしないように)  正確な意味：ひとつの「決まりきった手続き(プログラム)で」その問題の「すべてのインスタンスに」正解を出すことはできない  停止性：ひとつの(固定された)プログラムで「すべてのプログラム，すべての入力」に対して必ず停止して，正しく「停止/非停止」を判定するプログラムは存在しない  ディオファンティン：ひとつの(固定された)プログラムで「あらゆる整数係数多項式」に対して必ず停止し，正しく整数解の「存在/非存在」を判定するプログラムは存在しない   「人類の叡智を集めても決して解のあるなしが判定できない多項式が存在する」というのとは違うましてや，この問題が決定不能だからFermat予想は証明できないなんてのは「トンデモ」の類計算困難な問題   易しい・難しいの線引き  易しい(クラスP) ：問題の大きさnに対しnの多項式時間で解けるアルゴリズムが存在する時間計算量f (n)がある定数によって f (n)  O(n)となる  難しい(クラスco-P) ：そうではない問題易しい問題の例  整列，文字列検索，etc. 困難な問題   世の中にはPに入らない(難しい)ことが証明されているいくつかの問題が存在する一方，易しい(Pに入る)かどうかわかっていない問題があまりにも数多く存在する  誰も多項式時間アルゴリズムを発明していない  しかしそのようなアルゴリズムが「存在しない」も証明されていない  そのような問題の多くがNPというクラスに属するクラスPに属すかどうか，わかっていない多数の問題の実例      充足可能性問題(SAT)： n変数の命題論理の式(変数が0 or 1の値のみをとる式)が，適当に変数の値を決めることによって真となる(充足可能)か? グラフ彩色(k-COLORING)： (日常的な言い換え) n人の人と k個の部屋がある．人同士の敵対関係が与えられている．「敵対する人同士を同じ部屋に入れずに，全員をk個の部屋に収納できるか? 巡回セールスマン(TSP) ： n個の都市と都市間の運賃，総予算が与えられている．すべての都市を予算以下で回れるか? これらはすべて次に述べるNPというクラスに属している ... (その他数千の実例が知られている) ... クラスNP   ある条件を満たす解のある(1)，なし(0)を判定する問題を考える非決定的なプログラミング言語：複数の文の中から非決定的に選択して実行という不思議な文を持つ言語を考える  either S1 or S2 or ... or Sm; (Si の中からどれかを選択)  しかもその選択は「神様がベストの選択をしてくれる」とする    どれかが解を見つけたら(1を返したら)解が見つかったとみなすどれも解を見つけなかったら(すべてが0を返したら)解が見つからなかった NP : この非決定的なプログラミング言語で多項式時間で解ける問題  NP : Non-deterministic Polynomial (非決定的多項式時間)  「あり得ないほど強力なコンピュータ」なら多項式時間で解ける  じゃあそれは「現実のコンピュータ」だと多項式時間で「解けない」ということ? それはまだ分かっていない! (P = NP問題) 本講義で学んでほしいこと       アルゴリズムの正しさの議論アルゴリズムの計算量の重要さプログラミングを通した練習  アルゴリズム  プログラム  計算量と実際の性能決定不能な問題という概念 P, NPという問題のクラス  特にNPの正しい理解と実例  せっかくだからP=NP問題を人に説明できる子になろうなど