可計(jì)算性與計(jì)算復(fù)雜性導(dǎo)引

前言

計(jì)算機(jī)科學(xué)技術(shù)日新月異，新東西層出不窮、舊東西迅速被淘汰。但是，作為一門科學(xué)，它有其自身的基礎(chǔ)理論。這些思想精華長久地、甚至永恒地放射著光芒。這些理論在應(yīng)用開發(fā)中好像是"無用的"，但實(shí)際上，對于每一位從事計(jì)算機(jī)科學(xué)技術(shù)的研究和開發(fā)的人來說，它們都是不可缺少的，就像能量守恒之類的物理定律對于每一位自然科學(xué)工作者和工程技術(shù)人員那樣。北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系開設(shè)了"理論計(jì)算機(jī)科學(xué)基礎(chǔ)"這門課，就是希望能把這樣一些最基本的知識介紹給學(xué)生。本書是在這門課的講稿的基礎(chǔ)上加工而成的。    本書的內(nèi)容包括三部分：可計(jì)算性、形式語言與自動機(jī)、計(jì)算復(fù)雜性。這三個領(lǐng)域（更不用說整個理論計(jì)算機(jī)科學(xué)）的內(nèi)容極其豐富并且在不斷地發(fā)展。作為本科生一個學(xué)期的課程只能選擇其中最基本的部分，使學(xué)生在這些方面有一個大的理論框架。本書主要取材于參考文獻(xiàn)[1]～[4]。書中部分章節(jié)涉及到數(shù)理邏輯和圖論中的一些問題，不熟悉這些內(nèi)容的讀者可查閱參考文獻(xiàn)[6]、[7]。書末附有中英文名詞索引和記號，并給出定義這些名詞和記號的章節(jié)。    本書的出版得到北京大學(xué)出版社的熱情支持，筆者在此表示衷心的感謝。在本書的出版和寫作過程中得到董士海教授、袁崇義教授、王捍貧博士和黃雄的各種形式的幫助，對他們表示感謝。最后，筆者要特別感謝許卓群教授，作為主管教學(xué)工作的系領(lǐng)導(dǎo)，許卓群教授從這門課的開設(shè)到本書的出版給予了一貫的積極支持和指導(dǎo)。    張立昂    1996年春于北大燕北園

內(nèi)容概要

本書是學(xué)習(xí)理論計(jì)算機(jī)科學(xué)基礎(chǔ)的教材和參考書，內(nèi)容包括三部分： 可計(jì)算性、形式語言與自動機(jī)、計(jì)算復(fù)雜性。主要介紹幾種計(jì)算模型及它們的等價性，函數(shù)、謂詞和語言的可計(jì)算性等基本概念，形式語言及其對應(yīng)的自動機(jī)模型，時間和空間復(fù)雜性，NP完全性等。    本書可作為計(jì)算機(jī)專業(yè)本科生和研究生的教材，也可作為從事計(jì)算機(jī)科學(xué)技術(shù)的研究和開發(fā)人員的參考書，還可作為對理論計(jì)算機(jī)科學(xué)感興趣的讀者的入門教材。

書籍目錄

第一章 程序設(shè)計(jì)語言×和可計(jì)算函數(shù)  1.1 預(yù)備知識   1.2 Church-Turing論題  1.3 程序設(shè)計(jì)語言×  1.4 可計(jì)算函數(shù)  1.5 宏指令   習(xí)題第二章 原始遞歸函數(shù)  2.1 原始遞歸函數(shù)  2.2 原始遞歸謂詞  2.3 迭代運(yùn)算、有界量詞和極小化  2.4 配對函數(shù)和Godel數(shù)  2.5 原始遞歸運(yùn)算  2.6 Ackermann函數(shù)  2.7 字函數(shù)的可計(jì)算性  習(xí)題第三章 通用程序   3.1 程序的代碼  3.2 停機(jī)問題  3.3 通用程序  3.4 遞歸可枚舉集  習(xí)題第四章 Turing 機(jī)  4.1 Turing 機(jī)的基本模型  4.2 Turing 機(jī)的各種形式  4.3 Turing 機(jī)與可計(jì)算性  4.4 Turing 機(jī)接受的語言  4.5 非確定型Turing 機(jī)  習(xí)題第五章 過程與文法  5.1 半Thue過程   5.2 用半Thue過程模擬Turing 機(jī)  5.3 文法  5.4 再論遞歸可枚舉集  5.5 部分遞歸函數(shù)  5.6 再論Church-Turing論題  習(xí)題第六章 不可判定的問題  6.1 判定問題  6.2 Turing 機(jī)的停機(jī)問題  6.3 字問題和Post對應(yīng)問題  6.4 有關(guān)文法的不可判定問題  6.5 一階邏輯中的判定問題  習(xí)題第七章 正則語言  7.1 Chomsky譜系  7.2 有窮自動機(jī)  7.3 有窮自動機(jī)與正則文法的等價性  7.4 正則表達(dá)式  7.5 非正則語言   習(xí)題第八章 上下文無關(guān)語言第九章 時間復(fù)雜性與空間復(fù)雜性第十章 NP完全性第十一章 NP類的外面 第十二章 P類的里面第十三章 隨機(jī)算法與隨機(jī)復(fù)雜性類附錄參考文獻(xiàn)

章節(jié)摘錄

插圖：

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    可計(jì)算性與計(jì)算復(fù)雜性導(dǎo)引 PDF格式下載

---