お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今日は、本年度最後の授業でしたが、多変数多項式の因数分解における一般 Hensel 構成として「一般化された Hensel の補題」を説明しました。そして、多変数多項式の因数分解の計算例を提示しました。授業時間をちょっと超過してしまいました。すみません。
以上で今年度の授業が終わりましたが、残念ながら、当初目指した、多項式の因数分解の実装にまでは至りませんでした。しかし、計算機やアルゴリズムの基本、多項式の表現や四則演算の実装を、Scheme の処理系とともに示した一方、因数分解のアルゴリズムにかかわる数学の説明を一通り行いましたので、計算数学の理論と実践の両面に触れたことが、履修者の皆さんにとってよい収穫になってくれることを願っています。
先週は不本意ながらも休講してしまいましたが、今日は、整数上の1変数多項式の因数分解のまとめを行いました。Hensel 構成に基づく算法は、最後の「試し割り」の段階で、因子の組み合わせの個数が因子の個数の指数関数になり、理論上は多項式時間ではありませんが、実用上は、数次から数十次の多項式の因数分解には問題ないことなどを説明しました。
引き続いて、多変数多項式の因数分解における一般 Hensel 構成の紹介を行いました。私の担当はあと2月20日のみとなってしまいましたが、次の1回で、一般 Hensel 構成について、できるだけ説明を行いたいと思います。
今日は、授業開始前に所用で事務に立ち寄ったところ、思いの外時間がかかり、4〜5分程度遅れて教室に着きましたが、教室に誰もおらず、それから10分程度待っても誰も来ませんでした。
この直後、総合研究棟（B棟）の院生室を訪ねてわかったのですが、授業開始時刻に来ていた人達がおり、私が先週インフルエンザにかかっていたのを知っていたそうで、私が復帰していないものと推測し、退出していたことがわかりました。私の遅刻が原因でしたので、お詫びいたします。その後、一部の人は帰ってしまったということで、残っている履修者が1人になっていたため、今日は休講としました。
次回は、前回の続きで、Hensel 構成に基づく整係数1変数多項式の因数分解について、順を追って説明します。
今日は、前回に引き続き、1変数多項式の因数分解の話で、今回は、Hensel 構成の中心となる定理「Hensel の補題」を説明しました。その前に、導入として、中国剰余定理に基づく因数分解の発想もできるけれども、手間の面から効率的ではない点についても触れました。
その後、Hensel 構成に基づく因数分解の手順について、順を追って説明することになりますが、今日はその導入部で終わってしまったので、残りはまた次回説明したいと思います。
今日は、今年最初の授業ということで、整係数1変数多項式の因数分解の話題に入りました。ここでは Hensel 構成による因数分解を説明しますが、今日はその準備として、有限体上の拡張 Euclid 互除法におけるいくつかの性質について説明しました。
今日は、就職活動で出席率が半分でしたが、次回は Hensel 構成の説明に入りたいと思います。今の時期、M1 の人達も、就職活動が大変と思いますが、ご健闘をお祈りします。
今回は、まず、前回の続きで、行列の triangular idempotent form を用いて零空間（の基底）を計算する方法について説明しました。その後、f-reducing polynomial を用いて、与えられた多項式の既約因子をすべて分離する計算の部分について、補足説明を行いました。最後は、実際の例を用いて、Berlekamp による因数分解の計算結果を紹介しました。
有限体上の1変数多項式の因数分解については、これで一区切りとなります。次回からは、整係数の1変数多項式の因数分解に入る予定です。この授業の今年の講義はこれで終わりますが、新年も幸先のよいスタートになればと思います。
今回は、前回に引き続き、f-reducing polynomial の計算法の続きを説明しました。
この中で、ある行列の零空間 (kernel) （の基底）を計算する必要がありますが、そこで、行列の triangular idempotent form (下三角行列で、2乗すると自身に等しくなるような行列) を求めることで、零空間の計算の手がかりになります。今回はその紹介をしたところで時間がきたので、次回はそれを用いた零空間の計算から説明する予定です。
今回から3学期に入りました。
今回は、前回欠席者もいたので、「中国剰余定理」の多項式版を説明した後、f-reducing polynomial が必ず存在することを、中国剰余定理を用いて説明しました。
その後、f-reducing polynomial の計算法について説明を始めましたが、途中で時間がきたので、続きは次回行います。
今日は、有限体上の1変数多項式の因数分解への準備として、f-reducing polynomial の概念と、中国剰余定理について説明しました。
2学期の授業はこれが最後で、来月、3学期は、中国剰余定理をもとにした、f-reducing polynomial の存在性と、その計算方法から説明していく予定です。
今日から、有限体上の1変数多項式の因数分解の話題に入りました。この授業では、有限体上の1変数多項式の因数分解として、Berlekamp による算法を取り上げます。
今日はまず、導入として、環や体の術語（概念）の復習を行い、ついで、有限体上の多項式や、代数拡大による有限体の構成について、例題を挙げながら解説しました。そして、今後使う道具として、Fermat の小定理を説明しました。
次回以降は、引き続き、これから使う道具、特に中国剰余定理の説明をしながら、算法の解説に進む予定です。
ついでに、余談ですが、毎回、この授業が終わった後の教室に、次の授業を受ける学部の3年生の人達が入ってきますが、一部の人達が興味深そうに、残った板書を眺めています。そんな彼らに、今は有限体上の多項式の因数分解をやっていますなどと話したりしています。
彼らの授業は2学期で終わるそうなので、板書の見物も今月限りだと思いますが、もし、彼らの中で、このまま大学院に進み、数年後、私もこの授業を続けていて、彼らが聴きに来たりするようなことになったら、ちょっとおもしろいかも、と思いました。
今日から久々に授業再開ということで、今日から、多項式の因数分解の話題に入りました。
今日のところは、因数分解の全体的な道筋を説明し、引き続いて無平方分解の説明を行いました。無平方分解の説明は今回で一通り済んだので、次回は、有限体上の1変数多項式の因数分解の話題に進みます。
今日の授業では、1変数多項式の四則演算の実装の続きを説明しました。
まず、減算の実装に先立って、多項式の「定数倍」の実装について説明し、その後、減算の実装について説明しました。「定数倍」の実装については、実際に履修者に実装してもらうレポート課題にしました。
引き続き、乗算の実装に先立って、多項式に単項を掛ける演算を実装し、これに基づいて乗算の実装を行う説明をしました。
授業の今後の予定ですが、次週10日は休日につき休講で、その後、10月17日と24日は、田島先生が授業を担当されます。よって、私の次回の授業は、月末の10月31日になります。今日出題のレポート課題の締切は、次回の私の授業の10月31日になりますので、各自取り組んでもらいたいと思います。
前の授業日が木曜日で月曜の授業、それから金、土、日と3連休して月曜日になりましたので、月曜の授業が2日続くことになります。
今日から1変数多項式の四則演算の実装ということで、今日は加法について説明しました。
昨年度は、この段階で初めて多項式演算の算法について説明したので、説明のステップが多くなって大変でしたが、今年度は、すでに1学期のうちに、多項式演算も含めたアルゴリズムの概要を説明しました。今回からの説明では、Scheme でよく用いられる末尾再帰を用いて、より Scheme の実装に近い形で、多項式の四則演算の説明を行うことにしました。
今日のところは、何とか加法の説明を終えました。次回以降、減法、乗法、除法について順次説明したいと思います。
今日は木曜日ですが、月曜の振替授業日です。今日は、計算機による（より具体的には、Scheme のようなリストを扱う言語処理系でよく行われる）多項式の表現について説明しました。
次回は、これをふまえて、1変数多項式の四則演算の実装について説明します。
今日から、2学期の授業が始まりました。
今日の授業では、前回に引き続き、 Scheme での「逐次」「選択」「反復」のアルゴリズムの記述法について説明しました。「逐次」は begin 形式、「選択」は if 文と cond 文、反復は再帰的定義です。
特に、再帰的定義では「末尾再帰」を取り上げ、末尾再帰が一般のループの形に直せることや、スタックの消費が少なく、効率的である点を説明しました。
Scheme の一般的な解説はこれで終わり、次回は、計算機上（特に Scheme 上）での多項式の表現について説明します。
今日の授業では、プログラミング言語 Scheme の紹介に入りました。
今日は、atom と pair、Scheme (LISP) の基本関数、関数の実行と定義の方法を紹介しました。1学期の授業は今日で終わりなので、残りの部分は、2学期の最初に説明したいと思います。
今日は、前回に引き続き、計算機のしくみの話からで、メモリの配置とワードの説明をした後、計算機上の数の表現ということで、多倍長整数の表現として、リスト表現を含む表現について説明しました。その後、一般の情報のリスト表現へ話をつなぎました。
次回からはプログラミング言語 LISP（実際は Scheme）の説明に入る予定です。Scheme の話は2〜3回続く予定ですが、1学期の授業は次回で終わるので、残りの部分は2学期に引き続き行います。
今日は、前回レポート課題としていた、1変数多項式の乗算と除算の計算量について、レポートを回収してから答え合わせをしました。あいまいだった部分についても議論しながら細かく確認できたので、学生さん達のためにもなればと思います。
講義の方は、計算機のしくみに関する説明に入りました。今日は「計算機の5大装置」と「ビット」の単位の話をしました。これから3〜4回かけて、計算機上で整数や有理数を扱うためのデータ構造や、リスト表現に関する話につなげていきたいと思います。
今日はまず、先週出題したレポート課題「擬除算のアルゴリズム」について、レポートを回収してから答え合わせを行いました。指名した学生さんは、内容をよく理解して正しいアルゴリズムを書いていましたが、商を求めてから最後にあらためて剰余を求めていたので、商を求める過程で剰余も計算されていることを指摘しました。こういう考察は、やはり、実際にやってみて気づくこともあるので、実際的な観点から問題を考える力を養うよい機会になると思います。
そして、今日の話題は「計算量」でした。計算量の主な記法について説明し、今度は、前回の授業内容に基づいて、多項式の四則演算の計算量を考察しました。しかしながら、乗算と擬除算については今回も時間が足りなかったので、これもまたレポート課題になりました。
さて、次回の授業ですが、来週から3回（5月23日、30日、6月6日）、兼担している田島慎一先生に授業をしていただきますので、次回の私の授業は6月13日になります。レポートの締切も、6月13日の授業時としましたので、頑張って取り組んでほしいと思います。
連休明けの今回は「アルゴリズム」について説明しました。
この話は昨年の授業から入れたのですが、昨年は、Euclidの互除法のところでアルゴリズムの説明を入れました。しかし、1学期末のレポート課題に「擬除算のアルゴリズムを書く」課題を出したところ、苦戦している人が一部に見られました。
そこで、今年は、多項式の四則演算の直後にアルゴリズムの説明を行い、まず、多項式の四則演算のアルゴリズムを書き下し、ついで、アルゴリズムの流れを見ながら多項式演算の計算量について学ぶ、という流れにしました。
さて、多項式演算のアルゴリズムの説明は、加、減、乗・・・までいったところで時間になったので、擬除算のアルゴリズムについては、レポート課題としました。1学期は、授業内容から、学期末にまとめてレポートを課せるかちょっと微妙なので、重要なトピックのたびにレポートを課し、履修者の理解を促したいと思います。締切は来週、次回のこの授業です。