算法艺术与信息学竞赛+学习指导.pdf

5星(超过95%的资源)
所需积分/C币:50 2012-04-12 10:55:36 10.27MB PDF
84
收藏 收藏
举报

算法艺术与信息学竞赛+学习指导。经典的算法。
目录 1.4.6二进制和六进制 23 14.7内存和变量 25 1.4.8变量的类型..., 26 1.4.9变量的声明和使用 29 1.4.10运算符和表达式 1.4.11函数 35 14.12控制流和程序结构 38 数据结构基础 41 1.5.1逻辑结构:线性表、树和图 1.5.2逻辑结构的物理实现 .43 1.53外部特性和内部结构 47 1.5.4抽象数据类型 1.5.5时间复杂度 1.6语言和数据结构小结 53 第二章问题的复杂性 57 21时间下界 57 1.计算模型 57 2.1.2对立法 60 23归约法 63 22NP完全问题 66 2.2.1(ook定理和3- CNF-SAT 67 2.2.2更多NP完全问题 70 2.3图灵机和计算复杂性理论 74 2.3.1问题和语言.. 74 2.32图灵机 233计算复杂性类 80 24本章小结 第三章数据结构原理 84 3.1线性表、树和图.. IV 目录 3.1.1线性表 4鲁春 84 31.2树、二叉树和图 3.2常用数据结构. 321二叉堆 96 322并杳集 32.3哈希表 101 32.4排序二叉树 103 33平衡二叉树及其变种 33.1AVL树 106 3.32伸展树 109 33.3跳跃表 113 3.3.41 114 3.4可并优先队列 3.4.1左偏树和斜堆 116 34.2二项堆 119 34.3 Fibonacci堆 .,,,,.,,120 3.5木章小结. 123 第四章算法设计方法 125 4.1递归与分治 125 4.1.1递归思想 125 41.2三个经典的分治算法 128 41.3递归树和主定理 ...134 41.4运算的加速 .137 41.5排序与顺序统计 4,2贪心法 143 421几个简单的例子. 144 42.2区间上的问题 145 42.3 Huffman编码 .147 424两个调度问题 150 43动态规划 154 目录 4.31基本思想 154 43.2动态规划的条件 158 43.3最优矩阵链乘 ,,161 43.4最长公共子序列问题 164 43.5其他经典问题及其时间优化 168 44路径寻找问题 171 44.1引例和基本概念 .172 44.2状态空间 176 4.43盲目搜索 .,181 4.4.4启发式搜索(1):A*算法 185 4.4.5启发式搜索(2):启发函数和其他算法 45约束满足问题 197 45.1再论回溯法 97 4.5.2约束传播和AC3算法 200 4.3CsP问题的结构 205 4.6对抗搜索 209 46.1问题定义和 MINIMAX算法 210 46.,2a-B剪枝和其他优化 47木章小结 216 第五章数学概念与算法 219 5.1数论基础 219 5.1.1基木概念(1):整除性、素数、最大公约数 219 512基木概念(2):Zn和Z群 22 5.1.3模方程(1): Euclid算法和中国剩余定理 225 5.1.4模方程(2):指数和原根 230 5.1.5素数及其判定.. 235 5.1.6因数分解(1):基木算法 242 5.1.7因数分解(2):连分数、椭圆曲线和其他 .246 52数值计算 254 52.1大整数运算 254 目录 5.22多项式与FFT 258 5.23矩阵和线性方程组 264 5.3组合计数 267 5.3.1计数原理和散概率 267 5.3.2编码、解码和枚举 5.33递推关系与生成函数 277 5.3.4等价类计数 281 5.4组合游戏 )8 5.4.1基本概仑和方法.,,, )8 542Nim和与 Sprague( rudy定理 543Nim积与 artan定理 第六章离散结构上的算法 299 6.1序列上的问题. 299 6.1.1线段树和树状数组 61.2RMQ问题和扩展 30 6.1.3更多排序算法. 62短形的算法 308 62.1数据结构和算法思想 .,309 62.2数字矩形相关问题 .312 62.3平面矩形和点相关问题 315 63树的算法 318 6.3.1LCA问题 ,.318 6.3.2树的计算和统计问题. .322 6.3.3树的构造和计数问题 325 6.4字符串及其算法 332 6.4.1字符串匹配问题 333 6.4.2Z算法和BM算法 340 6.4.3集合匹配和Aho- Corasick算法 346 6.4.4后缀树与 Ukkonen算法 349 6.4.5后缀数组和Skew算法 357 目录 6.4.6最长回文子串问题 .363 6.47小结和应用举例 365 第七章图论问题和算法 367 7.1图的结构 367 7.1.1图的遍历及其应用 67 7.1.2有向图的连通性 373 7.1.3无向图的连通性 378 72生成树和树型图 7.2.1求最小生成树的 Kruskal和Pim算法 383 7.22最小度限制生成树 386 7.2.3次小生成树及生成树的排序.. 392 7.2.4有向图的生成最小树形图 .394 7.2.5小结 399 7.3最短路问题 7.3.1单源最短路问题 7.3.2每对结点最短路问题 405 7.3.3k短路问题 407 7.3.4小结 412 7.4网终流问题 412 7.4.1最大流问题 413 7.4.2最大流问题的增丿路算法 418 7.4.3最大流问题的预流推进算法 ,,,421 7.4.4最小费用最大流问题 .423 74.5小结 426 7.5匹配问题 426 7.51二分图匹配 426 7.5.2一般图的最大基数匹配 431 753小结 433 7.6线性规划 433 7.6.1标准形式和松弛形式 434 目录 7.62单纯形法 439 7.6.3网络优化问题的线性规划模型 445 7.6.4原始-对偶算法 .447 7.6.5网络单纯形法 453 76.6小结 455 第八章几何基本问题 456 8.1代数方法 456 8.1.1向量乘积与仿射变换 458 8.1.2二维图元及其算法 466 81.3三维图元及其算法 474 8.1.4小结与应用举例 480 8.2基木几何问题 8.21定位问题 482 8.22多边形及其剖分 487 8.23半平面交和低维线性规划 497 824平面剖分 504 8.25运动规划初步 2.6小结与应用举例 518 8.3几何结构及其应用 519 8.31二维凸包与三维凸包 .,519 832二维 Voronoi图 8.33 Delaunay三角剖分 .541 83.4直线的排列 549 835小结与应用举例 55 插图目录 1.1Koh雪花曲线 1.2一种可能的内存情况. 25 1.3串的存储方式... 27 1.4树的相关术语 42 1.5图的直观表示 6数组中的删除操作 44 17链表 44 18二叉树的链式存储法 45 19二叉树的数组存储法 45 1.10树的左儿子右兄弟存储法 ,,46 1.11图的邻接矩阵和邻接表 46 2.1决策树 22字典问题的隐式排序二义树和判定树 58 23子串问题n为偶数时的对立法 61 24凸包的归约 64 25凸包归约框图 64 2.63SUM问题的平方算法 64 27线段分离问题是3SUM难度的 65 2.8路径规划问题是3SUM难度的 66 29路径规划问题的归约框图 210P.NP和co-NP的关系 .67 21NP完全问题 68 22SAT是NP完全的 插图目录 2.13最大团问题 鲁春 70 214 Hamilton回路的子结构 .71 2.15 Hamilton回路的转化 71 2.16 Hamilton回路转化举例 2173着色问题的基本结构 2183着色问题转化举例 74 31数组的基本操作。(a)数组的插入算法。(b)数组的删除算法。(c)数组反 转算法。 32单向链表和双向链表。(a)往单向链表的插入元素q。(b)从单向链表删除 元索q。(c)往双向链表的插入元素q。(d)从双向链表删除元素q。 6 3.3循环链表和双向链表。(a)真实链接关系。(b)虚拟结点做中转是循环链 表。(c)虚拟结点断开是普通链表。 87 3.4栈和队列的实现。(a)栈的实现。(b)队首始终为数组第一个元素时的队 列删除。(c)队首可变时的队列删除. 3.5二叉树。(a)二叉树的递归定义。(b)一棵二叉树 36从前序、中序遍历恢复二叉树 91 37树的表示。(a)一棵树。(b)该树的前向星表示。 3.8煕白棋盘上的问题。(a)黑白棋盘。(b)黑四连块。(c)以某白点为源的距 离标号。 94 3.9二维数组的一维化。(a)编号规则。(b)邻居编号。 94 3.10变形的迷宫问题。(a)最小转弯问题。(b)带钥匙的迷宫问题。 95 3.11建图。(a)最小转弯间题构图。(b)最小转弯问题的改进构图。(c)带钥匙 的迷宫问题构图。 32优先队列的功能 313一棵有14个结点的堆 97 3.14堆的删除最小值操作 97 3.15堆的插入操作 98 3.16并查集的合并操作 3.17并查集的查找操作 100 3.18哈希表的冲突处理。(a)链地址泅。(b)开放地址法。 l01

...展开详情
试读 127P 算法艺术与信息学竞赛+学习指导.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
imbosslx 我还没下载就让我评论啦?
2017-10-21
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享小兵

关注 私信
上传资源赚钱or赚积分
最新推荐
算法艺术与信息学竞赛+学习指导.pdf 50积分/C币 立即下载
1/127
算法艺术与信息学竞赛+学习指导.pdf第1页
算法艺术与信息学竞赛+学习指导.pdf第2页
算法艺术与信息学竞赛+学习指导.pdf第3页
算法艺术与信息学竞赛+学习指导.pdf第4页
算法艺术与信息学竞赛+学习指导.pdf第5页
算法艺术与信息学竞赛+学习指导.pdf第6页
算法艺术与信息学竞赛+学习指导.pdf第7页
算法艺术与信息学竞赛+学习指导.pdf第8页
算法艺术与信息学竞赛+学习指导.pdf第9页
算法艺术与信息学竞赛+学习指导.pdf第10页
算法艺术与信息学竞赛+学习指导.pdf第11页
算法艺术与信息学竞赛+学习指导.pdf第12页
算法艺术与信息学竞赛+学习指导.pdf第13页
算法艺术与信息学竞赛+学习指导.pdf第14页
算法艺术与信息学竞赛+学习指导.pdf第15页
算法艺术与信息学竞赛+学习指导.pdf第16页
算法艺术与信息学竞赛+学习指导.pdf第17页
算法艺术与信息学竞赛+学习指导.pdf第18页
算法艺术与信息学竞赛+学习指导.pdf第19页
算法艺术与信息学竞赛+学习指导.pdf第20页

试读结束, 可继续阅读

50积分/C币 立即下载