アルゴリズム

Cによる探索プログラミング
基礎から遺伝的アルゴリズムまで

伊庭斉志
オーム社

まえがき
コラム● C言語のコンパイルと実行方法

第1章 C 言語の基礎の復習

  • 1.1 基本的なデータ型
  • 練習問題1.1 何を出力するか?(1)
  • 1.2 演算の優先順位
  • 練習問題1.2 何を出力するか?(2)
  • 1.3 ちょっと数学してみよう
  • 練習問題1.3 ハーディ・ラマヌジャン数
  • 練習問題1.4 ルース・アーロン・ペア
  • 練習問題1.5 PS 問題
  • 練習問題1.6 スミス数
  • 練習問題1.7 0 から9 の平方数
  • 練習問題1.8 ウェアリングの問題
  • コラム● 数学とコンピュータ

第2章 再帰とフィボナッチ数

  • 2.1 関数の再帰呼び出し
  • 練習問題2.1 6174 の不思議
  • 2.2 ユークリッド互除法と計算量
  • 練習問題2.2 最大公約多項式
  • 2.3 フィボナッチ関数
  • コラム● ピサのレオナルド
  • 練習問題2.3 フィボナッチの問題
  • コラム● 黄金比とフィナボッチ数
  • 2.4 tail recursion
  • 2.5 f(x) = 0 の根を求める
  • 練習問題2.4 Newton-Raphson 法の2 次の収束性
  • 2.6 整数の分割
  • 練習問題2.5 整数の分割
  • 2.7 再帰を用いた練習問題
  • 練習問題2.6 カエルパズル(1)
  • 練習問題2.7 カエルパズル(2)
  • 練習問題2.8 必ず1となる

第3章 ランダム関数とシミュレーション

  • 3.1 乱数とランダム関数
  • コラム● シミュレーションと複雑系
  • 3.2 乱数の発生方法
  • 3.3 円周率を計算する
  • 3.4 自然対数の底を計算する
  • 練習問題3.1 乱数で自然対数の底を作る(1)
  • 練習問題3.2 乱数で自然対数の底を作る(2)
  • 3.5 ビュフォンの針
  • 練習問題3.3 ビュフォンの針(1)
  • 練習問題3.4 ビュフォンの針(2)
  • 3.6 Hit & Blow
  • 練習問題3.5 Hit & Blow
  • 3.7 交叉、逆位と突然変異

第4章 ポインタ入門

  • 4.1 アドレスとポインタ
  • 4.2 呼び出し元の変数の値を変更する関数
  • 4.3 アドレスを対象とした演算
  • 4.4 ポインタと配列
  • 練習問題4.1 何を出力するか?(3)
  • 4.5 文字列と文字列処理関数
  • 練習問題4.2 文字列が含まれるかの判定
  • コラム● 自己複製と人工生命
  • 4.6 自分自身をコピーするプログラム
  • 4.7 バイナリ表現とグレイ表現

第5章 ポインタの配列と構造体

  • 5.1 ポインタの配列/ポインタを指すポインタ
  • 練習問題5.1 何を出力するか?(4)
  • 練習問題5.2 何を出力するか?(5)
  • 5.2 ポインタの配列によるテキストの表現
  • 5.3 コマンド行の引数
  • 5.4 構造体
  • 5.5 構造体を指すポインタ
  • 練習問題5.3 座標の変換
  • 5.6 10 を作るパズル
  • 練習問題5.4 10 を作る
  • コラム● ドナルド・クヌース

第6章 より複雑なデータ構造

  • 6.1 自己参照的構造体
  • 6.2 線形リスト
  • 練習問題6.1 何を出力するか?(6)
  • 6.3 逆ポーランド記法と簡易計算
  • 練習問題6.2 逆ポーランド記法(1)
  • 練習問題6.3 逆ポーランド記法(2)
  • 6.4 4 つの4
  • 練習問題6.4 4 つの4(30 まで)
  • 練習問題6.5 4 つの4(113 まで)
  • 6.5 小町算
  • 練習問題6.6 100 を作る

第7章 木構造の探索

  • 7.1 N クィーン問題と木構造
  • 7.2 パズルの探索
    • 7.2.1 ひとりにしてくれ
    • 7.2.2 黒マスはどこだ
    • 練習問題7.1 黒どこ
    • 7.2.3 ぬりかべ
    • 練習問題7.2 ぬりかべ
    • 7.2.4 ナンバープレイス
    • 練習問題7.3 ナンバープレイス
  • 7.3 インド式算数パズル
  • 練習問題7.4 インド式計算パズル
  • 7.4 式のインタプリタ
  • 練習問題7.5 多分木の処理
  • 練習問題7.6 Lisp のインタプリタ(1)
  • 7.5 Lisp入門
  • 練習問題7.7 Lisp のインタプリタ(2)
  • コラム● Lisp と人工知能

第8章 最適値の探索

  • 8.1 最適値探索とは何か?
  • 8.2 局所的探索
  • 8.3 焼きなまし法
  • 練習問題8.1 焼きなまし法(1)
  • 練習問題8.2 焼きなまし法(2)
  • 8.4 虫の世界
  • 練習問題8.3 虫の世界
  • コラム● ヒューリスティックス
  • 8.5 サイクロトロンパズル
  • 練習問題8.4 サイクロトロンパズル

第9章 GAを作る

  • 9.1 進化計算とGA
  • コラム● 進化論的手法
  • 9.2 GAを実装しよう
    • 9.2.1 遺伝子型と表現型
    • 9.2.2 遺伝的オペレータ
    • 9.2.3 選択方式
    • 9.2.4 適合度計算
    • 9.2.5 GAの実行
    • 9.2.6 ソースコードとその説明
    • 練習問題9.1 GAで方程式の解を求める(1)
    • 練習問題9.2 GAで方程式の解を求める(2)
  • 9.3 巡回セールスマン問題
  • 練習問題9.3 GAでNクィーン問題を解く
  • 練習問題9.4 GAの応用
  • 9.4 プログラムの進化
  • 練習問題9.5 GP を作る

おわりに
付録 演習問題のヒントと解答例

  • 解答例1.3 ハーディ・ラマヌジャン数
  • 解答例1.4 ルース・アーロン・ペア
  • 解答例1.5 PS問題
  • 解答例1.7 0 から9の平方数
  • 解答例2.2 最大公約多項式
  • 解答例2.3 フィボナッチの問題
  • 解答例2.5 整数の分割
  • 解答例2.6 カエルパズル(1)
  • 解答例2.8 必ず1となる
  • 解答例3.4 ビュフォンの針(2)
  • 解答例4.2 文字列が含まれるかの判定
  • 解答例5.3 座標の変換
  • 解答例6.2 逆ポーランド記法(1)
  • 解答例6.3 逆ポーランド記法(2)
  • 解答例6.5 4 つの4(113 まで)
  • 解答例7.5 多分木の処理
  • 解答例7.7 Lisp のインタプリタ(2)
  • 解答例8.1 焼きなまし法(1)
  • 解答例8.2 焼きなまし法(2)
  • 解答例8.3 虫の世界
  • 解答例9.2 GAで方程式の解を求める(2)
  • 解答例9.3 GAでNクィーン問題を解く
  • 解答例9.4 GAの応用
  • 解答例9.5 GPを作る

関連図書
索引