Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Good Programmers learn Mathematics

良いプログラマは数学を学ぶ、方が良いと思う

　この文章は 2003 年 2 月 28 日（金曜日）に株式会社 ACCESS の研究開発室のメンバ向けに行われた講義のために準備されたものです。

はじめに

　これから何回か皆さんの前で数学の話をさせてもらうことになりましたが、今回はまず、その手始めとして「どうして皆さんが数学を学んだ方が良いのか」、いいえ、「どうして皆さんに数学を学んでほしいと私が思っているのか」というお話をさせて下さい。もちろん、それは皆さんに、より良いプログラマになって欲しいからですが、また、私の経験によれば、コンピュータサイエンスの教育の現場では、何故か数学が軽視されることが多いことを残念に思っているからでもあります。

　皆さんが数学を学ぶべき理由は主に三つあると思います。まず、第一に皆さんが日々、ソフトウェアの実装にあたって生じてくる問題と向かい合うとき、実は、そもそもその問題が数学の問題である場合がある。このことは決して自明なことではありません。思わぬところに数学の問題は隠れていて、しかもそれが非常に難しい、時には現代数学においても未解決な問題ですらある、そんなこともありうるでしょう。つまり、プログラマは時に数学者でなくてはならない。

　第二に、その問題を解くために、数学的な解決法が必要になる場合がある。つまり、アルゴリズムの問題です。情報科学の教育を受けた方なら、例えば、ソーティングのアルゴリズムを勉強して、クイックソートの驚くべきアイデアに心打たれたことがあるでしょう。どれだけ沢山アルゴリズムを知っているかを数えることには、それほど意味はありません。大事なことは、アルゴリズムそのものの意味を理解すること、できるだけ根本に近い一般性のあるアイデアを捕まえること、それらを自分の中で整理することです。

　第三に、プログラミングそれ自体に、数学的な発想、もっと格好良く言わせてもらえれば、 数学とプログラミングの美学が関係していることです。

　今、無理に三つ挙げてみましたが、もちろんこれは枚挙にも、分類にもなっていません。とりあえず、いくつか例を挙げて「アルゴリズム」という皆さんに親しい概念で数学の力を見ましょう。そしてその後で、私が本当に言いたいこと、つまり、 「数学を嫌いにならず、仲良くしてください、きっとそれがあなたをより良いプログラマにしてくれるはずです」 というお話をさせてください。

アルゴリズム　―　数学によって可能になること

　数学によって可能になること、という意味は、多くの場合、数学を用いることによって現実的な速度やリソースで可能になること、ということを指します。いくらでも時間とエネルギーとリソースを費やしてもよいなら、プログラミングにおける大抵の問題は解決するのですが、もちろんそんな範囲で仕事をさせてもらえるプログラマは一人もいませんね。ある処理は非常に短時間に終わる必要があるとか、そもそもプアなリソースしか持たないプラットホームで開発しなければならない、とか言う仕様上の問題もありますが、ある種の問題はそもそも人間的なスケールで実装するためには、数学の力を借りざるをえません。この数学の力が「アルゴリズム」です。

　確かにハードウェアの処理能力はどんどん速く強力になっていきます。ある伝説によれば、指数的に成長し続けるようです。それならば賢いアルゴリズムを考える必要はないのではないか、と言う議論もありえなくはないでしょう。しかし、多くの場合は問題の難しさの指数的増大に比べて、ハードウェアの進歩の速度はあまりに遅すぎます。なぜなら、おかしな言い方かも知れませんが、問題にはそもそも限界がないからです。問題は常に純粋に理論的なものであり、物理的な制限がないのですから。巧妙なアルゴリズムなしには、 いかなる計算機をもってしても 未来永劫にわたって不可能である場合もありえます。

　いくつかの例を挙げてみましょう。まずは皆さんにはおなじみのはずの「文字列の検索」を取り上げましょう。ある文書の中で与えられた単語をサーチするアルゴリズムについては、皆さんは良くご存知でしょう。でも、以下のような問題はいかがですか？今、ある文書の中からある単語を検索したいのですが、ぴったりその単語に等しい文字列はおそらくないだろうと予想されるのです。したがって次善の策として、目的の単語に「できるだけ似ている」文字列を検索したい。ここで似ているという言葉の意味は、目的の単語のある箇所（一箇所とは限らない）に何文字か挿入されている、または何文字か欠損している、またはその両方が起こっている場合です。

　下の図が一つの例です。文字一つが一致していれば 1 点、一致していなければ 0 点、挿入を表す "-" 記号には -1 点を減点として与えて、一番高い得点を得られるものを探せ、という問題です。（この得点の与え方は問題によります。）

データベース： ...BDABDCAEDDCAAAABCCABDDB...   ...BDABDCAEDDC-AAAABCCABDDB
検索文字列　： DABDDBBAAAAAC               -->     DABD---DDBBAAAAAC
                                                   oooo---oox-ooooxo (11 - 4 = 7 pts)

　ご存知の方もいるかもしれませんが、実はこの問題は今、非常に注目されているものです。皆さんは我々の遺伝子、正確に言えば DNA （デオキシリボ核酸）が四種類の文字からなる列だということはご存知ですね。単語を探す文書が DNA やそのデータベースの記号列、検索する文字列はその一部、例えば特定のたんぱく質を合成する部分だとしてください。 DNA は突然変異などによって、一部が欠損したり、ある長さの文字列が挿入されたりします。 DNA のデータベースからできるだけ似ている文字列を探すという、この問題の重要性は今や明白でしょう。このような「できるだけ似ている」文字列を探す問題を ホモロジー検索と言います。（余談ですが、数学用語のホモロジーとは関係ないです）

　さて、では皆さんが今日、この DNA データベースのホモロジー検索ソフトウェアの実装を依頼されたとしましょう。どのようにこれをプログラミングしますか？今、ちょっと考えてみてください。正規表現を使って何とかなりそうですか？データベースの文字列の長さを N として、ホモロジー検索する文字列の長さを n としましょう。これらに対してどれくらいの時間がかかりますか？例えば、N が 1 メガバイト、n が数百バイトだったら？

「こういう時に最初に考えなくていけないのは、問題が指数的なオーダーか、そうでないかですね。パラメータを倍にすると計算の手間は何倍になるか？３倍にするとどうなる？」

　検索する単語の全ての文字間に任意の長さの文字列が挿入される可能性があり、探すデータベースの文字列の方も全ての文字間に任意の長さの文字列が挿入される可能性があり、しかもその挿入欠損箇所は複数かも知れない、この可能性を全て検索して行くとすれば、とてつもない数になってしまう… 皆さんは既に優秀なプログラマですから、この問題が非常に、非常に、困難であることを直感したことと思います。

　では、これが非常に高速に可能であることを示しましょう。実際のところ、驚くべきことですが、 N と n の積のオーダーの計算量で可能です。まず、データベースの文字列を横に並べ、検索する文字列を縦に並べます。格子点がそれぞれの文字のペアを示すように N かける n の長方形の格子を書きましょう。さらに、各マスの中に左上隅から右下隅への斜めの線も入れます。この長方形の格子全体の左上隅から右下隅まで、各格子点を右か、下か、右下への一つを選びながらたどって行ってみてください。どんな道でも構いません。一本の道が引けたら、その道がデータベース文字列と検索文字列の一つの対応のさせ方を表していることを観察してください。よくこの図を睨んでもらえれば、わかるはずです。

　さらに、各格子点に対して、スタート地点の左上隅から、その場所に行くときに得られる最高得点を書き込みます。ここで注意すべきことは、左上隅から順番に書き込んでいけば、各格子点での得点を計算するのに必要な情報は、その直前の三つの格子点の得点だけだと言うことです。結局、格子点の数の定数倍の計算量で得点の書き込みが終わります。いったん、得点の書き込みが終われば、これらの情報を使って、最も高い得点を得る径路が、右下隅から逆向きにたどっていくことで得られます。

練習問題：「上の説明を自分できちんとアルゴリズムの形にしてみましょう。さらに自分の得意な、またはこの問題に適切と思われる、プログラミング言語で実装してみましょう」

　確かに巧妙な素晴らしい方法です。しかしこの方法の真に素晴らしい点は、その一般性です。このアルゴリズムは「動的計画法(Dynamic Programming)」と呼ばれる方法で、もちろん最初はホモロジー検索とは無関係に生まれました。まず音声認識の分野に応用され、さらに分子生物学への応用が発見されたそうです。これは全てのアルゴリズムに言えることです。アルゴリズムは特定の問題の解法にとどまらない。それは純粋に抽象的な一つの論理だからです。それはその論理で作られた一個の創造物として既に完全な美しさを持ち、しかもその強力なパワーを発揮すべく、特定の問題に応用されるのを静かに待っている。

　次の例を挙げてみましょう。今度は私の得意の話題です。皆さんは公開鍵暗号系という言葉を耳にしたことがあるでしょう。公開鍵暗号系とは一言で言えば、錠を閉める鍵と開ける鍵を異なる鍵にし、鍵Aで閉めたものは、対応した鍵Bでしか開かないという仕組みです。もしこれが可能ならば、閉めるべき鍵を世間に公開してしまい、それを開ける鍵だけを自分がしっかり秘密にしておけば、まったく秘密裏に鍵を交換する必要のない、画期的な暗号システムができたことになります。誰でも公開されいてる鍵を使って暗号化し、あなたに暗号化メッセージを送り、対応する鍵を持っているあなただけがそのメッセージを復号できるからです。

　問題はどうやってそのような鍵の仕組みを実装するか、ですね。これには数学の力を使わざるをえません。世界で最初に実装された方法は、整数論の結果、特に素数の性質を巧妙に用いるものでした。今でもこの方法が支配的です。ここで、数学の中でも特に整数論は、世の中に全く応用されないことで有名だったという事実を注意しておくことには価値があるでしょう。応用のなさ、つまりその純粋さを誇りにしていた数学者もいるようですが、今や、暗号の問題のおかげで、整数論は最も強力な応用のある分野になってしまいました。（もちろん、数学は応用がなくても素晴らしいもので、そこが数学の良い所でもあります。素数の定義のこれ以上ないほどの単純さと、素数の性質が持つ果てしない深さの対比こそが数学の美しさです。）

　かつて私が御社でそのような公開鍵暗号システムを実装していたとき、まず問題になったのは非常に大きな数、例えば、数百ビット以上の整数の計算を高速に行うことでした。特にべき乗剰余計算（x^y mod. z) が必要でした。まず最初は某大企業から多倍長演算ライブラリをもらったのですが、なんとそれはこのべき乗剰余計算を、本当にべき乗して剰余をとる方法で計算をしていたのです。扱う数が数百桁の整数なのですから、どんな途方もない計算になることか！失礼のないように断っておくと、このライブラリは非常に高名な、優れたライブラリでした。ただ、この目的には使えないものだったのです。

　では、どうすればよいのでしょうか。自乗乗算法と言う非常に一般的なアイデアがあります。ポイントは、自分をどんどん自乗していけば(x * x)、あっと言う間に大きくなると言うことです。ある大きな数に到達するのに、自乗計算で充分近づいておいて、余ったところで、また残りの中で自乗計算を繰り返す。もっと具体的に説明しましょう。 x の y 乗を計算するのに、まず、y を二進法に展開します。とすると、こう変形されますから… 結局、二進法の各桁が１か０かに従って、自乗か、掛け算か、を繰り返して行けば答えに到達するわけです。計算量は y の二進法表現の桁数程度になります。つまり計算量はもとの対数程度と言う驚異的な量にまでに削減されました。

練習問題：「上の説明を自分できちんとアルゴリズムの形にしてみましょう。さらに自分の得意な、またはこの問題に適切と思われる、プログラミング言語で実装してみましょう」

　もちろんこのライブラリを作るにあたって、もっと色々なアイデアを使いましたよ。あまり数学的でないアルゴリズム、例えば計算をする代わりに既に計算結果を表にして保持しておくとか。しかし、そのようなプログラマ的な（失礼）アイデアは、所詮計算量を数分の一にするとか、その程度のささやかな力しか持ちません。計算量を対数的にまで下げる、などという、猛烈なパワーはアルゴリズムの、つまり数学の力です。

　では、アルゴリズムを勉強するにはどうすればよいのでしょうか。これは難しい問題です。ある意味では通常の数学の分野を勉強していくのよりも難しいことです。なぜなら、通常、アルゴリズムは、個別の問題に対するその巧妙な解法の集まり、といった捉えられ方しかできませんので、系統的に学ぶことは不可能なのです。 D. Knuth の大著 "The Art of Programming" など、素晴らしい書物が書かれてはいますが（まだ書かれている最中ですか？）、やはりトリックの雑多なコレクションの範疇におさまっています。大学などの教育においても、こんなアルゴリズムもある、こんなのもある、といったケーススタディがせいぜいの所でしょう。

　私からの提案は、良いアルゴリズムを沢山知り、沢山考え、沢山実装する、何が本質なのかを考え、より本質的なアルゴリズムを学び、自分なりに整理していく、と言った正攻法が一つ。そしてもうひとつは、皆さんの得意なメタ思考的に言えば、巧妙なアルゴリズムを生み出す思考法（アルゴリズム）に一歩でも近づくこと。つまり、それこそプログラマが数学を学ぶことの意味だと私は思うのです。これは次の章のテーマに自然につながります。

数学とプログラミングの美学　―　（多分）一番たいせつなこと

　みなさんは良いプログラマですから、良いコードが良いデザインに基づくこと、否、良いコードとは 良いデザインそのものである (*1) ことを既にご存知でしょう(cf. "Taste for Makers" by P.Graham)。そしてそれをより深く実感するほどに、良いプログラマになるということも。今日、私が皆さんに強調したいのは、数学を学ぶことがその助けになるということなのです。

　その最大の理由は、ぜひ怒らないで聞いていただきたい、最大の理由は「プログラミングは数学の一部だから」だと思います。プログラミングは数学ではない、アートなのだ、数学以上のものなのだ、いや、むしろ数学こそプログラミングに含まれている（チューリング機械！）、といくらでも反論はあるでしょうが、プログラミングというアートにおける倫理、美学は、実際のところその精神においては、数学における倫理と美学をそのままに受け継いでいるのです。

　昔、御社で一年だけ働かせてもらったときに、私は良いプログラマたちが頻繁に「美しい」という言葉を用いることに気づきました。良いプログラマは、問題に対する解や、そのプログラミングによる実装を、「美しい」と呼ぶことがあり、そのセンスは「一般の」プログラマには理解されないが、数学しか学んだことのない私には理解できた、ということに驚きました。（ただ、正直に言うと、彼らはあまりに頻繁に「美しい」を使うので、少々インフレ気味なのではないか、とも思いましたが…。数学者は控えめな�ので、おおむね、「美しい」「エレガントな」という言葉は、とっておきの場合のためにキープされています。）

　数学においてはどのようなことが「美しい」と呼ばれるのでしょうか。野崎昭弘氏はその著書「数学的センス」 (*2)の中で、美しい数学とは「大切なこと、しかも、一般性のあることを、すっきりと、ムダのない言葉で述べたものである」と書かれています。さらに、野崎氏は、つまり美しい数学とは詩なのです、と文章を続けられていますが、皆さんにはこれがつまり、良いプログラムのことでもあることは明白でしょう。

　数学的センスには美的センス以外にも色々なものがあります。上に挙げた野崎氏の著書には、その他に、 「命名」「判断」「分析」「集中」「わからないということ」「わかりやすいということ」「言葉」「空間」「構造」「無限」「論証」などの章が立てられています。これらはまさにあなた方、良いプログラマが日々苦闘していることではないですか！オブジェクトや関数に良い名前をつける、的確な制御文、柔軟な変数の空間を構造化する、正確に仕様を分析し…

　プログラマの日常業務においては、このような概念について、良いセンスを身につけることは易しいことではありません。めちゃくちゃな仕様、無茶な追加機能の際限のない要求、迫り来る納期、言うことを聞かない無能なアシスタントプログラマ、言うことを聞かない無能な上司、日々は慌しく、「美しいデザイン」などとは無縁に過ぎていきます。私は良く知っています。あなた方、優れたプログラマが泣く泣く、あえて「醜い」「邪悪」なコードをやむなく書き加え、エレガントどころかエレファントな無駄な機能を付け加えていることを。それだからこそ、数学を学んでください。ほんのわずかでも良いのです。数学を楽しんで学んでください。それは最も迂遠な道に見えて、実は最も近道であることが、いずれ分かるはずです。その最初のステップとして、例えば、上に挙げた「数学的センス」は最適だと思います。非常に楽しいエッセイ集です。他には以下のようなものが私のお薦めです。

（「数学的センス」（野崎昭弘著、日本評論社））
「いかにして問題を解くか」（G.ポリヤ著、柿内賢信訳、丸善）
「数学の問題の発見的解き方１，２」（G.ポリヤ著、柴垣和三雄、金山靖夫訳、みすず書房）
「数と図形」（H.ラーデマッヘル、O.テープリッツ著、山崎三郎、鹿野健訳、日本評論社）
「数学点描」（I.J.シェーンベルグ著、三村護訳、近代科学社）

上に挙げたようなエッセイ風の書物で数学に親しんだ後は、ぜひ、本物の数学を勉強してください。上の書物がけして本物の数学を伝えていないというわけではありませんが、プログラミングが厳しいディシプリンに支えられているのと同じように、数学も定義から順に積み重ねられていく高い山を一歩一歩、自分の足で上り詰めていくこと、そしてその高みから見下ろした時の、簡潔に調和した荘厳な風景こそが本釈��跏��鉗�盥�鈞��孖�驫��戟矼��魍��一纖��邏飢蟒�を押入れから取り出して、�粢��聽寀�屋�膵��覦�蜉侚�砌�現�綽�悗慮斥佞任發�硴�蟠飢蟒�があ�教芽就颪任�盡�茣��銕�覬�肭�雅�觚��蓿繙就ｈ�嘗��、かなり難しいし、古いものですが今も定評ある教科書、高木貞治「解析概論」(*4)などはいかがでしょうか。

　さらにその後は…道は無限に広がっています。私はぜひ、複素解析学の美しさ （こういうときにこそ「美しい」という言葉を使うのです！）を一度は味わってもらいたいと思いますが、勉強するのはあなたですから自分の好みに従って学んでいけばよいでしょう。プログラマの方なら自然に集合論、基礎論に親しんでいるでしょうし、代数学や整数論なども好みに合うかも知れません。離散的な対象を扱うものがプログラマ好みのようですが、微分幾何、トポロジー、関数解析、確率論、などもそれぞれ同じように、繊細さと美と驚異に満ちた素晴らしい分野であり、また、より高い見地からすれば、数学に分野の境界は存在しないのです。なんでも好きなように楽しんで学んでください。

質問と回答

　以下は講義後の質問とその回答から抜粋したものです。

質問：「プログラミングのセンスは教えることが可能でしょうか？」
回答：
私はプログラミングにそれほど詳しいわけではありませんが、数学との類推で考えるに… 私の個人的意見では可能だと思います。ある優れたプログラマがこう言っていました。プログラミングは出来るか出来ないかのどちらかで、教えてやることはできない、と。これを私なりに追加説明すると、こういうことではないでしょうか。良いセンスを教えることも学ぶことも可能ですし、より良いセンスを身につけ、より良いプログラマになることも可能でしょう。しかし、「より良いコードを書きたい」という情熱がなければなんにもならないのです。そしてこの情熱は…そう、教えることが非常に難しいことは確かです。数学もそうだと思いますね。

質問：「数学は理工系の人に嫌われてるんですか？そうだとしたら何故ですか？」
回答：
残念ながら最近では、嫌われていることが多いみたいですね。特に情報科学の人には。「数学なんて大嫌いだし全然使わないけど、私はこんなに立派な研究ができた」と言うのがそういう場合の決まり文句みたいです。だからと言って、嫌う必要はないと思うのですが ;-) 何故、嫌われているのか、というと、やはりそれは数学者の方にかなりの責任があるのではないでしょうか。数学を応用、つまり道具としてしか使わない人にとっては、数学の真の姿を知らないままに、それを憎むことが論理的に可能なのですね。それは昔、数学を学んだときのトラウマがあるのかも知れないし… 正直に言って、その理由はよくわかりません。でも数学者は部外者にとって「いやなやつ」であることが多いみたいですね、ええ、多いんですよ。すぐに「それは自明」とか言って、木で鼻をくくるような態度だし、適当にごまかしておけばよさそうなことを、無理に全部ごちゃごちゃと話そうとするし。嫌われてもいいんだ、自分が正しいんだから、という傲慢さもありますしね。私は、そんな壁を越えて、本当の数学はこんなに素敵だ、と常に訴えかけていく努力が必要だと思うし、その怠慢が多分、第一の原因だと思います。
皆さんはぜひ、数学を嫌いにならないでください（笑）

文献表

*1 Taste for Makers: P. Graham による論説 "Taste for Makers"と、 Kawai Shiro さんによる翻訳「ものつくりのセンス」。
*2 「数学的センス」: 野崎昭弘著、日本評論社。1984 年 5 月から翌年 7 月まで雑誌「数学セミナー」（日本評論社）に連載された記事をまとめたもの。
「いかにして問題を解くか」: G.ポリヤ著、柿内賢信訳、丸善。
「数学の問題の発見的解き方１，２」: G.ポリヤ著、柴垣和三雄、金山靖夫訳、みすず書房。
「数と図形」: H.ラーデマッヘル、O.テープリッツ著、山崎三郎、鹿野健訳、日本評論社。
「数学点描」: I.J.シェーンベルグ著、三村護訳、近代科学社
*3 「解析教程（上、下）」: E.ハイラー＆G.ワナー著、蟹江幸博訳、シュプリンガー・フェアラーク東京。
*4 「解析概論」: 高木貞治著、岩波書店。

Copy Left.

Keisuke HARA, Ph.D.(Math.Sci.), kshara@mars.dti.ne.jp
http://www.mars.dti.ne.jp/~kshara/

良いプログラマは数学を学ぶ、方が良いと思う

目次

はじめに

アルゴリズム ― 数学によって可能になること

数学とプログラミングの美学 ― （多分）一番たいせつなこと

質問と回答

文献表

はじめに

アルゴリズム ― 数学によって可能になること

数学とプログラミングの美学 ― （多分）一番たいせつなこと

質問と回答

文献表

アルゴリズム　―　数学によって可能になること

数学とプログラミングの美学　―　（多分）一番たいせつなこと

アルゴリズム　―　数学によって可能になること

数学とプログラミングの美学　―　（多分）一番たいせつなこと