この一年間学んだ、ソフトウェア概論、如何がだったでしょうか?
一年次に、コンピュータ概論で、計算機(1)の利用方法を覚え、この二年次のソフトウェア概論で、Fortranという新しい計算機言語(2)を学び、(3)というものを初めて、自分で作ってみた方も多かったかと思います。
演習問題も沢山解き、少しは、Fortran Programが書けるようになったのではないかと思います(4)。
しかし、その一方、この科目を学んで、「確かに、FortranのProgramは作れるようになった。しかし、これって、何の役に立つの?」とか、「これで、どうやってGameが作れるかしら?」と疑問を持ちはじめた方も居ることでしょう。
結論からいえば、残念ながら、「ソフトウェア概論」で学んだ内容だけでは、上記の疑問の答は、いずれにせよ否定的なものにならざるを得ません(5)。
なぜなら、「ソフトウェア概論」で、学んだ内容は、実は、「Programを作成する」という目的としては、まだ、半分しかないからです。
「ソフトウェア概論」で学んだFortran (などの計算機言語)が利用できるようになったということは、「計算機に意図を伝える手段を得た」ということでしかありません。それは、丁度、英語に於ける基本的な単語と英文法を学んだ段階に過ぎません。もちろん、これだけあれば、米国に観光旅行をするには十分でしょうが、米国に住んで暮すとか、米国人とビジネス交渉ができるようにということにはなりません。
これは、単に、単語力の問題というより、米国の習慣や、典型的な慣用句等が別に存在し、それらを学ばない限り、より自然な、あるいは、明確な意図を伝えることができないからです。
計算機においても同様なことがおきます。Fortranという計算機言語で、片言の会話(6)ができるようになったからといって、直にProgrammerになれるわけではないのです。
実際に、役立つProgramがかけるようになるには、次年度に設置されている次のような科目で習う内容も必要(7)です。
本日の内容では、ソフトウェア概論から、アルゴリズム概論への橋渡しの話をしたいと思います。
ある問題のアルゴリズム(8)とは、簡単にいえば、「その問題を解くための手順」のことです。つまり、その手順に従えば、(自動的に..、)問題が解けるようなものということです。
ここでFortran Programを考えてみると、Programというのは、計算機に対して、計算する手順を(Fortranという言語形式で..)指示したものです。
つまり、その意味では、「ある問題を解くFortranのProgramを作成する」ということは、「その問題のアルゴリズムをFortran形式で記述する」(9)と解釈することができるわけです。
つまり、「Fortran Programを作成する」ということは、次の二つの作業が必要だということです。
与えられたアルゴリズムを(Fortran等の..) Programming言語の形に書き直す仕事をする人のことをCoder (コーダ:コード化する人.. )と呼びます。
つまり、ソフトウェア概論で学んだことは、ほぼ、Coder (ただし、Fortran専用.. )としての技能(の一部.. )を身に付けたことに相当します。
それに対して、Programmer (プログラマ: Programを書く人)という職業は、更に、今回説明する、アルゴリズム等を把握し、正しく適用したり、あるいは、小さな問題に関しては、アルゴリズムを自分で作成できる人ということになります。
アルゴリズムの定義を上記のような、大まかな形で考えれば、沢山の演習をこなした皆さんは、沢山のアルゴリズムをしっていることになります。しかし、一般には、そうはいいません。
一般に、手順が、アルゴリズムとよばれる為には、次のような条件が必要となります。
最初の二つに関しては、Fortran CompilerがErrorとしなければ、条件を満すことになります。また、実際に次の二つは、正しいProgramであるための条件となります。
つまり、これまでの演習では、最初の四つに関しては、色々と経験を積んだわけですが、最後の条件に関する経験に乏しく、そして、「アルゴリズム」と敢て述べるような手順は、この最後の条件を満すものなわけです。
では、最後の条件、即ち、「良い手順( =アルゴリズム)」とはなんでしょうか?これには、色々な観点があり、一言では言い切れないのですが、幾つか例を挙げると、次のような形になります。
以前は、効率がよいことが、重視されていましたが、現在は、むしろ、理解りやすく、変更が容易であることが重視されています。
ただし、一般にアルゴリズムという言葉を利用する場合は、効率の観点から選ばれることが多く、以下の議論でも、その観点で説明します。
効率の良い手順をアルゴリズムと呼びます。つまり、同じ問題を解く二つの手順があった場合、その手順の効率を比較して、より効率の良いものを特に選んでアルゴリズムと呼ぶわけですが、そのためには、効率を比較する必要があります。
効率に関しては、時間効率と空間効率の二つがありますが、以下では、単に時間効率だけを考えます。
実際に、Programができてしまえば、その二つのProgramを同じ計算機環境、同じ入力を与え、それぞれ実行し、その実行時間を比較すればよい(10)わけですが、一般に、アルゴリズムを考えている場合は、Program言語を仮定していない(11)ので、それもできません。
そこで、考えられたのが、オーダーという尺度で、これは、「入力のサイズが定義されており、そのサイズnに対して、実行時間T(n)が、n関数f(n)に関してnを無限大にしたときに( 0でない)定数倍になっている時にT(n)のオーダーはO(f(n))である」と定義します。
前期に行った(12)、虱潰し法のオーダーを幾つか考えてみましょう。
最大公約数を虱潰しで解くProgramは、次のようなものでした。
program gcm
integer m
integer n
integer mn
integer rm
integer rn
integer d
integer gcm
! 最大公約数を求める二つの数 ( m, n ) を入力する
write(*,*) '二つの数の最大公約数を求めます'
write(*,*) '一つ目の数 (m) を入力してください'
read(*,*) m
write(*,*) '二つ目の数 (n) を入力してください'
read(*,*) n
! 二つの数、m, n の内、大きくない方を mn に入れる
if ( m < n ) then
mn = m
else
mn = n
endif
! d を 1 - mn に変化させ虱潰しで、最大公約数を求める
gcm = 1 ! 最大公約数候補として、とりあえず 1 を考える
do d = 1, mn
rm = m - ( m / d ) * d ! rm は m を d で割った余り
rn = n - ( n / d ) * d ! rn は n を d で割った余り
if rm == 0 .and. rn == 0 then
! d が m と n を共に割切れるので公約数
gcm = d
endif
end do
write(*,*) m, 'と', n, 'の最大公約数は', gcm
end
このProgramでは、do文が一つあり、1からmnまで繰り返しを行っています。do文の中では、二つの数の余りの計算と、条件文が一つで、これは、定数時間に実行されますので、O(mn)と解釈できます。入力は、mとnの二つの整数で、mnはmとnの小さい方ですので、mまたはnそのものを入力サイズと考えれば、だいたいO(n)(13)というふうに考えることができます。
また、もし、nのビット長さをb ( n = 2^b )とすれば、O(2^b)のオーダーということになります。
今度は、互除法の場合を考えてみます。
program euclid
integer m
integer n
integer mm
integer nn
integer r
integer gcm
! 最大公約数を求める二つの数 ( m, n ) を入力する
write(*,*) '二つの数の最大公約数を求めます'
write(*,*) '一つ目の数 (m) を入力してください'
read(*,*) m
write(*,*) '二つ目の数 (n) を入力してください'
read(*,*) n
mm = m
nn = n
do
if ( nn == 0 ) then
gcm = mm
exit
endif
rr = mm - ( mm / nn ) * nn ! rr は mm を nn で割った余り
mm = nn
nn = rr;
end do
write(*,*) m, 'と', n, 'の最大公約数は', gcm
end
このProgramでは、変数mm, nn ( mm > nn )の二つの変数の対に着目すると、Loopを一回実行する度に、( mm, nn )が( nn, rr ) ( rrはmmをnnで割った余り)になります。nnとrrを比較すると、平均してrrはnnの半分になるので、rrは、毎回1/2になり、これが0になればProgramが終了するため、n = 2^bであれば、繰り返し回数は、平均してb回となるわけです。
つまり、互除法のオーダーは、O(b)あるいはO(log n)となります。
ここで、虱潰し法と、互除法のオーダーを比較すれば、後者のオーダーが明らかに小さいということは言うまでもないでしょう。
したがって、最大公約数のアルゴリズムに相応しいのは互除法であるということがいえます。
円の面積を虱潰で解くプログラムのオーダーを考えてみます。
program circle integer x integer y integer r integer s ! 半径は 100 cm r = 100 ! 発見できた内側の桝の個数を s で表す。最初は 0 個 s = 0 ! 方眼の左上の位置を x, y で表す do x = -r, r do y = -r, r if x*x + y*y < 100*100 then ! 桝の右上の点が円の内部だった。 s = s + 1 endif end do end do write(*,*) '半径', r, 'cm の円の面積は', s, '平方センチメートル' end
このプログラムでは、半径のサイズrを入力サイズと考えればrに関する二重のdoループがあるので、オーダーは、O(r*r) = O(r^2)となります。
つまり内側のループの実行回数がr回で、それを外側のループで、r回繰り返すのでその積が全体の繰り返し回数となるわけです。
課題 b.1.1 次の Program のオーダーを求めよ不定方程式を虱潰で解くprogram futei integer x integer y ! x, y の値を 1 から 192 まで、虱潰す do x = 1, 192 do y = 1, 192 if 7 * x + 13 * y == 192 then ! 方程式が満されたので結果を出力 write(*,*) '(x,y)=(', x, ',', y, ')' end if end do end do end
課題 b.1.2 以前に、学んだ課題に関して、オーダーを調べてみましょう。
まず、円の対称性を使って、次のような形に、プログラムを書き換えます。これは、1/4円の面積を調べ、その4倍によって、面積を求めようということです。
program circle integer x integer y integer r integer s ! 半径は 100 cm r = 100 ! 発見できた内側の桝の個数を s で表す。最初は 0 個 s = 0 ! 方眼の左上の位置を x, y で表す do x = 0, r y = int( sqrt( real( r*r - x*x ) ) ) ! その x における、一番、大きな y の値を求める s = s + y ! その y までの桝は、円に含まれる end do write(*,*) '半径', r, 'cm の円の面積は', s * 4, '平方センチメートル' end
元のプログラムは、O(r^2)であった。しかし、y軸方向の方眼を一つずつ調べるのはいかにも、効率がわるいように思われる。そこで、その部分を改良することを考える。
元の方程式x^2 + y^2 = r^2をyについて解きy = \sqrt{r^2 - x^2}とすれば、各々のxについて、y方向の方眼の個数は一度で得ることができる。
program circle integer x integer y integer r integer s ! 半径は 100 cm r = 100 ! 発見できた内側の桝の個数を s で表す。最初は 0 個 s = 0 ! 方眼の左上の位置を x, y で表す do x = 0, r y = int( sqrt( real( r*r - x*x ) ) ) ! その x における、一番、大きな y の値を求める s = s + y ! その y までの桝は、円に含まれる end do write(*,*) '半径', r, 'cm の円の面積は', s * 4, '平方センチメートル' end
このProgramのオーダーは、O(r)であることを確かめることができます。
課題 b.2.1 放物線 y = x^2 の 0cm から 10cm までの定積分を考えよう。虱潰し法ではなく、 上記の改良方法の方法を試してみよう。
課題 b.2.2 虱つぶし法をつかっって、半径が r の球の体積を求めてみよう。 また、そのプログラムのオーダーは幾つだろうか ?
課題 b.2.3 上記の問題を改良して、より効率の良いプログラムを作成しなさい。 また、そのプログラムのオーダーは幾つだろうか ?
提出先
softa-2004@rep.s.cn.cst.nihon-u.ac.jp
ただし、次の点に注意してください。