授業展開＃１２ コンピュータの扱いにくい問題 扱いにくい問題 処理時間がかかる。 メモリを大量に必要とする。 プログラムの優劣、アルゴリズムの優劣を比 較するためには、標準的なコンピュータで比 較する必要がある。 処理時間を計るのに、コンピュータのモデル として、チューリングマシンを考え、動作の系 列の長さで表す。 → 時間計算量 問題の大きさと処理時間 問題の大きさの特徴量（指標）「ｎ」 「ｎ」桁の数の加算 「ｎ」桁の数の乗算 「ｎ」個の名前の名簿の並び替え 「ｎ」が変化したときの処理量の関係を調べる。 ｎが2倍、３倍になったときの処理スピードが どうなるのかは、アルゴリズムの問題。 加算の計算量 ２つの「ｎ」桁の整数の加算 加算は１桁の整数の加算をｎ段重ねたもの 下の桁から順次計算してゆく → 計算量はおおよそ「ｎ」に比例する 乗算の計算量 乗算は１桁のかけ算と加算の繰り返し、およ び桁ずらしを基本処理として、それらを組み 合わせる。 １桁のかけ算と加算は乗数の各位ごとに被 乗数の桁数の「ｎ」回あり、それを乗数の「ｎ」 桁分おこなう。 → 計算量はおおよそｎ２に比例する 整数の加算と乗算の計算量の見積 ８６７２５ ＋６３７９８ １３ １１ １４ １９ １４ １６０５２３ × ３４５ ６７８ ４０ ３２ ２４ ３５ ２８ ２１ ３０ ２４ １８ ２33９１０ シフト シフト ｎ個のデータのソート ソートの基本操作は２つのデータの比較であ る。 勝ち抜き法での単純ソートで、全部決めるの に必要な比較回数は、 (n-1)+(n-2)+...+2+1=n(n-1)/2 ｎが大きいところでは、だいたいn2に比例 ナップザック問題 いろいろな重さで価格も様々な荷物があり、この中 からいくつかを１つのナップザックに入れる。 ナップザックに入れられる重量には上限がある。 制限重量以内で価格の総和が最大になるような荷 物の詰め方を求める。 あらゆる可能な荷物の組み合わせは、荷物がｎ個 の場合、２ｎ通り → 計算量はおおよそｎ×２ｎで増大する 巡回セールスマン問題 セールスマンが、いくつかの地方都市を１度 だけ順に訪問し、はじめの都市に戻ってくる 場合、総移動距離が最小になる訪問順路を 求める。 → 順路は（ｎー１）！通り Ｃ Ｆ Ｂ Ｃ Ｆ Ｂ Ｅ Ｅ Ｇ Ａ Ｄ Ｇ Ａ Ｄ 計算量のクラス ある問題を解くアルゴリズムの時間計算量が 「ｎ」に依存しない場合 → 時間計算量（１）のクラス 「ｎ」に比例する場合 → 時間計算量（ｎ）のクラス 「ｎ２」に比例する場合 → 時間計算量（ｎ２ ）のクラス ｢ｎｋ｣、ｋ＝１，２，３・・・に比例する場合 → 多項式時間計算量のクラス （Ｐ問題のクラス、クラスＰ） NP問題 1台のコンピュータでなく、多数並列して実行 したときに、多項式時間計算量で処理できる 問題を、NP問題のクラス、クラスNPという。 例 ナップザック問題： 時間計算量は、だいたいｎ×2nに比例 2n台のコンピュータを同時に使うことができ れば、時間計算量は、ｎに比例 → 多項式時間計算量となる。 → NP問題 ＮＰ完全問題 ＮＰ問題で、どうアルゴリズムを工夫しても多項 式時間計算量にならない問題を、ＮＰ完全問題 という。 とても難しい問題。 ナップザック問題 セールスマン巡回問題 手におえない問題 時間計算量（１）クラス コンピュータが早くなれば、計算時間は短くなる。 時間計算量（ｎ）クラス コンピュータのスピードが倍になれば、同じ時間で 倍の大きさの問題が解ける。 時間計算量（n2）クラス ｎが倍になると時間が４倍かかる。スピードが４倍 にならないと、同じ時間で倍の大きさの問題が解け ない。 NP問題 指数関数的に時間計算量が増大。 指数関数と多項式 アルゴリズムA：2ｎ ：指数関数時間計算量 アルゴリズムB：１０００×n５ ：多項式時間計算量 もし、1秒に1憶回の演算をする計算機を使うと、問題 を解くのにかかる時間は以下の通り。 データ数 アルゴリズム Ａ Ｂ １０ ９０ １０万分の１秒 ４千億年 １秒 １６時間
© Copyright 2024 ExpyDoc
