easyarithmetician's tips and announcements: 2016-07

2016-07-26

今回は、この授業の最終回でしたが、前回残したハミルトングラフに関する定理の系を証明してもらったのに続き、最短経路探索と、中国の郵便配達問題のアルゴリズムを説明してもらいました。

「中国の郵便配達問題」という名前は、証明した人が中国人ということで、「中国の郵便配達」とは関係ありませんが、この定理の他にも、別の授業で取り上げた「中国剰余定理」のような呼ばれ方があります（主に西洋の視点と思いますが）。

今回のテキストでは、アルゴリズムがきちんと提示されていたわけではありませんでしたので、必要があれば、他の本でアルゴリズムを確認するとよいのではないかと思います。

以上、今学期でテキスト全体の1/3程を読みましたが、授業中は積極的な質疑応答が行われ、よい雰囲気で授業ができたのではないかと思います。今後も、履修者の皆さんには、本を読んだり、仲間と議論したりすることで数学を理解し、これからの各自の研究などにつなげていってもらえればと思います。

今回は、本授業の最終回でしたが、有理数の再構成について説明しました。今回は分量がやや多く、ちょっと急いでしまいましたが、講義ノート等で内容を補っていただければと思います。

以上、春学期の授業が一通り終わりました。計算機の構成、演算のしくみから、主に1変数多項式の基本的な演算、そして拡張Euclid互除法が中心になりました。内容は基礎的なものがほとんどでしたが、自分で手を動かして、アルゴリズムを理解してほしいと思います。

秋からは卒業予備研究が始まりますが、計算機分野への応募もお待ちしています。

今回は、拡張Euclid互除法の応用例として、中国剰余定理とその計算を紹介しました。

次回がこの講義の最終回ですが、次回は有理数の再構成について説明したいと思います。

なお、授業サポートページが、アクセス権設定の不具合で閲覧不能な状態が続き、ご迷惑をおかけしましたが、このほど、別の場所に予備のページを開設しましたので、講義ノートのダウンロードや講義録画のアクセスはそちらからご利用ください。

今回は、ハミルトン・グラフについて論じました。特に、単純グラフがハミルトニアンになるための十分条件の一つを与えているOreの定理で、頂点数が一般のnの場合の証明について、詳しく議論しました。

授業日程の都合で、次回授業は7月26日、これが最終回となります。次回は、単純グラフがハミルトニアンになるための別の十分条件として知られているDiracの定理について調べたのち、グラフのいくつかのアルゴリズムについて学びます。

現在、私の仕事場のホームページ https://www.math.tsukuba.ac.jp/~terui/ が閲覧できない状態になっています。より正確に申しますと、ページを表示するとログイン画面が現れます。

これは、私の意図でそのようにしたわけではなく、ベースになっているwikiのシステムをアップグレードしたところ、アクセス制御に何らかの不具合が発生している模様です。

現在、原因の究明と復旧に努めているところです。ご不便をおかけしている方々にお詫びします。以下、いくつかのう回先です。

今回は、拡張Euclid互除法の応用として、剰余環で与えられた元が乗法の逆元をもつ際に、その逆元（法逆元）を求める方法について説明しました。

次回は、拡張Euclid互除法の別の応用として、中国剰余定理の構成的計算法を紹介する予定です。