離散数学

社会でどう使われるか

Googleのページランクはグラフ理論で動いている。SNSの友人推薦もグラフ理論だ。コンパイラは命題論理と有限オートマトンで設計されている。「n段の証明が成り立つから n+1 段も成り立つ」——数学的帰納法はアルゴリズムの正当性証明の基本技法だ。離散数学なしにプログラミング・ネットワーク・暗号は存在しない。

要点

グラフ理論の基礎

グラフ G = (V, E) は頂点集合 V と辺集合 E からなる。有向グラフ・無向グラフ・重み付きグラフなどがある。次数（degree）は頂点に接続する辺の数。

数学的帰納法

①P(1)が成り立つ（基底）、②P(k)が成り立つと仮定すると P(k+1)も成り立つ（帰納）——この2つを示せばすべての自然数 n で P(n) が成り立つ。

帰納法で Σk = n(n+1)/2 を証明

①n=1: 1=1×2/2=1 ✓ ②P(k)仮定: Σ₁^k k = k(k+1)/2 → P(k+1): Σ₁^{k+1} k = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓

命題論理とブール代数

真偽値（0/1）の演算。AND（∧）、OR（∨）、NOT（¬）、XOR（⊕）。真理値表で全パターンを記述できる。論理回路・CPUの設計基盤。

BFS/DFS（グラフ探索）

幅優先探索（BFS）は最短経路・SNS距離の計算に使う。深さ優先探索（DFS）はバックトラッキング・迷路探索・トポロジカルソートに使う。

この単元を使う職業

ソフトウェアエンジニア（アルゴリズム）¥1400万

暗号エンジニア¥1500万

データエンジニア（グラフDB）¥1200万

要点

この単元を使う職業

ここから先は会員限定です

コメント