文档介绍：第一章计算与计算机科学——引论§1,什么是计算、什么是计算科学?一、概念:《putation》——:“什么是计算?我相信,世界上没有两个计算机科学家会就这一概念给出相同的定义。”一个也许是最容易理解的定义:计算科学是使用数学语言对信息进行描述与处理的系统理论应用的科学。计算不等于数学,但数学确源于计算。计算科学不等于信息科学,但信息科学必须基于计算科学。二、内容1,基础——构造性数学(数理逻辑、代数系统、图论、集合论)历史:数学的三次飞跃。解析几何:由于笛卡尔坐标系的发明,把数与形联系在一起;微积分:将数学引人无穷小分域;群论:代数系统的整体结构研究。数学基础问题:集合论悖论()定义集合S={x|xS)数学公理体系的相容性。*特别关于“无矛盾与完备证明”以及“无穷总体的存在与真实性”的讨论导致三个数学派别的明确形成。,认为数学从逻辑推导而来,是逻辑的扩展。数学与逻辑是一个主题,逻辑先于数学。也就是说,数学可以不通过外加入新的概念而纯逻辑得到。罗素的《数学原理》。,认为数学是形式系统。每一个数学分支有自己的概念、公理和推导定理的法则以及自己的定理。把数学演绎系统通过形式的逻辑推理方式建立数学分支,而产生的数学分支将不存在悖论。数学的形式主义学派数学的直觉主义学派十九世纪末,由对数系与几何的严密化,。强调数学先于逻辑,而逻辑是从数学思维中总结出来的规律。主张数学中所有概念和证明都必须是构造性的,排中律只有在有限论域中是正确的,对无穷论域就不一定正确。一个数学名题除了正、反两面之外,还有一种可能——不可解。对数学证明中普遍使用的反证法,直觉主义学派只限于证明否定命题。三种数学学派都在现代数学中存在且各有利弊。从直觉主义学派的观点产生的构造性数学是计算科学的基础。计算必须建立在可构造的逻辑推理基础上。2,计算的数学理论计算理论、高等逻辑、形式语言与自动机、形式语义学、Petri网论、通信顺序进程(CSP)、通信系统演算、λ演算、进程代数(PA)、分布式事件代数(DEA)等。计算理论可计算性理论:抽象的计算模型及其性质,可计算函数以及之间关系;算法理论:抽象模型上的算法设计与算法复杂度;计算复杂性:算法复杂性,可计算函数的复杂性。高等逻辑模型论:形式语言及其解释之间的关系;非经典逻辑:时序逻辑、模态逻辑、概率逻辑、非单调逻辑、归纳逻辑、模糊逻辑。形式语言与自动机理论形式语言理论是用数学方法研究语言的语法(词法与文法),研究语言的构造性结构的学问;自动机理论,主要研究各种能自动处理符号的数学机器;当将自动机看成是一种符号接受器或识别器的时候,文法与自动机可以证明是等价的。形式语言学用数学方法研究语言的语义或语言的含义。特别是研究程序设计语言的语义。例:操作语义、指称语义、公理语义和代数语义。3,计算机组成原理、器件与体系结构根据计算模型研究计算机的工作原理,并按照器件、设备、工艺条件设计,制造具体的计算机。由于硬件的极限,当前重在分布式网络计算机系统和并行计算机系统。同时产生了对解问题的分布式算法与并行算法。可变结构与开放式系统是有希望的方向。算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术。算法基础是研究数值算法与非数值算法的基本设计方法与分析。数据结构主要研究数据表示与存储的方法、抽象的逻辑结构以其上定义的各种基本操作。4,计算机应用基础微机接口技术研究计算机之间及与外部设备仪器之间的数据连接问题。5,计算机应用技术数值计算、信号处理技术、图形学与图象处理技术、网络技术、多媒体技术、计算可视化与虚拟现实技术、人工智能技术、辅助设计、测试、制造、教学等辅助技术等。6,软件基础高级语言、数据结构、程序设计、编译原理、数据库原理、操作系统原理、软件工程。§2,计算机原理一、历史1623年:WilhelmSchikard在给开普勒的信中提出了加法器、乘法器和记录中间结果机构等三步分组成的机械式计算机的设想。1642年:,:,并制成样机,,:,并且用齿轮式寄存器、运算装置和专门控制操作顺序的结构组成的通用数字计算机的设计方案,1972年在美国明尼苏达大学建立了巴贝治信息处理研究所。19世纪: