《计算科学导论》笔记大全

1) 人工智能中的机器学习和知识获取就与模型论有关。一个扩展知识的工作由机器来完成，有什么方法能够保证加入新知识后原有体系是无矛盾的呢？用模型论的语言来说，一个具有模型的逻辑系统如何扩张。可惜，今日从事机器学习和知识获取研究的学者，目前还很少使用模型论。

2) 对软件系统高可靠性的要求使得如何保证程序的正确性成为一个令人头痛的大问题。这个问题不能靠经验技术加以解决，而只能走程序正确性证明之路或从一开始就依靠某种在开发过程中能确保软件正确的技术道路，并贯彻在整个软件的始终，即所谓的形式软件开发方法之路。
在并发和并行软件的开发中，由于并发程序和并行程序的动态语义定值问题一直是一个尚未彻底解决的困难问题，从而导致证明这类程序的正确性便成为一个悬而未决的问题。

3) 为什么说数理逻辑和代数是计算科学的主要基础？
1，从计算模型和可计算性的研究来看，可计算函数和可计算谓词（一种能够能行判断其真值的断言）相互之间可以转化。这就是说，计算可以用逻辑来表达。作为一种数学形式系统，图灵机及其与它等价的计算模型的基础是数理逻辑。
2，实际计算机的设计与制造，使用数字逻辑技术襀计算机的各种运算的理论基础是代数和布尔代数。布尔代数只是在形式演算方面使用了代数的方法，其内容的实质仍然是逻辑。而数字逻辑技术和集成电路技术只是计算机的一种产品的技术形式。
3，从计算机程序设计语言方察，语言的理论基础是形式语言、形式语义学。而形式语言、形式语义学所采用的主要研究思想和方法来源于数理逻辑和代数。此外，程序设计语言中的许多机制和方法，如子程序调用中的参数传递、赋值等都出自数理逻辑的方法。也就是说，数理逻辑的发展为语言学提供了方法论的基矗
4，在计算机体系结构的研究中，像容错计算机系统、TRANSPUTER系统、阵列式计算机等都是直接或间接与逻辑与代数密不可分。如容错计算机的重要基础之一是多值逻辑。
5，从计算机的各种应用的程序设计方面考察，任何一个可以存储程序式电子数字计算机上运行的程序，其对应的计算方法首先必须是构造性的，数据表示必须离散化，计算操作必须使用逻辑或代数的方法进行，这些，都体现在算法和程序之中。此外，到目前为止，程序的语义及其正确的理论基础仍然是数理逻辑，或进一步的模型。

4) 在计算科学的发展中，有一批在种个分支学科中重复出现的概念。它们虽然在各个学科中的具体解释在形式上有差异，但相互之间存在着重要的联系。核心楰是计算机科学重要思想、原则、方法、技术过程的集中体现，有助于在学科的深层统一誝计算科学。对核心概念的深入理解和正确拓展与应用的能力，是计算科学家和工程帅成熟的标志之一。
计算机科学的核心概念：
1，计算模型与能行性：
计算模型(comutation model)，可计算性(computability)，计算复杂性(computational complexity)，最优性(optimum)，相似性与对偶性(similarity and duality)。
2，抽象与构造性描述
论域与计算对象(domain and computing object)，枚举与有穷表示(enumeation and finite representation)，分层与抽象的级(hierarchy and levels of abstraction)，内涵与外延(intension and extenstion)，递归(recursion)，归纳(induction)，自由与约束(freedom and restriction)。
3，系统特征
相容性(consistency)，完备性(completeness)，单调性(monotoneity)，透明性(transparence)，容错与安全性(fault-tolerant and security)，开放性(openness)，稳定性(stability)，健壮性(robustness)。
4，计算方法
折衷(compromise)，分解(decomposition)，集成(integration)，类比(analogy)，推导(inference or reasoning)，变换(transformation)，扩展(extension and expansion)。
5，实现技术
类型(type)，进程与线程(process and thread)，顺序与并发(sequence and comcurrence)，软计算结点(actor)，关联与实例化(binding)，现役的(active)，虚拟(virtual)，编码(coding)，模式匹配(pattern matching)，分杈(branching)，合一（或通代）(unification)，循环与迭代(loop and iteration)，重用(reuse)，协议(protocol )，规范与标准化(standardization)。

5) 计算机科学中的一组典型实例：
停机问题，哲学家共餐问题，可满足性问题，货郎担问题，生产与消费问题，方法的二义性问题，上下文语义问题，最小生成树问题，阿克曼函数，鞍点问题，子集和数问题，确定性自动机与不确定性自动机的等价问题，八皇后问题，三个中国人算法。。。