内容紹介
情報理論の基盤をなす離散数学がしっかり学べる教科書、待望の改訂！
離散数学は、ディジタル時計の数値のように「とびとび」の値をもつ量や現象を扱う数学であり、情報理論の基盤をなします。例えば、次の問いに正確に答えるには、いずれも離散数学の知識を要します。
・コンピュータを使って計算するとはどういうことか
・コンピュータの設計を見通し良く行うにはどうすべきか
・コンピュータを効率良く使うにはどうすべきか
・コンピュータネットワークにはどのような性質があるか
本書は、情報系の学部・学科の学生が確実に押さえておくべき離散数学の基礎を効率良くしっかり学べる教科書として発行された『IT Text 離散数学』の改訂版です。改訂にあたり、グラフ理論やネットワークの内容を充実させたほか、オートマトンの分野を中心として問題演習量の増加、古い記述の見直し、情報科学の理解を深めるコラムの追加など、本書の特長「丁寧でわかりやすい解説」「豊富な図表と問題演習」がさらに実感いただける内容としました。
情報科学を学ぶ学生や若手社会人におすすめの教科書です。
このような方におすすめ
・大学、高専などで情報科学や情報工学およびその関連の学問を学ぶ学生
・離散数学、情報理論の基礎を学ぶ若手社会人
目次
主要目次
第1章 集合・写像・関係
第2章 論理と証明
第3章 数え上げ
第4章 グラフと木
第5章 オートマトン
第6章 アルゴリズムと計算量
第7章 数論
詳細目次
第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. 環と体
演習問題
演習問題略解
参考文献
続きを見る