高一信息学竞赛班NOIP赛前冲刺培训课件：基础理论知识.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title,汕头金山中学信息竞赛班,基础知识,信息学竞赛相关活动介绍,IOI,：国际信息学奥林匹克竞赛,（,International Olympiad in Informatics,）,每年,8,月举行，我国连续多年，四名选手全获金牌,信息学竞赛相关活动介绍,NOI,：全国青少年信息学奥林匹克竞赛,自,1984,年至开始，每省派若干名学生组成代表队参加，每年,7,月底举行。,NOI,同步进行的还有,NOI,网上同步赛。,信息学竞赛相关活动介绍,NOIP,：全国青少年信息学奥林匹克联赛,(National Olympiad in Informatics in Provinces,简称,NOIP),自,1995,年至今，每年,10-11,月举行，全国在校中学生均可参加。分普及组和提高组。,信息学竞赛相关活动介绍,冬令营,全国青少年信息学奥林匹克竞赛冬令营在每年寒假期间（,1,月）开展为期一周的培训活动。国家集训队（,NOI,前,50,名的选手）正式营员。,信息学竞赛相关活动介绍,CTSC 参加国际信息学奥林匹克竞赛的中国代表队的选拔赛,从国家集训队的（获,NOI,前,50,名）选手中，经上机比赛及现场答辩，选拔前,4,名的优胜者，代表中国参加国际,IOI,。,信息学竞赛相关活动介绍,信息学奥赛,Olympiad in Informatics,官方网站：,信息技术：,ITInformation Technique,CAI,计算机辅助教学,CAD,计算机辅助设计,信息学竞赛相关活动介绍,1984,年邓小平说：“计算机的普及要从娃娃做起。”,计算机简史,计算机发展代别划分,代别,逻辑元件,*年代,第一代,电子管,1946,1958,使用机器语言,第二代,晶体管,1959,1964,使用高级语言,第三代,集成电路,1965,1970,第四代,大规模集成电路,1971,？,出现微型机,未来计算机发展方向：生物、光、量子计算机,计算机简史,1946,年,2,月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机,ENIAC,，这台计算机占地,170,平方米，重,30,吨，用了,18000,多个电子管，每秒能进行,5000,次,加法运算，其输入设备和输出设备分别为,开关,和,指示灯,。,计算机简史,计算机简史,1944,年，美籍匈牙利数学家 冯,诺依曼 提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。,时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯,诺依曼架构。,计算机简史,其理论要点如下：,1,、计算机硬件设备由,存储器,、,运算器,、,控制器,、,输入设备,和,输出设备,5,部分组成。,2,、存储程序思想,把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。,计算机简史,Ada Lovelace,世界上第一个写程序的人,著名英国诗人拜伦之女,ADA语言,计算机简史,图灵（,Alan Mathison Turing,）：英国数学家，被称为“人工智能之父”,他提出有限状态自动机，即著名的图灵机模型，提出了重要的衡量标准“,图灵测试,”，对人工智能的发展作出诸多贡献。曾协助军方破解德国的著名密码系,统,Enigma,，帮助盟军取得了二战的胜利。,计算机简史,图灵奖：由美国计算机协会于,1966,年设立，专门奖励对计算机事业有重要贡献的个人，有“计算机界的诺贝尔奖”之称。,计算机简史,姚期智,美籍华人，,2000,年图灵奖得主，世界著名计算机学家，美国科学院院士，中国科学院外籍院士，,2004,年起在清华大学担任全职教授。,姚班,清华大学“计算机科学实验班”，姚期智于,2004,年创办，每届,20,左右名学生。,计算机简史,我国的计算机发展情况,1958,年，我国第一台通用数字电子计算机,103,型机研制成功，每秒运行,1500,次；,1983,年，每秒运行一亿次的银河巨型计算机在,国防科技大学诞生；,1999,年“银河,IV”1000,亿次,/,秒；,计算机简史,“天河2号”计算机，2013年底入驻广州的国家超级计算机中心,计算机简史,计算机分类,按体积大小分：巨型机、大型机、小型机、,微型机、单片机,单片机：指集成在一块,芯片,上的完整计算机系统，也称微控器。它的使用领域十分广泛，如智能仪表、实时工控、通讯设备、导航系统、家用电器等，用上了单片机的产品常被冠以“智能型”来形容。,计算机系统的基本组成,计算机硬件由五大部分组成：,运算器、控制器、存储器、,输入设备、输出设备,计算机系统由硬件和软件两部分组成,计算机系统的基本组成,中央处理器,CPUCentral Processing Unit,在微机中常被称为微处理器,（,MPUmicroprocessor,）,由运算器、控制器和一些寄存器组成。,（注意：不要把“寄存器”写成“存储”）；,计算机系统的基本组成,CPU,计算机系统的基本组成,运算器进行各种算术运算和逻辑运算；,控制器是计算机的指挥系统，,它的操作过程是：,取指令,分析指令,执行指令；,计算机系统的基本组成,CPU,的主要性能指标：,主频：即计算机,CPU,的主时钟频率，主频越高，速度越快。,字长：一次性能并行处理的二进制数码位数；,例如：某微机,CPU,型号为,P4 2.6G,，其中,2.6G,指的就是,CPU,的主时钟频率；,AMD64,位,CPU,，其中,64,位指的是,CPU,的字长。,计算机系统的基本组成,存储器的分级结构,目前在计算机系统中，通常采用三级存储器结构：,计算机系统的基本组成,计算机系统的基本组成,内部存储器：中央处理器能直接访问的存储器，它包括快速缓冲存储器和主存储器。内存也常泛指主存，但严格上说，只有当内存中只有主存，而没有快速缓冲存储器时，才能称为主存。,外部存储器：中央处理器不能直接访问的存储器，外部存储器中的信息必须调入内存后才能为中央处理器处理。,计算机系统的基本组成,存储器速度比较：,内存,外存,快存,主存,辅存,计算机系统的基本组成,快速缓冲存储器（,Cache,）：,简称快存或缓存，速度比主存储器快，但容量较小，位于,CPU,与主存之间，用以加快机器速度。,计算机系统的基本组成,主存储器按读写功能，可分只读存储器（,ROM,）和随机存储器（,RAM,）两种。,只读存储器（,ROMRead Only Memory,）：只能读出，不能写，且原来所存信息不会因断电而丢失。,*,PROM,可编程的只读存储器：可改写一次。,*,EPROM,可擦可编程的只读存储器：可多次改写。,随机存储器（,RAMRandom Access Memory,）：可以读出和写入信息，,RAM,中存储的信息将因断电或机器重新启动而丢失。,计算机系统的基本组成,外部存储器：也称为辅助存储器，一般容量较大，速度比主存较慢。,硬盘（,Hard disk,）：目前的硬盘大多采用了温彻斯特技术，所以又称为“温盘”；,软盘（,Floppy Disk,）：常见的是,3.5,英寸,1.44 MB,光盘存储器（,CD-ROM,）：只能读，不能写；,CD,盘片的存储量大约是,650 MB,，,DVD,盘片容量大约是,4.7GB,。,*,CD,RW,：可读写光驱，能读又能写。,移动存储：主要有移动硬盘和移动闪存盘。,计算机系统的基本组成,输入设备,键盘（,Keyboard,）、鼠标（,Mouse,）、手写笔、触摸屏、麦克风,扫描仪（,Scanner,）、视频输入设备、条形码扫描器,输出设备,显示器（,Monitor,）：目前主要有,CRT,（阴极射线管）显示器和,LCD,液晶显示器。,打印机（,Printer,）：主要有针式打印机、喷墨打印机、激光打印机。,绘图仪,音箱,计算机系统的基本组成,总线（,Bus,）,总线是计算机各部件之间传输信息的公共通道，由多根导线组成，根据传输信息的不同，可分为数据总线、地址总线和控制总线。,计算机系统的基本组成,计算机软件可分为系统软件和应用软件两大类。,系统软件：,包括：,(1),操作系统软件，如：,DOS,、,Windows95/98/2000,、,Unix,、,Linux,、,WindowsNT,；,(2),语言的编译软件,Free Pascal,、,Dephi,、,C+Builder,等；,(3),某些数据库系统也被归属于系统软件，但此项常有争议，,如,foxbase,、,Foxpro,、,SQL,等；,注意，系统软件不等于操作系统！,应用软件：为了某个应用目的而编写的软件，主要有文字处理软件、电子表格软件、数据库管理软件、辅助设计软件、实时控制软件等。,信息数字化,数字化信息的计量,信息数字化,ASCII,码,(American Standard Code for Information Interchange),美国的标准信息交换代码,将每个,字符,用,7,位的二进制数来表示，共有,128,种状态,信息数字化,计算机中的数据用二进制表示,分为有符号数和无符号数,有符号数在数值的最高位前加,0,或,1,表示数值的符号（正,/,负）,常用的机器码有原码、反码、补码,原码：最高位表示符号（正,0,，负,1,），其它位表示数值。,如：,X,1011101 X,原,01011101,X,1011101 X,原,11011101,机器码,信息数字化,反码：,正数的反码与原码相同，符号位用,0,表示，数值位不变；,负数的符号位用,1,表示，数值位为原码数值位按位取反。,如：,X,1011101 X,反,01011101,X,1011101 X,反,10100010,信息数字化,补码：,正数的补码与原码相同，,负数的补码位反码加,1,形成。,如：,X,1011101 X,补,01011101,X,1011101 X,补,10100011,信息数字化,为什么要设反码、补码？,例如：,1+(-1),、,1-1,，用原码计算，则须分加减、,正负进行处理，比较复杂；,而利用补码计算：,1+(-1)=00000001,补,[phone],补,=00000000,补,1-1=1+(-1)=,设计补码的目的是：,使符号位与数值部分一起参加运算，简化运算规则,.,使减法运算转换为加法运算，简化计算机中运算器的线路设计,信息数字化,定点数、浮点数,定点数：是指数据中小数点的位置是固定不变。,小数点固定在有效数据最低位右边，数据表示为整数；,小数点固定在有效数据最高位之前，数据表示为纯小数。,在机器中，定点数的形式为：,符号位（正,/,负）,有效数据,信息数字化,浮点数：指数据中的小数点位置没有预先固定。,任何一个十进制数,N,可用科学计数法表示：,同样，二进制数,N,可表示为：,（,E,称为阶码，,M,称为尾数，统一用纯小数表示。）,计算机中的浮点数的形式为：,阶符,阶码,数符,尾数,阶符表示阶码的符号，正,0,负,1,；数符表示,N,的正负，同样，正,0,负,1,。,信息数字化,二进制数据经过传送、存取等环节，会发生误码（,1,变成,0,或,0,变成,1,），为了发现和纠正误码，在原始数据后增加一个或若干个校验位，进行数据校验。,1,、奇偶校验码,这是最基础的一种检验码，是由,n,为有效数据位和,1,个校验位组成校验码，这种校验码仅能发现错误（奇数个位出错的情况），不能纠正误码。,2,、能纠正误码的校验码,海明码：是一种多重,(,复式,),奇偶检错系统，每一个奇偶位被编在传输码字的特定位置上。,循环冗余校验码（,CRC,码）：在串行传送（磁盘、通讯）中广泛采用。,操作系统,只认得,0,和,1,操作系统,DOS,操作系统,DOS命令,dir,cd,操作系统,Unix、Linux,操作系统,Windowsx,系列：,Windows 98,，,Windows XP,，,Windows Vista,，,Windows 7,，,Windows 8,Windows 10,是微软公司新一代操作系统。,Windows 10,正式版将于,2015,年发布，将涵盖,PC,、平板电脑、手机、,XBOX,和服务器端,操作系统,操作系统的功能主要有：,处理机,(CPU),管理、作业管理、存储管理、,文件管理、设备管理。,CPU,管理：进程控制、进程同步、进程通信、进程调度,作业管理：作业调度、作业控制,文件管理：存储空间管理、目录管理、文件读写、,文件保护、用户接口,存储管理：内存分配、内存保护、地址映射、内存扩充,设备管理：缓冲管理、设备分配、设备处理、虚拟设备功能,操作系统,进程,进程是程序的一次执行，是可以和别的计算并发执行的计算；,是一个程序及其数据，在处理机（,CPU,）上顺序执行时所,发生的活动；,进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位；,操作系统,进程的状态,就绪、执行、等待,或称“挂起”、“阻塞”,当进程获得所有必需资源时，排入等待的队列，称为“就绪”状态；,当进程已获得,CPU,，则处于“执行”态；,当进程必需资源不满足时，则处于“等待”,状态，当资源获得时又转让“就绪”态。,操作系统,进程死锁,原因,：,多个进程因为竞争资源，或执行时推进的顺序不当，,或相互通信而永久阻塞现象。,产生死锁的四个必要条件：,互斥、占有且等待、非剥夺、循环等待。,解决死锁的方法：,1,、预防死锁：,(a),禁止“互斥”条件,(b),禁止“占有且等待”条件：一次性分配策略,(c),禁止“不剥夺”条件：剥夺资源法,(d),禁止“循环等待”条件：资源有序分配策略,2,、避免死锁：银行家算法,3,、检测并解除死锁,数据库,DBMS,数据库管理系统（,DBMSData Base Management System,）是使用户可以定义、创建、维护数据库以及对数据库有限制访问的软件系统。用户通过,SQL,语言或窗口操作对数据库进行插入、删除、更新、检索等操作。,数据库,机器世界的数据模型：层次模型、网状模型、关系模型,关系模型采用二维表格结构来表示实体以及实体之间联系的数据模型，目前的数据库管理软件几乎都支持关系模型。,常用的数据库软件：,Orcal,、,Sybase,、,SOL Server,、,Access,、,Foxpro,等。,这些都是关系型数据库管理系统。,数据库,数据库,数据库,SQL,语言,SQL,（,Structured Query Language,，结构化查询语言）是关系数据库的标准语言，由,IBM,公司研制。,常用命令有,CREAT TABLE,（创建表）、,ALTER,（插入新字段）、,CREATE INDEX,（创建索引）、,INSERT INTO,（插入纪录）、,UPDATE,（修改）、,SELECTFROM,（查询）等。,地址与内容,：,指向内存地址,：,该地址的内容,变量,地址,内容,X,10110010,5,y,00101110,B,x:=5;,w:=x;,z:=w;,地址与内容,2007,年联赛第,4,题：,program s402;,var a,b:integer;,x,y:integer;,procedure fun(a,b:integer);,var k:integer;,begin k:=a;a:=b;b:=k;end;,begin,a:=3;b:=6;,x:=a;y:=b;,fun(x,y);,write(No.1:,a,b,);,fun(a,b);,writeln(No.2:,a,b);,end.,