科羅拉多大學(xué)計算理論導(dǎo)引課程介紹了自動機(jī)理論、可計算性理論和復(fù)雜性理論的基礎(chǔ)，研究了自動機(jī)和形式語言之間的關(guān)系，闡述了哪些問題可以通過計算手段解決(可判定性與不可判定性)，同時探討了與問題的計算復(fù)雜性相關(guān)的概念。以下是這門課的考點梳理。

一、計算理論導(dǎo)引課程考點

1、常規(guī)語言：確定性有限狀態(tài)機(jī)；非確定有限狀態(tài)機(jī)；正則表達(dá)式；常規(guī)語言性質(zhì)；非常規(guī)語言(抽取引理)。

2、上下文無關(guān)語言：上下文無關(guān)文法；下推自動機(jī)；上下文無關(guān)語言的屬性；CFL抽取引理。

3、可計算性理論：圖靈機(jī)及其變體；丘奇-圖靈論題；可判定語言；不可判定性；使用問題歸約證明給定問題的不可判定性；賴斯定理；著名的不可判定問題，如郵政通信問題(pCp)，平鋪問題，多棧和雙計數(shù)器機(jī)器的停機(jī)問題。

4、復(fù)雜性理論：時間和空間復(fù)雜性；復(fù)雜性類p和Np，以及Np-完全性；著名的Np完全問題；復(fù)雜性類pSpACE和pSpACE-完備性；復(fù)雜度類L和NL，以及NL-完全性。

5、專題：一元二階邏輯和自動機(jī)；單詞和樹的正則變換；描述性復(fù)雜性；隨機(jī)計算；量子計算；交互式證明和復(fù)雜性類Ip；pCp定理和逼近的困難(計算復(fù)雜性)；時間和混合自動機(jī)；概率自動機(jī)。

二、計算理論導(dǎo)引課程目標(biāo)

計算理論導(dǎo)引課程的目標(biāo)是介紹計算理論，涵蓋以下三個理論計算機(jī)科學(xué)分支：

1、自動機(jī)理論

(1)通過形式語言形式化問題的概念。

(2)使用稱為自動機(jī)的“抽象計算設(shè)備”來形式化計算的概念。

(3)理解問題類別或形式語言的層次結(jié)構(gòu)。

(4)理解自動機(jī)類別的層次結(jié)構(gòu)(有限自動機(jī)、下推自動機(jī)和圖靈機(jī))。

2、可計算性理論

(1)理解丘奇-圖靈論題。

(2)理解不可判定性的概念，即當(dāng)一個問題不能用計算機(jī)解決時。

(3)如何用問題歸約的概念來表示不可判定性。

3、復(fù)雜性理論

(1)復(fù)雜性分類：如何根據(jù)時間和空間需求對可判定的問題進(jìn)行分類。

(2)復(fù)雜性類p和Np，以及難處理性(Np-完全性)。

(3)如何證明Np完全性？

(4)空間復(fù)雜性：NL-完全性和pS apce-完全性。

希望我們梳理的科羅拉多大學(xué)計算理論導(dǎo)引課程考點以及課程目標(biāo)對你的學(xué)習(xí)有幫助。你可以參考上述信息進(jìn)行學(xué)習(xí)規(guī)劃。如果你在學(xué)習(xí)過程中遇到問題，隨時可以聯(lián)系我們喲。