2025年大學《信息與計算科學》專業(yè)題庫——信息與計算科學專業(yè)計算理論研究考試時間：______分鐘總分：______分姓名：______一、名詞解釋（每小題4分，共20分）1.無向圖2.不可達3.文法4.喬姆斯基譜系5.P類問題二、判斷題（每小題2分，共10分。在括號內打√或×表示正確或不正確）1.如果存在一條從頂點u到頂點v的路徑，那么在強連通圖中也一定存在一條從v到u的路徑。（）2.任何有限自動機都等價于一個確定有限自動機。（）3.如果語言L包含空串ε，那么L一定是正則語言。（）4.如果L是上下文無關語言，那么L也是遞歸可枚舉語言。（）5.對任意語言L，如果L∈P，那么L也一定屬于NP。（）三、簡答題（每小題6分，共30分）1.設G=(V,E)是一個無向連通圖，證明G中至少存在兩個頂點的度數(shù)是偶數(shù)。2.描述并解釋確定有限自動機（DFA）與非確定有限自動機（NFA）的主要區(qū)別。3.簡述P類和NP類問題的定義，并舉例說明一個屬于P類但可能不屬于NP類的例子（或解釋為什么通常認為它們不同）。4.寫出命題邏輯永真式（重言式）的定義，并給出一個包含至少三個命題變元的永真式的例子。5.解釋什么是圖靈機，并簡述其在計算理論中的意義。四、證明題（每小題10分，共20分）1.證明：一個有向圖G是強連通的當且僅當G中存在一個頂點u，使得從u到圖中每一個頂點以及從每一個頂點到u都存在路徑。2.證明：語言L={a^nb^nc^n|n≥1}不是正則語言。（可以使用泵引理）五、算法設計題（12分）設計一個算法，判斷給定的有向圖G=(V,E)是否含有環(huán)（即是否存在一個頂點序列v?,v?,...,v?，其中v?∈V,v?≠v?，且存在有向邊v?→v???，對于1≤i<k≤?）。描述你的算法思路，并用偽代碼或自然語言清晰地表達算法步驟。六、分析題（18分）考慮以下語言L：L={w∈{a,b}*|w中a的個數(shù)是2的冪次方}。例如，a,aa,bbb,aaaabbbb屬于L，而ab,aab,bab不屬于L。1.（6分）證明L不是正則語言。（可以使用pumpinglemma或其他方法）2.（12分）構造一個確定性下推自動機（DPDA）或線性有界自動機（LBA），能夠識別語言L。描述自動機的結構（包括狀態(tài)、棧字母、輸入字母、轉換函數(shù)等），并簡要說明其工作原理。試卷答案一、名詞解釋1.無向圖：由非空頂點集合V和邊集合E組成，其中每條邊e∈E連接一對頂點<u,v>，且<u,v>和<u,v>視為同一條邊，即邊是無序的（u,v)=(v,u))。2.不可達：在有向圖G=(V,E)中，如果頂點u和頂點v屬于V，且不存在一條有向路徑從u出發(fā)經過若干條有向邊到達v，則稱頂點u不可達頂點v。3.文法：一個形式化的規(guī)則集合，用于描述一個形式語言中所有字符串的結構。通常由四個部分組成：非終結符集合N，終結符集合Σ，開始符號S，以及產生式規(guī)則P。4.喬姆斯基譜系：喬姆斯基根據形式文法的復雜度將文法分為四個等價類型，從簡單到復雜依次為：0型文法（遞歸可枚舉文法，對應遞歸可枚舉語言），1型文法（上下文有關文法，對應上下文有關語言），2型文法（上下文無關文法，對應上下文無關語言），3型文法（正則文法，對應正則語言）。5.P類問題：在計算復雜性理論中，P類（Polynomialtime）是指所有可以在確定性圖靈機上在多項式時間內解決的問題的集合。換句話說，如果一個問題是P類的，那么存在一個算法，對于任意輸入，該算法能在時間T(n)=O(n^k)（k為常數(shù)）內給出正確答案，其中n是輸入的規(guī)模。二、判斷題1.(√)證明：設G=(V,E)是強連通圖。任取頂點u∈V，因為G是強連通的，所以對于V中的每一個頂點v，存在從u到v的有向路徑p?。同樣，對于每一個頂點v∈V，存在從v到u的有向路徑p??？紤]路徑p?的終點，記為v'。由于G是強連通的，存在從v'到u的有向路徑p?。于是，從u出發(fā)，經過p?然后p?，可以到達v'。因為v'是p?的終點，且p?是從v到v'的路徑，所以從u出發(fā)，經過p?然后p?再經過p?，最終到達v。這表明從u到v存在路徑。由u和v的任意性，結論成立。2.(√)證明：設M=(Q,Σ,δ,q?,F)是一個NFA。構造一個DFAM'=(Q',Σ,δ',q?',F')如下：Q'是Q的所有狀態(tài)子集，即Q'=P(Q)，Q'中的每個元素對應一個等價狀態(tài)。δ'是DFA的轉移函數(shù)，定義為：對于任意的S∈Q',a∈Σ，δ'(S,a)=∪{δ(q,a)|q∈S}。即DFA的轉移是NFA在S狀態(tài)下，對輸入a的所有可能轉移狀態(tài)的并集。q?'={q?}。F'={S∈Q'|S∩F≠?}?？梢宰C明M'是確定的，并且M'和M接受相同的語言。3.(×)反例：考慮語言L={a?|n是奇數(shù)}。L包含空串ε（當n=1時）。但是，L不是正則語言?？梢允褂胮umpinglemma證明。假設L是正則的，根據pumpinglemma，存在一個常數(shù)p，對于任意w∈L且|w|≥p，w可以分成xyz，滿足|xy|≤p,|y|≥1，以及對于所有i≥0，xy^iz∈L。取w=a^(2p+1)，|w|=2p+1≥p。此時x=a^k,y=a^m,z=a^(2p+1-k-m)，其中m≥1。將y重復i次，當i=2時，字符串變?yōu)閍^(k+m*2+m)=a^(2p+1+m)。由于m≥1，新字符串的長度為2p+1+m，不再是奇數(shù)（除非m=0，但m≥1），即不屬于L。矛盾，因此L不是正則語言。4.(√)證明：上下文無關語言（CFL）是遞歸可枚舉語言（RE）的一個子集。因為所有CFL都可以被確定性下推自動機（DPDA）或非確定性下推自動機（NPDA）接受，而DPDA或NPDA都可以被圖靈機模擬。因此，存在一個圖靈機可以接受任何CFL，所以CFL是RE的子集。另一方面，所有遞歸問題都是RE的，而遞歸問題都可以被圖靈機解決，因此所有遞歸問題都是RE的。上下文無關語言是形式語言的一種，可以通過形式文法定義，而形式文法的產生過程本身是遞歸定義的，因此可以構造一個圖靈機來判定一個字符串是否屬于某個特定的CFL（雖然判定任意CFL是否是CFL是PSPACE-complete問題，但給定一個具體的CFL，判定字符串是否屬于它屬于RE）。因此，CFL是遞歸的。5.(√)證明：假設L不是NP類的。根據定義，不存在一個非確定性圖靈機NTM，能在多項式時間內判定L。這意味著對于任意L中的字符串w，不存在一個在多項式時間內能接受w的NTM。但是，對于P類問題，存在一個確定性圖靈機DM，能在多項式時間內判定。如果L是P類的，那么它也是NP類的（因為P?NP）。因此，如果L不是NP類的，它必然不屬于P類。反之，如果L是P類的，那么它顯然屬于NP類。所以，L∈PiffL∈NP。三、簡答題1.證明：證明無向連通圖中偶度頂點個數(shù)是V(G)（頂點數(shù)）+E(G)（邊數(shù)）-1的奇數(shù)倍。根據歐拉公式，對于無向連通圖，V(G)-E(G)+F(G)=1，其中F(G)是連通分量數(shù)，對于連通圖F(G)=1。所以V(G)-E(G)=0，即V(G)=E(G)。將V(G)=E(G)代入V(G)+E(G)-1，得到2E(G)-1，這是一個奇數(shù)。設偶度頂點個數(shù)為e，奇度頂點個數(shù)為o。根據握手定理，所有頂點的度數(shù)之和等于邊數(shù)的兩倍，即Σv∈Vdeg(v)=2E(G)。因為偶度頂點度數(shù)之和是偶數(shù)，奇度頂點度數(shù)之和也是偶數(shù)（因為奇數(shù)個奇數(shù)相加是奇數(shù)，偶數(shù)個奇數(shù)相加是偶數(shù)），所以它們的總和Σv∈Vdeg(v)是偶數(shù)。因此，e必須是偶數(shù)。又因為2E(G)-1是奇數(shù)，而V(G)=E(G)，所以V(G)（即頂點數(shù)）也必須是奇數(shù)。設V(G)=2k+1。那么2E(G)-1=2(2k+1)-1=4k+1。這意味著V(G)+E(G)-1=(2k+1)+(2k+1)-1=4k+1。所以V(G)+E(G)-1是奇數(shù)。根據之前推導，V(G)+E(G)-1=2E(G)-1，是奇數(shù)?，F(xiàn)在知道V(G)是奇數(shù)，e是偶數(shù)。設o=V(G)-e。因為e是偶數(shù)，V(G)是奇數(shù)，所以o必須是奇數(shù)。即奇度頂點的個數(shù)是奇數(shù)。因此，無向連通圖中奇度頂點的個數(shù)o是奇數(shù)，偶度頂點的個數(shù)e是偶數(shù)。因為總頂點數(shù)V(G)=e+o，且V(G)是奇數(shù)，e是偶數(shù)，所以o必須是奇數(shù)。即至少存在兩個（實際上是偶數(shù)個，但題目問至少）頂點的度數(shù)是偶數(shù)。2.DFA與NFA的區(qū)別：*狀態(tài)轉換：DFA的每個狀態(tài)轉換是確定的，即對于給定的狀態(tài)和輸入符號，只能轉移到一個唯一確定的新狀態(tài)。NFA的每個狀態(tài)轉換可以是確定的，也可以是不確定的（多個可能的新狀態(tài)）。NFA還允許ε轉換（空串轉換），即在不消耗輸入符號的情況下從一個狀態(tài)轉移到另一個狀態(tài)。*接受方式：DFA接受字符串w當且僅當DFA從初始狀態(tài)開始，讀取完w后到達某個接受狀態(tài)。NFA接受字符串w當且僅當存在至少一條從初始狀態(tài)開始，讀取完w后到達某個接受狀態(tài)的路徑（允許使用ε轉換）。*等價性：任何DFA都可以模擬一個NFA。反之，任何NFA都可以被一個DFA等價模擬（雖然模擬的DFA可能狀態(tài)數(shù)會指數(shù)級增長）。因此，DFA和NFA接受的語言類是相同的，都是正則語言。*復雜度：DFA的模擬通常比NFA更直接、效率更高。3.P類和NP類：*P類：P類（Polynomialtime）是指所有可以在確定性圖靈機（DTM）上在多項式時間內解決的問題的集合。多項式時間意味著算法的運行時間T(n)對于輸入規(guī)模n，滿足T(n)≤c*n^k，其中c和k是常數(shù)。這類問題是“易解的”，因為存在一個快速的、確切的算法可以找到解。*NP類：NP（Non-deterministicPolynomialtime）是指所有可以在非確定性圖靈機（NTM）上在多項式時間內驗證解的正確性的問題的集合。換句話說，一個語言L屬于NP，如果存在一個多項式時間的“驗證器”程序V和多項數(shù)r，使得對于任意輸入w：*如果w∈L，那么存在一個長度不超過r|w|的“證書”或“證據”x，使得V(w,x)接受。*如果w?L，那么對于任何長度不超過r|w|的x，V(w,x)都拒絕。NP類的問題是“易驗證的”。注意，問題本身可能很難解（即w∈L時找到證書x可能很困難），但一旦有人提供了一個候選解（證書x），我們可以在多項式時間內快速驗證它是否為真解。*例子（P≠NP通常認為成立）：著名的例子是旅行商問題（TSP）。給定一系列城市和每對城市之間的距離，找到訪問所有城市恰好一次并返回起點的最短路徑。對于TSP，找到這條最短路徑本身被認為是NP-hard的（可能比P更難）。但是，如果我們被告知一條路徑，我們可以很容易地在多項式時間內計算這條路徑的總長度，并判斷它是否小于某個給定的界限（例如已知的最短路徑長度）。因此，TSP是NP類的。而它是否屬于P類（即是否存在多項式時間的算法來找到最短路徑）是未知的，也是PvsNP問題核心的一部分。通常認為P≠NP，即存在屬于NP但不屬于P的問題（如TSP通常被認為如此）。4.命題邏輯永真式：*定義：命題邏輯永真式（或重言式）是一個命題公式，它在所有可能的真值賦值下，其取值都為真。換句話說，無論命題變元取真（T）還是假（F），整個公式的真值總是T。*例子：(p∨?p)→p。分析：*當p=True時，?p=False。p∨?p=True∨False=True。所以(p∨?p)→p=True→True=True。*當p=False時，?p=True。p∨?p=False∨True=True。所以(p∨?p)→p=True→False=False。*看起來這個例子在p=False時為False，所以不是永真式。修改例子：(p∨?p)?(p∨?p)。分析：*當p=True時，?p=False。p∨?p=True∨False=True。所以(p∨?p)?(p∨?p)=True?True=True。*當p=False時，?p=True。p∨?p=False∨True=True。所以(p∨?p)?(p∨?p)=True?True=True。*因此，(p∨?p)?(p∨?p)是一個永真式。它實際上是一個重言律，稱為排中律。5.圖靈機：*定義：圖靈機（TuringMachine,TM）是一個抽象的計算模型，由一個有限狀態(tài)集合、一個輸入字母表、一個帶字母表、一個初始狀態(tài)、一個接受狀態(tài)集合和一個轉換函數(shù)組成。它模擬了一個無限長的紙帶上的計算過程，紙帶被劃分成單元格，每個單元格可以存放帶字母表中的一個符號。一個讀寫頭可以在紙帶上左右移動，并根據當前狀態(tài)和讀取到的符號通過轉換函數(shù)確定下一個狀態(tài)、寫入一個新符號以及移動方向。*意義：圖靈機是計算理論中描述計算能力的核心模型。它是“通用計算裝置”的模型，意味著任何可計算的函數(shù)（只要它是有限的或遞歸的）都可以被一個圖靈機實現(xiàn)。它為計算理論提供了形式化的基礎，定義了什么是“可計算的”。圖靈機也用來定義計算復雜性理論中的不同復雜度類（如P、NP、PSPACE等），這些類描述了計算問題的“難度”。圖靈機是不可計算性的證明（如停機問題）的關鍵工具。四、證明題1.證明：*(?)證明G是強連通的?存在u使得從u到任意頂點及任意頂點到u都有路徑：因為G是強連通的，所以對于任意兩個頂點u,v∈V，都存在從u到v和從v到u的有向路徑。特別地，對于任意頂點v∈V，存在從u到v的路徑p?，存在從v到u的路徑p??？紤]路徑p?的終點，記為v'。因為G是強連通的，存在從v'到u的路徑p??，F(xiàn)在構造從u到v的路徑：先沿p?從v到v'，再沿p?從v'到u，最后可以從u開始沿p?的一部分或其逆從u到達v。同樣，構造從v到u的路徑：先沿p?從u到v，再沿p?從v到v'，最后沿p?從v'到u。因此，對于任意頂點v∈V，都存在從u到v和從u到v的路徑。特別地，可以取u為任意頂點，結論成立。*(?)證明存在u使得從u到任意頂點及任意頂點到u都有路徑?G是強連通的：假設存在一個頂點u∈V，使得對于任意頂點v∈V，都存在從u到v的路徑puv，并且對于任意頂點v∈V，都存在從v到u的路徑pvu。為了證明G是強連通的，需要證明對于任意兩個頂點x,y∈V，都存在從x到y(tǒng)的路徑pxy。考慮任意x,y∈V。因為存在從u到x的路徑pxu，并且存在從x到u的路徑pxu，所以存在從u到x的路徑，存在從x到u的路徑。同樣，存在從u到y(tǒng)的路徑uyu，存在從y到u的路徑uyu。現(xiàn)在構造從x到y(tǒng)的路徑：先沿pxu從x到u，再沿uyu從u到y(tǒng)。這條路徑就是從x到y(tǒng)的路徑pxy。由于x和y是任意的，所以對于任意兩個頂點x,y∈V，都存在從x到y(tǒng)的路徑。因此，G是強連通的。2.證明（使用泵引理）：*泵引理：對于任何屬于NP類的語言L，存在一個常數(shù)p（泵長度），使得對于L中的任意字符串w，如果|w|≥p，那么w可以寫成xyz，滿足：1.|xy|≤p,|y|≥12.對于所有i≥0，xy^iz∈L*證明L={a^nb^nc^n|n≥1}不是正則語言：假設L是正則語言，則根據泵引理，存在一個泵長度p。取w=a^pb^pc^p，|w|=3p≥p，所以w∈L。根據泵引理，w可以寫成xyz，滿足|xy|≤p,|y|≥1。*因為|xy|≤p，且w的前p個符號是a，所以x和y中只包含a。即x=a^i,y=a^j,z=a^(p-i-j)b^pc^p，其中i+j≤p,j≥1。*將y重復i=2次，得到w'=xyz^2=a^i(a^j)^2a^(p-i-j)b^pc^p=a^(i+j+j+p-i-j)b^pc^p=a^(p+j)b^pc^p。*要使w'∈L，必須滿足w'的形式是a^nb^nc^n。比較w'的首部，w'以a^(p+j)開始，而L中的字符串以a^n(n≥1)開始。因為j≥1，所以p+j≥p+1>p。因此，w'的首部是a^(p+j)，這與L中字符串a^n(n≥1)的形式不符（因為n必須等于總長度3p，而w'的首部長度是p+j）。*這與泵引理的結論（xy^iz∈L對所有i≥0成立）矛盾。因此，假設L是正則語言是錯誤的。所以L不是正則語言。五、算法設計題算法思路：使用深度優(yōu)先搜索（DFS）來檢測圖中是否存在環(huán)。在DFS過程中，記錄每個頂點的訪問狀態(tài)（未訪問、已訪問、訪問中）。如果在DFS遞歸過程中，訪問到一個本身已經在“訪問中”狀態(tài)的頂點，則說明存在一條從該頂點到當前頂點的路徑，這條路徑加上當前頂點到該“訪問中”頂點的邊，構成一個環(huán)。為了處理強連通分量，可以多次執(zhí)行DFS，直到所有頂點都被訪問。偽代碼：```functionDetectCycle(G=(V,E)):color=arrayofVelements,initializedto"WHITE"foreachvinV:ifcolor[v]=="WHITE":ifDFSVisit(v,G,color):return"Yes,cycleexists"return"No,cycledoesnotexist"functionDFSVisit(v,G,color):color[v]="GRAY"http://Markasvisitingforeachuinneighbors(v)ofG:ifcolor[u]=="GRAY":returnTrue//Foundabackedge,hencecycleifcolor[u]=="WHITE"andDFSVisit(u,G,color):returnTruecolor[v]="BLACK"http://MarkasvisitedreturnFalse```說明：1.`color`數(shù)組用于記錄每個頂點的狀態(tài)：`"WHITE"`表示未訪問，`"GRAY"`表示正在訪問（DFS棧中），`"BLACK"`表示已訪問完成。2.`DetectCycle`函數(shù)初始化顏色，然后對每個未訪問的頂點調用`DFSVisit`。3.`DFSVisit`函數(shù)將當前頂點v標記為`"GRAY"`（正在訪問）。4.遍歷v的所有鄰接頂點u。如果發(fā)現(xiàn)鄰接頂點u的狀態(tài)是`"GRAY"`，則說明找到了一條從u到v的回邊（即從v或其后代沿著邊回到v或其祖先），這構成了一個環(huán)，返回True。5.如果鄰接頂點u的狀態(tài)是`"WHITE"`，則遞歸調用`DFSVisit(u)`。6.當所有鄰接頂點都被處理后，將當前頂點v標記為`"BLACK"`（已訪問完成）。7.如果`DFSVisit`從未返回True，則說明從v出發(fā)沒有發(fā)現(xiàn)環(huán)。8.`DetectCycle`函數(shù)如果對任何頂點調用`DFSVisit`返回True，則整個圖包含環(huán)；否則不包含環(huán)。六、分析題1.證明L={a^nb^nc^n|n≥1}不是正則語言（使用泵引理）：*泵引理假設：假設L是正則語言，則存在一個泵長度p。根據泵引理，對于L中的任意字符串w，如果|w|≥p，w可以寫成xyz，滿足|xy|≤p,|y|≥1,且對于所有i≥0,xy^iz∈L。*構造反例：取w=a^(p+1)b^(p+1)c^(p+1)。顯然|w|=3(p+1)≥p，所以w∈L。根據泵引理，w=a^pxa^kb^(p+1)c^(p+1)=a^(p+k)xyz，其中x=a^i,y=a^k,z=b^(p+1)c^(p+1)，滿足|xy|≤p(因為y只含a且長度為k)且k=|y|≥1。*選擇i并檢查：考慮i=2。計算w'=xy^2z=a^(p+k)a^(2k)b^(p+1)c^(p+1)=a^(p+3k)b^(p+1)c^(p+1)。*分析w'：w'的形式是a^(p+3k)b^(p+1)c^(p+1)。要使w'∈L，必須滿足w'的形式是a^nb^nc^n，其中n是相同的。比較首部，w'以a^(p+3k)開始，而L中字符串以a^n(n≥1)開始。因為k≥1，所以3k≥3>0。因此，p+3k≥p+3>p。這意味著w'的首部是a^(p+3k)，這與L中字符串a^n(n≥1)的形式不符（n必須等于總長度3(p+1)，而w'的首部長度是p+3k）。*得出結論：對于i=2，w'?L。這與泵引理的結論（xy^iz∈L對所有i≥0成立）矛盾。因此，假設L是正則語言是錯誤的。所以L不是正則語言。2.構造接受器：*選擇接受器類型：由于L不是正則語言，它不能被DPDA接受。L是上下文無關語言（可以通過下推文法描述：S→ABC|ε,A→aA|ε,B→bB|ε,C→cC|ε），所以可以被線性有界自動機（LBA）或確定性下推自動機（DPDA，如果L是LL的）接受。這里選擇構造一個確定性下推自動機（DPDA），假設L是LL(2)的（實際上它是LL(k)對任意k，因為文法不左遞歸且因子長度有限）。如果L不是LL(k)的，則需要LBA。*自動機結構：*狀態(tài)（Q）：Q={q?,q?,q?,q_f}。q?是初始狀態(tài)，q_f是接受狀態(tài)，q?用于計數(shù)a，q?用于計數(shù)b和c。*輸入字母表（Σ）：Σ={a,b,c}。*棧字母表（Γ）：Γ={X,Y,Z,$}。$是棧底標記。*初始狀態(tài)（q?）：q?