判定樹理論導(dǎo)引

定　價：￥6.20

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

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

內(nèi)容簡介

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

作者簡介

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

圖書目錄

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