出版書誌データベース

情報科学の隠れた名著が翻訳刊行に

原著は米国ポートランド大学を中心に幅広く教科書として採用され、3rd Editionを重ねるまでになっています。本書は全3分冊でコンピュータ数学の基礎分野を網羅する新しい独習シリーズの第1冊目となり、その最も基本となる離散構造（整数論など）に関する「基本的な概念と記法、関数、構成技法、同値/順序/帰納的証明、解析技法」などに関して、精密な解説と豊富な例題で学べるようになっています。Binary Hacsk / Write Great Code / The Art of Computer Programming など名著と呼ばれるコンピュータ書の読者層に特にお薦めなシリーズです。

第1章　基本概念と表記法

1.1　証明入門
　　　1.1.1　文と真理値表
　　　1.1.2　数についてひと言
　　　1.1.3　証明技法
1.2　集合
　　　1.2.1　集合の定義
　　　1.2.2　集合上の演算
　　　1.2.3　有限集合を数える
　　　1.2.4　多重集合
　　　1.2.5　集合は複雑過ぎてはいけない
1.3　順序構造
　　　1.3.1　組
　　　1.3.2　リスト
　　　1.3.3　文字列と言語
　　　1.3.4　関係
　　　1.3.5　組を数える
1.4　グラフと木
　　　1.4.1　グラフの定義
　　　1.4.2　グラフ中の経路
　　　1.4.3　グラフの走査
　　　1.4.4　木
　　　1.4.5　全域木
1.5　章のまとめ

第2章　関数について

2.1　定義と例
　　　2.1.1　関数の定義
　　　2.1.2　床関数と天井関数
　　　2.1.3　最大公約数
　　　2.1.4　剰余関数
　　　2.1.5　対数関数
2.2　関数を構成する
　　　2.2.1　関数の合成
　　　2.2.2　map関数
2.3　関数の性質
　　　2.3.1　単射と全射
　　　2.3.2　全単射と逆関数
　　　2.3.3　鳩の巣原理
　　　2.3.4　単純な暗号
　　　2.3.5　ハッシュ関数
2.4　可算可能性
　　　2.4.1　集合の大きさを比較する
　　　2.4.2　可算な集合
　　　2.4.3　対角線論法
　　　2.4.4　計算可能性の限界
2.5　章のまとめ

第3章　構成技法

3.1　帰納的に定義される集合
　　　3.1.1　数
　　　3.1.2　文字列
　　　3.1.3　リスト
　　　3.1.4　二分木
　　　3.1.5　集合のデカルト積
3.2　再帰関数と手続き
　　　3.2.1　数
　　　3.2.2　文字列
　　　3.2.3　リスト
　　　3.2.4　二分木
　　　3.2.5　更に2つの問題
　　　3.2.6　無限列
3.3　文法
　　　3.3.1　英文法の復習
　　　3.3.2　文法の構造
　　　3.3.3　導出
　　　3.3.4　文法を構成する
　　　3.3.5　意味と曖昧さ
3.4　章のまとめ

第4章　同値、順序、帰納的証明

4.1　二項関係の性質
　　　4.1.1　関係の合成
　　　4.1.2　閉包
　　　4.1.3　経路問題
4.2　同値関係
　　　4.2.1　定義と例題
　　　4.2.2　同値類
　　　4.2.3　直和分割
　　　4.2.4　同値関係を生成する
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.5　章のまとめ

第5章　解析技法

5.1　アルゴリズムを解析する
　　　5.1.1　最悪実行時間
　　　5.1.2　決定木
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.4　離散型確率
　　　5.4.1　確率の用語
　　　5.4.2　条件付き確率
　　　5.4.3　独立事象
　　　5.4.4　期待値と平均的な振舞い
　　　5.4.5　有限マルコフ連鎖
　　　5.4.6　近似（モンテカルロ法）
5.5　漸化式を解く
　　　5.5.1　単純な漸化式を解く
　　　5.5.2　分割統治漸化式
　　　5.5.3　生成関数
5.6　成長率を比較する
　　　5.6.1　ビッグ・オー
　　　5.6.2　ビッグ・オメガ
　　　5.6.3　ビッグ・シータ
　　　5.6.4　リトル・オー
　　　5.6.5　記号を使用する
5.7　章のまとめ
　　　注釈

付録
　ギリシャ文字
　記号
　参考文献


索引

訳：神林　靖