定義概念題目：
第三章：
1. 圖靈機：是一種精確的通用計算機模型，能模擬實際計算機的所有計算行為，它的核心是轉移函式δ，它說明了機器如何從乙個格局走到下乙個格局。
對於圖靈機，δ的形式如下：q×γ→q×γ,圖靈機是乙個7元組（q，∑，γ，δ，q 0,qaccept,qreject）.其中q，∑，γ都是有窮集合，並且1）q是狀態集；2）∑是輸入字母表，不包括特殊空白符號凵，3）γ是帶字母表，其中凵∈г，∑∈г4）δ
2. 格局：圖靈機的計算過程中，當前狀態，當前內容和讀寫頭當前位置組合在一起。例如：1011q701111：當前狀態q7，當前讀寫頭位置在第二個0上。
定義3.2 如果乙個語言能被某乙個圖靈機識別，則稱該語言是圖靈可識別的（遞迴可列舉語言）
定義3.2 如果乙個語言能被某乙個圖靈機判定，則稱該語言是圖靈可判定的簡稱可判定的（遞迴語言）
3.圖靈機的變形：多帶圖靈機、非確定型圖靈機、列舉器。
每個4.列舉器：他是圖靈機的一種變形，是帶有印表機的圖靈機，圖靈機把印表機當作輸出裝置，從而可以列印串，每當圖靈機想在列印序列中增加乙個串時，就把此串送到印表機。
乙個語言是圖靈可識別的，當且僅當有列舉器列舉它。
5.圖靈機的術語：形式化描述，實現描述，高水平描述。
第四章：
1.可判定的語言有：（adfa、anfa、arex、edfa、eqdfa 是正則語言）、（acfg、ecfg 是上下無關語言）每個上下文無關語言都是可判定的。
2.不可判定的語言有:：eqcfg、atm 、停機問題、halttm 、etm 、regulartm 、eqtm 、 elba 、allcfg 、pcp
atm =｛｜m是tm，ω是串，m接受ω｝是不可判定的。
證明：假設證atm 是可判定的，下面將由之匯出矛盾。設h是atm 的判定器。
令m是乙個tm，ω是乙個串。在輸入上，如果m接受ω，則h就是停機且接受ω；如果m不接受ω，則h也會停機，但拒絕ω。換句話說，h是乙個tm使得：
h（）=，現在來構造乙個圖靈機d，它以h作為子程式。當m被輸入它自己的描述時，tm d就呼叫h，以了解m做什麼。一旦的到這個訊息，d就反著做，即：
如果m接受它就拒絕；如果m不接受，它就接受。下面是d的描述：d=「對於輸入，其中m是乙個tm。
1）在輸入>上執行h。2）輸入h輸出的相反結論，即如果h接受就拒絕；如果h拒絕就接受。」得出：
d ()=，當以d的描述作為輸入來執行d自身是得到：d()=不論d做什麼，它都是被迫相反地做，這顯然是乙個矛盾。
注：存在不能被任何圖靈機識別的語言。乙個語言是可判定的當且僅當它既是圖靈可識別的也是補圖靈可是識別的。不是圖靈可是識別的。(要證明)
3.語言類的關係：從大到小為（圖靈可識別的、可判定的、上下無關的、正則的）
第五章：
1.接受計算歷史：設m是乙個圖靈機，ω是乙個串，m在ω上的乙個接受計算歷史是乙個格局序列c1，c2, ···cι,其中c1是m在ω上的起始格局，cι是m的乙個接受格局，且每個ci都是ci-1的合法結果，級符合m的歸則。
m在ω上的乙個拒絕計算歷史可類似定義，只是cι應是乙個拒絕格局。它是證明atm可歸約到某些語言的重要技術。
2.線性界定自動機（lba）：是一種受到限制的圖靈機，它不允許其讀寫頭離開包含輸入的帶區域。
如果此機器試圖將它的讀寫頭移除輸入的兩個端點，則讀寫頭就保持在原地不動。這與普通的圖靈機的讀寫頭不會離開帶子的左端的方式是一樣的。
3.可計算函式：函式f：
∑*→∑*是乙個可計算函式，如果有某個圖靈機m，使得在每個輸入ω上m停機，且此時只有f (ω)出現在帶上。可計算函式可以是算術運算的描述之間的變換。
4.對映可歸約性的形式定義：語言a是對映可歸約到語言b的，如果存在可計算函式f:：∑*→∑*使得對每個ω，ω∈a〈=〉f(ω)∈b,記做a≤mb。稱函式f為a到b的歸約。
5.定理：如果a≤mb且b是可判定的，則a也是可判定的。
證明：設m是b的判定器，f是從a到b的可歸約。a的判定器n的描述如下：
n=「對於輸入ω：1）計算f(ω)。2）在f(ω) ∈b，輸出m的輸出。
顯然，如果ω∈a，則f(ω) ∈b，因為f到b的歸約。因此，只要ω∈a，則m接受f(ω)故n執行正如所求。
如果a≤mb且a是不可判定的，則b也是不可判定的。
如果a≤mb且b是圖靈可識別的，則a也是可識別的。如果a≤mb且a不是圖靈可識別的，b也不是圖靈可識別的eqtm既不是圖靈可識別的，也不是補圖靈可識別的。
第七章：
1.時間複雜度：令m是乙個所有輸入上都停機的確定型圖靈機。
m執行時間或者時間複雜度是乙個函式f:n→n，其中n是非負整數集合，f(n)是m在所有長度為n的輸入上執行是所經過的最大步數。若f(n)是m的執行時間則稱m在時間f(n)內執行，m是f(n)時間圖靈機。
通常使用n表示輸入的長度。
2.設t(n)是乙個函式，t(n) ≥n，則每乙個t(n)時間的多帶圖靈機都和某乙個o（t2(n)）時間的單帶圖靈機等價。
設t(n)是乙個函式，t(n) ≥n，則每乙個t(n)時間的非確定型單帶機都和某乙個2o（t(n)）時間的確定型單帶圖靈機等價。
單帶與多帶相差乙個平方，多帶之間相差t2(n).
3.多項式驗證機：
語言a的驗證機是乙個演算法v，這裡a＝｛ω｜對某個字串c，v接受（ω,c）｝因為只根據ω的長度來度量驗證機的時間，所以多現實時間驗證機在ω的長度的多項式時間內執行。若語言a有乙個多項式時間驗證機，則稱它為多項式可驗證的。
4.多項式時間可歸約性：
語言a稱為多項式時間對映可歸約到語言b,或簡稱為多項式可歸約到b，記為a≤pb，若在多項式時間可計算函式f: ∑*→∑* ,對於每乙個ω，有ω∈a <=> f(ω)b函式f稱為a到b的多項式時間歸約。
5.np完全性的定義：
如果語言b滿足下面的兩個條件，就成為np完全的，1）b屬於np並且2）np中的每個a都是多項式時間可歸約到b。若上述的b是np完全的且b∈p，則p=np。若上述的b是np完全的，且b≤pc ，c屬於np則c是np完全的
第八章：
1. 空間複雜度：令m是—個在所有輸入上都停機的確定型圖靈機。
m的空間複雜度是乙個函式f ：n→n，其中f (n)是m在任何長為n的輸入上掃瞄帶方格的最大數。若m的空間複雜度為，則稱m在空間內執行。
2. 薩維奇定理：對於任何函式f：
n→r+，其中f (n)≥n，。3. 令f ：
n→r+是乙個函式。空間複雜性類space（）和nspace（）定義如下：space() =
nspace() =
4. pspace類的非確定型版本npspace，可以類似地用nspace類來定義。然而，任何多項式的平方仍是多項式，根據薩維奇定理，則npspace＝pspace。
5. pspace完全性
語言b是pspace完全的。若它滿足下面兩個條件：1）b屬於pspace。
2）pspace中的每乙個語言a多項式時間可歸約到b。若b只滿足條件2），則稱它為pspace難的。
6.為什麼pspace完全性時，用的是多項式時間歸約，而不是多項式空間歸約？若在空間複雜度為f(n)內判定，那麼其時間複雜是: 薩維奇定理裡有。
答：完全問題是主要的。因為他們是複雜性類中最困難的樣例。
完全問題是最難的，因為該類中的問題很容易歸約到它。如果找到一種簡便的方法求解完全問題，就很容易求解該類中的其他所有問題。為了使這種邏輯能夠成立，相對於該類中典型問題的複雜性，歸約過程就必須是容易的。
如歸約過程本身就很難算，當為乙個複雜性類定義完全問題是，歸約的模型必須比用來定義類本身的模型更加受限。
7. 對數空間轉換器：a是有一條唯讀輸入帶、一條只寫輸出帶和一條讀寫工作帶的圖靈機。
工作帶可以包含個符號。對數空間轉換器m計算乙個函式f：，其中f(w)是把w放在m的輸入帶上啟動m執行，到m停機時輸出帶上存放的字串。
稱a為對數空間可計算函式。如果語言a通過對數空間可計算函式f對映可歸約到語言b，則稱a對數空間可歸約到b，記為alb。
8.p類是確定型單帶圖靈機在多項式時間內可判定的語言類。換言之,p=time（nk）。
np類是具有多項式時間驗證機的語言類即np=ntime（nk）。
pspace是在確定型圖靈機上、在多項式空間內可判定的語言類。換言之，。
npspace是在非確定型圖靈機上在多項式空間內可判定的語言類。
l是確定型圖靈機在對數空間內可判定的語言類。換言之 l＝space()
nl是非確定型圖靈機在對數空間內可判定的語言類，換言之，nl＝nspace()
conl是語言類中的補語言構成的語言類nl=conl。
lnlconlpnppspace=npspaceexptime
屬於p類的有：path，relprime，每乙個上下無關語言都是p的成員，
屬於np類的有：cliquenp，subset―sum，
np完全的有：sat，3sat,clique,vertex―cover,hampath,uhampath,subset―sum,
pspace完全的有：tqbf，formula―game，gg
若有乙個nl完全語言屬於l則l=nl。path是nl完全的。nlp
sat∈p當且僅當p=np。若a≤pb且b∈p則a∈p 。
浙江10版定額部分章節說明及規則 現澆砼及工程
4 滿堂基礎及地下室底板已包括集水井模板杯殼，不再另行計算 設計為帶形基礎的單位工程，如僅樓 電 梯間 廚廁間等少量部位採用滿堂基礎時，其工程量併入帶形基礎計算。5 箱形基礎的底板 包括邊緣加厚部分 套用無樑式滿堂基礎定額，其餘套用柱 梁 板 牆相應定額。6 裝置基礎僅考慮塊體形式，其他形式裝置基礎...
北師大版初中數學八下知識點彙總 分章節整理
北師大版 數學知識點彙總 八年級 下冊 第一章一元一次不等式和一元一次不等式組 一.不等關係 1.一般地,用符號 或 或 連線的式子叫做不等式.2.要區別方程與不等式 方程表示的是相等的關係 不等式表示的是不相等的關係.3.準確 翻譯 不等式,正確理解 非負數 不小於 等數學術語.非負數 大於等於0...
金融理論與實務章節考點總結及講解
金屬鑄幣本身具有內在價值。現代經濟中信用貨幣不具有內在價值，其所代表的價值表現為在市場上購買商品勞務的能力，即所謂貨幣購買力。指數的倒數便是代表貨幣購買力，它被稱為貨幣的對內價值。二 貨幣的對外價值 貨幣的價值還可表現為兌換其他貨幣的比率，即匯率。它被稱為貨幣的對外價值。貨幣的對內價值與對外價值間有...