数式処理システム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2014年8月18日 (月) 23:28時点における133.86.108.32 (トーク)による版 (書籍)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

数式処理システム(すうしきしょりシステム、テンプレート:Lang-en-shortCAS,Formula Manipulation System,広義にはSymbolic Computation System)は、コンピュータを用いて数式を記号的に処理するソフトウェアである。通常のコンピュータによる計算では数値情報の処理では,厳密な計算が困難であったりできない場合あるいは応用する上で十分であれば誤差を許した値を求める近似計算であるのに対して、数式処理システムでは主としてより抽象度が高い記号列を取り扱い,可能な範囲で代数的な規則に基づいた記号処理を行う。最近の数式処理システムでは、数値として近似値を含めて扱うことができるものも多くなり、(数値・数式の)統合計算システムと呼ぶのに相応しいものも存在する。

また,数式処理システムに向けた計算アルゴリズムを研究する分野も数式処理(あるいは computer algebra の直訳として計算機代数)と呼ぶ。

処理できる数式

数式処理システムは、一般に次のような数式を表現、保持や演算処理できる。

記号的操作

記号的操作には、次のようなものがある。

  • 任意の精度の数値の操作。
  • 数式内の函数や数値を記号的に置換する。
  • 数式の形式を変更する。三角関数を指数函数で置換するなど。
  • 微分偏微分の操作。
  • 式を可能な限り単純な形式に変換したり、何らかの標準形式にする。前提条件や制約条件を考慮した自動的な簡約化も行う。※ 但し、この操作は常に可能とは限らず、ある程度一般的な(例えば初等函数と絶対値函数を含む)二つの数式の等価性の判定はアルゴリズム的には決定不能なことが示されている。
  • 記号的な制約条件に基づいて最適値を与えるための必要条件を数式として導くこと。
  • 単変数あるいは多変数の多項式の因数分解
  • 一部の不定積分定積分。多次元積分も含む。
  • 数列や函数の極限を求める。※ 常に可能なわけではない。
  • 一部の微分方程式差分方程式を解く。
  • 単変数の低次あるいは高次の代数方程式を厳密にあるいは近似的に解く。消去法により多変数の線形あるいは非線形の連立代数方程式を解く。
  • 各種領域での線型および非線型の方程式を解く。
  • 函数の級数への展開、級数の総和や積計算など。※ 
  • 行列に対する各種操作。行列積の計算、逆行列の計算、固有多項式の計算、各種標準形への変換など。
  • 限量記号消去法(Quantifier Elimination Method)。

その他の機能

上記以外にも、以下のような機能を持つ数式処理システムがある。

  • 数値を近似値として高精度に計算する。例えば、21/3 を1万桁以上計算するなど。
  • 計算物理学のための物理学パッケージのように、応用数学的な応用分野に特化したアドオンが提供されているもの。
  • 関数を2次元または3次元の図にプロットしたり、アニメーション表示する(画像ファイルとして出力する)。関数値を波形とみなして音を鳴らす。
  • データベースや表計算システム、プログラミング言語から利用するためのAPI
  • 文字列探索などの文字列操作機能。
  • 数式をTeXに類似した組版システムを使って綺麗に表示する。あるいはTeX形式でテキストファイルとして(入)出力する。
  • 数式などを、Fortranなどの他の言語で用いられている表記法で(入)出力する。
  • 統計学的な計算の機能
  • 定理の自動証明や証明検証(Proof Checker)
  • 画像処理機能
  • 音響合成
  • 有限群論機能
  • システムに対するプログラミングやユーザーからの入力指示とそれに対する出力結果を保存して、再利用や再度の実行を可能とするユーザーインタフェース。

多くの場合、プログラミング言語が含まれ、ユーザー自身の作ったアルゴリズムをプログラミングして組み込むことができる。言語の系統は様々で、命令型プログラミング関数型プログラミングもあれば、制約プログラミング論理プログラミングもあるし、4GL的なものもある。

歴史

名称の由来からも分かるように、人類史上初の高級言語処理系FORTRAN(FORmula TRANslator)のコンパイラの開発は、プログラム中に記述された数式の列を処理して(必要なら等価な変形や最適化を施して)機械語の列に変形するという意味では数式処理システムの先駆であった。

初期のシステムとして、ノーベル物理学賞受賞のマルティヌス・フェルトマンが理論素粒子物理学計算のために1963年にCDC計算機のアセンブラで開発したSchoonschip、 同じく理論素粒子物理学計算のためにAnthony.C.Hearnが1963年にLISP上で開発したREDUCE、天文学計算に特化したケンブリッジ大学のCAMAL、 そのほかFORTRANで記述されたFORMACとPL/Iで記述されたPL/I FORMAC、などのいろいろな試みがあった。(REDUCEは今でも商用版あるいは無料版が存在する。今日でもまだ例えば長大な多項式や有理式を主とする計算では価値がある。)

1960年代には記号処理の側面から人工知能の研究の一環として主にLISPベースでいくつかの数式処理システムが作られた。 その最も典型的な例は、MITのProject-MACの成果であるMACSYMA である。(後にMACSYMAを元にして Common Lisp 上に移植して作られたMaximaは、GPLライセンスのフリーソフトウェアとして開発改良が現在でも続けられている)。

当初の数式処理研究の方向性は、人間の手計算で普通に行われていた(中学・高校・大学生レベルの)教科書に出てくるような数式の初等的な取り扱い方法を、(主にLISPシステムなどの記号処理系の上で)実装し実現することであった。 それにより、人間が手計算で行うのに比べて非常に高速にしかも長大な式計算が可能となり(アルゴリズムやプログラムのバグがなければ)計算結果にミスがない利点があった。 しかし、次第に試行錯誤による方法の限界、計算量の理論からの観点、より高度な数学を利用する処理の実現に向かうにつれて、普通の人間が行う(初等的で自明な)計算法や公式集に出ている規則のパターンマッチによる適用だけではなくて、 むしろより系統的な(高度な)数学アルゴリズムの開発と実装に研究の中心が推移し、それまでの単なる記号処理や人工知能の技法の応用分野では無くなって今日に至っている。 電子計算機が安価にかつ強力になりまた個人での所有と利用もできて高度でインタラクティブなプログラム開発環境が普遍的となったことなどにより、次第に通常の数学研究者も参入を始めたことで、高度な数学を駆使したアルゴリズムが数式処理に取り入れられる傾向はより加速されたといえるであろう。

現在、実務であるいは教育で最もよく使われている商業版システムはMathematicaMapleであろう。

日本で開発された国産の数式処理システムとしては、理研の佐々木建昭らによるLisp ベースの GAL、元富士通研究所で開発された(現在は神戸大学などが中心となっている) Risa/Asir、シンプレックス社の開発した数学表記のままで処理が行えるカルキング、 などがある。

1987年、ヒューレット・パッカードは世界初の数式処理機能を持った電卓 HP-28シリーズをリリースした。代数的な数式を入力でき、方程式を解いたり、微積分が可能であった。

1995年、テキサス・インスツルメンツは数式処理システム Derive を搭載した電卓 TI-92 をリリースした。その後も TI-89 などの後継機種をリリースしている。

数式処理システムが扱う数学的操作の例

関連項目

参考文献

書籍

洋書(年代順に列挙)

  • Richard J. Fateman: "Essays in algebraic simplification". Technical report MIT-LCS-TR-095, 1972. オンライン版 - その後の数式処理研究の方向性を示した歴史的に重要な文書.
  • Edited by B. Buchberger, G.E.Collins, and R. Loos in cooperaion with R. Albrecht: "Computer Algebra: Symbolic and Algebraic Computation",(2nd Edition),Springer-Verlag, ISBN 0-387-81776-X, (1983).
  • J.H.Davenport, Y. Siret and E. Tournier:"Computer algebra: systems and algorithms for algebraic computation",ISBN 0-12-204230-1, (1988).
  • R. E. Zippel(Ed.): "Computer Algebra and Parallelism", (Proceedings of CAP '90, Second International Workshop, Ithaca, USA, May, 1990) ,LNCS 584, Springer-Verlag, ISBN 0-387-55328-2, (1991).
  • Evelyne Tournier(Ed): "Computer Algebra and Differential Equations",Cambridge University Press, London Mathematical Society Lecture Note Series,ISBN 9780521447577,(1994/03).
  • Tan Kiat Shi and Willi-Hans Steeb:"SymbolicC++: An Introduction to Computer Algebra Using Object-Oriented Programming",Springer-Verlag, ISBN:981-3083-55-7, (1998).
  • Edited by Michael J. Wester: "Computer algebra systems: a practical guide",John Wiley & Sons, ISBN 0-471-98353-5, (1999).
  • Tan Kiat Shi, Willi-Hans Steeb and Yorick Hardy: "SymbolicC++: an introduction to computer algebra using object-oriented programming",(2nd extended and reviced edition), Springer-Verlag, London, ISBN 1-85233-260-3, (2000).
  • A. Schinzel:"Polynomials with Special Regard to Reducibility",Cambridge Univ. Press, Encyclopedia of Mathematics and its Applications,ISBN 9780521662253,(2000/04).
  • David Eisenbud, Daniel R. Grayson, Mike Stillman, Bernd Sturmfels(Eds):"Computations in Algebraic Geometry with Macaulay 2",(Algorithms and Computation in Mathematics) ,Springer-Verlag, ISBN 978-3540422303,(2001/10/25).
  • Joel S. Cohen: "Computer algebra and symbolic computation : elementary algorithms", A. K. Peters, Ltd., Canada, ISBN 1-56881-158-6, (2002).
  • Joel S. Cohen: "Computer algebra and symbolic computation : mathematical methods", A. K. Peters, Ltd., Canada, ISBN 1-56881-159-4, (2003).
  • Hal Schenck:"Computational Algebraic Geometry", (London Mathematical Society Student Texts) , Cambridge University Press, ISBN 978-0521536509, (2003/10/06).
  • Gert-Martin Greuel, Gerhard Pfister: "A Singular Introduction to Commutative Algebra", 2nd Ed., Springer-Verlag, ISBN 978-3540735410, (2007/12/04).
  • Yorick Hardy, Kiat Shi Tan and Willi-Hans Steeb: "Computer algebra with SymbolicC++", World Scientific, ISBN 978-981-283-360-0, (2008).
  • Joachim von zur Gathen,"Modern Computer Algebra", (3rd Ed.),Cambridge Univ. Press, ISBN 978-1107039032, (2013/04/25).
  • Wolfram Decker, Gerhard Pfister:"A First Course in Computational Algebraic Geometry", Cambridge University Press (AIMS Library of Mathematical Sciences), ISBN 978-1107612532, (2013/02/07).

和書(年代順に列挙)

  • 渡辺 隼郎:「常微分方程式の数式処理」,シリーズ新しい応用の数学4,教育出版 ,ISBN 978-4316375502,(1974年5月).
  • 佐々木建昭:「数式処理」,情報処理叢書7,情報処理学会,(1981年5月).
  • 伊理正夫, 一松信, 山本純恭, 内野正弘, 佐々木 建昭, 長尾 真, 田丸 啓吉:「数と式と文の処理」,岩波講座情報科学23,岩波書店,(1981年12月10日).
  • 後藤英一:「記号処理の基礎と応用」(情報処理叢書〈8〉),情報処理学会, (1982年1月).
  • 後藤英一一松信広田良吾(編):「計算機による数式処理のすすめ」,共立出版bit別冊,(1986年3月号).
  • 「大特集:数式処理」,情報処理,Vol.27,No.4, (1986年4月号),情報処理学会(1986年4月15日発行).
  • 佐々木 建昭, 渡辺 隼郎, 元吉 文男:「数式処理システム」,ソフトウェア講座36,昭晃堂,ISBN 978-4785635367,(1986年8月).
  • 古川 昭夫:「muMATH入門―マイコン用数式処理システム」,現代数学社,ISBN 978-4768701386, (1986年12月).
  • A. C. ハーン:「REDUCEユーザーズ マニュアル」,マグロウヒル,(1988年8月30日).
  • 広田良吾, 伊藤 雅明:「REDUCE入門―パソコンによる数式処理活用法」,サイエンス社,ISBN 978-4781905464,(1989年6月).
  • 大河内 茂美:「数式処理ソフトREDUCEで数学を」,森北出版,ISBN 978-4627832602,(1990年1月).
  • 落合 豊行, 永友 清和:REDUCEによる線形代数 (コンピュータと数学) ,近代科学社(インプレス),ISBN 978-4844372936, (1990年1月20日).
  • 牧野潔夫:「整数論の数式処理」,サイエンティスト社,(1991年1月20日).
  • 下地 貞夫:「数式処理」,森北出版,(基礎情報工学シリーズ),ISBN 978-4627806306,(1991年9月).
  • マーコ・ペトコブセク,ハーバート S. ウィルフ,ドロン ザイルバーガー:「A=B 等式証明とコンピュータ」, トッパン,ISBN 4-8101-8972-4,(1997年9月29日).
  • 斎藤 友克,平野 照比古, 竹島 卓: 「日本で生まれた数式処理ソフト ― リサアジールガイドブック」, SEG出版,ISBN 978-4872430769,(1998年10月).
  • 臼田昭司,東野勝治,葭谷安正:「最適OSで使いこなす 数式処理/数値計算」,ISBN 4-274-07866-3, オーム社,(1998年11月26日).
  • 河野 実彦:「微分方程式と数式処理」 (数学選書),森北出版,ISBN 978-4627038110,(1998年11月).
  • 藤重 悟, 佐々木 建昭, 今井 浩, 浅野 孝夫, 杉原 厚吉:「計算代数と計算幾何」,岩波講座 応用数学10,岩波書店,ISBN 978-4000108003,(1998年11月20日).
  • 赤間世紀:「はじめてのMuPAD MuPAD Pro2.0 for Windows」,シュプリンガー・フェアラーク東京,ISBN 978-4431709466,(2000年12月14日).
  • 赤間世紀, 山口喜博:「MuPADで学ぶ基礎数学」,丸善,ISBN 978-4621074657,(2004年9月).
  • 生越 茂樹:「基礎からのMuPAD―安価で人気の「数式処理システム」を使いこなす!」,工学社(I・Oブックス),ISBN 978-4777510849,(2004年12月).
  • J.フォン ツァ ガテン:「コンピュータ代数ハンドブック」,朝倉書店 ,ISBN 978-4254111064,(2006年6月).# 原書 "Modern Computer Algebra" の(旧版の)邦訳.
  • 横田 博史:「はじめてのMaxima」,工学社,ISBN 978-4777512010,(2006年9月).
  • 竹内薫:「はじめての数式処理ソフト―Maximaで楽しむ数式計算と物理グラフィック」,講談社(ブルーバックス) ,ISBN 978-4062575607, (2007年7月20日).
  • David Joyner:「群論の味わい - 置換群で解き明かすルービックキューブと15パズル」,共立出版,ISBN 978-4320019416,(2010年12月10日).
  • 穴井 宏和, 横山 和弘:「QEの計算アルゴリズムとその応用―数式処理による最適化」,東京大学出版会,ISBN 978-4130614061,(2011年8月25日).
  • 数学セミナー 2012年 02月号,特集「グレブナ-基底の新天地」,日本評論社,(2012年1月12日).
  • 穴井 宏和:「数理最適化の実践ガイド」,講談社,(2013年2月20日).
  • 阿部 寛:「古典的数式処理プログラムMACSYMAとその今日への継承」、柏艪舎、ISBN 978-4434189807(2014年3月).

グレブナ基底関連の参考書

  • David A. Cox, John B. Little, Donal O'Shea:"Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra",2nd version,Springer-Verlag,ISBN 978-0387946801,(Nov.,1996).
  • David A. Cox, John Little, Donal O'Shea:"Using Algebraic Geometry",2nd ed.,Springer-Verlag,ISBN 978-0387207063,(March,9th,2005).
  • 丸山 正樹:「グレブナー基底とその応用」,共立出版 (共立叢書・現代数学の潮流),ISBN 978-4320016934, (2002年10月).
  • 日比 孝之:「グレブナー基底」,朝倉書店(すうがくの風景) ,ISBN 978-4254115581,(2003年06月).
  • 野呂 正行, 横山 和弘:「グレブナー基底の計算基礎篇-計算代数入門」,東京大学出版会,ISBN 978-4130614047,(2003年06月17日).
  • 齋藤 友克, 竹島 卓, 平野 照比古:「グレブナー基底の計算 実践篇-Risa/Asirで解く」,東京大学出版会,ISBN 978-4130614054, (2003年06月17日).
  • 日比 孝之 (編): 「グレブナー基底の現在」,数学書房,ISBN 978-4826931052,(2006年07月).
  • JST CREST 日比チーム:「グレブナー道場」,共立出版,ISBN 978-4320019768,(2011年09月23日).
  • D.コックス:「グレブナ基底と代数多様体入門・上」,丸善出版,ISBN 978-4621062937,(2012年07月17日).
  • D.コックス:「グレブナ基底と代数多様体入門・下」,丸善出版,ISBN 978-4621063736,(2012年07月17日).
  • D.コックス,J.リトル,D.オシー:「グレブナー基底・1」,丸善出版,ISBN 978-4621064061,(2012年07月17日).
  • D.コックス,J.リトル,D.オシー:「グレブナー基底・2」,丸善出版,ISBN 978-4621064191,(2012年07月17日).

国際会議のプロシーディング

国際会議 ISSAC(International Symposium on Symbolic and Algebraic Computation)

  • (ただいま書誌情報を調査中)

国際会議 CASC(Computer Algebra in Scientific Computing)

  • Ernst W. Mayr, E. V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing CASC '99:Proceedings of the Second Workshop on Computer Algebra in Scientific Computing, Munich, May31-June4, 1999",(Workshop on Computer Algebra in Scientific Computing 1999),Springer-Verlag,ISBN 978-3540660477,(1999/07).
  • Samarkand, Ernst Mayr, E. V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing Casc 2000: Proceedings of the Third Workshop on Computer Algebra in Scientific Computing, Samarkand, October 5-9, 2000", (Workshop on Computer Algebra in Scientific Computing 2000) ,Springer-Verlag, ISBN 978-3540410409, (2000/10).
  • V. G. Ganzha, Ernst W. Mayr, E. V. Vorozhtsov (Eds):"Computer Algebra in Scientific Computing: Casc 2001, Proceedings of the Fourth International Workshop on Computer Algebra in Scientific Computing, Konstanz, Sept. 22-26, 2001", Springer-Verlag, ISBN 978-3540423553,(2001/09).
  • CASC2002(ただいま書誌情報調査中)
  • CASC2003(ただいま書誌情報調査中)
  • CASC2004(ただいま書誌情報調査中)
  • Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing, 8th International Workshop, CASC 2005, Kalamata, Greece, September 12-16, 2005, Proceedings",(Lecture Notes in Computer Science/Theoretical Computer Science and General Issues), Springer-Verlag,ISBN 978-3540289661,(2005/09/30).
  • V.G. Ganzha, E.W. Mayr, E.V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing:9th International Workshop, CASC 2006, Proceedings", (Lecture Notes in Computer Science / Theoretical Computer Science and General Issues), Springer-Verlag, ISBN 978-3540451822, (2006/10/9).
  • V.G. Ganzha, E.W. Mayr, E.V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing, 10th International Workshop, CASC 2007, Bonn, Germany in September 2007", (Lecture Notes in Computer Science / Theoretical Computer Science and General Issues), Spriner-Verlag, ISBN 978-3540751861,(2007/10/23).
  • CASC2008は開催されず.
  • Valadimir P. Gerdt, Ernst W. Mayr, Evgenii V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing:11th International Workshop, CASC 2009, Kobe, Japan, September 13-17, 2009, Proceedings", (Lecture Notes in Computer Science/Theoretical Computer Science and General Issues) , Spriner-Verlag, ISBN 978-3642041020,(2009/09/29).
  • Vladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, Evgenii V. Vorozhtsov(Eds): "Computer Algebra in Scientific Computing: 12th International Workshop, CASC 2010, Tsakhadzor, Armenia, September 6-12, 2010, Proceedings", (Lecture Notes in Computer Science / Theoretical Computer Science and General Issues),Springer-Verlag,ISBN 978-3642152733,(2010/12/1).
  • Vladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, Evgenii V. Vorozhtsov(Eds):"Computer Algebra in Scientific Computing: 13th International Workshop, CASC 2011, Kassel, Germany, September 5-9, 2011. Proceedings",(Lecture Notes in Computer Science / Theoretical Computer Science and General Issues), Springer-Verlag, ISBN 978-3642235672,(2011/10/20).
  • Vladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, Evgenii V. Vorozhtsov(Eds): "Computer Algebra in Scientific Computing: 14th International Workshop, CASC 2012, Maribor, Slovenia, September 3-6, 2012, Proceedings", (Lecture Notes in Computer Science / Theoretical Computer Science and General Issues), Springer-Verlag, (2012/07/26).
  • 今後も続く予定

国際会議 SNC(Symbolic and Numeric Computation)

  • (ただいま書誌情報を調査中)

外国の学術専門誌

計算機代数や記号計算の外国専門学術誌には:

  • Applicable Algebra in Engineering, Communication and Computing (略称:AAECC), 発行:Springer
  • The Journal of Symbolic Computation (略称:JSC), 発行:Elsevier
  • London Mathematics Society Journal of Computation and Mathematics, 発行:London Mathematics Sciety
  • Mathematics in Computer Science (略称:MCS), 発行:Birkhauser

などがあり、また上記以外の外国雑誌誌で計算機代数や記号計算の論文が良く掲載されるものには:

  • ACM Transactions on Mathematical Software (ACM TOMS), 発行:ACM
  • Computational Complexity, 発行:Springer
  • Computers and Mathematics with Applications, 発行:Elsevier
  • Experimental Mathematics ,発行:A.K.Peters
  • Fundations of Computational Mathematics, 発行:Springer
  • Mathematics of Computation , 発行:AMS
  • SIAM Journal on Computing (SICOMP), 発行:SIAM
  • Theoretical Computer Science, 発行:Elsevier

などがある。

外部リンク

テンプレート:Computer algebra systemsテンプレート:Asbox