授業展開＃１２ コンピュータの扱いにくい問 題

扱いにくい問題  処理時間がかかる。  メモリを大量に必要とする。  プログラムの優劣、アルゴリズムの優劣 を比較するためには、標準的なコン ピュータで比較する必要がある。  処理時間を計るのに、コンピュータのモ デルとして、チューリングマシンを考え、 動作の系列の長さで表す。 → 時間計 算量

問題の大きさと処理時間  問題の大きさの特徴量（指標）「ｎ」 「ｎ」桁の数の加算「ｎ」桁の数の乗算「ｎ」個の名前の名簿の並び替え  「ｎ」が変化したときの処理量の関係を 調べる。 ｎが 2 倍、３倍になったときの処理ス ピードがどうなるのかは、アルゴリズム の問題。 ｎが 2 倍、３倍になったときの処理ス ピードがどうなるのかは、アルゴリズム の問題。

加算の計算量  ２つの「ｎ」桁の整数の加算 加算は１桁の整数の加算をｎ段重ねたもの下の桁から順次計算してゆく → 計算量はおおよそ「ｎ」に比例す る → 計算量はおおよそ「ｎ」に比例す る

乗算の計算量  乗算は１桁のかけ算と加算の繰り返し、 および桁ずらしを基本処理として、それ らを組み合わせる。  １桁のかけ算と加算は乗数の各位ごとに 被乗数の桁数の「ｎ」回あり、それを乗 数の「ｎ」桁分おこなう。 → 計算量はおおよそｎ ２ に比例する → 計算量はおおよそｎ ２ に比例する

整数の加算と乗算の計算量の見積 ８６７２５ ＋６３７９８ １３ １１ １４ １９ １４ １６０５２３ ３４５ × ６７８ ４０ ３２ ２４ ３５ ２８ ２１ ３０ ２４ １８ ２ 33 ９１０ シフト

ｎ個のデータのソート  ソートの基本操作は２つのデータの比較 である。  勝ち抜き法での単純ソートで、全部決め るのに必要な比較回数は、 (n-1)+(n-2) =n(n-1)/2 (n-1)+(n-2) =n(n-1)/2  ｎが大きいところでは、だいたい n 2 に比 例

ナップザック問題  いろいろな重さで価格も様々な荷物があり、こ の中からいくつかを１つのナップザックに入れ る。  ナップザックに入れられる重量には上限がある。  制限重量以内で価格の総和が最大になるような 荷物の詰め方を求める。  あらゆる可能な荷物の組み合わせは、荷物がｎ 個の場合、２ ｎ 通り → 計算量はおおよそｎ × ２ ｎ で増大する → 計算量はおおよそｎ × ２ ｎ で増大する

巡回セールスマン問題  セールスマンが、いくつかの地方都市を １度だけ順に訪問し、はじめの都市に 戻ってくる場合、総移動距離が最小にな る訪問順路を求める。 Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ → 順路は（ｎー１）！通り

計算量のクラス ある問題を解くアルゴリズムの時間計算量が  「ｎ」に依存しない場合 → 時間計算量（１）のクラス → 時間計算量（１）のクラス  「ｎ」に比例する場合 → 時間計算量（ｎ）のクラス → 時間計算量（ｎ）のクラス  「ｎ ２ 」に比例する場合 → 時間計算量（ｎ ２ ）のクラス → 時間計算量（ｎ ２ ）のクラス  ｢ｎ ｋ ｣、ｋ＝１，２，３・・・に比例する場合 → 多項式時間計算量のクラス → 多項式時間計算量のクラス （Ｐ問題のクラス、クラスＰ）

 1 台のコンピュータでなく、多数並列して 実行したときに、多項式時間計算量で処 理できる問題を、 NP 問題のクラス、クラ ス NP という。  例 ナップザック問題： 時間計算量は、だいたいｎ ×2 n に比例 時間計算量は、だいたいｎ ×2 n に比例 2 n 台のコンピュータを同時に使うこと ができれば、時間計算量は、ｎに比例 2 n 台のコンピュータを同時に使うこと ができれば、時間計算量は、ｎに比例 → 多項式時間計算量となる。 → 多項式時間計算量となる。 → NP 問題 → NP 問題 NP 問題

ＮＰ完全問題  ＮＰ問題で、どうアルゴリズムを工夫して も多項式時間計算量にならない問題を、Ｎ Ｐ完全問題という。  とても難しい問題。 ナップザック問題 セールスマン巡回問題

手におえない問題  時間計算量（１）クラス コンピュータが早くなれば、計算時間は短く なる。 コンピュータが早くなれば、計算時間は短く なる。  時間計算量（ｎ）クラス コンピュータのスピードが倍になれば、同じ 時間で倍の大きさの問題が解ける。 コンピュータのスピードが倍になれば、同じ 時間で倍の大きさの問題が解ける。  時間計算量（ n 2 ）クラス ｎが倍になると時間が４倍かかる。スピード が４倍にならないと、同じ時間で倍の大きさの 問題が解けない。 ｎが倍になると時間が４倍かかる。スピード が４倍にならないと、同じ時間で倍の大きさの 問題が解けない。  NP 問題 指数関数的に時間計算量が増大。

指数関数と多項式  アルゴリズム A ： 2 ｎ ：指数関数時間計算量  アルゴリズム B ：１０００ ×n ５ ：多項式時間計算 量  もし、 1 秒に 1 憶回の演算をする計算機を使うと、 問題を解くのにかかる時間は以下の通り。 デー タ数 デー タ数アルゴリズム１０９０ Ａ １０万分の１ 秒 ４千億年 Ｂ１秒１６時間