可能与不可能的边界：PNP问题趣史 - (EPUB全文下载)

文件大小：2.58 mb。
文件格式：epub 格式。
书籍内容：

版权信息
书名：可能与不可能的边界：P/NP问题趣史
作者：Lance Fortnow
译者：杨帆
ISBN：978-7-115-33566-1
本书由北京图灵文化发展有限公司发行数字版。版权所有，侵权必究。
您购买的图灵电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
目录
版权声明
献词
前言
致谢
第1章　金券
1.1　划分的难题
1.2　手
1.3　P/NP问题
1.4　找到金券
1.5　漫漫长途
1.6　划分难题的解
第2章　美妙的世界
2.1　厄巴纳算法
2.2　计算机1，癌症0
2.3　棒球比赛
2.4　奥卡姆剃刀
2.5　创造力的自动化
2.6　终极侦探
2.7　美妙世界的阴暗面
2.8　回到现实
第3章　P和NP
3.1　敌友国
3.2　六度理论
3.3　牵线搭桥
3.4　团问题
3.5　“递棍儿”
3.6　刷房子
3.7 分组
3.8　P和NP
3.9　敌友国之外
3.10　Icosian游戏的一个解
第4章　NP中最难的问题
4.1　第一个NP完全问题
4.2　21个问题
4.3　起个好名字有那么重要吗
4.4　超越卡普的工作
4.5　漏网之鱼
第5章　P和NP诞生前的历史
5.1　西方
5.2　东方
5.3　哥德尔的信
5.4　火星人法则
第6章　处理困难的问题
6.1　蛮力
6.2　启发式方法
6.3　搜索小规模的解
6.4　近似计算方法
6.5　解决一个不同的问题
6.6　接受现实
6.7　总结
第7章　证明P≠NP
7.1　骗子悖论
7.2　电路
7.3　证明P≠NP时常犯的错误
7.4　现状
第8章　秘密
8.1　经典密码学简史
8.2　现代密码学
8.3　P=NP下的密码学
8.4　零知识数独
8.5　玩游戏
8.6　在云上进行加密计算
8.7　创造随机性
8.8　持续的挑战
第9章　量子
9.1　量子录像机
9.2　量子密码学
9.3　量子隐形传输
9.4　量子的未来
第10章　未来
10.1　并行计算
10.2　处理大数据
10.3　一切事物的网络化
10.4　应对科技变革
10.5　关于P/NP问题的结束语
章节注释和文献
人名表
05. 轻松撰写功能规格书 - 第一部分： 为什么要写？
　　　
版权声明
Original edition, entitled The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow, ISBN: 978-0-691-15649-1 , published by Princeton University Press.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without permission in writing from Princeton University Press.
Simplified Chinese translation copyright ©2013 by Posts & Telecom Press.
本书简体中文版由普林斯顿大学出版社授权人民邮电出版社独家出版。未经出版者许可，不得以任何方式复制本书内容。
仅限于中华人民共和国境内（中国香港、澳门特别行政区和台湾地区除外）销售发行。
版权所有，侵权必究。
献词
献给Marcy、Annie 和Molly，愿他们知道我是做什么的，以及为何而做。
英国著名科学家臭臭教授发明了一个机器，不用打开糖果包装，它就能立刻告诉你里面有没有金券。机器的机械手臂出手如电，一抓一个准儿，不会漏掉哪怕藏有一点点金子的任何东西。目前看来，它解决了所有的问题。
——罗尔德·达尔，《查理和巧克力工厂》
前言
近半数的美国人都拥有智能手机。智能手机也是计算机，其计算能力比几十年前的超级计算机还要强。计算机将世界上的信息呈现在我们眼前，也帮我们梳理信息。计算机让人们可以彼此交流，无论什么身份，地处何方。计算机能执行数量巨大的运算，从模拟宇宙事件到调度复杂的航线。计算机可以识别人的声音、面孔和动作。计算机可以获悉人们的喜好，并据此推荐图书、音乐和电影。在不远的将来，借助计算机技术，无人驾驶的汽车将随处可见。这么说，计算机简直无所不能。
真是这样吗？在这本书里，我们将探讨许多计算问题，其中一部分可能永远都无法用简单的计算得到答案。试着解答它们是计算机科学，乃至整个数学和科学领域最重要的挑战。人们给这些问题起了一个有些奇怪的名字：P/NP问题。
P/NP是克雷数学研究所公布的7个千禧年数学难题之一，该研究所为求解这道难题设立了百万美元的奖金。不过，P/NP问题的意义远不止于此。
P指的是用计算机能很快求解的问题，NP指的是我们想找到最优解的问题。如果P=NP，那么我们将很容易找到任意给定问题的解。P=NP意味着我们所了解的社会将发生巨变，医学、科学、娱乐和人类社会一切任务的自动化程度都将立即发生质的飞跃。
相反，如果P≠NP，那么总会有部分问题无法迅速地被解决。那也没有关系，因为我们可以根据具体情况研发出某些技术来解决这些问题。P≠NP意味着不可能用自动化的方法解决所有问题。然而，知道哪些工具不好用也有助于人们找到更好用的工具。
2008年8月，《ACM通讯》的主编莫舍·瓦迪约我写一篇关于P/NP问题的文章。ACM（美国计算机协会）是一个为计算机研 ............

书籍插图：

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。