全新正版现代算法设计与分析9787111679554机械工业

出版者的话<br/>译者序<br/>前言<br/>致谢<br/>章　模型与分析1<br/>　1.1　计算斐波那契数1<br/>　1.2　快速乘法3<br/>　1.3　计算模型3<br/>　1.4　随机算法简介4<br/>　　1.4.1　另一种随机算法6<br/>　1.5　计算模型8<br/>　　1.5.1　外部存储器模型8<br/>　　1.5.2　并行模型8<br/>　拓展阅读10<br/>　习题10<br/>第2章　概率基础与尾部不等式13<br/>　2.1　概率基础13<br/>　2.2　尾部不等式17<br/>　.　生成随机数20<br/>　　..1　生成具有任意分布的随机变量21<br/>　　..2　由顺序文件生成随机变量21<br/>　　..　生成随机置换<br/>　拓展阅读25<br/>　习题25<br/>第3章　热身问题27<br/>　3.1　计算公因子的欧几里得算法27<br/>　　3.1.1　扩展欧几里得算法27<br/>　　3.1.2　在密码学中的应用28<br/>　3.2　寻找第k小的元素28<br/>　　3.2.1　选择随机的划分元29<br/>　　3.2.2　中位数的中位数30<br/>　3.3　词的排序32<br/>　3.4　可归并的堆34<br/>　　3.4.1　归并二项堆35<br/>　3.5　一个简单的半动态词典35<br/>　　3.5.1　势能法与平摊分析36<br/>　3.6　下界37<br/>　拓展阅读39<br/>　习题39<br/>第4章　优化Ⅰ：蛮力法与贪婪策略42<br/>　4.1　启发式搜索方法42<br/>　　4.1.1　博弈树44<br/>　4.2　贪婪算法的框架46<br/>　　4.2.1　支撑树49<br/>　　4.2.2　寻找权值子集49<br/>　　4..　一个调度问题50<br/>　4.3　支撑树算法的高效数据结构51<br/>　　4.3.1　并查集的一种简单数据结构52<br/>　　4.3.2　更快的方案53<br/>　　4.3.3　增长慢的函数54<br/>　　4.3.4　整合55<br/>　　4.3.5　仅做道路压缩56<br/>　4.4　不同形式的贪婪策略57<br/>　4.5　与贪婪策略的折中58<br/>　4.6　梯度下降59<br/>　　4.6.1　应用63<br/>　拓展阅读65<br/>　习题66<br/>第5章　优化Ⅱ：动态规划69<br/>　5.1　背包问题70<br/>　5.2　上下文无关文法的解析71<br/>　5.3　单调子序列72<br/>　5.4　函数逼近74<br/>　5.5　似然估计的Viterbi算法75<br/>　5.6　树中的权独立集76<br/>　拓展阅读76<br/>　习题77<br/>第6章　查找80<br/>　6.1　跳表——一个简单的字典80<br/>　　6.1.1　跳表的构造80<br/>　　6.1.2　分析81<br/>　　6.1.3　更强的尾部估计82<br/>　6.2　树堆：随机查找树83<br/>　6.3　全域哈希86<br/>　　6.3.1　全域哈希函数的存在8<br/>　6.4　完美哈希函数88<br/>　　6.4.1　将期望界转换为差情况的界89<br/>　6.5　一个复杂度为log log N的优先级队列89<br/>　拓展阅读91<br/>　习题92<br/>第7章　多维查找与几何算法94<br/>　7.1　区间树与范围树94<br/>　　7.1.1　一维范围查找94<br/>　　7.1.2　二维范围查找96<br/>　7.2　kd树97<br/>　7.3　优先级查找树99<br/>　7.4　平面凸包101<br/>　　7.4.1　Jarvis March算法102<br/>　　7.4.2　Graham扫描算法102<br/>　　7.4.3　排序与凸包103<br/>　7.5　快速凸包算法104<br/>　　7.5.1　分析105<br/>　　7.5.2　期望运行时间106<br/>　7.6　使用持久化数据结构的点定位107<br/>　7.7　增量构造法109<br/>　拓展阅读111<br/>　习题111<br/>第8章　字符串匹配与指纹函数114<br/>　8.1　RabinKarp指纹字符串查找算法114<br/>　8.2　KMP算法117<br/>　　8.2.1　KMP算法的分析120<br/>　　8.2.2　模式分析120<br/>　8.3　字典树及其应用121<br/>　拓展阅读1<br/>　习题1<br/>第9章　快速傅里叶变换及其应用125<br/>　9.1　多项式求值与插值125<br/>　　9.1.1　多项式相乘126<br/>　9.2　CooleyTukey算法126<br/>　9.3　蝶形网络128<br/>　9.4　SchonageStrassen快速乘法算法129<br/>　9.5　广义字符串匹配131<br/>　　9.5.1　基于卷积的方法131<br/>　拓展阅读133<br/>　习题133<br/>0章　图算法135<br/>　10.1　深度优先搜索135<br/>　10.2　深度优先搜索的应用138<br/>　　10.2.1　强连通分支138<br/>　　10.2.2　双连通分支140<br/>　10.3　道路问题142<br/>　　10.3.1　BellmanFord单源短道路算法143<br/>　　10.3.2　Dijkstra单源短道路算法143<br/>　　10.3.3　任意两点之间的短道路算法145<br/>　10.4　计算赋权图中的支撑子145<br/>　10.5　全局割148<br/>　　10.5.1　收缩算法149<br/>　　10.5.2　割的概率149<br/>　拓展阅读150<br/>　习题151<br/>1章　流及其应用153<br/>　11.1　流的质与算法155<br/>　　11.1.1　流与割155<br/>　　11.1.2　FordFulkerson算法156<br/>　　11.1.3　EdmondKarp可增广道路策略157<br/>　　11.1.4　单调引理及迭代次数的界158<br/>　11.2　流的应用159<br/>　　11.2.1　边不相交的道路159<br/>　　11.2.2　二部图的匹配159<br/>　　11..　环流问题162<br/>　　11.2.4　项目规划164<br/>　拓展阅读165<br/>　习题165<br/>2章　NP完全与近似算法168<br/>　12.1　分类与可归约170<br/>　12.2　CookLevin定理172<br/>　1.　常见的NP完全问题173<br/>　12.4　NP完全的明175<br/>　　12.4.1　顶点覆盖及相关问题175<br/>　　12.4.2　图的3着色问题176<br/>　　12.4.3　背包问题及相关问题177<br/>　12.5　重要的复杂度类179<br/>　12.6　使用近似算法处理困难11<br/>　　12.6.1　背包问题182<br/>　　12.6.2　集合覆盖183<br/>　　12.6.3　几何旅行商问题184<br/>　　12.6.4　3着色问题185<br/>　　12.6.5　割问题185<br/>　拓展阅读186<br/>　习题186<br/>3章　降维188<br/>　13.1　随机投影与JohnsonLindenstrauss引理188<br/>　13.2　高斯消元法191<br/>　13.3　奇异值分解及其应用192<br/>　　13.3.1　矩阵代数与SVD定理192<br/>　　13.3.2　使用SVD的低秩近似194<br/>　　13.3.3　低秩近似的应用196<br/>　　13.3.4　聚类问题197<br/>　　13.3.5　SVD定理的明199<br/>　拓展阅读200<br/>　习题200<br/>4章　并行算法201<br/>　14.1　并行计算模型201<br/>　14.2　排序和比较问题202<br/>　　14.2.1　寻找值202<br/>　　14.2.2　排序204<br/>　14.3　并行前缀208<br/>　14.4　基本的图算法212<br/>　　14.4.1　列表排名212<br/>　　14.4.2　连通分支214<br/>　14.5　基本的几何算法216<br/>　14.6　并行模型之间的关系217<br/>　　14.6.1　网格上的路由218<br/>　拓展阅读220<br/>　习题220<br/>5章　层次化存储结构及高速缓存2<br/>　15.1　层次化存储模型2<br/>　15.2　矩阵转置224<br/>　　15.2.1　矩阵乘法225<br/>　15.3　在外部存储器中进行排序226<br/>　　15.3.1　我们可以改进这个算法吗227<br/>　15.4　高速缓存参数无关的算法设计228<br/>　　15.4.1　参数无关的矩阵转置229<br/>　拓展阅读1<br/>　习题2<br/>6章　流数据模型<br/>　16.1　引言<br/>　16.2　查找流中的频繁元素<br/>　16.3　流中的相异元素<br/>　16.4　频数矩问题及其应用<br/>　　16.4.1　均值的中位数241<br/>　　16.4.2　二阶频数矩的特例241<br/>　16.5　流模型下界的明243<br/>　拓展阅读244<br/>　习题245<br/>附录A　递推关系与生成函数247<br/>参考文献253

---作者简介---<br><br>桑迪普?森（SandeepSen）印度理工学院德里分校计算机科学与工程系教授，印度科学院院士，印度科学院院士，研究领域包括随机算法、计算几何、动态图算法和计算模型等。曾在IBM研究实验室、微软研究实验室、北卡罗莱纳大学教堂山分校等机构担任访问研究员。<br><br>阿米特?库玛尔（AmitKumar）印度理工学院德里分校计算机科学与工程系教授，印度科学院院士，研究领域包括组合优化、调度、图论和聚类等。曾任职于贝尔实验室，并曾在微软印度研究院和IBM印度研究院担任访问教授。曾荣获2018年印度ShantiSwarupBhtanagar数学科学奖。<br><br>---译者简介---<br>刘铎于清华大学计算机科学与技术系获工学博士，现为北京交通大学软件学院副教授。主要研究方向为应用密码学、信息安全、组合算法的设计与分析。主持和参与、省部级科研项目多项，以作者身份在各类重要刊物和会议上发表20余篇，目前主持建设并讲授的“离散数学”课程被评为首批（线上）课程。