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