01 / 読書ガイド
読書ガイド
対象読者
本科の二科目目の離散数学や組合せ論向け、とくに計算機と応用数学の学生に合う。計算の前に表現を選ぶ習慣を育て、公式を別々の処方として暗記せず説明と証明を行う。
前提知識
離散数学入門と帰納法が役立つ。集合、関数、二項係数、グラフ記法、基本代数を復習する。確率と生成関数の手法は本文で発展させられる。
扱う内容
数え上げ、帰納、グラフ、半順序、包除、生成関数、漸化式、確率から、グラフ算法とフローへつなぐ。外見の異なる問題で共通の構造を見抜く応用と形式的な展開を両立する。
使い方
何を一個と数えるか定め、順序と重複の扱いを明示する。小さい場合を列挙して式を検証し、関係が中心ならグラフや半順序を描く。漸化式と生成関数の初期項を比べ、最適化では制約を点検する。失敗した案と改善の手掛かりも書き残す。
版と出典
著者の2016年全文版を安定した形で読める。CC BY-SA 4.0で、新しい改訂は別に維持される。授業と併用するときは同じ版を使い、章、問題番号、記法を照合して新旧の参照を混ぜない。
