簡體書 » 可能與不可能的邊界P/NP問題趣史

可能與不可能的邊界P/NP問題趣史

定價：~~234~~ 元

NT $ 204

作者：(美)福特諾
出版社：人民郵電出版社
出版日期：2014-01-01
語言：簡體中文
ISBN10：7115335664
ISBN13：9787115335661
裝訂：146頁 / 普通級 / 1-1

內容簡介

P/NP 問題是計算機科學乃至整個數學領域最重要的開放問題。本書從非技術角度介紹了什麼是P/NP 問題、它豐富的歷史，以及對於人機交互乃至更多問題的數學意義。

在這本趣味十足的書中，作者首先追溯了P/NP 問題是如何產生的，然后給出了這個問題的許多實例，涉及經濟學、物理學和生物學在內的多個學科。接下來探討了涵蓋P/NP 難題中所有難度等級的問題，從尋找游玩迪士尼樂園所有景點的最短路線，到地圖填色問題，再到找出Facebook 上互為好友的一群人。

本書深入探尋了計算能夠做到什麼、無法做到什麼，描繪了嘗試解決P/NP問題的益處和其中難以預想的挑戰。本書讀來引人入勝，適合所有對計算和數學感興趣的讀者。

第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章　證明
7.1 　騙子悖論
7.2 　電路
7.3 　證明時常犯的錯誤
7.4 　現狀
第8章　秘密
8.1 　經典密碼學簡史
8.2 　現代密碼學
8.3 　下的密碼學
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問題的結束語
章節注釋和文獻
人名表

看更多