第 II 部 数学的構造

整数の性質を研究する分野は数論 (number theory) と呼ばれる。本書の第 \(\text{II}\) 部は数論の話題から始まる。整数は誰もが慣れ親しんでいる数学的構造でありながらも、簡単に表明できて興味深い証明を持つ性質を多く持つからである。そのため、第 \(\text{I}\) 部で紹介した証明技法を本格的に使う練習場として数論は優れている。さらに、数論は情報科学の様々な場面で応用される。例えば、現代的なデータの暗号化手法のほとんどは数論を利用する。

本書では整数を、異なる特徴を持つ要素から構成される数学的な構造 (structure) として扱う。整数という構造の構成要素の一つは、当然ながら、整数全体の集合である。二つ目の構成要素として加算・乗算・冪乗といった基礎的な数学演算がある。他の構成要素としては、整数の重要な部分集合がある ── 例えば素数全体の集合は、その要素の積で任意の整数を表現できるために重要である。

さらに一般的に言えば、構造を持ったオブジェクトは情報科学において基礎的な役割を果たす。コードを書くとき、最適化問題を解くとき、ネットワークを設計するとき、あなたは構造と格闘することになる。

グラフ (graph) は情報科学で基礎的な役割を果たす構造の一つであり、ネットワーク (network) とも呼ばれる。グラフはオブジェクトの組の関連付けをモデル化できる: 例えば「同じ時間に開催できない二つの試験」「お互いを知っている二人の人間」「独立に実行できる二つのサブルーチン」といった概念のモデル化でグラフは利用できる。第 10 章では、一方向の関係をモデル化する有向グラフ (directed graph, digraph) を紹介する。例えば人間の恋愛関係 (残念ながら相互的でない場合の方が多い) やタスクの依存関係は有向グラフで表現できる。章の最後では、半順序 (partial order) という関係のクラスに対応する有向非巡回グラフ (directed acyclic digraph, DAG) と呼ばれる有向グラフの特殊ケースに触れる。半順序はスケジューリングや並列性を考え始めると頻繁に姿を現す。第 11 章ではデータ通信とルーティングの問題を有向グラフでモデル化する例を示す。

第 12 章では単純グラフ (simple graph) を説明する。単純グラフは 「衝突状態にある」「互換性がある」「独立する」「並列に実行できる」といった対称的 (相互的) な関係を表現する。第 \(\text{II}\) 部の最終章である第 13 章では平面グラフ (planar graph) ── 平面上に辺を交差させずに描画できる平面グラフ ── に触れる。この章の最後では地球の周回軌道上に \(50\) 個の衛星を均一に配置できないことが証明される。