アルゴリズム

Javaデータ構造とアルゴリズム 基礎講座

長尾和彦

技術評論社

はじめに

第1章 アルゴリズムと計算量

  • 1.1 アルゴリズムとは
    • 1.1.1 鶴亀算
    • 1.1.2 問題の認識と解決
    • 1.1.3 アルゴリズムの構造とフローチャート
    • 1.1.4 アルゴリズムの停止性
  • 1.2 アルゴリズムの性能評価と計算量
    • 1.2.1アルゴリズムの評価基準
  • 1.3 計算量の評価
    • 1.3.1 最悪の場合の実行時間
    • 1.3.2 計算量の漸近的な評価
    • 1.3.3 O記法
    • 1.3.4 計算量の和・積の公式
  • まとめ・演習問題

第2章 アルゴリズムの設計手法

  • 2.1 力ずく法
    • 2.1.1 組み合わせの作り方
  • 2.2 欲張り法
  • 2.3分割統治法
    • 2.3.1 機能的な分割の方法
    • 2.3.2 再帰的定義
  • 2.4 動的計画法
    • 2.4.1 分割統治法がうまくいかない例
  • まとめ・演習問題

第3章 配列

  • 3.1 配列
    • 3.1.1 配列の要素
    • 3.1.2 配列の長さ
    • 3.1.3 データの終端の表現
    • 3.1.4 配列へのデータの挿入
    • 3.1.5 配列のデータの削除
    • 3.1.6 配列の複製
  • 3.2 多次元配列
    • 3.2.1 多次元配列
  • まとめ・演習問題

第4章 スタックとキュー

  • 4.1 スタック
    • 4.1.1 スタックの実装
  • 4.2 キュー
    • 4.2.1 キューの実装
  • まとめ・演習問題

第5章 リスト

  • 5.1 連結リスト
    • 5.1.1 データの挿入と削除
  • 5.2 ポインタによるリストの実装
    • 5.2.1 リストセルクラス:Cell
    • 5.2.2 線形リストクラス:LinkedListCell
    • 5.2.3 イテレータ
  • 5.3 カーソルによるリストの実装
    • 5.3.1 カーソルリストクラス:ListCursor
  • 5.4 双方向リスト
    • 5.4.1 双方向リストの実装
  • まとめ・演習問題

第6章 木

  • 6.1 木とは
    • 6.1.1 木の定義
    • 6.1.2 順序木と無順序木
    • 6.1.3 順序木の探索
  • 6.2 2分木
    • 6.2.1 2分木
    • 6.2.2 完全2分木
    • 6.2.3 2分木の実装
  • 6.3 2分探索木
    • 6.3.1 2分探索木の実装
    • 6.3.2 2分探索木の計算量
  • まとめ・演習問題

第7章 グラフ

  • 7.1 グラフとは
    • 7.1.1 グラフの定義
    • 7.1.2 グラフの用語
  • 7.2 グラフの実装と探索
    • 7.2.1 ノードクラス:Node
  • 7.3 状態空間の探索
    • 7.3.1 コンストラクタ
    • 7.3.2 状態空間の定義:makeStateSpace
    • 7.3.3 幅優先探索:breadthFirst
    • 7.3.4 深さ優先探索:depthFirst
    • 7.3.5 分岐限定法:branchAndBound
    • 7.3.6 山登り法:hillClimbing
    • 7.3.7 最良優先探索法:bestFirst
    • 7.3.8 A(A∗)アルゴリズム
  • まとめ・演習問題

第8章 データの検索

  • 8.1 線形検索
    • 8.1.1 番兵による線形検索の改良
  • 8.2 2分検索
  • 8.3 ハッシュ法
    • 8.3.1 ハッシュ法とは
    • 8.3.2 チェイン法
    • 8.3.3 オープンアドレス法
  • まとめ・演習問題

第9章 ソート

  • 9.1 ソートとは
    • 9.1.1 内部ソートと外部ソート
    • 9.1.2 アニメーションによるソートの表示―――Sorting
  • 9.2 単純交換ソート(バブルソート)
  • 9.3 単純選択ソート
  • 9.4 単純挿入ソート
  • 9.5 シェルソート
  • 9.5.1 ギャップの選択
  • 9.6 クイックソート
  • 9.7 マージソート
    • 9.7.1 ソート済み配列のマージ
    • 9.7.2 マージソートのアルゴリズム
    • 9.7.3 プログラムと実行結果
  • 9.8 ヒープソート
    • 9.8.1 ヒープ
    • 9.8.2 ヒープソート
    • 9.8.3 ヒープソートの計算量
  • まとめ・演習問題

付録A Eclipseのインストール

  • A.1 Eclipseの入手
  • A.2 Eclipseの日本語化
  • A.3 Eclipseの起動

付録B Eclipseによるプログラミング入門

  • B.1 初めてのプログラミング
  • B.1.1 プロジェクトの作成
  • B.1.2 テストファースト

付録C アルゴリズム公式集

  • 等差数列・等比数列
  • 対数(log)の公式
  • 指数の公式

付録D 漸化式の解き方

  • D.1 漸化式の解き方
    • D.1.1 例:2分検索
    • D.1.2 例:階乗の計算
  • D.1.3 例:フィボナッチ数列
  • D.1.4 クイックソート
  • D.1.5 その他の漸化式1
  • D.1.6 その他の漸化式2

付録E フラクタル

  • E.1 プロジェクトの説明
  • E.2 コッホ曲線
  • E.3 樹木曲線
  • E.4 ヒルベルト曲線
  • E.5 シェルピンスキー曲線

参考文献
おわりに
索引