离散数学

绪论

(Press ? for help, n and p for next and previous slide)

戴望州

南京大学・智能科学与技术学院
2023年-春季

https://daiwz.net

课程信息

时间：周二第3-4节 & 周四第1-2节
地点：馆3-201
教师：戴望州
- 研究方向：人工智能，机器学习，符号推理
- 答疑时间：每周三上午 9:00 - 10:00
- 联系方式：daiwz@nju.edu.cn，18651611832
助教：
- 黎运泽：yunzeli@smail.nju.edu.cn，18252070509
- 王子龙：zilongwang@smail.nju.edu.cn，18252070211
- 赵晶婵：zhaojingchan@163.com，13830793328
- 赵晓颖：522022320216@smail.nju.edu.cn，18602565253
课程主页：http://daiwz.net/teaching/
教材：Kenneth H. Rossen，离散数学及其应用，机械工业出版社

课程分数

平时分：30%
- 作业
- 课堂表现
- 与老师、助教的交流
- 考勤
期中考试（闭卷）：20%
期末考试（闭卷）：50%

离散数学是什么？

“连续”数学
“离散”数学：计算机学科的数学基础
- 关于数学的数学：“元数学”（metamathematics）
  - 数理逻辑、集合论、抽象代数
- 关于（离散）问题求解的数学
  - 组合数学、概率（离散部分）、图论

“离散”比“连续”更复杂

Fermat's Last Theorem \[\not\exists x,y,z,n\in\mathbb{Z}^+(xyz>0\wedge n\geq3\wedge x^n+y^n=z^n)\]

“关于此，我确信已发现了一种美妙的证法，
可惜这里空白的地方太小，写不下。”

数学“缝合怪”？

为什么要把这些看起来毫不相干的东西放在一起？

例子

集合 \(\{1,2,\ldots,2000\}\) 的子集中，
有多少个子集的和能被 \(5\) 整除？

数学“缝合怪”？

离散数学研究离散对象的结构

课程内容比例

逻辑与证明
集合论
计数与离散概率
抽象代数
图论

离散数学有什么用？

数学

现代数学的基础

计算机科学

数据结构
算法
数据库理论
形式语言与自动机
编译原理
操作系统
信息安全

例子：八皇后

n_queens(N, Qs) :-
        length(Qs, N),
        Qs ins 1..N,
        safe_queens(Qs).

safe_queens([]).
safe_queens([Q|Qs]) :-
        safe_queens(Qs, Q, 1),
        safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
        Q0 #\= Q,
        abs(Q0 - Q) #\= D0,
        D1 #= D0 + 1,
        safe_queens(Qs, Q0, D1).

人工智能

符号推理
统计学习
神经网络

智能的分工：系统I、系统II

你能多快判断出以下命题的正误？

\(1+1=2\)是对的。
窗外的树有些是绿色的。
\(\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\longleftarrow\)这里有5个圈。
\(\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\longleftarrow\)这里有18个圈。
若\(p\rightarrow q\)且\(q\rightarrow r\)，那么\(p\rightarrow r\)。
\(1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}+\cdots=\frac{\pi^2}{6}\)。
如果教室里有一百只大象，那么我的离散数学就拿能满分。
“我只给自己不理发的人理发，所以我可以给自己理发”。
乌克兰在一年之内应该会停火。
\(P= NP\)是错的。

智能的分工：系统I、系统II

系统I：

直觉思维、一步到位
大量训练实现肌肉记忆、熟能生巧
速度快、几乎不消耗注意力
失败时放弃并转向系统II

系统II：

程序思维、逐步推理
必须依赖背景知识、举一反三
速度慢、消耗大量注意力
经常（盲目）相信系统I提供的信息
过于困难时放弃并转向系统I

离散符号：认知计算的基本表征

一个大胆，但又不得不做的假设：认知是一种计算

“计算”具有普适性：
- 通用图灵机
- \(\lambda\)演算
- 原始递归函数
- C语言
“计算”是一种抽象过程，与承载它的物理设备无关：
- 大脑
- 电子计算机
- 量子计算机
我们最终希望用计算机实现一个认知体（弱/强人工智能）

离散符号：认知计算的基本表征

一个大胆，但又无法避免的结论：认知是关于离散符号的计算

没有无符号表征的计算：包括用代码实现的DNN
计算是由规则支配的过程：函数、证明、形式语言、逻辑推理
所谓的黑箱——直觉、情绪乃至神经网络：输出的表征仍然是符号
认知是可穿透的：可解释、可调试

离散数学怎么学？

挑战

这是一门关于抽象本身的数学课；
- 可能不是大家想像中传统的数学课；
- 和分析、线代不一样，解题的“技巧”不是最关键的；
- 关键在于理解定义和概念，以及为什么要定义这些结构；
课程系统性不明显，topics 之间跳跃性较大；
- 我们会尽量将它们串起来，多 callback，帮助大家加强印象；
作为一个前导课程，内容大多浅尝辄止，目的性不强；
- 我们会介绍一些背景与动机；
  - 计算机、人工智能方面的应用背景；
  - 数学上的意义；

（期望的）收获

获得大量外功招式
- 一些未来迟早会用到的数学工具；
- 命题论证与问题求解的能力；
提升内力
- 抽象思维；
- 数学审美；
打通任督二脉
- 学会系统性思维；
- 除了收获学分积，更要提升悟性！