マグロウヒル大学演習 離散数学（改訂3版） コンピュータサイエンスの基礎数学

詳細目次

序章　集合論，関係，関数およびアルゴリズムの基礎知識
0.1　集合論
0.2　関係
0.3　写像，関数，アルゴリズム

第1章　論理と命題計算
1.1　はじめに
1.2　命題および複合命題
1.3　基本的な論理演算
1.4　命題と真理表
1.5　恒真命題と矛盾命題
1.6　論理的同値
1.7　命題演算
1.8　条件付きの主張
1.9　論　法
1.10 命題関数と限定子
1.11 限定子をもつ命題の否定
演習問題
補充問題

第2章　数え上げ：順列と組合せ
2.1　はじめに
2.2　数え上げの基本原理
2.3　主要な関数
2.4　順　列
2.5　組合せ
2.6　鳩の巣原理
2.7　包除原理
2.8　樹形図
演習問題
補充問題

第3章　数え上げの発展的技法，再帰
3.1　はじめに
3.2　重複組合せ
3.3　順序付けられた，または順序を考えない分割
3.4　包除原理再論
3.5　鳩の巣原理再論
3.6　漸化式
3.7　定数係数の線形漸化式
3.8　2階斉次線形漸化式の解法
3.9　一般化されたk階の定係数斉次漸化式
演習問題
補充問題

第4章　グラフ理論
4.1　データ構造
4.2　グラフと多重グラフ
4.3　部分グラフ，同型および準同型グラフ
4.4　道，連結
4.5　周遊可能性，およびオイラーグラフ，ケーニヒスベルクの橋
4.6　ラベル付き，および重み付きグラフ
4.7　完全，正則および2部グラフ
4.8　木
4.9　平面グラフ
4.10 グラフの彩色
4.11 コンピュータの記憶領域上におけるグラフの表現
4.12 グラフ探索アルゴリズム
4.13 巡回セールスマン問題
演習問題
補充問題

第5章　有向グラフ
5.1　はじめに
5.2　有向グラフ
5.3　基本的な定義
5.4　根付き木
5.5　有向グラフの直列的表現
5.6　ワーシャルのアルゴリズム，最短経路
5.7　有向グラフのリンク表現
5.8　深さ優先／幅優先探索アルゴリズム
5.9　有向サイクルフリーグラフ，トポロジカルソート
5.10 最短経路のための枝刈りアルゴリズム
演習問題
補充問題

第6章　2分木
6.1　はじめに
6.2　2分木
6.3　完全2分木，拡張2分木
6.4　記憶領域上の2分木の表現
6.5　2分木の走査
6.6　2分探索木
6.7　優先キュー，ヒープ
6.8　重み付き経路長，ハフマンのアルゴリズム
6.9　一般木
演習問題
補充問題

第7章　整数の性質
7.1　はじめに
7.2　順序，絶対値
7.3　数学的帰納法
7.4　除法の計算
7.5　整除性と素数
7.6　最大公約数とユークリッドの互除法
7.7　算術の基本定理
7.8　合同関係
7.9　合同方程式
演習問題
補充問題

第8章　言語，オートマトン，文法
8.1　はじめに
8.2　アルファベット，単語，自由半群
8.3　言　語
8.4　正則表現と正則言語
8.5　オートマトン
8.6　文　法
演習問題
補充問題

第9章　有限状態機械とチューリングマシン
9.1　はじめに
9.2　有限状態機械
9.3　ゲーデル数
9.4　チューリングマシン
9.5　計算可能関数
演習問題
補充問題

第10章 順序集合および束
10.1　はじめに
10.2　順序集合
10.3　順序集合のハッセ図
10.4　一致数え上げ
10.5　上限と下限
10.6　順序集合の同型
10.7　整列集合
10.8　束
10.9　有界な束
10.10 分配束
10.11 補元，可補束
演習問題
補充問題

第11章 ブール代数
11.1　はじめに
11.2　基本的な定義
11.3　双対性
11.4　基本的な定理
11.5　束としてのブール代数
11.6　表現定理
11.7　集合の積和標準形
11.8　ブール代数の積和標準形
11.9　ブール代数の最小積和標準形，主項
11.10 論理ゲートおよび論理回路
11.11 真理表，ブール関数
11.12 カルノー図
演習問題
補充問題

付録　代数系と暗号
A.1　演算と代数系
A.2　有限な代数系の例と演算表
A.3　単位元，逆元
A.4　半群，モノイド，群
A.5　部分群，正規部分群，および群の位数，群の同型
A.6　環と体
A.7　体K上の多項式環
A.8　ベクトル空間と行列
A.9　暗号方式の例