今回は、本授業科目の最後の授業でしたが、1変数多項式の高速乗算アルゴリズムの一つとして、高速フーリエ変換 (FFT) を用いた乗算法を紹介しました。2つのn次の1変数多項式の乗算にかかる計算量は、古典的なアルゴリズムで O(n^2), 前回紹介したKaratsubaのアルゴリズムでは O(n^(log 3)) ですが、今回のFFTを用いたアルゴリズムでは O(n log n) となります。
以上が本授業の内容で、この授業では、拡張Euclid互除法を軸に、主に代数的なアルゴリズムを紹介しました。この授業科目は、本学で数学の教員免許を取得するための必修科目にも位置付けられていますが、この授業が、数学の代数分野における構成的な計算を学んだり考えたりするきっかけの一つになればと思います。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
0 件のコメント:
コメントを投稿