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

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

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

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

そのような中で

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

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

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

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

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

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

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

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

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