判定樹理論導引

定　價：￥6.20

作　者：	堵丁柱著
出版社：	湖南教育出版社
叢編項：	現(xiàn)代數(shù)學叢書
標　簽：	圖論

ISBN：	9787535526007	出版時間：	1998-01-01	包裝：	平裝
開本：	19cm	頁數(shù)：	103頁	字數(shù)：

內(nèi)容簡介

　　本書介紹計算復雜性理論的一個重要部分：判定權理論。全部內(nèi)容圍繞該理論中的一個重要且未解決的問題：Karp猜想。全書分九講。前四講介紹判定權的一般理論及Karp猜想的提出背景。五至八講介紹研究Karp猜想的方法及已存在的成果。最后一講介紹隨機判定樹以及其中的Yar：Karp猜想。作者試圖通過對這一具體問題的詳盡剖析，向讀者展示計算復雜性理論的思想方法和意義，并將讀者引入研究的前沿。本書是為數(shù)學以及理論計算機科學專業(yè)的研究生和高年級的大學生所寫的通俗讀物，對從事這方面工作的教師與科技工作者也有參考價值。

作者簡介

　　堵丁柱，黑龍江齊齊哈爾人，1948年5月生。1977年考入齊齊哈爾經(jīng)工學院，1978年后隨導師越民義分入應用數(shù)學所。1982年獲碩士學位并赴美攻讀博士。1985年于加里福尼亞大學圣巴巴拉分校獲數(shù)學博士。先后工作于伯克利數(shù)學科學研究所、麻省理工學院以及普林斯頓大學?，F(xiàn)為中國科學院應用數(shù)學所研究員，同時為美國明尼蘇達大學計算機科學系正教授。自1980年從事應用數(shù)學研究以來，在國內(nèi)外發(fā)表論文百余篇，并著有《可行方向方法的收劍理論》和《組合群試的理論與應用》（與黃光明合著）?，F(xiàn)任《組合優(yōu)化雜志》（英文）主編和《組合優(yōu)化從書》（英文）主編。

圖書目錄

第一講　布爾函數(shù)與判定樹
1.1　布爾函數(shù)
1.2　圖與圖性質(zhì)
1.3　判定樹
練習題
第二講　下界與上界
2.1　隱子與子句
2.2　界
2.3　弱對稱函數(shù)
練習題
第三講　詭函數(shù)
3.1　代數(shù)判別法
3.2　弱對稱詭函數(shù)
3.3　一個反例
練習題
第四講　圖性質(zhì)
4.1　幾個例子
4.2　Karp猜想
4.3　團與染色
練習題
第五講　拓撲方法
5.1　單純復形與歐拉示性數(shù)
5.2　可塌性
5.3　拓撲判別法
練習題
第六講不動點的妙用
6.1　不動點定理
6.2　單純映象
6.3　二分圖的性質(zhì)
練習題
第七講　置換群的應用
7.1　自同構群的不動點
7.2　Wreath積
7.3　單調(diào)圖性質(zhì)
練習題
第八講　六階圖
8.1　驗證Karp猜想
8.2　對有向圖的注記
8.3　啟迪與思考
練習題
第九講　隨機判定樹
9.1　定義
9.2　下界
9.3　Yar-Karp猜想
練習題
后記
參考文獻