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

定　價(jià)：￥39.00

作　者：	（美）Lance Fortnow 著，楊帆譯
出版社：	人民郵電出版社
叢編項(xiàng)：
標(biāo)　簽：	計(jì)算機(jī)理論、基礎(chǔ)知識(shí) 計(jì)算機(jī)與互聯(lián)網(wǎng)

購買這本書可以去

ISBN：	9787115335661	出版時(shí)間：	2014-01-01	包裝：	平裝
開本：	16開	頁數(shù)：	160	字?jǐn)?shù)：

內(nèi)容簡介

　　P/NP 問題是計(jì)算機(jī)科學(xué)乃至整個(gè)數(shù)學(xué)領(lǐng)域最重要的開放問題?！犊赡芘c不可能的邊界：P/NP問題趣史》從非技術(shù)角度介紹了什么是P/NP 問題、它豐富的歷史，以及對(duì)于人機(jī)交互乃至更多問題的數(shù)學(xué)意義。在這本趣味十足的書中，作者首先追溯了P/NP 問題是如何產(chǎn)生的，然后給出了這個(gè)問題的許多實(shí)例，涉及經(jīng)濟(jì)學(xué)、物理學(xué)和生物學(xué)在內(nèi)的多個(gè)學(xué)科。接下來探討了涵蓋P/NP 難題中所有難度等級(jí)的問題，從尋找游玩迪士尼樂園所有景點(diǎn)的最短路線，到地圖填色問題，再到找出Facebook 上互為好友的一群人。本書深入探尋了計(jì)算能夠做到什么、無法做到什么，描繪了嘗試解決P/NP問題的益處和其中難以預(yù)想的挑戰(zhàn)?！犊赡芘c不可能的邊界：P/NP問題趣史》讀來引人入勝，適合所有對(duì)計(jì)算和數(shù)學(xué)感興趣的讀者。

作者簡介

　　Lance Fortnow，世界級(jí)計(jì)算機(jī)科學(xué)家，佐治亞理工學(xué)院計(jì)算機(jī)科學(xué)系教授、系主任，在計(jì)算復(fù)雜性和交互式證明系統(tǒng)領(lǐng)域取得了一系列重要研究成果，為計(jì)算機(jī)界所熟知。Fortnow早年師從著名的理論計(jì)算機(jī)科學(xué)家Michael Sipser，獲麻省理工學(xué)院應(yīng)用數(shù)學(xué)博士學(xué)位。畢業(yè)后曾在西北大學(xué)、芝加哥大學(xué)擔(dān)任教授，之前還做過NEC研究院高級(jí)研究員。他是知名博客Computational Complexity的創(chuàng)辦者，經(jīng)常與他人共同執(zhí)筆撰寫計(jì)算復(fù)雜性方面的文章。

圖書目錄

第1章　金券　　
維露卡的父親索爾特先生是個(gè)富商，他決定買光他能找到的巧克力。這還不夠，就算有堆積如山的巧克力，要從中找到小小的金券也很困難。
1.1 　劃分的難題　　
1.2 　手　　
1.3 　P/NP問題　　
1.4 　找到金券　　
1.5 　漫漫長途　　
1.6 　劃分難題的解　　
第2章　美妙的世界　　
“不完全準(zhǔn)確，”醫(yī)生說，“沒錯(cuò)，厄巴納算法幫人們戰(zhàn)勝了癌魔，治愈了艾滋病和糖尿病?？墒?，我們還不知道如何應(yīng)對(duì)普通感冒?！?br />2.1 　厄巴納算法　　
2.2 　計(jì)算機(jī)1，癌癥0　　
2.3 　棒球比賽　　
2.4 　奧卡姆剃刀　　
2.5 　創(chuàng)造力的自動(dòng)化　　
2.6 　終極偵探　　
2.7 　美妙世界的陰暗面　　
2.8 　回到現(xiàn)實(shí)　　
第3章　P和NP　　
1852年，南非數(shù)學(xué)家弗朗西斯？格思里在為英國各郡的地圖填色時(shí)，猜想是否只用四種顏色，就足夠讓所有地圖上每兩個(gè)接壤的地區(qū)有不同的顏色。
3.1 　敵友國　　
3.2 　六度理論　　
3.3 　牽線搭橋　　
3.4 　團(tuán)問題　　
3.5 “遞棍兒”　　
3.6 　刷房子　　
3.7 　分組　　
3.8 　P和NP　　
3.9 　敵友國之外　　
3.10 　Icosian游戲的一個(gè)解　　
第4章　NP中最難的問題　　
高德納對(duì)這個(gè)民選結(jié)果不太滿意，但也沒有覺得它差到讓人活不下去的地步。他本人特別想要找一個(gè)英文詞，既能捕捉“困難的搜索問題”這個(gè)直觀的意象，又要瑯瑯上口，便于向大眾普及。
4.1 　
第一個(gè)NP完全問題　　
4.2 　21個(gè)問題　　
4.3 　起個(gè)好名字有那么重要嗎　　
4.4 　超越卡普的工作　　
4.5 　漏網(wǎng)之魚　　
第5章　P和NP誕生前的歷史　　
圖靈在1936年就指出，圖靈機(jī)并不是什么都能計(jì)算。最著名的例子是停機(jī)問題，即沒有計(jì)算機(jī)能通過查看一段代碼就知道自己是會(huì)永遠(yuǎn)執(zhí)行下去還是會(huì)最終停止。
5.1 　西方　　
5.2 　東方　　
5.3 　哥德爾的信　　
5.4 　火星人法則　　
第6章　處理困難的問題　　
有時(shí)候一個(gè)問題天生排斥任何可能解決它的方法，對(duì)此你能做的只有放棄，然后去干點(diǎn)別的。
6.1 　蠻力　　
6.2 　啟發(fā)式方法　　
6.3 　搜索小規(guī)模的解　　
6.4 　近似計(jì)算方法　　
6.5 　解決一個(gè)不同的問題　　
6.6 　接受現(xiàn)實(shí)　　
6.7 　總結(jié)　　
第7章　證明　　
2010年8月6日，惠普實(shí)驗(yàn)室的科學(xué)家維納里？德奧拉利卡向22位頂尖的理論計(jì)算機(jī)科學(xué)家發(fā)送了他寫的論文，題目簡潔有力：“ “。
7.1 　騙子悖論　　
7.2 　電路　　
7.3 　證明時(shí)常犯的錯(cuò)誤　　
7.4 　現(xiàn)狀　　
第8章　秘密　　
每個(gè)人都有秘密，從密碼到電子郵件，我們都有不想讓別人看到的東西。意味著某些NP問題擁有不為人知的秘密，無法很快找到它的答案。
8.1 　經(jīng)典密碼學(xué)簡史　　
8.2 　現(xiàn)代密碼學(xué)　　
8.3 　下的密碼學(xué)　　
8.4 　零知識(shí)數(shù)獨(dú)　　
8.5 　玩游戲　　
8.6 　在云上進(jìn)行加密計(jì)算　　
8.7 　創(chuàng)造隨機(jī)性　　
8.8 　持續(xù)的挑戰(zhàn)　　
第9章　量子　　
即使有極小部分的量子和外界環(huán)境發(fā)生輕微作用而喪失了糾纏態(tài)，從另一頭出現(xiàn)的我就很可能被毀形，甚至變成一團(tuán)死肉。
9.1 　量子錄像機(jī)　　
9.2 　量子密碼學(xué)　　
9.3 　量子隱形傳輸　　
9.4 　量子的未來　　
第10章　未來　　
我本人對(duì)P/NP問題得到解決的前景持悲觀態(tài)度：我認(rèn)為，而且此生都看不到它的證明。
10.1 　并行計(jì)算　　
10.2 　處理大數(shù)據(jù)　　
10.3 　一切事物的網(wǎng)絡(luò)化　　
10.4 　應(yīng)對(duì)科技變革　　
10.5 　關(guān)于P/NP問題的結(jié)束語　　
章節(jié)注釋和文獻(xiàn)　　
人名表