【精编】高一信息学竞赛班NOIP赛前冲刺培训：基础理论知识-精心整理-.ppt

JSZX汕头金山中学信息竞赛班可编辑1信息学竞赛相关活动介绍vIOI：国际信息学奥林匹克竞赛（InternationalOlympiadinInformatics）每年8月举行，我国连续多年，四名选手全获金牌可编辑2信息学竞赛相关活动介绍vNOI：全国青少年信息学奥林匹克竞赛自1984年至开始，每省派若干名学生组成代表队参加，每年7月底举行。NOI同步进行的还有NOI网上同步赛。可编辑3信息学竞赛相关活动介绍vNOIP：全国青少年信息学奥林匹克联赛(NationalOlympiadinInformaticsinProvinces简称NOIP)自1995年至今，每年10-11月举行，全国在校中学生均可参加。分普及组和提高组。可编辑4信息学竞赛相关活动介绍v冬令营全国青少年信息学奥林匹克竞赛冬令营在每年寒假期间（1月）开展为期一周的培训活动。国家集训队（NOI前50名的选手）正式营员。可编辑5信息学竞赛相关活动介绍vCTSC参加国际信息学奥林匹克竞赛的中国代表队的选拔赛从国家集训队的（获NOI前50名）选手中，经上机比赛及现场答辩，选拔前4名的优胜者，代表中国参加国际IOI。可编辑6信息学竞赛相关活动介绍v信息学奥赛OlympiadinInformaticsv官方网站：v信息技术：ITInformationTechniquevCAI计算机辅助教学vCAD计算机辅助设计可编辑7信息学竞赛相关活动介绍v1984年邓小平说：“计算机的普及要从娃娃做起。”可编辑8计算机简史v计算机发展代别划分代别逻辑元件*年代第一代电子管19461958使用机器语言第二代晶体管19591964使用高级语言第三代集成电路19651970第四代大规模集成电路1971？出现微型机未来计算机发展方向：生物、光、量子计算机可编辑9计算机简史v1946年2月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC，这台计算机占地170平方米，重30吨，用了18000多个电子管，每秒能进行5000次加法运算，其输入设备和输出设备分别为开关和指示灯。可编辑10计算机简史可编辑11计算机简史v1944年，美籍匈牙利数学家冯诺依曼提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。v时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯诺依曼架构。可编辑12计算机简史v其理论要点如下：1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成。2、存储程序思想把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。可编辑13计算机简史vAdaLovelace世界上第一个写程序的人著名英国诗人拜伦之女vADA语言可编辑14计算机简史v图灵（AlanMathisonTuring）：英国数学家，被称为“人工智能之父”v他提出有限状态自动机，即著名的图灵机模型，提出了重要的衡量标准“图灵测试”，对人工智能的发展作出诸多贡献。曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。可编辑15计算机简史v图灵奖：由美国计算机协会于1966年设立，专门奖励对计算机事业有重要贡献的个人，有“计算机界的诺贝尔奖”之称。可编辑16计算机简史v姚期智美籍华人，2000年图灵奖得主，世界著名计算机学家，美国科学院院士，中国科学院外籍院士，2004年起在清华大学担任全职教授。v姚班清华大学“计算机科学实验班”，姚期智于2004年创办，每届20左右名学生。可编辑17计算机简史v我国的计算机发展情况1958年，我国第一台通用数字电子计算机103型机研制成功，每秒运行1500次；1983年，每秒运行一亿次的银河巨型计算机在国防科技大学诞生；1999年“银河IV”1000亿次/秒；可编辑18计算机简史v“天河2号”计算机，2013年底入驻广州的国家超级计算机中心可编辑19计算机简史v计算机分类按体积大小分：巨型机、大型机、小型机、微型机、单片机单片机：指集成在一块芯片上的完整计算机系统，也称微控器。它的使用领域十分广泛，如智能仪表、实时工控、通讯设备、导航系统、家用电器等，用上了单片机的产品常被冠以“智能型”来形容。可编辑20计算机系统的基本组成 v计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、输出设备v计算机系统由硬件和软件两部分组成可编辑21计算机系统的基本组成 v中央处理器CPUCentralProcessingUnit在微机中常被称为微处理器（MPUmicroprocessor）由运算器、控制器和一些寄存器组成。（注意：不要把“寄存器”写成“存储”）；可编辑22计算机系统的基本组成CPU可编辑23计算机系统的基本组成 v运算器进行各种算术运算和逻辑运算；v控制器是计算机的指挥系统，它的操作过程是：取指令分析指令执行指令；可编辑24计算机系统的基本组成 CPU的主要性能指标：v主频：即计算机CPU的主时钟频率，主频越高，速度越快。v字长：一次性能并行处理的二进制数码位数；例如：某微机CPU型号为P42.6G，其中2.6G指的就是CPU的主时钟频率；AMD64位CPU，其中64位指的是CPU的字长。可编辑25计算机系统的基本组成v存储器的分级结构目前在计算机系统中，通常采用三级存储器结构：可编辑26计算机系统的基本组成可编辑27计算机系统的基本组成 v内部存储器：中央处理器能直接访问的存储器，它包括快速缓冲存储器和主存储器。内存也常泛指主存，但严格上说，只有当内存中只有主存，而没有快速缓冲存储器时，才能称为主存。v外部存储器：中央处理器不能直接访问的存储器，外部存储器中的信息必须调入内存后才能为中央处理器处理。可编辑28计算机系统的基本组成 v存储器速度比较：内存外存快存主存辅存可编辑29计算机系统的基本组成 v快速缓冲存储器（Cache）：v简称快存或缓存，速度比主存储器快，但容量较小，位于CPU与主存之间，用以加快机器速度。可编辑30计算机系统的基本组成v主存储器按读写功能，可分只读存储器（ROM）和随机存储器（RAM）两种。只读存储器（ROMReadOnlyMemory）：只能读出，不能写，且原来所存信息不会因断电而丢失。*PROM可编程的只读存储器：可改写一次。*EPROM可擦可编程的只读存储器：可多次改写。随机存储器（RAMRandomAccessMemory）：可以读出和写入信息，RAM中存储的信息将因断电或机器重新启动而丢失。可编辑31计算机系统的基本组成v外部存储器：也称为辅助存储器，一般容量较大，速度比主存较慢。硬盘（Harddisk）：目前的硬盘大多采用了温彻斯特技术，所以又称为“温盘”；软盘（FloppyDisk）：常见的是3.5英寸1.44MB光盘存储器（CD-ROM）：只能读，不能写；CD盘片的存储量大约是650MB，DVD盘片容量大约是4.7GB。*CDRW：可读写光驱，能读又能写。移动存储：主要有移动硬盘和移动闪存盘。可编辑32计算机系统的基本组成v输入设备键盘（Keyboard）、鼠标（Mouse）、手写笔、触摸屏、麦克风扫描仪（Scanner）、视频输入设备、条形码扫描器v输出设备显示器（Monitor）：目前主要有CRT（阴极射线管）显示器和LCD液晶显示器。打印机（Printer）：主要有针式打印机、喷墨打印机、激光打印机。绘图仪音箱可编辑33计算机系统的基本组成v总线（Bus）总线是计算机各部件之间传输信息的公共通道，由多根导线组成，根据传输信息的不同，可分为数据总线、地址总线和控制总线。可编辑34计算机系统的基本组成v计算机软件可分为系统软件和应用软件两大类。v系统软件：v包括：(1)操作系统软件，如：vDOS、Windows95/98/2000、Unix、Linux、WindowsNT；v(2)语言的编译软件vFreePascal、Dephi、C+Builder等；v(3)某些数据库系统也被归属于系统软件，但此项常有争议，v如foxbase、Foxpro、SQL等；v注意，系统软件不等于操作系统！v应用软件：为了某个应用目的而编写的软件，主要有文字处理软件、电子表格软件、数据库管理软件、辅助设计软件、实时控制软件等。可编辑35信息数字化 v数字化信息的计量可编辑36信息数字化vASCII码(AmericanStandardCodeforInformationInterchange)美国的标准信息交换代码将每个字符用7位的二进制数来表示，共有128种状态可编辑37信息数字化v计算机中的数据用二进制表示v分为有符号数和无符号数有符号数在数值的最高位前加0或1表示数值的符号（正/负）常用的机器码有原码、反码、补码原码：最高位表示符号（正0，负1），其它位表示数值。如：X1011101X原01011101X1011101X原11011101机器码可编辑38信息数字化反码：正数的反码与原码相同，符号位用0表示，数值位不变；负数的符号位用1表示，数值位为原码数值位按位取反。如：X1011101X反01011101X1011101X反10100010可编辑39信息数字化补码：正数的补码与原码相同，负数的补码位反码加1形成。如：X1011101X补01011101X1011101X补10100011可编辑40信息数字化v为什么要设反码、补码？例如：1+(-1)、1-1，用原码计算，则须分加减、正负进行处理，比较复杂；而利用补码计算：1+(-1)=00000001补+11111111补=00000000补 1-1=1+(-1)=设计补码的目的是：使符号位与数值部分一起参加运算，简化运算规则.使减法运算转换为加法运算，简化计算机中运算器的线路设计可编辑41信息数字化v定点数、浮点数定点数：是指数据中小数点的位置是固定不变。小数点固定在有效数据最低位右边，数据表示为整数；小数点固定在有效数据最高位之前，数据表示为纯小数。在机器中，定点数的形式为：符号位（正/负）有效数据可编辑42信息数字化浮点数：指数据中的小数点位置没有预先固定。任何一个十进制数N可用科学计数法表示：同样，二进制数N可表示为：（E称为阶码，M称为尾数，统一用纯小数表示。）计算机中的浮点数的形式为：阶符阶码数符尾数阶符表示阶码的符号，正0负1；数符表示N的正负，同样，正0负1。可编辑43信息数字化v二进制数据经过传送、存取等环节，会发生误码（1变成0或0变成1），为了发现和纠正误码，在原始数据后增加一个或若干个校验位，进行数据校验。1、奇偶校验码这是最基础的一种检验码，是由n为有效数据位和1个校验位组成校验码，这种校验码仅能发现错误（奇数个位出错的情况），不能纠正误码。2、能纠正误码的校验码海明码：是一种多重(复式)奇偶检错系统，每一个奇偶位被编在传输码字的特定位置上。循环冗余校验码（CRC码）：在串行传送（磁盘、通讯）中广泛采用。可编辑44操作系统只认得0和1可编辑45操作系统vDOS可编辑46操作系统vDOS命令dircd可编辑47操作系统vUnix、Linux可编辑48操作系统vWindowsx系列：Windows98，WindowsXP，WindowsVista，Windows7，Windows8Windows10是微软公司新一代操作系统。Windows10正式版将于2015年发布，将涵盖PC、平板电脑、手机、XBOX和服务器端可编辑49操作系统v操作系统的功能主要有：处理机(CPU)管理、作业管理、存储管理、文件管理、设备管理。CPU管理：进程控制、进程同步、进程通信、进程调度作业管理：作业调度、作业控制文件管理：存储空间管理、目录管理、文件读写、文件保护、用户接口存储管理：内存分配、内存保护、地址映射、内存扩充设备管理：缓冲管理、设备分配、设备处理、虚拟设备功能可编辑50操作系统v进程进程是程序的一次执行，是可以和别的计算并发执行的计算；是一个程序及其数据，在处理机（CPU）上顺序执行时所发生的活动；进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位；可编辑51操作系统v进程的状态就绪、执行、等待或称“挂起”、“阻塞”当进程获得所有必需资源时，排入等待的队列，称为“就绪”状态；当进程已获得CPU，则处于“执行”态；当进程必需资源不满足时，则处于“等待”状态，当资源获得时又转让“就绪”态。可编辑52操作系统v进程死锁原因：多个进程因为竞争资源，或执行时推进的顺序不当，或相互通信而永久阻塞现象。产生死锁的四个必要条件：互斥、占有且等待、非剥夺、循环等待。解决死锁的方法：1、预防死锁：(a)禁止“互斥”条件(b)禁止“占有且等待”条件：一次性分配策略(c)禁止“不剥夺”条件：剥夺资源法(d)禁止“循环等待”条件：资源有序分配策略2、避免死锁：银行家算法3、检测并解除死锁可编辑53数据库vDBMS数据库管理系统（DBMSDataBaseManagementSystem）是使用户可以定义、创建、维护数据库以及对数据库有限制访问的软件系统。用户通过SQL语言或窗口操作对数据库进行插入、删除、更新、检索等操作。可编辑54数据库v机器世界的数据模型：层次模型、网状模型、关系模型v关系模型采用二维表格结构来表示实体以及实体之间联系的数据模型，目前的数据库管理软件几乎都支持关系模型。常用的数据库软件：Orcal、Sybase、SOLServer、Access、Foxpro等。这些都是关系型数据库管理系统。可编辑55数据库可编辑56数据库可编辑57数据库vSQL语言vSQL（StructuredQueryLanguage，结构化查询语言）是关系数据库的标准语言，由IBM公司研制。v常用命令有CREATTABLE（创建表）、ALTER（插入新字段）、CREATEINDEX（创建索引）、INSERTINTO（插入纪录）、UPDATE（修改）、SELECTFROM（查询）等。可编辑58地址与内容：指向内存地址：该地址的内容变量地址内容X101100105y00101110Bx:=5;w:=x;z:=w;可编辑59地址与内容v2007年联赛第4题：programs402;vara,b:integer;x,y:integer;procedurefun(a,b:integer);vark:integer;begink:=a;a:=b;b:=k;end;begina:=3;b:=6;x:=a;y:=b;fun(x,y);write(No.1:,a,b,);fun(a,b);writeln(No.2:,a,b);end.可编辑60