お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今日の授業では、最小全域木 (MST) を構成するプリム (Prim) のアルゴリズムが正しく動くことの証明から行いました。背理法を用いた証明で、理解に若干難しいところもあったかもしれませんが、発表者の人も頑張って説明できたと思います。
授業の後半では、プリムのアルゴリズムのようなものが、一般に greedy algorithm （「欲張り」アルゴリズム）と呼ばれる話や、MST を構成する別の greedy algorithm の例として、クルスカルのアルゴリズムを見ました。
次回は、greedy algorithm が、なぜ、正しく MST を構成できるのか、その辺の舞台裏を探っていくと思います。次回の発表者にも期待したいと思います。
Maple Techno Forumは、数式処理システム Maple の日本販売元で、昨年から開発元の Maplesoft の親会社になったサイバネットシステムが、数式処理システム（特に自社製品の Maple や MapleSim）を、モデリングやシミュレーションの中で、こんな風に使えますよ〜／使ってみませんか〜、という、事例紹介や、先端研究の成果を紹介などを行うセミナーです。
私も、Maple ユーザの一人として、アルゴリズムの研究開発の立場にいますが、実際に、ものづくりの現場で数式処理システムをどのように使おうとしているのか、どのような使い道があるのか、見てみようということで、行ってきました。
例年、このセミナーは水曜日に開かれていますが、水曜日というと、数学類の「演習デー」で、毎年授業と日程がぶつかるのですが、今年度の1・2学期は、たまたま水曜日の演習から外れているので、久し振りに足を運ぶことにしました。
今回の自分は、前回（3年前）行ったときと比べて、だいぶ自分の中での目的意識がはっきりしていて、前回よりずっといろいろな印象も強く残り、全体的に、ためになった会議でした。以下、講演の内容、講演のテーマ、講演のスタイル（プレゼンテーション）、参加者を見渡してという観点から、感想を書きたいと思います。
講演内容で、一番興味を持ったのは、(MapleSim による) 自動車のシミュレーション技術が、想像よりもはるかに進んでいたことでした。Waterloo の Maple と自動車業界との接点がどこにあるんだろうと、これまで話を聞くたび常々不思議でしたが、Waterloo は、北米の五大湖周辺の、自動車産業が活発な地域（USA だとデトロイトなどの周辺）に位置することがわかり、納得しました。それから、トヨタ自動車やGMとの共同研究で、ハイブリッド電気自動車 (HEV) の動作を MapleSim でモデルを作って動かすなど、普段あまり聞く機会のない情報に接することができたのは収穫でした。
講演のテーマですが、成功例でも失敗例でもよいのですが「新しい話」は、印象に残りました。自分の実践に基づく話だと、より印象に残った気がします。大学の授業と異なり、個人的には、教科書的な話よりは「自分でこれをやってみました」とか「今、こういうことをしています」という話の方が、より興味を持てました。普段、自分は、研究会などで、専門家を相手にした話をする機会が多いですが、専門家以外の人に向けた話を考える上で、参考になりました。
次に、プレゼンテーションを見ていて感じたことは「箇条書きは寝ます」。いや、寝たわけではありませんが、箇条書きは読むのに疲れる、内容を頭に入れるのにも疲れる、で、スライドは文章よりも図や写真を見せて、しゃべりで説明するのが、聴く立場としては聴きやすいと思いました。
このようなプレゼン技法には BBP (Beyond Bullet Points) というのがあり、私も本を買ったりしてスライドを作るときにいろいろ考えています。実は、明日某所で話すスライドがあったのですが、どうしても時間がないのに負けて、箇条書きでスライドを作りました。しかし、今日のプレゼンを見て、やはり箇条書きは使わないに越したことはないなーという思いを新たにしました。残念ながら、明日のプレゼンはもう直す時間がありませんが、今後心したいと思います。
一般の聴講者を見ていて思ったことですが、聴講者で、講演者の人達に話しかけたり話し合ったりしている人が、少ない印象を持ちました。私も、最初その気にはならなかったのですが、自動車のシミュレーションの話をしたカナダの先生の講演の後で、その先生にいろいろ話しかけている人を見て「せっかくチャンスがあるんだから、自分も話していかなきゃもったいないな！」と思い直し、後でその先生と話す機会を得ました。
まずは通り一遍の挨拶だけでもいいですし、とにかく「さっきの先生の講演は興味深かったです」とか何とか挨拶すれば、もしかしたら話に花が咲くかもしれませんし、いい機会になると思うのですが、参加された技術者（の方が多かったと思いますが）の皆さん、いかがでしょう。私も、最初は挨拶程度ですが、自分の仕事を紹介したり、講演中にちょっと気になったことを質問したりと、個人的にはためになる会話ができたと思います。あと、この日のために、名刺を、今回は日／英両面で作ったのですが、英語の名刺を作っておいたのもラッキーでした。
こんなところですが、講演者や聴講者に、同分野で知り合いの方もおり、久々にお会いして近況を伝え合ったりもできました。ありがとうございました。学生時代の研究室の盟友であり、現在カナダに渡って活躍中の山口 (Tetsu) さんも、MapleSim の最新バージョンの紹介をバッチリやってました。Good job, Tetsu san! Maple の動向には今後も注目したいと思います。
今日の授業では、まず「前処理」（第12章：仕事の前に一仕事）で、最短経路探索の前に、探索対象をある程度絞ったり、探索に直接関係ないノードを減らしたりして、探索にかかる計算量を減らす工夫についてやりました。
ついで、「最小全域木 (Minimum Spanning Tree: MST)」の話（第13章：木々の合間で鬼ごっこ）をやりました。与えられたグラフに対する「最短経路木」は、開始ノードを変えるとMSTでもあり「得る」という部分と、本の例題として扱っている最短経路木はMSTに等しくない証明が、ちょっと複雑だったかもしれませんが、テキストに沿って順を追って考えていくと、それ程難しいことではないと思うので、よく復習してほしいと思います。
ちなみに、第13章の冒頭、「チューリングテスト」に合格したプログラムに賞金を出すという、ローブナー賞 (Loebner prize) というのが紹介されており、調べてみたところ、毎年コンテストが行われていて、今年のコンテストはなんと明日行われるのだそうです。どういう結果になるのでしょうか。
来週の授業では、今日登場したMSTを計算するアルゴリズムをやると思います。次の担当の人にも頑張ってほしいと思います。
今日の授業では、前回予告した「補題 1」の証明を行いましたが、最後のケースの証明が授業時間に収まりませんでした。これを次回に持ち越し、次回は引き続き補題2の証明を進めたいと思います。
今日の授業では、ダイクストラのアルゴリズムの計算量の見積りを中心にやりました。一般のn個のノードを考えた場合というのは、なかなかピンとこないようですが、数個の具体例を考えて計算すると、納得できたという人が多いようでした。
あとは、グラフの辺の重みがノード間の距離に対応するような場合は、直観的な距離の探索が役に立つ・・・というのは、すでに始点と終点を結ぶ経路を1つ知っていた場合、最短経路は、始点と終点を焦点とし、すでに知っている経路の距離を長軸にもつ楕円の内部に存在する、という話も出ましたが、この話は、多くの人達にとって新鮮だったようです。
次回は、前処理の話と、グラフの「最小全域木（スパニングツリー）」の話になると思います。私も予習を頑張りたいと思います。
私の所属する数学専攻の月例談話会。今月は、このタイトルで、昨年、円周率計算で2兆5769億8037万桁の記録を出された、高橋大介先生（筑波大学 システム情報工学研究科／計算科学研究センター）がお話をされました。
数学系月例談話会
2010年10月7日（木）16:00〜17:00
会場：自然系学系棟D棟, 5階 D509
高橋 大介 氏 （筑波大学大学院システム情報工学研究科・計算科学研究センター） 「最近の円周率計算」
アブストラクト：
現在，円周率πの値は小数点以下5兆桁まで明らかになっている．これはコンピュータの性能の向上だけによるものではなく，円周率πを効率良く計算する公式の発見， 5兆桁もの数の加減乗除を効率良く計算する方法の確立，そして複数のグループによる計算競争という複数の要因が順次オーバーラップして効果を発揮してきた結果といえる．この講演ではこれまでの円周率計算の歴史について触れた後に，円周率πという数は具体的にはどのように計算されるのか，円周率πを計算することにどのような意味があるのか，などについて述べる．
（筑波大学数学系月例談話会ホームページより引用）
高橋先生は、ハイパフォーマンスコンピューティング (HPC) の専門家として、これまでにも何度か、円周率の新記録にかかわっていらっしゃる方で、以前行われた、筑波大学計算科学研究センターのHPCセミナーも聴講したことがあるので、今回、学科内でお話をされるとのことで、早速駆けつけました。
これを読んでいる方はご存知の方もいらっしゃると思いますが、昨年、高橋さんが、筑波大のスーパーコンピュータで新記録を出した後で、昨年から今年にかけて、フランス人が記録を更新し、日本人・アメリカ人のチームが、さらに記録を更新したことが話題になりましたが、その辺のより詳しい事情（後述）も知ることができました。
今回のお話は、まず、上述の最近の進展にちょっと触れた後で、円周率の算法と計算桁数の歴史的な発展について話されました。
算法では、まず、円に内接／外接する正多角形の外周の長さを測ることから始まり、微分学の登場で、無限級数の計算に発展するわけですが、現在もよく用いられる公式の一つに、算術・幾何平均を求める、ガウス・ルジャンドルの公式（高橋さんも用いた）があります。ガウスは、数学をやる人の間ではよく知られているように、数学のほとんどいたるところの分野に業績を残している人ですが、円周率にもいたか〜、やっぱりすごいなという印象を持ちました。それから、ガウスは、自分の業績の多くを生前には発表しなかったことでも有名ですが、この公式も、1970年代になって再発見されたものであるということで、ガウスの先見性を再認識しました。
20世紀後半以降、コンピュータによる計算が始まって以降は、多倍長数の乗算をいかに効率的に行うかが、計算全体の算法面での効率化の上で本質的に鍵を握るようになります。現在では高速フーリエ変換 (FFT) が主流ですが、FFT は多くの科学技術計算で用いられるもので、円周率の計算を行う上での研究成果が、計算科学全体に貢献していることをあらためて知りました。ぜひ、おけいちゃん（先日出荷が始まった、次世代スーパーコンピュータ「京」）の FFT 計算も頑張ってもらいたいところです。
それから、高橋さんが、筑波大のスーパーコンピュータ「T2K筑波」で行った計算では、主計算と検算を合わせて、約73時間の間計算を続けたとのことですが、この間、システムダウンなく、最後まで計算したとのことでした。これは、システムの耐久性といった工学的観点から見るとすごいことなのだそうです。そういえば、以前、やはり円周率の計算に携わっている専門家の方から「スーパーコンピュータの性能ギリギリまで計算をさせると、しばしば部品（素子）が壊れる→計算結果に誤りが生ずる」という話を聞いたことがあったので、これだけの計算をシステムダウンなしで行ったのはやはりすごそうです。
ちなみに、T2K筑波の規模は、648 ノード × 4 ソケット/ノード × 4 コア/ソケット＝10368 コアとのことで、これだけのコア数を約73時間動かすというのは、普通のパソコン、例えば 2 コアとすると約37万時間≈約15000日≈約40年間動かすことに相当するのでしょうか。
最後に、高橋さんが記録を出して以降の新記録について触れていましたので、こちらも書きたいと思います。
まず、昨年末に 2.7 兆桁の記録を出した、フランスの Fabrice Bellard 氏ですが、彼は天才的なハッカー（コンピュータの専門家）であるのみならず、数学も非常に達者な方なのだそうです。計算に使った機器も、CPUがCore i7 2.93GHz, RAM 6GB, HDD 1.5TB x 5 = 7.5 TBで、普通の人にもそこそこ手が届く程度の機器のようですので、数学的な工夫による功績が大きいようです。
次に、今年に入って 5 兆桁の記録を出した、アメリカの Alexander J. Yee 氏と日本の近藤茂氏ですが、円周率の計算には Chudonovsky の公式を用いており、高橋さんによりますと、現時点で全桁の検算は終わっていないとのことですが、末尾数十桁は検証済みとのことで、BBP (Bailey-Borwein-Plouffe) 型公式を用いると、16進数で円周率の第d桁をいきなり求めることができるのだそうです。この辺も興味深いお話でした。
そして、講演の最後に「円周率は、文明の進歩を示す一つの尺度」という言葉がありました。高橋さん曰く、これはテレビの取材を受けた時にぱっと思いついたとのことですが、歴史的な進展と人々の貢献を振り返ると、まさに格言だと思います。非常にためになるお話でした。
なお、筑波大学数学系月例談話会は「専門を離れて幅広い数学の動向を知るための場です．非専門家を対象とした概説講演のみを取り上げます．大学院生や学群生を含む，幅広い方のご参加を歓迎します．」ということですので、興味のある方はのぞいてみて下さい。ホームページは http://www.math.tsukuba.ac.jp/~colloq/ です。
今日は、前回定義した「部分終結式」の例題から始まりました。先週出した例題に対して、部分終結式の計算をしてきた人がいましたので、黒板で実際に計算してもらいました。例題を作った際、私は計算ミスが重なって苦労しましたが、学生さんの計算はそれに比べるとちゃんとしたもので、感心しました。お疲れさまでした。
今日の残りの時間では、部分終結式を1つの行列式で表す表し方（本来はこちらの方がよく使われる）を説明しました。
今日はここで時間となりましたが、これから先の予定は以下の通りです。
まずは、来週、と思いましたが、来週は体育の日でお休みですので、再来週、補題 1から続けます。
前回の授業の感想を一通り読みましたが、学生さん達の多くが書いていた感想として「アルゴリズムに入り、内容が急に難しくなった」というのがありました。一方で、数人の人達が書いていた感想として「最初にアルゴリズム全体を見た時には、とても理解できそうに見えなかったが、少しずつ内容を読んでいくと、徐々に理解できるようになった（気がした）」というのもありました。
以上の2点を踏まえて、現時点で、学生さん達には、以下のことを伝えました。
あと、上記で「理解できるようになった（気がした）」と書きましたが、理解できた「気になる」というのも、数学を学ぶ上では大切だと思います。もちろん、ちゃんと理解する必要があるので、本当に自分が理解できたかどうか、用心する必要がありますが、その上で「わかった！」というのが、最初は「気」だけだっとしても、「わかった気になる」と「そのチェック」を繰り返すことにより、徐々に本当の理解に収束していくものと信じていますし、そのくらいの楽天性もあった方がよいかもしれません。
さて、今日の授業では、前半で、ダイクストラのアルゴリズムの残りの部分を説明してもらい、後半では、グラフの辺に負の重みがあった場合や、グラフに閉路が存在するような場合の最短経路の探索について、発表してもらいました。2人とも、テキストの内容をよく読んで、説明も工夫していたと思います。
次回は、ダイクストラのアルゴリズムの計算量解析が話題の中心になると思いますが、次回の発表も楽しみにしています。