绪论自动机、可计算性与复杂性 计算复杂性理论 可计算性理论 自动机理论 数学概念和术语集合序列和多元组序列 是某些元素或成员按某种顺序排成的一个列表。 与集合一样，序列也可以是有穷序列或者无穷序列。通常把有穷序列称为 多元组 。k个元素的序列称为 k元组。例如，（7,21,57)为一个3元组。 2元组也称为 有序对。 A的 幂集 为A的所有子集的集合。设A为集合{0,1}，则A的幂集为集合...
Continue reading

正则语言计算模型（Computational Model) 有穷自动机有穷状态机(Finite State Machine) 是描述能力和资源极其有限的计算机的模型。 有穷自动机和与之对应的 马尔科夫链（Markov Chains) 常用于识别数据中的模式。 状态图(State Diagram) 从一个状态指向另一个状态的箭头称为 转移 。 有穷自动机的形式化定义有穷自动机是一个5元组$(Q,Σ...
Continue reading

丘奇-图灵论题有穷自动机能较好地描述计算资源较少的设备，下推自动机虽然能描述具有无限存储的设备，但“后进先出”的栈机制使其能力受到限制，还证明了这些模型对于有些非常简单的任务都不能完成，由于它们过于局限，因此不能作为计箅机的通用模型。 图灵机图灵机(Turing Machine)与有穷自动机相似，但它有无限大容童的存储且任意访问内部数据。图灵机是一种精确的通用计算机模型，能模拟实际计算机的所有计算...
Continue reading

可判定性可判定语言与正则语言相关的可判定性问题与上下文无关语言相关的可判定性问题每个上下文无关语言都是可判定的。 停机问题检査一个图灵机是否接受一个给定的串问题是不可解的。 对角化方法康托对测量无限集合的规模问题提出了一个非常好的解决办法。他注意到：对于两个有限集合，如果其中一个集合的元素能与另一集合的元素配对，则它们有相同的规模。这个方法没有凭借计数就比较了规模，因而可以将此思想推广到无限集合...
Continue reading

可计算性理论的高级专题递归定理自引用存在可计算函数$q:Σ^ → Σ^ $，对任意串$w,q(w)$是图灵机$P_w$的描述，$P_w$打印出$w$，然后停机。 递归定理 设$T$是计算函数$t:Σ^ ×Σ^ →Σ^ $的一个图灵机。则存在计算函数$r:Σ^ →Σ^* $的一个图灵机$R$，使得对每一个$w$ 有：$t(w)=t(,w)$ 初看之下，此定理的叙述技术性很强，但实际上，它代表的事情很...
Continue reading

可归约性可用来证明问题是计算上不可解的一种基本方法， 可归约性 。 归约 旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题。 语言理论中的不可判定问题$HALT_{tm}$ (停机问题) 不可判定 线性界限自动机（linear bounded automaton，LBA) 是只有有限存储的图灵机。 映射可归约性将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使...
Continue reading

空间复杂性令$M$是一个在所有输入上都停机的确定型图灵机。$M$的空间复杂度(space complexity) 足一个函数$f:N→N$，其中$f(n)$是$M$在任何长为$n$的输入上扫描带方格的最大数。若$M$的空间复杂度为$f(n)$，则称$M$在空间$f(n)$内运行。 萨维奇定理该定理表明确定型机器可以用非常少的空间模拟非确定型机器。对于时间复杂性，这种模拟似乎需要指数倍地增加时间。对...
Continue reading

时间复杂性度量复杂性在 最坏情况分析（worst-case analysis) 中，即这里考察的形式，考虑在某特定长度的所有输人上的最长运行时间。在 平均情况分析(average-case analysis) 中，考虑在某特定长度的所有输入上的运行时间的平均值。 令$M$是一个在所有输入上都停机的确定型图灵机。$M$的运行时间或者 时间复杂度，是一个函数$f:N→N$,其中$N$是非负整数集合，$...
Continue reading

领域驱动设计何为领域驱动设计软件是由代码最终构成的。也许我们被代码所诱惑,在它上面花费了太多的时间,将软件看作是简单的对象或者方法。 为了创建一个好软件,你必须知道这个软件究竟是什么。在你充分了解金融业务是什么之前,你是做不出一个好的银行业软件系统领域的,你必须理解银行业的 领域 。 理解你的领域在启动一个软件项目时,我们应该关注软件涉及的领域。软件的最终目的是增进一个特定的领域。为了达到这个目的...
Continue reading

监控多个服务的指标跟踪Graphite之类的指标跟踪工具 服务指标暴露一切数据,然后依靠指标系统对它们进行处理。 综合监控Nagios监控告警 使用 合成事务 来确保系统行为在语义上的正确性,这也是这种技术通常被称为 语义监控 的原因。 在运行的系统上运行这些测试的子集，作为系统语义监控的一种方式。我们可以在生产环境上设置一组假用户和一些已知的数据集，不过必须确保不会触发意料之外的副作用。 使用关...
Continue reading