今日は、前回の勢いも一段落し、導関数の計算や、漸近展開の計算などの問題をやりました。
レポートの方はめでたく全員提出です。
お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今日は、先週宿題にしていた、拡張Euclidの互除法の計算量について、答え合わせのような形で実際に算出しました。途中、多項式の和の計算量を合算するのを忘れていた部分があり、途中から直し直し計算を行いましたが、ミスは受講生の方に申し訳なかったと思います。
その後、多項式剰余列(PRS)計算の時に起こる係数膨張の例について、いくつかの例を挙げて説明しました。最終的には、整数のGCDを計算することなく、係数の共通因子を除くための方法として、部分終結式の理論をやります、という入口の部分まで説明しました。
次回は、終結式の導入から続けていきます。
今日は、先週配布した問題がたくさん解かれました。授業が始まって初めて、板書→解説のルーチンが2巡し、問題数が多く解けたのはよかったと思います。
先週配布の問題で、未回答で残ったのは結局3問。これらは今日の宿題になりました。来週締切のレポート課題です。
今日は、計算量のさわりを話しました。もっと前に導入してもいいのかもしれませんが、ある程度の算法(拡張Euclidの互除法)を扱ってからの方が、実感がわくかなと思い、ここで導入しました。
内容としては、時間計算量を中心に、計算量の概念、計算量の漸近表示の記法を説明し、その後、1変数多項式の加減乗除の計算量について説明しました。高速算法は今回は除外です。
拡張Euclidの互除法の計算量については、今日の宿題にしました。次回は、ここから部分終結式の話に持っていこうと思います。
先週が金曜日の授業でしたので、授業の間隔がいつもより短く、ちょっと違和感があります。
で、今日の授業は、関数の連続性の問題などを解きましたが、最初に説明してくれた人の答案の内容を勘違いして、今は必ずしも必要でない内容(主にイプシロン-デルタ論法)に授業の前半の時間を割いてしまいました。時間がなくなった分については反省です。
今日は導関数の計算に関する補充問題を出したので、来週解いてきてくれるとよいのですが。来週も頑張りましょう。
今日は、拡張Euclidの互除法について話しました。定理で、存在、cofactorの次数、一意性を示し、アルゴリズムの形で書き下して今日は終了です。
次回は、ちょっと脇道にそれますが、計算量について説明します。