| 書誌種別 |
図書 |
| タイトル |
アルゴリズムデザイン |
| タイトルヨミ |
アルゴリズム デザイン |
| 人名 |
J.Kleinberg／著
É.Tardos／著
浅野 孝夫／訳
浅野 泰仁／訳
小野 孝男／訳
平田 富夫／訳
|
| 人名ヨミ |
J Kleinberg E Tardos アサノ タカオ アサノ ヤスヒト オノ タカオ ヒラタ トミオ |
| 人名ヨミ |
|
| 出版者・発行者 |
共立出版
|
| 出版者・発行者等ヨミ |
キョウリツ シュッパン |
| 出版地・発行地 |
東京 |
| 出版・発行年月 |
2008.7 |
| ページ数または枚数・巻数 |
26,802p |
| 大きさ |
27cm |
| 価格 |
￥１５０００ |
| ISBN |
978-4-320-12217-8 |
| ISBN |
4-320-12217-8 |
| 注記 |
原タイトル:Algorithm design |
| 注記 |
文献:p735〜742 |
| 分類記号 |
007.64
|
| 件名 |
アルゴリズム
|
| 内容紹介 |
様々な分野で生じる複雑な形式の問題から明快な定式化を発見する方法と、その定式化に基づいて実際の問題に対する効率的なアルゴリズムをデザインする方法をわかりやすく解説する。章末に演習問題も掲載。 |
| 著者紹介 |
コーネル大学情報学科教授。2006年ネバンリンナ賞受賞。 |
| 言語区分 |
jpn |
| タイトルコード |
1009811094967 |
| 目次 |
第1章 はじめに:いくつかの代表的問題 |
|
1.1 最初の問題:安定マッチング／1.2 五つの代表的な問題／解答付き演習問題／演習問題／ノートと発展文献 |
|
第2章 アルゴリズム解析の基礎事項 |
|
2.1 計算容易性／2.2 増加の漸近的オーダー／2.3 リストと配列による安定マッチングアルゴリズムの実装／2.4 よく現れる計算時間の復習／2.5 より複雑なデータ構造:優先順位付きキュー／解答付き演習問題／演習問題／ノートと発展文献 |
|
第3章 グラフ |
|
3.1 基本的定義と応用／3.2 グラフの連結性とグラフ走査／3.3 キューとスタックを用いたグラフ走査／3.4 二部グラフ性の判定:幅優先探索の応用／3.5 有向グラフの連結性／3.6 有向無閉路グラフとトポロジカル順序付け／解答付き演習問題／演習問題／ノートと発展文献 |
|
第4章 グリーディアルゴリズム |
|
4.1 区間スケジューリング:グリーディアルゴリズムの先進性／4.2 遅延最小化スケジューリング:交換議論／4.3 最適キャッシング:より複雑な交換議論／4.4 グラフにおける最短パス／4.5 最小全点木問題／4.6 Kruskalのアルゴリズムの実装:Union‐Findデータ構造／4.7 クラスタリング／4.8 Huffman符号とデータ圧縮／4.9 最小コスト有向木:多フェーズグリーディアルゴリズム／解答付き演習問題／演習問題／ノートと発展文献 |
|
第5章 分割統治法 |
|
5.1 最初の漸化式:マージソートアルゴリズム／5.2 さらなる漸化式／5.3 反転数の数え上げ／5.4 最近点対の発見／5.5 整数の積の計算／5.6 畳込みと高速フーリエ変換／解答付き演習問題／演習問題／ノートと発展文献 |
|
第6章 動的計画法 |
|
6.1 重み付き区間スケジューリング:再帰的手続き／6.2 動的計画法の原理:部分問題上での記憶化と反復／6.3 区分最小二乗法:多肢選択／6.4 部分集合和とナップサック:変数の追加／6.5 RNA二次構造:区間上での動的計画法／6.6 系列アライメント／6.7 分割統治法による線形の領域の系列アライメント／6.8 グラフの最短パス／6.9 最短パスと距離ベクトルプロトコル／6.10 グラフの負閉路／解答付き演習問題／演習問題／ノートと発展文献 |
|
第7章 ネットワークフロー |
|
7.1 最大フロー問題とFord‐Fulkersonアルゴリズム／7.2 ネットワークの最大フローと最小カット／7.3 良い増加パスの選択／7.4 プリフロープッシュ最大フローアルゴリズム／7.5 最初の応用:二部グラフのマッチング問題／7.6 有向グラフと無向グラフにおける素パス／7.7 最大フロー問題の拡張版／7.8 市場調査デザイン／7.9 航空スケジューリング／7.10 画像分割／7.11 プロジェクト選択／7.12 野球ペナントレースの優勝の可能性の消去／7.13 発展:辺にコストの付随するマッチング問題／解答付き演習問題／演習問題／ノートと発展文献 |
|
第8章 NPと計算困難性 |
|
8.1 多項式時間リダクション／8.2 “ガジェット”を用いたリダクション:充足可能性問題／8.3 効率的な証明とNPの定義／8.4 NP-完全問題／8.5 系列化問題／8.6 分割問題／8.7 グラフ彩色問題／8.8 数値問題／8.9 co‐NPとNPの非対称性／8.10 計算困難な問題の部分的な分類／解答付き演習問題／演習問題／ノートと発展文献 |
|
第9章 PSPACE:クラスNPを超える問題のクラス |
|
9.1 クラスPSPACE／9.2 PSPACEに属する困難な問題／9.3 限量化問題とゲームの多項式領域解法／9.4 計画問題の多項式領域解法／9.5 PSPACE-完全性の証明／解答付き演習問題／演習問題／ノートと発展文献 |
|
第10章 計算容易性の拡大 |
|
10.1 小さい点カバーの発見／10.2 木におけるNP-困難問題の解法／10.3 円弧集合の彩色／10.4 グラフの木分解／10.5 木分解の構成／解答付き演習問題／演習問題／ノートと発展文献 |
|
第11章 近似アルゴリズム |
|
11.1 グリーディアルゴリズムと最適解に対する近似解の上界:負荷均等化問題への適用／11.2 センター選択問題／11.3 集合カバー:一般的なグリーディヒューリスティック／11.4 価格付け法・点カバーへの適用／11.5 価格付け法による最大化:素パス問題／11.6 線形計画法とラウンディング:点カバーへの適用／11.7 負荷均等化問題(再考):より高度なLPの応用／11.8 究極の近似保証:ナップサック問題／解答付き演習問題／演習問題／ノートと発展文献 |
|
第12章 局所探索 |
|
12.1 最適化問題の景観図／12.2 Metropolisアルゴリズムとシミュレーテッドアニーリング／12.3 Hopfieldニューラルネットワークへの局所探索の応用／12.4 局所探索による最大カットの近似／12.5 近傍関係の選択／12.6 局所探索による分類／12.7 最善反応行動とNash均衡／解答付き演習問題／演習問題／ノートと発展文献 |
|
第13章 乱択アルゴリズム |
|
13.1 第一の応用:競合の解消／13.2 大域的最小カットの発見／13.3 ランダム変数と期待値／13.4 MAX3-SATに対する乱択近似アルゴリズム／13.5 乱択分割統治法:中央値発見とクイックソート／13.6 ハッシング:辞書の乱択実装／13.7 最近点対を求める乱択アプローチ／13.8 乱択キャッシング／13.9 Chernoff限界／13.10 負荷均等化／13.11 パケットルーティング／13.12 背景:いくつかの基本的な確率の定義／解答付き演習問題／演習問題／ノートと発展文献 |
|
第14章 永遠に動作するアルゴリズム |
