主要研究内容数值计算致力于设计、分析、使用模拟物理过程或社会过程的各种数值算法。早在18、19世纪，C.F.高斯、I.牛顿、J.傅里叶等著名数学家就研究过数值计算方法，而计算机的诞生则大大促进了数值计算的发展。数值计算涉及的内容很多，包括方程求根、数值逼近、数值微分、数值积分、数值代数、线性代数方程组的数值求解、矩阵特征值的计算、微分方程的数值求解等。例如，高次代数方程求根，常用的方法有二分法、牛顿法、割线法等；数值微分，即导数近似值的计算，常用的是有限差分法。数值积分研究求定积分近似值的理论与方法，其中梯形法和辛普森法最为人熟知。线性代数方程组的数值求解（见线性代数方程组数值解法），即求线性代数方程组的数值解，有直接法和迭代法两类：高斯消去法为前者，而简单迭代法和赛德尔迭代法都属后者。 符号计算研究如何在计算机上表示和处理有含义的抽象符号，设计用于符号运算和推理的有效算法以及适合实施这些算法的程序语言和软件系统，并将其用于解决各式各样的理论与实际问题。符号计算同数值计算不同，前者是指符号对象、符号表达式之间的运算和推理，通常是形式的、精确的，因而没有误差。符号计算始于20世纪60年代，其发展始终与代数计算和软件研发联系在一起，并受到物理计算的激励，其主要学科分支包括计算机代数与分析、几何计算、自动推理和自动编程等。符号计算、自动推理与中国学者吴文俊开创并倡导的数学机械化密切相关，而作为相近学科它们又各具特色、优势不一。符号计算强调构造性理论的建立与发展、有效算法的设计与实施、软件系统的研制与开发，以及它们在科学工程中的应用。计算机代数是符号计算的一个主要分支，所研究的对象是抽象的数学符号与概念，如整数、有理数、多项式、理想等，其中心课题是设计处理这些代数对象的算法并将其在计算机上有效地实施，进而解决各种代数计算和推理问题。计算实代数几何探讨实闭域上的量词消去，实系数多项式实根数目的判定和整系数多项式的实根隔离算法等。几何计算主要研究在计算机图形环境下对曲线、曲面信息的表示、逼近、分析和综合。符号微积分主要研究符号微分、符号积分和微分方程的符号求解算法。符号与数值混合计算主要研究如何将符号计算和数值计算结合起来，运用符号计算来处理近似奇异或对扰动敏感的病态问题，而用数值方法来加速符号计算的某一部分或计算可靠的近似解。基于符号计算的吴方法为计算机证明和发现几何定理、解决各种几何问题提供了有效工具，使几何定理的机器证明成为自动推理领域最活跃的分支之一。 离散数学泛指数学中讨论离散对象的分支。同连续数学不同，离散数学通常涉及整数系。由于数字计算机是离散机，离散数学的重要性不言而喻。通常认为离散数学包含集合论、图论、组合数学、数理逻辑、抽象代数、线性代数、差分方程、离散概率论等学科。图论是研究图的性质的学科。图论中的图并非初等数学中的图，后者只是连续函数的图形，而前者则是一组顶点（结点）和一组连接两顶点的边（支）所构成的集合。组合数学讨论计算某类对象个数的方法，它在统计学、理论物理、化学、社会科学、通信理论和计算机科学技术中都发挥着重要作用。多数组合学问题可以归结为存在性问题、枚举性问题或选择性问题。数理逻辑研究形式系统。作为其组成部分的命题演算与谓词演算等在计算机科学技术中极为重要、不可或缺。诸如计算机设计、软件开发、程序正确性验证，以及人工智能等领域无不用到数理逻辑。抽象代数讨论离散对象的结构，它在计算机科学技术中应用广泛。例如，半群被用于形式语言理论和自动机理论，群在编码理论中有其重要作用。线性代数虽然涉及实变量，但其结构与处理问题的方式均为离散型，因而也可归为离散数学。此外，差分方程、离散概率论等亦属离散数学。 概率统计包含概率论和数理统计两个部分。概率论是研究客观世界随机现象数量规律的学科，主要探讨事件发生的可能性，最初与赌博问题有关。1713年，J.伯努利建立了概率论中第一个极限定理，即伯努利大数定律，阐明了事件的频率趋近于它的概率，从而奠定了概率论的基础。随后A.棣莫弗和P.S.拉普拉斯又导出了中心极限定理的原始形式。P.S.拉普拉斯在系统总结前人工作的基础上写出了《分析的概率理论》，明确给出了概率的古典定义，并在概率论中引入了更有力的分析工具，将概率论推向一个新的发展阶段。19世纪末，俄国数学家P.L.切比雪夫、A.A.马尔可夫、A.M.李亚普诺夫等人用分析方法建立了大数定律及中心极限定理的一般形式。20世纪初，应用物理学、生物学、管理科学等学科发展的需求，以依赖时间参数的一组随机变量的全体作为研究对象的随机过程理论和方法逐步建立起来，具体内容包含布朗运动、泊松过程、正态过程、二阶过程、马尔可夫过程、平稳过程、鞅点过程、分支过程等，A.N.科尔莫戈罗夫、N.维纳、A.A.马尔可夫、A.Y.辛钦、P.P.莱维及W.费勒等人对这些随机过程的建立和发展作出了杰出贡献。以概率论为理论基础，数理统计研究如何有效收集、分析和解释数据，以提取信息、建立模型，并对随机现象进行推断和预测，为寻求规律和优化决策提供科学依据，其主要内容包括参数估计、假设检验、多元统计分析、大样本统计、非参数统计、统计决策、贝叶斯统计、实验设计、回归分析、相关分析、序贯分析、时间序列分析、稳健统计等众多分支。K.皮尔森、R.A.费希尔等学者的工作对数理统计的建立起到了决定性的作用。 计算理论和程序理论是计算机科学理论的两大支柱。计算理论是研究计算的过程与效用的数学理论，主要包括可计算性理论、计算复杂性理论、形式语言与自动机理论等。作为计算机科学的理论基础，计算理论的主要研究目标是致力解决“什么能够被有效地自动化”这个根本问题。 可计算性理论是用数学的方法研究计算的一般性质的数学理论，目的是为了精确区分哪些问题是可计算的，哪些问题是不可计算的。计算的过程就是执行算法的过程。20世纪30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻画为递归性。20世纪30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻画为在具有严格定义的理想计算机上的可解性。可计算性理论主要包括图灵机、丘奇图灵论题、λ演算、原始递归函数、部分递归函数、递归集、递归可枚举集、可判定性等。 计算复杂性理论是以各种可计算函数（即递归函数）为研究对象，用数学的方法研究其计算复杂性（早期称为计算难度）的理论，目的是将可计算问题根据它们的计算复杂性进行分类，从而断定哪些问题是可以被有效计算的。算法复杂性是针对特定算法而言的，研究在计算过程中所需的资源，比如时间和空间，以及如何尽可能地节省这些资源。关于这一领域的名称曾有争议。一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论主要包括复杂性的度量、P与NP、NP完全等各类复杂性。 自动机理论是用数学的方法研究抽象的信息处理和计算装置及其计算能力的理论。自动机理论与形式语言理论密切关联，因为自动机通常按它们所能识别的形式语言类来分类。自动机理论的研究可上溯到20世纪30年代A.M.图灵提出的图灵机。J.冯∙诺伊曼在20世纪50年代初提出了有自繁殖功能的计算机的概念。王浩在20世纪50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出了一种存储带上的内容不能清除的机器，并证明了这种机器是与图灵机等价的。多数自动机都是图灵机的特例。自动机理论一般包括有限自动机理论、无限自动机理论、概率自动机理论、细胞自动机理论等。形式语言理论是用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的语法的理论，主要包括描述工具、文法分类（如乔姆斯基层次）、语言分类，以及各类语言的性质及其相互关系等。 计算理论已经广泛应用于科学的各个领域。例如，程序存储式计算模型就是在图灵机的基础上产生的，程序设计中使用了递归函数的思想，自动机作为一种基本工具在程序设计的编译过程中被广泛使用。 程序理论是研究程序的语义性质和程序设计及开发方法的理论，主要包括程序语义理论、数据类型理论、程序逻辑理论、程序验证理论、并发程序设计理论和混合程序设计理论等。程序语义又称形式语义，是以数学为工具，利用符号和公式，精确地定义和解释计算机程序设计语言语义，使语义形式化的学科，主要包括操作语义、指称语义、公理语义和代数语义。形式语义的研究始于20世纪60年代初期，ALGOL60是第一个明确区分语法和语义的程序设计语言。20世纪70年代以后，形式语义的研究取得了重大进展。程序理论对形式语义的需求，促进了论域、偏序以及范畴论等数学理论的发展。在形式语义学基础上，形式规范、程序变换、编译自动化等研究都取得了丰硕成果。 程序理论的早期研究是为了解决程序验证问题，即要证明程序能达到某种预定目标。J.冯∙诺伊曼在1947年发表的论文中就提到了程序正确性证明。美国计算机科学家R.W.弗洛伊德（Robert W．Floyd）于1967年系统地提出了验证程序正确性的归纳断言方法，引起了计算机科学界研究程序验证的热潮。C.A.R.霍尔在20世纪60年代首次提出了程序逻辑理论，为程序语言的每个语句都给出相应的逻辑规则，通过利用这些规则验证程序执行前后程序变量是否满足相应的条件。为了克服霍尔逻辑不能进行逻辑演算的缺点，一些学者在20世纪80年代提出了类型理论以求为程序设计与开发建立更完善的理论框架，只要对给定的规约（逻辑命题）进行证明，就可以构造出符合此规约的程序，从而保证程序的正确性。 为了保证在操作系统中多个没有因果关系的并行执行进程的正确性，并发程序理论在20世纪70年代初应运而生。随着并行和分布式计算机系统的迅速发展，并发程序理论逐渐成为程序理论的一个重要分支，主要研究并行进程的行为描述，各种通信和同步机制，死锁及活性、可观察性和发散性等并发现象。自20世纪90年代以来，越来越多的控制系统中存在两类不同对象：根据传统控制理论，使用微分方程刻画的连续现象和根据逻辑或代数方法，使用计算机程序控制的离散型事件，这类系统又称混合系统。混合系统的程序理论已成为新的研究热点，主要研究问题包括如何建立混合系统的计算模型，设计描述混合系统的高级语言，探索混合系统程序的设计和开发方法。 主要研究机构、代表性期刊和学术会议美国计算机协会算法与计算理论委员会（Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, ACM SIGACT，1968年创建）和欧洲理论计算机科学协会（European Association for Theoretical Computer Science, EATCS，1972年创建）是协调推动计算机科学理论交流合作的两个主要国际学术组织。成立于1983年的中国计算机学会理论计算机科学专业委员会，旨在加强全国范围内的学术交流，促进计算机科学理论的普及和推广。 计算机科学理论的学术研究广泛深入，其文献著作大量出版，其中的代表性期刊包括《信息与计算》(Information and Computation, 1987～ )、《理论计算机科学》(Theoretical Computer Science, 1975～ )、《计算系统理论》(Theory of Computing Systems, 1967～ )、《计算的形式方法》(Formal Aspects of Computing, 1989～ )、《美国计算机协会杂志》(Journal of the ACM, 1954～ )、《工业和应用数学学会计算杂志》(SIAM Journal on Computing, 1972～ )、《符号计算杂志》(Journal of Symbolic Computation, 1985～ )、《计算机科学基础国际杂志》(International Journal of Foundations of Computer Science, 1990～ )、《离散数学与理论计算机》(Discrete Mathematics and Theoretical Computer Science, 2001～ )、《理论计算机科学基础与趋势》(Foundations and Trends in Theoretical Computer Science, 2005～ )、《自动机，语言与组合学杂志》(Journal of Automata, Languages and Combinatorics, 1996～ )、《信息学报》(Acta Informatica, 1971～ )、《信息科学基础》(Fundamenta Informaticae, 1986～ )、《美国计算机协会算法学报》(ACM Transactions on Algorithms, 2005～ )、《美国计算机协会计算理论学报》(ACM Transactions on Computation Theory, 2009～ )、《计算复杂性》(Computational Complexity, 1991～ )、《复杂性杂志》(Journal of Complexity, 1985～ )和《计算机科学中的数学》(Mathematics in Computer Science, 2007～ )。 计算机科学理论领域的会议主要包括：美国计算机协会计算理论年会 (Annual ACM Symposium on Theory of Computing, STOC)，电气与电子工程师协会计算机科学基础年会 (Annual IEEE Symposium on Foundations of Computer Science, FOCS)，理论计算机科学创新(Innovations in Theoretical Computer Science, ITCS)，美国计算机协会与电气与电子工程师协会离散算法研讨会 (ACM–SIAM Symposium on Discrete Algorithms, SODA)， 美国计算机协会与电气与电子工程师协会计算机科学中的逻辑年会 (Annual ACM/IEEE Symposium on Logic in Computer Science, LICS), 计算复杂性会议(Computational Complexity Conference, CCC)，自动机、语言与程序国际会议 (International Colloquium on Automata, Languages and Programming, ICALP)， 计算几何年会 (Annual Symposium on Computational Geometry, SoCG)，美国计算机协会分布式计算原理研讨会 (ACM Symposium on Principles of Distributed Computing, PODC)，美国计算机协会并行算法与架构研讨会 (ACM Symposium on Parallelism in Algorithms and Architectures, SPAA)，计算机科学理论方法研讨会 (Symposium on Theoretical Aspects of Computer Science, STACS)，欧洲算法大会 (European Symposium on Algorithms, ESA)，美国计算机协会符号与代数计算国际研讨会 (ACM International Symposium on Symbolic and Algebraic Computation, ISSAC)， 算法与计算国际研讨会 (International Symposium on Algorithms and Computation, ISAAC)和计算理论基础国际研讨会 (International Symposium on Fundamentals of Computation Theory, FCT)。 扩展阅读
|
|
|
来自： 求是1025 > 《133新一代信息技术产业》
