20世紀のトップ10アルゴリズム

書籍情報
シリーズ名計算科学講座 全10巻 第1部 計算科学の基盤 【2】巻
ISBN978-4-320-12267-3
判型A5 
ページ数356ページ
発売日2022年01月21日
価格4,950円(税込)
20世紀のトップ10アルゴリズム 書影
20世紀のトップ10アルゴリズム

新刊

米国物理学協会とIEEE computer societyによる共同誌``Computing in Science & Engineering”は,2000年第1号で「``Top 10 Algorithms of the Century”(今世紀のトップ10アルゴリズム)」という特集を組んだ。特集は,20世紀の科学技術の発展に目覚ましい成果を挙げ,関連分野の発展にも多大な貢献をもたらした10個のアルゴリズムを取り上げ,各々について3~10ページ程度の短い分量ながらも簡潔かつ丁寧に紹介したもので,当時この特集は非常に大きな反響を呼んだ。

それから20年余りが経過した。その間にも計算機分野や計算科学分野は更なる目覚ましい発展を遂げ,新たなアルゴリズムも無数に誕生した。しかし「トップ10アルゴリズム」の重要性は聊かも揺らぐことはなく,諸分野の根幹をなす不可欠な要素として未だ使われ続けている。また,10個のアルゴリズム自身もこの20年余りで研究が進んでおり,今もなお応用範囲を大きく拡げている。

本書は,これら10個のアルゴリズムそれぞれの代表的な研究者に執筆を依頼し,その黎明から今日までの発展の歴史や理論の詳細を,将来の展望も見据えて初学者にもわかりやすくまとめた書籍である。非常に広汎な計算機科学・計算科学の発展の様相を一冊で俯瞰することができる,大変稀有な書籍といえるだろう。

目次

第1章 モンテカルロ法(小柳義夫)
1.1 モンテカルロ法とモンテカルロ・シミュレーション
1.2 モンテカルロ法による決定論的計算
1.3 メトロポリス法とその発展
1.4 確率微分方程式によるシミュレーション
1.5 乱数の変換
1.6 一様乱数の生成

第2章 線形計画法のアルゴリズムとその周辺(土谷隆)
2.1 公理としての線形計画問題
2.2 線形計画問題の歴史
2.3 線形計画問題とその例
2.4 標準形問題・双対標準形問題・双対問題
2.5 線形計画問題の解法概観
2.6 単体法
2.7 線形計画問題の最適解の性質
2.8 計算複雑度の分野の勃興と線形計画法
2.9 単体法・ネットワーク問題・整数計画問題
2.10 楕円体法
2.11 内点法
2.12 凸2次計画法・半正定値計画法・対称錐計画法
2.13 おわりに

第3章 線形方程式のためのクリロフ部分空間法(曽我部知広)
3.1 記号と定義
3.2 クリロフ部分空間法の枠組み
3.3 グラム・シュミットの直交化法
3.4 クリロフ部分空間の直交基底生成法
3.5 前処理技術
3.6 エルミート行列用のクリロフ部分空間法
3.7 非エルミート行列用のクリロフ部分空間法I
3.8 非エルミート行列用のクリロフ部分空間法II
3.9 おわりに

第4章 行列計算に対する分解アプローチ(杉原正顯)
4.1 LU分解
4.2 LU分解に基づく連立1次方程式の解法
4.3 LU分解の様々な計算法
4.4 LU分解の変種
4.5 LU分解(もしくはその変種)の更新
4.6 Gaussの消去法の後退誤差解析
4.7 終わりに ―様々な分解

第5章 Fortran最適化コンパイラ(西山博泰)
5.1 FortranI言語
5.2 FortranIコンパイラ
5.3 FortranI以降のプログラミング言語の発展
5.4 FortranI以降のコンパイラ技術の発展
5.5 まとめ

第6章 QR法(山本有作)
6.1 はじめに
6.2 QR法の原理
6.3 非対称行列向けのマルチシフトQR法
6.4 対称行列向けのマルチシフトQR法
6.5 QR法の応用
6.6 おわりに

第7章 クイックソート(平田富夫)
7.1 C.A.R.Hoare
7.2 クイックソートの特徴
7.3 クイックソートの原理
7.4 計算時間の解析
7.5 確率アルゴリズム
7.6 プログラムへの実装
7.7 使用記憶領域
7.8 マルチキークイックソート

第8章 高速フーリエ変換(大浦拓哉)
8.1 基本的なアルゴリズムの概略
8.2 複素数FFTの分類
8.3 複素数FFTの応用
8.4 複素数上以外の変換に対するFFTアルゴリズム
8.5 FFTの解説書とソフトウェア

第9章 整数関係探知(張紹良・山本有作 訳)
補遺:PSLQアルゴリズムの動作原理(山本有作)
9.1 はじめに
9.2 準備
9.3 PSLQアルゴリズム
9.4 PSLQアルゴリズムの停止性と反復回数
9.5 おわりに

第10章 高速多重極子展開法(須田礼仁)
10.1 FMMとは何か
10.2 関数近似~マジックの「種」~
10.3 近似式の一般化~マジックの応用編~
10.4 領域分割~近似式のパワーを倍増する「てこ」~
10.5 階層的領域分割~損して得取れ~
10.6 近似式の変換~親孝行な子供たち~
10.7 多重極子展開と局所展開~二刀流で計算量を斬る~
10.8 FMMのアルゴリズム~マジックの完成~
10.9 おわりに

索 引