組合せアルゴリズム通論

組合せアルゴリズム通論

組合せアルゴリズムとはなにか?最適化とは?計算量とは?NP理論とは?探索,ソート,列挙,分割統治,動的手法,などについて,多くの教科書に見る知識と実践至上主義を超えて,組合せ論的思考力強化を狙う1学期間用教科書。

ジャンル
発行年月日
2002/11/25
判型
A5
ページ数
208ページ
ISBN
978-4-339-02394-7
組合せアルゴリズム通論
在庫僅少
在庫が少ない商品です。品切れとなっている場合がございます。

定価

2,530(本体2,300円+税)

カートに入れる

購入案内

  • 内容紹介
  • 目次
  • レビュー
  • 著者紹介

組合せアルゴリズムとはなにか?最適化とは?計算量とは?NP理論とは?探索,ソート,列挙,分割統治,動的手法,などについて,多くの教科書に見る知識と実践至上主義を超えて,組合せ論的思考力強化を狙う1学期間用教科書。

1.離散構造とアルゴリズム
1.1 離散集合
1.2 離散構造
1.3 組合せ問題
1.4 組合せアルゴリズム
1.5 アルゴリズムの評価
 章末問題

2.アルゴリズムの計算量
2.1 アルゴリズム評価の枠組み
2.2 ソートアルゴリズムの計算量
2.3 計算量のオーダ評価
2.4 多項式オーダ
2.5 アルゴリズム改良と計算機高速化効果
 章末問題

3.再帰的分割統治法
3.1 分割統治融合法と表現
3.2 加法的な再帰アルゴリズム
3.3 乗法的な再帰アルゴリズム
3.4 バランス2分割原理
3.5 分割統治と計算量限界
 章末問題

4.グラフ理論の基礎
4.1 グラフ構造
4.2 グラフの図式表示と平面描画
4.3 パス,カット,木
4.4 双対グラフと双対論法
 章末問題

5.グラフの行列表現と回路解析
5.1 グラフの行列表現
5.2 行列積
5.3 行列式
5.4 行列式による全域木列挙
 5.4.1 対角隣接行列
 5.4.2 木多項式
5.5 回路関数の木積和公式
 章末問題

6.グリーディアルゴリズム
6.1 グリーディ戦略
6.2 最大木問題
6.3 フローネットワーク
 6.3.1 フロー保存則
 6.3.2 単一フローネットワーク
 6.3.3 フロー増大可能パス
 6.3.4 最大フロー最小カット定理
 章末問題

7.動的な分割統治融合法
7.1 分割統治融合法の効率化手法
7.2 動的な分割統治融合法
7.3 有向無サイクルグラフの最長パス問題
 7.3.1 最長パスアルゴリズム
 7.3.2 詰込みへの応用
7.4 最短パス問題
7.5 最適行列積順問題
 章末問題

8.難しい問題,やさしい問題
8.1 判定問題と非決定性アルゴリズム
8.2 問題の多項式還元
8.3 最も難しい問題
8.4 NPC問題
 章末問題

あとがき
解答
索引

amazonレビュー

梶谷 洋司(カジタニ ヨウジ)