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

1、 JSZX汕头金山中学信息竞赛班汕头金山中学信息竞赛班信息学竞赛相关活动介绍vIOIIOI：国际信息学奥林匹克竞赛：国际信息学奥林匹克竞赛 （International Olympiad in InformaticsInternational Olympiad in Informatics）每年每年8 8月举行，我国连续多年，四名选手全获金牌月举行，我国连续多年，四名选手全获金牌信息学竞赛相关活动介绍v NOI NOI：全国青少年信息学奥林匹克竞赛：全国青少年信息学奥林匹克竞赛 自自19841984年至开始，每省派若干名学生组成代年至开始，每省派若干名学生组成代表队参加，每年表队参加，每年7

2、7月底举行。月底举行。NOINOI同步进行的还有同步进行的还有NOINOI网上同步赛。网上同步赛。 信息学竞赛相关活动介绍vNOIPNOIP：全国青少年信息学奥林匹克联赛：全国青少年信息学奥林匹克联赛 (National Olympiad in Informatics in Provinces(National Olympiad in Informatics in Provinces 简称简称NOIP)NOIP)自自19951995年至今，每年年至今，每年10-1110-11月举行，全国在校中学月举行，全国在校中学生均可参加。分普及组和提高组。生均可参加。分普及组和提高组。 信息学竞赛相关活动

3、介绍v 冬令营冬令营全国青少年信息学奥林匹克竞赛冬令营在每年寒全国青少年信息学奥林匹克竞赛冬令营在每年寒假期间（假期间（1 1月）开展为期一周的培训活动。国家集月）开展为期一周的培训活动。国家集训队（训队（NOINOI前前5050名的选手）正式营员。名的选手）正式营员。 信息学竞赛相关活动介绍v CTSC CTSC 参加国际信息学奥林匹克竞赛参加国际信息学奥林匹克竞赛的中国代表队的选拔赛的中国代表队的选拔赛从国家集训队的（获从国家集训队的（获NOINOI前前5050名）选手中，经上机名）选手中，经上机比赛及现场答辩，选拔前比赛及现场答辩，选拔前4 4名的优胜者，代表中国名的优胜者，代表中国参加

4、国际参加国际IOIIOI。 信息学竞赛相关活动介绍v信息学奥赛信息学奥赛 Olympiad in Informaticsv官方网站：官方网站：v信息技术：信息技术：ITITInformation TechniqueInformation Technique vCAICAI计算机辅助教学计算机辅助教学vCADCAD计算机辅助设计计算机辅助设计 信息学竞赛相关活动介绍v19841984年邓小平说：年邓小平说：“计算机的普及要从娃娃做起。计算机的普及要从娃娃做起。” 计算机简史v计算机发展代别划分计算机发展代别划分 代别代别逻辑元件逻辑元件* *年代年代第一代第一代电子管电子管19461946195

5、81958使用机器语言使用机器语言第二代第二代晶体管晶体管1959195919641964使用高级语言使用高级语言第三代第三代集成电路集成电路1965196519701970第四代第四代大规模集成电路大规模集成电路19711971？出现微型机出现微型机未来计算机发展方向：未来计算机发展方向： 生物、光、量子计算机生物、光、量子计算机 计算机简史v19461946年年2 2月，在美国宾夕法尼亚大学诞生了世界上月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机第一台电子计算机 ENIACENIAC ，这台计算机占地，这台计算机占地170170平方米，重平方米，重3030吨，用了吨，用了18000

6、18000多个电子管，每秒能多个电子管，每秒能进行进行50005000次次加法运算，其输入设备和输出设备分加法运算，其输入设备和输出设备分别为别为开关开关和和指示灯指示灯。 计算机简史计算机简史v19441944年，美籍匈牙利数学家年，美籍匈牙利数学家 冯冯诺依曼诺依曼 提出计提出计算机基本结构和工作方式的设想，为计算机的诞算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。生和发展提供了理论基础。v时至今日，尽管计算机软硬件技时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体术飞速发展，但计算机本身的体系结构并没有明显的突破，当今系结构并没有明显的突破，当今的计算机仍属于

7、冯的计算机仍属于冯诺依曼架构。诺依曼架构。计算机简史v其理论要点如下：其理论要点如下：1 1、计算机硬件设备由、计算机硬件设备由存储器存储器、运算器运算器、控制器控制器、输入设备输入设备和和输出设备输出设备5 5部分组成。部分组成。2 2、存储程序思想、存储程序思想把计算过程描述为由许多命令把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理输入计算机，计算机对已存入的程序和数据处理后，输出结果。后，输出结果。 计算机简史vAda Lovelace Ada Lovelace 世界上第一个写程序的

8、人世界上第一个写程序的人著名英国诗人拜伦之女著名英国诗人拜伦之女vADAADA语言语言计算机简史v 图灵（图灵（Alan Mathison TuringAlan Mathison Turing）：英国数学家，被称为）：英国数学家，被称为“人工智能之父人工智能之父”v 他提出有限状态自动机，即著名的图灵机模型，提出了重他提出有限状态自动机，即著名的图灵机模型，提出了重要的衡量标准要的衡量标准“图灵测试图灵测试”，对人工智能的发展作出诸多，对人工智能的发展作出诸多贡献。曾协助军方破解德国的著名密码系贡献。曾协助军方破解德国的著名密码系 统统EnigmaEnigma，帮助盟军取得了二战的胜利。，帮助

9、盟军取得了二战的胜利。 计算机简史v图灵奖：由美国计算机协会于图灵奖：由美国计算机协会于19661966年设立，年设立，专门奖励对计算机事业有重要贡献的个人，专门奖励对计算机事业有重要贡献的个人，有有“计算机界的诺贝尔奖计算机界的诺贝尔奖”之称。之称。 计算机简史v姚期智姚期智美籍华人，美籍华人，20002000年图灵奖得主，世年图灵奖得主，世界著名计算机学家，美国科学院院界著名计算机学家，美国科学院院士，中国科学院外籍院士，士，中国科学院外籍院士，20042004年年起在清华大学担任全职教授。起在清华大学担任全职教授。 v姚班姚班清华大学清华大学“计算机科学实验班计算机科学实验班”，姚期智，

10、姚期智于于20042004年创办，每届年创办，每届2020左右名学生。左右名学生。计算机简史v我国的计算机发展情况我国的计算机发展情况 19581958年，我国第一台通用数字电子计算机年，我国第一台通用数字电子计算机103103 型机研制成功，每秒运行型机研制成功，每秒运行15001500次；次；19831983年，每秒运行一亿次的银河巨型计算机在年，每秒运行一亿次的银河巨型计算机在 国防科技大学诞生；国防科技大学诞生；19991999年年“银河银河IVIV”10001000亿次亿次/ /秒；秒； 计算机简史v “天河天河2 2号号”计算机，计算机，20132013年底入驻广州年底入驻广州的国

11、家超级计算机中心的国家超级计算机中心计算机简史v计算机分类计算机分类 按体积大小分：巨型机、大型机、小型机、按体积大小分：巨型机、大型机、小型机、 微型机、单片机微型机、单片机单片机：指集成在一块单片机：指集成在一块芯片芯片上的完整计算机系上的完整计算机系统，也称微控器。它的使用领域十分广泛，如统，也称微控器。它的使用领域十分广泛，如智能仪表、实时工控、通讯设备、导航系统、智能仪表、实时工控、通讯设备、导航系统、家用电器等，用上了单片机的产品常被冠以家用电器等，用上了单片机的产品常被冠以“智能型智能型”来形容。来形容。 计算机系统的基本组成计算机系统的基本组成 v计算机硬件由五大部分组成：计算

12、机硬件由五大部分组成： 运算器、控制器、存储器、运算器、控制器、存储器、 输入设备、输出设备输入设备、输出设备v计算机系统由硬件和软件两部分组成计算机系统由硬件和软件两部分组成 计算机系统的基本组成计算机系统的基本组成 v中央处理器中央处理器 CPUCPUCentral Processing UnitCentral Processing Unit 在微机中常被称为微处理器在微机中常被称为微处理器（MPUMPUmicroprocessormicroprocessor） 由运算器、控制器和一些寄存器组成。由运算器、控制器和一些寄存器组成。（注意：不要把（注意：不要把“寄存器寄存器”写成写成“存存储

13、储”）；）； 计算机系统的基本组成计算机系统的基本组成CPU计算机系统的基本组成计算机系统的基本组成 v运算器进行各种算术运算和逻辑运算；运算器进行各种算术运算和逻辑运算； v控制器是计算机的指挥系统，控制器是计算机的指挥系统， 它的操作过程是：它的操作过程是： 取指令取指令分析指令分析指令执行指令；执行指令；计算机系统的基本组成计算机系统的基本组成 CPUCPU的主要性能指标：的主要性能指标：v主频：即计算机主频：即计算机CPUCPU的主时钟频率，主频越高，的主时钟频率，主频越高，速度越快。速度越快。v字长：一次性能并行处理的二进制数码位数；字长：一次性能并行处理的二进制数码位数；例如：某微

14、机例如：某微机CPUCPU型号为型号为P4 2.6GP4 2.6G，其中，其中2.6G2.6G指的指的就是就是CPUCPU的主时钟频率；的主时钟频率；AMD64AMD64位位CPUCPU，其中，其中6464位位指的是指的是CPUCPU的字长。的字长。 计算机系统的基本组成计算机系统的基本组成v存储器的分级结构存储器的分级结构 目前在计算机系统中，通常采用三级存储器结构：目前在计算机系统中，通常采用三级存储器结构： 计算机系统的基本组成计算机系统的基本组成计算机系统的基本组成计算机系统的基本组成 v内部存储器：中央处理器能直接访问的存储器，内部存储器：中央处理器能直接访问的存储器，它包括快速缓冲

15、存储器和主存储器。内存也常泛它包括快速缓冲存储器和主存储器。内存也常泛指主存，但严格上说，只有当内存中只有主存，指主存，但严格上说，只有当内存中只有主存，而没有快速缓冲存储器时，才能称为主存。而没有快速缓冲存储器时，才能称为主存。v外部存储器：中央处理器不能直接访问的存储器，外部存储器：中央处理器不能直接访问的存储器，外部存储器中的信息必须调入内存后才能为中央外部存储器中的信息必须调入内存后才能为中央处理器处理。处理器处理。计算机系统的基本组成计算机系统的基本组成 v存储器速度比较：存储器速度比较： 内存内存 外存外存 快存快存 主存主存 辅存辅存计算机系统的基本组成计算机系统的基本组成 v快

16、速缓冲存储器（快速缓冲存储器（CacheCache）：）：v简称快存或缓存，速度比主存储器快，但简称快存或缓存，速度比主存储器快，但容量较小，位于容量较小，位于CPUCPU与主存之间，用以加快与主存之间，用以加快机器速度。机器速度。 计算机系统的基本组成计算机系统的基本组成v 主存储器按读写功能，可分只读存储器（主存储器按读写功能，可分只读存储器（ROMROM）和随机存）和随机存储器（储器（RAMRAM）两种。）两种。 只读存储器（只读存储器（ROMROMRead Only MemoryRead Only Memory）：只能读出，）：只能读出，不能写，且原来所存信息不会因断电而丢失。不能写，

17、且原来所存信息不会因断电而丢失。 * * PROM PROM 可编程的只读存储器：可改写一次。可编程的只读存储器：可改写一次。 * * EPROM EPROM 可擦可编程的只读存储器：可多次改写。可擦可编程的只读存储器：可多次改写。 随机存储器（随机存储器（RAMRAMRandom Access MemoryRandom Access Memory）：可以）：可以读出和写入信息，读出和写入信息，RAMRAM中存储的信息将因断电或机器重新中存储的信息将因断电或机器重新启动而丢失。启动而丢失。计算机系统的基本组成计算机系统的基本组成v外部存储器：也称为辅助存储器，一般容量较大，外部存储器：也称为辅

18、助存储器，一般容量较大，速度比主存较慢。速度比主存较慢。硬盘（硬盘（Hard diskHard disk）：目前的硬盘大多采用了温彻斯）：目前的硬盘大多采用了温彻斯特技术，所以又称为特技术，所以又称为“温盘温盘”；软盘（软盘（Floppy DiskFloppy Disk）：常见的是）：常见的是3.53.5英寸英寸1.44 MB1.44 MB光盘存储器（光盘存储器（CD-ROMCD-ROM）：只能读，不能写；）：只能读，不能写； CDCD盘片的存储量大约是盘片的存储量大约是650 MB650 MB，DVDDVD盘片容量大约盘片容量大约是是4.7GB4.7GB。* * CDCDRWRW： 可读写光

19、驱，能读又能写。可读写光驱，能读又能写。 移动存储：主要有移动硬盘和移动闪存盘。移动存储：主要有移动硬盘和移动闪存盘。 计算机系统的基本组成计算机系统的基本组成v输入设备输入设备键盘（键盘（KeyboardKeyboard） 、鼠标（、鼠标（MouseMouse）、）、 手写笔、手写笔、 触摸屏触摸屏 、麦克风、麦克风扫描仪（扫描仪（ScannerScanner） 、视频输入设备、视频输入设备、 条形码扫条形码扫描器描器v输出设备输出设备显示器（显示器（MonitorMonitor）：目前主要有）：目前主要有CRTCRT（阴极射线管）（阴极射线管）显示器和显示器和LCDLCD液晶显示器。液晶显

20、示器。打印机（打印机（PrinterPrinter）：主要有针式打印机、喷墨打）：主要有针式打印机、喷墨打印机、激光打印机。印机、激光打印机。绘图仪绘图仪 音箱音箱 计算机系统的基本组成计算机系统的基本组成v 总线（总线（BusBus） 总线是计算机各部件之间传输信息的公共通总线是计算机各部件之间传输信息的公共通道，由多根导线组成，根据传输信息的不同，道，由多根导线组成，根据传输信息的不同，可分为数据总线、地址总线和控制总线。可分为数据总线、地址总线和控制总线。 计算机系统的基本组成计算机系统的基本组成v 计算机软件可分为系统软件和应用软件两大类。计算机软件可分为系统软件和应用软件两大类。v

21、系统软件：系统软件： v 包括：包括： (1) (1) 操作系统软件，如：操作系统软件，如：v DOSDOS、Windows95/98/2000Windows95/98/2000、UnixUnix、LinuxLinux、WindowsNTWindowsNT；v (2) (2) 语言的编译软件语言的编译软件v Free PascalFree Pascal、DephiDephi、C+Builder C+Builder 等；等；v (3) (3) 某些数据库系统也被归属于系统软件，但此项常有争议，某些数据库系统也被归属于系统软件，但此项常有争议，v 如如foxbasefoxbase、FoxproFo

22、xpro、SQLSQL等；等；v 注意，系统软件不等于操作系统！注意，系统软件不等于操作系统！v 应用软件：为了某个应用目的而编写的软件，主要有文字处理软件、电子表应用软件：为了某个应用目的而编写的软件，主要有文字处理软件、电子表格软件、数据库管理软件、辅助设计软件、实时控制软件等。格软件、数据库管理软件、辅助设计软件、实时控制软件等。信息数字化信息数字化 v数字化信息的计量数字化信息的计量 信息数字化vASCIIASCII码码 ( American Standard Code for ( American Standard Code for Information Interchange )

23、Information Interchange ) 美国的标准信息交换代码美国的标准信息交换代码 将每个将每个字符字符用用7 7位的二进制数来表示，共位的二进制数来表示，共有有128128种状态种状态 信息数字化v 计算机中的数据用二进制表示计算机中的数据用二进制表示v 分为有符号数和无符号数分为有符号数和无符号数有符号数在数值的最高位前加有符号数在数值的最高位前加0 0或或1 1表示数值的符号（正表示数值的符号（正/ /负）负）常用的机器码有原码、反码、补码常用的机器码有原码、反码、补码 原码：最高位表示符号（正原码：最高位表示符号（正0，负，负1），其它位表示数值。），其它位表示数值。如：

24、如： X1011101 X原原01011101 X1011101 X原原11011101 机器码机器码信息数字化反码：反码： 正数的反码与原码相同，符号位用正数的反码与原码相同，符号位用0表示，数值表示，数值位不变；位不变； 负数的符号位用负数的符号位用1表示，数值位为原码数值位按表示，数值位为原码数值位按位取反。位取反。 如：如： X1011101 X反反01011101 X1011101 X反反10100010 信息数字化 补码：补码： 正数的补码与原码相同，正数的补码与原码相同， 负数的补码位反码加负数的补码位反码加1 1形成。形成。 如：如： X1011101 X补补01011101

25、X1011101 X补补10100011 信息数字化v为什么要设反码、补码？为什么要设反码、补码？例如：例如： 1+(-1)、1-1，用原码计算，则须分加减、，用原码计算，则须分加减、 正负进行处理，比较复杂；正负进行处理，比较复杂； 而利用补码计算：而利用补码计算： 1+(-1) = 00000001补+11111111补 = 00000000补 1-1 = 1+(-1) = 设计补码的目的是：设计补码的目的是： 使符号位与数值部分一起参加运算，简化运算使符号位与数值部分一起参加运算，简化运算规则规则. 使减法运算转换为加法运算，简化计算机中运使减法运算转换为加法运算，简化计算机中运算器的线

26、路设计算器的线路设计 信息数字化v 定点数、浮点数定点数、浮点数 定点数：是指数据中小数点的位置是固定不变。定点数：是指数据中小数点的位置是固定不变。小数点固定在有效数据最低位右边，数据表示为整数；小数点固定在有效数据最低位右边，数据表示为整数；小数点固定在有效数据最高位之前，数据表示为纯小数。小数点固定在有效数据最高位之前，数据表示为纯小数。 在机器中，定点数的形式为：在机器中，定点数的形式为： 符号位（正符号位（正/负）负）有效数据有效数据信息数字化浮点数：指数据中的小数点位置没有预先固定。 任何一个十进制数N可用科学计数法表示：同样，二进制数N可表示为： （E称为阶码，M称为尾数，统一用

27、纯小数表示。） 计算机中的浮点数的形式为： 阶符阶码数符尾数阶符表示阶码的符号，正0负1；数符表示N的正负，同样，正0负1。信息数字化v 二进制数据经过传送、存取等环节，会发生误码（二进制数据经过传送、存取等环节，会发生误码（1 1变变成成0 0或或0 0变成变成1 1），为了发现和纠正误码，在原始数据后），为了发现和纠正误码，在原始数据后增加一个或若干个校验位，进行数据校验。增加一个或若干个校验位，进行数据校验。1、奇偶校验码、奇偶校验码这是最基础的一种检验码，是由这是最基础的一种检验码，是由n为有效数据为有效数据位和位和1个校验位组成校验码，这种校验码仅能发现错误（奇数个位个校验位组成校验

28、码，这种校验码仅能发现错误（奇数个位出错的情况），不能纠正误码。出错的情况），不能纠正误码。2、能纠正误码的校验码、能纠正误码的校验码海明码：是一种多重海明码：是一种多重(复式复式)奇偶检错系统，每一个奇偶位被编在奇偶检错系统，每一个奇偶位被编在传输码字的特定位置上。传输码字的特定位置上。循环冗余校验码（循环冗余校验码（CRC码）：在串行传送（磁盘、通讯）中广泛码）：在串行传送（磁盘、通讯）中广泛采用。采用。操作系统只认得只认得0 0和和1 1操作系统v DOS DOS操作系统v DOSDOS命令命令dircd操作系统v UnixUnix、LinuxLinux操作系统v WindowsxWin

29、dowsx系列：系列： Windows 98Windows 98，Windows XPWindows XP， Windows Vista Windows Vista，Windows 7Windows 7，Windows 8Windows 8Windows 10 Windows 10 是微软公司新一代操作系统。是微软公司新一代操作系统。Windows 10 Windows 10 正式版将于正式版将于20152015年发布，将涵盖年发布，将涵盖PCPC、平板电脑、手机、平板电脑、手机、XBOXXBOX和服务器端和服务器端操作系统v 操作系统的功能主要有：操作系统的功能主要有： 处理机处理机(CPU

30、)(CPU)管理、作业管理、存储管理、管理、作业管理、存储管理、 文件管理、设备管理。文件管理、设备管理。CPUCPU管理：进程控制、进程同步、进程通信、进程调度管理：进程控制、进程同步、进程通信、进程调度作业管理：作业调度、作业控制作业管理：作业调度、作业控制文件管理：存储空间管理、目录管理、文件读写、文件管理：存储空间管理、目录管理、文件读写、 文件保护、用户接口文件保护、用户接口存储管理：内存分配、内存保护、地址映射、内存扩充存储管理：内存分配、内存保护、地址映射、内存扩充设备管理：缓冲管理、设备分配、设备处理、虚拟设备功设备管理：缓冲管理、设备分配、设备处理、虚拟设备功能能操作系统v

31、进程进程进程是程序的一次执行，是可以和别的计算并发执行的计算；进程是程序的一次执行，是可以和别的计算并发执行的计算；是一个程序及其数据，在处理机（是一个程序及其数据，在处理机（CPU）上顺序执行时所）上顺序执行时所发生的活动；发生的活动； 进程是程序在一个数据集合上运行的过程，是系统进行资源分进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位；配和调度的一个独立单位； 操作系统v 进程的状态进程的状态就绪、执行、等待就绪、执行、等待 或称或称“挂起挂起”、“阻阻塞塞” 当进程获得所有必需资当进程获得所有必需资源时，排入等待的队列，源时，排入等待的队列，称为称为“就绪就绪”状态；状态；当进程已获得当进程已获得CPU，则，则处于处于“执行执行”态；态；当进程必需资源不满足当进程必需资源不满足时，则处于时，则处于“等待等待”状态，当资源获得时又状态，当资源获得时又转让转让“就绪就绪”态。态。操作系统v 进程死锁进程死锁原因原因：多个进程因为竞争资源，或执行时推进的顺序不当，多个进程因为竞争资源，或执行时推进的顺序不当， 或相互通信而永久阻塞现象。或相互通信而永久阻塞现象。产生死锁的四个必要条件：产生死锁的四个必要条件： 互