打开主菜单

信息学


目录

信息学编辑

信息学是研究信息的产生、获取、传输、处理、分类、识别、存储及利用的学科。20世纪60年代以后逐渐形成。它的主要基础理论和科学方法论是神经生理学、心理学、计算机科学、系统工程、信息论、控制论等。它主要研究以下问题:(一)客观世界信息源理论。这一理论探讨如何掌握生物、人类和计算机发出和获取信息的规律。(二)建立在模糊数学基础上的信息识别理论。在人类社会中,信息是以语言、声音、图象、文字等形式出现的,计算机系统尚未完全解决识别这些信息的问题。(三)人工智能理论。由于计算机辅助设计、专家系统和机器人的出现,因而建立这一理论变得十分迫切。(四)信息的结构和层次研究,如社会信息产业的统计和划分等。(五)信息系统(获取、处理、存储、传播过程等等作为一个整体过程)研究。(六)信息管理和经济效益等等信息的利用问题。

综述编辑

信息学是研究信息的获取,处理,传递和利用的规律性的一门新兴学科。信息学(信息为研究对象,以计算机等技术为研究工具,扩展人类的信息功能为主要目标的一门综合性学科。又称信息科学,旧称情报学(和制汉字)。主要是指利用计算机及其程序设计来分析问题、解决问题的学问。与图书馆学有密切的关系。

2研究内容编辑

信息学的主要内容包括信息加工学、信息资源管理学、信息安全学、信息传播学及计算机科学等等。

3技术发展编辑

伴随记忆和运算工具的飞速发展,特别是以计算机为代表的信息加工和运算设施,加速了人类掌握信息技术的发展。

信息化编辑

任何组织机构,为了应对瞬息万变的世界,必须建立信息系统和资源管理系统,以应对日益复杂的信息文明和短缺的资源。

应用编辑

国际竞争和商业竞争的演化,直接演绎竞争情报的飞速发展,特别是军事竞争情报。

4学科竞赛编辑

竞赛种类编辑

信息学奥林匹克(Olympiad in Informatics)简称IOI是联合国教科文组织支持的学科竞赛之一。我国已经建立起一组相对完善的选拔机制,选手比赛成绩优异全部获得金牌。

ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate ProgrammingContest(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展,ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。

NOI(全国青少年信息学奥林匹克竞赛)

NOIP(全国青少年信息学奥林匹克联赛/分区联赛)在每年十一月的第三个星期六举行

WC(Winter Camp) 全国信息学冬令营。

CTSC(Chinese Team Selection Contest) IOI中国代表队选拔赛 暨全国信息学精英赛

APIO(亚洲与太平洋地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad)

POI(Polish Olympiad in Informatics) 波兰高中信息学编程竞赛,在世界上影响很大。

CEOI中欧信息学竞赛(Central European Olympiad in Informatics),中欧的高中信息学编程竞赛,在世界上影响很大。

BOI波罗的海国家信息学奥林匹克竞赛

知识体系编辑

数学离散数学集合论关系代数系统数理逻辑图论

组合数学排列组合母函数群论递推与递归

数学规划线性 动态整数

高等数学向量行列式与矩阵 微积分初步

概率统计

初等数论素数 整数理论同余与模线性方程

计算几何

数据结构存储结构线性表

(一级结构)静态:数组 栈 队列广义表字符串

动态:指针链表动态数组

(二级结构)表示法(静态、动态) 二叉树 森林

(三级结构)表示法(矩阵、邻接表、三元组)

特殊结构散列表(HASH表)并查集线段树后缀树哈夫曼树与哈夫曼编码地址表 Bit图 滚动数组 棋盘图 边顶置换图 二分点图(网络流)

常用方法遍历树 图 前/中/后序优先

转化拓扑排序(三级结构转一级结构)最小生成树最小树形图(三级结构转二级结构) 逆遍历

压缩路径树的线索化

压缩存储

查找线性直接 折半 Fab

树形二叉查找树平衡二叉树B+树B-树线索二叉树索引表

排序插入排序直接排序、折半排序、2-路排序

交换排序冒泡排序快速排序归并排序

堆排序

基数排序链式基数排序桶排序

代码素养代码的编写速度和准确性误码率

算法实现

算法优化

调试 查错 测试

习惯变量名 注释 缩进 模块化

基本算法数学高精度计算(模拟计算)

表达式处理括号 前/中/后缀表达式表达式树

排列组合求值嵌套控制

高斯消元法

筛选素数素数表

分数处理

基本操作实现大量数据赋值与移动Fillchar fillword move等函数

处理实数比较大小 高精度

字符串处理基本函数KMP算法

图论

(显示图搜索)路径问题

(边集)连通性测试传递闭包算法 极大强连通子图 最小点基

最短路问题标号法 第k小路 减半最短路Dijkstra算法floyd算法bellman-ford算法Warshall算法

特殊路径欧拉路及回路 哈密尔顿路及回路

图的中心和重心

生成树Kruskal算法Prim算法

(顶点集)覆盖集

独立集

支配集

割顶和块

网络流容量有上下界的网络最大 / 小流

容量有上下界的网络最小费用最大 / 小流

顶容量网络最大流

供求约束可行流

二分图匹配匈牙利算法

关键路径

搜索

(隐式图搜索)深度优先搜索

(回溯法)剪枝优化

预处理

记忆化搜索

可变下界的深度优先搜索

随机化搜索

广度优先搜索双向广搜*多向广搜

启发式搜索(A算法)

分枝定界

多阶段决策贪心算法

动态规划

其他构造法穷举

模拟