算法设计技巧与分析(中文版)阿苏外耶

所需积分/C币:22 2015-03-09 11:02:19 31.56MB PDF
0
收藏 收藏
举报

本书是西安电子科技大学智能科学与技术专业的算法课程用书。本人强力推荐此书,原因是该书的内容详实,最重要的是书中的伪代码的思路清晰,基本上可以照伪代码写出源码。
本书拟用做算法设计和分析领域的教科书,它包含了可作为两学期算法课程的内容 第1章到第⑩0章提供了大学三四年级算法课程的核心材料,有些内容可以跳过,如合并查 找算法的平摊分析、稠图情况下最短路径和最小生成树的线性时间算法。教师可能会发现, 加上后面章节的一些材料,如回溯、随机算法、近似算法或几何扫描是有用的。余下的材料 可作为研究生的算法课程內容。 本书所要求的预备知识已经减到最少,仅需要离散数学和数据结构的基本知识。 感谢 King Fahd university of Petroleum& Minerals( KFUPM,皇家法哈德石油矿业大学)的 支持和对手稿准备提供的方便。本书的编写得到KFUM的项目 ics/algorithm/182的资助。我 还要感谢那些认真阅读手稿各部分并且提出许多有益建议的人,包括一些在KFUM学习算 法课程的本科生和研究生。特别感谢S.Alam,H. Almuallim和 S, Ghanta的有价值的评注。 M.H. alsuwaiyel 第一部分基本概念和算法导引 第1章算法分析基本概念 日日·44‘山自4年·命号·+·D 1.2历史背景 p●td 1.3二分搜索 中···◆顰『曾罪q 4合并两个已排序的表 ···甲p◆ 222367 1.5选择排序…… 6插入排序 鲁■自“4幽自■ ●鼻◆鲁·ψ·■甲◆即曾■即D■■●啁b■ 1.7自底向上合并排序 1.8时间复杂性 D····自↓··4Bs:‘·‘: 12 1.9空间复杂性… ··“·····.············ 1.10最优算法 冒■■■會鲁■号● pd■如● q看景■鲁鲁◆●●自dp 1.11如何估计算法运行时间 ◆■即 21 1.12最坏情况和平均情况的分析 …26 1.13平摊分析…… ………………29 1.14输入大小和问题实例 章●●●●● ▲自自自命命●啁·●● 甲q甲罩即p司自啬番电 1.15练习……… 1.16参考注释 中旱·卓日b···■郾D自▲中命·中44p◆『咱卡日p甲q■昏 38 第2章数学预备知识 ■旱◆·b昏音◆b鲁·◆自自■■自■自■血·血■甲单●·◆·◆々···日·■■聊 卓■看山·■口■ 2.1集合、关系和函数… 2.2证明方法 自鼻中中甲●·D4甲◆看·●● 41 23对数 .··d‘; 24底函数和顶函数……… ■■卓鲁44自↓◆p“◆聊费『即『Ppp■ 45 25阶乘和二项式系数……………………………………………45 2.6鸽巢原理………… 48 27和式……… ·◆會·司●ψd■b●曲●●●命 48 28递推关系 52 29练习… …63 第3章数据结构 自县鲁·命咖甲司甲看看●●普 3.1引言 3.2链表… 3.3图…… ···········旱·唱日·◆···甲··日日●·■·●···日q昏日·D看自·dp 34树 3.5根树 36二叉树 …71 3.7练习 38参考注释 怪自幽●· 第4章堆和不相交集数据结构 ∴74 4.1引言… ◆·會聊D·自昏bp 4.2堆 冒鲁■■鲁q··鲁■卩·■■吾··晕帽●●郾p會啁鹵·q●自自聊●●·■非喜自·啁D看省■曲D●bp·■■ 备↓·自命··自b·中即卡·卢· ∴……·74 4.3不相交集数据结构…… 4练习……… q鲁·聊曾■专甲■即q甲D即●萨卾■q音■■看·會看●卩鲁4p看聊音自D聊看■D自■■·血●昔自曲 4.5参考注释 第二部分基于递归的技术 …………………89 第5章归纳法 5.1引言 卾◆·咖冒·卾如卾甲即ψ曾q■甲■■斷卾■■■■聊看∮卩●b●p自tp●■·自●血 t●■■● 5.2两个简单的例子… 5.3基数排序 自▲备幽聊●▲ 甲看p·电 中甲。◆甲要罪 54整数幂 ◆4·*·4 會甲·日「昌·鲁号昏帚·冒會自φ1會bpψ毒音p 5.5多项式求值( Homer规则)………… 56生成排列……………………… ●量●看非●◆ 5.7寻找多数元素 ······『·····.··『·D日山吾自BD 294989 58练习 ■■■曾■自自萨■自■品p着自■自晶m·●备 59参考注释 101 第6章分治… 6.1引言 ………………………102 6.2二分搜索… tq血命咖罪q·血 6.3合并排序 ●·辛p看申pp ●中看 105 6.4分治范式 …………107 65寻找中项和第k小元素……… ●自■·血 109 66快速排序 争● ……112 67大整数乘法 ………118 68矩阵乘法 专·申··D申◆··命甲曾··自■ψ晋自中會■即咖。申甲『■啁曾曾■鲁看。■■D4●D 鲁 l19 6.9最近点对问题 121 6.10练习 …124 6.11参考注释 中■◆·中咖P··曾甲『◆會 …128 第7章动态规划 p■p .1引言 聊d·■■ 身备qP會■即◆看P聊 124 72最长公共子序列问题 1 73矩阵链相乘……………………………………………………………132 74动态规划范式 …136 7,5所有点对的最短路径问题 136 7.6背包问题… 138 7.7练习 旨●口甲骨音■曾■冒《d甲伊冒雪雪●甲q看●即口。■鲁看即●■■p■●個■■■■曲曲■p■·包血■■■b 78参考注释 日鲁pd山b 第三部分最先割技术 中↓b聊鲁個◆电會ψ啁·4自音b■■_d也督·■食自●音p■_●日■bD自曲曲音■bp■温 ……145 第8章贪心算法 ……146 ●山◆·■自4罪·●单自命D●自命 8.1引言 8.2最短路径问题 ●◆·聊卩『●4 8.3最小耗费生成树( Kruskal算法)… 15 8.4最小耗费生成树(Pim算法) 153 85文件压缩 食中●◆·◆ ■■ 4·44··日··44····· ……157 8.6练习 ◆ψ鲁帽●d●聊D●d■自看◆自◆自■tp4pb 159 8.7参考注释 161 第9章图的遍历 旱卩會唱●音罪D·看自·d4自看■·◆ 162 9.1引言 ■·鲁备自命·晶 162 92深度优先搜索 ∷∷162 93深度优先搜索的应用…………………………………………………1 94广度优先搜索 9,5广度优先搜索的应用 食1看 96练习 Pd·d司pb血ppD口mm●dp■ ·a··日··:■ 9.7参考注释 第四部分问题的复杂性 ■■■ ……………………………173 第10章NP完全问题 ●。1曾即■■ 4■■■■■■ ……………174 10.1引言 10.2P类 4甲····4··4··4··自··卜· 曾甲·昌吾晶 ·。。·申■b● ……176 I0.3NP类………………………………………… 176 10.4NP完全问题 卩·罩『■■鄙鲁自··自自■■4自p■■●血b命t 177 10.5coNP类 182 10.6NI类 183 10.7四种类之间的关系 p鲁看■●●音血b血血血咖■申自甲要咖ψ命 ●音個D看血p者■自 18 08练习 10.9参考注释 ↓·●·◆ψ曾■ψ·ψ·■■鲁曾冒■●即pb■·晷b··t罪b音b ……186 第11章计算复杂性引论 ■■■鲁鲁·■』 …I87 11.1引言 ◆甲p■血■d■■●音■●■申 I87 12计算檩型图灵机 中 角t曾争日D■萨看面 87 l1.3k带图灵机和时间复杂性…… 18 11.4离线图灵机和空间复杂性… 189 11.5带压缩和线性增速 91 116复杂性类之间的关系 …191 11.7归约 甲要甲甲曾中甲 甲聊甲甲 118完全性 ●d↓pp看 11.9多项式时间层次 203 11.10练习 205 11.11参考注释… 208 第12章下界 2.1引言 曾■冒·冒鲁D■冒■罪鲁曾q鲁鲁即唱■·■■·看P看 ■鲁命早·■看■P鲁甲■b号甲·命聊●·鲁罪b■量●●吾●@D●鲁曹 12.2平凡下界 ……209 12.3决策树模型 ………………209 124代数决策树模型 司 211 12.5线性时间归约 213 126练习… P●卓 ………214 12.7参考注释 ………216 第五部分克服困难性 ■■■■■省 217 第13章回溯法… 218 13.1引言 218 13.23着色问题 普4日BD日日日·日日日日日日日日·日日.·『日日日日日↓sD日日日吾 ■■自自■鲁4自鲁■自命命●自A血串晶卓● 218 1338皇后问题 134-般回溯方法… ·會自●·····。◆·■■◆中·鲁●··身 …223 13.5分支限界法 會■P●冒■鲁冒·争 225 6练习… ………………227 13.7参考注释… 中号『甲旷看 号。■。● 甲看■甲口●1甲即 ■■ 228 第14章随机算法 14.1引言… ·自·■ψ···甲■即甲即甲■◆导即甲甲■甲曾普·即·即即即学《看即甲即q●导唱■即即吧《罪即罪即聊d■會會會 42 Las vegas和 Monte carlo算法… 229 14.3随机化快速排序 ■鲁■章罩■p■罩■●會■●章罩會冒D·■●鲁■音卩●●●●d 230 14.4随机化的选择算法… 231 l4.5测试串的相等性 ……232 4.6模式匹配 国导●早●罩 ■·章晉■●●昏·ψ●昏■●督●●●■會自·●■●音·b音画自d音■■ 234 14.7随机取样 ……235 14.8素数性测试… 會哥罩·?■ 237 14.9练习…………………………………………24L 14.10参考注释 242 第15章近似算法 244 15.1引言……………… 4·····◆········-● 44 152基本定义…………… 5.3差界 …………………∵245 15.4相对性能界 申···如‘甲 246 15.5多项式近似方案………………………………………250 15.6完全多项式近似方案 ●Pqp《■D口■■●看血山d血自■画血山 253 15.7练习… 即↓■聊●■自自『鲁D看 15.8参考注释 ●看p 第六部分域指定问题的迭代改进 唱鲁D■自自幽自自咖带即·甲罪··阝●·●t看也■。音 259 第16章网络流 ↓·、"··、:p:···:吾t◆.p日·日-aa·‘dd·4----·;b··↓;; 16.1.引言 260 16.2预备知识 看甲·會■自自■■●46血↓曲 ■·◆·· 260 6.3 Ford-Fulkerson方法 ■聊會dψ■·音P画曲 262 16.4最大容量增值… 号旱■■罪●唱·q吾自 263 16.5最短路径增值 申d 264 166 Dinic算法 16.7MPM算法……………………………………………………269 16.8练习 中·甲咱即曾甲·即哥甲pp“看 270 16.9参考注释 血●■···即自吾吾音当·■自中·4··4·.s·旷q 早●e …271 第17章匹配… 17.1引言 272 172预备知识 日口日···甲曾日··●●甲阝4bt日Db·◆看 272 173网络流方法… D画● 274 174二分图的匈牙利树方法 卓·即4自P 274 17.5一般图中的最大匹配 甲■··鲁命 ……………276 176二分图的O(n23)算法 ●qp自_↓甲·聊●D◆ψ甲·■■日■晶奇命 17.7练习……… 178参考注释 辛即·鲁即甲甲■鼻 286 第七部分计算几何技术 …∴…287 第18章几何扫描 争鲁即●音● ●鲁鲁香自。自●甲如。 288 18.1引言 ■咖■■命。 38 18.2几何预备知识… q音罪●晶血●血山自 289 183计算线段的交点 ··t卓··◆卓即曾日·日日p日日“·甲q甲罪 h;◆■ 18.4凸包问题 q·中日日日4·吾4中44··『··“日日二 292 18.5计算点集的直径 .t·········“.······。·↓.·.···"·‘=…日自;卜省 18.6练习 ·■日■郾·命●·◆● 冒曾口鲁鲁■幽血命卓自■ ●●自 18.7参考注释 ……299 第19章 Vorono图解… ……300 19.1引言 db↓鲁■音■口p着d自着■b■ ■自自■自■■自■番晶画b 300 192最近点 图解 19.3 Voronoi图解的应用 ■鲁甲甲甲甲即甲罪甲甲●p罪甲 194最远点 voronoi图解 ……306 19.5最远点 voronoi图解的应用 308 196练习 看●电■■昌■■■●曲D是▲■ 309 19.7参考注释… 310 参考文献 节甲要要即『■p 311 12 第一部分基本概念和算法导引 本书的这一部分研究算法设计和分析的基本工具与准备知识。 第1章是为本书其余部分做准备的。这一章将讨论一些简单算法的例子,这些算法用来 解决几乎在所有计算机科学应用中都会遇到的基本问题,包括搜索、合并和排序。参考这些 示例算法,接着研究作为算法分析基础的数学知识,尤其对如何分析一个给定算法的运行时 间和所需空间进行了详细研究。 第2章研究的是算法分析所需的最基本的数学背景知识,详细讲述了分析算法时最常遇 到的求和与递推关系。需要着重强调的是分治递推的解决方法,因为它是分析分治这一大类 算法的基础。这里不打算在本书中讨论一般递推式的解与生成函数的方法,要详细了解这部 分内容的读者,可以参考标准的离散数学书。 第3章回顾了一些在算法设计中经常使用的基本的数据结构。本章没有深入进行讨论, 如要了解更加全面的知识,可以参考标准的数据结构书 第4章较详尽地讨论用来保持优先队列和不相交集的两种基本数据結构。在许多有效算 法中(特别是图的算法设计中),这两种数据结构(堆和不相交集数据结构〕被用做构件模块 本书中,堆用来设计有效排序算法ⅧAⅣORT。在第8章中,堆还是解决单源最短路径问題、 最小生成树问题和为数据压缩寻找可变长编码问题的有效算法,堆也被用在分支服界法中 (在135节讨论)。8.3节的算法 KRUSKAL将用不相交集数据结构来子找无向图中的最小生 成树。在有关文献中,这两种数据结构都被广泛用来设计更加复杂的算法。

...展开详情
试读 127P 算法设计技巧与分析(中文版)阿苏外耶
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
蓝色之眼 好书不错,挺好的
2015-07-21
回复
kongming888 书很好很清楚
2015-03-16
回复
上传资源赚积分or赚钱
    最新推荐
    算法设计技巧与分析(中文版)阿苏外耶 22积分/C币 立即下载
    1/127
    算法设计技巧与分析(中文版)阿苏外耶第1页
    算法设计技巧与分析(中文版)阿苏外耶第2页
    算法设计技巧与分析(中文版)阿苏外耶第3页
    算法设计技巧与分析(中文版)阿苏外耶第4页
    算法设计技巧与分析(中文版)阿苏外耶第5页
    算法设计技巧与分析(中文版)阿苏外耶第6页
    算法设计技巧与分析(中文版)阿苏外耶第7页
    算法设计技巧与分析(中文版)阿苏外耶第8页
    算法设计技巧与分析(中文版)阿苏外耶第9页
    算法设计技巧与分析(中文版)阿苏外耶第10页
    算法设计技巧与分析(中文版)阿苏外耶第11页
    算法设计技巧与分析(中文版)阿苏外耶第12页
    算法设计技巧与分析(中文版)阿苏外耶第13页
    算法设计技巧与分析(中文版)阿苏外耶第14页
    算法设计技巧与分析(中文版)阿苏外耶第15页
    算法设计技巧与分析(中文版)阿苏外耶第16页
    算法设计技巧与分析(中文版)阿苏外耶第17页
    算法设计技巧与分析(中文版)阿苏外耶第18页
    算法设计技巧与分析(中文版)阿苏外耶第19页
    算法设计技巧与分析(中文版)阿苏外耶第20页

    试读结束, 可继续阅读

    22积分/C币 立即下载 >