信息学奥林匹克竞赛 PPT课件

信息学奥林匹克竞赛,2014.03.16,交流内容：,一.信息学奥林匹克竞赛赛事介绍二.目前我省信息学奥赛开展情况三.考试内容四.学生的选拔与组织五.辅导进度与时间安排六.对辅导老师的一点建议七.问题解答,高中阶段五科奥林匹克竞赛：数学、物理、化学、生物、信息学全国联赛（省赛区）全国竞赛,一.信息学奥林匹克竞赛赛事介绍,1、省赛区的竞赛名称,全国高中数学联赛；全国中学生物理竞赛(省级赛区)；全国高中学生化学竞赛(省级赛区)；全国青少年信息学奥林匹克联赛；全国中学生生物学联赛。,2.全国决赛的名称,中国数学奥林匹克；全国中学生物理竞赛决赛；全国高中学生化学竞赛；全国青少年信息学奥林匹克竞赛；全国中学生生物学竞赛。,国家对获奖学生的政策：,高中2013届（2010级）前：,高中阶段：学科奥林匹克竞赛：下列两个之一就具备保送资格：省赛区中获得一等奖全国决赛一、二、三等奖的应届高中毕业生,2011级开始：,参加全国决赛进入国家集训队保送（全国前50，金牌）金银铜高考加20分省赛区联赛一等奖不再具有保送资格大学有自己的自主招生政策（单独）,信息学奥林匹克竞赛,面向全国中学生的一种竞赛活动，旨在激发中学生在计算机科学方面的兴趣，培养他们逻辑思维的能力，给那些有才华的学生提供相互交流和学习的机会，通过竞赛和相关的活动培养和选拔优秀的计算机后备人才。,信息学奥林匹克竞赛赛事：,1.NOIP（全国信息学奥林匹克联赛）NationalOlympiadinInformaticsinProvinces2.NOI（全国信息学奥林匹克竞赛）NationalOlympiadinInformatics3.IOI（国际信息学奥林匹克竞赛）InternationalOlympiadinInformatics,NOIP分区联赛,初赛：10月中旬（周六下午2:30-4:30）笔试（100分）资格赛，地市独立组织（全国统一命题，统一时间）复赛：11月份中旬（第二周,周六、周日上午8:30-12:00）两试（上机）每试3个题目，每题100分，共600分提交源程序，黑盒子测试法各省统一组织考试全国统一评测,NOI全国赛：,7月底举行（两试,每试3个题目，每试5小时）每个省选拔队员参加10-15名我省从上一年参加NOIP的获得一等奖的选手中经过两次选拔赛选拔当年参加NOI的队员4月份，5月份两次选拔赛,二.目前我省信息学奥赛开展情况,NOIP报名参赛人数全国前两位。一等奖分数线基本前5一等奖人数分配到省（山东50左右，不包括重复获奖）NOI全国前6左右金牌8枚(4所学校),全省地市学校情况：,NOIP201376个一等奖分布在29个学校获奖学生呈分散趋势传统成绩较好的学校，实力减弱越来越多的学校开始着手抓奥赛,信息学奥林匹克竞赛属于智力与应用计算机解题能力的比赛，题目有相当的难度，解好这类题目，需要具备很强的综合能力1.观察和分析问题的能力；2.将实际问题转化为数学模型的能力；3.灵活地运用各种算法的能力；4.熟练编写程序并将其调试通过的能力；5.根据题目的要求，自己设计测试数据，检查自己的解法是否正确、是否完备的能力,三.考试内容,能够参加信息学竞赛的选手应该具有很强的自学能力。需要学习有关组合数学、图论、基本算法、数据结构、人工智能搜索算法等知识熟练高级语言和编程技巧，要具备很强的上机操作能力,要求：,掌握一门计算机程序设计语言(怎样选择)：PascalCC+数据结构与算法,一、语言：Freepascal（c/c+）基础,二、数据结构线性表、栈、队列、树、图,三、算法：高精度运算排序算法搜索算法（dfs，bfs）动态规划dp贪心算法、模拟算法等相关的数论知识,全国联赛（NOIP）知识点：,主要考察基本数据结构与算法的应用能力,全国竞赛（NOI）,并查集、树状数组、线段树查找树网络流几何算法,主要考查建立模型和算法的优化能力,四.学生的选拔与组织,信息学奥赛是一种选拔性竞赛不是一般计算机知识的普及。,兴趣能力勤奋,1.综合成绩突出。2.扎实的数学基础。3.很强的自学能力。4.乐于和同学合作与交流。5.能坐得住。,学生自身：,外力：,家长和班主任老师的支持,人数,每个年级保持在15人左右较好开始多一点，慢慢的淘汰,吸引学生、培养兴趣,第一堂课很重要,信息学奥赛解决的问题：,经过思考能够得出解决的方法，但是却很难或者根本不可能用人工的做出来。设计算法，用计算机语言设计程序实现自己的方法，从而解决问题。,步骤：,观察分析问题思考问题，得出模型（数学模型）设计解决问题的算法或者步骤用计算机语言设计程序实现算法调试验证算法的正确性,要将一张100元的大钞票，换成等值的10元、5元、2元、1元一张的小钞票，每次换成40张小钞票，每种至少1张。如，有一种换法：10元：1张5元：5张2元：31张1元：3张问：一共有多少种换法。,【举例1】换钱问题,举几个例子激发学生的学习兴趣和欲望,10元：a张(不超过10张)5元：b张(不超过20张)2元：c张(不超过50张)1元：d张(不超过100张)不定方程组：10*a+5*b+2*c+d=100a+b+c+d=40a=1;b=1;c=1;d=1问题转化为：方程组有多少组正整数解？,分析：,给学生代码：试运行vara,b,c,d,n:longint;beginn:=0;fora:=1to10doforb:=1to20doforc:=1to50doford:=1to100doif(10*a+5*b+2*c+d=100)and(a+b+c+d=40)thenn:=n+1;writeln(n);end.,换成50张有多少种换法？,两张100的换成40张，有多少种换法？,让学生试一试：,已知：s=1+1/2+1/3+1/n求：使s的值大于10时最小的n。,【举例2】求最小的n,varn:longint;s:real;begins:=0;n:=0;repeatn:=n+1;s:=s+1/n;untils10;writeln(n);end.,使s的值大于10时最小的n?n=123467使s的值大于15时最小的n?使s的值大于30时最小的n?知道：计算机的计算范围是有限的。,有两个无刻度标志的水杯，分别可装满x升和y升的水。设另一个水缸，可以用来向水杯灌水或从水杯向水缸里倒水，两个水杯之间也可以相互倒水。已知x升的水杯开始是盛满水的，y升的杯子是空的，问如何通过倒水和灌水操作，用最少的步数能在y升的杯子里量出z升水。,Y,X,水缸（足够的水,未满）,X=20Y=15Z=10？Y10,【问题3】：倒水问题,开始:200step1:515step2:015step3:150step4:1515step5:2010,XY,算法：广度优先搜索数据结构：队列,找学生回答,复杂一点的还能吗？,知识的讲解,任务驱动根据任务的需要讲知识点避免使用以前大学老师的讲课方式,五.辅导进度与时间安排,三个阶段：,高一年级：（周六一个上午3个小时）语言基本算法与数据结构（基本的，不要贪多）高一假期专项强化训练：算法的完善和补充高二复赛考试前（11月份）模拟训练,高一,语言部分,用什么讲什么粗放型，不要面目俱到1.三种基本结构（ifforwhile）2.数组结合渗透：枚举算法；一种简单的排序算法3.递归（自定义函数与过程）及简单应用慢慢熟练语言（6到7个半天）,算法与数据结构：,1.深度优先搜索算法2.广度优先搜索算法（数据结构队列）3.简单的动态规划算法4.树及其应用5.图论算法邻接矩阵存储法存数两种最小生成树算法:普里姆算法（prim）;克鲁斯卡尔（kruskal）两种最短路径方法算法：弗洛伊德算法：floyed迪杰斯特拉算法：dijkstra,侧重基本知识，勿贪多，讲练结合,高一暑假期间（重要的集中学习时间）,算法与数据结构的补充和加深（实用性）,堆的使用并查集最短路径算法spfa，图的邻接表存储方法动态规划技巧与处理方法,建议参加山东省夏令营活动（7月中旬下旬）学校自己训练,高二开学（9月份，10月份，每周两次）,10月中旬的初赛根据具体情况，一般不需专门准备多报一部分人（参加学习是分子+增加分母）模拟复赛训练提高应试能力,联赛考完后的高二下学期：,分流：没有获奖的同学坚持学的继续从头复习获得联赛一等的想参加省选的学习新的知识,初中具备基础的最好，根据情况跟高二上课鼓励从初中开始早学习,六.辅导老师的要求,认真备课不要用别人现成的课件。只能借鉴。自己重新整理。自己动手写程序题目多准备几种算法；多角度讲解,已经掌握知识的老师,上课辅导：,刚刚起