了解下数学

发布于 2017-07-17 11:26:30

集合论 命题验算 谓词逻辑 共同构成了数学的公理化基础

  • 空间

    • 度量空间
    • 拓扑空间
    • 向量空间

  • 完备性

    • 完备空间
    • 柯西序列：它的元素随着序数的增加而愈发靠近。
      • 更确切地说，在去掉有限个元素后，可以使得余下的元素中任何两点间的距离的最大值不超过任意给定的正数。
      • 柯西列的定义依赖于距离的定义，所以只有在度量空间中柯西列才有意义。
      • 在更一般的一致空间中，可以定义更为抽象的柯西滤子和柯西网。???

  • 逻辑

    • 归纳推理
    • 演绎推理
    • 溯因推理

  • 数理逻辑

    • 研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。
    • 皮亚诺算术公理（无限集合与自然数集的一一对应）

  • 形式系统

    • 形式语言
      • 语法
      • 语义
    • 推理规则

  • 计算理论

    • 计算模型
      • 图灵机
      • 天气预报模型、地球模拟器模型、飞行模拟器模型、分子蛋白质折叠模型和神经网络模型。
    • 可计算性
    • 复杂性
      • NP问题
        • 缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”。 直观的讲，我们将P中的问题视为可以较快解决的问题。
        • P和NP相等吗？
        • 假设P ≠ NP的复杂度类的图解。若P = NP则三类别相同。
        • 例子：子集合加总问题（背包问题）
          • 利用动态规划，背包问题存在一个伪多项式时间算法
          • 把上面算法作为子程序，背包问题存在完全逼近多项式时间方案
          • 作为NP完全问题，背包问题没有一种既准确又快速（多项式时间）的算法
        • 伪多项式时间：若一个数值算法的时间复杂度可以表示为输入数值规模N的多项式，但其运行时间与输入数值规模N的二进制位数呈指数增长关系
        • 假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的：
          • 忽略了常数因子
          • 忽略了指数的大小
          • 只考虑了最坏情况的复杂度
          • 只考虑确定性解
          • 即使一个量子计算机算法被发现能够有效的解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。
      • NPC：NP完全或NP完备（NP-Complete，缩写为NP-C或NPC）。
        • 一个决定性问题C若是为NPC，则代表它对NP是完备的：若任何NPC问题得到多项式时间的解法，那此解法就可应用在所有NP问题上。
          • 它是一个NP问题，且
          • 其他属于NP的问题都可归约成C。
            • 归约：将某个计算问题转换为另一个问题的过程。
            • 以直觉观之，“问题A可归约为问题B”，指问题B的答案可用于解决问题A。因此解决A不会难于解决B。一般写作A ≤ B，通常也在≤符号下标使用的归约手法。
        • 若任何一个NPC问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。
          • 因此NPC问题应该是最不可能被化简为P（多项式时间可决定（可计算出结果））的决定性问题的集合。
      • 简单的说（2017.10.27更新）
        • P问题：容易解决的
        • NP问题：不容易解决的
          • NPC问题：NP问题中的“本质”问题，其他问题都可以归约成它
        • P = NP?：是否可以将难问题转化成简单问题
          • 途径：证明NPC问题属于P问题(f(NPC)=P)

  • 群