二十一世纪信息时代的到来,世界发生着深刻的变化。为了推动世界的进一步发展,个人研究认为,在高中阶段的信息学课程应当开设一下内容:
分为必修和选修部份。
高中-信息学
必修:
《基本概念与基本理论》
介绍了计算机组成、发展,网络组成,计算机基本概念等概念以及后面课程 所需的复杂性估计基本理论。
《基本语言实现》(Pascal版,C版,C++版,Java版,Basic版,Pyphon版)
教授各语言版本的基础实现
《基础算法》
介绍了基础贪心法,排序法,枚举法,基本搜索法,模拟法等最基本的算法,为进一步学习打下基础。
选修部份:
《进阶算法》
介绍了基本动态规划、基本的图论算法(Prim和Dijkstra)、模式匹配KMP算法和RK算法、基础网络流知识、基础几何问题和基本数学问题。并简要分析了数据结构对算法设计的影响。
《数据结构与算法分析》
在此前学习过的线性表、线性排序表的基础上,学习链表、索引表和哈希表。并学习对算法优化十分必要的栈、队列和优先队列(仅介绍堆),还有一些更加复杂但有用的结构如排序二叉树、线段树和平衡树、Trie、图结构的邻接表和邻接矩阵,哈希表的多种实现和冲突处理等。并分析了数据结构的操作复杂性。
《搜索算法》
介绍了常见搜索算法:深度优先(包括衍生的迭代加深、启发迭代加深、双向深度优先)、广度优先算法(包括衍生的迭代加宽、启发搜索和双向广度优先)、随机搜索算法和敌对搜索算法。
《动态规划,贪心法和近似算法》
学习动态规划、贪心法和近似算法(Monte Carlo、Las Vegas等)的运用。
《图论问题》
介绍简单的图论问题,包括最小生成树(MST)、最短路(SSSP、APSP)、图遍历(包括强连通分支的查找等内容)、树结构。
《网络流》
简单的网络流。在《进阶算法》的基础上,从Ford Fulkerson解最大流问题到Edmonds Karp的两个算法、Sap、HLPP、Dicnic等常见算法并介绍了最基本的最小费用最大流算法。并从理论上学习网络流的结构概念和定理,如最小割最大流定理。
《计算几何初步》
计算几何问题入门,计算几何与解析几何在实现上、复杂性上的比较等。
《算法分析模型及理论》
从图灵机的算法分析理论,进一步推广到更加普遍或特殊的计算模型和理论。
《组合数学与算法》
介绍了组合数学。
《编译原理》
编译原理学习。
《代码实现优化》
学习如何更好地编码。
|