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

前言

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

內(nèi)容概要

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

書(shū)籍目錄

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

章節(jié)摘錄

插圖：

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

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

---