谁能给我一些计算机理论知识

[马克思主义基本理论考点请帮忙分析分析马克思主义基本原理要考的主]马克思主义基本原理要考的主要考点：（1）世界的统一性在于物质性原理；（2）物质和意识的辩证关系原理；（3）必然性和偶然性辩证关系原理；（4）量变和质变的辩证关系原理；（5）辩证的否定观；（6）否定...+阅读

理论计算机科学 theoretical computer science 关于计算和计算机械的数学理论，也称为计算理论或计算机科学的数学基础。学科的产生在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。

30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。

学科内容理论计算机科学主要包括：①自动机论与形式语言理论；②程序理论（包括程序正确性证明、程序验证等）；③形式语义学；④算法分析和计算复杂性理论。在这些领域中，自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机（无限自动机）。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。

王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机（简称RAM）以及多带图灵机等。形式语言理论导源于数理语言学中的乔姆斯基理论。在这种理论中，形式语言分为四种：①0型语言；②1型语言；③2型语言；④3型语言。

相应地存在着0型、1型、2 型、3型四种形式文法。1型语言又名上下文有关语言，2型语言又名上下文无关语言，3型语言又名正则语言。其中2型语言最受人注意。60年代中期，还发现了这四类语言与四类自动机之间的对应关系（见表）在上表中，左边所列的语言恰好是右边与之对应的自动机所能识别的语言（见形式语言理论）。程序设计理论包括程序正确性证明和程序验证，它的一些基本概念和方法是40年代后期诺伊曼和图灵等人提出的。

诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。他的方法是：设有一给定的程序，且有变量X1,X2，…，Xn以及输入谓词P(X1，…，Xn)与输出谓词Q(X1，…，Xn)。如果能证明下列事实：若在程序执行前谓词P(X1，…，Xn)成立，则在程序执行后，谓词Q(X1，…，Xn)成立，程序的正确性得证。图灵的这一结果长期未引起注意，一直到P.瑙尔在1963年和E.F.费洛伊德在1966年重新提出这一方法后，才引起计算机科学界的重视。

此后，有不少理论工作者在从事这方面的研究。但正如E.W.戴克斯特拉在70年代中期曾指出的，实际有效的方法是边设计边验证，在设计完毕时证明或验证的过程也同时结束。J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。这种方法是先选定成千种基本程序模块，并借助已知的各种验证方法（包括程序正确性证明）来保证这些基本程序的正确性。

然后再提出一组能保持正确性的程序组合规则。这样，就可以通过不断的组合，生成各种各样的程序。有人指出，程序正确性证明技术所发展出来的“循环不变式”，即一个程序中的某一循环的入口或出口点上所附的谓词，有些文献中称作“归纳断言”，可以用来供程序研究用。也就是说，不像过去那样，对一个给定的程序找出其若干个循环不变式，然后借助这些不变式来证明这个程序的正确性；而是在编制这个程序之前，根据对这一程序的要求，找出若干个循环不变式，然后根据这些不变式来生成这个程序。

自动程序设计的概念也是从40年代提出的。图灵在1947年的一篇论文中，提出借助定理证明的方法来设计程序。他的想法大致如下：设要求设计一个程序，使成为计算一个给定的递归函数F(X)的程序，并令F(n)=m（这里n是任一自然数，m是自然数），需要找到一个证明F(n)=m的构造性证明。在有了这样一个构造性证明以后，就可以从这个证明中提取出F(X)的求值算法，然后生成所需要的程序。

图灵的这一思想长时间不为人所知。1969年又有人独立地提出了这一想法。程序语言的形式语法的研究，从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少研究工作者从事这方面的工作，提出几种不同的语义理论，主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学，但仍没有一种公认在软件技术中够用的形式语义学，因而需要提出一种更适于用到实际计算中的新的语义学。

在程序正确性证明和形式语义学中应用的程序逻辑，是60年代末发展起来的。这是谓词逻辑的一种扩充。原来的谓词逻辑...