アルゴリズムとデータ構造

基礎のツールボックス

原書名	Algorithms and Data Structures-The Basic Toolbox
著者名	浅野　哲夫 訳
発行元	丸善出版
発行年月日	2012年01月
判型	B5変
ページ数	366ページ
ISBN	978-4-621-06187-9
Cコード	3055
ジャンル	電気・電子・情報工学 >  情報・コンピュータ 電気・電子・情報工学 >  情報・コンピュータ >  アルゴリズム/データ構造

• この商品に関するお問い合わせ・感想

内容紹介

コンピュータを応用して何か自明でないことができるときにはいつもその中心にアルゴリズムが存在する。本書は効率の良いアルゴリズムを開発するための道具箱を提供することを目的として著された解説書である。本書では、まず最初に実世界で生じる問題について論じることから始め、何が問題なのかを本当に理解できるように言葉だけで解説した後、必要最低限の数学的表現を用いた簡単な解について詳しく説明している。さらに、理論的な解析だけでなく、C、C++、Javaなどの言語で実装する際のライブラリの有効利用や実装面での工夫など、実用的に役立つ記述も豊富である。著者のＫ. メールホルンは現在ドイツのザールランド大学教授であり、マックス・プランク情報科学研究所所長。アルゴリズムライブラリLEDAの創始者の一人である。

目次

第１章　食前酒――整数計算
　１．１　和
　１．２　乗算――学校式の計算法
　１．３　結果の検証
　１．４　学校式の計算法の再帰版
　１．５　カラツバ乗算法
　１．６　アルゴリズム工学
　１．７　プログラム
　１．８　補題１．５と定理１．７の証明
　１．９　実装に関する注意
　１．10　歴史に関するノートとその後の発展　
第２章　序論
　２．１　漸近記法
　２．２　マシンモデル
　２．３　疑似プログラム
　２．４　正しいアルゴリズムとプログラムの設計
　２．５　例――２分探索
　２．６　アルゴリズム解析の基礎
　２．７　平均時の解析
　２．８　乱択アルゴリズム
　２．９　グラフ
　２．10　ＰとＮＰ
　２．11　実装に関する注意
　２．12　歴史に関するノートとその後の発展
第３章　配列と連結リストによる列の表現
　３．１　連結リスト
　３．２　サイズ制限のない配列
　３．３　ならし解析
　３．４　スタックとキュー
　３．５　リスト対配列
　３．６　実装に関する注意
　３．７　歴史に関するノートとその後の発展
第４章　ハッシュ表と連想配列
　４．１　チェイニングを用いたハッシュ法
　４．２　万能ハッシュ法
　４．３　線形探査を用いたハッシュ法
　４．４　チェイニング法対線形探査法
　４．５　完全ハッシュ法
　４．６　実装に関する注意
　４．７　歴史に関するノートとその後の発展
第５章　ソーティングと選択問題
　５．１　簡単なソート法
　５．２　マージソート――Ｏ（nlogn）のソーティング・アルゴリズム
　５．３　下界
　５．４　クイックノート
　５．５　選択問題
　５．６　下界を破る
　５．７　外部ソーティング
　５．８　実装に関する注意
　５．９　歴史に関するノートとその後の発展
第６章　優先順位付きキュー
　６．１　２分ヒープ
　６．２　アドレス可能な優先順位付きキュー
　６．３　外部記憶
　６．４　実装に関する注意
　６．５　歴史に関するノートとその後の発展
第７章　ソート列
　７．１　２分探索木
　７．２　（a,b）-木と２色木
　７．３　その他の操作
　７．４　更新操作のならし解析
　７．５　探索木の補強
　７．６　実装に関する注意
　７．７　歴史に関するノートとその後の発展
第８章　グラフの表現
　８．１　辺の非順序列
　８．２　隣接配列――静的グラフ
　８．３　隣接リスト――動的グラフ
　８．４　隣接行列表現
　８．５　暗黙の表現
　８．６　実装に関する注意
　８．７　歴史に関するノートとその後の発展
第９章　グラフの走査
　９．１　幅優先探索
　９．２　深さ優先探索
　９．３　実装に関する注意
　９．４　歴史に関するノートとその後の発展
第10章　最短経路
　10．１　基本的な概念から汎用アルゴリズムへ
　10．２　有向非巡回グラフ
　10．３　辺コストが非負の場合（ダイクストラのアルゴリズム）
　10．４　ダイクストラ法の平均時解析
　10．５　単調な整数優先順位付きキュー
　10．６　辺コストが任意の場合（ベルマン―フォードのアルゴリズム）
　10．７　全点対間最短経路と節点ポテンシャル
　10．８　最短経路問合せ
　10．９　実装に関する注意
　10．10　歴史に関するノートとその後の発展
第11章　最小全域木
　11．１　カット条件と閉路条件
　11．２　ヤルニック―ブリムのアルゴリズム
　11．３　クラスカルのアルゴリズム
　11．４　統一―検索のデータ構造
　11．５　外部記憶
　11．６　応用
　11．７　実装に関する注意
　11．８　歴史に関するノートとその後の発展
第12章　最適化のための汎用的な手法
　12．１　線形計画法――ブラックボックスの問題ソルバー
　12．２　貪欲法――決して後を振り向かない
　12．３　動的計画法――徐々に組み立てていく方式
　12．４　組織的な探索――疑わしいときは腕力を使うこと
　12．５　局所探索――思考は大局的に，行動は局所的に
　12．６　進化アルゴリズム
　12．７　実装に関する注意
　12．８　歴史に関するノートとその後の発展
付録
　Ａ．１　数学記号
　Ａ．２　数学的概念
　Ａ．３　基本的な確率論
　Ａ．４　役に立つ公式

出版社からのメッセージ

本書は2009年６月にシュプリンガー・ジャパン株式会社より出版された同名書籍を再出版したものです。