今回は、前半で、モジュラー法の一つとして、中国剰余定理を用いた1変数多項式のGCD計算のアルゴリズムについて説明しました。後半では、1変数多項式の無平方分解の話題に入り、無平方分解に用いる性質を説明しました。
次回は、今回の説明を踏まえ、無平方分解のアルゴリズムを紹介します。
お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、前半で、モジュラー法の一つとして、中国剰余定理を用いた1変数多項式のGCD計算のアルゴリズムについて説明しました。後半では、1変数多項式の無平方分解の話題に入り、無平方分解に用いる性質を説明しました。
次回は、今回の説明を踏まえ、無平方分解のアルゴリズムを紹介します。
今回と次回では、常微分方程式の数値解法を扱います。
今回は、常微分方程式の種類と問題例を紹介したのち、微分方程式の差分化による差分方程式の導出について説明しました。
次回は、差分法のアルゴリズムを紹介し、代表的な問題に対する差分法の計算について説明します。
今回は、モジュラー法の中から、Hensel構成による1変数多項式のGCDの計算を行うアルゴリズムを紹介しました。
次回は中国剰余定理に基づく1変数多項式のGCDの計算法を紹介し、無平方分解の話題に進みます。
今回からは、1変数多項式の最大公約子 (GCD) 計算のうち、モジュラー法の話題を紹介します。今回は、モジュラー法の背景と、モジュラー法を用いる際に必要となる、多項式の約元や公約式のノルムの見積もりについて説明したのち、Hensel構成の基礎となるHenselの補題の証明を行いました。
次回は、Hensel構成によるGCD計算のアルゴリズムの説明から行う予定です。
今回は、1変数関数の定積分の計算法として、台形則、シンプソン則およびその一般化であるロンバーグ積分法を紹介しました。
次回からは常微分方程式の解法について説明します。
今回は、前回までで証明した「部分終結式の基本定理」に基づき、多項式剰余列の係数膨張を抑える「縮小PRSアルゴリズム」および「部分終結式PRSアルゴリズム」の紹介を行いました。
次回からは、モジュラー法による多項式の最大公約子 (GCD) 計算の効率化手法の紹介に入ります。
今回は、前回のラグランジュ補間のアルゴリズムに続き、ラグランジュ補間の誤差評価を行った後で、スプライン補間と最小二乗法について説明しました。
次回は数値積分の説明を行う予定です。
今回は、前回の内容を踏まえ、2つの補題の証明をした後で「部分終結式の基本定理」の証明を行いました。
次回は、部分終結式の基本定理に基づいて多項式剰余列の係数膨張を抑えるアルゴリズムの紹介を行う予定です。
今回は、前半で、1変数方程式の近似解法として「2分法」および「ニュートン法」を紹介しました。後半では、曲線の推定方法の一つとして「ラグランジュの補間法」を紹介しました。
次回は、ラグランジュの補間法の誤差評価を説明し、曲線の推定の後半として、スプライン補間法と、最小二乗法について説明します。
今回の前半では、前回の話の一般化として、多項式剰余列の各要素の係数を、最初に与えられた多項式の係数を成分にもつ行列式で表す方法について紹介し、部分終結式の導入を行いました。後半では、部分終結式を1つの行列式で表す表現を与え、この授業の目標の一つである「部分終結式の基本定理」に至る補題の証明でよく用いられる、部分終結式を表す行列式の行変形について議論しました。
次回は、「部分終結式の基本定理」の証明の準備として、補題の証明に進む予定です。
今回は、まず1変数多項式の多項式剰余列と拡張Euclid互除法を導入しました。次に、部分終結式の理論の導入として、1回の擬除算における擬剰余の係数を、入力多項式の係数を成分となる行列式で表すことで、1変数多項式の除算を行列の行消去で表せることについて説明し、終結式とGCD、多項式剰余列の関連性について説明しました。
次回は、今回の考察をさらに多項式剰余列に進める予定です。
今回は、連立1次方程式の解法から「反復法」と呼ばれる方法、具体的にはヤコビ法、ガウス・ザイデル法、SOR法を紹介しました。
連立1次方程式の説明は今回で終わりです。次回は(非線形)方程式の数値解法と、関数補間の話題に進みます。
今回は、1変数多項式の加減乗除のアルゴリズムのその計算量、1変数多項式の最大公約子 (GCD)、最小公倍子 (LCM) について説明しました。
次回は、拡張Euclid互除法から部分終結式の導入に進む予定です。
今回と次回の授業では、連立1次方程式の解法を紹介します。
今回は、「直接法」と呼ばれる解法から、おなじみガウスの消去法とLU分解による解法を紹介しました。普通、数学におけるガウスの消去法は行簡約から簡約階段行列の計算でおしまいですが、今回は、枢軸選択(ピボッティング)により、アルゴリズムを正しく動かす、もしくは数値解の精度を向上させる部分も説明しました。
次回は「反復法」と呼ばれる解法を紹介します。
今学期、大学院の授業を担当します。昨年まで「数理科学II」という授業でしたが、今年は自分がかかわる授業科目の改編があり、「計算機数学」という授業科目名になりました。学類の授業科目名と紛らわしいので、記事のタイトルは「計算機数学(大学院)」とします。
この授業では、計算機代数に関するトピックを扱います。前半では1変数多項式の最大公約式(GCD)と部分終結式アルゴリズム、後半では多項式の因数分解を扱います。
今回は、授業のガイダンスを行い、多項式環の性質を復習し、1変数多項式の擬除算と、アルゴリズムの記法を紹介しました。次回は1変数多項式の四則演算のアルゴリズムに関する議論を行う予定です。
本年度も秋学期に数学類開設授業科目「計算機数学II」を担当します。
この授業では、数値計算を扱います。今回は、数値計算の目的や用途、数値計算の流れ、浮動小数や誤差、計算量、その他の基礎事項を扱いました。
次回は連立1次方程式の解法を紹介します。
今回はプログラミング言語Scalaの最終回で、再帰的定義によるリストの作成、リストの長さなどを求める(オブジェクト指向の)計算、リストに対するmap関数といった内容を取り上げました。
これでこの授業は一通り終了です。本年度は、数式処理システムMathematicaに加えて、バージョン管理システムGit、文書処理システムLaTeX、プログラミング言語Scalaを使い、数学と計算機が関わる内容をいくつかの角度から学びました。プログラミングは、最初は戸惑う人もいたようですが、回数を重ねるにつれて、何を考えればよいかがだんだんとつかめるようになってきていたように見えます。今後、数学を計算機の側面から眺めたり、触れたりする上での一助になることを望みます。
今回は、この授業の最終回で、離散フーリエ変換 (Discrete Fourier Transform, DFT) と高速フーリエ変換 (Fast Fourier Transform, FFT) に基づく1変数多項式の高速乗算アルゴリズムを紹介しました。
以上で春学期の講義が一通り終わりました。今回は、整数や多項式を主な対象にした代数的なアルゴリズムの構成や計算量評価を中心に行いました。この授業が、構成的な数学を知る上での一助になることを望みます。
今回は、プログラミング言語Scalaの実習で、while式とfor式による繰り返し処理を行いました。題材は、while式にはEuclid互除法、for式には台形則による数値積分を取り上げました。
次回はこの授業の最終回ですが、リストの作り方と、リストを用いた計算を行います。
今回と次回は1変数多項式の高速乗算法の紹介で、今回は、Karatsuba(カラツバ)による1変数多項式の高速乗算法を紹介しました。
次回がこの講義の最後の授業ですが、次回は離散フーリエ変換と高速フーリエ変換 (FFT) を用いた高速乗算法を紹介します。
前回の授業で、モジュラー算法の計算量を行った際、除算や中国剰余算法の計算はまだ出ていませんでした。そこで今回は、1変数多項式の除算や中国剰余算法の計算量の評価を行いました。
次回から1変数多項式の高速乗算法に関する説明に入ります。次回はカラツバ (Karatsuba) による高速乗算法の紹介を行います。
今回は、プログラミング言語Scalaの2回目で、条件分岐や関数の再帰的定義を、Euclid互除法を題材に行いました。
次回は、繰り返しの制御構造を中心に扱う予定です。
今回からこの授業の残りの期間は、プログラミング言語Scalaによるプログラミングを行います。今回は、REPL (Read-Eval-Print-Loop) を用いた数や文字列の演算、最初のいわゆる "Hello, world" プログラム、簡単な数値の演算のプログラムの作成を行いました。
次回は条件分岐と関数の再帰的定義を学びます。
今回は「モジュラー算法」と呼ばれる一連のアルゴリズムについて紹介しました。これは、多倍長整数でコストがかかる計算を、複数のより小さな整数を法とする剰余環に分けて計算し、複数の計算結果を中国剰余定理で合わせて整数上の計算結果を復元する方法です。
今回は、モジュラー算法の中から、行列積の計算を取り上げ、中国剰余算法を用いたアルゴリズムと、その計算量の見積もりを行いました。
次回は、今回の計算で出てきた、除算の計算量の見積もりと、中国剰余算法の計算量の見積もりを行います。
今回は、LaTeX と Beamer パッケージを用いたプレゼンテーションの作成に取り組みました。
題材は、前々回のレシピか前回の数学を使って書いてもらったので、内容選びには困らなかったと思いますが、TeXのコンパイル時にこれまであまり見たことがないエラーが続出し、サポートに追われました。それでも、ネタがあらかじめ揃っていたからか、授業直後にはそれなりの人数の人達がレポートを完成させていたようです(本当に完成しているかどうかは実際に評価しないとわかりませんが)。
次回からはプログラミング言語Scalaの実習に入ります。
今回は、拡張Euclid互除法の応用の一つとして、有理数の計算を剰余環に埋め込み、剰余環での計算結果から有理数の計算結果を再構成する方法を紹介しました。
次回は、中国剰余算法の応用から「行列積の法計算」を紹介します。
今回は、前回に引き続き、LaTeXの実習を行いました。今回は数式を含む文書の作成で、番号付き数式の作成、それらの式番号の引用や、参考文献リストの作成とそれらの引用も行いました。
Gitを使ったレポートの提出は、まだ手順に習熟していない学生もいるようでしたが、今日の授業中にだいぶ落ち着いてきた印象です。サポートのTAが活躍しています。
次回はLaTeXの3回目で、Beamerパッケージを用いたプレゼンテーションスライドの作成を行います。
今回は、拡張Euclid互除法の応用例として、中国剰余定理を構成的に証明し、連立線形合同式を拡張Euclid互除法を用いて解く「中国剰余算法」を紹介しました。
次回は、拡張Euclid互除法の応用例として、有理数を剰余環に埋め込んで計算し、有理数の計算結果を再構成する手法について説明します。
今回は、前回の授業で説明を残した、pull requestによるレポートの提出から始めました。
次に、LaTeXの1回目に入りました。今回は、LaTeXのtexファイルをを編集、コンパイルし、PDFの文書を作る手順を説明し、取り組んでもらいました。
次回はLaTeXの2回目で、数式を含む文書の作成を行います。
今日は、前半では拡張Euclid互除法に関する性質を紹介しました。後半では、有理数の連分数展開をEuclid互除法を用いて行う方法と、無理数の連分数近似を同様の手順で行う方法について紹介しました。
次回は、中国剰余算法について説明する予定です。
本年度から、計算機演習の授業では、Mathematicaに続いて、文書処理(組版)システムLaTeXとプログラミング言語Scalaに取り組みます。そして、LaTeXとScalaの授業では、バージョン管理システムGitを使い、GitのオンラインリポジトリサービスGitHubを使って、レポートの提出や評価を行います。演習に使うシステムも、前回までのWindowsに代えて、今回以降は全学計算機システムに入っているUbuntu (Linux) を使います。
今回は、GitとGitHubを使うための準備と練習の回ということで、以下を行いました。授業が始まる前に、GitHubにユーザ登録することを宿題としていました。テキストやレポート課題といった教材は、GitHub Classroomを使って配り、学生ごとに個別のリポジトリを作って課題に取り組んでもらいます。
次回以降の3回は、LaTeXの使い方を学びます。
今回は、拡張Euclid互除法の性質を紹介した後、応用の一つとして、剰余環における乗法の逆元(法逆元)の計算法を紹介しました。
次回は実数の連分数近似について触れます。
今回は、Mathematica編の最終回でしたが、プログラミングの応用で、タートルグラフィクスでフラクタル図形の描画を行いました。
次回はバージョン管理システムGitの使い方を学びます。この後は文書処理システムLaTeXの使い方を学びます。
今回から、主に1変数多項式に対するEuclidの互除法を中心にした説明に移りました。今回はまず、Euclidの互除法と拡張Euclid互除法を紹介しました。
次回からしばらくは、拡張Euclid互除法の応用を扱います。次回は法逆元の計算法を扱う予定です。
今回は、Mathematicaにおけるプログラミングとして、ルールベースドプログラミングと手続き型プログラミングの両方を扱いました。
次回はMathemaitca編の最終回ですが、プログラミングの応用として、フラクタル図形の描画を扱います。
今回は、1変数多項式および多倍長整数の乗算、それから1変数多項式の除算のアルゴリズムと計算量について説明しました。
次回からはEuclidの互除法に進みます。
今回は、Mathematicaを用いた微積分の計算を中心に取り上げました。
次回はMathematicaによるプログラミングの初歩に進みます。
今回は、1変数多項式の加算に関連して、多項式の変数に値を代入して評価する計算を取り上げ、そのための Horner 法を紹介しました。その後、Horner法の応用として、分数や小数の10進・2進変換の方法を説明しました。
次回は1変数多項式や多倍長整数の乗除算に進みます。
今回は、時間計算量の漸近記法について説明し、前回紹介した多倍長整数の加算の計算量の見積もりを行いました。後半では、1変数多項式の加算のアルゴリズムを示し、その計算量の見積もりを行いました。
次回は1変数多項式のHorner法の話題に進みます。
連休明けの今回は、(符号なし)多倍長整数の加算のアルゴリズムについて説明し、併せて擬似コードを用いたアルゴリズムの記法を説明しました。
次回は計算量について説明し、多倍長整数の加算の計算量を議論します。
今回は、前回に引き続き、Mathematicaの基本的な計算として、複素数の扱い、連立方程式の解法、グラフィクスのオプションなどを扱いました。
次回は線形代数を扱います。
今回は、計算機上の数値の表現として、整数表現と浮動小数点数の説明をしました。整数表現では、2の補数による負数の表現を扱いました。
次回は多倍長数の表現を扱います。
本年度も、数学類の「計算機数学I」を担当します。この授業では、主に代数的な計算とアルゴリズムを学びます。
今回は初回ということで、計算機の仕組みや計算機のメモリの構成について説明しました。次回は計算機上の数値の表現について学びます。
授業サポートページ: https://www.math.tsukuba.ac.jp/~terui/compmath1-2019
今回は、偏微分方程式の2回目ということで、拡散方程式の安定性評価から始め、波動方程式とラプラス方程式の差分法を紹介しました。
これで、数値計算の教科書を1冊、一通り内容を紹介しました。今回の授業で扱った範囲は、数値計算のほんの入口に過ぎないと思いますが、それでも、今後、各自が数値計算を行う際に必要な学びの手がかりの一つになればと思います。
今回の授業は、大学のオープンコースウェアにも掲載することになり、講義が一通り録画、編集されました。撮影、編集に当たられた皆様に感謝いたします。
この授業も残すところあと2回ですが、これから2回は偏微分方程式の数値解法を扱います。
今回は、偏微分方程式の前半で、この授業で扱う代表的な偏微分方程式(放物型、双曲型、楕円型)の例題を取り上げ、拡散方程式(放物型)の差分法のアルゴリズムを、陽解法と陰解法に分けて説明しました。
次回は、拡散方程式の陰解法の安定性評価から始め、波動方程式(双曲型)、ラプラス方程式(楕円型)の差分法を示します。
今回は、前半で、前回に引き続き、有限体上の1変数多項式の因数分解を行うBerlekampのアルゴリズムについて、効率化の手法を説明しました。後半は、もう1つのアルゴリズムであるカンターとザッセンハウス (Cantor and Zassenhaus) によるアルゴリズムの導入を行いました。
次回は、Cantor and Zassenhausアルゴリズムの前半の部分である因子次数分離分解 (Distinct Degree Factorization) について説明します。
今回は、前回に引き続き、常微分方程式の解法を扱いました。まず、前回からの内容の続きで、差分法から、オイラー法、ホイン法、ルンゲ-クッタ法のアルゴリズムを説明しました。それから、前の時間に紹介した主な例題の解法について説明しました。
次回とその次の回でこの授業が終わります。最後の2回は偏微分方程式の解法を扱います。
年明けの授業が始まりました。Berlekampによる有限体上の1変数多項式の因数分解のアルゴリズムで、今回は、前回までで求めたf-簡約多項式から、fの既約因子を具体的に求める方法について説明しました。
次回は、Berlekampアルゴリズムの効率化に関して説明した後、有限体上の1変数多項式の因数分解のアルゴリズムで、もう1つのアルゴリズムである、カンターとザッセンハウス (Cantor and Zassenhaus) によるアルゴリズムの紹介に進む予定です。
今年の講義が始まりました。今回からは、常微分方程式ということで、この授業では、差分法による常微分方程式の解法を扱います。
今回は、常微分方程式の代表例、差分法の基礎、微分方程式の差分化、それによって導いた差分方程式の解法の基礎について説明しました。
次回は、差分法に基づく代表的な解法のアルゴリズムと、差分法による各種の常微分方程式の解法を説明します。