お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、前回の内容に関連する内容として、除算のアルゴリズムと計算量に関する補足説明を行いました。
前回「行列積の法計算」では、中国剰余算法を用いて整数を成分にもつ行列の乗算の効率化を図る手順を紹介しましたが、その中で、中国剰余算法の計算量に触れました。そこで、今回は、これに関連して、1変数多項式の除算の計算量、多倍長数を単精度数で割る除算のアルゴリズムとその計算量について紹介し、中国剰余算法の計算量の導出を行いました。
以上、春学期の授業を通して、多倍長数や1変数多項式の四則演算のアルゴリズムと計算量や、拡張Euclid互除法のアルゴリズムとその応用を中心に紹介してきました。代数的な計算のアルゴリズムへの理解を深めていただければと思います。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、前回に引き続き、数式処理に関連するいくつかのテーマを取り上げました。
まず、ある履修者の人が現在取り組んでいるという、openFrameworksというC++のツールキットについて紹介してもらいました（現在、openFrameworksを使った映像制作を行っているようです）。
次に、学類3年で私の学類の授業を履修している人ですが、Haskellで、多変数多項式の演算と、Groebner (グレブナー)基底を計算するBuchberger（ブッフバーガー）アルゴリズムを実装したというので、紹介してもらいました。
最後に、私の話題で、1階述語論理式の量化子消去 (QE) を用いた大学入試問題の解法について、その概要を紹介しました。
今回は、モジュラー算法 (modular algorithm) の一例として、「行列積の法計算」を紹介しました。
「モジュラー算法」は、ある特徴をもつアルゴリズムの総称ですが、計算途中に多倍長数が現れるアルゴリズムを、いくつかの互いに素な、より小さい数を法とする剰余環上で計算し、最後に中国剰余定理を用いて、整数上の解答の係数を計算するものです。今回は、行列積の計算を例に取り上げ、モジュラー算法によって計算の効率化が図られることを紹介しました。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、数式処理に関する種々の話題から、私の専門分野である「数式・数値融合計算」を取り上げ、近似最大公約子 (GCD) のアルゴリズム研究の経過や動向について解説しました。
次回も、数式処理に関する種々の話題から、テーマを取り上げて解説する予定です。
今回は、拡張Euclid互除法の応用の一つとして、有理数の再構成を紹介しました。具体的な応用方法は2種類あり、1つは、有理数演算を剰余環に埋め込んで計算し、計算結果から有理数の計算結果を復元するもの、もう1つは、小数で近似された有理数からもとの有理数の既約分数表現を求めるものです。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、部分終結式の基本定理を用いた係数膨張の防止策として、縮小PRS算法 (Reduced PRS Algorithm) および部分終結式PRS算法 (Subresultant PRS Algorithm) を紹介しました。
次回以降は、多項式剰余列やGCD計算に関連する話題を紹介したいと思います。
今回は、拡張Euclid互除法の応用例の一つとして、中国剰余定理による連立線形合同式の解法を取り上げました。
次回も、拡張Euclid互除法の応用例の一つとして、有理数の再構成の計算を紹介します。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、Euclid互除法の応用例の一つとして、実数の連分数展開を取り上げました。
連分数は、数学の理論や計算の分野でしばしば用いられており、例として、初期の円周率の近似値の計算でも用いられています。
与えられた数が有理数の場合は、Euclid互除法を用いて、その連分数展開を求めることができます。与えられた数が無理数の場合は、Euclid互除法は使えませんが、有理数の連分数展開と同様、与えられた数を整数部と小数部に分けることで、有理数と同様の連分数近似を求めることができます。
次回は、拡張Euclid互除法の応用例の一つとして、中国剰余定理を取り上げます。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
前週は出張により、授業を坂井先生とTAの皆さんにお願いしましたが、前週でMathematica編が終了しました。Mathematica編の最終回は、タートルグラフィクスによるフラクタル図形の描画を行いました。
今週から、坂井先生が担当するHaskell編に入りました。第1回目となる今回は、Haskellの言語環境の起動と対話的操作、テキストエディタの起動などから始まりました。
今回は、拡張Euclid互除法の性質について触れるとともに、応用の一つとして「法逆元の計算」を紹介しました。これは、剰余環で与えられた元に乗法の逆元が存在する際に、その逆元を拡張Euclid互除法を用いて効率的に計算するものです。
次回も、拡張Euclid互除法の応用例を紹介していきます。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回も、部分終結式と多項式剰余列の関係を示した「部分終結式の基本定理」の証明に向けて、2つ目の補題を説明しました。前回の補題は、1回の多項式除算に関するものでしたが、今回は、それを、多項式剰余列の中の計算に当てはめたものです。
次回は「部分終結式の基本定理」の証明を行う予定です。
このたび、千葉県高等学校教育研究会数学部会の平成29年度総会・春季研究大会において、標記の講演の機会をいただきました。
今回の会場は千葉県茂原市の千葉県立長生高校で、今年創立130周年を迎えるという伝統校です。最初、このお話をいただいた際に、過去の講演者のリスト（部会のホームページに過去の記録が掲載されています）を見たところ、錚々たる顔ぶれで、自分も話を聴きたいような先生方ばかりでした。そのような中で、自分にどんな話ができるだろうと考えた結果、これまで共同研究に参加させていただいている「東ロボ」に関連し、数式処理で数学の演習／入試問題を解く手法の紹介を行うことにしました。
講演では、「東ロボ」のプロジェクトの概要の紹介、数学ソルバによる解答の流れの紹介を行った後、「実閉体上の一階述語論理式の量化子消去 (Quantifier Elimination; QE)」に焦点を当て、「実閉体上の一階述語論理式」とはどんなものか、QEとはどのようなことを行うものかを紹介しました。この中では、オンラインで使える数式処理システム CoCalc 上で、QEパッケージの QEPCAD を使ったQEの計算も紹介しました。本当は直接オンラインでデモンストレーションをやりたかったのですが、残念ながらインターネット接続がうまくいかなかったので、あらかじめファイルに保存しておいた計算セッションを見せながら紹介しました。
そして、QEの汎用アルゴリズムの一つである Cylindrical Algebraic Decomposition (CAD) の紹介を行いました。もちろんCADの全体像を説明する時間はありませんから、今回は、CADの要素として、1) 与えられた多項式の値が正、0、負になる領域を調べること、2) しかし、各変数ごとにすべての値を調べるのは原理的に無理なので、与えられた多項式の実零点が重なったり、実零点の個数が変化したりする特徴的な部分を調べること、3) そのために、与えられた多項式の終結式や判別式を求めること、4) その上で、1変数代数方程式の実零点の数え上げを行うこと、を説明しました。そして、1変数代数方程式の実零点の数え上げの方法としてSturm法を紹介しました。
こんな形で今回の講演を行いましたが、講演後の高校の先生方との意見交換では、いろいろと貴重なお話も伺い、大変有意義な時間になりました。今回、このような機会を作ってくださった皆様に感謝申し上げます。なお、今回のような内容の講演や、この内容に興味／関心を持つ高校生の人達とのQE計算の実習など、ご希望がございましたら、時間が許す範囲でお応えしたいと思います。
今回は、部分終結式と多項式剰余列の関係を示した「部分終結式の基本定理」の証明に向けた、最初の補題を説明しました。
次回も引き続き「部分終結式の基本定理」の証明に向けた説明を行う予定です。
今回は、Euclid互除法および拡張Euclid互除法のアルゴリズムについて説明しました。前提となる環の基本事項は既知として話を進めます（必要事項は一通りテキストにも載っています）。
次回からは拡張Euclid互除法の応用例を紹介していきます。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、Mathematica編の第6回ということで、「ルールベースドプログラミング」および「手続き型プログラミング」を取り上げ、Mathematicaによるプログラミングの初歩を紹介しました。
次回は、Mathematica編の最終回ということで、フラクタル図形の描画を行います。
今回は、前回導入した部分終結式の定義に関連する事項として、部分終結式を1つの行列式で表す表示について説明しました。
次回からは、部分終結式と多項式剰余列の要素である多項式の関連について、「部分終結式の基本定理」を目標に説明していきます。
今回は、まず、1変数多項式と多倍長整数の乗算のアルゴリズムと計算量評価について説明しました。引き続いて、整数の剰余つき除算の用語の定義などを確認し、1変数多項式の剰余つき除算のアルゴリズムについて説明しました。計算量評価は授業後のレポート課題としています。
今回でテキストの第2章は終わりです。次回からは第4章「ユークリッド互除法」に進みます。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017