计算机与算法初步.ppt

《计算机与算法初步.ppt》由会员分享，可在线阅读，更多相关《计算机与算法初步.ppt（76页珍藏版）》请在三一文库上搜索。

1、计算机与算法初步,北京工业大学计算机学院 软件学科部 宋凯 教案下载：http:/172.21.14.209/网上教学/ E-mail：,教学目的和任务,将初步建立起计算机系统的概念，了解计算机的基本原理、特点，了解与计算机技术有关的重要概念；初步明确今后在学习专业时，各门课程的地位和作用。,将通过介绍算法及C语言的初步，能够掌握结构化程序设计方法，解决如何制定求解问题的算法，及算法描述方法，养成良好的程序设计风格。,为学好高级语言的程序设计及专业课的学习创造条件。,教学安排,总学时:48 上课：32学时 星期一 7-8节（2-6周） 1-401 星期四 1-2节（3-5,10-17周） 1-

2、414 上机：16学时 星期一 3-4节(10-14周) 信南510,512室 星期三 1-2节（4-6周） 信南206(微机1室),引言,计算机：现代化的信息处理工具 处理信息提供结果（输出） 结果取决于它接收到的信息（输入）和处理算法 计算机科学技术 研究计算机的设计与制造 利用计算机进行信息获取、表示、储存、处理和控制的理论、原则、方法和技术的学科,引言,计算机产业 将科学技术成果转化为商品 为商品提供开发、生产、销售、服务、培训的产业 相互关系 计算机是计算机科学技术的研究对象、是计算机产业的商品 计算机产业是计算机与计算机科学技术的依托 计算机科学技术是计算机与产业发展的生命源泉,第

3、一章 计算机基础知识,计算机的基本结构 计算机软件 计算机应用技术 操作系统 程序设计语言 参考书： 计算机文化基础教程，冯博琴著，清华大学出版社 计算机文化，朱海滨等译，机械工业出版社,1.1 计算机的基本结构,计算机系统由硬件系统和软件系统组成 硬件(Hardware) 构成计算机系统的物质元器件、部件、设备，以及它们的工程实现（设计、制造和检测技术） 软件(Software) 计算机系统中的程序及其文档，及其研究、开发、维护所涉及的理论、方法和技术。,计算机组成结构,计算机组成（1/2）,输入设备（输入单元） 负责接收信息：键盘、鼠标、手写板 输出设备（输出单元） 负责输出信息：显示器、

4、打印机 内存（主存、内存单元） 存取速度快的存储器，保存信息 停电则失去记忆 外存（二级存储单元） 大容量存储、存取速度较慢 光盘和磁盘（硬盘、软盘、闪盘） 可长期保存信息,计算机组成（2/2）,运算器（算术逻辑单元） 负责算术运算、逻辑运算（二进制） 控制器 控制管理各个单元的工作（控制输入、输出、存储器访问、计算请求） 中央处理单元（CPU） CPU = 运算器+控制器+处理总线,主机与外部设备,主机 中央处理器（CPU） 存储器（内存、硬盘） 驱动器（软驱、硬驱、光驱） 外部设备 打印机、显示器、绘图仪 摄象机、键盘、鼠标等,计算机的分类,按照规模和性能分类 微型计算机、工作站、小型计算

5、机、中型计算机、大型计算机和巨型计算机 界限趋于模糊 按照用途分类 通用机 特定场合：服务器、嵌入式计算机 专用机 特殊功能：过程控制、抗恶劣环境、数据流、逻辑推理、生物计算、量子计算,主要指标（1/2）,计算机字长 直接参与运算的二进制位数 （常见：32位=1个字） CPU 运算速度 CPU 主频（如：1.8GHz） MIPS（每秒执行百万指令数） 显示器 屏幕尺寸：常用15英寸、17英寸 点距（毫米）、最大分辨率：800*600， 1024*768 显示内存,主要指标（2/2）,存储器容量（存储单元的个数） 每个单元：一个字节byte（8个二进制数bit） 1TB = 1024 * GB

6、1GB = 1024 * MB 1MB = 1024 * KB 1KB = 1024 个字节 地址：内存单元的编号 32位二进制数（常见） 支持信息的存取,微型计算机的启动,冷启动 打开电源开关或按复位按钮 系统自动运行系统引导程序 随后启动操作系统 热启动 同时按下 Ctrl + Alt + Del 三键 常用于机器故障（死机）时,信息处理过程,计算机的信息处理过程 按照给定的处理算法接收输入信息，完成计算，产生输出结果 信息处理的实现 计算机负责将程序翻译成描述处理算法的指令序列，发送给控制器，指挥运算器，协调各个硬件单元，完成指定的信息输入、各种运算和信息输出 技术人员负责根据处理需求，

7、设计计算机程序，来描述处理算法,指令系统,指令（Instruction）： 要求计算机执行某个操作的命令 机器指令 控制器能够识别与执行的操作命令 代表该操作的二进制数 计算机控制的最小单位 指令系统 计算机可以识别的全部指令 各种计算机的指令系统不同,指令的种类,数据传送类指令 算术运算与逻辑运算类指令 程序控制类指令（转移指令等） 输入输出类指令 控制和管理计算机的指令 （停机、启动、复位等） 信息处理算法由指令序列（程序）实现,指令系统决定了计算机的能力，也影响着计算机的体系结构。,工作原理（存储程序概念）,1. 利用存储器（内存）来存放要执行的指令序列； 2. 中央处理器（CPU）依次

8、从内存读出程序中的每条指令 3. 分析和执行指令 4. 直至完成全部指令任务。,从存储器取一条指令,执行指令,是停止指令?,程序执行过程,程序执行的流程就是“取指-分析-执行”的循环过程。,否,是,分析该条指令,程 序,结束,存储程序概念(续),存储程序概念决定了计算机的结构（冯.诺依曼） 指令和数据都保存在内存中 程序确定了计算机的用途 程序设计是计算机技术的基本技能,冯诺依曼计算机模型的基本要点:, 采用二进制形式表示数据和指令 采取“存储程序”工作方式 计算机硬件部分由五大部件组成,即运算器、控制器、存储器、输入设备和输出设备. 到目前为止，各种类型的计算机都属冯.诺依曼计算机。,1.2

9、 计算机软件,软件：Computer Software 计算机系统中的程序、数据和文档 用户和硬件的接口 程序 计算任务的处理对象和处理规则的描述 可执行程序：指令序列 数据和文档 程序的说明资料；保存在二级存储器（外存）上。,软件分类,系统软件 管理、监控和维护计算机软硬件资源 支撑软件 支撑软件开发与维护的软件 应用软件 特定应用领域专用的软件,系统软件,操作系统 管理软硬件资源（MS DOS, WINDOWS） 编译系统 计算机语言处理（C/C+语言、Java语言。） 数据库管理系统 数据维护和管理（Oracle, SQL Server 。） 网络软件 网络操作系统、网络管理软件 其他系

10、统软件 系统引导程序 基本输入输出程序（BIOS） 设备驱动程序（打印机、显示卡、网卡。）,支撑软件和应用软件,支撑软件 软件开发环境、软件工具、应用服务器 例如C语言：Turbo C，Visual C/C+ 网页制作软件 应用软件 办公软件：文字处理（WORD）、表格处理（Excel）、演示文稿（PowerPoint） 管理信息系统、图象处理 电子商务、电子政务、数字地球,在不同的系统软件环境下开发的应用程序要在不同的系统软件下运行。,程序运行方式,可执行程序 二进制的指令序列，保存在二次存储器（硬盘）中 程序启动 自动：系统引导、操作系统 手动：应用软件、支撑软件 运行过程 1. 将可执行

11、程序装入到内存中 2. 逐条解释执行各指令（数据存取、计算、控制转移） 3. 直到遇到终止指令,1.3 操作系统概要,Operating System 用途 管理硬件资源、控制程序运行、改善人机界面、支撑应用软件 主要功能 处理器管理（CPU） 设备管理（打印机、IO设备） 存储器管理（内存单元的分配） 文件管理（程序与文档的访问和组织） 典型操作系统 Windows、MS DOS、UNIX、Linux 地位：“总管家”，其他软件的基础。 目标：提高资源利用率。,人机交互界面,MS DOS 系统 命令行方式 程序启动方法：输入命令文本 Windows 系统 图形用户界面 程序启动方法：菜单选择

12、、双击图标等,Windows 操作系统,版本 Windows 98/Windows 2000 32位多用户多任务操作系统 多窗口界面操作手段（启动程序） 双击桌面图标 点击多级菜单（从左下角的“开始）,资源管理器,集成了文件管理和设备管理的功能 管理各种程序文件和数据文件 文件命名规则 文件名.扩展名 扩展名表示文件种类 例如： SETUP.EXE 可执行程序文件 MYPROC.C C语言程序文件 MYPROC.OBJ 机器语言程序文件 MYPAPER.TXT 文本文件 MYPIC.BMP 图象文件,资源管理器中的文件夹窗口,以多级目录的形式展示各种资源的组织结构，如： 我的文档：私有文件 我

13、的电脑：磁盘中的文件 3.5 软盘（A:） 盘符标识 本地磁盘（C:） 网上邻居：网络资源 计算机、打印机等,文件夹的维护方法,选中操作对象 当前文件或当前文件夹 鼠标拖动 点击“文件(F)”菜单项 “新建”文件夹 或 各种文件 删除 重命名 查看方法 左窗口点击加号：展开文件夹 右窗口显示当前文件夹内容（文件名或图标）,文件使用方法,选中操作对象 可执行程序文件 其他文件（数据文件、程序文件） 鼠标双击文件名或图标 对于可执行程序文件，则启动该程序 对于其他文件，则调用规定的可执行程序来编辑 Windows系统中可以规定各种数据文件的处理程序 例如：WORD负责编辑*.DOC文件 Power

14、Point负责编辑*.PPT文件,命令行操作方式,“开始”“运行(R)” （Windows 2000) 在“打开”窗口中输入 cmd, 点击“确定” “开始”“程序”“MS-DOS方式”（Windows 98） 显示运行窗口，等待用户输入命令 则跳出命令行窗口，以闪烁光标提示用户输入 这种方式叫做控制台方式（Console) 是早期操作系统采用的使用方式 如：MS DOS系统、Unix系统 用户输入命令，回车之后；必须等待计算机执行该命令的结果,控制台窗口,当前路径指示（光标左侧） 如：C:Documents and SettingsSong 表示当前目录是磁盘C:中文件夹Documents

15、and Settings的文件夹Song 常用命令（DOS命令） CD 将当前磁盘根文件夹作为当前目录 CD 将当前目录的父文件夹作为当前目录 CD 文件夹名 改变当前目录 MD 文件夹名 创建子文件夹 RD 文件夹名 删除指定文件夹,控制台常用命令（DOS命令）,DIR 列出当前目录中的所有文件名 DEL F1.C 删除文件F1.C（当前目录中） COPY F1.C F2.C 将文件F1.C复制为F2.C TYPE F1.C 展示文件F1.C的内容 A: 将当前目录改变到磁盘A: 程序的执行 SETUP 启动可执行程序SETUP.EXE,计算机软件的安装与卸载,各种安装方式（各种软件要求不同

16、） 将程序复制到磁盘中，直接运行 光盘插入后，直接进入安装 将程序复制到磁盘中，直接运行安装程序（常见：Setup.exe, Install.exe） 基本常识 序列号：厂商提供 安装位置（磁盘、文件夹）可选择 C:盘应保留足够的空间（300MB以上） 卸载 “控制面板”“添加或删除程序”,计算机硬件的配置,兼容性问题 打印机、显示器、显示卡、网卡、调制解调器、闪盘、宽带接入点。 安装设备专用的驱动程序 Windows 自动检测 或 “控制面板”“添加硬件” 进入安装向导，输入提示的信息,1.4 计算机网络概要,地理上分散的多台独立自主的计算机通过软硬件设备互连，以实现资源共享和信息交换的系统

17、。 网络具备的三个要素 多台计算机的资源共享（软件、硬件和数据） 多台计算机的互相连接（电缆、无线网） 共同遵守的网络通信协议（TCP/IP等） 通信网络 局域网数十公里以内 广域网数十公里以外 因特网（Internet、互连网) 信息高速公路,常见的网络硬件设备,服务器 提供共享资源：CPU、内存、磁盘、打印机、数据其他计算机（客户机）或网络终端 使用专用操作系统（如：Windows 2000 Server) 网络适配器（网卡） 连接电缆（双绞线、光纤）、转换信号 交换机和集线器 通过通信线路连接多台计算机 调制解调器(MODEM) 用于通过电话线连接网络,资源共享的内容,数据共享 数据访问

18、、数据下载、数据维护 服务共享 信息处理、应用共享 协同工作 信息交流、协作完成特定的工作 资源共享的参与者 使用者 计算机软件（分布式系统）,网络连接的建立,安装必要的硬件 网卡或调制解调器、电缆 网络软件配置 Windows 2000中的配置过程 “开始”“设置”“网络和拨号连接” Windows 98中的配置过程 “开始”“程序”“附件”“通讯”“拨号网络” 选择“新建连接”，按照连接向导输入以下信息： 拨号到Internet、手动设置Internet连接、通过电话线和调制解调器连接、输入电话号、用户名、密码、连接名,1.5 计算机应用技术,计算机在生产、科学研究、文化、管理、经营以及其

19、他各种社会活动中的应用所涉及的原理、技术和方法 核心技术：信息的处理和管理 中文信息处理、计算机图形学和图像处理、多媒体技术 数据库应用技术（基于数据库管理系统）,应用领域,科学计算 数值分析、计算数学 计算机信息系统 数据的采集、处理、管理以及信息服务 金融管理、企业管理、电子商务、电子政务 计算机辅助系统 计算机辅助设计（CAD）、制造（CAM）、工程（CAE）、教学（CAI） 计算机控制与仿真系统 计算机控制系统：工业过程控制 计算机仿真技术：数学模型、过程模型,几个常用的应用软件,Internet Explorer（IE） 网络浏览器：显示网页 Outlook Express 电子邮件

20、软件 Microsoft Word 文字处理软件,Internet Explorer的使用,在地址栏输入URL（统一资源定位器），如： 北京工业大学：http:/ 软件学科部：http:/172.21.14.209/（网址） 网页浏览 超连接：其他网页的入口 （手形光标指示处） 通过鼠标双击进入,电子邮件的使用,电子邮件系统 服务器为用户提供专用邮箱，邮箱地址 例如： Outlook Express功能 接收邮件、发送邮件、编辑邮件 使用前的设置 帐号：“工具”“帐号”“添加”“邮件” 填写邮箱地址、邮件服务器名、帐户名、密码,Outlook Express的使用,左侧文件夹指示当前目录 收件

21、箱、发件箱等 邮件的编辑和发送 点击“创建邮件” 输入收件人邮箱地址，主题和内容等 点击“发送” 邮件的接收和查看 点击“发送/接收” 查看收件箱，双击收到的邮件表项,Microsoft Word的使用,创建或打开文档,内容输入（文字、图形、表格等）,文档编辑（选定内容、删除、复制、移动等）,文档排版（字符、段落、图文混排等）,文档存盘（保存、另存为）,文档创建、内容输入和选择,新建或打开方法 点击按钮： “文件”菜单项： 内容输入 键盘输入：在光标指定位置 汉字输入：Ctrl+Space切换 其他内容的插入：“插入”菜单项 内容选定 鼠标双击 鼠标拖动选择,内容编辑、排版和保存,内容删除 D

22、elete键、或Ctrl+X 删除选定的内容 剪贴板的使用 Ctrl+X 将选定内容移到剪贴板 Ctrl+C 将选定内容复制到剪贴板 Ctrl+V 将剪贴板内容插入光标位置 排版：“格式”菜单 字体、段落等等 保存（“文件”菜单内） 指定文件名、文件夹名（保存位置）,计算机操作技能的训练,基本操作 汉字输入方法、资源管理器的使用 DOS 命令的使用 应用软件 Word 的使用，IE 浏览器的使用，电子邮件的使用 学习方法 上机实践、反复试用、达到熟练 有问题：请教同学、老师；查工具书、手册,1.6 计算机数据表示法,常用的各种数据 数值数据（十进制数、十六进制数） 表示为二进制数 字符数据 汉

23、字表示 图形数字化 多媒体数据 提供二进制编码表示,数值的按位展开（转化为十进制）,十进制数 78.2 表示 7101+8100+210-1 二进制数 101.1 表示 122+021+120+12-1 十六进制数 2af a-f（A-F） 分别表示10-15 表示 2162+10161+15160 提供了各种进制数向十进制数的转化方法,十进制整数转换为二进制整数: “除2取余”,用竖式计算整数59的二进制数： 2 59 余1 2 29 余1 2 14 余0 2 7 余1 2 3 余1 2 1 余1 0 （59）10 =（111011）2,(最低位),(最高位),直到商为0为止,十进制小数转换

24、为二进制小数,方法: “乘2取整” 例1: （0.375）10=（0.011）2,改为0后继续,直到小数部分为0为止,如果该十进制小数不能完整地转换为二进制小数，可以保留小数点后若干位（按题目要求做）。,例:(0.15)10,有符号数的表示,二进制表示的最高位（符号位）表示符号 规定“0”代表正数，“1”代表负数。 例如：如果整数表示采用8个二进制位（bit） 正整数 +83 表示为 01010011 负整数 83 表示为 11010011（原码表示） 其他表示法 目的：方便运算的机器实现 反码：-83 表示为 10101100（按位取反） 补码：-83 表示为 10101101（反码加一）

25、正整数的反码、补码与原码的正整数相同;,实数的表示,实数可以表示为 500.55 = 0.50055103 = 5.0055102 = 5005.5 10-1 尾数和阶码 十进制中：N =d10P 二进制中：N =d2P 其中，d称为N的尾数，P称为阶码 机器实现（浮点表示） 在存储单元内分别保存尾数和阶码 例：阶码占用8bit、尾数占用24bit（包括符号位） 阶的正负，实际上是指示小数点的实际位置; 尾数的正负，表示整个数是正数还是负数。,西文字符表示,常用ASCII字符编码标准 （American Standard Code for Information Interchange） 7b

26、it表示 52个英文大小写字母 10个阿拉伯数字 标点符号、运算符和控制符 ASCII编码占用一个字节，最高位为“0”,pqr s t uvwxyz,a b c d e f g h I j k l m n o,P Q RS T U V W XYZ,A B C D E F G H I J K L M N O,0 1 2 3 4 5 6 7 8 9,0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111,b6b5b4,000 001 010 011 100 101 110 111,b3b2b1b

27、0,控制信号,ASCII码表,“0”的编码为0110000(48),“A”的编码为1000001(65),“a”的编码1100001(97),汉字编码,国标码：国家标准信息交换用汉字编码（ GB2312-80 标准） 用两个7bit表示一个汉字 以94个字符代码为基础，任何两个代码组成一个汉字交换码（两个字节） 第一个字节为“区”码（共94个区） 第二个字节为“位”码（共94个位）,图形数字化编码,采用像素点阵 例如：显示分辨率 800600个像素 黑白图象 每个像素采用1bit 256色图象 每个像素采用8bit 真彩色图象 每个像素采用24bit,内存中的二进制数,同一个二进制数 可以表示

28、不同的数据 如：整数、指令、图象 信息处理中必须记录数据的类别 操作系统中标明 （如：文件扩展名） 程序设计中提供数据说明,1.7 程序设计语言,程序设计语言是人与计算机交流的工具 人使用程序设计语言来编制程序（程序设计）来描述信息处理算法，通过语言处理系统来生成可执行程序文件。计算机通过程序执行来实现规定的信息处理 语言分类 机器语言 汇编语言 高级语言,机器语言,是二进制形式表示的程序设计语言，是各种不同功能的机器指令的集合。 例：10000000 加 10010000 减 机器语言编写的程序可以被计算机硬件识别、理解，直接执行。 特点：机器相关，程序执行效率高，编写难度大，不便阅读，调试

29、修改困难，无法移植到其他计算机。,汇编语言,符号化的机器语言，也称符号语言 用助记符来表示机器指令，便于使用和记忆。 例： MOV AL，8 数据传输 ADD AL，9 加法计算 特点： 语句与机器指令几乎一一对应 程序可读性优于机器语言程序、其他优缺点仍存在 汇编语言指令是机器不能直接识别、理解和执行。要经过翻译程序。,高级语言,算法语言：用户主要考虑解题算法的逻辑和过程的描述。 与自然语言和数学语言更接近，独立于指令系统，易于被用户掌握、便于记忆、阅读和理解，编程方便。 常用的有：FORTRAN、PASCAL、BASIC、COBOL、C、C+、JAVA、PROLOG等。,高级语言程序例,C

30、语言程序： main( ) int al; al = 8 + 9; printf (“%dn”, al); ,BASIC语言程序： 10 AL = 8 + 9 20 PRINT AL 30 END,语言处理程序,编译方式：,解释方式：解释一句执行一句，无目标程序生成。,它是一个翻译系统，是将用户用各种程序设计语言编写的源程序翻译成计算机可识别的机器指令的软件。 根据处理对象的不同：汇编程序、编译程序、解释程序。,语言的实现,目标程序和可执行程序都是机器语言程序,其他目标程序 .LIB或.DLL,高级语言的程序开发（以C语言为例）,1. 编制程序 C程序 使用编辑器、综合开发环境（Turbo C等） 2. 编译 目标程序 使用预处理程序、编译器 3. 连接 可执行程序 使用连接器 4. 运行 装入 内存 执行,程序设计的学习,程序设计方法的学习 算法设计与算法描述 数据组织和程序结构 程序设计语言的学习 语法规则：程序的书写格式 操作语义：语句功能的说明 通过上机调试的反馈与验证 验证对语言的掌握情况 检验算法设计的正确性,第一章作业,上机实验 实验指导书：实验1.1 实验1.2 实验1.3 阅读 对照13-14页习题 阅读第一章,