情報学のための離散数学

内容紹介

本書は情報科学を学ぶに当たって必要な離散数学の基礎部分，論理関数とその応用，グラフとネットワーク理論に絞った教科書である．精選したテーマを詳説し，類書では省略されるものにもできるだけ証明を与えた．一見難解そうだが丁寧に読めば必ず理解できるよう配慮されており，自習書としても活用できるであろう．

ダウンロード→　正誤表

目次

1. 基礎概念

   集合／写像（関数）／関係／グラフ／命題と述語／数学的帰納法／アルゴリズムとその複雑さ／文献と関連する話題

2. 論理関数とその応用

   論理関数の表現／論理回路への応用／論理式と簡単化／論理関数の双対理論／充足可能性問題／文献とその他の話題

3. 論理関数のいろいろなクラス

   単調関数／しきい関数／自己双対関数／ホーン関数／線形関数／論理関数の万能性／部分定義論理関数／文献と関連する話題

4. グラフ理論

   グラフの連結性／グラフの探索とその応用／平面的グラフ／グラフの彩色／文献と関連する話題

5. ネットワーク最適化

   代表的なネットワーク最適化問題／ネットワークフロー問題／マッチング問題／無向グラフの最小カット／文献と関連する話題

6. 組合せ論の基礎

   順列と組合せ／2項定理と多項定理／包除原理とその応用／母関数／差分方程式／文献と関連する話題

ひとやすみ

• 放浪の数学者エルドシュ
• ブール関数の誕生と歴史
• 論理関数の拡張
• グラフ理論の始まり―ケーニヒスベルクの橋
• 結婚問題あれこれ
• フィボナッチ数