-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathContents.txt
94 lines (86 loc) · 5.95 KB
/
Contents.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
培训教程建议目录和编写提示
本文件仅规定各章节的大方向。具体章内的小节内容、章节名称由编写者自行确定。下面建议稿中，每个章节下面的内容是该章知识点，但是具体的安排顺序不严格规定，大家可以便宜行事。
编写建议：
1， 语言尽量直白，不要把它当做写书，而是要当成阐述道理。切忌像教科书一样教条。
2， 建议在阐述算法的过程中用例子引入，否则会让学生面对这个算法手足无措，不知道它能干什么。
3， 尽量多的例子、尽量多的代码。请尽量上机测试，以保证代码的正确性！
4， 记得再每节结束之后给出适量例题。有回顾性例题（例如让学生自己回顾某种算法，写出大致流程），还要有大量上机题！！！！
5， 等培训开始后，我们的上课和上机所占比例大约是3:7。上机可以留在课下去完成。
目录：
第-1章：前言（负责人：石博天）
ACM/ICPC竞赛介绍
包括：比赛的历史、参加比赛的目的、参加比赛所能带来的益处
第零章：绪论（负责人：石博天）
算法及数据结构的基本概念
包括：什么是算法，什么是数据结构，为什么要基本的学习算法与数据结构，算法与数据结构在计算机科学中占有怎样的地位。
第一章：程序设计入门（负责人：石博天）
C++基础语法（指针是重点）
包括：程序基础（程序？源程序？目标文件？编译？程序在内存中的组织形式等基本概念），C++基本语法（选择，循环，顺序结构），变量类型及其在内存中的存在，指针
C++面向对象（类、成员）
包括：基本的类的概念，对象的概念
不包括：C++高级特性（继承、多态等）
本章补充：时间复杂度，空间复杂度，伪代码，各种语言的优劣
本章主讲人需要将以上补充内容穿插在课程中。
第二章：算法入门（负责人：张怀文）
简单排序
包括：什么是排序，排序的动机，排序的复杂度分析
算法：插入排序、选择排序、冒泡排序
备注：需要配有例题，算法需要有相应实现
递归、分支（思想）
包括：什么是递归，递归的动机，递归的复杂度分析
算法：经典的递归例题
概率分析、随机算法
包括：什么是随机算法，随机算法的动机，随机算法结果的期望，随机算法的复杂度
备注：配有例题简单介绍即可。
本章补充：代码调试
第三章：排序（负责人：张怀文）
高级排序
包括：为什么还要学习排序，排序的效率比较
算法：堆和堆排序、快排、归并排序
备注：需要写出代码用程序来说明排序的快慢，获取不同数量级的随机数，用各种排序算法（包括第二章排序算法）进行排序，并比较所需时间
线性时间排序
包括：线性排序原理，线性排序的局限性
算法：计数排序、基数排序、桶排序
备注：需要有实现（代码，或者伪代码，推荐类C风格的伪代码）
本章补充：简单的代码测试
第四章：数据结构（负责人：李政霖）
线性结构：栈、队列、链表等
散列结构：hash表、散列函数、冲突处理等
树形结构：二叉树、二叉查找树、Huffman树、Huffman编码等、红黑树
图：图的概念、图的存储结构
包括（每种结构）：概念，动机，实现，例题，一次增删改查的时间复杂度，空间复杂度
第五章：基础算法（负责人：薛家斌）
深度优先、广度优先、启发式搜索、剪枝
包括：搜索的概念，搜索的动机，搜索的选择，N、NP、NPC问题
备注：每种类型的搜索需要典型的例题作为讲解。
分治
包括：分治的概念，分治的动机，分治与递归的区别与联系
备注：需要例题，讲解如何制定分治策略
贪心算法
包括：贪心的概念，贪心的动机，贪心的证明（证明最优性）
博弈论
包括：什么是博弈？博弈问题的分析方法，三种典型的博弈问题（巴什博奕（Bash Game）、威佐夫博奕（Wythoff Game），尼姆博奕（Nimm Game））
第六章：高级算法（负责人：薛家斌）
（内容很多，而且不易讲解，推荐使用较长的时间来讲解）
记忆化搜索
包括：什么是记忆化搜索，搜索记忆化的动机，记忆化的效果（提高多少效率）
备注：需要例题，并跟踪执行过程
动态规划
包括：什么是DP，DP的动机，DP的两种实现方式（记忆化搜索与递推），DP的基本概念（阶段，状态，状态转移方程，边界），如何选择合适的实现方式，DP的种类，如何设计DP的状态转移方程，怎么理解最优子结构，怎么理解无后效性
备注：需要例题，讲解设计状态转移方程设计的方法及过程
图论相关：
包括：最短路径，最小生成树，AOE网，AOV网，网络流的基本概念，适用范围
算法：最短路径，最小生成树，AOE网，AOV网，网络流
二分图
包括：什么是二分图，二分图的匹配问题
算法：匈牙利算法
备注：配合例题简单讲解
第七章：数学（负责人：杜志浩）
代数
包括：初等数论（素数，约数，公约数，公倍数，唯一因子分解，中国剩余定理，欧拉函数，离散对数，素数测试，大数的素性检测，梅森素数）
算法：判断素数，筛选法求素数，最大公约数，最小公倍数，扩展欧几里得，唯一因子分解，n！素因子分解，同余，求解模线性方程，RSA算法，Rabin-Miller素数测试，Pollard测试
几何
包括：三角形，圆，矩形，椭圆等图形的几何性质
解析几何
包括：直线段的方程描述，圆，椭圆的方程表示，凸包问题，平面上直线段的位置关系，向量，平面上的角
算法：凸包的扫描算法