计算机与算法初步.ppt

计算机与算法初步,北京工业大学计算机学院软件学科部宋凯教案下载：网上教学/E-mail：,教学目的和任务,将初步建立起计算机系统的概念，了解计算机的基本原理、特点，了解与计算机技术有关的重要概念；初步明确今后在学习专业时，各门课程的地位和作用。,将通过介绍算法及C语言的初步，能够掌握结构化程序设计方法，解决如何制定求解问题的算法，及算法描述方法，养成良好的程序设计风格。,为学好高级语言的程序设计及专业课的学习创造条件。,教学安排,总学时:48 上课：32学时 星期一 7-8节（2-6周）1-401 星期四 1-2节（3-5,10-17周）1-414上机：16学时 星期一 3-4节(10-14周)信南510,512室 星期三 1-2节（4-6周）信南206(微机1室),引言,计算机：现代化的信息处理工具处理信息提供结果（输出）结果取决于它接收到的信息（输入）和处理算法计算机科学技术研究计算机的设计与制造利用计算机进行信息获取、表示、储存、处理和控制的理论、原则、方法和技术的学科,引言,计算机产业将科学技术成果转化为商品为商品提供开发、生产、销售、服务、培训的产业相互关系计算机是计算机科学技术的研究对象、是计算机产业的商品计算机产业是计算机与计算机科学技术的依托计算机科学技术是计算机与产业发展的生命源泉,第一章 计算机基础知识,计算机的基本结构计算机软件计算机应用技术操作系统程序设计语言参考书：计算机文化基础教程，冯博琴著，清华大学出版社计算机文化，朱海滨等译，机械工业出版社,1.1 计算机的基本结构,计算机系统由硬件系统和软件系统组成硬件(Hardware)构成计算机系统的物质元器件、部件、设备，以及它们的工程实现（设计、制造和检测技术）软件(Software)计算机系统中的程序及其文档，及其研究、开发、维护所涉及的理论、方法和技术。,计算机组成结构,计算机组成（1/2）,输入设备（输入单元）负责接收信息：键盘、鼠标、手写板输出设备（输出单元）负责输出信息：显示器、打印机内存（主存、内存单元）存取速度快的存储器，保存信息停电则失去记忆外存（二级存储单元）大容量存储、存取速度较慢光盘和磁盘（硬盘、软盘、闪盘）可长期保存信息,计算机组成（2/2）,运算器（算术逻辑单元）负责算术运算、逻辑运算（二进制）控制器控制管理各个单元的工作（控制输入、输出、存储器访问、计算请求）中央处理单元（CPU）CPU=运算器+控制器+处理总线,主机与外部设备,主机中央处理器（CPU）存储器（内存、硬盘）驱动器（软驱、硬驱、光驱）外部设备打印机、显示器、绘图仪摄象机、键盘、鼠标等,计算机的分类,按照规模和性能分类微型计算机、工作站、小型计算机、中型计算机、大型计算机和巨型计算机界限趋于模糊按照用途分类通用机特定场合：服务器、嵌入式计算机专用机特殊功能：过程控制、抗恶劣环境、数据流、逻辑推理、生物计算、量子计算,主要指标（1/2）,计算机字长直接参与运算的二进制位数（常见：32位=1个字）CPU 运算速度CPU 主频（如：1.8GHz）MIPS（每秒执行百万指令数）显示器屏幕尺寸：常用15英寸、17英寸点距（毫米）、最大分辨率：800*600，1024*768显示内存,主要指标（2/2）,存储器容量（存储单元的个数）每个单元：一个字节byte（8个二进制数bit）1TB=1024*GB1GB=1024*MB1MB=1024*KB1KB=1024 个字节 地址：内存单元的编号 32位二进制数（常见）支持信息的存取,微型计算机的启动,冷启动打开电源开关或按复位按钮系统自动运行系统引导程序随后启动操作系统热启动同时按下 Ctrl+Alt+Del 三键常用于机器故障（死机）时,信息处理过程,计算机的信息处理过程按照给定的处理算法接收输入信息，完成计算，产生输出结果信息处理的实现计算机负责将程序翻译成描述处理算法的指令序列，发送给控制器，指挥运算器，协调各个硬件单元，完成指定的信息输入、各种运算和信息输出技术人员负责根据处理需求，设计计算机程序，来描述处理算法,指令系统,指令（Instruction）：要求计算机执行某个操作的命令机器指令控制器能够识别与执行的操作命令代表该操作的二进制数计算机控制的最小单位指令系统计算机可以识别的全部指令各种计算机的指令系统不同,指令的种类,数据传送类指令算术运算与逻辑运算类指令程序控制类指令（转移指令等）输入输出类指令控制和管理计算机的指令（停机、启动、复位等）信息处理算法由指令序列（程序）实现,指令系统决定了计算机的能力，也影响着计算机的体系结构。,工作原理（存储程序概念）,1.利用存储器（内存）来存放要执行的指令序列；2.中央处理器（CPU）依次从内存读出程序中的每条指令3.分析和执行指令4.直至完成全部指令任务。,从存储器取一条指令,执行指令,是停止指令?,程序执行过程,程序执行的流程就是“取指-分析-执行”的循环过程。,否,是,分析该条指令,程 序,结束,存储程序概念(续),存储程序概念决定了计算机的结构（冯.诺依曼）指令和数据都保存在内存中程序确定了计算机的用途程序设计是计算机技术的基本技能,冯诺依曼计算机模型的基本要点:,采用二进制形式表示数据和指令 采取“存储程序”工作方式 计算机硬件部分由五大部件组成,即运算器、控制器、存储器、输入设备和输出设备.到目前为止，各种类型的计算机都属冯.诺依曼计算机。,1.2 计算机软件,软件：Computer Software计算机系统中的程序、数据和文档用户和硬件的接口程序计算任务的处理对象和处理规则的描述可执行程序：指令序列数据和文档程序的说明资料；保存在二级存储器（外存）上。,软件分类,系统软件管理、监控和维护计算机软硬件资源支撑软件支撑软件开发与维护的软件应用软件特定应用领域专用的软件,系统软件,操作系统管理软硬件资源（MS DOS,WINDOWS）编译系统计算机语言处理（C/C+语言、Java语言。）数据库管理系统数据维护和管理（Oracle,SQL Server。）网络软件网络操作系统、网络管理软件其他系统软件系统引导程序基本输入输出程序（BIOS）设备驱动程序（打印机、显示卡、网卡。）,支撑软件和应用软件,支撑软件软件开发环境、软件工具、应用服务器例如C语言：Turbo C，Visual C/C+网页制作软件应用软件办公软件：文字处理（WORD）、表格处理（Excel）、演示文稿（PowerPoint）管理信息系统、图象处理 电子商务、电子政务、数字地球,在不同的系统软件环境下开发的应用程序要在不同的系统软件下运行。,程序运行方式,可执行程序二进制的指令序列，保存在二次存储器（硬盘）中程序启动自动：系统引导、操作系统手动：应用软件、支撑软件运行过程1.将可执行程序装入到内存中2.逐条解释执行各指令（数据存取、计算、控制转移）3.直到遇到终止指令,1.3 操作系统概要,Operating System 用途管理硬件资源、控制程序运行、改善人机界面、支撑应用软件主要功能处理器管理（CPU）设备管理（打印机、IO设备）存储器管理（内存单元的分配）文件管理（程序与文档的访问和组织）典型操作系统Windows、MS DOS、UNIX、Linux 地位：“总管家”，其他软件的基础。目标：提高资源利用率。,人机交互界面,MS DOS 系统命令行方式程序启动方法：输入命令文本Windows 系统图形用户界面程序启动方法：菜单选择、双击图标等,Windows 操作系统,版本Windows 98/Windows 200032位多用户多任务操作系统多窗口界面操作手段（启动程序）双击桌面图标点击多级菜单（从左下角的“开始）,资源管理器,集成了文件管理和设备管理的功能管理各种程序文件和数据文件文件命名规则 文件名.扩展名扩展名表示文件种类例如：SETUP.EXE可执行程序文件MYPROC.CC语言程序文件MYPROC.OBJ机器语言程序文件MYPAPER.TXT文本文件MYPIC.BMP图象文件,资源管理器中的文件夹窗口,以多级目录的形式展示各种资源的组织结构，如：我的文档：私有文件我的电脑：磁盘中的文件3.5 软盘（A:）盘符标识本地磁盘（C:）网上邻居：网络资源计算机、打印机等,文件夹的维护方法,选中操作对象当前文件或当前文件夹鼠标拖动点击“文件(F)”菜单项“新建”文件夹 或 各种文件删除重命名查看方法左窗口点击加号：展开文件夹右窗口显示当前文件夹内容（文件名或图标）,文件使用方法,选中操作对象可执行程序文件其他文件（数据文件、程序文件）鼠标双击文件名或图标对于可执行程序文件，则启动该程序对于其他文件，则调用规定的可执行程序来编辑Windows系统中可以规定各种数据文件的处理程序例如：WORD负责编辑*.DOC文件 PowerPoint负责编辑*.PPT文件,命令行操作方式,“开始”“运行(R)”（Windows 2000)在“打开”窗口中输入 cmd,点击“确定”“开始”“程序”“MS-DOS方式”（Windows 98）显示运行窗口，等待用户输入命令则跳出命令行窗口，以闪烁光标提示用户输入这种方式叫做控制台方式（Console)是早期操作系统采用的使用方式如：MS DOS系统、Unix系统用户输入命令，回车之后；必须等待计算机执行该命令的结果,控制台窗口,当前路径指示（光标左侧）如：C:Documents and SettingsSong表示当前目录是磁盘C:中文件夹Documents and Settings的文件夹Song常用命令（DOS命令）CD 将当前磁盘根文件夹作为当前目录CD.将当前目录的父文件夹作为当前目录CD 文件夹名改变当前目录MD 文件夹名创建子文件夹RD 文件夹名删除指定文件夹,控制台常用命令（DOS命令）,DIR 列出当前目录中的所有文件名 DEL F1.C 删除文件F1.C（当前目录中）COPY F1.C F2.C 将文件F1.C复制为F2.CTYPE F1.C 展示文件F1.C的内容A:将当前目录改变到磁盘A:程序的执行SETUP启动可执行程序SETUP.EXE,计算机软件的安装与卸载,各种安装方式（各种软件要求不同）将程序复制到磁盘中，直接运行光盘插入后，直接进入安装将程序复制到磁盘中，直接运行安装程序（常见：Setup.exe,Install.exe）基本常识序列号：厂商提供安装位置（磁盘、文件夹）可选择C:盘应保留足够的空间（300MB以上）卸载“控制面板”“添加或删除程序”,计算机硬件的配置,兼容性问题打印机、显示器、显示卡、网卡、调制解调器、闪盘、宽带接入点。安装设备专用的驱动程序Windows自动检测 或“控制面板”“添加硬件”进入安装向导，输入提示的信息,1.4 计算机网络概要,地理上分散的多台独立自主的计算机通过软硬件设备互连，以实现资源共享和信息交换的系统。网络具备的三个要素多台计算机的资源共享（软件、硬件和数据）多台计算机的互相连接（电缆、无线网）共同遵守的网络通信协议（TCP/IP等）通信网络局域网数十公里以内广域网数十公里以外因特网（Internet、互连网)信息高速公路,常见的网络硬件设备,服务器提供共享资源：CPU、内存、磁盘、打印机、数据其他计算机（客户机）或网络终端使用专用操作系统（如：Windows 2000 Server)网络适配器（网卡）连接电缆（双绞线、光纤）、转换信号交换机和集线器通过通信线路连接多台计算机调制解调器(MODEM)用于通过电话线连接网络,资源共享的内容,数据共享数据访问、数据下载、数据维护服务共享信息处理、应用共享协同工作信息交流、协作完成特定的工作资源共享的参与者使用者计算机软件（分布式系统）,网络连接的建立,安装必要的硬件网卡或调制解调器、电缆网络软件配置Windows 2000中的配置过程“开始”“设置”“网络和拨号连接”Windows 98中的配置过程“开始”“程序”“附件”“通讯”“拨号网络”选择“新建连接”，按照连接向导输入以下信息：拨号到Internet、手动设置Internet连接、通过电话线和调制解调器连接、输入电话号、用户名、密码、连接名,1.5 计算机应用技术,计算机在生产、科学研究、文化、管理、经营以及其他各种社会活动中的应用所涉及的原理、技术和方法核心技术：信息的处理和管理中文信息处理、计算机图形学和图像处理、多媒体技术数据库应用技术（基于数据库管理系统）,应用领域,科学计算数值分析、计算数学计算机信息系统数据的采集、处理、管理以及信息服务金融管理、企业管理、电子商务、电子政务计算机辅助系统计算机辅助设计（CAD）、制造（CAM）、工程（CAE）、教学（CAI）计算机控制与仿真系统计算机控制系统：工业过程控制计算机仿真技术：数学模型、过程模型,几个常用的应用软件,Internet Explorer（IE）网络浏览器：显示网页Outlook Express电子邮件软件Microsoft Word文字处理软件,Internet Explorer的使用,在地址栏输入URL（统一资源定位器），如：北京工业大学：http:/（网址）软件学科部：（网址）网页浏览超连接：其他网页的入口（手形光标指示处）通过鼠标双击进入,电子邮件的使用,电子邮件系统服务器为用户提供专用邮箱，邮箱地址例如：songkaiOutlook Express功能接收邮件、发送邮件、编辑邮件使用前的设置帐号：“工具”“帐号”“添加”“邮件”填写邮箱地址、邮件服务器名、帐户名、密码,Outlook Express的使用,左侧文件夹指示当前目录收件箱、发件箱等邮件的编辑和发送点击“创建邮件”输入收件人邮箱地址，主题和内容等点击“发送”邮件的接收和查看点击“发送/接收”查看收件箱，双击收到的邮件表项,Microsoft Word的使用,创建或打开文档,内容输入（文字、图形、表格等）,文档编辑（选定内容、删除、复制、移动等）,文档排版（字符、段落、图文混排等）,文档存盘（保存、另存为）,文档创建、内容输入和选择,新建或打开方法点击按钮：“文件”菜单项：内容输入键盘输入：在光标指定位置汉字输入：Ctrl+Space切换其他内容的插入：“插入”菜单项内容选定鼠标双击鼠标拖动选择,内容编辑、排版和保存,内容删除Delete键、或Ctrl+X删除选定的内容剪贴板的使用Ctrl+X将选定内容移到剪贴板Ctrl+C将选定内容复制到剪贴板Ctrl+V将剪贴板内容插入光标位置排版：“格式”菜单字体、段落等等保存（“文件”菜单内）指定文件名、文件夹名（保存位置）,计算机操作技能的训练,基本操作 汉字输入方法、资源管理器的使用 DOS 命令的使用 应用软件 Word 的使用，IE 浏览器的使用，电子邮件的使用 学习方法 上机实践、反复试用、达到熟练 有问题：请教同学、老师；查工具书、手册,1.6 计算机数据表示法,常用的各种数据数值数据（十进制数、十六进制数）表示为二进制数字符数据汉字表示图形数字化多媒体数据提供二进制编码表示,数值的按位展开（转化为十进制）,十进制数 78.2表示 7101+8100+210-1二进制数 101.1表示 122+021+120+12-1十六进制数 2afa-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为止,十进制小数转换为二进制小数,方法:“乘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（反码加一）正整数的反码、补码与原码的正整数相同;,实数的表示,实数可以表示为 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）7bit表示52个英文大小写字母10个阿拉伯数字标点符号、运算符和控制符ASCII编码占用一个字节，最高位为“0”,pqrstuvwxyz,abcdefghIjklmno,PQRSTUVWXYZ,ABCDEFGHIJKLMNO,0123456789,0000000100100011010001010110011110001001101010111100110111101111,b6b5b4,000 001 010 011 100 101 110 111,b3b2b1b0,控制信号,ASCII码表,“0”的编码为0110000(48),“A”的编码为1000001(65),“a”的编码1100001(97),汉字编码,国标码：国家标准信息交换用汉字编码（GB2312-80 标准）用两个7bit表示一个汉字以94个字符代码为基础，任何两个代码组成一个汉字交换码（两个字节）第一个字节为“区”码（共94个区）第二个字节为“位”码（共94个位）,图形数字化编码,采用像素点阵例如：显示分辨率 800600个像素黑白图象每个像素采用1bit256色图象每个像素采用8bit真彩色图象每个像素采用24bit,内存中的二进制数,同一个二进制数 可以表示不同的数据 如：整数、指令、图象 信息处理中必须记录数据的类别 操作系统中标明（如：文件扩展名）程序设计中提供数据说明,1.7 程序设计语言,程序设计语言是人与计算机交流的工具人使用程序设计语言来编制程序（程序设计）来描述信息处理算法，通过语言处理系统来生成可执行程序文件。计算机通过程序执行来实现规定的信息处理语言分类机器语言汇编语言高级语言,机器语言,是二进制形式表示的程序设计语言，是各种不同功能的机器指令的集合。例：10000000 加10010000 减机器语言编写的程序可以被计算机硬件识别、理解，直接执行。特点：机器相关，程序执行效率高，编写难度大，不便阅读，调试修改困难，无法移植到其他计算机。,汇编语言,符号化的机器语言，也称符号语言用助记符来表示机器指令，便于使用和记忆。例：MOV AL，8数据传输 ADD AL，9加法计算特点：语句与机器指令几乎一一对应程序可读性优于机器语言程序、其他优缺点仍存在汇编语言指令是机器不能直接识别、理解和执行。要经过翻译程序。,高级语言,算法语言：用户主要考虑解题算法的逻辑和过程的描述。与自然语言和数学语言更接近，独立于指令系统，易于被用户掌握、便于记忆、阅读和理解，编程方便。常用的有：FORTRAN、PASCAL、BASIC、COBOL、C、C+、JAVA、PROLOG等。,高级语言程序例,C语言程序：main()int al;al=8+9;printf(“%dn”,al);,BASIC语言程序：10 AL=8+920 PRINT AL30 END,语言处理程序,编译方式：,解释方式：解释一句执行一句，无目标程序生成。,它是一个翻译系统，是将用户用各种程序设计语言编写的源程序翻译成计算机可识别的机器指令的软件。根据处理对象的不同：汇编程序、编译程序、解释程序。,语言的实现,目标程序和可执行程序都是机器语言程序,其他目标程序.LIB或.DLL,高级语言的程序开发（以C语言为例）,1.编制程序-C程序 使用编辑器、综合开发环境（Turbo C等）2.编译-目标程序 使用预处理程序、编译器3.连接-可执行程序 使用连接器4.运行 装入-内存 执行,程序设计的学习,程序设计方法的学习算法设计与算法描述数据组织和程序结构程序设计语言的学习语法规则：程序的书写格式操作语义：语句功能的说明通过上机调试的反馈与验证 验证对语言的掌握情况 检验算法设计的正确性,第一章作业,上机实验 实验指导书：实验1.1 实验1.2 实验1.3 阅读 对照13-14页习题 阅读第一章,