信息学奥赛基础知识提纲.doc

信息学奥赛基础知识提纲 （2014年9月）1 计算机系统11概述一个完整的计算机系统包括硬件系统和软件系统两大部分，必须具有五大功能：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能。它的工作特点是：运算速度快、运算精度高、记忆能力强、通用性广、自动运算。计算机按照规模可分为：巨型机、大型机、中型机、小型机、微型机、单片机等几种类型。根据用途不同分为通用机和专用机。硬件指的是计算机的设备实体；软件通常泛指各类程序和文件。软硬件的关系：硬件是软件的基础。软件是硬件的扩充与完善。硬件与软件在逻辑上是等价的。1946年，世界上第一台计算机诞生于宾夕法尼亚大学，称为ENIAC。1949年,第一台存储计算机EDSAC,英国剑桥大学威尔克斯（Wilkes）设计和制造的。1951年，第一台商用计算机是UNIVAC。按照计算机采用的电子器件可划分为四代，分别是：第一代19461958第二代19581964第三代1964-1975第四代1975至今主要电子器件电子管晶体管集成电路大规模及超大规模集成电路内存汞延迟线磁芯存储器半导体存储器半导体存储器外存储器穿孔卡片、纸带磁带磁带、磁盘磁盘、光盘等大容量存储器处理速度（指令数/秒）几千条几百万条几千万条数亿条以上12 硬件系统121 冯诺伊曼（J.von Neumann）机：美籍匈牙利数学家现代计算机的基本结构被称为冯诺伊曼结构。它的主要特点是储存程序的概念：（1） 采用二进制形式表示数据和指令。（2） 将程序（包括操作指令和操作数）事先存入主存储器中，使计算机在工作时能够自动高速地从存储器中取出指令加以执行。（3） 由运算器、存储器、控制器、输入设备、输出设备五大基础部件组成计算机系统。122 计算机的总线结构计算机的各个部件需要以某种方式互联，进行数据交换。最常见的互联结构就是总线互联结构和多总线互联结构。总线是一种连接多种设备的信息传递通道，实际上是一组信号线。典型的计算机总线结构由内部总线和系统总线组成。（1） 内部总线：用于连接CPU内部的各个模块。（2） 系统总线：又称外部总线，用于连接CPU、存储器和输入输出设备。系统总线的信号线分为三类：数据线、地址线和控制线。数据线（Data Bus）：数据总线的宽度就是指组成数据总线的信号线的数目，它决定了在该总线上一次可以传送的二进制位数。地址线（Address Bus）：用以传递地址信息，来指示数据总线上的数据来源和去向。地址线的数目决定了能够访问空间的大小。控制线（Control Bus）：用来控制数据总线和地址总线。某SRAM芯片，其存储容量为64K*16位，则该芯片的地址线数目和数据线的数目？123 中央处理器（Central Processor Unit）1、CPU包含了冯机五大部件中的运算器（即加法器）和控制器。运算器：对信息加工和处理的部件，主要完成各种算术运算和逻辑运算。控制器：通过读取各种指令，并进行翻译、分析，而后对各部件作出相应的控制。输 出 门A L U输入选择门A输入选择门B通用寄存器组.+12、CPU主要由三大部分组成：寄存器组、算术逻辑单元（ALU）和控制单元（控制器）。寄存器组：分为通用寄存器（通用寄存器、数据寄存器、地址寄存器、标志寄存器）和状态控制寄存器（程序计数器PC、指令寄存器IR、存储器地址寄存器MAR、存储器缓冲寄存器MBR）以及程序状态字PSW。算术逻辑单元ALU： 寄存器、存储器、I/O设备把待处理的数据输入到ALU。控制单元：控制器的基本功能就是时序控制和执行控制。根据当前运行的程序，控制器使CPU按一定的时序关系执行一序列的微操作从而完成程序。时钟信号：控制器根据时钟电路产生的时钟信号进行定时，以控制各种操作按指定的时序进行。计算机的基本功能是执行程序，而程序由一连串的指令组成；计算机的执行过程由一连串的指令周期组成，每一指令周期完成一条指令。这些指令周期又可进一步细分为更小的单元，直到微操作uop-CPU完成的基本的原子操作。 时钟脉冲发生器的晶振频率成为机器的主频，它产生的时钟脉冲信号是整个机器的时间基准，其周期T称为该计算机的时钟周期。 完成一个微操作的时间就称为CPU周期（机器周期）。执行一条机器指令所需的时间称为一个指令周期。3、指令系统（精简指令系统）：操作类指令和控制类指令一条指令：操作码 + 地址码 一条机器指令的执行：取指令分析指令执行指令4、CPU的主要指标有：字长：CPU一次所能处理的二进制位数。它决定着寄存器、加法器、数据总线等的位数。主频：计算机的时钟频率。（即内频）单位：MHz或GHz。运算速度：CPU每秒钟能完成的指令数MIPS。运算速度=1 执行一条机器指令所需的时间124 存储器存储单位：（1） 最小单位：位（bit，缩写b），（2） 基本单位：字节（Byte，缩写B）（3） 常用单位： 1KB(1千字节 )= 1024B 1MB (兆字节)=1024KB 1GB(1千兆字节)= 1024MB 1TB=1024GB存储器的分类关系如图：图 2内存储器：又称主存，存储器按字节编址。（1） ROM：断电后信息不会丧失，但是信息只能读出不能写入。（BIOS）（2） RAM：信息可读出和写入，断电后信息全部丢失。（如“内存”、“显存”等）外存储器：又称作辅助存储器。外存储器是一般容量较大且可以移动。例如：硬盘、软盘、光盘、ZIP盘、MO光磁盘、USB存储器等。计算机硬件系统存取信息的方式如图：CPUCache(缓存)RAM(主存)Disk( 辅存)存储器的主要性能指标是存储容量和存取周期（存取周期与存取速度成反比）存储容量：辅存主存缓存；存取速度：缓存主存辅存125 输入输出（I/O）设备输入设备：键盘、鼠标、光笔、数字化仪、图形扫描仪、摄像机等。输出设备：显示器、打印机、绘图仪、磁盘驱动器等。显示器：分为阴极射线管（CRT）和液晶显示（LCD/TFT）两种。其主要性能指标是分辨率。（其他还有如点距、刷新率等）。126 非冯诺伊曼型计算机到目前为止，各种类型的计算机都属于冯诺伊曼型计算机。正在研制中的第五代智能计算机，将具有自动识别自然语言、图形、图像的能力，具有理解和推理的能力，具有知识获取、知识更新的能力，可望突破当前计算机的结构模式。研制朝两个反向努力：1、 创建非冯诺伊曼式语言： LISP、 PROLOG（人工智能语言，用逻辑设计取代程序设计）、 F.P.（供理论研究用的理想语言）2、 创建以人脑神经系统处理信息原理为基础的非冯诺伊曼式的计算机 生物计算机、光子计算机、量子计算机13 软件系统：包括系统软件和应用软件。系统软件：系统软件指管理、监控和维护计算机资源（包括硬件和软件）的软件，主要包括操作系统、各种程序设计语言及其解释编译系统、数据库管理系统等。系统软件中最重要的是操作系统。应用软件：用户利用计算机及其提供的系统软件为解决各种实际问题而编制的计算机程序。 131 操作系统（Operating System）1、常见的操作系统操作系统建立了用户与计算机之间的接口。当前常见的操作系统有DOS（微软公司，Disk Operating System磁盘操作系统）、Windows 9x/Me/NT/2000/XP（微软公司，视窗系列操作系统）、UNIX、Linux、SunOS（升阳公司）、IBM OS/2等。DOS是一个单用户单任务操作系统，Windows 95是一个单用户多任务操作系统，Windows NT/2000/XP等属于多用户多任务操作系统。UNIX（多任务分时操作系统，网络操作系统）：20世纪70年代初期由美国贝尔实验室用C语言开发的。在所有比微机性能更好的工作站型计算机上，都是使用该操作系统。Linux网络操作系统。是一个与UNIX完全兼容的免费操作系统，它的内核全部重新编写，并公布了所有源代码。Linux由芬兰人Linux Torvalds首创，现在已经成为一个稳定可靠、功能完善、性能卓越的操作系统。 2、操作系统的主要功能包括：处理机管理；存储管理；设备管理；文件管理；作业管理。 3、操作系统管理控制方式：A、分时操作系统：一台计算机连接多个终端，分时系统把CPU的运行时间分成很短的时间片，按时间片轮流把CPU分配给各联机作业使用。B、实时操作系统：系统响应速度快，他要求计算机对输入的信息做出及时响应，并在规定时间内完成任务。C、网络操作系统：网络用户与计算机网络之间的接口。通过通信子网实现数据通信，通过资源子网进行数据处理，实现共享。132 程序设计语言世界上第一位程序员：英国著名诗人拜伦的女儿Ada Lovelace程序设计语言是用户用来编写程序的语言。它分为机器语言、汇编语言和高级语言。机器语言是最底层的计算机语言。它的特点是用机器语言编写的程序，每条指令都是二进制形式的指令代码，由和组成。计算机硬件可以直接识别，执行速度快，但不易调试、修改，程序的直观性差、移植性差。所谓指令是指一种规定CPU执行某种特定操作的命令，也称为机器指令，它包括操作码和地址码。 机器语言低级语言编译或解释汇编汇编语言汇编语言是用指令助记符合地址符号书写的指令。用汇编指令编写的程序成为汇编语言源程序。计算机不能直接识别汇编语言编写的源程序，必须由翻译程序翻译成机器语言程序才能执行，执行效率较高，相对机器语言程序而言，易读、易检查、易修改，但其通用性和移植性仍较差。翻译的过程称为，负责翻译的程序称之为汇编程序。高级语言面向对象编程语言（OOPLs） ：C+，Dephi，Visual Basic，Java，SmallTalk，Object Pascal等。Smalltalk是最早的纯面向对象编程语言之一。面向对象编程语言结构化程序设计语言结构化程序设计语言：FORTRAN、BASIC、PASCAL、C等。 Ada语言是迄今为止 最复杂，最完备的软件工具。美国国防部指定的 唯一的一种可用于军用系统开发的语言，我国军方也将Ada做为军内开发标准（GJB 1383程序设计语言Ada）。133 应用软件由于计算机有大量的应用软件，它在生活、生产中的应用很广泛。专门用途的应用软件如字处理软件（如Word）、财务软件、图形处理软件（如PhotoShop）已经深入了我们的生活。计算机常见的应用还包括计算机辅助教学（CAI）、计算机辅助制造（CAM）、计算机辅助设计（CAD）等。1-3-6知识产权 1997 年中华人民共和国刑法 界定了计算机犯罪 1991年 计算机软件保护条例 计算机知识产权方面的法律法规 2001年11月全国青少年网络文明公约针对青少年使用网络，团中央、教育部等部门 2001年12月公布了新的计算机软件保护条例，即计算机软件是受法律保护的，不可以随便复制、盗版。137 计算机病毒计算机病毒指的是会影响计算机系统正常工作的一类特殊的程序，它的主要特点是传播性、潜伏性、破坏性与隐蔽性。按照计算机病毒存在的媒体和传播方式分类，可以把它分为文件型、引导区型、网络型、混合型、宏病毒等。网络病毒通过计算机网络传播感染网络中的可执行文件，文件病毒感染计算机中的文件（如：com，exe等），引导型病毒感染启动扇区（Boot）和硬盘的系统引导扇区（MBR），还有这三种情况的混合型，例如：多型病毒（文件和引导型）感染文件和引导扇区两种目标。计算机病毒通常都具有复杂的算法或者很好的心理学特性。137 数据库（DB-DataBase）1、 数据库的基本概念：在计算机存储设备上存储的数据集合。建立在微型机上的关系型数据库是一张二维表格。2、 数据库特性：（1） 最小冗余：数据尽可能不重复存储（2） 数据共享：数据可以为多个用户程序服务（3） 数据独立性：DB中数据与应用程序不存在依赖关系（4） 安全性：保护DB以防止不合法使用（5） 完整性：存取DB的过程中要确保其正确性、一致性和有效性。3、 常见的数据库管理系统（DBMS）：（1） 高档数据库产品（分布式数据库管理软件）：Oracle，Infomix，Sybase，DB2（2） 中、低档数据库产品(集中式)：Foxpro，DBASE, Access,（3） 数据库开发工具：Access，Visual Basic，Power Builder，SQL Server ,My SQL。基于（Client/Server）客户机/服务器环境中的数据库开发工具。4、 SQL-数据库的结构查询语言 select 学号，姓名 From 学生表 insert into 学生表 values(学号，姓名)14 计算机中的数据表示141 数据类型及其存储:计算机里用到的数据类型主要可以分为两类：表示数量的数值数据和非数值性的符号数据。所有的数据都是以二进制的形式在计算机里处理和存储。143 进制的运算和转换1、N进制的数据就是由0N1这N个数字按照一定的顺序排列组合，运算上逢N进一的数。（即以N为基数的数据）常见的进制有二进制（BINary）、八进制（OCTonary）、十进制（DECimalism），十六进制（HEXadecimal）。二进制的运算分为算术运算与逻辑运算两种：（1） 常用的算术运算（进位和借位）： 加法：0000111011110 减法：0001011101110（2） 常用的逻辑运算（逐位进行）： 逻辑或（OR）：000011101111 逻辑与（AND）：0000101001112、十进制数转换成N进制数：整数部分除N取余，小数部分乘N取整 整数部分的转换：除二取余例如：(19)10(10011)2 小数部分的转换：乘2取整例如：(0.125)10(0.001)2并非所有的十进制小数都能用有限位的二进制小数来表示。如(0.63)10。3、 二进制与十六、八进制的转换1个十六进制位=4个二进制位 1个八进制位=3个二进制位二进制0000000100100011010001010110011116进制01234567二进制1000100110101011110011011110111116进制89ABCDEF表1 二进制与十六进制数字对照表二进制000001010011100101110111八进制01234567表2 二进制与八进制数字对照表4、 N进制数转换成十进制数(各位数字与权植乘积累加) (ABCDE.FG)n =A*n4+B*n3+C*n2+D*n1+E*n0+F*n-1 + G*n-2142 数值数据在计算机中的存储为了解决数据的表示范围问题，计算机中存储的数值数据分为定点数据和浮点数据两类。定点数据是各种数据类型中最简单、最基本的一种数据表示，它用以表示二进制形式具有固定比例换算的量（即小数点的位置固定不变）。由于定点位置的不同，定点数一般分为两类：整数（Integer，小数点固定于最低位右边的数）和小数（Fraction，小数点固定于数的左端，在20与21之间，又称为分数）。计算机中浮点数据表示的基本原理来源于十进制数中使用的科学记数法。一个数N的科学记数法形式可写成：NMRE。其中M代表尾数，E代表阶码，R代表基数。当尾数、阶码采用二进制，基数R2时，就是计算机中的浮点数据表示。浮点数是实数的一种近似表示，存在下溢和上溢，浮点数格式必须兼顾表示范围及表示精度的要求。浮点数的一般表示方式如下：符号阶码E（定点整数）尾数M（定点小数）144 定点数据的编码为了解决数据的正、负问题，定点数据引入数据的原码、反码、补码表示。位运算：not 二进制按位取反 and 二进制按位与 shr 二进制按位右移shl 二进制按位左移 or 二进制按位或 xor 二进制按位异或采用补码制进行运算，所以必须确定该数存储的字节数，再决定该数的补码。原理一个字节表示的数据范围举例原码用最高位（最左位）来表示数的符号，0为正数，1为负数127127共255个数（0）原00000000（0）原100000000010101143，1010101143。反码正数的反码都与它的原码相同，负数的反码则是它的逐位取反（符号位不变）127127共255个数（0）反00000000（0）反11111111(56)原(56)反00111000(56)原10111000(56)反11000111补码正数的补码也与它的原码相同，负数的补码等于它的反码加一（进位自然舍去）128127共256个数(-0)补=11111111+00000001（1）00000000（）补(-1)补=11111111(-2)补=11111110（-128）补=10000000(56)原=(56)反=(56)补00111000（56）补11001000145 非数值数据在计算机中的存储1、ASCII（美国标准信息交换代码）, 一个西文字符用一个7位的ASCII码表示，最高位填0，存储需要一个字节。2、1980年， 信息交换用汉字编码字符集基本集（GB2312-80），字符集收入常用汉字6763个，其中包括一级汉字3755个（按汉语拼音排列），二级汉字3008个（按偏旁部首排列）。将6763个汉字分为94个区，每个区又分为94位。汉字在代码表中的区号、位号就叫做汉字的区位码（例如“国”：25-90）；将汉字的区号、位号各增加32即为国标码（例如“国”：57-122）；国标汉字在计算机内以连续的两个字节来表示。为了和ASCII码区别，这两个字节的最高位都填1，理论上能够表示的汉字数共28128112812816384个汉字，国标汉字在计算机内的编码叫做机内码。3、当前常用的其他汉字字符集编码： 国家标准（GBK）汉字扩展内码规范；台湾汉字编码规范（BIG5）等4、计算机上字符的输出是通过在计算机中预存字形信息库，简称字库（Font），以下以汉字为例，字形有两种表示方法：点阵字形库和轮廓字形库。点阵字形库时一点振兴是描述的汉字字形代码，其点阵的密度决定了汉字的美观清晰度。普通的点阵为1616，更高的有2424、3232、6464等。点阵字形库需要占据大量的存储空间。以1616为例，每个汉字要占用1616位32字节，6763个汉字共占用326763256KB。由于点阵字形库美观程度差、空间占用大，我们现在所采用的一般都是轮廓字形库（包括Windows9x内的宋体、楷体、黑体）。5、 汉字激光照排系统的创始人王选,“汉字印刷术的第二次发明”。15 计算机网络1-5-1、计算机网络： 1969年，美国国防部ARPANET (1) 按照距离分类 网络类型距离适合的对象局域网LAN几米10公里位于一个建筑物或一个单位内城域网MAN10公里100公里 对一个城市的LAN互联位于一座城市中广域网 WAN几百公里几千公里国家，邮电部的CHINANET，CHINAPAC，和CHINADDN网互联网 INTERNET一个洲或洲际（2）拓扑结构：总线型，星形，环形，树形应用层（Application Layer)表示层（Presentation Layer)会话层（Session Layer）传输层（Transport Layer)网络层(Network Layer)数据链路层（Data Link Layer)物理层（Physical Layer)1-5-3、OSI（开放式系统互连参考模型）OSI（开放式系统互连参考模型）是ISO就网络体系提出的一个参考模型，这个模型把网络通信的工作分为7层.1-5-4、TCP/IP协议 TCP/IP协议把Internet网络系统描述成具有4个层次功能的网络模型应用层应用程序间沟通的层，如简单电子邮件传输（SMTP）、文件传输协议（FTP）、网络远程访问协议（Telnet）等传输层提供了节点间的数据传送，应用程序之间的通信服务，主要功能是数据格式化、数据确认和丢失重传等。如传输控制协议（TCP）、用户数据报协议（UDP）等，TCP和UDP给数据包加入传输数据并把它传输到下一层中，这一层负责传送数据，并且确定数据已被送达并接收。互连网络层负责提供基本的数据封包传送功能，让每一块数据包都能够到达目的主机（但不检查是否被正确接收），如网际协议（IP）网络接口层接收IP数据报并进行传输，从网络上接收物理帧，抽取IP数据报转交给下一层，对实际的网络媒体的管理，定义如何使用实际网络（如Ethernet、Serial Line等）来传送数据。1-5-6 、IP地址与子网掩码IPv4地址：32bit位二进制组成，由类型标志、网络标志和主机标识组成。IP地址分为：A、B、C、D、E五类。常用的是A、B、C。 01 8 31A类：0网络号主机号 0 1 2 16 31B类：10网络号主机号 0 1 2 3 24 31C类：110网络号主机号网址范围子网掩码A类l -126 . 0 - 255 . : U/ N0 J% 8 Y7 .0-255 . * l7 G$ c3 |+ v* I: m& r, D1-254 & P255000B类128-191 . 0-255 . 0-255 . I1-25425525500C类192-233 . 0 L0-255 . 0-255 . 1-25425525500 第二代中国教育和科研计算机网CERNET2是中国下一代互联网示范工程CNGI最大的核心网和唯一的全国性学术网，CERNET2全国网络中心位于清华大学。CERNET2具有以下特点： 1 . 是中国第一个IPv6国家主干网。 2 . 是目前世界上规模最大的纯IPv6主干网。 3 . 建成中国下一代IPv6网交换中心。 4 . 采用了自主开发的关键设备及技术，为下一代互联网带动的产业经济打下了坚实基础。 IPV6地址长度为128比特。 2004年3月，CERNET2试验网正式向用户提供IPv6下一代互联网服务。目前，CERNET2已经初具规模。CERNET2已经接入北京大学、清华大学、复旦大学、上海交通大学、浙江大学等100多所国内高校，并与谷歌实现基于IPv6的1Gbps高速互联。1-5-6域名系统及DNS服务器 在Internet网上的主机就可以用“主机名域名”的方式唯一的标识。如：WWWTONGJIEDIJCN名字中WWW为主机名，由服务器管理员命名，TONGJIEDU.CN 为域名，由服务器管理员申请合法可以使用。 DNS服务器：/ Z% N2 6 ?: Z: WT) h提供主机域名与IP地址之间相互转换服务的计算机系统。它保存了一张域名(domain name)和与之相对应的IP地址 (IP address)的表，以解析消息的域名。1-5-7 WEB服务器：WEB服务器也称为WWW(WORLD WIDE WEB)服务器，主要是提供网上信息浏览服务。(1)应用层使用HTTP协议。(2)HTML文档格式：html 超文本标记语言，HTML命令可以说明文字、图形、动画、声音、表格、链接等。网页设计中，超链接：本站点网页之间的联系 或 指向外部的网络资源。标签：本网页之间的跳转。（3)浏览器统一资源定位器(URL)。1-5-8 常见的协议协议中 文在网络模型中的层次TCP/IP协议传输控制协议 / 因特网互联协议传输层/互连网络层Http超文本传输协议应用层FTP文件传输协议应用层SMTP简单电子邮件传输应用层Pop3邮局协议, 个人计算机连接到互联网上的邮件服务器收发邮件的协议应用层Telnet网络远程访问协议应用层2、竞赛与编程环境全国青少年信息学奥林匹克竞赛系列活动简介简称 描 述NOI全国青少年信息学奥林匹克（2011年第28届）NOIP全国青少年信息学奥林匹克联赛(2011年第17届)冬令营全国青少年信息学奥林匹克竞赛冬令营APIO亚洲与太平洋地区信息学奥赛选拔赛（ctsc）选拔参加国际信息学奥林匹克中国代表队的竞赛IOI国际信息学奥林匹克竞赛NOI2009、NOIP2009竞赛环境说明 分类软件版本说明系统软件NOI Linux内核- 2.6.24 NOILinux 1.2操作系统编译器Gcc4.1.2C编译器G+4.1.2C+编译器Freepascal，Fpc2.0.4Pascal编译器调试器Gdb6.6命令行启动Ddd3.3.11命令行启动集成开发环境GUIDE1.0.0单文件程序IDE（C/C+/Pascal）Anjuta1.2.4C/C+IDELazarus0.9.22PascalIDE3、图灵与图灵奖图灵是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。图灵机就是指一个抽象的机器，理想计算机模型。“图灵奖”是美国计算机协会（ACM，Association for C