第1章 基礎(chǔ)知識

計算機(jī)科學(xué)與技術(shù)學(xué)科強(qiáng)調(diào)4個方面的專業(yè)能力：計算思維能力，算法設(shè)計與分析能力，程序設(shè)計與實(shí)現(xiàn)能力，計算機(jī)系統(tǒng)的認(rèn)知、分析、設(shè)計和運(yùn)用能力。這也是計算機(jī)科學(xué)與技術(shù)學(xué)科同其他學(xué)科的重要區(qū)別。相關(guān)的理論是計算機(jī)科學(xué)與技術(shù)學(xué)科的基礎(chǔ)。理論方面的知識是計算機(jī)的真正靈魂。理論是從計算機(jī)應(yīng)用中抽象出來的，目的在于使用抽象出來的理論去更好地指導(dǎo)實(shí)踐。

在本科階段的學(xué)習(xí)過程中，學(xué)生以觀察、描述、比較、分類、推斷、應(yīng)用、創(chuàng)造性思維等科學(xué)思維過程為主，強(qiáng)調(diào)自學(xué)的能力在于培養(yǎng)；研究生階段，需要對學(xué)生進(jìn)一步進(jìn)行抽象思維、邏輯思維、創(chuàng)造性思維能力的培養(yǎng)。本科生與研究生的根本區(qū)別，在于研究生需要寬厚、堅實(shí)的理論基礎(chǔ)。

建立物理符號系統(tǒng)并對其實(shí)施等價變換，是計算機(jī)科學(xué)與技術(shù)學(xué)科進(jìn)行問題描述和求解的重要手段。“可行性”所要求的“形式化”及其“離散特征”使得數(shù)學(xué)成為重要的工具，而計算模型無論是從方法還是從工具等方面，都表現(xiàn)出它在計算機(jī)科學(xué)中的重要作用。

計算機(jī)科學(xué)與技術(shù)學(xué)科要求具有形式化描述和抽象思維能力，要求掌握邏輯思維方法。這種能力就是計算思維能力或計算機(jī)思維能力[1]。

計算機(jī)科學(xué)與技術(shù)學(xué)科系統(tǒng)地研究信息描述和變換算法，重點(diǎn)包括信息描述和變換算法的理論、分析、效率、實(shí)現(xiàn)與運(yùn)用。學(xué)科的根本問題在于：什么能被（有效地）自動化？學(xué)科的重要內(nèi)容之一是研究計算領(lǐng)域中的一些普遍規(guī)律，描述算法的基本概念與模型。

計算思維能力的培養(yǎng)主要是通過基礎(chǔ)理論系列課程實(shí)現(xiàn)的，該系列由數(shù)學(xué)和抽象度較高的理論課程組成，包括數(shù)學(xué)分析、集合和圖論、近世代數(shù)、數(shù)學(xué)建模、計算理論等。它們構(gòu)成了對學(xué)生計算思維能力培養(yǎng)的一個階梯訓(xùn)練系統(tǒng)，如圖1.1所示^^chapter2.xhtml-[1]$$[1]。

在計算思維階梯訓(xùn)練系統(tǒng)中，連續(xù)數(shù)學(xué)、離散數(shù)學(xué)、計算模型3部分內(nèi)容按階段分開。3個階段對應(yīng)于計算機(jī)學(xué)科的學(xué)生在本科和研究生學(xué)習(xí)期間的思維方式和能力變化的3個步驟，使得學(xué)生的計算思維能力不斷提高。

在中學(xué)階段所學(xué)的數(shù)學(xué)，研究的是具體的、靜止對象的計算。到了數(shù)學(xué)分析階段，通過連續(xù)變量和函數(shù)，將運(yùn)動帶入了問題考慮的范圍中，到離散數(shù)學(xué)和近世代數(shù)階段，開始考慮基本運(yùn)算系統(tǒng)，該系統(tǒng)更加抽象，更具一般性，所考慮的計算對象具有更明顯的抽象和離散的特征。到形式語言與自動機(jī)理論階段，所考慮的運(yùn)算對象是更高級別上抽象出來的形式化特征，而運(yùn)算也呈現(xiàn)出模型化的特征。計算從孤立的、單一的計算演變?yōu)橐话恪⑿问交挠嬎悖话恪⑿问交挠嬎悖怯嬎銠C(jī)科學(xué)所要研究的計算。

考慮的計算對象不同，所需要的思維方式和能力就有所不同，正是通過系列課程的學(xué)習(xí)，在不斷升華的過程中，逐步培養(yǎng)出學(xué)生的抽象思維能力和邏輯思維方法，同時，創(chuàng)新意識的建立和創(chuàng)新能力的培養(yǎng)也在學(xué)習(xí)過程中不斷進(jìn)行。

計算理論是研究使用計算機(jī)解決計算問題的數(shù)學(xué)理論。它有 3 個核心領(lǐng)域：形式語言與自動機(jī)理論、可計算性理論和計算的復(fù)雜性理論。可計算性理論的中心問題是，建立計算的數(shù)學(xué)模型，進(jìn)而研究哪些是可計算的，哪些是不可計算的。計算的復(fù)雜性理論研究算法的時間復(fù)雜性和空間復(fù)雜性。在可計算性理論中，將問題分成可計算的和不可計算的；在復(fù)雜性理論中，目標(biāo)是把可計算的問題分成簡單的和困難的。

形式語言與自動機(jī)理論論述計算的數(shù)學(xué)模型的定義與性質(zhì)，這些模型在計算機(jī)科學(xué)的若干應(yīng)用領(lǐng)域中起著重要作用，其應(yīng)用范圍已被擴(kuò)展到生物工程、自動控制系統(tǒng)、圖像處理與模式識別等許多領(lǐng)域。

形式語言與自動機(jī)理論是學(xué)習(xí)計算理論的良好起點(diǎn)，不僅能提高感知能力，同時也能提高思維的敏捷性，使得考慮問題仔細(xì)、嚴(yán)謹(jǐn)、周密、有理有據(jù)；由具體形象思維逐漸向抽象思維過渡，從而促進(jìn)邏輯思維和創(chuàng)造力的發(fā)展；使得邏輯思維過程清晰化、條理化、整體化，有利于培養(yǎng)計算表達(dá)能力，提高推理、判斷、分析問題和解決問題的能力。

計算理論并不神秘，也不令人厭煩，而是容易理解的，甚至是有趣的。計算理論中包括許多迷人而重要的思想，要體會并感悟思想的閃光，并且體會大師們當(dāng)初發(fā)現(xiàn)這些思想而獲得的極大樂趣。

計算機(jī)學(xué)科的方法論有 3 個過程：抽象、理論和設(shè)計及實(shí)現(xiàn)。最根本的問題是：問題如何進(jìn)行描述？哪些部分能夠被自動化？如何進(jìn)行自動化描述？

問題的計算機(jī)求解建立在高度抽象的基礎(chǔ)上，問題的符號表示及處理過程的機(jī)械化、嚴(yán)格化等固有特性決定了數(shù)學(xué)是計算機(jī)科學(xué)與技術(shù)學(xué)科的重要基礎(chǔ)之一。數(shù)學(xué)及其形式化描述以及嚴(yán)密的表達(dá)和計算，是計算機(jī)科學(xué)與技術(shù)學(xué)科的重要工具。建立物理符號系統(tǒng)并對其實(shí)施變換，是計算機(jī)科學(xué)與技術(shù)學(xué)科進(jìn)行問題描述和求解的重要手段。學(xué)科所要求的計算機(jī)問題求解的“可行性”限定了從問題抽象開始到根據(jù)適當(dāng)理論的指導(dǎo)進(jìn)行實(shí)現(xiàn)的科學(xué)世界過程。

形式語言與自動機(jī)理論包括 3 方面的內(nèi)容：形式語言理論、自動機(jī)理論和形式語言與自動機(jī)等價性理論。本書主要討論自動機(jī)理論和形式語言與自動機(jī)等價性理論。

本書內(nèi)容屬于理論計算機(jī)科學(xué)的理論范疇，所需的數(shù)學(xué)基礎(chǔ)知識較多。本章對形式語言和有限自動機(jī)理論中所需的數(shù)學(xué)基礎(chǔ)知識做扼要的介紹，內(nèi)容包括集合及其運(yùn)算、關(guān)系、證明和證明的方法以及圖與樹的概念；對形式語言和自動機(jī)理論中的基本知識做簡要介紹。