情報科学演習III --- 計算代数とその応用 --- 中山 裕貴(修士2年) nak-den@is.s.u-tokyo.ac.jp
計算代数とは 多項式の因数分解 連立方程式の求解 多項式のGCDの計算 等を、高速・正確に行うことを目指す 符号理論、整数計画問題など、様々な 分野への応用
多項式の因数分解 (特に多変数の場合は)難しい 一つの方法として、 によって計算 有限体上での因数分解 (Berlekampのアルゴリズム) Hensel構成 試し割り によって計算
グレブナー基底 連立代数方程式の解を逐次的に効率よく計算 多項式f1,…,fn,gが与えられたとき、gをh1f1+・・・+hnfn(hiは多項式)の形で表せるか判定 グレブナー基底が有用
演習3で扱う内容:例 論文・テキストの購読 アルゴリズムの実装・評価 他に何かやりたいことがあれば、 それをやるのも良いでしょう Ideals, Varieties, and Algorithms 計算機代数入門(野呂) アルゴリズムの実装・評価 Risa/Asir (数式処理ソフト)など使用 他に何かやりたいことがあれば、 それをやるのも良いでしょう