データ構造とアルゴリズム(コンピュータサイエンス教科書シリーズ〈2〉) [全集叢書]

データ構造とアルゴリズム(コンピュータサイエンス教科書シリーズ〈2〉) の 商品概要

• 目次

  1.　はじめに
  1.1　アルゴリズムとデータ構造の重要性
  1.2　計算モデルと計算量
  　1.2.1　問題と問題例
  　1.2.2　計算機モデル
  　1.2.3　アルゴリズムのオーダー表記
  　1.2.4　指数関数と多項式関数の比較
  　1.2.5　計算量とアルゴリズムの種類
  1.3　NP完全性
  　1.3.1　PとNP
  　1.3.2　NPの定義
  　1.3.3　多項式時間帰着とNP完全
  演習問題
  
  2.　基本的データ構造
  2.1　配列
  2.2　線形データ構造
  　2.2.1　配列を使う方法
  　2.2.2　リスト
  　2.2.3　スタック
  　2.2.4　キュー（待ち行列）
  2.3　木
  　2.3.1　一般的木構造
  　2.3.2　完全二分木
  2.4　グラフ
  　2.4.1　グラフの基本
  　2.4.2　次数とカット
  　2.4.3　部分グラフと路と連結性
  　2.4.4　木と森とDAGと二部グラフと完全グラフ
  　2.4.5　グラフのデータ構造
  　2.4.6　グラフの探索－幅優先探索と深さ優先探索
  演習問題
  プログラム演習
  
  3.　整列
  3.1　整列とはなにか
  3.2　バブルソート
  　3.2.1　バブルソートのアルゴリズム
  　3.2.2　バブルソートの計算時間
  3.3　マージソート
  　3.3.1　マージソートのアルゴリズム
  　3.3.2　マージソートの計算時間
  3.4　クイックソート
  　3.4.1　クイックソートのアルゴリズム
  　3.4.2　クイックソートの計算時間
  3.5　バケットソート
  　3.5.1　バケットソートのアルゴリズム
  　3.5.2　バケットソートの計算時間
  3.6　基数ソート
  　3.6.1　基数ソートのアルゴリズム
  　3.6.2　基数ソートの計算時間
  3.7　ヒープソート
  　3.7.1　ヒープとはなにか
  　3.7.2　ヒープの構造
  　3.7.3　Insertの方法
  　3.7.4　DeleteMinの方法
  　3.7.5　Deleteの方法
  　3.7.6　ヒープソートのアルゴリズム
  　3.7.7　ヒープの線形時間作成法
  3.8　整列計算時間の下界値
  演習問題
  プログラム演習
  
  4.　集合に関する操作
  4.1　主な操作とデータ構造
  4.2　辞書
  　4.2.1　ハッシュ表
  　4.2.2　外部ハッシュ法
  　4.2.3　内部ハッシュ法
  4.3　カッコウハッシュ
  　4.3.1　カッコウハッシュとはなにか
  　4.3.2　カッコウハッシュの詳細
  　4.3.3　格納列の閉路と単純格納列
  　4.3.4　カッコウハッシュの解析*
  4.4　ユニオン・ファインド
  　4.4.1　問題設定
  　4.4.2　配列による実現
  　4.4.3　ポインタでの実現
  　4.4.4　木による実現－ほぼ線形時間のユニオン・ファインド
  　4.4.5　木構造上に限定された場合の線形時間ユニオン・ファインド
  演習問題
  プログラム演習
  
  5.　平衡二分探索木
  5.1　平衡二分探索木の基本
  　5.1.1　二分探索
  　5.1.2　二分探索木の構造とMember
  　5.1.3　最大値・最小値の発見と整列
  　5.1.4　データの挿入と削除
  　5.1.5　回転操作
  5.2　二色木
  　5.2.1　二色木の基本
  　5.2.2　二色木における挿入
  　5.2.3　二色木における削除
  　5.2.4　二色木の合併と分割
  　5.2.5　別のデータの管理
  5.3　スプレー木
  　5.3.1　オンラインアルゴリズムと動的最適性予想
  　5.3.2　スプレー木のアルゴリズム
  　5.3.3　スプレー木のO（logn）競合化*
  5.4　タンゴ木
  　5.4.1　タンゴ木の基本思想とインターリーブ限界
  　5.4.2　タンゴ木の構造
  　5.4.3　補助木のつくり替え
  　5.4.4　タンゴ木の計算時間の解析*
  演習問題
  プログラム演習
  
  6.　古典的アルゴリズム
  6.1　最小木問題
  　6.1.1　問題の定義
  　6.1.2　貪欲算法とクラスカルのアルゴリズム
  　6.1.3　クラスカルのアルゴリズムの正当性
  6.2　最短路問題
  　6.2.1　最短路問題とはなにか
  　6.2.2　最短路の存在条件
  　6.2.3　最短路木
  　6.2.4　ダイクストラ法
  　6.2.5　フロイド・ワーシャル法
  6.3　彩色問題
  　6.3.1　平面グラフとその性質
  　6.3.2　グラフ彩色問題
  　6.3.3　1,2彩色問題
  　6.3.4　染色数とその上限
  　6.3.5　四色定理*
  演習問題
  
  7.　定数時間アルゴリズム
  7.1　定数時間アルゴリズムとはなにか
  　7.1.1　定数時間アルゴリズムの一般的枠組み
  　7.1.2　性質検査
  　7.1.3　グラフの「性質」
  　7.1.4　グラフGと性質Pの距離
  　7.1.5　インスタンスの表現法
  　7.1.6　検査アルゴリズムと検査可能性
  7.2　隣接行列モデル
  　7.2.1　無三角性検査
  　7.2.2　手続きTriangleFreeの正当性の証明
  　7.2.3　一般化－無H性とモノトーン性
  7.3　次数制限モデル
  　7.3.1　次数制限モデルの基本
  　7.3.2　無三角性検査と無H性検査
  　7.3.3　無閉路性検査
  　7.3.4　マイナー閉鎖な性質と超有限性と分割定理
  　7.3.5　分割神託
  　7.3.6　無Hマイナーなグラフの検査アルゴリズム
  演習問題
  プログラム演習
  
  8.　数学用語の解説
  8.1　基本用語
  8.2　対応・関係・関数・順序
  8.3　基本公式
  8.4　グラフマイナー
  　8.4.1　クラトウスキーの定理
  　8.4.2　グラフマイナー定理
  8.5　正則性補題
  　8.5.1　正則性補題とはなにか
  　8.5.2　正則性補題の証明*
  演習問題
  
  引用・参考文献
  索引

• 内容紹介

  カッコウハッシュ，タンゴ木，定数時間アルゴリズムなど，非常に重要であるが内容が先進的であるために通常の教科書では取り上げられなかったアルゴリズムについて，初心者にでもわかるように解説したこれまでにない教科書。

• 著者紹介（「BOOK著者紹介情報」より）（本データはこの書籍が刊行された当時に掲載されていたものです）

  伊藤 大雄(イトウ ヒロオ)
  １９８５年京都大学工学部数理工学科卒業。１９８７年京都大学大学院修士課程修了（数理工学専攻）。日本電信電話株式会社基礎研究所。１９９０年日本電信電話株式会社通信網総合研究所。１９９５年博士（工学）（京都大学）。１９９６年豊橋技術科学大学講師。２００１年京都大学助教授。２００７年京都大学准教授。２０１２年電気通信大学教授

データ構造とアルゴリズム(コンピュータサイエンス教科書シリーズ〈2〉) の商品スペック