信息学奥林匹克竞赛基础知识.ppt

信息学奥林匹克竞赛简介1 全国青少年信息学奥林匹克分区联赛 简称NOIP 它又分为初赛 笔试 初赛在东营市称为东营市信息学奥林匹克竞赛 在每年10月份举行 获市一等奖的初中学生中考时加10分 在初赛中成绩突出的学生 将被选拔参加同年11月份举行的复赛 上机编程 在复赛中获得国家级一等奖的高中学生 就获得了保送到全国重点大学的资格 在复赛中获得国家级二等奖的学生 就获得了参加重点大学自主招生考试的资格 在复赛中获得国家级一 二等奖的初中学生中考时加20分 中考加分情况每年可能有变化 具体情况请咨询相关主管部门 2 全国青少年信息学奥林匹克竞赛 简称NOI 在上一年联赛 NOIP 中成绩突出的同学 将于第二年5月份参加山东省队选拔赛 被选拔上的同学参加第二年8月份举行的NOI比赛 在NOI比赛中获得前20名 一等奖 的高中学生 获得免试保送到清华 北大等名牌大学的资格 获前50名左右 二等奖 的高中学生 获得免试保送到复旦 南开等重点大学的资格 只要是三等奖以上的学生都可以获得免试保送到上海交通大学的资格 3 国际青少年信息学奥林匹克竞赛 简称IOI 在全国信息学奥赛 NOI 突出的学生将被选拔参加第二年8月份举行的国际比赛 IOI 它轮流在世界各国举行 在比赛中成绩优异的学生 不仅有丰厚的奖品和国内大学任意选择 而且国际上有名的大学也非常愿意接收这样的学生 计算机的基础知识 一 计算机的发展和应用 二 计算机概述 三 多媒体技术应用 四 计算机网络使用基础 第一台电子计算机的诞生 1946年世界上第一台数字式电子计算机是由美国宾夕法尼亚大学的物理学家约翰 莫克利和工程师普雷斯伯 埃克特领导研制的取名为ENIAC的计算机 由于这台计算机使用了电子器 电子管和电子线路 因此其功能在当时确实是出类拔萃 例如 它可以在一秒钟内进行5000次加减法运算 3毫秒便可以进行一次乘法运算 与手工计算相比速度大大加快 但是 它也明显地存在着缺点 它体积庞大 机器中约有18800只电子管 1500个继电器 70000只电阻及其他各类电气元件 重30吨 占地170平方米 运行时耗电量很大 存储容量很小 只能存储20个字长为10位的十进制数 另外 它采用线路连接的方法来编排程序 因此每次解题都要靠人工改接连线 准备时间大大超过实际计算时间 它没有存储程序的能力 不具备自动计算功能 一 计算机的发展和应用 计算机发展的几个阶段 研制中的第五代计算机 至目前为止 各种类型的计算机都属于冯 诺依曼型计算机 即采用存储程序方式进行工作 随着计算机应用领域的扩大 冯 诺依曼型的工作方式逐渐显露出其局限性 所以科学家提出了制造非冯 诺依曼式计算机 正在开发研制中的第五代智能计算机 将具有自动识别自然语言 图形 图像的能力 具有理解和推理的能力 具有知识获取 知识更新的能力 可望能够突破当前的计算机的结构模式 研制朝两个方向努力 1 创建非冯 诺依曼式语言2 创建以人脑神经系统处理信息原理为基础的非冯 诺依曼的计算机模型 如 生物计算机 光子计算机 量子计算机 计算机的应用 1 科学计算 数值计算 2 数据处理 信息处理 3 人工智能 4 自动控制 5 计算机辅助设计 CAD 和制造 计算机辅助教育 CAI 信息高速公路 能源 材料 物质 信息是社会发展的三大支柱 1993年美国宣布了国家信息基础设施 NII 计划 正式提出了建设全国性信息高速度公路的设想 二十多年来逐步演变和发展的Internet网络 已为信息高速公路勾画出一个雏形 并为整个信息基础设施打下了一定的基础 在美国政府提出信息高速公路发展计划之后 全球许多国家纷纷制订了本国的信息计划 以期在新世纪来临之际 占领有利位置 谋求国家的长远利益 一时间信息高速公路热席卷全球 我国的 三金 工程 1 金桥工程 即国家公用经济信息通信网络工程 晚国信息化建设的基础设施之一 其目标是建立一个覆盖全国各省市 自治区 500个中心城市 与各部门 地方专用计算机网相联 与男家综合管理部门信息中心的计算机网相联 并实行与国际计算机联网的公用基干网和网中网 2 金关工程 它是金桥工程的起步工程之一 将为海关 外贸 外汇管理和税务等部门的业务系统专用网络实行计算机联网 3 金卡工程 即电子货币工程 是金融电子化和商业流通现代化的重要组成部分 分类标准一 大型通用机 巨型机 小型机 工作站 微型机 PC机 网络计算机 NC机 分类标准二 巨型机 大型机 中型机 小型机 微机 二 计算机概述 计算机的分类 计算机的组成和工作原理 1 存储程序工作原理 存储程序工作原理 是由美籍匈牙利数学家冯 诺依曼在1946年提出的 其基本思想是 在计算机中设置存储器 将符号化的计算步骤存放在存储器中 然后依次取出存储的内容 由一个被称之为控制器的部件进行译码 译码结果在运算器中进行计算 从而实现计算机工作的自动化 运算器和控制器统称CPU 冯 诺依曼依据此原理设计出第一台具有存储程序功能的计算机EDVAC 离散变量自动电子计算机 二 计算机概述 2 计算机指令系统 机器指令是要计算机执行某种操作的命令 且由计算机直接识别执行 一台计算机可以有许多指令 作用也各不相同 所有指令的集合称为计算机的指令系统 计算机的类型不同 指令系统也不同 例如 苹果机采用的是6502指令系统 IBMPC采用的是8086 8088指令系统 指令系统是计算机基本功能具体而集中的体现 从计算机系统结构的角度看 指令系统是软件和硬件的界面 指令是对计算进行程序控制的最小单位 指令系统的内核是硬件 当一台机器指令系统确定之后 硬件设计师根据指令系统的约束条件 构造硬件组织 由硬件支持指令系统功能得以实现 而软件设计师在指令系统的基础上建立程序系统 扩充发挥机器的功能 用机器指令编写的程序称之为机器语言程序 一条指令通常由操作码和地址码两部分组成 如图所示 指令按其功能可以分为 1 操作类指令 2 控制转移类指令 3 计算机硬件系统 存储器 Memory 存储器的主要功能是存放程序和数据 程序是计算机操作的依据 数据是计算机操作的对象 为了实现自动计算 各种信息必须预先存放在计算机内的某个地方 这个地方就是存储器 存储器有内存 主存 和外存 辅存 之分 外存是存放程序和数据 仓库 可以长时间的保存大量信息 但程序必须调入到内存方可执行 待处理的数据也只有进行内存后才能被程序加工 所以内存和外存之间的严格的分工 存储器采取按地址存 写 取 读 的工作方式 一个内存体内包括许多的存储单元 每个单元可以存放适当单位的信息 全部存储单元按一定的顺序编号 这种编号就称为存储器的地址 存储器按其读写性可以分为 RAM 随机存储器 ROM 只读存储器 当电源关闭时RAM不能保留数据 如果需要保存数据 就必须把它们写入到一个长期的存储器中 例如硬盘 内存 组成 是由RAM组成的分类 SDR DDR容量 64M 128M 256M 512M 外存 硬盘20G 40G 80G 120G 200G软盘1 44M光盘650MU盘64M 128M 256M 512M SDR内存 DDR内存 硬盘 软盘 光盘 U盘 USB接口 中央处理器 CPU CPU是指令的解释和执行部件 是计算机的心脏 它主要是是由运算器 控制器和通用寄存器组成 目前主流CPU Intel公司 celeron 赛扬 Pentium4 奔四 AMD公司 Sempron 闪龙 Athlon 速龙 CPU的主要性能指标主频即CPU的时钟频率 CPUClockSpeed 这是我们最关心的 我们所说的3 2GHz 2 0GHz等就是指它 一般说来 主频越高 CPU的速度就越快 整机的就越高 不过现在AMD都采用了更加模糊的命名方式 企图让消费者淡化以主频率计算性能的观念 比如Athlon3000 它的频率有可能是2 20GHz 也有可能是2 0GHz Intel则采用了Pentium643这种更易让人眼花缭乱的命名方式 一般人不查参数 很难记得它的意义 FSB前端总线即CPU的外部时钟频率 由电脑主板提供 以前一般是133MHz 目前Intel公司最新的芯片组i925XE芯片组使用1066MHz的FSB 内部缓存 L1Cache 封闭在CPU芯片内部的高速缓存 用于暂时存储CPU运算时的部分指令和数据 存取速度与CPU主频一致 L1缓存的容量单位一般为KB L1缓存越大 CPU工作时与存取速度较慢的L2缓存和内存间交换数据的次数越少 相对电脑的运算速度可以提高 外部缓存 L2Cache CPU外部的高速缓存 现在处理器的L2Cache是和CPU运行在相同频率下的 以前P2P3的二级缓存运行在相当于CPU频率一半下 输入 输出 Input Output I O 设备 I O设备实现外部世界与主机之间的信息交换 提供人机交互的硬件环境 输入设备 显示器 打印机 绘图仪输出设备 键盘 鼠标 扫描仪 显示器阴极射线管显示器 CRT 液晶显示器LCD 打印机 针式打印机 喷墨打印机 激光打印机 绘图仪 扫描仪 4 程序的自动执行 计算机硬件系统只能执行由机器指令组成的程序 程序在执行前必须首先装入内存 程序执行时CPU负责从内存中逐条取出指令 分析识别指令 最后执行指令 从而完成一条指令的执行周期 CPU就是这样周而复始地工作 直至程序的完成 计算机的软件系统 软件可以分为 系统软件和应用软件 系统软件是生成 准备和执行其他程序所需要的一组程序 它通常负责管理 控制和维护计算机的各种软硬件资源 并为用户提供友好的操作界面 常见的系统软件包括 操作系统 语言处理程序 汇编和编译程序等 数据库管理系统 连接装配程序 系统实用程序 多种工具软件等 应用软件是专业人员为了种应用目的而编制的程序 由于这些程序是在系统软件支持的环境下编写的 因此不必要了解机器的硬件细节 如 文字处理软件 图形处理软件 成绩管理 银行管理等 操作系统 1 MS DOS操作系统 单用户单任务操作系统 2 Windows操作系统Windows3 1Windows95Windows98 单用户多任务操作系统 WindowsNT 多用户多任务操作系统 Windows2000 professional server WindowsXPWindows20033 UNIX操作系统 多用户多任务操作系统 4 Linux操作系统5 MacintoshOS操作系统 1984年苹果公司推出的 市场上第一个图形界面的 6 IBMOS 2操作系统 数据库 现在比较流行的大中型关系型数据库有IBMDB2 Oracle SQLServer SyBase Informix等 常用的小型数据库有Access Pradox Foxpro等 现在个人用户比较常用的主要是基于中小型数据库MSSQLServer和Access的 所以在以下的篇幅中我们介绍这两种数据库系统的简单操作 计算机编程语言 系统软件 低级程序设计语言机器语言汇编语言高级程序设计语言过程化语言 BASIC PASCAL C COBOL FORTRAN LOGO非过程化语言 Fox系列典型的面向对象语言有 SIMULA67 Smalltalk EIFFEL C Java Delphi VC VB不完全面向对象 解释类 执行方式类似于我们日常生活中的 同声翻译 应用程序源代码一边由相应语言的解释器 翻译 成目标代码 机器语言 一边执行 因此效率比较低 而且不能生成可独立执行的可执行文件 应用程序不能脱离其解释器 但这种方式比较灵活 可以动态地调整 修改应用程序 编译类 编译是指在应用源程序执行之前 就将程序源代码 翻译 成目标代码 机器语言 因此其目标程序可以脱离其语言环境独立执行 使用比较方便 效率较高 但应用程序一旦需要修改 必须先修改源代码 再重新编译生成新的目标文件 OBJ 才能执行 只有目标文件而没有源代码 修改很不方便 现在大多数的编程语言都是编译型的 例如VisualC VisualFoxpro Delphi等 信息的表示和存储 不论是指令还是数据 若想存入计算机中 都必须采用二进制编码形式 即便是图形 声音等这样的信息 也必须转换成二进制数的形式 才能存入计算机中 采用二进制来表示信息的原因主要有 1 易于物理实现 2 二进制运算简单 3 机器可靠性高 4 通用性强 进制转换 N进制转十进制 1101101 0101 2 109 3125 155 24 8 109 3125 6D 5 16 109 3125注 十六进制表示 0 1 2 3 4 5 6 7 8 9 A B C D E F 十进制转N进制 整数部分 除N取余小数部分 乘N取整 109 3125 10 1101101 0101 2 109 3125 10 155 24 8 109 3125 10 6D 5 16 二 八 十六进制的相互转换 2 8 三位组一位2 16 四位组一位8 2 一位分三位16 2 一位分四位 计算机中的单位 1个二进制位 1bit8个二进制位 1字节 Byte或B 1024B 1K1024K 1M1024M 1G1024G 1T 计算机中带符号数的表示法 机器数和真值 数的符号在计算机中是通过增设一位符号位来数码化的 正数符号用 0 表示 负数符号用 1 来表示 如 1001100在计算机中表示为01001100 1001100在计算机中表示为11001100 已经数码化的带符号数称为机器数 符号没有数码化的称为真值 在计算机中机器数常用三种表示方法 原码 补码 反码 原码 在用二进制原码表示的数中 符号位为0表示正数 符号位为1表示负数 其余各位表示数值部分 这种表示法称原码表示法 反码 除符号位以外 表示数值部分取反 也就是 1 变成 0 0 变成 1 补码 补码表示法可以把负数换化为正数 使减法转换为加法 从而使正负数的加减运算换化为单纯的正数相加运算 补码 12 9 3 现在标准时间为3点 为了校准时钟需要把时针拔到3点的位置 可以倒拔三个格 相当于 3 还以正拔九个格 相当于 9 也就是 6 3 36 9 12 自动丢失 3 3这个自然丢失的数就叫做 模 mod 同样一个字长为8位的二进制数 最大可以表示 11111111 2 255 28 1那么如果要表示28即 100000000 2时 用八位二进制来表示时 第九位的 1 就自动丢失了 只剩下 00000000 2 那么原码是8位的二进制数的 模 是28 同理原码是n位二进制数的 模 就是2n 整数的补码为 小数的补码为 例如 X 1101001 X 补 01101001X 1101001 X 补 10010111X 0 1011 X 补 01011X 0 1011 X 补 10101 补码是定义 即 正数的补码就是原码负数的补码是模加真值 非数值信息的表示 在计算机内部非数值信息 如文字 图形 图像 声音等也都是由二进制数来表示的 西文字符编码 1 ASCII码 美国信息交换标准代码 注 用一个字节 七位二进制数来表示 共127个 0100001a1100001 0100010b1100010 2 EBCDIC 是IBM公司在其机器上广泛使用的一种代码 注 用一个字节 八位二进制数来表示 共256个中文信息编码 GB2312 80 国家标准信息交换用汉字编码 简称国标码 注 用二个字节 每字节中的七位来表示一个汉字 三 多媒体应用技术 多媒体技术 就是用计算机交互地综合处理文本 图形 图像 动画 音频及视频影像等多种信息 并使这些信息建立逻辑连接 它的英文原语是 Multimedia 目前市场上也以多媒体计算机 ultimediaPersonalComputer MPC 为主流 多媒体计算机系统 CD ROM2 显示卡色彩数 16 256 65536 16M分辨率 640 480800 6001024 7681280 10243 显示器刷新率 60Hz 75Hz4 声卡5 音箱 数据压缩和解压缩技术 1 静止图像压缩标准JPEG压缩比 10 1到80 12 动态图像压缩标准MPEG压缩比 50 1到100 13 多通道的动态图像压缩标准P 64 有关名词解释 图形文件 位图 向量图 像素 真彩色16M4 RGB模式 红 绿 蓝 5 HSB模式 色调 饱和度 亮度 产生比RGB模式更好的视觉效果 四 计算机网络使用基础 计算机网络简介 2 计算机网络的发展 1 计算机网络的雏形 主机 终端 系统 实时处理 分时处理 批处理联机系统 2 计算机网络的里程碑 ARPANET网 1969年 3 广域网 WAN 和局域网 LAN 4 覆盖全球的互联网 Internet 1 计算机网络的含义凡是将分布在不同地理位置的具有独立功能的多台计算机系统 遵照一定的协议 通过通信介质有机组合在一起 再配上相应的网络软件 以实现计算机之间相互通信 资源共享的系统 称为计算机网络 3 计算机网络的功能信息的通信资源的共享 硬件 软件 数据与信息 计算机网络的物理组成 1 各种类型的计算机 网终中心主干机 服务器 工作站 2 共享的外部设备3 网卡 即网终接口卡或网络适配器 4 通信线路 双绞线 同轴电缆 光缆等 5 局部网络通信设备 中继器 集线器Hub 交换机 6 网络互连设备 网桥 路由器 网关 7 网络软件 UNIX NetWare WindowsNT等 目前流行的 客户机 服务器 体系结构中 把网络操作系统的主要部分放在服务器上 以行使对主要网络资源的管理 为客户机提供各种网络服务 计算机网络的拓扑结构 网络中各个站点相互连接的方法和形式称为网络拓扑 1 总线拓扑 2 星型拓扑 3 环型拓扑 4 树型拓扑 网络体系结构 1 ISO OSI网络体系结构 2 Internet网络体系结构 TCP IP网络体系统结构 Internet简介 什么是Internet Internet 因特网 国际互联网 是全球最大的 开放的 有众多网络互连而成的计算机网络 1 网络地址 IP地址 IP地址由四个字节 32位二进制数组成 书写时通常用四组十进制数表示 如 166 111 5 51 2 域名 DN 用字符串来表示IP计算机类型名 网络名 机构名 顶级域名如 常用机构名 顶级域名 3 域名服务器系统 DNS 3 统一资源定位器 URL 协议名 http 超文本传输协议 ftp 文件传输协议 telnet 远程登录协议 file 本地机协议 例如 Internet的服务功能 文件传输服务 ftp 2 远程登录服务 telnet 3 电子邮件服务 mail 用户名 计算机域名采用简单邮件协议 SMTP 4 网络新闻和电子公告栏 BBS 5 信息查询服务 www 万维网 超文本 非顺序文本吃呈现方式 超媒体 超文本和多媒体在浏览环境下的结合 网页 用超文页标记语言 HTML 编写的文本文件 通过浏览器解释执行 搜索引擎 应用最广泛的信息搜索工具 Internet上网方式 电话拨号入网 DDN 数据数字网 方式 ISDN 综合业务数字网 方式 ADSL 非对称数字用户环路 方式5 VDSL 高速数字用户环路 6 CableModem 电缆调制解调器 方式7 Lan IE浏览器的用法