BOOK SEARCH
入門〈有限・離散の数学〉 1 離散数学入門 改訂版
内容紹介
無限ではないが,天文学的な数でしか表現できない問題を扱う数学――離散数学。その入門的話題を,世界と日本の第一人者が解説。〔内容〕組合せ幾何/可視性問題/最短ネットワーク/詰込み/スケジュール作成/コンピューターの限界/他
編集部から
目次
1. 組合せ幾何I
1.1 整数距離をもつ点集合
1.2 距離の出現回数
1.3 点集合と直線(線分)
1.4 無交差単体の存在性
2. 組合せ幾何II
2.1 点の封じ込み定理
2.2 点集合の均等分割
2.3 格子点集合の均等分割
2.4 Hellyの定理とその応用
2.5 分離問題
3. 可視性問題I
3.1 美術館問題
3.2 要塞問題
3.3 刑務所問題
4. 可視性問題II
4.1 警備問題I
4.2 警備問題II
4.3 照明問題
5. 最短ネットワーク問題
5.1 最小全域木
5.2 最小シュタイナー木
5.3 シュタイナー点の性質
5.4 Melzakのアルゴリズム
5.5 正n角形の頂点に対するシュタイナー木
5.6 最小シュタイナー木の評価
6. 詰め込み問題
6.1 円の最密詰め込み――Thueの定理
6.2 長方形への単位円の最密詰め込み
6.3 正方形の詰め込み
7. スケジュール作成問題――Job Scheduling Problem
7.1 独立なタスク群
7.1.1 アルゴリズム:LIST
7.1.2 アルゴリズム:LIST-Dec.
7.2 順序に制約のあるタスク群
7.3 スケジュール作成問題の難しさ
8. コンピューターの限界
8.1 コンピューターアルゴリズム
8.2 アルゴリズム決定不可能問題(計算不能問題)
8.3 コンピューターにとって難しい決定可能問題(実際的計算が不可能な問題)
8.4 手に負えない問題
8.5 未来への展望
9. 離散数学の3つの話題
9.1 ナンパ問題
9.2 エイズ予防問題
9.3 ゴシップ問題
10. 問題の解答
11. 索 引