1、计算机科学研究概述Lecture 3第一节 计算机科学研究的历史背景n1.1 计算机科学源于欧美，诞生于20世纪40年代初。n在第一台电脑诞生以前n1.2 ACM和IEEE-CSnAssociation for Computing MachinerynInstitute of Electrical and Electronics Engineers-Computer Societyn1.3 计算作为一门学科的报告（Computing as a Discipline）nCC1991nCC2001世界上第一台计算机 ENINAC1.4 计算学科中的典型问题n哥尼斯堡七桥问题哥尼斯堡七桥问题n17世
2、纪的东普鲁士有一座哥尼斯堡城世纪的东普鲁士有一座哥尼斯堡城，城中有一座奈佛夫岛，普城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区南区和岛区4个区域，全城共有个区域，全城共有7座桥将座桥将4个城区相连起来。个城区相连起来。n通过这通过这7座桥到各城区游玩，问题座桥到各城区游玩，问题：寻找走遍这寻找走遍这7座桥的路径，要座桥的路径，要求过每座桥只许走一次，最后又回到原出发点。求过每座桥只许走一次，最后又回到原出发点。 岛 区 北 区 东 区 南 区 问题的抽象问题的抽象n1736年，大数学家列年，大数
3、学家列昂纳德昂纳德欧拉（欧拉（L.Euler）发表了关于发表了关于“哥尼斯堡哥尼斯堡七桥问题七桥问题”的论文的论文。n他他抽象出问题最本质的抽象出问题最本质的东西，忽视问题非本质东西，忽视问题非本质的东西（如桥的长度的东西（如桥的长度等），从而将哥尼斯堡等），从而将哥尼斯堡七桥问题抽象为一个数七桥问题抽象为一个数学问题，即经过图中每学问题，即经过图中每边一次且仅一次的回路边一次且仅一次的回路问题问题 D C B A 欧拉回路n欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方法给出了三条判定规则：n如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。n如果只有两个地方通奇数座桥，可以从这两个地
4、方之一出发，找到所要求的路线。n如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。图论的形成和发展n欧拉的论文为图论的形成奠定了基础。n图论已广泛地应用于n计算学科n运筹学n信息论n控制论等学科n图论已成为我们对现实问题进行抽象的一个强有力的数学工具。n图论在计算学科中的作用越来越大，图论本身也得到了充分的发展。梵天塔问题梵天塔问题n将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，既将整个塔迁移，同时定下3条规则：n每次只能移动一个盘子；n盘子只能在三根柱
5、子上来回移动，不能放在他处；n在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上 64 个个盘盘子子 63 个个盘盘子子 Hanoi Tower递归：解决n个盘子问题的方法，与解决n-1个盘子问题的方法是一样的。Hanoi Towern假定假定每秒移动一次每秒移动一次，一年有，一年有31536000秒，秒，则僧侣们一刻不停地来回搬动，也需要则僧侣们一刻不停地来回搬动，也需要花费大约花费大约5849亿年亿年的时间。的时间。n假定计算机以假定计算机以每秒每秒1000万万个盘子的速度个盘子的速度进行搬迁，则需要花费大约进行搬迁，则需要花费大约58490年年的时的时间。间。n理论上可以计算的
6、问题，实际上并不一理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究定能行，这属于算法复杂性方面的研究内容。内容。证比求易算法证比求易算法(1)(1)n艾述国王向邻国秋碧贞楠公主求婚。公主出了一道题：n求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。n国王回去后立即开始逐个数地进行计算，他从国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因
7、子。国王很快就验证是它的一个真因子。国王很快就验证了这个数确能除尽了这个数确能除尽48 770 428 433 377 171。证比求易算法证比求易算法(2)(2)n国王立即回国，并向时任宰相的大数学国王立即回国，并向时任宰相的大数学家家孔唤石孔唤石求教，大数学家在仔细地思考求教，大数学家在仔细地思考后认为这个数为后认为这个数为17位，则最小的一个真位，则最小的一个真因子不会超过因子不会超过9位，位，n他给国王出了一个主意：按自然数的顺序给他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个给出
8、数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。即上报，赏金万两。顺序算法和并行算法顺序算法和并行算法n国王最先使用的是一种顺序算法，其复杂性表现国王最先使用的是一种顺序算法，其复杂性表现在时间方面，在时间方面，n后面由宰相提出的是一种并行算法，其复杂性表后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。现在空间方面。n直觉上，我们认为顺序算法解决不了的问题完全直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着
9、处理器数目的不断增系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是加而不断提高，从而解决难解性问题，其实这是一种误解。一种误解。n当将一个问题分解到多个处理器上解决时，由于算法中当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。了并行计算机系统的加速能力。第二节 计算机科学研究的主领域n离散结构(DS)n程序设计基础(PF)n算法与复杂性(AL)n体系结构(AR)n操作系统(OS)n网络计算(NC)n程序设计语言(PL)n人机交互(HC)
10、n图形学和可视化计算(GV)n智能系统(IS)n信息管理(IM)n软件工程(SE)n社会和职业的问题(SP)n科学计算(CN)2.1 离散结构（DS）n离散结构列为第一主领域的重要性:既属于学科理论形态方面的内容，又具有广泛的应用价值，为各分支领域提供了强有力的数学工具。n离散结构的主要内容包括集合论，数理逻辑，近世代数，图论和组合数学等。2.2 程序设计基础（PF）n该主领域主要包括程序设计结构，算法，问题求解和数据结构等。nPF的基本问题n对给定的问题，如何进行有效的描述并给出算法n如何正确选择数据结构n如何进行设计，编码，测试和调试程序2.3 算法与复杂性（AL）nAL包括算法分析，算法
11、策略，并行和分布式算法nAL涉及到的理论有并行计算理论，密码学，可计算理论等。n具体的应用比如对并行和分布式算法的实现和测试；对重要问题类的算法的选择，实现和测试；对通用算法的实现和测试，密码协议等。2.4 体系结构（AR）nAR涉及到布尔代数，开关理论，编码理论等基础理论。n具体应用包括超级计算机，快速计算的硬件单元（如算术逻辑单元ALU，高速缓冲存储器Cache）Memory TechnologySRAMCacheDRAMMemory2.5 操作系统（OS）n操作系统涉及到的理论问题有程序行为和存储管理的理论（如存储分配的优化策略），并发理论，调度理论，性能的模型化与分析等。n具体研究问题
12、有分时系统，自动存储分配器，内存管理器，分层文件管理系统和其他作为商业系统基础的重要系统组件，构建OS（如UNIX，DOS，WINDOWS）的技术，建立实用数据库的技术（如编辑器，文件形式程序，编译器，连接器和设备驱动器），文件和文件系统等。2.6 网络计算（NC）n网络计算的理论有数据通信理论，排队理论，密码学，协议的形式化验证等。n网络计算研究的具体问题有网络体系结构，包含在TCP/IP中的协议技术，虚拟电路协议，Internet，实时会议等。2.7 程序设计语言（PL）n计算机语言在本学科占有特殊地位，是计算学科中最富有智慧的成果之一，是程序员与计算机交流的主要工具。n主要内容包括程序设
13、计模式，虚拟机，类型系统，执行控制模型，语言翻译系统，程序设计语言的语义学，基于语言的并行构件等。nPL研究的基本问题包括n语言如何定义机器；机器如何定义语言n什么样的表示法（语义）可以有效地用于描述计算机应该做什么2.8 人机交互（HC）n人机交互的理论有人机通信（含减少人为错误和提高人的生产力的交互模式的心理学研究），涉及到认知心理学，社会交互科学等n具体研究内容包括交互设备（如键盘，语音识别器，盲人学习系统等），有关人机交互的常用子程序库，图形专用语言，原形工具，用户接口的主要形式（如子程序库，专用语言和交互命令），交互技术（如选择，定位，定向，拖动等技术），图形拾取技术，以“人为中心”
14、的人机交互软件的评价标准等。2.9 图形学和可视化计算（GV）nGV主要内容有显示图像的算法，计算机辅助设计（CAD）模型，实体对象的计算机表示，图像处理和加强的方法n涉及到的基本理论有二维和高维几何（包括解析，投影，仿射和计算几何），颜色理论，认知心理学，线性代数，图论等。n具体研究问题包括不同的图形设备上图形算法的实现，不断增多的模型和现象的实验性图形算法的设计与实现，在显示中彩色图的恰当使用，在显示器和硬拷贝设备（指印刷出的纸张，照片等）上彩色的精确再现，图形标准，图形语言和特殊的图形包，不同用户接口技术的实现，CAD系统，图像增强系统等。2.10 智能系统（IS）n智能系统，又称人工智
15、能，研究内容有知识表示，处理知识的方法，自然语言理解和自然语言表示的模型，语音识别与合成，从文本到语音的翻译，推理与学习模型。模仿生物系统的机器体系结构（如神经网络），人类的记忆模型以及自动学习和机器人系统的其他元素等。nIS研究的具体问题有自然语言理解系统，神经网络的实现，国际象棋和其他策略性游戏的程序，语音合成器、识别器，机器人，在小范围领域中使用专家系统的技术，专家系统外壳程序，逻辑程序设计的实现（PROLOG）。2.10 智能系统（智能系统（IS）（）（续）续）n人工智能中的若干哲学问题人工智能中的若干哲学问题n西尔勒的西尔勒的“中文屋子中文屋子”n计算机中的博奕问题计算机中的博奕问题
16、n历史简介历史简介n“深蓝深蓝”与卡斯帕罗夫之战与卡斯帕罗夫之战西尔勒的西尔勒的“中文屋子中文屋子”n美国哲学家约翰美国哲学家约翰西尔勒（西尔勒（J.R.Searle）将有关人工将有关人工智能的研究划分为强人工智能（智能的研究划分为强人工智能（Strong Artificial Intelligence，简称强简称强AI）和弱人工智能（和弱人工智能（Soft Artificial Intelligence，简称弱简称弱AI）两个派别。两个派别。n弱弱AI认为：计算机的主要价值在于它为我们提供了一个认为：计算机的主要价值在于它为我们提供了一个强大的工具；强大的工具；n强强AI的观点则是：计算机不
17、仅是一个工具，形式化的计的观点则是：计算机不仅是一个工具，形式化的计算机是具有意识的。算机是具有意识的。n1980年，西尔勒在年，西尔勒在Behavioral and Brain Sciences杂志上发表了杂志上发表了 Minds、Brains and Programs的的论文，在文中，他以自己为主角设计了一个论文，在文中，他以自己为主角设计了一个“中文中文屋子（屋子（Chinese Room）”的假想试验来反驳强的假想试验来反驳强AI的的观点。观点。电脑博弈传奇电脑博弈传奇n19971997年年5 5月月1111日，日， 人机世纪大战终于降下了人机世纪大战终于降下了帷幕，随着国际象棋世界冠
18、军帷幕，随着国际象棋世界冠军卡斯帕罗夫卡斯帕罗夫败败给了给了IBMIBM公司的一台机器公司的一台机器 “深蓝深蓝” , ,全世界全世界都永远不会忘记那震惊世界的都永远不会忘记那震惊世界的9 9天天的的“搏杀搏杀”。n卡斯帕罗夫卡斯帕罗夫在在19881988年曾说过，年曾说过，20002000年前电脑年前电脑绝不会战胜特级象棋大师，虽然卡斯帕罗夫绝不会战胜特级象棋大师，虽然卡斯帕罗夫也承认，电脑有可能击败一般的特级大师，也承认，电脑有可能击败一般的特级大师，但是他斩钉截铁地强调指出：但是他斩钉截铁地强调指出：“不包括卡尔不包括卡尔波夫和我！波夫和我！”卡斯帕罗夫卡斯帕罗夫n1963.4.13 1
19、963.4.13 出生于阿塞拜疆的首都巴库。出生于阿塞拜疆的首都巴库。n19801980年他获得世界少年组冠军，年他获得世界少年组冠军，n19811981年他并列夺得苏联冠军，随后他又在一系列年他并列夺得苏联冠军，随后他又在一系列的国际大赛里频频夺冠。的国际大赛里频频夺冠。 n19841984年他一路过关斩将赢得向当时的世界年他一路过关斩将赢得向当时的世界冠军卡尔波夫挑战的资格。冠军卡尔波夫挑战的资格。n19851985年年2222岁的卡斯帕罗夫成为历史上最年轻的岁的卡斯帕罗夫成为历史上最年轻的国际象棋冠军。国际象棋冠军。n从那以后连续三次击败俄罗斯的卡尔波夫，分别从那以后连续三次击败俄罗斯的
20、卡尔波夫，分别各一次击败英国的肖特和印度的阿南德，捍卫了各一次击败英国的肖特和印度的阿南德，捍卫了自己的冠军头衔。自己的冠军头衔。 许峰雄许峰雄n许峰雄设计的第一台能下棋的电脑叫许峰雄设计的第一台能下棋的电脑叫“蕊验蕊验”。n19871987年，他设计的电脑在与其它电脑的角逐中年，他设计的电脑在与其它电脑的角逐中获得冠军，获得冠军，n19881988年，他把年，他把“蕊验蕊验”电脑升级为电脑升级为“深思深思”，首次战胜了国际象棋特级大师本特首次战胜了国际象棋特级大师本特拉尔森，拉尔森，赢得电脑界同行一片喝彩声。赢得电脑界同行一片喝彩声。n19891989年，许峰雄和他的两名助手带着有年，许峰雄
21、和他的两名助手带着有250250多多个芯片个芯片，每秒能计算，每秒能计算750750万步棋万步棋的的“深思深思”电电脑，来到脑，来到IBMIBM公司设在纽约的电脑研究中心公司设在纽约的电脑研究中心Deep blue Deep blue n19951995年，年，“学名学名”为为“IBM AS/6000 SPIBM AS/6000 SP大规模多用途大规模多用途并行处理机并行处理机”正式诞生，计算速度达到了正式诞生，计算速度达到了每秒钟每秒钟1 1亿亿棋棋步。步。n最大特点是最大特点是3232个处理器采用个处理器采用“并行处理并行处理”的方式解决复杂的方式解决复杂问题。问题。Deep-BlueDe
22、ep-Bluen19961996年年2 2月，月， 在美国费城，许峰雄指挥在美国费城，许峰雄指挥“深蓝深蓝”与卡斯帕罗夫再次交锋。与卡斯帕罗夫再次交锋。n卡斯帕洛夫到底不愧为卡斯帕洛夫到底不愧为“有史以来最伟大的棋有史以来最伟大的棋手手”，他稳扎稳打，以，他稳扎稳打，以3 3胜胜2 2平平1 1负的战绩再次战负的战绩再次战胜了电脑。胜了电脑。n双方作战的过程十分艰难，许峰雄从双方作战的过程十分艰难，许峰雄从“深蓝深蓝”的进步的进步中看到了曙光。中看到了曙光。n在以后的一年里，许峰雄和另外四位电脑科学家在以后的一年里，许峰雄和另外四位电脑科学家决心给电脑输入了近两百万局国际象棋程序，再决心给电脑
23、输入了近两百万局国际象棋程序，再次提高了它的运算速度，使它每秒能分析次提高了它的运算速度，使它每秒能分析2 2亿步棋亿步棋。由国际象棋特级大师由国际象棋特级大师本杰明本杰明为它当为它当“陪练陪练”，找，找出某些棋局的弱点，然后再修改程序。出某些棋局的弱点，然后再修改程序。Deep-Bluen棋盘一侧是卡斯帕罗夫，棋盘的棋盘一侧是卡斯帕罗夫，棋盘的另一侧是许峰雄博士另一侧是许峰雄博士n许峰雄将通过另一台带有液晶显示许峰雄将通过另一台带有液晶显示屏的黑色电脑，负责操纵屏的黑色电脑，负责操纵“深蓝深蓝”迎战人类世界冠军。迎战人类世界冠军。2.11 信息管理（IM）n信息管理的内容包括表示数据的逻辑结
24、构和数据元素之间关系的模型（如ER模型，关系模型，面向对象模型），为快速检索的文件表示（如索引），保证更新时数据库完整性的方法，防止非授权泄露或更改数据的方法，对不同类信息检索系统和数据库（如超文本，文本，空间的，图像的，规则集）进行查询的语言，允许文档在多个层次上包含文本，视频，图像和声音的模型（如超文本），人的因素和接口问题。nIM的基本理论有关系代数，关系演算，数据依赖理论，并发理论，统计推理，排序与搜索，性能分析以及支持理论的密码学。2.11 信息管理（IM）（续）nIM研究的具体问题如关系，层次，网络，分布式和并行数据库的设计技术；信息检索系统的设计技术，安全数据库系统的设计技术，超
25、文本系统的设计技术，把大型数据库映射到磁盘存储器的技术，把大型的只读数据库映射到光存储介质上的技术。数据库的地位n数据库技术产生于六十年代末，是数据管理的最新技术，是计算机科学的重要分支n数据库技术是信息系统的核心和基础，它的出现极大地促进了计算机应用向各行各业的渗透n数据库的建设规模、数据库信息量的大小和使用频度已成为衡量一个国家信息化程度的重要标志数据模型n在数据库中用数据模型这个工具来抽象、表示抽象、表示和处理和处理现实世界中的数据和信息。通俗地讲数据模型就是现实世界的模拟n数据模型应满足三方面要求n能比较能比较真实真实地模拟现实世界地模拟现实世界n容容易易为人所为人所理解理解n便于在计
26、算机上便于在计算机上实现实现层次数据模型 1 根结点根结点 2 兄弟结点兄弟结点 3 叶结点叶结点 4 兄弟结点兄弟结点 5 叶结点叶结点 叶结点叶结点层次模型是数据库中最早出现的层次模型是数据库中最早出现的 数据模型。是一个以记录型为结点的有数据模型。是一个以记录型为结点的有根的定向树或森林。用节点表示一个记录类型，用树形结构表示实体类型根的定向树或森林。用节点表示一个记录类型，用树形结构表示实体类型及实体间的联系，结点是实体，连线表示实体和实体之间的关系。这种关及实体间的联系，结点是实体，连线表示实体和实体之间的关系。这种关系只能是一对多的关系。该树的特点是：根结点只有一个，根结点以外的系
27、只能是一对多的关系。该树的特点是：根结点只有一个，根结点以外的各结点有且只有一个父结点，但一个父结点可对应多个子结点。该模型具各结点有且只有一个父结点，但一个父结点可对应多个子结点。该模型具有层次分明、结构清晰的优点，它适用于描述客观存在的事物中有主次之有层次分明、结构清晰的优点，它适用于描述客观存在的事物中有主次之分的结构。其特点是只能反映一对多的关系分的结构。其特点是只能反映一对多的关系。典型的层次数据库系统IMS数据库管理系统n第一个大型商用第一个大型商用DBMSn1968年推出年推出nIBM公司研制公司研制网状数据模型 1 2 R3 L1 L2 R1 R1 R2R2 L3L3 L1 L
28、2 L1 L2 R3R3 L4L4 R4 R4 R5R5 网状模型是以记录型为结点的网络，它反映现实世界中较为复杂的网状模型是以记录型为结点的网络，它反映现实世界中较为复杂的事物之间的联系。网状数据模型的数据结构是：允许有一个以上的结事物之间的联系。网状数据模型的数据结构是：允许有一个以上的结点无父结点，一个子结点可以有多个父结点，且两个结点之间可以有点无父结点，一个子结点可以有多个父结点，且两个结点之间可以有两种或多种联系。可见，网状模型可以直接描述多对多的关系，可以两种或多种联系。可见，网状模型可以直接描述多对多的关系，可以用丛结构表示实体类型和实体间联系用丛结构表示实体类型和实体间联系。
29、典型的网状数据库系统nDBTG系统，亦称CODASYL系统n由由DBTG提出的一个系统方案提出的一个系统方案n奠定了数据库系统的基本概念、方法和技术奠定了数据库系统的基本概念、方法和技术n70年代推出年代推出n实际系统nCullinet Software Inc.公司的公司的 IDMSnUnivac公司的公司的 DMS1100nHoneywell公司的公司的IDS/2nHP公司的公司的IMAGE关系模型n最重要的一种数据模型。也是目前主要采用的数据模型n1970年由美国IBM公司San Jose研究室的研究员E.F.Codd提出关系数据模型的数据结构 n在用户观点下，关系模型中数据的逻辑结构是
30、一张二维表，它由行和列组成。学学生生登登记记表表学学 号号姓姓 名名年年 令令性性 别别系系 名名年年 级级95004王王小小明明19女女社社会会学学9595006黄黄大大鹏鹏20男男商商品品学学9595008张张文文斌斌18女女法法律律学学95典型的关系数据库系统nORACLEnSYBASEnINFORMIXnDB/2nCOBASEnPBASEnEasyBasenDM/2nOpenBase2.12 软件工程（SE）n软件工程指的是一种过程，一种大型软件设计的总体方法与步骤体系。nSE的内容有程序开发自动化方法，可靠计算的方法学，软件工具与程序设计环境，程序和系统的测度与评价，软件系统到特定机
31、器的相匹配问题域，软件研制的生命周期模型。2.12 软件工程（SE）（续）nSE的主要理论有程序验证与证明，可靠性理论等。nSE具体的设计问题有版本修改系统，面向语法的编辑器，行编辑器，屏幕编辑器和字处理系统，实际使用并受到支持的特定软件开发方法，测试的过程与实践（如遍历，手工仿真，模块间接口的检查），质量保证与工程管理，程序开发和调试，成形，文本格式化和数据库操作的软件工具，安全计算系统的标准等级与确认过程的描述，用户接口设计，可靠，容错的大型系统的设计方法，“以公众利益为中心”的软件从业人员认证体系。2.13 社会和职业的问题（SP）n该领域中价值观，道德观属于技术评估方面的内容，知识产权
32、属于技术保护方面的内容。n主要内容包括计算的历史，计算的社会背景，分析方法和工具，专业和道德责任，基于计算机系统的分线与责任，知识产权，隐私与公民的自由，计算机犯罪，与计算有关的经济问题，哲学框架等。n该领域基本问题包括计算学科本身的文化，社会，法律和道德的问题；有关计算的社会影响问题，以及如何评价可能的一些答案的问题；哲学问题。2.14 科学计算（CN）n科学计算涉及的理论包括物理问题的数学模型（连续或离散）的形式化表示，连续问题的离散化技术，线性代数，数值分析及支持领域的微积分，实数分析，复数分析和代数等。n科学计算的具体内容包括用于线性代数的函数库与函数包，常微分方程，统计，非线性方程和
33、优化的函数库与函数包。第三节 计算机科学中的核心概念n算法n数据结构n程序n软件n硬件算法n算法的定义和特征n一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列 。n有穷性、确定性、输入、输出、能行性n算法实例n算法的表示方法n算法分析数据结构n数据结构的基本概念n数据结构的组成n数据逻辑结构的形式化定义n数据的存储结构n数据结构的基本运算内容常用的几种数据结构n线性表n数组n树和二叉树n图程序n这里的程序是指计算机程序。n计算机程序就是按照工作步骤事先编排好的，具有特殊功能的指令序列。软件n计算机软件一般指计算机系统中的程序和文档，也可以指在研究，开发，维护
34、，以及使用软件所涉及的理论，方法，技术所构成的分支学科。n一般软件分为系统软件，支撑软件和应用软件三类。硬件n计算机硬件指构成计算机系统的所有物理器件，部件，设备，以及相应的工作原理与设计，制造，检测等技术的总称。n硬件系统的物理元器件n硬件系统的部件和设备n硬件系统的工程技术我国自主研发的芯片第四节 计算学科本质及根本问题n计算学科的本质n计算学科的本质，也就是计算的本质。图灵用形式化方法成功地表述了计算这一过程的本质。直观地说，所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过
35、程。n计算学科的根本问题n即什么能被(有效地)自动进行计算学科的未来n计算学科能否持续兴旺下去？或者是否会在我们的下一代衰落下去？n 一个学科的兴旺取决于它存不存在(或能否涌现)大量的科学问题，如果该学科的科学问题已基本解决，则这个学科就面临衰落的可能，否则，它将因为不断涌现的科学问题而继续兴旺下去。n人类的发展历史就是一个不断提出问题和解决问题的历史。以上列举了计算学科各主领域需要解决的大量基本问题和一些富有挑战性的科学问题，只要这些富有挑战性的科学问题没有得到彻底解决，那么这个学科还将持续兴旺地发展下去。计算学科是工科还是理科 n计算学科是“工科”还是“理科”的问题是一个长期以来一直困扰计
36、算机界的问题。这个问题在计算作为一门学科报告中得到阐明。n计算作为一门学科报告给出了一个计算学科的二维定义矩阵，使得学科各主领域中有关抽象、理论和设计3个形态的核心内容完整地呈现出来，该二维定义矩阵是对学科的一个高度概括和总结。“工科“ VS “理科“n3个学科形态的内容以及学科的根本问题都清楚地表明：计算机科学和计算机工程在本质上没有区别，学科中的抽象、理论和设计要解决的都是计算中的“能行性”和“有效性”的问题。n相对而言，计算机科学注重理论和抽象，计算机工程注重抽象和设计，计算机科学和工程则居中。因此，不能简单地将计算学科归属于“理科”还是“工科”。n在统一认识之后，ACM和IEEE-CS任务组将计算机科学、计算机工程、计算机科学和工程、计算机信息学以及其他类似名称的专业及其研究范畴统称为计算学科。程序设计在计算学科中的地位n计算学科所包括的范围要远比程序设计大得多n例如：硬件设计、系统结构、操作系统结构、应用系统的数据库结构设计，以及模型的验证等。内容覆盖了计算学科的整个范围，但是这些内容并不是程序设计。n正确地位：程序设计是计算学科课程中固定练习的一部分，是每一个计算学科专业的学生应具备的能力，是计算学科核心科目的一部分。并且，程序设计语言还是获得计算机重要特性的有力工具。
