1. 空性：對于R，若給定形式是自動機比如£-NFA，則等價于判定能否從初始狀態到達接受狀態，這需計算可達狀態集合，若任一接受狀態在里面，則為非空，否則為空。耗時不超過O(n^2)，n為自動機的狀態數。若給定形式是正則表達式，則可先轉為£-NFA，再計算可達狀態集合，如此增多轉化時間O(s)，s為正則表達式的長度。也可不轉為自動機，直接根據基礎歸納規則用遞推法判定，耗時為O(s)。 對于CFL，等價于判定開始符號是否為產生的，若是則非空，否則為空。如直接用產生變元的基礎歸納法計算，那耗時O(n^2)，n為文法G的規模，接近變元的個數。一個改進的算法實現，預先建立以變元為索引的數組、每個變元的鏈接（產生式內鏈接、產生式間鏈接），則耗時O(n)
2. 成員性：設串w的長度為n。對于R，等價于判定自動機能否接受w，若給定形式是DFA，則耗時O(n)。若給定形式是NFA，則耗時O(n*s^2)，s為狀態數，如NFA有£轉移，那需先計算它的閉包，耗時增多O(s^2)，可見總耗時還是O(n*s^2)。若給定形式是正則表達式，則先轉為NFA，耗時增多O(r)，r為表達式的長度。 對于CFL，等價于判定從文法G的開始符號S能否推導出w，一般用CYK算法構造產生式三角表，再查看S是否屬于表的頂點集合，若屬于則能推導出w，否則不能，耗時為O(n^3)
posted @
2023-09-09 08:09 春秋十二月 閱讀(109) |
評論 (0) |
編輯 收藏因為一個整數p，若檢測為合數，這永遠是真命題；而檢測為素數，這命題只以較大概率成立。 可構造一種NP檢測算法，步驟如下：
1. 猜測p（位長度n）的因子列表｛p1,p2,…pi｝，這是非確定的，每個分支耗時O(n)
2. 驗證p1*p2*…pi？=p-1，耗時不超過O(n^2)
3. 若各因子乘積等于p-1，則用當前算法遞歸驗證每個因子都是素數
4. 隨機選擇p最小剩余系內的一個數x，計算x^((p-1)/q) （q遍歷上述列表經過步驟3驗證過的素因子）是否都不同余于1模p，若是則必有x^(p-1)同余于1模p，則由指數整除p的歐拉數及費馬小定理，知p為素數，考慮到有少量的合數也滿足費馬小定理，故需多次選擇x重復驗證，選擇個數最多為log(p)
分析：本算法涉及的數論定理——設p是奇素數，p-1的所有素因子是q1,q2,…qs，那么g為原根的充要條件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
結論：第3步可以看成遞歸調用樹，每個頂點為待檢測整數，其每個子結點為一個因子，則最多n層，每層至多耗時O(n^4)，所以每個路徑即檢測p是否素數的非確定任一分支中，總耗時O(n^5)。 2002年，印度科學家發現素檢測確定性多項式時間算法，于是從NP前進到了P
posted @
2023-09-09 08:07 春秋十二月 閱讀(699) |
評論 (0) |
編輯 收藏為什么命題邏輯有效性是可判定的，而謂詞邏輯有效性是不可判定的？
因為命題邏輯由有限個合式公式及原子命題構成，且原子命題的取值只有真、假兩種，簡單的判定方法是真值表窮舉，其復雜度為指數級：2^N，N為原子命題數量。快速的方法是先轉成合取范式（輸入是由否定、而且、或者、蘊含四種連接詞構成的語法正確的命題邏輯公式，經過對公式結構歸納作蘊含釋放、否定原子、分配律變換三步處理，同時運用DAG優化：共享終止即葉子結點、刪除冗余的測試結點、刪除重復的有相同子圖結構的內部結點，輸出等價最小的合取范式），再檢測合取范式的有效性（檢查所有子句，若每個子句包含至少一個原子及其否定形式，則有效，否則因為存在一種真值指派使其為假而導致整個合取范式無效），其復雜度為多項式級：N*logN+N，N為公式長度。謂詞邏輯基于命題邏輯擴展，添加了變元、函數、量詞“所有”與“存在”，如果量詞沒有約束變元范圍即定義域無限，那么函數值域也是無限的，另外可能引入的自由變元不受限制，這導致了解空間是無限的，所以不存在通用算法去判定任意謂詞邏輯公式是否有效，具體證明可以用pcp歸約，即構造一組特定的謂詞邏輯公式，它是有效的當且僅當pcp實例有解，又已知pcp是不可判定的，故該特定謂詞邏輯有效性是不可判定的，由于任意包括特定，所以謂詞邏輯有效性是不可判定的
posted @
2023-09-09 08:05 春秋十二月 閱讀(115) |
評論 (0) |
編輯 收藏設程序片段S=if C then S1 else S2，S1和S2可以是由賦值、條件、循環構成的復雜語句，S不為當前程序最后語句或某個循環主體最后語句，則S對應的流圖生成的深度優先生成樹T有3條樹邊，有S1的出口數+S2出口數-1條交叉邊。為什么是3條樹邊？C到S1、C到S2、S1或S2到S3（S3是S后繼結點，下同）。為什么交叉邊數是S1出口數+S2出口數-1？因為流圖中S1出口及S2出口到S3的邊，在生成T的過程中，只有1個出口比S3先訪問，這對應形成1條樹邊，訪問S3后再訪問其它出口，這對應形成其它出口到S3的交叉邊，注意這里沒有前向邊，因為較晚訪問的出口在T中不可能是S3的祖先。如果把S改為if C then S1，情況會怎樣？結果取決于生成T的過程中先訪問S3還是S1。若先訪問S3，則有樹邊2條：C到S3、C到S1，交叉邊數等于S1的出口數：S1的每個出口到S3各一條邊，沒有前向邊。若先訪問S2，則有樹邊1條：C到S2，前向邊1條：C到S3，交叉邊數等于S1出口數-1。
總結此類問題分析的基本思路是對程序控制結構先構建流圖，再構建深度優先生成樹，辨別其中的前向邊、交叉邊、后退邊
posted @
2023-09-07 06:50 春秋十二月 閱讀(77) |
評論 (0) |
編輯 收藏1.閉包記錄分配：若逃逸分析能識別哪些閉包記錄在創建它們的函數中是出口不活躍的，則這些閉包記錄可分配在棧幀中（不再是堆中）
2.內聯擴展：由于小函數較多，因此內聯可以免去調用開銷而提高性能，對于遞歸函數，需先用循環前置頭轉換再內聯，如果是尾遞歸函數，可先使用尾調用優化刪除遞歸。如果一個函數的所有調用都被內聯擴展，并且該函數沒有作為參數傳遞或其它方式被引用，那么可以刪除這個函數本身即函數定義。內聯擴展可以繼續作用于擴展后的函數體，只要存在函數調用，這也叫層疊式內聯
3.循環不變量參數外提：遞歸函數經過循環前置頭轉換后，若每次遞歸調用頭函數，傳入的某些參數值總不變，則可以將它們從函數參數中刪除，函數體中的每次使用出現用序曲函數對應的參數名替換
4.解開嵌套的let：將嵌套的多層let中的代碼合并為一個let中的代碼，in中的代碼不變
5.避免代碼膨脹：由于內聯復制函數體，通常使程序體積變大，且層疊式內聯可無限擴展下去，因此為避免代碼膨脹，有如下啟發式策略對內聯進行控制
a) 只內聯執行很頻繁的函數調用，可根據靜態估計比如循環嵌套深度、迭代次數，或根據執行剖面分析反饋，計算函數的執行頻率
b) 內聯很小的函數，其函數體不會比直接調用多出較多指令
c) 內聯只調用一次的函數，然后刪除原來的函數定義
posted @
2023-09-07 06:47 春秋十二月 閱讀(77) |
評論 (0) |
編輯 收藏1. 整數r>s>0，(r, s)=1，2?r+s，x=r^2-s^2, y=2rs, z=r^2+s^2，求證(x, y)=1，(y, z)=1
?證明：由2?r+s（r與s必一奇一偶）知2?r-s，故2?r^2-s^2，以及2?(r+s)(r+s)。又1=(r, s)=(r+s, r)=(r+s, s)=(r+s, rs)。同理得1=(r, s)=(r-s, rs)，故1=((r+s)(r-s), rs)=(r^2-s^2, rs)，又1=(2, r^2-s^2)，故(r^2-s^2, 2rs)=1，即(x, y)=1。?(y, z)=(2rs, r^2+s^2)=(2rs, r^2+s^2+2rs)=(2rs, (r+s)(r+s))=(rs, (r+s)(r+s))=(rs, r+s)=(r, r+s)=(r, s)=1
?注：用最大公約數定義、整除性質、反證法，也可以得出(x, y)=1，(y, z)=1。本法則直接從最大公約數定理推導
2. u^2+3v^2=2p不可能成立，u、v為整數，p為奇素數
證明：u^2+3v^2=2p => u^2+v^2=2(p-v^2) => ?2|u^2+v^2=(u+v)^2-2uv => 2|(u+v)^2 => 2|u+v。得出這個中間結論，再由它可得4|2(u+v)|2v(u+v)=2v^2+2uv，以及4|(u+v)^2=u^2+v^2+2uv，故得4|u^2+3v^2+4uv，繼得4|u^2+3v^2=2p，即2|p，所以矛盾，證畢
?3. 若四個正整數y1*x2=y2*x1，(x1,y1)=(x2,y2)=1，則x1=x2，y1=y2
?證明：由y1*x2=y2*x1可得x1|y1*x2，又因(x1,y1)=1，故x1|x2；另得x2|y2*x1，又因(x2,y2)=1，故x2|x1；終得x1=x2，y1=y2
4. 假設2?z，z^3=x^2+3y^2有解且滿足(x, y)=1，其通解形式為x=a^3-9ab^2，y=3a^2b-3b^2，a、b滿足z=a^2+3b^2，求證(-3/p)=1，p是z的任一素因子；(a, 3b)=1
證明：先論證中間結論3?z，p>3且(p, xy)=1。若3|z，則3|x^2+3y^2=>3|x^2=>3|x=>9|x^2，另有9|x^2+3y^2=>9|3y^2=>3|y^2=>3|y，這與(x, y)=1矛盾，故3?z。又2?z，得p>3，由此若p|x，則p|3y^2得p|y，或若p|y，則p|x^2得p|x，都與(x, y)=1矛盾，故(p, xy)=1。
再論證勒讓德符號(-3/p)=1。由以上中間結論得等價形式x^2+3y^2=(Z^3p^2)p，及p?x^2、p?y^2，推得1=(x^2/p)=(-3y^2/p)=(-3/p)。
最后論證(a, 3b)=1。假設2|z，則2|a^2+b^2=(a+b)^2-2ab或(a-b)^2+2ab =>2|a+b, 2|a-b。因題設是2?z，故2?a+b, 2?a-b，由此推得2?a^2-b^2, 4?a^2-b^2，進而8?a^2-b^2，即(8, a^2-b^2)=1。由1=(x, y)=(a^3-9ab^2, 3a^2b-3b^2)=(a(a^2-9b^2), 3b(a^2-b^2))。又(a^2-9b^2, a^2-b^2)=(8b^2, a^2-b^2)=(b^2, b^2-a^2)=(b^2, a^2)=(a, b)^2，于是令a^2-9b^2=(a, b)^2*A, a^2-b^2=(a, b)^2*B，則得1=(x, y)=(a, b)^2*(aA, 3bB)，故(a, 3b)=1
5. 已知2?u+w，3?u，(u, w)=1，求證(2u, u^2+3w^2)=1
證明：2?u+w=>2?u^2+w^2=>2?u^2+3w^2，即(2, u^2+3w^2)=1。
由3?u，(u, w)=1得(u, 3w)=(u, 3w^2)=(u, u^2+3w^2)=1。
綜上兩式結果得(2u, u^2+3w^2)=1
6. 已知(3v, w)=1，2?3v+w，求證(18v, 3v^2+w^2)=1
證明：(3v, w)=1=>(3v, w^2)=(3v, 3v^2+w^2)=1。
(3v, w)=1=>(3, w)=1=>(3, w^2)=(3, 3v^2+w^2)=1。2?3v+w=>2?v+w=>2?v^2+w^2=>2?3v^2+w^2，即(2, 3v^2+w^2)=1。
綜上三式結果得(18v, 3v^2+w^2)=1
###############################
從1、5和6問題的證明過程可得，如果一個數由兩個或多個因子相乘，那么求證是否互素可以逐一求每個因子與另一個數是否都互素
posted @
2023-09-07 06:43 春秋十二月 閱讀(634) |
評論 (0) |
編輯 收藏周知aes有限域同構于系數為F2域一元多項式環的商環，其理想由不可約多項式m(x)=x^8+x^4+x^3+x+1生成，即F2^8≌F2[x]/(m(x))。這次進一步用域擴張的觀點分析，可以得知F2[x]/(m(x))正是包涵m(x)零點的擴域，設為K。那么如何理解？
令I=(m(x))，則K=F2[x]/I，理解關鍵是找出m(x)在K上的零點，以及K怎樣包涵F2？
1. 零點為~x。這里用~g(x)表示多項式在K中的陪集，即~g(x)=g(x)+I，所以~x=x+I。把~x代入m(x)，根據商環定義的加乘運算，代換結果為m(x)+I=~m(x)=~0（~0是K的零元）。那么還有嗎？比如~(x+a)（a非0），~x^2，代入這些得到的陪集代表不等于m(x)，所以不是零點。因此零點是唯一的一次多項式x之陪集
2. 構造映射σ，把0對到K中的零多項式即~0，1對到K中的常數多項式即~1，且σ(0+1)=~1=~0+~1=σ(0)+σ(1)，σ(0*1)=~0=~0*~1=σ(0)*σ(1)，又依多項式比較法則得~0不等于~1，故σ是單同態，K包涵F2
小結：商群、商環、商域類似模同余之剩余系，理解這些結構的關鍵是深入理解等價類、陪集，進而可理解正規子群、理想，最后就是商X之類的東西
posted @
2023-09-07 06:39 春秋十二月 閱讀(121) |
評論 (0) |
編輯 收藏1. 輸入：前者是二進制可執行程序，后者是高級語言源程序
2. 優化對象：前者主要是直線型代碼區域比如蹤跡或超塊（熱點路徑代碼），超塊類似后者中的擴展塊；后者是控制流圖，即所有代碼塊，不限于熱點路徑代碼。超塊構造類似后者中的基本塊放置和過程放置
3. 優化方法：前者要運行時采集剖析數據比如結點剖析和邊剖析，再基于剖析數據形成有利于指令cache局部性的超塊，然后在超塊上作常量傳播、常量折疊、強度削弱、復寫傳播、死代碼消除、公共表達式消除等基本優化，也會作指令重排，但考慮到陷阱處理要恢復精確的客戶進程狀態，因此比較受限，沒有后者中的指令重排自由。后者如果基于剖析作優化，那么效果和前者差不多
4. 寄存器分配：都是基于活躍范圍的沖突圖著色算法，但前者考慮到陷阱處理會延長相關寄存器的活躍范圍，而后者不用
————————————————————————
總結：二進制優化所用的技術和編譯優化其實相同，不同的是為陷阱處理所作的改變調整，以及運用在熱點代碼塊而非所有塊
posted @
2023-09-06 23:44 春秋十二月 閱讀(88) |
評論 (0) |
編輯 收藏1. NFA到DFA：設NFA的狀態數為n，根據子集構造法，則至多有2^n個狀態轉移，對每個狀態轉移，其狀態分量至多有n個狀態，每個狀態計算它的可達狀態集合耗時為O(n^2)，另可達狀態集合的并耗時為O(n^2)，故一個轉移耗時為n*O(n^2)=O(n^3)，則所有轉移總耗時為O(n^3*2^n)。由于實際產生的狀態數遠小于2^n（通常為n），因此耗時為O(n^3*s)，s為DFA實際具有的狀態數
2. DFA到NFA：轉化方法是修改轉移表，對每個狀態轉移的目標狀態加上集合括號（因NFA對特定輸入可能有多個目標狀態，故為集合），若轉為£-DFA，則還需對每個狀態增加對£的轉移為空集。該方法耗時為O(n)，n為DFA的狀態數
3. DFA到正則表達式：設DFA狀態數為n，根據遞推公式R(i,j,k)=R(i,j,k-1)+R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)（1<=i<=j<=n，0<=k<=n）來逐步構造表達式，最終的表達式就是所有R(1,j,n)的并，其中j為可接受狀態。該過程會產生總共n^3+n^2個表達式，每次k遞增導致表達式長度增為4倍，故總耗時為O(n^3*4^n)。另一種更快的方法是消除所有除初始和接受狀態外的中間狀態，每次消除一個，就合并其前驅經過它到其后繼的正則表達式和前驅直接到后繼的正則表達式，因前驅或后繼至多n-2個，則共有(n-2)^2個前驅到后繼的直通邊，且中間狀態至多n-2個，故耗時為O(n^3)；最后合并各接受狀態的正則表達式，因接受狀態至多n-1個，故耗時為O(n)。故總耗時為O(n^3)
4. 正則表達式到£-NFA：作詞法分析，對每個終結符號構建狀態結點及轉移邊，即子£-NFA，特定符號對應用并、連接、閉包、結合之一聯合已構建的子£-NFA，耗時為O(n)，n為正則表達式的長度
posted @
2023-09-06 23:42 春秋十二月 閱讀(90) |
評論 (0) |
編輯 收藏1. 三條定律：交換律、結合律、吸收律（對于半格是冪等律），吸收律包含了冪等律
2. 上下界：交半格每對元素都有唯一最大下界，并半格每對元素都有唯一最小上界，格每對元素都有唯一最大下界和唯一最小上界
3. 格定義一個偏序，偏序有三個性質：自反性、反對稱性、傳遞性
4. 格與偏序的關系：每個格對應一個偏序，但不是所有偏序都對應一個格，要滿足每對元素都有唯一最小上界和（或，對于半格）唯一最大下界。如果集合中的任何一個子集（包括空集）均存在最小上界和最大下界，那么對應一個完備格
5. 任何元素有限的格都是完備格，格中的交運算和并運算對于其定義的偏序來說是單調的
6. 格的乘積、和、提升、映射仍然是格，利用這個性質，可以在已有格的基礎上增量地構造描述能力更豐富的格，這種技術稱為論域精化，是提高程序靜態分析精度的重要指導思想之一
posted @
2023-09-06 23:39 春秋十二月 閱讀(483) |
評論 (0) |
編輯 收藏