tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

信息学算法学习流程


说明: 1、 什么是信息学竞赛?信息学竞赛就是以计算机为工具,通过编程的方式来解 决具体问题。在解决具体问题的过程中需要设计解决问题的思路(算法)和 构建合理的数据结构。 2、 各级信息学竞赛的知识与难度? 联赛级要求:计算机基础部分+数据结构基础部分 省队和国家集训队级要求:复杂数据结构+数学知识拓展+计算几何。 3、 每一个知识点的掌握都需要配合大量的练习,在充分的实践运用中

去提升。 www.vijos.org ----------湖南师大附中信息学网站 www.nocow.cn----------usaco 中文网站

希望同学们能脚踏实地、循序渐进,逐步提高,把算法理 论和数据结构知识灵活运用到解决问题中。

计算机基础部分 ----------------------------------------------------------------------------------------------------------------(一) 、数学基础知识
简单排列、可重复的排列、简单组合、杨辉三角形

(二) 、基本算法设计策略
1、数值处理算法:枚举、计数、统计、数学运算 2、排序算法:冒泡排序、选择排序、插入排序、合并排序、快速排序 3、递推、迭代、递归 4、算法的时空复杂度分析 5、分治与查找算法:顺序查找、二分查找 6、贪心算法 7、模拟算法 8、高精度计算:高精度与单精度的加减法;高精度与高精度加减法;高精度与单精度乘 法。 9、搜索算法:回溯、深度优先搜索、广度优先搜索 10、启发式搜索;搜索的优化剪枝 11、动态规划:线性动态规划、树形动态规划 11、移位运算: 算术右移、算术左移、逻辑右移、逻辑左移、循环逻辑右移、循环逻辑左移

数据结构基本部分 ----------------------------------------------------------------------------------------------------------------1、线型数据结构 线性表及其应用 堆栈及其应用 队列及其应用 矩阵及其应用 字串及其应用 2、散列表 散列的构造: 整数的哈希函数、字串的哈希函数、排列的哈希函数 散列的冲突: 开散列、闭散列 3、树型数据结构 树:二叉树;二叉树排序树;最优二叉树(HAFFMAN 树) ;并查集;堆;树状数组 4、图 图的存储结构;图的遍历 深度优先和宽度优先遍历 图的连通性问题关键路径 连通分量(最小生成树) ;强连同分量;求割点; 图的 HAMILTON 回路;拓扑序列 5、图的最短路算法 Dijkstra 算法、bellman 算法、spfa 算法、folyd 算法

复杂数据结构 ----------------------------------------------------------------------------------------------------------------1 块状链表及其应用 2、二叉排序树及其平衡 二叉排序树、AVL 树、SPLAY 树、TREAP、跳跃表 3、线段树及其应用 线段树、RMQ 和 LCA 问题 4、Trie 树结构和 Patricia 树结构原理及其应用 5、后缀树和后缀数组 6、 KMP 算法、扩展 KMP 算法 7、网络流算法 费用流及其应用、有上下界的网络流问题 8、二分图的匹配 最大匹配、完备匹配、最佳匹配 9、图的覆盖集和支配集 10、图的点连通度和边连通度

数学知识拓展 -------------------------------------------------------------------------------------------------------------1、矩阵及其运算 矩阵的概念,矩形的初等行变换,矩阵的转置,矩阵的加减乘法,矩阵的逆,矩阵的秩 2、排列和组合的字典序,错排问题、容斥原理,string 数、cantlan 数、抽屉原则、莫比乌

斯反演、ramsey 定理、二项式分解定理,杨辉三角形 3、数论 模线方程求整数解(扩展欧几里德算法) 、欧拉定理与欧拉函数、模线方程组(中国剩余定 理) 、 4、行列式基本知识 行列式的概念及运算,代数余子式、齐次方程组及其解法 5、高斯消元法解 n 元一次方程组 6、线性规划 7、整数规划 8、数值处理 二分法,牛顿迭代,梯形法 9、置换群 Burnside_引理、Pólya 原理 10、游戏论的基本理论 NIM 问题,SG 函数

计算几何 ----------------------------------------------------------------------------------------------------------------1、矢量 矢量的概念、矢量加减法、矢量点积(内积)和叉积(外积) 2、折线段的拐向判断 3、点与线的关系:判断点是否在线段上 4、线与线的关系 5、判断两线段是否相交 6、判断线段和直线是否相交 7、点、线段、折线、圆与矩形之间的关系 8、判断矩形是否包含点 9、判断线段、折线、多边形是否在矩形中 10、判断矩形是否在矩形中 11、判断圆是否在矩形中 12、点、线段、折线、矩形、圆与多边形之间的关系 13、判断点是否在多边形中;判断点是否在圆内 14、判断线段、折线、多边形、圆是否在多边形内 15、判断线段、折线、多边形、圆是否在圆内 16、点与线的距离:计算点到线段的最近点;计算点到折线、矩形、多边形的最近点 17、点与圆的距离 18、计算点到圆的最近距离及交点坐标 19、求交点: 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 20、凸包: 凸包的概念 凸包的求法(Graham 算法、卷包裹法) 21、半平面:半平面概念,求半平面交(联机算法、分治算法)


推荐相关:

高中信息学奥赛辅导的几点感悟

算法是高中信息学奥赛教学课程中至关重要的教学 内容,怎样才能激发学生学习算法的...例如在学习程序解决实际问题的这个单元内容的时候,首先给学生演示一个 “心理...


算法在信息学奥赛中的应用 (基础篇)

算法信息学奥赛中的应用 (基础篇) 学习程序设计的人对算法这个词并不陌生,从广义上讲,算法是指为解决 一个问题而采用的方法和步骤;从程序计设的角度上讲,...


信息学联赛中 一位退役OLDER的经验

书籍推荐:绿书+蓝书(青少年信息学奥林匹克竞赛培训...这样,一个程序就算写完了,我这个算法流程只是提供一...最后,祝各位 OIer 学习进步,Rp++,在 NOIP 中狂...


信息学奥赛(NOIP)必看经典书目汇总

2、谭浩强老先生写的《C 语言程序设计(第三版) 》 (推荐指数:5 颗星) 针对...3、 《学习指导》 (推荐指数:5 颗星) 刘汝佳著, 《算法艺术与信息学竞赛》...


信息学奥赛(NOIP)必看经典书目汇总

2、谭浩强 老先生写的《C 语言程序设计(第三版)》(推荐指数:5 颗星) 针对...3、《学习指导》(推荐指数:5 颗星) 刘汝佳著,《算法艺术与信息学竞赛》的辅导...


信息学奥赛经典算法C语言经典例题100例

信息学奥赛经典算法C语言经典例题100例_其它课程_高中教育_教育专区。信息学奥赛...【程序 15】 题目:利用条件运算符的嵌套来完成此题:学习成绩>=90 分的同学用...


选修课《信息学竞赛》

你肯定看不懂,没有学过面向过程的语言就直接学习面向对象的语言是不 可能学的...《信息学竞赛》讲义 3.查找(顺序查找、二分法) 4.回溯算法二、复赛内容与要求...


信息学竞赛中得高分的关键环节--测试

通常竞赛中编写一个程序可以分为这样几个环节:分析题目—设计 算法和数据结构—编码—调试—测试,设计测试数据的能力是竞赛考察的重点之一。但是很多学习信息学 奥...


信息学奥赛算法教程_Pascal

常用的算法:列举了穷举搜索、递归、回溯、信息学奥赛辅导教程第3章 算法程序...为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末...


最新浙江高中信息学考算法及算法的表示专题复习

最新浙江高中信息学算法算法的表示专题复习_其它课程_高中教育_教育专区。...分支结构 流程图 D.循环结构 流程图 5.下面是一段关于计算变量s的算法: ①s...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com