本仓库是受 Linear Algebra Left Undone 的启发而建，其初衷是相似的，就不再赘述。在这里，笔者想要谈谈离散数学与线性代数相比的特殊性，以及这本讲义的特殊之处。

一方面，离散数学是一个非常广阔，近乎无所不包的领域。线性代数研究的范围大体可以称为“线性的代数结构”，即向量空间和其上的运算。这就使得它本身具备一个较为完整的体系结构：线性空间、线性映射、矩阵、二次型，这些概念几乎是顺理成章、一以贯之的。而离散数学就其题意而言，“数学”一词本就大而化之，无所设限；“离散”则强调其研究范围不是连续的东西——但是在研究过程中，连续化本身又是一个关键的方法。因此，笔者唯有以教材（Discrete mathematics and its applications by Kenneth H. Rosen）为蓝本，以个人理解为依托设计本讲义的框架。这使得这份讲义除了教材翻来覆去讲述的那些概念以外，增加了很多额外的私货。

另一方面，离散数学往往被视作“程序员的数学”。作为计算机专业的必修课，它本身就着眼于应用场景，看似少有严肃的数学见地。我们的授课老师、以及 K. H. Rosen 的教材均是按此种方式进行处理。这就导致同学们觉得，离散数学的核心就是“离”和“散”——教考分离、内容散乱。笔者则希望在此展现一套更具备“数学风格”的理论体系：一方面，直面计算机学科的问题，不仅就技术应用而言，也就计算机科学本身而言；另一方面，体现这套理论体系所立足的数学**和方法，这需要诉诸近代数学，尤其是理论计算机科学的发展，并在此有所反映。

以上两点，也就诱发了这个仓库的取名：Concrete 和 Discrete 本来就构成了一对文字游戏，而我们的立足点，具体的写作风格和完整的体系建构，也是这个标题要旨的一部分。

如题所述，这本书探讨的问题是“离散”的问题——这相当于什么都没说。当我们仔细思考什么叫做离散的时候，我们不免会用到连续的概念，这也是个拓扑学的概念。在此，笔者粗略地将其解释为间断性——在两个对象中间不具备一个连续的转变过程。因此，这种结构（自第三部分形式化的描述开始）将称为本书的核心。

因为离散数学无所不包的特性，我们尝试以专题的形式构建整个体系，大致分为以下九个专题：

• 数理逻辑：主要探讨命题和证明的结构。这个部分在 K. H. Rosen 的书中为第 1 章、第 5 章和第 12 章。此外，因为 Rosen 的书中对逻辑讲的冗杂且古典，我们的展现将会体现一些现代性的要素，例如模型论和证明论的诸多操作等等。由于这部分对于计算机科学的特殊重要性，一些算法和工具的介绍也是必须的。
• 算法和计算：对应第 3 章和第 5 章的一部分以及第 12、13 章。同样的，Rosen 以古典方式呈现的东西会被形式化，并且最终提出理论计算机科学的核心问题。
• 离散结构：第 2 章和第 9 章。除此以外，我们会覆盖更多代数中讨论的结构，这是为了第九部分做铺垫。
• 离散动力系统：这一部分主要事关序列，包含部分第 8 章的内容。此外，我们会讨论更多动力系统的主题，包括离散博弈、以及离散系统的遍历性和一些信息论。
• 组合学：第 6 章和第 8 章的内容。我们会覆盖更多方法，例如分析组合学，以及一些使用在离散结构中讨论过的代数结构的方法。组合优化也是一个贯穿后半部分的主题。
• 概率：第 7 章。除了基本的内容以外，我们还会设计随机算法，尤其是将其应用在组合优化算法上。另外，我们会给出一些随机算法相关的复杂度类，这是对第二部分的延续。
• 图论：第 10 章和第 11 章。同样，我们在正题之外，还会从代数拓扑的视角去介绍一些图论的基本思路，这也是为了离散几何中的一部分内容做铺垫。
• 编码论和密码学：第 4 章。除了对初等数论的涉及以外，一些编码理论和密码学的内容会以更加体系化的方式呈现。这一方面得益于第二部分给出了密码学的真正背景，另一方面得益于第三部分对离散结构的介绍。在这里，全书的两条主线将首次贯串在一起。
• 离散几何：这是对 Rosen 的书的有益补充。离散几何的研究在近几十年来逐渐兴盛，其应用也愈发广泛。另外，对连续对象离散化、离散对象连续化的**呈现来说，这也是相当重要且经典的一个例子。

对于读者而言，笔者认为难以割舍的很多有意思的材料无疑反而会成为阅读的障碍，因此，在此，我们希望写作者遵循以下规范，这也是对笔者本人的一个提示：

• 尽可能减少对于非必要内容的引用。所谓的非必要内容，即不在 Rosen 书中的内容。如果需要引用，应该在章节前标明其依赖关系，以供读者参考。
• 对于难以完整呈现的话题，要么直接割舍，要么注明参考文献。不要为了一碟醋包饺子，为了一个只能称得上有点意思的结论花费超过一讲的篇幅。
• 既要注重文本的易读性，又要注意不应过度冗长。Rosen 的书遭人诟病的一大原因，就是它的例子之类的东西过度简单却占据了过长的篇幅。
• 允许引用后文，但需给出提示。因为本身体系的复杂性，我们不可避免地会用到一些后文才会完整介绍的内容。但是，作者在写作时，应该一方面尽可能减少这样的情况，另一方面允许读者不查阅后文即可有个粗略的了解，这对于作者的内容安排是一个很大的挑战。

读者若要通读本书全部内容，笔者实该感激涕零。而若是摘取其中部分章节来读，则笔者亦乐于为其提供完整的路径。为此，我们将 Rosen 书中涉及的内容分成完整的几讲放在对应的部分当中，虽然其中有些枝节或许并不值得单开一讲来讨论。急切的读者可以先阅读对应的部分，再寻找其他的内容选择性阅读。每个部分的开头往往是对此部分历史和发展的评述以及对本部分数讲内容的概括，读者亦可根据那里的介绍自行寻觅。

如果一本教科书只能被按顺序阅读，那该是多无趣的一件事啊！（Serge Lang，知名数学家、数学教育家）

如果你希望为这个项目做出贡献，你需要了解或遵循的是：

• 本项目的许可证为 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
• 贡献方式
  • Pull Request（推荐）：推荐通过 PR（即 Pull Request）的形式来进行贡献，具体流程：
    • 在 GitHub 网页端点击右上角的 fork，将本仓库 fork 到自己的帐号下
    • 在自己帐号的对应仓库中进行修改
    • 修改完成后，点击 New Pull Request，提交一个 PR
    • 等待其他人审核、修改，然后合并到本 repo 中
  • 如果要修改的内容不多，只是一些 typo 等，或是有更好的编写思路等可以通过提 issue 的方式与我们进行交流
  • 特别注意：如果你不是本项目的合作者，请不要直接向本仓库 push，这样的行为都将是无效的
• 讲义部分请严格按照当前文件结构进行提交，即保持现有的章节目录，图片放在 figs 文件夹中。如果有文件结构上的改变请先提 issue 或直接与我通过邮件/QQ 等方式交流

请在 src 目录下使用 XeLaTeX 编译 PDF。

latexmk -xelatex -interaction=nonstopmode -file-line-error -output-directory=build *.tex