幫助中心 | 我的帳號 | 關於我們

計算複雜性理論(教育部高等學校電腦類專業教學指導委員會推薦教材)/電腦科學理論系列叢書

  • 作者:傅育熙|責編:龍啟銘
  • 出版社:清華大學
  • ISBN:9787302627982
  • 出版日期:2023/05/01
  • 裝幀:平裝
  • 頁數:379
人民幣:RMB 79 元      售價:
放入購物車
加入收藏夾

內容大鋼
    本書是一本介紹計算複雜性理論的基礎教材,內容包括時間複雜性、空間複雜性、NP-理論、多項式譜系、電路複雜性、隨機計算及去隨機、計數複雜性、交互證明系統、PCP定理、近似計算與不可近似性。
    本書的主要讀者群是高年級本科生、碩士生、博士生,以及希望了解(更多)計算複雜性理論的教師和科研工作者。本書可用於以下課程:(1)面向高年級本科生、研究生的「計算複雜性理論導論」課程,內容涵蓋前3章;(2)面向研究生的「計算複雜性理論高等議題」課程,內容涵蓋后3章;(3)面向高年級本科生、研究生的「演算法理論」課程,涵蓋第4章、第6章中有關隨機演算法和去隨機、近似演算法和不可近似性的內容;(4)面向高年級本科生、研究生的「計算理論」課程,以第1章的內容為核心,並根據學分多少和授課對象不同做適當補充。

作者介紹
傅育熙|責編:龍啟銘
    傅育熙,1992年獲英國曼徹斯特大學電腦博士學位,1994年起任職于上海交通大學電腦系,現為上海交通大學特聘教授,研究領域為理論電腦科學,是國家傑出青年基金獲得者、上海市優秀學科帶頭人、Mathematical Structures in Computer Science的編委。曾任上海交通大學電腦系主任(2000-2009)、軟體學院院長(2001-2013)、國務院學位委員會第六屆學科評議組成員(2010-2014)、上海市電腦學會理事長(2015-2018)、教育部電腦類專業教學指導委員會副主任(2013-2022)。講授的「計算複雜性理論」課程獲得「2019年度高校電腦專業優秀教師獎勵計劃」。

目錄
第1章  計算理論
  1.1  圖靈機
  1.2  時間可構造性
  1.3  通用圖靈機
  1.4  對角線方法
  1.5  丘奇-圖靈論題
  1.6  加速定理
  1.7  時間複雜性類
  1.8  非確定圖靈機
  1.9  命題邏輯
  1.10  謂詞邏輯
  1.11  計算的邏輯刻畫
  1.12  時間譜系定理
  1.13  間隙定理
  1.14  神諭圖靈機
  1.15  歸約
  1.16  空間複雜性類
  1.17  對數空間類
  1.18  多項式空間類
  1.19  對數空間的補封閉性
  1.20  TIME(T(n))=SPACE(T(n))嗎
  第1章練習
第2章  難解性
  2.1  可驗證性
  2.2  NP-完全性
  2.3  庫克-萊文定理
  2.4  拉德納定理
  2.5  貝克-吉爾-索羅維定理
  2.6  多項式譜系
  2.7  譜系的邏輯刻畫
  2.8  譜系的交替機刻畫
  2.9  無限譜系假設
  2.10  第二層中的完全問題
  第2章練習
第3章  電路複雜性
  3.1  電路譜系定理
  3.2  一致電路
  3.3  P/poly
  3.4  並行計算
  3.5  P-完全性
  3.6  哈斯塔德對換引理
  第3章練習
第4章  隨機計算與去隨機
  4.1  隨機演算法
  4.2  通用哈希函數族
  4.3  概率圖靈機
  4.4  BPP與ZPP
  4.5  PP與#P
  4.6  積和式計算
  4.7  戶田定理

  4.8  隨機遊走
  4.9  蒙特卡羅方法
    4.9.1  近似採樣
    4.9.2  馬爾可夫鏈蒙特卡羅方法
    4.9.3  均混時間
  4.10  擴張圖與去隨機
    4.10.1  線性代數相關知識
    4.10.2  圖的譜
    4.10.3  擴張圖
    4.10.4  擴張圖上的隨機遊走
  4.11  擴張圖的構造
    4.11.1  擴張圖的構造運算元
    4.11.2  固定大小擴張圖構造
    4.11.3  顯式擴張圖族
  4.12  萊因戈爾德定理
  第4章練習
第5章  交互證明系統
  5.1  私幣交互證明
  5.2  公幣交互證明
  5.3  IP=PSPACE
  5.4  兩類系統的等價性
  5.5  多證明者交互證明系統
    5.5.1  定義
    5.5.2  NEXP的多證明者協議
  5.6  多線性性測試演算法
  5.7  並行重複定理
    5.7.1  統計距離、詹森不等式、相對熵
    5.7.2  隨機變數的近似嵌入
    5.7.3  博弈的近似生成
    5.7.4  證明的最後一步
  5.8  單回合雙證明者交互系統
  第5章練習
第6章  近似計算與不可近似性
  6.1  近似演算法
  6.2  不可近似性
  6.3  局部可驗證性與不可近似性
  6.4  錯誤放大
  6.5  證明思想
  6.6  線性增強
  6.7  線性歸減
  6.8  PCP定理的證明
  6.9  布爾函數的分析技術
    6.9.1  傅里葉展開式
    6.9.2  卷積定理
    6.9.3  BLR-測試
    6.9.4  長碼
  6.10  哈斯塔德3-比特PCP-定理
    6.10.1  哈斯塔德驗證器
    6.10.2  哈斯塔德演算法的可靠性
  6.11  閾值定理

  第6章練習
參考文獻
定理索引
圖索引
術語索引

  • 商品搜索:
  • | 高級搜索
首頁新手上路客服中心關於我們聯絡我們Top↑
Copyrightc 1999~2008 美商天龍國際圖書股份有限公司 臺灣分公司. All rights reserved.
營業地址:臺北市中正區重慶南路一段103號1F 105號1F-2F
讀者服務部電話:02-2381-2033 02-2381-1863 時間:週一-週五 10:00-17:00
 服務信箱:bookuu@69book.com 客戶、意見信箱:cs@69book.com
ICP證:浙B2-20060032