数学特別演習（第5回）

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

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

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

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