IT Text 離散数学（改訂2版）

詳細目次

第1章　集合・写像・関係
1.1 集合
　1. 集合の記法
　2. 集合の演算
　3. 直積集合・べき集合
　演習問題
1.2 写像
　1. 全射・単射
　2. 逆写像・合成写像
　3. 集合の濃度
　演習問題
1.3 関係
　1. 同値関係
　2. 順序関係
　演習問題

第2章　論理と証明
2.1 命題論理
　1. 命　題
　2. 論理記号
　3. 真理値表
　4. 論理式の性質
　5. 標準形
　演習問題
2.2 述語論理
　1. 述　語
　2. 限量子
　3. 多変数の述語
　演習問題
2.3 推論と証明
　1. 推論規則
　2. 公理と定理
　3. 背理法
　4. 数学的帰納法
　5. 場合分けによる証明
　演習問題

第3章　数え上げ
3.1 組合せ
　1. 写像の個数、置換と階乗
　2. 2項係数
　演習問題
3.2 数え上げと部分集合
　1. 鳩の巣原理
　2. 包除原理
　演習問題
3.3 数列と漸化式、母関数
　1. 数列と母関数
　2. 母関数の応用
　演習問題
3.4 数え上げの応用
　1. ダブルカウンティング
　2. ブロックデザイン
　演習問題

第4章　グラフと木
4.1 グラフの定義
　1. グラフ理論の用語
　2. 特殊なグラフ
　3. 連結性
　4. グラフの隣接行列と接続行列
　演習問題
4.2 木
　1. 木の定義
　2. 深さ優先探索木と幅優先探索木
　演習問題
4.3 閉路
　1. オイラー小道
　2. ハミルトン閉路
　演習問題
4.4 グラフの彩色問題
　1. 頂点彩色とブルックスの定理
　2. 辺彩色とビヅィングの定理
　演習問題
4.5 平面グラフ
　1. 平面グラフと多面体
　2. オイラーの公式
　3. 四色問題
　演習問題
4.6 マッチング
　1. 完全マッチング
　2. 結婚定理
　3. 完全マッチング分解
　演習問題
4.7 グラフの連結度
　1. 連結度の定義
　2. メンガーの定理
　演習問題

第5章　オートマトン
5.1 有限オートマトン
　1. 状態と遷移関数
　2. 言語とオートマトン
　演習問題
5.2 非決定性
　1. 非決定性有限オートマトン
　2. 等価性
　演習問題
5.3 正規表現
　1. 言語の演算
　2. 非正規言語
　演習問題
5.4 文脈自由文法
　1. 書換え規則
　2. 構文解析
　3. プッシュダウンオートマトン
　演習問題

第6章　アルゴリズムと計算量
6.1 計算可能性の理論
　1. 計算とは何か|チャーチ・チューリングの提唱
　2. 計算できない問題|決定不可能性
　演習問題
6.2 計算の複雑さの理論
　1. 計算の効率を測る|計算量の概念
　2. 効率的な解法がある問題|クラスP
　3. 最大フロー問題
　4. 効率的に解くことが難しい問題|NP 困難性
　演習問題

第7章　数論
7.1 整数の性質
　1. 素数、素因数分解
　2. 最大公約数、最小公倍数
　演習問題
7.2 合同式
　1. 合同の定義
　2. 加減乗除について
　3. 逆　数
　4. 合同方程式
　演習問題
7.3 応用
　1. 秘密鍵暗号
　2. 公開鍵暗号
　演習問題
7.4 群、環、体
　1. 演算と代数系
　2. 群
　3. 環と体
　演習問題

演習問題略解
参考文献