算法基础 打开算法之门 内容简介

算法基础 打开算法之门 内容简介

算法基础 打开算法之门 目录

算法基础 打开算法之门 精彩文摘

《算法导论》作者托马斯 H. 科尔曼面向大众读者的算法著作理解计算机科学中关键算法的简明读本,帮助您开启算法之门你想知道你的GPS是如何在几秒钟内从看起来无数多条可能路径中找到到达目的地的快捷路径的吗?当你在网上购物时,你的信用卡账号是如何被保护的呢?答案均是算法。本书是关于计算机算法基础的指南。在本书中,作者展示了计算机如何通过算法解决问题。读者将学习到什么是计算机算法,如何描述计算机算法,以及如何评估计算机算法。读者还将学习到在计算机中查找信息的简单方法;在计算机中将信息按照某个预定的顺序重排(“排序”);如何解决那些在计算机中能使用一种被称为“图”的数学结构来建模的基本问题(可用于对道路网建模,针对任务间的依赖建模,以及金融套利交易建模);如何解决关于字符串(例如DNA结构)的问题;密码学的基本原理;数据压缩的基本原理;甚至那些至今还没有人得出如何借助计算机在一段合理的时间内求解的问题。读者将理解什么是计算机算法,如何描述它们,以及如何来评估它们。这些计算机算法将提供:利用计算机搜索信息的简单方式;解决各种排序问题的方法;利用有向无环图和短路径法来解决基本问题的方法(可用于建模公路网络,任务间的依赖以及金融关系;解决字符串(例如DNA结构)问题的方法;密码学背后的基本原理;数据压缩的基础知识;以及甚至一些没有人能够理解如何在计算机上用相当长的时间来解决的问题。Algorithms Unlocked出版者的话译者序前言第1章什么是算法以及为什么应该关注算法11.1正确性21.2资源利用31.3针对非计算机专业人士的计算机算法51.4针对计算机专业人士的计算机算法61.5拓展阅读7第2章如何描述和评估计算机算法92.1如何描述计算机算法92.2如何描述运行时间162.3循环不变式192.4递归212.5拓展阅读23第3章排序算法和查找算法243.1二分查找263.2选择排序313.3插入排序343.4归并排序383.5快速排序473.6小结553.7拓展阅读57第4章排序算法的下界和如何超越下界584.1基于排序的规则584.2基于比较排序的下界594.3使用计数排序超越下界604.4基数排序664.5拓展阅读68第5章有向无环图695.1有向无环图725.2拓扑排序725.3如何表示有向图765.4拓扑排序的运行时间775.5PERT图表中的关键路径785.6有向无环图中的最短路径825.7拓展阅读86第6章最短路径876.1Dijkstra算法896.2BellmanFord算法986.3FloydWarshall算法1036.4拓展阅读112第7章字符串算法1147.1最长公共子序列1147.2字符串转换1207.3字符串匹配1287.4拓展阅读135第8章密码学基础1368.1简单替代密码1378.2对称密钥加密1388.3公钥加密1428.4RSA加密系统1448.5混合加密系统1538.6计算随机数1538.7拓展阅读154第9章数据压缩1569.1哈夫曼编码1589.2传真机1659.3LZW压缩1669.4拓展阅读176第10章难?问题17710.1棕卡车问题17710.2P、NP和NP完全类18110.3可判定问题和归约18310.4主问题18610.5NP完全问题例析18810.6总体策略20310.7前景20610.8不可判定问题20810.9小结21010.10拓展阅读211参考文献212索引214让我们从我经常被问到的一个问题开始:“什么是算法?”一个常见的回答是,“完成一个任务所需的一系列步骤。”在日常生活中经常会碰到算法。刷牙的时候会执行一个算法:打开牙膏盖,拿出牙刷,持续执行挤牙膏操作直到足量的牙膏涂在你的牙刷上,盖上牙膏盖,将牙刷放到嘴的1/4处,上下移动牙刷N秒,等等。如果你必须乘通勤车去工作,乘通勤车也是一个算法。诸如此类。但是本书是关于运行在计算机上的算法的,或者更概括地来讲,是关于运行在计算设备上的算法的。正如你日常所运行的算法会影响你每天的生活一样,在计算机上运行的算法也会影响你的生活。你使用过GPS来寻找旅行路线吗?它运行一种称为“最短路径”的算法以寻求路线。你在网上购买商品吗?那么你会使用(应该正在使用)一个运行加密算法的安全网站。当你在网上购买商品时,它们是由一个私营快递公司发货的吗?它使用算法将包裹分配给不同的卡车,然后确定每个司机发件的顺序。算法运行在各种设备上―在你的笔记本上,服务器上,智能手机上,嵌人式系统上〔例如你的车中,你的微波炉中,或者气候控制系统中)―无处不在!

类似文章

发表回复

您的电子邮箱地址不会被公开。