課程內(nèi)容：

本課程為回答以下問題提供了初步方法：有哪些方法可以幫助理解復(fù)雜的系統(tǒng)或程序？如何確保程序按照我們的意圖運(yùn)行？計算機(jī)如何識別文本？如果有兩種方法可以解決同一個問題，我們?nèi)绾螌ζ溥M(jìn)行比較？如何衡量其中一種方法更快地解決問題？我們?nèi)绾卫斫庥嬎銠C(jī)原則上能做什么，是否存在計算機(jī)無法解決的問題？

課程大綱：

課程的前半部分（10講）涉及特定字符串和字符串集合的表達(dá)，在此課程將介紹計算機(jī)處理這些字符串的方法。此外，課程還將涉及有限狀態(tài)自動機(jī)、正則表達(dá)式和（正則）語法。

課程的后半部分（10講）介紹了復(fù)雜性、正確性和可計算性等主題。共有四大主題：WHILE編程語言；漸近復(fù)雜性；部分和全部程序的正確性；可計算性。

學(xué)習(xí)成果：

成功完成本課程后，學(xué)生將能夠：

1、使用各種機(jī)制描述形式語言。  

2、定義語言類別并演示這些類別之間的轉(zhuǎn)換。

3、說明語言類別的關(guān)鍵屬性，并確定這些屬性何時成立。

4、定義計算模型，并使用這些模型演示什么可以計算，什么不可以計算。