離散数学
とびとびの対象を扱う数学。計算機は有限の離散的な機械なので、その理論的な土台になる。
とびとびの対象を扱う数学。 連続量を扱う微分積分と対になる。
計算機は有限の離散的な機械なので、 その理論的な土台はほぼ離散数学の上にある。
主な話題#
| 話題 | どこで使うか |
|---|---|
| 集合・関係・写像 | あらゆる定義の土台 |
| 命題・論理演算 | 回路、論理、証明 |
| 証明・帰納法 | アルゴリズムの正しさ |
| 順列・組合せ | 組合せ最適化の候補数、確率 |
| グラフ・木 | ネットワーク、探索、Max-Cut |
参考文献#
- Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
- MIT OCW 6.042J Mathematics for Computer Science https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/