计算机科学的理论基础

二、程序理论

   程序理论研究的主要内容包括算法设计与分析，形式语言与自动机理论、形式语义学、程序逻辑、程序验证、以及程序设计自动化的理论基础。

   算法设计的目标是涉及具有高度时空效率的问题求解方法。具有基本数学结构的问题的快速算法和包括各种图论算法在内的组合优化算法一直是算法设计研究的重点之一。预算发射机密切相关的是算法的分析和算法效率测试的选择。由于大多数求解最有解算法的困难性，人们转而研究各种启发式搜索算法，以及与之相适应的概率分析方法。从本质上说这是牺牲完全性来换取高效率。启发式算法将对今后的计算机科学，特别是人工智能的研究产生重大影响。

由于VLSI技术的飞速发展，使得硬件的体积不断缩小，价格大幅下降，于是人们很自然的产生了建造拥有大量处理单元的并行处理机系统的想法。并行处理技术已经成为一个研究热点。

   并行算法是并行处理技术的核心。现有两种不同类型的并行算法，分布式算法和紧藕合算法。并行计算机发展带来的基本问题是：那种问题适合于并行处理，即可以从并行中得到实质的好处，如何设计并行算法才能最大限度的得到这些好处。

    从并行中得到“实质性”好处要求并行算法的运行时间不超过输入规模的对数多项式，例如logn或(logn)^2。使用合理数量（多项式界限）处理机的并行算法在上述以一下求解的所有问题组成NC类。这样第一个基本问题就是P=?NC研究表明答案可能是否定的，但和P=?NP一样，计算理论方面的成果都回避这个问题，并致力于寻找适合于并行处理的领域。

     1976年出现的随机算法拓宽了算法的概念，开拓了算法设计的新领域。目前研究比较多的随机类有ZPP、BPP、PP等。这些类与其他一些重要的复杂性类之间存在着深刻联系，因而P=?BPP在计算复杂性研究中也是吸引人的问题。软件开发自动化是提高软件生产率，保证软件产品可靠性的途径之一。算法设计是软件开发中最困难的也是最富创造性的活动，因而算法设计自动化的研究构成了软件开发自动化研究的核心内容。从目前来看，算法设计自动化的目标应是人机合作系统，并不断减少人工干预，逐步提高系统的自动化程度。

     形式语义学、形式语言与自动机理论的研究近年来似乎不那么活跃，但是更加深入细致的刻画自然语言中的内在的逻辑结构，研究自然语言的形式化问题仍是令人关注的，比如Montague的内在逻辑系统已经引起人们的重视。三、计算机科学中的逻辑与代数

   逻辑与代数是计算机基础理论的两大基础，这一领域的传统课题和值得注意的发展方向是机器证明、模型论、各种非经典逻辑和范畴论。

   机器证明就是使用计算机证明定理。机器证明有试探法、判定算法和证明算法等研究方向。机器证明是程序推导、程序验证、机器推理、和专家系统等研究领域的重要基础。

由于经典逻辑在表达能路和推理方法上的局限，使得人们从不同的应用、不同的角度、出发提出各种非经典逻辑。这一领域的研究相当活跃，而且有进一步发展的势头。目前引起人们关注或得到较多应用的是模态逻辑、时态逻辑、直觉主义逻辑、非单调逻辑、模糊逻辑和内涵逻辑等。范畴论则由于其表达方式的高度抽象性和构造性，在程序设计语言语义学、程序规范和逻辑学等诸多分枝中获得了应用，为这些学科的研究提供了新工具和新思想。今后范畴轮在计算机科学领域有望开拓更多的应用领域。

   计算机基础理论研究既有经典难题，有又不断出现的新问题，是一个活跃的，不断产生新概念、新思想、新方法的研究领域。预计未来将会在渐进中酝酿或产生新的突破。