[算法设计技巧与分析(中文版)].阿苏外耶.扫描版.pdf

所需积分/C币:50 2015-10-20 10:46:59 31.56MB PDF
收藏 收藏
举报

无需下载点 直接可以下载 服务要学习的人
本书拟用做算法设计和分析领域的教科书,它包含了可作为两学期算法课程的内容 第1章到第⑩0章提供∫大学三四年级算法课程的核心材料,有些内容可以跳过,如合并查 找算法的平摊分析、稠图情况下最短路径和最小生成树的线性时间算法。教师可能会发现 加上后面章节的一些材料,如回溯、随机算法、近似算法或几何扫描是有用的。余下的材料 可作为研究生的算法课程内容。 本书所要求的预备知识已经减到最少,仅需要离散数学和数据结构的基本知识。 感谢 King Fahd university of Petroleum& Minerals( KFUPM,皇家法哈德石油矿业大学)的 支持和对手稿准备提供的方便。本书的编写得到 KFUPM的项目 ics/ algorithm/182的资助。我 还要感谢那些认真阅读手稿各部分并且提出许多有益建议的人,包括一些在 KFUPM学习算 法课程的本科生和研究生。特别感谢S. Albassam,H. Almuallim和 S. Ghanta的有价值的评注。 M.H. alsuwaiyel 第一部分基本概念和算法导引 第1章算法分析基本概念 1.1引言……… ◆··卡· 1.2历史背景 看自甲音t电●D口■4看p看曲p■曲tp山血画 13二分搜索 4合并两个已排序的表 导甲甲甲qp看■督鲁曲血 222367 5选择排序… 1.6插入排序……… 血自▲幽血·即命卓●pd·b 1.7自底向上合并排序… 789 1.8时间复杂性……… …………………12 1.9空间复杂性…… "·日 1.10最优算法 号导甲■看即鲁口@阝。■■着■■■ 1.11如何估计算法运行时间 ·昏■·司●●·音●●■自p■画 ………21 1.12最坏情况和平均情况的分析 b●P 1.13平摊分析… 1l4输入大小和问趣实例… 1.15练习 1.16参考注释… 38 第2章数学预备知识… 39 集合、关系和函数 2.2证明方法 鲁·昏聊卡·。管兽D曲 2.3对数 q■昌■幽画日命4卡·●●● 24底函数和顶函数 45 25阶乘和二项式系数 ……………45 26鸽巢原理 中.···.°··...··...·44·4··:··4··FD···“4a·· 2.7和式 28递推关系… ··4命····.·····=甲=■ 52 29练 第3章数据结构 血● …67 3.1引言……… 单b自卓·导●唱··◆·●·q曾冒會日bb·日自曲命卓pd 67 32链表 3.3图… 3.4树 ●●看■鲁鲁··●■命命命b 7 3.5根树 36二又树… 3.7练习…… 72 38参考注释 a-aa日·:‘.a.·日·4·‘“··山·日4.4·4·‘·甲····=·····甲···■ 第4章堆和不相交集数据结构… …74 4.1引言 74 4.2堆……………………………………………………………………74 4.3不相交集数据结构… ····日·卡·日日···.44s品·· 80 4.4练习… 4.·······早‘·······*···‘4···········甲·.吾卜口 4.5參考注释 …M88 第二部分基于递归的技术…… ·······44····.中··.日↓·日 第5章归纳法 5.1引言 ·自命甲 ◆■■奋司●4 52两个简单的例子…… 日昏···4·.;···吾自B‘自血 5.3基数排序 q早P鲁■P h·■p自▲·■备山D备● 92 5.4整数幂 命d 4·甲曾看■甲旱甲自”唱·晷晷警日《昏鲁▲D■自山》↓D■·●●·●晶dp●b· 5.5多项式求值( Homer规则) 56生成排列……………………………………………………… 5.7寻找多数元素… 58练习 9%g ■■■冒罩●◆■p■■■P哥·q看 ●看冒b●● 59参考注释 第6章分治 血4◆即 62二分搜索 63合并排序… ■■p即■■ 鲁郾p■看d鲁p鲁曲 4··4·占*°甲4·中 105 64分治范式 幽■■·即■自■由申中■自中由■血· …I07 6.5寻找中项和第k小元素 甲甲■申冒罪即·自■·司■即··p■甲看p■■·兽着●·■幽●■ 自自P 66快速排序 112 67大整数乘法 118 68矩阵乘法……… ……………………119 69最近点对问题 ···罪····曾···↓···.D·D4..···◆44·吾b自 121 6.10练习 鲁■鲁D■■·司唱D■■↓郾郾·自自画暴』·■‘自申喜■■自善“■鲁备咖晶晶命● 124 6.11参考注释 第7章动态规划 即■t■p■『日b看■都 7.1引言 …12 72最长公共子序列问题… 73矩阵链相乘 ···日b■···音自b■日·看·血■日·↓ψ督·.·歌·44◆即p·■■p■■晷■●·■■ψ■· 7.4动杰规划范式 136 7.5所有点对的最短路径问题 ↓····中司··· …I36 76背包问题 138 7.7练习 甲會●甲量p看口甲鲁■『■■甲口會督甲甲q甲甲看看口甲●啁p甲冒■鲁冒口鲁D■p曲看 140 78参考注释 144 第三部分最先割技术 ◆·自申■■◆會■血▲·自自會■■■■血■p·▲·■●p■▲●有■自命命要▲郾·幽 145 第8章贪心算法… 146 8.1引言 146 8.2最短路径问题 自即●申·p甲·● 83最小耗费生成树( Kruskal算法) ··.幽中··‘..4·日日‘ 151 84最小耗费生成树(Pmm算法) 153 8.5文件压缩 命白◆即食4 ■号■ ■鲁↓·b卓电鲁暑由● 157 86练习 山■看 学单鲁■画●···p·甲年·甲Db·m甲● 鱼日自自血 159 87参考注释 161 第9章图的遍历 ………………162 9.1引言 92深度优先搜索 申●●●●■司●● 93深度优先搜索的应用 ●●啁●雪即吾自ψ即■■命甲罪量看·自D會■自甲·看 165 94广度优先搜索………… ■备4。自■自。命·自备 ··“.a4··甲;日·····*◆·D◆ …169 95广度优先搜索的应用 产鲁◆■■即音甲即■■阝■4D4■dmb 96练习… 97参考注释 第四部分问题的复杂性 ··.········4·中··.········日F·····命‘·B·日自4日日吾备日。d“4 173 第10章NP完全问题… 4·昏日■◆辛·西ψ·血d■■音■■命血血看▲·n自●可p 10.1引 174 10.2P类 ···P····中···↓···→··『日“··b4pb ………176 10.3NP类 176 10.4NP完全问题 即◆■『罪 即 l77 10.5cNP类 白◆甲■即·ψ甲■p●量电甲司看啁4·歌●d 号西血●● 182 10.6NP类 ········中中s◆ ……………………183 10.7四种类之间的关系 ▲·唱↓自击早·●·自ψ自兽聊伊·●·中要中會●_■ 10.8练习 10.9参考注释 ··ψ■···●··口·■『··卩吾■谭聊曾●音音■P看D●音▲▲西■·◆看自自●d·☆司 186 第11章计算复杂性引论… 单罪···吧鲁 ………187 11.1引言 187 1.2计算檩型图灵机 ■■鲁·甲鼻··幽●··即·vD·咖甲『■郾■即q4■晶44■画命●▲乌聊 87 11.3k带图灵机和时间复杂性… 18 11.4离线图灵机和空间复杂性 189 11.5带压缩和线性增速 191 116复杂性类之间的关系… 191 11.7归约 ●●中●bd甲● 118完全性 ↓·血哥■◆ …·198 11.9多项式时间层次 203 11.10练习 鲁■■鲁画鲁 205 11.11参考注释 …208 第12章下界 12.1引言…… 209 12.2平凡下界………… 209 12.3决策树模型 电申噜會甲看p甲甲甲p甲冒看看甲日D●pD■即 124代数决策树模型 甲甲甲甲?即會甲『。。■ 211 12.5线性时间归约… 213 12.6练习… ………………………214 12.7参考注释 216 第五部分克服困难性 罪■● 2l7 第13章回溯法 ■■■幽●■幽鲁鲁■鲁↓■■口■4■■■口看看曲鲁 幽卓咖。·自●● 13.1引言 218 13.23着色问题… ■■p■■■■ 日4『『日·日日·『日日·日s‘B日吾◆ 218 1338皇后问题 134一般回溯方法 ·P 13.5分支限界法… p■■口口■■■●■■ 225 13.6练习 227 13.7参考注释 ·····qv··· ……………………………228 第14章随机算法… 229 4.1引言……………… 曾谭·■『冒◆曾口會會■■■■冒罾晕曾·即■■■鲁鲁■即p■《■备鲁■鲁自自■各“■鲁鲁■司t■■●自■邮 42 Las vegas和 Monte carlo算法 ■曾 229 14.3随机化快速排序 14.4随机化的选择算法 q■曾看■甲■即看 ■p■■■■■备鲁■自··■自鲁 14.5测试串的相等性… 232 14.6模式匹配 會●·『■音啁·會p自■晋■·↓ψ●D日·血●啁●pψp■看·bb血■d■■自■曲■ 鲁晶■争鲁■·自命邮●·自■44◆●●● 234 14.7随机取样 血·申t◆申自會◆奇曾中·要甲■?管甲。甲。看口 p■看個鲁口甲p《鲁■■■■■曲品 235 148素数性测试 …237 14.9练习 ··.··早···°··°···4·.;····日·日會···4·西↓日···香P自自‘·a品44·4· 14.10参考注释 242 第15章近似算法 244 15.1引言… ●pd幽◆甲●亡●自自··● …………………………244 15.2基本定义……… 244 15.3差界…… 2 15.4相对性能界……… 看■督■■ 246 15.5多项式近似方案 250 15.6完全多项式近似方案… 253 15.7练习………… 158参考注释 ●····卾卾···甲DP甲■■章曹罪◆●p鲁郾p看■·d鲁 ·自即即■单看p·《看『●甲着 25 第六部分域指定问题的迭代改进 4音号●自中即D即即■p口■ 259 第16童网终流 早■■t·自自自中·◆自44咱嘻◆ 甲督■口●鲁 260 16.Ⅰ ◆中甲·●哪 ■鲁 162预备知识 ◆备甲 260 6.3Frd- Fulkerson方法 262 16.4最大容量增值…… ■自幽卓●■·鲁鼻◆● 263 6.5最短路径增值…… 166 Dinic算法 ●會P噜■着4·p加命日备p·t 2 16.7MM算法 ◆·卾身■自ψ■■·昏q看晷■聊■·ψ·罪昏备自血喜■●·p■▲画4 68练习 270 16.9参考注释 鲁鲁■b命··看■即●●b番 ■自·中卾■■申甲甲晷。●看罪·bd幽 号山口 271 第17章匹配 17.1引言 鲁◆学P··鲁● 272 172预备知识 ...·.44·4·‘·······4日··..4··4·4“··4““日a▲如a4 173网络流方法 ●■血4◆D 274 174二分图的匈牙利树方法 ■Dψ ●◆■■▲看■■■■看 274 175一般图中的最大匹配 中●普·· …………276 176二分图的0(n25)算法 281 177练习 ■■·鲁■鲁■■■命■■■▲· 曾·····●「···b看p●◆p·自即咖邮即P看■p 178参考注释 ·4·●单p●·■即q■ 286 第七部分计算几何技术 ■中甲司■音■ 28 第18章几何扫描… ↓●·■D●甲聊看昏兽···画··西ψ鲁如吾ψ·φ··甲咖●中甲日··暑看即甲■音自命p晶 288 8.1引言 b●甲P●■●p■曲郾 咖會看會咖■■■■曲▲●昌画 18.2几何预备知识… :·…289 18.3计算线段的交点 日曾b自■昌自◆●昌◆pp·。冒·血 18.4凸包问题…… ………292 18.5计算点集的直径 司●■身自_自 295 6练习 18.7参考注释 第19章 Voronoi图解… 300 19.1引言…… ··········.·····甲甲→··.··4·日日····吾·l··4·d“日4a 192最近点 morone图解………… 300 19.3 voronoi图解的应用 304 194最远点 Voronoi图解 甲··看····口·■■··卩◆■·◆·日自哥阝●·即看·非ψ◆p自备■自自自■■萨■‘·幽▲▲ 306 19.5最远点 voronoi图解的应用 308 19.6练习 咖一曾晋甲甲甲即Pqp。■p看●●■■着■■p ■甲甲■·中●●p 幽·罪 197参考注释 ■早甲■伊日D■鲁■■D看 鲁↓■音量血 …310 参考文献 311 12 第一部分基本概念和算法导引 本书的这一部分研究算法设计和分析的基本工具与准备知识。 第1章是为本书其余部分做准备的。这一章将讨论一些简单算法的例子,这些算法用来 解决几乎在所有计算机科学应用中都会遘到的基本问题,包括搜索、合并和排序。参考这些 示例算法,接着研究作为算法分析基础的数学知识,尤其对如何分析一个给定算法的运行时 间和所需空间进行了详细研究。 第2章研究的是算法分析所需的最基本的数学背景知识,详细讲述了分析算法时最常遇 到的求和与递推关系。需要着重强调的是分治递推的解决方法,因为它是分析分治这一大类 算法的基础。这里不打算在本书中讨论一般递推式的解与生成函数的方法,要详細了解这部 分内容的读者,可以参考标准的离散数学书。 第3章回顾了一些在算法设计中经常使用的基本的数据结构。本章没有深入进行讨论 如要了解更加全面的知识,可以参考标准的数据结构书 第4章较详尽地讨论用来保持优先队列和不相交集的两种基本数据结构。在许多有效算 法中(特别是图的算法设计屮),这两种数据结构(堆和不相交集数据结枘〕被用做构件模块。 本书中,堆用来设计有效排序算法HAⅣSORT。在第8章中,堆还是解决单源最短路径问题、 最小生成树问题和为数据压缩寻找可变长编码问题的有效算法,堆也被用在分支限界法中 (在135节讨论)。83节的算法 KRUSKAL将用不相交集数据结构来寻找无向图中的最小生 成树。在有关文献中,这两种数据结构都被广泛用来设计更加复杂的算法。

...展开详情
试读 127P [算法设计技巧与分析(中文版)].阿苏外耶.扫描版.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分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币 立即下载 >