数理科学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問題の話から、有名な巡回セールスマンの話につながっていくようで、内容も今回よりは複雑になりそうですが、次回の人達にも頑張ってもらいたいと思います。

数学特別演習（第11回）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

微積分III演習（第3回）

今日も、数列の極限の問題を中心に解きました。数列の発散のε-N 法による定義や、数学でよく使う s.t (such that) 節などの説明も加えました。

講義は2クラスに分かれていて、1つのクラスでは関数の極限をすでに習い、もう1クラスではまだ習っていなくて、関数の連続性と一緒にやる予定とのことですが、関数の極限は計算練習も必要な部分ですので、ちょっと講義を先取りする形ですが、演習問題を配りました。

実際に解いてもらのは来年になりますが、新しい年も頑張りたいと思います。

計算機演習（第3回）

今日は、Mathematicaを使っての授業の第2回ということで、学生さん達の方も、端末やMathematicaやMoodleの操作にも少しずつ慣れてきたのではないかと思います。

今日が前回授業のレポートの締切日でもありますが、ほとんどの人が授業時間内に提出を済ませているようでした。

次回の授業は来年になります。次回は線形代数の話題に入りますが、学生さん達の活動に期待したいと思います。

数理科学II（第19回）

今日は、前回途中で終わった、部分終結式PRS算法の残りの部分について説明し、多項式剰余列の話が一通り終わりました。その後、数式処理システムMathematicaを用いて多項式剰余列を計算のデモンストレーションを行いました。

本来であれば、この後で「縮小PRSと部分終結式PRSを計算して、係数膨張の縮小を確かめる」という課題を出したいところですが、拡張Euclid互除法のアルゴリズムの解説、というか、1学期のレポート課題の答え合わせが残っていまして、これをやってからの方がよいだろう、と思います。アルゴリズムを書き下す部分をなぜ残しておいたかというと、この次のテーマとして、数式処理（多項式演算）の実装の話を考えており、そこではプログラミング言語も使って具体的な話をしますから、アルゴリズムについても、そこでちゃんと話をしよう、と思っているわけです。

そんなわけで、今年は、昨年と比べて、いろいろ事情はありましたが、2か月遅れで同じ話を終えました。2回は出張による代講、1回は集中講義、1回は別の授業の打ち合わせ、1回はアルゴリズムの基本を昨年よりも丁寧に話した部分、ということで、5回分で2か月遅れ!? と思ったのですが、期末試験の日程や秋休みなどを考慮すると、このくらいの遅れはやむを得ないようです。

昨年の講義回数からすると、あと6〜7回ですので、それまでに次の内容をうまくまとめられるようにしたいですね。次の講義は、1月18日（火）（月曜日の振替授業）ですので、約1か月先です。・・・これだけ時間があるなら、ちゃんと次の講義ノートが作れるはずですよね。頑張りましょう。今年もお疲れさまでした。来年もよろしくお願いします。

数学特別演習（第10回）

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

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

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

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

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

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

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

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

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

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

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

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

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