所蔵

所蔵件数は 1 件です。現在の予約件数は 0 件です。

所蔵場所	請求記号	資料コード	資料区分	帯出区分	状態
閲覧室	/007.6/ｸ/	116669185	成人一般	可能

ページの先頭へ

資料詳細

タイトル	アルゴリズムデザイン
タイトルカナ	アルゴリズム デザイン
著者	J.Kleinberg ／著, É.Tardos ／著, 浅野 孝夫 ／訳, 浅野 泰仁 ／訳, 小野 孝男 ／訳, 平田 富夫 ／訳
著者カナ	クラインバーグ ジョン,タルドシュ エーバ,アサノ タカオ,アサノ ヤスヒト,オノ タカオ,ヒラタ トミオ
出版者	共立出版
出版年	2008.7
ページ数	26,802p
大きさ	27cm
一般件名	アルゴリズム
ISBN13桁	978-4-320-12217-8
言語	jpn
分類記号	007.64
内容紹介	様々な分野で生じる複雑な形式の問題から明快な定式化を発見する方法と、その定式化に基づいて実際の問題に対する効率的なアルゴリズムをデザインする方法をわかりやすく解説する。章末に演習問題も掲載。
著者紹介	コーネル大学情報学科教授。2006年ネバンリンナ賞受賞。

ページの先頭へ

目次

第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 最短パスと距離ベクトルプロトコル

第7章 ネットワークフロー

  7.1 最大フロー問題とFord‐Fulkersonアルゴリズム

  7.2 ネットワークの最大フローと最小カット

  7.3 良い増加パスの選択

  7.4 プリフロープッシュ最大フローアルゴリズム

  7.5 最初の応用:二部グラフのマッチング問題

  7.6 有向グラフと無向グラフにおける素パス

  7.7 最大フロー問題の拡張版

  7.8 市場調査デザイン

  7.9 航空スケジューリング

第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の非対称性

第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限界

第14章 永遠に動作するアルゴリズム

ページの先頭へ