推理的迷宫悖论谜题及知识的脆弱性,完整pdf电子书,百度网盘下载庞德斯通

2017年7月14日08:28:23 发表评论

推理的迷宫悖论谜题及知识的脆弱性

完整pdf扫描电子书,百度网盘下载庞德斯通

一、作者简介:点击查看更多图书:

威廉·庞德斯通(William Poundstone),曾在麻省理工学院学习物理学,定居洛杉矶。他为世界各地的报刊、杂志以及美国电视台撰稿。迄今为止,庞德斯通已出版10余部著作,其中《循环的宇宙》、《推理的迷宫》获普利策奖提名。

推理的迷宫悖论谜题及知识的脆弱性,完整pdf电子书,百度网盘下载庞德斯通

二、目录:

前 言

第一部分

第 1 章悖论

缸中之脑 // 004

梦境和邪恶的天才 // 005

不确定性 // 009

有什么东西是确定的吗? // 010

演绎与归纳 // 015

证实理论 // 017

悖论 // 018

科学是外部世界的一幅地图 // 023

悖论与可满足性 // 024

普遍性问题 // 026

第 2 章归纳:亨佩尔的乌鸦

证实 // 030

物质与反物质 // 031

绝对证实和递增证实 // 033

反例 // 034

新奇的理论 // 036

换质位命题 // 038

绝不要说绝不 // 041

意识流 // 042

无穷小的证实 // 043

“99 英尺高的人”悖论 // 045

乌鸦与总体证据 // 048

第 3 章范畴:绿蓝—蓝绿悖论

绿蓝色的绿宝石 // 052

七拼八凑的范畴 // 054

反事实语句 // 056

旋转的调色盘 // 057

颠倒的光谱 // 059

魔鬼理论 16 号 // 060

任何事证实任何事 // 061

奥卡姆剃刀 // 062

判决日 // 065

可投射性 // 066

夸克是绿蓝色的吗? // 067

第 4 章不可知者:夜间倍增

反实在论 // 070

一团乱麻的物理学 // 072

魔鬼与倍增 // 074

变种 // 076

时间是在 5 分钟以前开始的吗? // 077

反实在论的危险 // 078

黑洞探测器 // 080

他人心灵 // 083

快乐和痛苦的夜间倍增 // 085

实在是唯一的吗? // 090

第二部分

插曲:华生大夫的谜题

智力测试 // 095

气、水、电 // 095

公司的流言 // 096

墓地谜题 // 098

一个测量员的困境 // 099

答案 // 100

第 5 章演绎:谷堆悖论

忒修斯之船 // 107

连锁推理 // 108

复杂性 // 110

说假话的和说真话的 // 112

谁在说谎? // 112

可满足性 // 117

猪排问题 // 118

电梯问题 // 121

科学与谜题 // 124

第 6 章观念:意外绞刑悖论

突然袭击的考试与隐藏的鸡蛋 // 126

霍利斯悖论 // 127

一个简化的悖论 // 128

时间旅行悖论 // 130

什么是知道? // 131

科学与三重理由 // 133

布里丹语句 // 135

盖梯尔反例 // 136

第四个条件 // 139

囚徒和盖梯尔 // 140

第 7 章不可能性:期望悖论

第 22 条军规 // 144

这样的事有可能吗? // 145

可能世界 // 148

有多少个“可能世界” // 150

悖论和可能世界 // 151

序言悖论 // 152

合理的观念必须是相容的吗? // 154

波洛克毒气室 // 157

第 8 章无限:汤姆森灯

圆周率机 // 162

芝诺悖论 // 163

造一盏汤姆森灯 // 165

几何级数 // 167

马尔萨斯灾难 // 169

奥尔贝斯悖论 // 171

反对“多” // 173

奥尔贝斯悖论的解决 // 174

特里斯特拉姆·香迪悖论 // 177

第 9 章NP完全:彭睢迷宫

nP完全 // 183

迷宫算法 // 185

右手法则 // 188

特雷莫算法 // 190

无限的迷宫 // 192

奥尔算法 // 193

迷宫的nP完全性 // 194

迷宫先知 // 198

P和nP // 200

最难的问题 // 202

经验目录 // 204

和宇宙一样大的计算机 // 206

第三部分

第 10 章意义:孪生地球

罗杰·培根 // 221

假破译 // 222

意义与胡话 // 225

洞穴寓言 // 228

电子洞穴 // 230

二进制洞穴 // 232

一颗“缸中之脑”是否可能发现真相? // 233

孪生地球 // 235

孪生地球的化学 // 236

亚特兰蒂斯图书馆 // 239

爱伦·坡的“iiiii……”密码 // 241

暴力法 // 245

检验破译结果 // 247

意义何在? // 248

第 11 章心灵:塞尔的中文屋

思维机器 // 250

功能主义悖论 // 252

图灵检验 // 253

中文屋 // 255

大脑和牛奶 // 257

回应 // 259

笨法学中文 // 260

杰基尔博士和海德先生 // 261

系统观点回应 // 262

说明书中的一页 // 263

与爱因斯坦的大脑对话 // 267

第 12 章全知者:纽康悖论

全知者悖论 // 270

囚徒困境 // 272

纽康悖论 // 273

反应 // 274

玻璃箱子 // 276

诺齐克关于选择的两条原则 // 279

这一定是骗局吗? // 282

两种预测 // 284

混沌 // 285

自由意志与决定论 // 288

预测和无穷倒退 // 289

公元 3000 年的纽康悖论 // 293

参考文献 // 297

三、书评:

1,计算复杂性

这是描述一种算法需要多少“时间”的度量。(也有空间复杂性,但因为它们能相互转换,所以通常我们就说时间复杂性。对于大小为 n 的输入,我们用含 n 的简化式子来表达。(所谓简化式子,就是忽略系数、常数,仅保留最“大”的那部分)

比如找出 n 个数中最大的一个,很简单,就是把第一个数和第二个比,其中大的那个再和第三个比,依次类推,总共要比 n-1 次,我们记作 O(n) (对于 n 可以是很大很大的情况下,-1可以忽略不计了)。

再比如从小到大排好的 n 个数,从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找,最好情况是第一个就是 x,最坏情况是比较了 n 次直最后一个,因此最坏情况下的计算复杂度也是 O(n)。还有一种方法:先取中间那个数和 x 比较,如偏大则在前一半数中找,如偏小则在后一半数中找,每次都是取中间的那个数进行比较,则最坏情况是 lg(n)/lg2。忽略系数lg2,算法复杂度是O(lgn)。

2,计算复杂性的排序:

根据含 n 的表达式随 n 增大的增长速度,可以将它们排序:1 < lg(n) < n < nlg(n) < n^2 < … < n^k (k是常数)< … < 2^n。最后这个 2 的 n 次方就是级数增长了,读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数,例如 2*n^3+9*n^2 可以被简化为 n^3?用集合什么的都能解释,我忘了精确的说法了。如果你还记得微积分的话就想像一下对 (2*n^3+9*n^2)/(n^3) 求导,结果是0,没区别,对不?

2,P 问题:对一个问题,凡是能找到计算复杂度可以表示为多项式的确定算法,这个问题就属于 P (polynomial) 问题。

3,NP 问题:

NP 中的 N 是指非确定的(non-deterministic)算法,这是这样一种算法:(1)猜一个答案。(2)验证这个答案是否正确。(3)只要存在某次验证,答案是正确的,则该算法得解。

NP (non-deterministic polynomial)问题就是指,用这样的非确定的算法,验证步骤(2)有多项式时间的计算复杂度的算法。

4,问题的归约:

这……我该用什么术语来解释呢?集合?太难说清了……如果你还记得函数的映射的话就比较容易想象了。

大致就是这样:找从问题1的所有输入到问题2的所有输入的对应,如果相应的,也能有问题2的所有输出到问题1的所有输出的对应,则若我们找到了问题2的解法,就能通过输入、输出的对应关系,得到问题1的解法。由此我们说问题1可归约到问题2。

5,NP-Hard:

有这样一种问题,所有 NP 问题都可以归约到这种问题,我们称之为 NP-hard 问题。

6,NP完全问题 (NP-Complete):

如果一个问题既是 NP 问题又是 NP-Hard 问题,则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题,此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。

从直觉上说,P<=NP<=NP-Complete<=NP-Hard,问题的难度递增。但目前只能证明 P 属于 NP,究竟 P=NP 还是 P 真包含于 NP 还未知。

weinxin
购买请添加微信
扫一扫添加:yiyingqk001
avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: