算法之美(精)

作者:(美)布莱恩·克里斯汀//汤姆·格里菲思
译者:万慧//胡小锐

ISBN：9787508686882

单价：59.0

出版年月：2018-05-01 00:00:00.0

出版社：中信出版社

币制：CNY

图书分类：社会科学

分类号： F0-39

语种：CHI

页数：358

装帧：精装

开本：32开

展开▼

评分：5.0

(本馆/总：0/1人荐购)

序言
1 最优停止理论：如何准确选择停止观望的时机？
秘书问题
37%从何而来？
情场上的出手时机
掌握候选对象的完整信息
卖房子的时机
最优停车位置
见好就收的时机
随时准备停止
2 探索与利用：要最新的还是要最好的？
什么是探索与利用？
如何利用剩余时间？
赢留输变
基廷斯指数
遗憾与乐观
网上“土匪”
试验中的临床实验
不安分的世界
孜孜不倦地探索
3 排序：建立秩序
排序狂潮
排序带来的苦恼
大O符号：衡量最坏情况的标准
平方时间：冒泡排序与插入排序
打破平方时间的魔咒：分治算法
超越比较法：比对数更好的算法
排下序是搜索的准备工作
排序与体育
发牢骚的权利：噪声与健壮性
杀戮排序：啄食顺序与优势等级
以竞争取代争斗
4 缓存：忘了它吧
分级存储器体系
缓存清理与未卜先知
重整图书馆藏书
本地需求
家庭生活中的“高速缓存”
归档与堆存
遗忘曲线
经验暴政
5 时间调度理论：要事先行
安排时间是一门科学
处理时限
把事情做好
找出问题所在
优先级反转和优先约束
减速带
放弃所有：抢占和不确定性
抢占并不是随意的：关联转换
颠簸状态
中断合并
6 贝叶斯法则：预测未来
贝叶斯牧师的倒推理
拉普拉斯定理
贝叶斯法则与先验信念
哥白尼原则
贝叶斯与哥白尼
真实世界先验……
……以及他们的预测规则
小数据与思维
我们的预测体现出我们自己
机械复制时代的先验
7 过度拟合：不要想太多
反对复杂性案例
数据崇拜
过度拟合无处不在
检测过度拟合：交叉验证
如何应对过度拟合：惩罚复杂性
启发法
人类进化中的过度拟合
何时应该想的更少？
8 松弛：顺其自然
最优化的难度
定义的难度
放松吧
无数灰色地带：持续的松弛
只是一张超速罚单：拉格朗日松弛算法
学会松弛
9 随机性：何时应用随机？
抽样
随机算法
抽样的优势
三部分的权衡
山、谷和陷阱
局部最大值之外
模拟退火算法
随机性、进化和创造力
10 网络：我们如何联系？
分组交换
信息确认
指数退避算法：宽恕的算法
流量控制和拥塞避免
反馈语：语言学的流量控制
缓存膨胀：这就是延时，傻瓜
迟到不如永远不到
11 博弈论：别人的想法
达到均衡
占优策略，无论好坏
公地悲剧
机制设计：改变游戏
机制设计的演变
信息瀑布：泡沫的悲剧理性
你自己的计算
结语计算善意

展开▼

导语

你以为布莱恩·克里斯汀、汤姆·格里菲思著万慧、胡小锐译的《算法之美(精)》讲的是算法吗？其实它说的是人生。“算法”并不只适用于计算机，同样适合我们的生活与工作，租房、收拾衣柜、选择餐厅、时间管理……无不能用算法解决。最优停止法则、时间调度法则、贝叶斯法则等等，看似艰深，其实连找停车位都能用得上！两位作者一位是学术派、一位是畅销书作者，两人合著此书，严谨而不失幽默，故事诙谐有趣，方法蕴含其中。

展开▼

内容简介

我们所有人的生活都受到有限空间和有限时间的限制，因此常常面临一系列难以抉择的问题。在一天或者一生的时光里，哪些事是我们应该做的，哪些是应该放弃的？我们对杂乱无序的容忍底线是什么？新的活动与熟悉并喜爱的活动之间如何平衡，才能取得令人愉快的结果？这些看似是人类特有的难题，其实不然，因为计算机也面临同样的问题，计算机科学家几十年来也一直在努力解决这些问题，而他们找到的解决方案可以给我们很多启发。通过丰富的跨学科研究，作者指出，计算机算法也可以用来解答人类面临的这些问题。布莱恩·克里斯汀、汤姆·格里菲思著万慧、胡小锐译的《算法之美(精)》告诉我们如何更有效地利用直觉、什么时候应该把选择权交给命运、无所适从的时候应该如何做出选择，以及如何有效地与他人保持联系。从找配偶到找停车位，从组织管理个人邮箱的收件箱到理解人类记忆的作用原理，这本书把计算机科学的智慧转化为人类生活的策略，引导我们做出明智的选择。

展开▼

作者简介

布莱恩·克里斯汀，《华尔街日报》畅销书《*有人性的人》作者，该书入选《纽约时报》编辑推荐书目，被《纽约客》杂志评为年度好书。他的多篇作品先后刊登在《纽约客》《大西洋》《连线》《华尔街日报》《卫报》《巴黎评论》及《认知科学》等杂志上，被翻译成11种语言。

展开▼

前言

假设你想租房子，正在旧金山四处寻找房源。旧金山可能是整个美国最难找房子的城市了。由于技术产业的蓬勃发展，再加上城市区划法律严格限制建造新住房，旧金山的房租已经与纽约不相上下，甚至比纽约还高。房源清单列出来几分钟，房子就会被人们一抢而空。通常情况下，只有第一个把定金支票塞到房东手里的人，才能拿到房子的钥匙。理论上讲，认真调查、仔细斟酌是理性消费者的一大特征，但是旧金山的残酷市场并没有为他们留有权衡考虑的机会。在购物中心或者网上购物时，人们可以反复权衡再做出决定，但是将要入住旧金山的租客没有这个特权，他们必须迅速做出决定：要么舍弃其他所有可能的选择，就选定当前正在看的这套房子，要么掉头就走，再也不要回头。简单起见，我们姑且假设，你唯一关心的就是尽最大可能增加挑中最理想公寓的机会。你的目标是把 “看过的好房子被人挑走”与“还有好房子没来得及看”这两种遗憾的发生概率降至最低。于是，你立刻发现自己陷入了两难境地：如果没有衡量的标准，如何判断一套公寓是否是最合适的呢？如果你不先看一些公寓（这些公寓将被你放弃），又如何确定衡量标准？你收集的信息越多，越能在最合适的机会出现时准确地认出它，但是你已经与最合适的机会失之交臂的可能性也越高。那么，到底该怎么办？如果收集信息的行为会危及结果，那么怎样才能在掌握足够多信息的基础上做出明智决定呢？这个令人极其为难的情境近乎于一个悖论。在被问及此类问题时，大多数人凭直觉给出的回答可能大致如此：这需要在继续挑选与立刻下手之间达成某种平衡。也就是说，你必须先看足够多的房子，确定一个标准，然后接受符合这个标准的房子。事实上，平衡概念正是解决这类问题的关键。但是，大多数人根本无法确定这个平衡点在哪里。好消息是，这个平衡点已经被找出来了。答案就是37%。如果你希望选中最合适公寓的可能性达到最大，那么在看前37%的房子时不要做出任何决定（如果你准备花一个月的时间挑选房子，那么在前11 天不要做出决定）。这段时间你是在为制定标准做准备，因此看房子时把银行卡放在家里吧。但是，过了这个时间点之后，你就要做好随时签约的准备（包括准备好定金等），一旦你对某套房子的满意程度超过之前看过的所有房子，就立刻下手。在继续挑选与立刻下手之间做出的这种妥协，并不仅仅是一种直觉，而是已经得到证明的最优解。我们知道这个答案，是因为找房子问题属于数学上被称作“最优停止”（optimal stopping）的一类问题。37% 法则明确了解决这些问题的一系列简单步骤（计算机科学称之为“算法”）。事实证明，找房子仅仅是最优停止问题在日常生活中的表现形式之一。在面临一连串选择时如何做出决定的难题，经常会改头换面，以不同的形式出现在我们的生活当中。在驶入停车位之前，需要绕整个停车场多少圈？在商业风险中何时套现脱身？在买房子或者停车时，何时是结束观望、做出决定的最佳时机？在约会这个更加令人头疼的问题上，人们也经常要面对这样的难题。最优停止理论是一夫一妻婚姻制度催生的科学。每天，人们都要面临最优停止问题的困扰（当然，诗人更愿意追逐的话题肯定是求婚带来的烦恼，而不是停车时的两难境地），有时至会因此而痛苦不堪。不过，我们大可不必如此，因为这类问题至少可以通过数学方法来解决。借助并不繁复的算法，我们不仅可以解决找房子的问题，生活中遭遇的所有最优停止问题都可以被妥善处理。从本质上讲，我们身边经常出现因为租房子、停车、求婚而感到苦恼的人，这些人其实就是在自寻烦恼。他们需要的不是治疗师，而是一种算法。治疗师告诉他们要在冲动与多虑之间找到一个正确的、舒服的平衡点。算法告诉他们这个平衡点就是37%。本书将探讨人类事务算法设计这个概念，以帮助人们更好地处理日常生活中遇到的难题。将计算机科学的研究方法应用于日常生活，可以在多个层面上产生深远的影响。首先，它可以提供切实有效的建议，帮助我们解决具体问题。例如，最优停止理论可以告诉我们何时应该小心观察，何时应该果断行动；探索 – 利用平衡理论教会我们如何在尝试新事物与因循守旧之间找到平衡点；排序理论可以帮我们判断出是否需要以及如何整理办公室；缓存理论可以帮助我们合理地填充橱柜；日程安排理论则可以提供合理安排时间的高招。其次，计算机科学还为我们理解这些领域的深层次运行规则提供了一套语汇。卡尔·萨根指出：“与其说科学是大量知识的汇总, 不如说它是一种思考方式。”即使生活中的某些情况非常复杂，我们无法进行严格的数值分析，找不到任何现成的答案，我们也可以考虑这些问题的简单化表现形式，从而得出某些直觉和概念，帮助我们理解其中的关键环节并取得进展。从更广泛的意义上看，借助计算机科学，我们可以

展开▼

后记

任何受制于空间和时间限制的动态系统都是与一组基础的、不可避免的核心问题相背离的。这些问题本质上是计算性的，这使计算机不仅成为我们的工具，也成为我们的伙伴。其中我们可以得出三个简单的智慧道理。首先，在某些案例中，计算机科学家和数学家已经确定了很好的算法方法，这些算法可以简单地转移到人类问题上。37％的规则，是最近最少使用算法处理满溢缓存的标准，以及作为探索指南的置信上限都是这方面的例子。其次，即使你没有得到你想要的结果，但知道你正在使用最优算也是一种解脱。37％规则在63％的可能里会失败。用最近最少使用算法的标准来维护你的缓存并不保证你总能找到你想要的东西。事实上，也不会有特别的洞察力。用置信上限的方法来探索或利用权衡并不意味着你不会遗憾后悔，只是那些遗憾会随着你的生活慢慢积累起来。即使是最好的策略有时也会产生不好的结果，这就是计算机科学家要小心区分“过程”和“结果”的原因。“如果你遵循了最好的流程，那么你就已经尽了最大的努力，如果结果不顺心，你也不应该责备自己。” 结果会成为头条新闻(的确，是它们使我们生活的世界变成现在的样子)，所以我们容易对结果念念不忘。但是过程是我们所能控制的。正如伯特兰·罗素所言：“看来我们必须考虑到客观公正的概率。” 客观正确的行为可能是最幸运的。我将把这定义为最明智的行为。“我们可以希望变得幸运，但我们应该努力做到明智。”我们将其称之为计算克制。最后，我们可以在容许和不容许直接解决方案的问题之间划出一条清晰的界限。如果你被困在一个棘手的问题中，请记住，运用启发法、近似值和随机的策略可以帮助你找到可行的解决方案。在我们对计算机科学家的采访中，曾反复出现的一个主题是：有时 “足够好”真的已经足够好了。更重要的是，意识到复杂性可以帮助我们选择问题：如果我们能够控制我们面对的情况，我们应该选择那些可以处理的问题。但我们选择的不只是我们给自己安排的问题。我们也会选择我们给彼此安排的问题，无论是我们设计城市的方式还是我们问问题的方式。这就创造了横跨计算机科学和伦理学的惊人桥梁——以我们称之为计算性善意原则的形式。在给本书安排采访时，我们中的两个人观察了一个悖论。平均而言，我们的面试者更有可能前来的预约时间是，比如“太平洋标准时间下周二下午1～2点 ”，而不是“在这一周任何方便的时间”。一开始，这似乎是荒谬的，就像那个著名的研究，平均而言，人们会捐更多的钱来拯救一只企鹅的生命，而不是8 000只企鹅，或者人们报告称，更担心死于恐怖主义行为，而不是其他原因(也包括恐怖主义)。在采访问题中，人们似乎更喜欢受到约束的问题，即使这些约束要求严格，而不是完全开放的。对于他们来说，适应我们的偏好和约束似乎比根据他们自己的方式来计算出更好的选择要困难得多。计算机科学家们会在这里点头，并指出“验证”和“搜索”之间的复杂性差距，这就像你能听出一首听过的好歌曲和在现场写一首好歌曲之间的差距一样大。尽管听起来很奇怪，但计算机科学隐含的原理之一便是，计算并不是好事：任何一种好的算法的指令都是把思考的劳动最小化。当我们与他人互动时，我们会向他们展示计算问题(不只是明确的要求和需求，而是隐含的挑战)，例如在解释我们的意图、我们的信念和我们的喜好时。因此，对这些问题的计算性理解可以揭示人类相互作用的本质。我们可以通过构造问题来对其他人进行“计算性善意”，从而使深层的计算问题更容易。这很重要，因为许多问题，尤其是社会问题，就像我们所看到的那样，本质上是难以解决的。还有一些其他例子，是在计算上更仁慈的设计。例如，考虑下餐厅座位政策问题。一些餐厅有一个“ 开放式座位”的政策，等待的顾客在那里徘徊，直到一张桌子被空出来，而第一个坐下来的人就会在这张桌子上用餐。其他人会记下你的名字，让你在酒吧喝一杯，当桌子准备好时再通知你。这些对稀缺共享资源管理的方法反映了计算机科学在“旋转”和“阻塞 ”之间的区别。当处理线程请求资源而无法获取时，计算机可以允许线程“自旋”——继续对资源进行永久检查，“它准备好了吗?”循环，或者它可以“阻塞”：停止那个线程，转换其他对象，然后在资源空闲的时候再回来。对于计算机科学家来说，这是一个实际的权衡：权衡在自旋中丢失的时间和在上下文切换中失去的时间。但在餐馆中，并非所有被交易的资源都是他们自己的。“旋转”的方式更快地填补了空桌子，但同时被损坏的中央处理器就是他们顾客的思想，被困在乏味且耗时间的警觉中。作为一个类似示例，考虑一下公交站所带来的计算问题。如果有一个实时显示器提示说，下一辆车“ 10分钟后到达”，那么你就可以决定是否继续等待，而不是将公共汽车还没来的事实作为推论证据，一刻

展开▼

用户登录

注册成功!