授業展開#12
コンピュータの扱いにくい問題
扱いにくい問題
 処理時間がかかる。
 メモリを大量に必要とする。
 プログラムの優劣、アルゴリズムの優劣を比
較するためには、標準的なコンピュータで比
較する必要がある。
 処理時間を計るのに、コンピュータのモデル
として、チューリングマシンを考え、動作の系
列の長さで表す。 → 時間計算量
問題の大きさと処理時間
 問題の大きさの特徴量(指標)「n」
「n」桁の数の加算
「n」桁の数の乗算
「n」個の名前の名簿の並び替え
 「n」が変化したときの処理量の関係を調べる。
nが2倍、3倍になったときの処理スピードが
どうなるのかは、アルゴリズムの問題。
加算の計算量
 2つの「n」桁の整数の加算
加算は1桁の整数の加算をn段重ねたもの
下の桁から順次計算してゆく
→ 計算量はおおよそ「n」に比例する
乗算の計算量
 乗算は1桁のかけ算と加算の繰り返し、およ
び桁ずらしを基本処理として、それらを組み
合わせる。
 1桁のかけ算と加算は乗数の各位ごとに被
乗数の桁数の「n」回あり、それを乗数の「n」
桁分おこなう。
→ 計算量はおおよそn2に比例する
整数の加算と乗算の計算量の見積
86725
+63798
13
11
14
19
14
160523
×
345
678
40
32
24
35
28
21
30
24
18
233910
シフト
シフト
n個のデータのソート
 ソートの基本操作は2つのデータの比較であ
る。
 勝ち抜き法での単純ソートで、全部決めるの
に必要な比較回数は、
(n-1)+(n-2)+...+2+1=n(n-1)/2
 nが大きいところでは、だいたいn2に比例
ナップザック問題
いろいろな重さで価格も様々な荷物があり、この中
からいくつかを1つのナップザックに入れる。
 ナップザックに入れられる重量には上限がある。
 制限重量以内で価格の総和が最大になるような荷
物の詰め方を求める。
 あらゆる可能な荷物の組み合わせは、荷物がn個
の場合、2n通り

→ 計算量はおおよそn×2nで増大する
巡回セールスマン問題
 セールスマンが、いくつかの地方都市を1度
だけ順に訪問し、はじめの都市に戻ってくる
場合、総移動距離が最小になる訪問順路を
求める。
→ 順路は(nー1)!通り
C
F
B
C
F
B
E
E
G
A
D
G
A
D
計算量のクラス
ある問題を解くアルゴリズムの時間計算量が
 「n」に依存しない場合
→ 時間計算量(1)のクラス
 「n」に比例する場合
→ 時間計算量(n)のクラス
 「n2」に比例する場合
→ 時間計算量(n2 )のクラス
 「nk」、k=1,2,3・・・に比例する場合
→ 多項式時間計算量のクラス
(P問題のクラス、クラスP)
NP問題
 1台のコンピュータでなく、多数並列して実行
したときに、多項式時間計算量で処理できる
問題を、NP問題のクラス、クラスNPという。
 例 ナップザック問題:
時間計算量は、だいたいn×2nに比例
2n台のコンピュータを同時に使うことができ
れば、時間計算量は、nに比例
→ 多項式時間計算量となる。
→ NP問題
NP完全問題
 NP問題で、どうアルゴリズムを工夫しても多項
式時間計算量にならない問題を、NP完全問題
という。
 とても難しい問題。
ナップザック問題
セールスマン巡回問題
手におえない問題
時間計算量(1)クラス
コンピュータが早くなれば、計算時間は短くなる。
 時間計算量(n)クラス
コンピュータのスピードが倍になれば、同じ時間で
倍の大きさの問題が解ける。
 時間計算量(n2)クラス
nが倍になると時間が4倍かかる。スピードが4倍
にならないと、同じ時間で倍の大きさの問題が解け
ない。
 NP問題
指数関数的に時間計算量が増大。

指数関数と多項式
アルゴリズムA:2n
:指数関数時間計算量
 アルゴリズムB:1000×n5 :多項式時間計算量


もし、1秒に1憶回の演算をする計算機を使うと、問題
を解くのにかかる時間は以下の通り。
データ数
アルゴリズム
A
B
10
90
10万分の1秒
4千億年
1秒
16時間
ダウンロード

授業展開#10