数学特別演習（第17回）

今回が、この授業の最終回となりました。

今回は、まず、巡回路を探索する際に、効率よく選択対象を絞るための「分枝限定法」すなわち「枝刈り」を取り上げました。枝刈りは、基本的には、巡回路の開始ノードからあるノードまでの経路を固定した最小1-木を計算し、その長さを、経路を固定しない場合の最小1-木の長さと比較して、長さが等しいかより短い経路のみを選択肢として残していくやり方です。

本書では、枝刈りのための経路を固定する方法として、以下の2つを取り上げました。まず、開始ノードから次の経路を順番に選択した場合、そして、経路を固定しない場合の最小1-木に、次数が3以上のノードが現われた場合に、そのノードを中心に、次数が2を越えないような経路を選択した場合です。特に後者の方法については、私も予習していて理解に苦しんだ部分でしたが、発表者の人はよく予習していて、おかげで私もよく理解することができました。

次に、後半の、最後の発表では「多面体的組み合わせ論」を扱いました。これは、ノードの個数がn個のグラフについて、すべてのグラフを1つ1つ格子点に対応させて考えます。辺がある場合は、それぞれの座標を1、ない場合は0とします。すると、巡回路全体の集合は、格子点のなす空間内で、多面体を構成します。巡回路の探索にあたって、この多面体をなるべく精度よく近似することで、効率的な巡回路の探索につなげようというものです。

この話題の中では、多面体の頂点と辺の個数の関係を取り上げました。まず、多面体の頂点と辺の個数の関係は、多面体に依存していろいろ異なった状況が存在します。頂点の個数に比べて辺の個数がずっと多い多面体もあれば、逆の場合もあります。次に、仮に頂点の個数が多い多面体でも、辺の個数が比較的少ない場合は、もとの空間から多面体を「切り取る」回数を小さく抑えられる可能性が指摘されました。この話題は、チーズを例に取り上げ、醸造したもとの形のチーズから、立方体のチーズのかたまりを切り取るという例が紹介されました。

最後の話題は、巡回路に対応する頂点から構成される多面体の話になりました。巡回路に対応する頂点から構成される多面体は、頂点の個数に比べて面の個数が大幅に増加します。しかし、それらの面をすべて正確に近似する必要はなく、最適な頂点の近くで、多面体をそこそこ（うまく）近似し、かつ面の個数がなるべく少ない多面体で（お気楽に）近似できれば十分で、現在の研究の最先端は、そのような「うまい」多面体の近似をいかに効率的に見つけるかが焦点の一つであるという説明で終わりました。

これで、結局、テキストの最後の1章を残して授業が終わりました。最後の1章は、巡回セールスマン問題の研究の歴史が紹介されています。

以上がこの授業とテキストの内容ですが、まず、テキストについての感想を述べますと、非常におもしろい本だったと思います。テーマが実社会の問題と密接に関連しており、興味がわくこと、その問題を解くための理論は数学に基づいていること、かつ、「存在証明」などの定性的な要素と、アルゴリズムなど、構成的な要素の両輪を用いて問題にアタックすること、等、私自身も興味をもって読みましたし、学生さん達にとっても、数学に対する認識を新たにする内容だったようです。

翻訳も、読み物的な本を、数学的な正しさを損なわずにわかりやすく訳すのは苦労があったと思いますが、おおむね、よく訳されていて読みやすかったと思います。ただ、数か所、訳文の数学的意味が読み取りづらい部分や、術語の記述が不正確な部分が見受けられたので、さらなる翻訳の向上に期待します。

授業に関しては、学生さん達は、皆積極的によく頑張って予習、発表していたと思います。授業の最初の頃は、皆さん苦労しているようでしたが、回数を重ねるにつれて、発表や板書の質やわかりやすさが徐々に向上していることが見てとれました。学生さん同士でやると、このように刺激になってよいものですね。

先日開かれた学類のクラス連絡会で、授業評価アンケートの結果が報告された際、微積分や線形代数の予習時間の少なさが指摘されていました。大学の授業に対する認識の結果だと思いますが、私がこの授業で学生さん達を見てきた限り、その気になれば予習に取り組む能力は十分に備わっていると確信したので、こうした力を他の授業でも発揮されることを望みます。

長いようで短い半年間でしたが、一緒に授業をつくってきた学生さん達に感謝します。この本は、これから本格的に数学を勉強しようとする学生さん方、数学を教える先生方、そして数学に興味を持つ多くの方々に、おすすめ度は「星3つです！」です。数学的な内容は割とちゃんと書いており、さらっとした会話の中にも重要事項が頻発ますので、1文1文を納得するまでじっくり読まれることをおすすめします。

さあ、学生さん達の最後の感想文に目を通すことにしましょう。ついでに、来年度もこの授業を受け持つ予定です。次はどんな本を読もうかしら・・・

数学特別演習（第16回）

今日は水曜日ですが、11日の金曜日が建国記念の日で休みになるため、金曜日の振替授業となりました。

今日は、長さ最短の巡回路に近い巡回路を計算するヒューリスティックの一つ「クリストファイズのアルゴリズム」を扱いました。このアルゴリズムで計算する巡回路の長さは、最短の巡回路に比べて、たかだか1.5倍に抑えられることが理論的にわかっています。

今日の授業では、最初の発表者に、クリストファイズのアルゴリズムの概要を説明してもらい、次の発表者に、クリストファイズのアルゴリズムで計算される巡回路の長さが、最短の巡回路に比べて1.5倍に近づくという、理論上最悪の例題の1つを説明してもらいました。

このうち、後半の、理論上最悪の例題では、ある規則的な形で、ノード数がどんどん増えていくグラフを扱いました。このノード数が大きくなると、クリストファイズのアルゴリズムで計算される巡回路の長さの、最短の巡回路の長さに対する比が1.5に収束するというものです。テキストでは、クリストファイズのアルゴリズムで計算される巡回の長さを「だいたい」の長さで計算しており、発表者の人も、それに従って発表していました。

しかし、数学を専門に学ぶ学生としては、「だいたい」の部分を「はっきり」させて確認する必要があると考え、その場で、巡回路の長さの見積りを厳密に計算してもらいました。そして、厳密に計算した長さの比も、3/2に近づくことを確かめてもらいました。

今回の授業を通して、本で読んだり人から聞いたりしたようなことでも、自分で確かめることが大切なこと、自分で確かめる作業は、数学では頭を使えばできる作業もあること、こういう作業によって、物事の道理を確かめることの大切さを学ぶことも、数学を学ぶ意義の一つであること、を知る機会になったと思います。

発表者の人は大変だったと思いますが、引き続き、完全グラフの巡回路を、樹形図で表す部分について説明してもらいました。よく頑張ったと思います。

次回はいよいよ最終回です。巡回路を探索する際の「分枝限定法」などを扱います。どこまで進めるかわかりませんが、なるべくゴールを目指して進みたいと思います。

数学特別演習（第15回）

今日は、与えられたグラフに対し「巡回路」を直接作る代わりに、より条件を緩めた問題を解く「緩和法」を扱いました。

巡回路を直接求める問題に対して「より条件を緩めた問題」というのが「1-木」と呼ばれるグラフの計算です。1-木は、前回扱ったヒューリスティックで求めた巡回路からノードを1個取り除き、残ったノードに関する「最小全域木」を構成し、それに、先程取り除いたノードを辺でつないで加えることで作られます。

このとき、巡回路は1-木の集合に含まれるので、経路の長さが最小となる1-木が求まれば、その経路の長さは、経路の長さが最小の巡回路の長さの下界になります。ポイントは、最小1-木を求めるのにかかる計算量が、最小全域木を求めるのと同程度（＝多項式時間）の速さで、巡回路の長さの下界が求まるという点です。

さて、今日の最後の発表者は、来月卒業を控えた4年生の人で、今回、早く成績を出す必要もあり、発表してもらいましたが、最後に1年生の履修者にメッセージをもらいました。数学は1つ1つの理論の積み重ねであることや、いろいろな分野の関連性があること、そういったことを念頭に学習することの大切さを話してくれました。1年生にとっても、今回の話はよい刺激になったのではないかと思います。

次回は、巡回路を求める新しいアルゴリズムで、求めた巡回路の長さが、最適な巡回路に比べて高々1.5倍で抑えられるようなアルゴリズムを扱います。

数学特別演習（第14回）

今日は「巡回セールスマン問題」(Traveling Salesman Problem, TSP) が取り上げられました。TSP は、これまでの授業で扱った「ハミルトン閉路」と関連して、グラフで最短のハミルトン閉路を求める問題で、グラフ理論の中でも最も有名な問題の一つとして知られています。

私は、これまで、TSP を輸送計画問題としてしか知りませんでしたが、テキストに載っていた TSP の応用例として、電子機器の基板にロボットがドリルがついた腕を移動させながら穴を開ける際、ドリルの移動距離が最短になるような穴を開けるための順番を TSP として解くという問題が紹介されており、予想していなかった応用例があることに驚きました。それから、以前の授業で「プロッタがペンで図形を描く際のペンの最短経路を求める問題」が、中国の郵便配達員問題に帰着されることをやりましたが、図形が連結していないと、こちらも TSP となり、NP 困難な問題になるという事実も紹介され、与えられた問題がちょっと変わるだけで、計算の難しさが大きく変わることにも驚きました。

授業の後半では、TSP のなるべくよい解を求めるための「ヒューリスティック」の紹介がありました。次回は、これらのヒューリスティックが、どれだけよい解を与えているかの目安を知ることを一つの目的として「緩和法」について議論する予定です。

テキストも終盤に入ったところで、なかなか骨のある話題が続きますが、次の担当者の人達にも頑張って予習してもらいたいと思います。

数学特別演習：第13回の感想から

今回の授業は「NP問題」や「NP困難」といった、計算可能性の概念を扱いましたが、なかなか難しかったようです。

「NP困難」の問題は、理解するのも困難

といったように「文字通り」困難だった、という感想が多数ありました。

そのような中で

レナとヤンの理解力に脱帽です。

というように、本の登場人物であるレナとヤンの理解力の高さを指摘する感想もありました。たしかに、あれだけの会話でNP困難や、それを証明するための帰納法を即座に理解できるというのは、高校生にしては理解度が高いかもしれません。

それから、ある問題がNP困難である事実から、別の問題がNP困難になることを導く「帰納法」のような証明のアプローチについては

様々な事象の関係性や「これを示せばこれが証明できる」といった考え方は、数学ではとても重要なので、いい訓練だったと思います。

という感想がありました。たしかに、数学では、いろいろな分野で、このような理論の展開が行われているので、有益な指摘ではないかと思います。

あと、「辺の重みとして負の値を許したグラフで、最大でも一度だけノードを通過する最短経路問題」を解くアルゴリズムAから、ハミルトン閉路を求めるアルゴリズムBが求まる、という命題の証明の方針が「与えられたグラフに重み0の辺を加えて完全グラフにしてから、アルゴリズムAを適用させる」となっていましたが、ここで「重み0の辺を加えて完全グラフにする理由は何か？」という疑問が示されました。たしかに、これに答えるような説明はテキストの中には見つけられなかったので、この辺は私にとっても宿題になると思います。

授業の内容以外の感想としては

それぞれの発表者の評価アンケートでもあったらおもしろいかもしれないと思った。

という感想がありました。なるほど、おもしろいかもしれないけど、発表者にとってはいいプレッシャーになるかもしれませんね。ま、とにかく、授業の残り回数も少ないので、発表する人も聴く人も、テキストの最後までうまくたどり着けるよう、頑張ってほしいと思います。

数学特別演習（第13回）

今日は、計算の複雑さが話題の中心になりました。「決定問題」や「NP問題」、「NP困難」の概念、ハミルトン閉路を求める問題が「NP困難」な問題の一つである事実、等です。

ハミルトン閉路が「存在するか」を問う問題は「NP問題」であっても、逆にハミルトン閉路が「存在しないか」を問う問題が、いまだにわかっていない、というのは、ちょっと意外な気もしましたが、存在を証明するより非存在を証明する方が難しい、ということを考えると、なるほどと思います。

それから、このテキストの最小の方で出てきた「負の重さが許されるグラフにおいて、最大でも一度だけ通過が許される最短経路問題」を効率的に解くアルゴリズムがあるとしたら、そのアルゴリズムを用いてハミルトン閉路問題も効率的に解くことが可能である、という命題の証明を通して、あるNP困難な命題から別の問題がNP困難である事実を導くというやり方も扱いましたが、最初の命題の証明も、なかなかすぐにはピンとこない人もいたようです。

今回は、全体的にやや難しい内容でしたが、この辺から「巡回セールスマン問題」の話題に入っていくと思うので、がんばって予習／復習をしてほしいと思います。

数学特別演習：第12回の感想から

先週1月14日は、大学入試センター試験の準備で休講になりましたので、前回1月7日の分の感想から、印象に残ったものを取り上げたいと思います。

まず、オイラー路とハミルトン路の区別から。

オイラー路とハミルトン路の違いがあいまいになっていたので、再確認できてよかった。

この点は、私も予習していて気がつき「これはやっておかないとな〜」とチェックした箇所でしたが、同様の感想を書いた人が数人いたので、復習の効果はあったのではないかと思います。発表者の人には事前予告なしにいきなり突っ込んだので、戸惑ったかもしれませんが、ちゃんと前に戻って確認し、正しく答えていました。お疲れさまでした。

次に、ケプラーのあまり知らなかった一面について。

ケプラーにも宗教的な一面が垣間見えて、正直驚いた。

（今回の授業で）一番気になったのが、天体の軌道に正多面体を組み入れたケプラーの考えです。ここには、ケプラーはぶっとんだ考えをしたというよりも、ケプラーは天体に対してすごい熱意があるなと思いました。それは、ケプラーの第三法則が出るまでどれだけかかったか、考えてもわかると思います。

ケプラーの宗教的な宇宙観は、ケプラーの法則からすると、かなり意外に思えましたが、ケプラーが生きていた時代の宗教の存在について、認識を新たにするきっかけになりました。このような時代に地動説を唱えるのがどれだけ勇気が要ることだったのか、ちょっとだけ深くわかった気がします。「すごい熱意」というのもなかなかいいとらえ方だなと思いました。

そして、お正月明けの雑感。

小学生よりも始業の早い筑波大学。筑波は東京よりも寒いですネ。
提出年月日は一度2010と書き間違えました。そんな人が多かったと思います、今日は。

たしかに、筑波は東京よりも寒いような気がします。昔、東京との行き来に高速バスをよく使いましたが、冬の夜、利根川を越えた途端に、窓ガラスが曇り始めていた気が・・・。それから、2010年と書き間違えるというのも、お正月明けは多そうですね。皆さん、もう2011年に慣れましたか!?

新年早々遅刻・・・ということにならずによかったです。いよいよ全員が当たってしまいました。また自分の担当になってしまうのが心配で、昼も寝れません。

この授業の発表者は、毎回、学生さんの名前が書かれたカードをシャッフルし、ランダムに取り出して割り当てています。このほど、ようやく、クラスの全員に発表の当番が回り、次回から、2巡目の指名ということになりました。それにしても「昼も」眠れないというのは、ヒットですねぇ。今年も頑張りましょう！

数学特別演習（第12回）

今日は、今年、2011年年明け最初の授業です。幸い、ほとんどの人が元気に顔を出していました。

今日テキストを読んだ範囲は、前回の「ナイト跳び」の続きです。チェス盤の1つ1つのマス目をノードに置き換え、ナイトが通りうる経路を辺で結ぶと、グラフになります。ナイト跳びのゲームは、こうしてできるグラフのすべてのノードを1回ずつ通過する経路が存在するか、という問題になります。こういう経路のことを「ハミルトン路」といい、さらに、ハミルトン路が最後に最初のノードに戻ってくる場合、これを「ハミルトン閉路」と呼ぶ話が出てきました。前のごみ収集車問題で扱った「オイラー路」と、今回の「ハミルトン路」の違いについても復習しました。

次の章では、「ハミルトン路」の語源になった、アイルランドの数学者ハミルトンの紹介と、ハミルトンが発明したという「二十ゲーム (icosian game)」の話がありました。そこから、プラトンの正多面体と呼ばれる5つの正多面体（正四面体、正六面体＝立方体、正八面体、正十二面体、正二十面体）が紹介され、さらに、天文学者ケプラーと正多面体の関わりの話につながっていきました。

ケプラーというと、「ケプラーの第○法則」という、重要な法則を発見したことで有名ですが、一方で、当時発見されていた地球を含め6つの惑星の軌道と、プラトンの正多面体の関係に関する著作が紹介されています。その考察は、現代の自然科学の立場で見るとかなり宗教的ですが、彼の生きていた時代のヨーロッパの社会は、宗教と科学が現代よりもずっと近い位置にいたであろうことが推測され、興味深いものだと思います。

今日はこの辺で授業が終わりましたが、後半のハミルトンとケプラーの話題について発表してくれた学生さんは、予習を忘れていたそうで、直前にささっと読んだ程度と言っていましたが、それでも、内容をよく理解した上で、堂々と話す話術（？）に感心しました。

次回は、NP問題の話から、有名な巡回セールスマンの話につながっていくようで、内容も今回よりは複雑になりそうですが、次回の人達にも頑張ってもらいたいと思います。

数学特別演習（第11回）

今日は「中国の郵便配達員問題」アルゴリズムの最後、入力が有向グラフの場合の話から始める、ということだったのですが、最初の担当の学生さんが、次の章からしか予習をしていません、ということで、急きょ、その場で発表をしてもらいました。

学生さんも、突然のことで面食らったと思いますが、私や、前回発表した人の説明を手がかりに、何とか無事この部分を終えることができました。

次の章では「ナイト跳び」の問題に関する議論が始まりました。これは、チェスの「ナイト」の駒を、チェス盤の上で動かし、すべてのマス目を一度だけ通過させることができるか？という問題です。ここでは「バックトラッキング法」や「ウォーンスドルフの方法」（1823年、ヒューリステックな方法）が紹介され、ついでオイラーによる研究成果（1757年）が紹介されました。ここでもオイラーが登場している。すごいです。

以上、最初の部分で詰まったことと、「ナイト跳び」の部分はよく準備してきたようなことから、最初の人に時間を使ってもらい、今日は1人で授業を終えました。

後で聞いたのですが、今日話した学生さんは、前回の2人目の人から、次の範囲が「ナイト跳び」から、と聞いていたのだそうで（私は前回の授業終了の際に、正しい範囲を伝えていたはずですが）、今日は本人もさぞかし驚いたことでしょう。でも、最後まできちんと説明していたのはよく頑張ったと思います。

そんなわけで、今日は予想外の展開になりましたが、今年の授業も今日で終わりです。よいクリスマス、お正月を過ごし、また年明けに元気に再会できることを願っています。

数学特別演習：第10回の感想から

今日も、次の授業の前に、第10回の学生さん達の感想から、興味深い（おもしろい？）と思ったものを紹介します。（文面の一部を編集しています。太字も私によるものです。）

今日の範囲はとても内容が濃く、難しかったと思う。しかし、発表者が丁寧に説明してくれたおかげで、よく理解できた。

「今回の内容が濃かった」という感想は、複数寄せられました。私も予習して感じた通りだったと思います。一方で、発表者の説明がわかりやすかった、という感想も複数ありました。たいてい、2つの感想がセットで書かれていました。今回の発表者のお二人、お疲れさまでした。

今まで、この授業に限らず、数学を学んでいて、一体これは何に使うんだろうということが数多くあった。大学に入ってから、様々な場面で論理と同様に応用先も学び始めた頃から、ようやく「スッキリ」し始めた部分がある。

数学科では、数学自体が研究の対象になる場合が多いため、なかなか応用に目が届きにくいかもしれませんが、世の中には興味深い（解きたい）問題も数多く存在し、それらに対する数学の興味深い応用もいろいろあると思うので、そうした応用問題に目を向けるのも有益だと思います。また、そうした応用問題の内容を理解する上でも「数学力」を身につけておくと、役に立つのではないかと思います。

今回の範囲は、ページ数の割に内容が難しいところで、自分が読んだ時に理解できなかった部分を、他の人の解釈から理解することができた。
こんな風に色々な観点から物事を見るのは大切なことかもしれないなぁ。　みつを

内容は最初の感想とほぼ同じですが、最後の一言に思わずニヤリ。もし、相田みつをさんがこんな額を書いたら、どんな感じになったんでしょう、見てみたい気がしました。

数学特別演習（第10回）

今日は、前回のペアリングの話を受けて、ごみ収集車の問題を解くための「中国の郵便配達員問題のアルゴリズム」をやりました。

今回、アルゴリズムの各処理は文章で書かれており、それぞれに異なるアルゴリズムを適用した計算が含まれています。個々のアルゴリズムについては、前に出てきたものだったり、難しいものだったりするため、具体的な計算は省略されており、したがって、アルゴリズムを読んだだけでは、その動作を理解するのが難しいと思いますが、今日の授業では、今まで取り扱っているごみ収集車の問題を例に挙げて、アルゴリズムの動作を解説してくれましたので、わかりやすかったのではないかと思います。

その後、中国の郵便配達員問題の別の応用例として、プロッタによる図の動画手順というのがありましたが、さすがに今の学生さん達は、プロッタの実物を見た人はいませんでした。そうでしょうね、私も見たと思いますが、記憶があやしいですし・・・

今日は、さらに、有向グラフに対する解法に進みましたが、ここは途中で時間となりました。事前に予習した時に感じていましたが、今日の範囲はなかなかページ数の割に内容が濃かったようです。次回は、今日の続きで、有向グラフに対する解法（の途中）から始まります。

数学特別演習：第9回の感想から

数学特別演習の授業では、毎回、学生さんに感想を書いてもらっていますが、今日は、その中からいくつか、印象に残ったものを紹介したいと思います。（なお、ここでは著者は匿名にし、文面は内容に合わせて一部改変している箇所があります。また、引用文中の太字は私によるものです。）

次数が奇数のノードに対して「操業橋渡し運行」を使ったり、なるべく計算回数が少なくてすむように、O(n!) ではなく O(n^k) の計算量を目指す、など、今回の授業は数学的な工夫、テクニックに関する内容が多く、楽しみながら授業を聴くことができた。

現実の世界で数学の力が活かされるのは、高度な理論はもちろんですが、今回のような「ちょっとした工夫」もたくさん活かされていますし、これらも高度な理論に劣らず重要だと思います。そして、こうした「ちょっとした工夫」ができることを見抜くためには、数学をきちんと勉強して理解し、数学的な問題解決法を身につけてこそ可能になると思います。

今日の授業で良いことを知った。何か作業をする前に、その作業がどの程度大変なのかをしっかり確認しておくことが大切だということだ。これは確かにこれまでも無意識のうちにやっていたことだが、数式にすると大変かどうかがよりはっきりする。また、今回の内容は割と具体的だったので面白かった。

今回の授業の中で「計算を始める前に、計算量解析を行い、あらかじめ効率がよりよい手段を選ぼう」という趣旨の話をしました。まず、事前に仕事量を見積もるという点、そして、数式で具体的に仕事量を比較するという点をつかんでくれたのは、よかったのではないかと思います。

関係ないことだが、レナ（この本の主人公の女子高生）の水泳のタイムは、高校生にしては速いと思う。（本文では、100m自由形で1分3秒5だが、本人の自己ベストはもっと速いと言っている）

なるほど、こういう着眼もありましたか。本書では、レナは友達とスイミングスクールに通っていて、400mメドレーリレーを友達と4人で組む時に、誰がどの種目を泳げばベストタイムになるか？という、組み合わせの問題の一種を考える場面があるのですが、水泳のタイムに着目するのは、おもしろいと思います。この本はもともとドイツで（ドイツ語で）出版された本ですが、水泳のタイムに関して、本国ではどんな反応があったのか、興味深いところです。

以上のような感じで、読み進めています。

数学特別演習（第9回）

今日からこの授業も3学期です。今日は、まず、前回の「オイラーの定理」を受けて、オイラーの業績の紹介がありました。複素関数論で現われる公式「e^{i π}+1=0」は、オイラーが発見した公式ですが、これは小説「博士の愛した数式」でもモチーフになっていました。それから、ドイツに伝わる一筆書き遊び「サンタクロースの家」というのも紹介されていました。期せずしてちょうどよいタイミングの話題になったと思います。

その次に、ごみ収集車が街中のごみを収集して回る最短経路の問題を考えることになりました。収集車のランニングコストを抑えるためには、収集車の総走行距離をなるべく抑える必要があります。そのためには、なるべく一筆書きに近い形で街中を通り抜けたいわけですが、街路には行き止まりなどもあり、なかなかそううまくはいきません。そこで、この問題をなるべくよい形で解くために「操業橋渡し運行」というのを導入し、操業橋渡し運行が最短になる組み合わせを求める問題として「ペアリング問題」を解くという話になりました。

「ペアリング問題」は、組み合わせの問題の一種なので、これを素朴に解こうとすると、時間計算量が O(n!) になり、組み合わせの爆発が起きるわけですが、これを O(n³) の計算時間で解くアルゴリズムがあるという事実が紹介されました。

次回は、これらを組み合わせて、ごみ収集車の問題を解くということで、ダイクストラのアルゴリズム、プリムのアルゴリズムに続いて、久々に具体的な形のアルゴリズムが授業に登場する予定です。私も予習をしつつ、学生さんの発表を見守りたいと思います。

数学特別演習（第8回）

今日の授業では、「ケーニヒスベルクの橋渡り問題」から入り、グラフの辺と頂点の個数に関する性質に続き、グラフの「一筆書き」に関連する「オイラーの定理」をやりました。

今日最初の定理の証明の部分では、テキストに数学的帰納法に関する説明がありました。数学的帰納法は、このクラスの学生さん達のほとんどは高校の数学で習ってきているようでしたので、今日の授業では特に問題ありませんでしたが、テキストではかなり丁寧に説明しており、帰納法に初めて触れる読者に対しても十分配慮している様子がうかがえました。

余談ですが、以前、私がある論文を投稿した時、証明の冒頭に "By mathematical induction. (数学的帰納法で証明する)" と書いていたら、査読者の一人に "What is an induction that is not mathematical? (数学的でない帰納法はどんなんかいな?)" と、辛らつとも思えるコメントを書かれたことがあり、以来、帰納法による証明を書く際には "By the induction. (帰納法で証明する: 「数学的」という言葉を省いた)" と書くようにしています（という話もしました）。

グラフの辺と頂点の個数に関する定理も、オイラーの定理も、証明は、式を計算したりするたぐいのものではなく、論理的に考えるだけで理解可能なもので、学生さんの感想を読むと、その点に感心している人もいました。それにしても、橋渡り問題を数学的にとらえて「グラフ」という抽象的な概念を創り出し、問題を解いたオイラーはやはりすごい人だなということを、再度実感しました。

2学期の授業は今日でおしまいです。残念ながら、全員に発表が回る程の回数がありませんでしたが、発表が回ってこなかった人達には、今学期の復習をレポートで出してもらう予定です。学生さんの感想に「授業の回数を重ねるにしたがって、発表の内容や方法のレベルが上がってきた」という指摘がかなりありました。こういう点で、お互い刺激しあえるのはこの授業の収穫だったのではないかと思います。3学期も、この調子での活発な授業になることを期待しています。

数学特別演習（第7回）

今日の授業では、greedy algorithm（欲張りアルゴリズム）とマトロイドの関係から始まりました。

マトロイドは、主に、数学の中でも組み合わせ論と呼ばれる分野において、線形代数の「1次独立」の概念をより抽象化した、「独立」の概念や構造のことをいいます。もちろん、この授業ではマトロイドの詳細には立ち入りませんが、今勉強しているグラフの木構造が、マトロイドの一例であること、ある与えられた構造において、greedy algorithm が常に最適な解を見つけるならば、その構造はマトロイドどなること、などの事実に触れました。

マトロイドは、1930年代に、幾何学者のホイットニー (H. Whitney) によって発見され、世界に広まった概念ですが、実は、同時期に、日本でも独立に発見されたことがわかってきました。東京文理科大学（筑波大学の前身の一つ）の中澤武雄氏が、東京文理科大学の紀要 (Science Reports of the Tokyo Bunrika Daigaku, Section A) に掲載した論文がそれです。この辺の概要は、筑波大学数学系のwebサイトにおいて、斎藤明先生による解説が掲載されています。

中澤武雄の数学的業績 (斎藤 明)
http://www.math.tsukuba.ac.jp/kouseki/knak/nakasawa.html

また、西村泰一先生と黒田享先生により、中澤氏の略歴と業績、マトロイドに関する論文（ドイツ語）およびその英訳が書籍にまとめられ、出版されています。

A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory
Nishimura, Hirokazu; Kuroda, Susumu (Eds.)
Birkhäuser, Basel, 2009, XII, 234 p. 14 illus., Hardcover
ISBN: 978-3-7643-8572-9

なお、この本のプレプリント（全文）は、つくばリポジトリ（筑波大学の機関リポジトリ）にて入手可能です。 http://hdl.handle.net/2241/104009

授業の後半では「ケーニヒスベルクの橋渡り問題」が取り上げられました。今後は、グラフの一筆書きの問題に話題を変えて話が進みそうです。

数学特別演習（第6回）

今日の授業では、最小全域木 (MST) を構成するプリム (Prim) のアルゴリズムが正しく動くことの証明から行いました。背理法を用いた証明で、理解に若干難しいところもあったかもしれませんが、発表者の人も頑張って説明できたと思います。

授業の後半では、プリムのアルゴリズムのようなものが、一般に greedy algorithm （「欲張り」アルゴリズム）と呼ばれる話や、MST を構成する別の greedy algorithm の例として、クルスカルのアルゴリズムを見ました。

次回は、greedy algorithm が、なぜ、正しく MST を構成できるのか、その辺の舞台裏を探っていくと思います。次回の発表者にも期待したいと思います。

数学特別演習（第5回）

今日の授業では、まず「前処理」（第12章：仕事の前に一仕事）で、最短経路探索の前に、探索対象をある程度絞ったり、探索に直接関係ないノードを減らしたりして、探索にかかる計算量を減らす工夫についてやりました。

ついで、「最小全域木 (Minimum Spanning Tree: MST)」の話（第13章：木々の合間で鬼ごっこ）をやりました。与えられたグラフに対する「最短経路木」は、開始ノードを変えるとMSTでもあり「得る」という部分と、本の例題として扱っている最短経路木はMSTに等しくない証明が、ちょっと複雑だったかもしれませんが、テキストに沿って順を追って考えていくと、それ程難しいことではないと思うので、よく復習してほしいと思います。

ちなみに、第13章の冒頭、「チューリングテスト」に合格したプログラムに賞金を出すという、ローブナー賞 (Loebner prize) というのが紹介されており、調べてみたところ、毎年コンテストが行われていて、今年のコンテストはなんと明日行われるのだそうです。どういう結果になるのでしょうか。

来週の授業では、今日登場したMSTを計算するアルゴリズムをやると思います。次の担当の人にも頑張ってほしいと思います。

数学特別演習（第4回）

今日の授業では、ダイクストラのアルゴリズムの計算量の見積りを中心にやりました。一般のn個のノードを考えた場合というのは、なかなかピンとこないようですが、数個の具体例を考えて計算すると、納得できたという人が多いようでした。

あとは、グラフの辺の重みがノード間の距離に対応するような場合は、直観的な距離の探索が役に立つ・・・というのは、すでに始点と終点を結ぶ経路を1つ知っていた場合、最短経路は、始点と終点を焦点とし、すでに知っている経路の距離を長軸にもつ楕円の内部に存在する、という話も出ましたが、この話は、多くの人達にとって新鮮だったようです。

次回は、前処理の話と、グラフの「最小全域木（スパニングツリー）」の話になると思います。私も予習を頑張りたいと思います。

数学特別演習（第3回）

前回の授業の感想を一通り読みましたが、学生さん達の多くが書いていた感想として「アルゴリズムに入り、内容が急に難しくなった」というのがありました。一方で、数人の人達が書いていた感想として「最初にアルゴリズム全体を見た時には、とても理解できそうに見えなかったが、少しずつ内容を読んでいくと、徐々に理解できるようになった（気がした）」というのもありました。

以上の2点を踏まえて、現時点で、学生さん達には、以下のことを伝えました。

• ある内容が理解できない時は、何度でも本のページを戻って、自分で納得できるようになるまで考えることが大切。
• すべての内容を一度に理解するのは大変なので、少しずつ段階を追って理解を深めていくことが有効（な場合が多い）。

さらに、これらはあくまでも私の意見で、自分に最も合ったやり方は、結局、自分で見つけるしかない （と思う。これも私の意見ではありますが）と添えました。

あと、上記で「理解できるようになった（気がした）」と書きましたが、理解できた「気になる」というのも、数学を学ぶ上では大切だと思います。もちろん、ちゃんと理解する必要があるので、本当に自分が理解できたかどうか、用心する必要がありますが、その上で「わかった！」というのが、最初は「気」だけだっとしても、「わかった気になる」と「そのチェック」を繰り返すことにより、徐々に本当の理解に収束していくものと信じていますし、そのくらいの楽天性もあった方がよいかもしれません。

さて、今日の授業では、前半で、ダイクストラのアルゴリズムの残りの部分を説明してもらい、後半では、グラフの辺に負の重みがあった場合や、グラフに閉路が存在するような場合の最短経路の探索について、発表してもらいました。2人とも、テキストの内容をよく読んで、説明も工夫していたと思います。

次回は、ダイクストラのアルゴリズムの計算量解析が話題の中心になると思いますが、次回の発表も楽しみにしています。

数学特別演習（第2回）

今日は2回目の授業でしたが、今日の発表者の最初の人が、グラフの例題に対して、最短経路を求めるアイデアの提示を行い、引き続いて2人目の人が、ダイクストラのアルゴリズムの説明に入りました。

テキストの難度は、前回に比べるとかなり増した様子です。今回集まった学生さんは、ほとんどが数学科の1年生ですが、授業中に尋ねたところ、プログラミングの経験や、アルゴリズムの疑似コードを読んだ経験のある人は皆無で、全員0からのスタートのようで、いきなり疑似コードを読むのはかなりのチャレンジのようでした。

発表している人も大分苦労しているようでしたが、それでも頑張って最後まで発表を続けたところは評価したいと思います。授業の中でのアドバイスとして、テキストで扱うような易しい例題に対して、実際にアルゴリズムが動く様子を、1ステップずつ、正確に頭の中で再現することを呼びかけました。この辺の頭の使い方は、数学を学ぶ時とほぼ1対1に対応すると思います。

次回は、ダイクストラのアルゴリズムの中心部分を読み進めていくことになると思いますが、来週の発表者の人達にも期待したいと思います。