计算机导论教材课件.ppt

,计 算 机 导 论,第12章 计算机科学与技术学科课程体系结构,第12章计算机科学与技术学科课程体系结构,教学目标掌握计算机科学与技术学科的基本内容掌握计算机科学理论 的组成掌握计算机科学与技术学科的课程体系结构 了解计算机科学与技术学科基础课程 了解计算机科学与技术学科各专业方向课程群,第12章计算机科学与技术学科课程体系结构,12.1 学科介绍12.2 课程体系结构,12.1 学科介绍,计算机科学与技术学科涉及到的基本内容有计算机科学理论、计算机组织与体系结构、计算机软件、计算机硬件、计算机应用技术、人工智能六个方面。计算机科学与技术学科有十四个主要分支领域：（1）离散数学DS；（2）程序设计基础PF；（3）算法与复杂性AL；（4）体系结构AR；（5）操作系统OS；（6）网络计算NC；（7）程序设计语言PL；（8）人机交互HC；（9）图形学和可视化计算GV；（10）智能系统IS；（11）信息管理IM；（12）软件工程SE；（13）社会和职业的问题SP；（14）科学计算CN。,计算机科学与技术学科的发展以高性能、网络化、智能化以及微型化等为主要方向，其中，计算机科学理论、计算机系统结构和软件为主流方向。计算机科学理论是研究计算机基本理论的学科。计算机科学理论主要包括自动机论、形式语言理论、程序理论、算法分析及计算复杂性理论等。,12.1 学科介绍,12.1.1 学科的产生 12.1.2 理论计算机科学12.1.3 形式语言理论12.1.4 程序设计理论12.1.5 算法分析和计算复杂性理论,12.1.1 学科的产生,为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。,12.1.2 理论计算机科学,理论计算机科学主要包括：自动机论与形式语言理论；程序理论（包括程序正确性证明、程序验证等）；形式语义学；算法分析和计算复杂性理论。,12.1.3 形式语言理论,形式语言理论源于数理语言学中的乔姆斯基理论。在这种理论中，形式语言分为四种：0型语言:短语结构语言，每个0型语言都是递归可枚举集1型语言:又名上下文有关语言2型语言:又名上下文无关语言3型语言:又名正则语言,12.1.4 程序设计理论,程序设计理论包括程序正确性证明和程序验证 40年代后期诺伊曼,诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。E.W.戴克斯特拉在70年代中期曾指出的，实际有效的方法是边设计边验证，在设计完毕时证明或验证的过程也同时结束。,J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。图灵在1947年的一篇论文中，提出借助定理证明的方法来设计程序。60年代以来研究工作者提出几种不同的语义理论，主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学在程序正确性证明和形式语义学中应用的程序逻辑，是60年代末发展起来的。,12.1.5 算法分析和计算复杂性理论,一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论原是可计算理论的一支，是以各种可计算函数(即递归函数)的计算复杂性为其研究对象的。,12.2 课程体系结构,12.2.1 学科基础课程12.2.2 专业方向课程群,12.2.1 学科基础课程,计算机导论 程序设计基础 离散数学算法与数据结构计算机组成原理操作系统,数据库系统原理编译原理软件工程计算机网络数字逻辑,（1）计算机导论,为计算机专业的新生提供一个关于计算机学科的入门介绍，使他们能对该学科有一个整体的认识，并了解该专业的学生应具有的基本知识和技能以及在该领域工作应有的职业道德和应遵守的法律准则。本课程为计算机专业的学生提供一个关于计算机科学学科的入门介绍，使他们能对该学科有一个整体的认识，提高他们学习本专业的兴趣。除了技术之外，还要注意讲授学科内涵和该专业学生应有的职业道德。,（2）程序设计基础,本课程既培养学生解决问题（算法与程序设计）的能力,又使他们比较熟练地掌握一种程序设计语言。应注意介绍独立于任何特定编程语言的算法概念和结构，强化训练程序设计的经验和相关技术。重点是程序设计实践及培养学生分析问题和解决问题的能力训练。先修课程：计算机导论。本课程介绍程序设计的基本概念，强调算法的重要性及其在程序设计中的作用。注意强调算法而不是语法细节。讲授程序设计语言的重点可以考虑用传统的过程式语言，也可用面向对象语言；事实上，使用面向对象语言介绍程序设计时，常常需要从这些语言的过程性语句开始。应注意使这门课程同面向对象的程序设计课程有所区别。在本课程中，对控制语句的讨论应先于对类、子类和继承等概念的讨论。,（3）离散数学,离散数学是计算机科学的基础内容。计算机的许多领域都要用到离散数学中的概念。离散数学包括了集合论、数理逻辑、图论和组合数学的重要内容。形式的数学证明贯穿此课程。数据结构和算法中有大量离散数学的内容。例如，在形式说明、验证、密码学中都需要有理解形式证明的能力。图论的概念被用于计算机网络、操作系统和编译原理等领域。集合论的概念被用在软件工程和数据库中。随着计算机科学的日益成熟,越来越多的分析技术被用于实践。为了理解将来的计算技术,学生需要对离散数学有深入的理解。先修课程：数学分析或高等数学。,（4）算法与数据结构,介绍常用的数据表示和处理技术，包括顺序存储和链接存储的线性表、栈和队列的表示和操作；字符串的模式匹配算法；插入排序、选择排序、快速排序等常见的内部排序方法；顺序存储的数组的地址计算方法；树的存储结构、遍历和线性表示；二叉树的遍历、存储和查找；穿线树和穿线排序；查找树、平衡树、Huffman算法、B树等常见树的表示和有关算法；图的表示、遍历及应用。先修课程：高级语言程序设计、离散数学。,（5）计算机组成原理,以冯诺依曼计算机模型为出发点，介绍计算机的组织结构和工作原理，剖析计算机的运算器、存储器、控制器和输入输出设备的结构、工作原理与相互关系。先修课程：计算机导论、数字逻辑。,（6）操作系统,介绍操作系统的设计和实现，包括操作系统各组成部分的概述，互斥性和同步性，处理器实现，调度算法，存储管理，设备管理和文件系统。先修课程：算法与数据结构、计算机组成基础。,（7）数据库系统原理,介绍数据库系统的基本概念、原理、方法及应用，主要包括数据库系统概论（数据库技术的发展、数据模型、数据库体系结构等；关系数据模型、数据库查询语言SQL、函数依赖及关系规范化理论）；数据库管理系统实现技术（事务、并发控制、恢复、完整性和安全性等概念及有关实现机制）；数据库存储结构（文件组织、索引、散列技术等）；其他类型的数据库系统介绍（分布式数据库、面向对象数据库、对象关系数据库及数据库技术发展趋势等）。先修课程：数据结构与算法、离散数学。,（8）编译原理,介绍编译原理的理论和实践，包括编译程序设计，词法分析，语法分析，符号表，声明和存储管理，代码生成以及优化技术。先修课程：程序设计、离散数学、算法与数据结构。本课程有两个不同的但有联系的目标。第一，它研究了语言翻译的理论。第二，它展示了怎样应用这个理论去建立编译器、解释器和编译器生成程序。,（9）软件工程,介绍软件工程的概念、技术和方法，包括软件的开发模型、软件项目管理、软件质量度量、可行性分析、需求分析、软件设计、编码、测试、维护；面向数据流的分析与设计方法、面向数据结构的分析与设计方法、面向对象的分析与设计方法；对软件重用、快速原型技术作简要的介绍。先修课程：程序设计、算法与数据结构,（10）计算机网络,介绍数据通信的基本概念和计算机网络的基本原理，包括计算机网络的体系结构、数据通信的基本方法和协议、计算机网络的主要应用协议；同时介绍计算机网络系统的安全和管理知识，使学生对数据通信和计算机网络有一个全面理解。先修课程：计算机导论、计算机组成、操作系统、算法与数据结构。,（11）数字逻辑,本课程作为电路设计的基础课程，介绍数字系统设计的基本方法，包括数制与码制、逻辑代数、组合电路的分析与设计、时序电路的分析与设计以及逻辑门陈列等知识。先修课程：计算机导论。,12.2.2 专业方向课程群,软件应用开发方向硬件应用开发方向网络技术应用方向研究生入学考试方向,（1）软件应用开发方向,软件应用开发主要包括编程基础算法与复杂性编程语言网络技术及应用人-机交互图像处理与可视计算智能系统信息管理软件工程,编程基础,主要内容包括程序设计结构，算法，问题求解和数据结构等。它考虑的是如何对问题进行抽象。它属于学科抽象形态方面的内容，并为计算学科各分支领域基本问题的感性认识(抽象)提供方法。,算法与复杂性,主要内容包括算法的复杂度分析，典型的算法策略，分布式算法，并行算法，可计算理论，P类和NP类问题，自动机理论，密码算法以及几何算法等。,编程语言,主要内容包括程序设计模式，虚拟机，类型系统，执行控制模型，语言翻译系统，程序设计语言的语义学，基于语言的并行构件等。,网络技术及应用,主要内容包括计算机网络的体系结构，网络安全，网络管理，无线和移动计算以及多媒体数据技术等。,人-机交互,主要内容包括以人为中心的软件开发评价，图形用户接口设计，多媒体系统人机接口等。,图像处理与可视计算,主要内容包括计算机图形学，可视化，虚拟现实，计算机视觉等。,智能系统,主要内容包括约束可满足性问题，知识表示和推理，Agent，自然语言处理，机器学习和神经网络，人工智能规划系统和机器人学等。,信息管理,主要内容包括信息模型与信息系统，数据库系统，数据建模，关系数据库，数据库查询语言，关系数据库设计，事务处理，分布式数据库，数据挖掘，信息存储与检索，超文本和超媒体，多媒体信息与多媒体系统，数字图书馆等。,软件工程,主要内容包括软件过程，软件需求与规格说明，软件设计，软件验证，软件演化，软件项目管理，软件开发工具环境，基于构件计算，形式化方法，软件可靠性，专用系统开发等。,（2）硬件应用开发方向,硬件应用开发主要包括:电子技术数字逻辑计算机组成原理微机原理与接口技术汇编语言嵌入式系统,电子技术,主要内容包括电路分析基础、模拟电子技术、数字电子技术等。,数字逻辑,主要内容包括数值与码制、逻辑代数及逻辑函数化简、基本逻辑电路及触发器、各种集成组合电路的设计与应用、同步时序电路与异步时序电路的设计与分析、集成化时序电路、逻辑电路的参数、集成化存储电路等。,计算机组成原理,主要内容包括计算机的发展概况、系统结构、数据的表示方法及其主要部件、内部的指令系统和存储系统、输入输出设备的结构和工作原理、CPU与外设间传送数据的控制方法。,微机原理与接口技术,主要内容包括微处理器的组成原理、体系结构、常用总线、存储器的组成以及外围接口电路，多功能外围芯片、输入输出设备的功能、工作原理及接口电路等。,汇编语言,主要内容是阐述IBM PC及其兼容机上汇编语言程序设计的方法和技术。包括IBM PC机的指令系统和寻址方式、子程序结构、输入输出程序方法、BIOS和DOS系统功能调用等程序设计技术。,嵌入式系统,围绕目前流行的32位ARM处理器和源码开放的Linux操作系统，讲述嵌入式系统的概念、软硬件组成、开发过程以及嵌入式Linux应用程序和驱动程序的开发设计方法。本课程的知识将为学生今后从事嵌入式系统研究与开发打下坚实的基础。,（3）网络技术应用方向,网络应用方向主要培养掌握计算机网络应用知识，能熟练地开发网络应用软件，构建和管理网络，具备较全面地解决实际问题的能力。课程体系包括如下内容：网络基础知识 网络软件开发 交换技术 网络安全技术技术,网络技术课程体系,网络基础知识包括TCP/IP协议、OSI模型及FTP、DNS服务器设置、组网技术、交换机及路由器的连接方式、基本配置等。网络软件开发包括ASP/JSP开发技术，能够独立开发网络版管理系统（如新闻发布）。交换技术包括交换机的VLAN、STP、RSTP高级配置技术，路由器的RIP和IP访问列表、NAT高级配置技术等。网络安全技术技术包括防火墙原理、防火墙应用、入侵检测等。,（4）研究生入学考试方向,研究生入学考试的专业课程主要包括:计算机组成原理程序设计基础算法与数据结构操作系统数据库系统原理,计算机组成原理,主要学习以下内容：数值的机器表示；定点数与浮点数表示，校验码；原码和补码并行乘法的电路实现，定点数的除法，并行除法电路的实现，ALU运算器的基本结构与工作原理，浮点数运算及浮点数运算器的实现；存储系统和结构；指令系统与中央处理器；IO接口与外围设备；总线等。,程序设计基础,主要学习以下内容：程序设计介绍；算法与问题求解；问题求解策略；问题求解过程中算法的角色；算法实现策略；变量；操作符；控制结构；条件结构；迭代循环结构；函数；调试；错误类型；调试技术；指针和数组；递归的概念；递归的数学函数描述；简单的递归过程；分治法策略；递归的回归；递归的实现；面向对象程序设计：面向对象设计；封装和信息隐蔽；行为和实现分离；类，子类和继承；多态性；类层次；类的聚集和反复协议。,算法与数据结构,主要学习以下内容：算法、算法的时间复杂度和空间复杂度，最坏和平均的时间复杂度等概念；算法描述和算法分析方法；常用算法设计方法；迭代法、穷举搜索法、递推法、算法的递归描述技术、回溯法、贪婪法、分治法；数据结构、数据类型、抽象数据类型、信息隐藏、线性表；线性表的存储结构；树型结构及其应用；图及其应用；常用排序算法：线性表上的查找、树的查找、散列技术；文件。,操作系统,主要学习以下内容：操作系统的地位和目的；操作系统的发展历史；一个典型操作系统的功能；设计问题；结构模型；抽象；进程和资源；应用程序接口；设备组织；中断；用户态和系统态的转换；并发性；并发执行的概念；状态和状态图表；实现结构；调度和上下文转换；并发环境中的中断处理；互斥；互斥问题的定义；死锁检查和预防；解决策略；模型和机制；抢占和非抢占调度；调度策略；进程和线程；物理存储回顾和存储管理硬件；涵盖技术，交换技术和划分技术；分页和分段；页面替换和替换策略；工作集和系统失效；高速缓存；虚拟存储技术；设备管理；串行设备和并行设备的特点；抽象设备区分；缓冲存储策略；直接存储器存取；错误恢复；文件系统；基本概念；目录的内容和结构；文件系统技术；存储映射文件；专用的文件系统；命名，搜索和存取；备份策略；系统安全概述；机制隔离；安全的保障方法和设备；保护，存取和认证；保护模式；加密技术；实时系统和嵌入式系统；作业控制等。,数据库系统原理,主要学习以下内容：不同类型数据资源的管理；商业前景；信息和数据库系统的历史和发展动力；信息存储和检索；信息管理应用软件；信息获取和表示；分析和索引；链接和导航；信息的隐私性，完整性，安全性和保存；可扩展性，效率和效力；数据库系统的构成要素；数据库管理系统（DBMS）的功能；数据库体系结构和数据独立性；信息模型和系统；数据建模；概念模型；面向对象模型；关系模型；关系演算；例子；SQL；查询优化；嵌入过程语言中的非过程查询；对象查询语言简介；建立数据库的基础方法学；数据库特有的问题；关系数据库设计；函数依赖；存储器和文件结构；索引文件；散列文件；签名文件；B树；密集索引；变长记录文件；数据库的效率和调节；事务处理；错误和恢复；并发控制；分布式数据库：分布式数据存储；分布式查询处理；分布式事务模型；并发控制；同构和异构解决方案；客户服务器结构；信息系统的设计、开发和进化；安全和控制；特定用途的信息系统，包括局域网和外部网；信息检索；数据库新技术介绍。,