数理科学II（第22回）

今日も、前回に引き続き Scheme の入門でした。今回は、LISPの基本関数（5大関数）（Scheme でいう car, cdr, cons, pair?, eq?）、数の四則演算と数値に対する関数、関数の定義と実行のしかた (define)、制御構造として、逐次（処理） (begin) について説明しました。

次回は、引き続き Scheme の説明を行う予定です。

数学特別演習（第14回）

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

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

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

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

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

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

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

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

そのような中で

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

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

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

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

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

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

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

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

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

微積分III演習（第6回）

まず、前回の授業の際に回収したレポートを評価しましたが、おおむね問題の内容と解法を理解し、よくできているようでした。今日、返却しましたが、足りない部分は各自復習してもらいたいと思います。

今日も、関数の極限値に関する問題を中心にやりました。先週、手詰まりになり、保留になっていた人も、今日はちゃんと解けていたのでよかったと思います。私の解説がちょっとゆっくりになったせいか、若干時間が足りなくなり、数問板書してもらった問題が残ってしまいました。時間配分は難しいですが、なるべく問題が残らないよう、気をつけたいと思います。

来週も、関数の収束に関する問題演習が中心になると思いますが、その次のテーマである、関数の連続性、一様連続性に関する演習問題も配りました。授業回数があと3回なので、今学期の演習は一様連続性あたりまでかと思いますが、次回も問題発表がたくさん行われることを期待します。

計算機演習（第5回）

今日の授業は、線形代数の第2回ということで、グラム・シュミットの直交化法と、Table関数を使った規則的なリスト生成や、リストの操作を行いました。

リストの生成や操作の部分は、これまでの数年間「発展学習」の方に含めていた内容でしたが、今年度、カリキュラムを再編成した際、今後学生さん達が使う可能性のあるデータ処理等に役立つのではないかとの判断で、必修の課程に含めました。

内容は全体的に易しかったようで、レポート締切は次回の授業日ですが、早くもレポート提出がそれなりの数ありました。次回からは、微積分の内容を扱います。

数理科学II（第21回）

今日は、前回に引き続き、多倍長整数と有理数の表現、リスト表現と進んで、プログラミング言語Lisp (Scheme) の説明に入りました。

といっても、Schemeの方は、atom と pair の説明をしたくらいです。次回は、数の演算、関数定義、再帰やらの説明を行って、1変数多項式の実装に進めるよう、必要最小限の準備をしたいと思います。

数学特別演習（第13回）

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

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

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

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

微積分III演習（第5回）

今日は、前回出題したレポート課題のレポートを回収した後、関数の極限に関する問題をやりました。

内容は、数列の極限とそれ程変わりありませんが、不等式で評価する際に作る、上から抑える関数の作り方など、私自身も授業をやりながらわかってきた部分もあります。

学生さん達の発表は、正解ばかりとは限りませんが、間違えた部分をよく検討することは、発表した本人だけでなく、クラス全体にとっても有益です。比較的リラックスした雰囲気の中で、これからも、誤りを恐れず、積極的に発表してほしいと思います。

次回も、同じテーマで引き続き演習を行う予定です。（そろそろ次のテーマの用意も必要かな・・・）

数理科学II（第20回）

今年の月曜日の授業は、なんとなんと、月のまん中を過ぎて下旬にさしかかろうという今日からです。しかも、昨日は大学入試センター試験のため、今日が火曜日のところ、曜日振替で月曜日の授業ですので、これがなければ、月曜日の授業は1月の間ほとんどなかったかもしれません。

そんなわけで、この授業も、前回からほぼ1か月ぶりです。前回「これだけ時間があるなら、ちゃんと次の講義ノートが作れるはずですよね。」と書いたのですが、どういうわけか、今日の授業の講義ノートを清書したのは昨夜でした、トホホ・・・（下書きはお正月明けに準備していたのですが。）

さて、今日から今年度の残りは、これまでとがらっと趣向を変えて、多項式演算の実装の話をします。といっても、今回の受講者は、予備知識の量もさまざまですから、なるべく基本的な部分に絞った話をします。したがって、実装のレベルはおもちゃの程度かもしれませんが、受講者の人達には、本質的な部分を提供し、あとは必要に応じて、自分達で学び進められるようなきっかけになれば、と思います。

今日のところは、計算機のしくみ（計算機の5大装置、ビット、メモリ空間、ワード）の話に引き続き、計算機上の数の表現として、整数、そして、数式処理でも使われる多倍長整数の途中まで話をしました。

次回は、これを踏まえて、この授業で使うプログラミング言語Schemeの話へと進めたいと思います。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

微積分III演習（第4回）

今日は、この授業の今年最初の授業でした。最初に配った、数列の極限に関する演習問題で、残った問題（主に証明問題）をやってもらいました。

問題数が少なかったので、時間が余るかな？と思いましたが、案外時間は余らずに収まりました。板書や説明の時間を割と丁寧にとったためと思います。

次回は、関数の極限に関する演習問題から、選択で数問をレポート課題にしました。その上で、これらの演習問題を授業で取り上げる予定です。

計算機演習（第4回）

今日の授業は、今年初めての授業でしたが、線形代数の第1回ということで、Mathematica上でのベクトル（リスト）や行列（リストのリスト）の扱い方を行い、ついで、対角化可能な正方行列に対して、行列の n 乗を計算する計算を行いました。

今日のテーマは内容が比較的易しかったためか、授業時間内にレポートを進める人も多く見られたようです。次回は、引き続き線形代数の計算を行い、加えて、要素に規則性のある行列やリストの効率的な求め方についてやりたいと思います。

数学特別演習（第12回）

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

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

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

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

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

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