Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


Presentation on theme: "授業展開#12 コンピュータの扱いにくい問 題. 扱いにくい問題  処理時間がかかる。  メモリを大量に必要とする。  プログラムの優劣、アルゴリズムの優劣 を比較するためには、標準的なコン ピュータで比較する必要がある。  処理時間を計るのに、コンピュータのモ デルとして、チューリングマシンを考え、"— Presentation transcript:

1 授業展開#12 コンピュータの扱いにくい問 題

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

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

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

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

6 整数の加算と乗算の計算量の見積 86725 +63798 13 11 14 19 14 160523 345 × 678 40 32 24 35 28 21 30 24 18 2 33 910 シフト

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

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

9 巡回セールスマン問題  セールスマンが、いくつかの地方都市を 1度だけ順に訪問し、はじめの都市に 戻ってくる場合、総移動距離が最小にな る訪問順路を求める。 A B C D E F G A B C D E F G → 順路は(nー1)!通り

10 計算量のクラス ある問題を解くアルゴリズムの時間計算量が  「n」に依存しない場合 → 時間計算量(1)のクラス → 時間計算量(1)のクラス  「n」に比例する場合 → 時間計算量(n)のクラス → 時間計算量(n)のクラス  「n 2 」に比例する場合 → 時間計算量(n 2 )のクラス → 時間計算量(n 2 )のクラス  「n k 」、k=1,2,3・・・に比例する場合 → 多項式時間計算量のクラス → 多項式時間計算量のクラス (P問題のクラス、クラスP)

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

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

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

14 指数関数と多項式  アルゴリズム A : 2 n :指数関数時間計算量  アルゴリズム B :1000 ×n 5 :多項式時間計算 量  もし、 1 秒に 1 憶回の演算をする計算機を使うと、 問題を解くのにかかる時間は以下の通り。 デー タ数 デー タ数アルゴリズム1090 A 10万分の1 秒 4千億年 B1秒16時間


Download ppt "授業展開#12 コンピュータの扱いにくい問 題. 扱いにくい問題  処理時間がかかる。  メモリを大量に必要とする。  プログラムの優劣、アルゴリズムの優劣 を比較するためには、標準的なコン ピュータで比較する必要がある。  処理時間を計るのに、コンピュータのモ デルとして、チューリングマシンを考え、"

Similar presentations


Ads by Google