隱藏信息檢測(cè)與還原技術(shù)

1、1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析黃劉生黃劉生中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 國(guó)家高性能計(jì)算中心（合肥）國(guó)家高性能計(jì)算中心（合肥）2008.8.192第一部分第一部分概率算法概率算法3ch.1 緒論緒論1. 故事：故事：想象自己是神化故事的主人公，你想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能的兩個(gè)地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。的兩個(gè)地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。假設(shè)你如果已到達(dá)其中一處，就立即知道假設(shè)你如果已到達(dá)其中一處，就立即知道該處是否為藏寶

2、地點(diǎn)。你到達(dá)兩處之一地該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地點(diǎn)，以及從其中一處到另一處的距離是點(diǎn)，以及從其中一處到另一處的距離是5天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財(cái)寶。假設(shè)你光顧寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶藏的方案有兩種：取寶藏的方案有兩種：1.1 引言引言4 方案方案1. 花花4天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn)，然天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn)，然后出發(fā)尋寶，一旦出發(fā)不能重新計(jì)算后出發(fā)尋寶，一旦出發(fā)不能重新計(jì)算 方案方案2. 有一個(gè)小精靈告訴你地圖的秘密，但你有一個(gè)小精靈告訴你地圖的秘密，但你必須付給他報(bào)酬，相當(dāng)于龍必須付給他報(bào)

3、酬，相當(dāng)于龍3晚上拿走的財(cái)寶晚上拿走的財(cái)寶 prob 1.1.1 若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代價(jià)，你是否接受小精靈的幫助？?jī)r(jià)，你是否接受小精靈的幫助？ 顯然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍栾@然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍杞o出給出3晚上被盜竊的財(cái)寶量，否則你將失去晚上被盜竊的財(cái)寶量，否則你將失去4晚被晚被盜財(cái)寶量。盜財(cái)寶量。 但是，但是，若冒險(xiǎn)，你可能做得更好！若冒險(xiǎn)，你可能做得更好！1.1 引言引言5 設(shè)設(shè)x是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)y是惡龍每是惡龍每晚盜走的寶藏價(jià)值，并設(shè)晚盜走的寶藏價(jià)值，并設(shè)x9y 方案方案1：4天計(jì)

4、算確定地址，行程天計(jì)算確定地址，行程5天，你得到的寶天，你得到的寶藏價(jià)值為：藏價(jià)值為：x-9y 方案方案2：3y付給精靈，行程付給精靈，行程5天失去天失去5y，你得到的，你得到的寶藏價(jià)值為：寶藏價(jià)值為：x-8y 方案方案3：投硬幣決定先到一處，失敗后到另一處投硬幣決定先到一處，失敗后到另一處(冒冒險(xiǎn)方案險(xiǎn)方案) 一次成功所得：一次成功所得：x-5y，機(jī)會(huì)，機(jī)會(huì)1/2 二次成功所得：二次成功所得：x-10y，機(jī)會(huì)，機(jī)會(huì)1/21.1 引言引言期望贏利：期望贏利：x-7.5y62. 意義意義 該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇

5、更好，尤其時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時(shí)間大于隨機(jī)選擇的平均時(shí)是當(dāng)最優(yōu)選擇所花的時(shí)間大于隨機(jī)選擇的平均時(shí)間的時(shí)侯間的時(shí)侯 顯然，概率算法只能是期望的時(shí)間更有效，顯然，概率算法只能是期望的時(shí)間更有效，但它有可能遭受到最壞的可能性。但它有可能遭受到最壞的可能性。73. 期望時(shí)間和平均時(shí)間的區(qū)別期望時(shí)間和平均時(shí)間的區(qū)別v 確定算法的平均執(zhí)行時(shí)間確定算法的平均執(zhí)行時(shí)間 輸入規(guī)模一定的所有輸入實(shí)例是等概率出現(xiàn)時(shí)，算法輸入規(guī)模一定的所有輸入實(shí)例是等概率出現(xiàn)時(shí)，算法的平均執(zhí)行時(shí)間。的平均執(zhí)行時(shí)間。v 概率算法的期望執(zhí)行時(shí)間概率算法的期望執(zhí)行時(shí)間 反復(fù)解同一個(gè)輸入實(shí)例所花的平均

6、執(zhí)行時(shí)間。反復(fù)解同一個(gè)輸入實(shí)例所花的平均執(zhí)行時(shí)間。 因此，對(duì)概率算法可以討論如下兩種期望時(shí)間因此，對(duì)概率算法可以討論如下兩種期望時(shí)間 平均的期望時(shí)間平均的期望時(shí)間：所有輸入實(shí)例上平均的期望執(zhí)行時(shí)：所有輸入實(shí)例上平均的期望執(zhí)行時(shí)間間 最壞的期望時(shí)間最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間84. 例子例子 快速排序中的隨機(jī)劃分快速排序中的隨機(jī)劃分要求學(xué)生寫一算法，由老師給出輸入實(shí)例，按運(yùn)行時(shí)間打分，要求學(xué)生寫一算法，由老師給出輸入實(shí)例，按運(yùn)行時(shí)間打分，大部分學(xué)生均不敢用簡(jiǎn)單的劃分，運(yùn)行時(shí)間在大部分學(xué)生均不敢用簡(jiǎn)單的劃分，運(yùn)行時(shí)間在1500-2600ms，三個(gè)學(xué)

7、生用概率的方法劃分，運(yùn)行時(shí)間平均為三個(gè)學(xué)生用概率的方法劃分，運(yùn)行時(shí)間平均為300ms。 8皇后問(wèn)題皇后問(wèn)題 系統(tǒng)的方法放置皇后系統(tǒng)的方法放置皇后(回溯法回溯法)較合適，找出所有較合適，找出所有92個(gè)解個(gè)解 o(2n)，若只找若只找92個(gè)其中的任何一個(gè)解可在線性時(shí)間內(nèi)完成個(gè)其中的任何一個(gè)解可在線性時(shí)間內(nèi)完成o(n)。 隨機(jī)法：隨機(jī)法：隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)n較大較大時(shí)時(shí) 判斷大整數(shù)是否為素?cái)?shù)判斷大整數(shù)是否為素?cái)?shù)確定算法無(wú)法在可行的時(shí)間內(nèi)判斷一個(gè)數(shù)百位十進(jìn)制數(shù)是否素確定算法無(wú)法在可行的時(shí)間內(nèi)判斷一個(gè)數(shù)百位十進(jìn)制數(shù)是否素?cái)?shù)，否則密碼就不安

8、全。數(shù)，否則密碼就不安全。 概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率95. 概率算法的特點(diǎn)概率算法的特點(diǎn) (1) 不可再現(xiàn)性不可再現(xiàn)性 在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果不盡相同，例在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果不盡相同，例如如 n-皇后問(wèn)題皇后問(wèn)題概率算法運(yùn)行不同次將會(huì)找到不同的正確解概率算法運(yùn)行不同次將會(huì)找到不同的正確解 找一給定合數(shù)的非平凡因子找一給定合數(shù)的非平凡因子每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必定相同定相同 (2) 分析困難分析困難 要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的

9、知識(shí)要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)106. 約定約定 隨機(jī)函數(shù)隨機(jī)函數(shù)uniform：隨機(jī)隨機(jī)，均勻均勻，獨(dú)立獨(dú)立 設(shè)設(shè)a，b為實(shí)數(shù)，為實(shí)數(shù)，ab, uniform(a, b) 返回返回x，a x b 設(shè)設(shè)i，j為整數(shù)，為整數(shù)，ij, uniform(i.j)=k, i k j 設(shè)設(shè)x是非空有限集，是非空有限集， uniform(x) x 11例例1：設(shè)設(shè)p是一個(gè)素?cái)?shù)，是一個(gè)素?cái)?shù)，a是一個(gè)整數(shù)滿足是一個(gè)整數(shù)滿足1a0 do if (j is odd) s sa mod p;a a2 mod p;j j div 2;return s;draw (a, p) / 在在x中隨機(jī)取一元素中隨機(jī)取一元

10、素j uniform(1.p-1);return modularexponent(a, j, p); / 在在x中隨機(jī)取一元素中隨機(jī)取一元素13n 偽隨機(jī)數(shù)發(fā)生器偽隨機(jī)數(shù)發(fā)生器在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。下是用偽隨機(jī)數(shù)發(fā)生器代替。大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：s: x x, 這里這里x足夠大，它是種子的值域足夠大，它是種子的值域r: x y, y是偽隨機(jī)數(shù)函數(shù)的值域是偽隨機(jī)數(shù)函數(shù)的值域使用使用s獲得種子序列：獲得種子序列：x0=g, xi=s(xi-1), i0然后使

11、用然后使用r r獲得偽隨機(jī)序列：獲得偽隨機(jī)序列：yi=r(xi), i 0該序列必然是周期性的，但只要該序列必然是周期性的，但只要s s和和r r選的合適，該選的合適，該周期長(zhǎng)度會(huì)非常長(zhǎng)。周期長(zhǎng)度會(huì)非常長(zhǎng)。tc中可用中可用rand()和和srand(time), 用用gnu c更好更好141. 基本特征基本特征隨機(jī)決策隨機(jī)決策在同一實(shí)例上執(zhí)行兩次其結(jié)果在同一實(shí)例上執(zhí)行兩次其結(jié)果(或過(guò)程或過(guò)程)可能不可能不同同在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不太相同在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不太相同2. 分類分類numerical, monte carlo, las vegas, sherwood.很多人

12、將所有概率算法很多人將所有概率算法(尤其是數(shù)字的概率算法尤其是數(shù)字的概率算法)稱為稱為monte carlo算法算法1.2 概率算法的分類概率算法的分類15 數(shù)字算法數(shù)字算法隨機(jī)性被最早用于求數(shù)字問(wèn)題的近似解隨機(jī)性被最早用于求數(shù)字問(wèn)題的近似解例如，求一個(gè)系統(tǒng)中隊(duì)列的平均長(zhǎng)度的問(wèn)題，確定算例如，求一個(gè)系統(tǒng)中隊(duì)列的平均長(zhǎng)度的問(wèn)題，確定算法很難得到答案法很難得到答案l 概率算法獲得的答案一般是近似的，但通常算法執(zhí)行概率算法獲得的答案一般是近似的，但通常算法執(zhí)行的時(shí)間越長(zhǎng)，精度就越高，誤差就越小的時(shí)間越長(zhǎng)，精度就越高，誤差就越小l 使用的理由使用的理由 現(xiàn)實(shí)世界中的問(wèn)題在原理上可能就不存在精確解現(xiàn)實(shí)世

13、界中的問(wèn)題在原理上可能就不存在精確解例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個(gè)無(wú)理數(shù)在計(jì)例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個(gè)無(wú)理數(shù)在計(jì)算機(jī)中只能近似地表示算機(jī)中只能近似地表示 精確解存在但無(wú)法在可行的時(shí)間內(nèi)求得精確解存在但無(wú)法在可行的時(shí)間內(nèi)求得有時(shí)答案是以置信區(qū)間的形式給出的有時(shí)答案是以置信區(qū)間的形式給出的1.2 概率算法的分類概率算法的分類16 monte carlo算法算法 (mc算法算法)蒙特卡洛算法蒙特卡洛算法1945年由年由j. von neumann進(jìn)行核武模擬提出進(jìn)行核武模擬提出的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算方法，它

14、是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。這里我們指的這里我們指的mc算法是：算法是： 若問(wèn)題只有若問(wèn)題只有1個(gè)正確的解，而無(wú)近個(gè)正確的解，而無(wú)近似解的可能時(shí)使用似解的可能時(shí)使用mc算法算法例如，判定問(wèn)題只有真或假兩種可能性，沒(méi)有近似解例如，判定問(wèn)題只有真或假兩種可能性，沒(méi)有近似解 因式分解，我們不能說(shuō)某數(shù)幾乎是一個(gè)因子因式分解，我們不能說(shuō)某數(shù)幾乎是一個(gè)因子n 特點(diǎn)：特點(diǎn)：mc算法總是給出一個(gè)答案算法總是給出一個(gè)答案，但該答案未必正確，但該答案未必正確，成成

15、功功(即答案是正確的即答案是正確的)的概率正比于算法執(zhí)行的時(shí)間的概率正比于算法執(zhí)行的時(shí)間n 缺點(diǎn)：缺點(diǎn)：一般不能有效地確定算法的答案是否正確一般不能有效地確定算法的答案是否正確1.2 概率算法的分類概率算法的分類17 las vegas算法算法 (lv算法算法)lv算法絕不返回錯(cuò)誤的答案。算法絕不返回錯(cuò)誤的答案。n 特點(diǎn)：特點(diǎn)：獲得的答案必定正確獲得的答案必定正確，但有時(shí)它仍，但有時(shí)它仍根本就找不根本就找不到答案到答案。 和和mc算法一樣，成功的概率亦隨算法執(zhí)行時(shí)間增加而增算法一樣，成功的概率亦隨算法執(zhí)行時(shí)間增加而增加。無(wú)論輸入何種實(shí)例，只要算法在該實(shí)例上運(yùn)行足夠加。無(wú)論輸入何種實(shí)例，只要算法

16、在該實(shí)例上運(yùn)行足夠的次數(shù)，則算法失敗的概率就任意小。的次數(shù)，則算法失敗的概率就任意小。 sherwood算法算法sherwood算法總是給出正確的答案。算法總是給出正確的答案。當(dāng)某些確定算法解決一個(gè)特殊問(wèn)題平均的時(shí)間比最壞時(shí)當(dāng)某些確定算法解決一個(gè)特殊問(wèn)題平均的時(shí)間比最壞時(shí)間快得多時(shí)，我們可以使用間快得多時(shí)，我們可以使用sherwood算法來(lái)算法來(lái)減少，甚減少，甚至是消除好的和壞的實(shí)例之間的差別至是消除好的和壞的實(shí)例之間的差別。1.2 概率算法的分類概率算法的分類18這類算法主要用于找到一個(gè)數(shù)字問(wèn)題的近似解這類算法主要用于找到一個(gè)數(shù)字問(wèn)題的近似解2.1 值計(jì)算值計(jì)算n實(shí)驗(yàn)：將實(shí)驗(yàn)：將n根飛鏢隨機(jī)

17、投向一正方形的靶子，計(jì)算落入此正方根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目形的內(nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點(diǎn)的概率相等假定飛鏢擊中方形靶子任一點(diǎn)的概率相等(用計(jì)算機(jī)模擬比任用計(jì)算機(jī)模擬比任一飛鏢高手更能保證此假設(shè)成立一飛鏢高手更能保證此假設(shè)成立)設(shè)圓的半徑為設(shè)圓的半徑為r，面積，面積s1= r2； 方靶面積方靶面積s2=4r2由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由此知：由此知： ch.2 數(shù)字概率算法數(shù)字概率算法2244krnr4 /4nk n k19n求求近似值的算法近似值

18、的算法為簡(jiǎn)單起見(jiàn)，只以上圖的右上為簡(jiǎn)單起見(jiàn)，只以上圖的右上1/4象限為樣本象限為樣本darts (n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1); / 隨機(jī)產(chǎn)生點(diǎn)隨機(jī)產(chǎn)生點(diǎn)(x,y)if (x2 + y2 1) then k+; /圓內(nèi)圓內(nèi)return 4k/n;實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果： =3.141592654n = 1000萬(wàn)萬(wàn): 3.140740, 3.142568 (2位精確位精確)n = 1億億: 3.141691, 3.141363 (3位精確位精確)n = 10億億: 3.141527, 3.141507 (4位精確位精確)

19、2.1 值計(jì)算值計(jì)算20求求近似值的算法近似值的算法ex.1 若將若將y uniform(0, 1) 改為改為 y x, 則上則上述的算法估計(jì)的值是什么？述的算法估計(jì)的值是什么？2.1 值計(jì)算值計(jì)算21monte carlo積分積分(但不是指我們定義的但不是指我們定義的mc算法算法)1、概率算法概率算法1設(shè)設(shè)f: 0, 1 0, 1是一個(gè)連續(xù)函數(shù)，則由曲線是一個(gè)連續(xù)函數(shù)，則由曲線y=f(x), x軸軸, y軸和直線軸和直線x=1圍成的面積由下述積分給出：圍成的面積由下述積分給出：向單位面積的正方形內(nèi)投鏢向單位面積的正方形內(nèi)投鏢n次，落入陰影部分的鏢的次，落入陰影部分的鏢的數(shù)目為數(shù)目為k，則，則

20、顯然，只要顯然，只要n足夠大足夠大2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)10( )sf x dx/1kssk nn/sk n 221.概率算法概率算法1hitormiss (f, n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1);if y f(x) then k+;return k/n;note: 是是s/4的面積，的面積， =s, 2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)1201x dx12041x dx231. 概率算法概率算法1ex2. 在機(jī)器上用在機(jī)器上用 估計(jì)估計(jì)值，給出不值，給出不同的

21、同的n值及精度。值及精度。ex3. 設(shè)設(shè)a, b, c和和d是實(shí)數(shù)，且是實(shí)數(shù)，且a b, c d, f:a, b c, d是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)算積分：算積分：注意，函數(shù)的參數(shù)是注意，函數(shù)的參數(shù)是a, b, c, d, n和和f, 其中其中f用函用函數(shù)指針實(shí)現(xiàn)，請(qǐng)選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出數(shù)指針實(shí)現(xiàn)，請(qǐng)選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)12041x dx( )baf x dx241.概率算法概率算法1*ex4. 設(shè)設(shè),是是(0,1)之間的常數(shù)，證明：之間的常數(shù)，證明：若若i是是 的正確值

22、，的正確值，h h是由是由hitormisshitormiss算法返回的算法返回的值，則當(dāng)值，則當(dāng)n i(1-i)/2時(shí)有：時(shí)有：prob|h-i| t j ;3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理52例例2 2：離散對(duì)數(shù)計(jì)算：離散對(duì)數(shù)計(jì)算l離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等l定義：設(shè)定義：設(shè) a=gx mod p，記，記 logg,pa=x，稱，稱x為為a的的(以以g為底模除為底模除p)對(duì)數(shù)。對(duì)數(shù)。 從從p，g，a計(jì)算計(jì)算x稱為稱為離散對(duì)數(shù)離散對(duì)數(shù)問(wèn)題。問(wèn)題。l簡(jiǎn)單算法簡(jiǎn)單算法 計(jì)算計(jì)算gx對(duì)所有的對(duì)所有的x，最多計(jì)算，最多計(jì)算0 x p-

23、1 或或 1xp，因?yàn)閷?shí)際，因?yàn)閷?shí)際上離散對(duì)數(shù)上離散對(duì)數(shù)是循環(huán)群；是循環(huán)群； 驗(yàn)證驗(yàn)證a=gx mod p 是否成立。是否成立。dlog(g, a, p) / 當(dāng)這樣的對(duì)數(shù)不存在時(shí)，算法返回當(dāng)這樣的對(duì)數(shù)不存在時(shí)，算法返回p x 0; y 1; do x+; y y*g; / 計(jì)算計(jì)算y=gx while ( a y mod p) and (x p); return x2,7xlog3x32 mod7例無(wú)解，不存在使53l問(wèn)題：最壞問(wèn)題：最壞o(p)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時(shí)平均循環(huán)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿足一定條件時(shí)平均循環(huán)p/2次次當(dāng)當(dāng)p=24位十進(jìn)制數(shù)，循環(huán)位十進(jìn)制數(shù)，循環(huán)1024次

24、，千萬(wàn)億次次，千萬(wàn)億次/秒秒 (1016次次/秒秒) 大約算大約算1年年(108秒秒/年年)若若p是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無(wú)法在可行的時(shí)間內(nèi)求解。是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無(wú)法在可行的時(shí)間內(nèi)求解。l假設(shè)有一個(gè)平均時(shí)間性能很好，但最壞情況差的確定算法求假設(shè)有一個(gè)平均時(shí)間性能很好，但最壞情況差的確定算法求logg,pa，怎樣用怎樣用sherwood算法求解該問(wèn)題？算法求解該問(wèn)題？設(shè)設(shè)p=19, g=2 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 a=gimod19 2 4 8 16 13 7 14 9 18 17 15 11 3 6

25、 12 5 10 1 2當(dāng)當(dāng)a=14, 6時(shí)，時(shí)，log2,1914 = 7, log2,196=14，即用，即用dlog求求14和和6的離散的離散對(duì)數(shù)時(shí)，分別要循環(huán)對(duì)數(shù)時(shí)，分別要循環(huán)7和和14次，執(zhí)行時(shí)間次，執(zhí)行時(shí)間與與a的取值相關(guān)的取值相關(guān)。 用用sherwood算法應(yīng)該使得算法應(yīng)該使得與與a無(wú)關(guān)無(wú)關(guān)，用隨機(jī)預(yù)處理的方法計(jì)算，用隨機(jī)預(yù)處理的方法計(jì)算logg,pa例例2 2：離散對(duì)數(shù)計(jì)算：離散對(duì)數(shù)計(jì)算54l 定理定理(見(jiàn)見(jiàn)p877, 31.6) dlogrh(g, a, p) / 求求logg,pa, a = gx mod p，求，求x / sherwood算法算法 r uniform(0.

26、p-2); b modularexponent(g, r, p); /求冪模求冪模b=gr mod p c ba mod p; /(gr modp)(gxmodp)modp=gr+xmodp=c y logg,pc; / 使用確定性算法求使用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求求xex. 分析分析dlogrh的工作原理，指出該算法相應(yīng)的的工作原理，指出該算法相應(yīng)的u和和v3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp55l 隨機(jī)

27、預(yù)處理提供了一種加密計(jì)算的可能性隨機(jī)預(yù)處理提供了一種加密計(jì)算的可能性 假定你想計(jì)算某個(gè)實(shí)例假定你想計(jì)算某個(gè)實(shí)例x，通過(guò)，通過(guò)f(x)計(jì)算，但你缺乏計(jì)算，但你缺乏計(jì)算能力或是缺乏有效算法，而別人有相應(yīng)的計(jì)算能力，計(jì)算能力或是缺乏有效算法，而別人有相應(yīng)的計(jì)算能力，愿意為你計(jì)算愿意為你計(jì)算(可能會(huì)收費(fèi)可能會(huì)收費(fèi))，若你愿意別人幫你計(jì)算，若你愿意別人幫你計(jì)算，但你不愿意泄露你的輸入實(shí)例但你不愿意泄露你的輸入實(shí)例x，你將如何做？，你將如何做？可將隨機(jī)預(yù)處理使用到可將隨機(jī)預(yù)處理使用到f的計(jì)算上：的計(jì)算上： 使用函數(shù)使用函數(shù)u將將x加密為某一隨機(jī)實(shí)例加密為某一隨機(jī)實(shí)例y 將將y提交給提交給f計(jì)算出計(jì)算出f(

28、y)的值的值 使用函數(shù)使用函數(shù)v轉(zhuǎn)換為轉(zhuǎn)換為f(x) 上述過(guò)程，他人除了知道你的實(shí)例大小外，不知道上述過(guò)程，他人除了知道你的實(shí)例大小外，不知道x的任何信息，因?yàn)榈娜魏涡畔?，因?yàn)閡(x,r)的概率分布的概率分布(只要只要r是隨機(jī)均勻是隨機(jī)均勻選擇的選擇的)是獨(dú)立于是獨(dú)立于x的。的。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理56 設(shè)兩個(gè)數(shù)組設(shè)兩個(gè)數(shù)組val1.n和和ptr1.n及及head構(gòu)成一構(gòu)成一個(gè)有序的靜態(tài)鏈表：個(gè)有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：例：3.3 搜索有序表搜索有序表:ptri給個(gè)關(guān)鍵標(biāo)非關(guān)鍵即關(guān)鍵出出下下一一字

29、字的的下下if vali最if vali最大大字字0 if vali是0 if vali是最最大大字字 i 1 2 3 4 5 6 7vali 2 3 13 1 5 21 8ptri 2 5 6 1 7 0 3rank 2 3 6 1 4 7 5head=4 有序表：有序表：1，2，3，5，8，13，21 57n 折半查找：折半查找： 若若val1.n本身有序，可用折半查找找某本身有序，可用折半查找找某個(gè)給定的個(gè)給定的key，時(shí)間為，時(shí)間為o(lgn)。n 順序查找：順序查找：但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時(shí)間是但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時(shí)間是(n)(n)。盡管如此，我們能夠找到一個(gè)確定性算法，平均時(shí)

30、間盡管如此，我們能夠找到一個(gè)確定性算法，平均時(shí)間為為 。 相應(yīng)的相應(yīng)的sherwoodsherwood算法的期望時(shí)間是算法的期望時(shí)間是 ，它雖，它雖然并不比確定性算法快，但他消除了最壞實(shí)例。然并不比確定性算法快，但他消除了最壞實(shí)例。 假定表中元素互不相同，且所求的關(guān)鍵字在表中假定表中元素互不相同，且所求的關(guān)鍵字在表中存在，則給定存在，則給定x x，我們是求下標(biāo)，我們是求下標(biāo)i i，使，使vali=x, 這里這里1i n。任何實(shí)例可以由兩個(gè)參數(shù)刻畫：任何實(shí)例可以由兩個(gè)參數(shù)刻畫： 前前n n個(gè)整數(shù)的排列個(gè)整數(shù)的排列 x x的的rank3.3 搜索有序表搜索有序表()on()on58設(shè)設(shè)sn是所有是

31、所有n!個(gè)排列的集合，設(shè)個(gè)排列的集合，設(shè)a是一個(gè)確定性算法是一個(gè)確定性算法 ta(n, k, )表示算法表示算法a的執(zhí)行時(shí)間，此時(shí)間與被查的執(zhí)行時(shí)間，此時(shí)間與被查找元素的秩找元素的秩k，以及，以及val的排列的排列相關(guān)。若相關(guān)。若a a是一個(gè)概是一個(gè)概率算法，則率算法，則ta(n, k, )表示算法的期望值。無(wú)論算法表示算法的期望值。無(wú)論算法是確定的還是概率的，是確定的還是概率的，wa(n)和和ma(n)分別表示最壞分別表示最壞時(shí)間和平均時(shí)間，因此有：時(shí)間和平均時(shí)間，因此有： 3.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nanna

32、asknw nt n kkn andsm ntn kn nknnsn的概率是，在 中每個(gè)排列的概率是591. 時(shí)間為時(shí)間為o(n)的確定算法的確定算法n 算法算法設(shè)設(shè)xvali且且x在表中，則從位置在表中，則從位置i開(kāi)始查找開(kāi)始查找x的算法為的算法為search(x, i) /仍可改進(jìn)仍可改進(jìn)while x vali do i ptri;return i;在表在表val1.n中查找中查找x的算法為：的算法為：a(x) return search(x, head);3.3 搜索有序表搜索有序表60n 性能分析性能分析設(shè)設(shè)rank(x)=k, 則：則： 算法算法a在在n個(gè)元素的表中查找個(gè)元素的表中

33、查找x所需的訪問(wèn)數(shù)組所需的訪問(wèn)數(shù)組元素的次數(shù)，元素的次數(shù)，顯然與顯然與無(wú)關(guān)無(wú)關(guān) 算法算法a a最壞時(shí)的訪問(wèn)次數(shù)最壞時(shí)的訪問(wèn)次數(shù) 算法算法a a平均的訪問(wèn)次數(shù)平均的訪問(wèn)次數(shù) 3.3 搜索有序表搜索有序表( , )atn kw ( )anm ( )an1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )aanaaknnkn tn kknnknwnnnnknnmntn knt no n 若時(shí)為最壞情況，此時(shí)設(shè)的概率相等，則綜上所述，612.時(shí)間為時(shí)間為o(n)的概率算法的概率算法n算法算法 d(x) i uniform(1.n);y vali;case x y: retur

34、n search(x, ptri); / case2 otherwise: return i; / case3， x = y3.3 搜索有序表搜索有序表62n性能分析性能分析(d訪問(wèn)數(shù)組次數(shù)訪問(wèn)數(shù)組次數(shù)) 一般情況一般情況 設(shè)設(shè)rank(x)=k, rank(vali)=j 若若 k j, 則則 ，屬于，屬于case2，從，從jth最小元之后搜索最小元之后搜索若若 k = j, 則則 ，屬于，屬于case3 最壞情況最壞情況3.3 搜索有序表搜索有序表( , ) dtn kk( , )-dtn kkj( , )0dtn kddnn,w (n)?j 1,knsearchn-1w (n)n 1 當(dāng)

35、時(shí)，執(zhí)行次數(shù)為， 63 平均情況平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 djnnnnddjkjkkjnjnn mnjnknnmntn kkkjnnnj jnjnjnnnn及的概率均為顯然平均時(shí)間性能優(yōu)于確定算法643.平均時(shí)間為平均時(shí)間為 的確定算法的確定算法n算法算法b(x) /設(shè)設(shè)x在在val1.n中中i head;max vali; / max初值是表初值是表val中最小值中最小值for j 1 to do / 在在val的前的前 個(gè)數(shù)中找不大于個(gè)數(shù)中找不大于x y val j

36、 ; / 的最大整數(shù)的最大整數(shù)y相應(yīng)的下標(biāo)相應(yīng)的下標(biāo)i if max y x then i j; max y; /endif / endforreturn search(x, i); / 從從y開(kāi)始繼續(xù)搜索開(kāi)始繼續(xù)搜索3.3 搜索有序表搜索有序表()onnn65n性能分析性能分析 for循環(huán)的目的：找不超過(guò)循環(huán)的目的：找不超過(guò)x的最大整數(shù)的最大整數(shù)y，使搜索從，使搜索從y開(kāi)開(kāi)始，若將始，若將val1.n中的中的n個(gè)整數(shù)看作是均勻隨機(jī)分布的，則個(gè)整數(shù)看作是均勻隨機(jī)分布的，則在在val1.l l中求中求y值就相當(dāng)于在值就相當(dāng)于在n個(gè)整數(shù)中，隨機(jī)地取個(gè)整數(shù)中，隨機(jī)地取l l個(gè)整數(shù)，個(gè)整數(shù)，求這求這l

37、 l個(gè)整數(shù)中不大于個(gè)整數(shù)中不大于x的最大整數(shù)的最大整數(shù)y。 可用一個(gè)與可用一個(gè)與l l和和n相關(guān)的隨機(jī)變量來(lái)分析，更簡(jiǎn)單的分析相關(guān)的隨機(jī)變量來(lái)分析，更簡(jiǎn)單的分析如下：如下：設(shè)設(shè)n個(gè)整數(shù)的排列滿足：個(gè)整數(shù)的排列滿足：a1 a2 0，更，更好的情況是：好的情況是：ch.4 las vegas 算法算法0,( )p x常數(shù)70obstinate(x) repeatlv(x, y, success);until success;return y; 設(shè)設(shè)t(x)是算法是算法obstinate找到一個(gè)正確解的期望時(shí)間，則找到一個(gè)正確解的期望時(shí)間，則 若要最小化若要最小化t(x)，則需在，則需在p(x),

38、s(x)和和e(x)之間進(jìn)行某種折衷，之間進(jìn)行某種折衷，例如，若要減少失敗的時(shí)間，則可降低成功的概率例如，若要減少失敗的時(shí)間，則可降低成功的概率p(x)。ch.4 las vegas 算法算法( )( ) ( )(1( )( ( )( )lv1( )( )( )( )( )t xp x s xp xe xt xlvp xt xs xe xp x成功的概率失敗的概率711. 傳統(tǒng)的回溯法傳統(tǒng)的回溯法4.1 8后問(wèn)題后問(wèn)題12341234iji+j 135度度對(duì)對(duì)角角線線：同同一一條條對(duì)對(duì)角角線線上上的的元元素素的的行行列列號(hào)號(hào)之之和和相相等等 i-j或或j-i 45度度對(duì)對(duì)角角線線：同同一一條條

39、對(duì)對(duì)角角線線上上的的元元素素的的行行列列號(hào)號(hào)之之差差相相等等 72置當(dāng)前行為第置當(dāng)前行為第1行，當(dāng)前列為第行，當(dāng)前列為第1列，即列，即ij1;while i 8 do / 當(dāng)前行號(hào)當(dāng)前行號(hào)i 8檢查當(dāng)前行檢查當(dāng)前行i：從當(dāng)前列：從當(dāng)前列j起向后逐列試探，尋找安全列號(hào)；起向后逐列試探，尋找安全列號(hào)；if 找到安全列號(hào)找到安全列號(hào) then 放置皇后，將列號(hào)記入棧，并將下一行置為當(dāng)前行放置皇后，將列號(hào)記入棧，并將下一行置為當(dāng)前行(i+); j1; /當(dāng)前列置為當(dāng)前列置為1 else 退?；厮莸缴弦恍?，即退?；厮莸缴弦恍?，即i-； 移去該行已放置的皇后，以該皇后所在列的下一列作為當(dāng)移去該行已放置的皇

40、后，以該皇后所在列的下一列作為當(dāng) 前列；前列；4.1 8后問(wèn)題后問(wèn)題73734.1 8后問(wèn)題后問(wèn)題2.las vegas方法方法v向量向量try1.8中存放結(jié)果中存放結(jié)果tryi表示第表示第i個(gè)皇后放在（個(gè)皇后放在（i，tryi)位置上位置上vtry1.k稱為稱為k-promising是指：是指：若若k個(gè)皇后的位置個(gè)皇后的位置(0k 8): (1,try1), (2,try2), , (k,tryk)互相不攻擊，則稱互相不攻擊，則稱try1.k是是k-promising的的.形式化：對(duì)形式化：對(duì) ，若，若 有有 (式式1)若式若式1成立，則：成立，則： 無(wú)行沖突：無(wú)行沖突：無(wú)須考慮，因?yàn)榈跓o(wú)須

41、考慮，因?yàn)榈趇個(gè)皇后放在第個(gè)皇后放在第i行，故行，故同一行不會(huì)有兩皇后同一行不會(huì)有兩皇后,1, i jkijtryi-tryj i-j,0,j-i74744.1 8后問(wèn)題后問(wèn)題 無(wú)列沖突：無(wú)列沖突：若對(duì)任意不同的兩行若對(duì)任意不同的兩行i、j，因?yàn)槠淞袛?shù)，因?yàn)槠淞袛?shù)之差不為之差不為0，故任意兩皇后不可能在同一列上。，故任意兩皇后不可能在同一列上。 135對(duì)角線無(wú)沖突：對(duì)角線無(wú)沖突： 和和 沖突時(shí)有：沖突時(shí)有： 即即 故任兩皇后不會(huì)在故任兩皇后不會(huì)在135對(duì)角線上沖突。對(duì)角線上沖突。 45對(duì)角線無(wú)沖突：對(duì)角線無(wú)沖突： 和和 沖突時(shí)有：沖突時(shí)有：即即tryi-tryj=i-j故任兩皇后不會(huì)在故任兩皇

42、后不會(huì)在45對(duì)角線上沖突。對(duì)角線上沖突。綜上所述，式綜上所述，式1成立時(shí)成立時(shí)try1.k是是k-promising。顯然，若顯然，若k 1，則向量，則向量try1.k是是k-promising的，對(duì)的，對(duì)8后問(wèn)題，解是后問(wèn)題，解是8-promising的。的。v 算法算法, i try ia i try ijtry j , j try ja try itry jji, i try ia, j try ja i try ij try j 7575 queenslv (success) /貪心的貪心的lv算法，所有皇后都是隨機(jī)放置算法，所有皇后都是隨機(jī)放置/若若success=true，則，則t

43、ry1.8包含包含8后問(wèn)題的一個(gè)解。后問(wèn)題的一個(gè)解。 col,diag45,diag135；/列及兩對(duì)角線集合初值為空列及兩對(duì)角線集合初值為空 k 0；/行號(hào)行號(hào) repeat /try1.k是是k-promising，考慮放第，考慮放第k+1個(gè)皇后個(gè)皇后 nb 0；/計(jì)數(shù)器，計(jì)數(shù)器，nb值為（值為（k+1)th皇后的皇后的open位置總數(shù)位置總數(shù) for i 1 to 8 do /i是列號(hào)是列號(hào), 試探（試探（k+1,i）安全否）安全否？ if (i col) and (i-k-1 diag45) and (i+k+1 diag135) then /列列i對(duì)（對(duì)（k+1）th皇后可用，但不一

44、定馬上將其放在第皇后可用，但不一定馬上將其放在第i列列 nb nb+1； if uniform(1.nb)=1 then /或許放在第或許放在第i列列 j i；/注意第一次注意第一次uniform一定返回一定返回1，即，即j一定有值一定有值i /endif /endfor，在在nb個(gè)安全的位置上隨機(jī)選擇個(gè)安全的位置上隨機(jī)選擇1個(gè)位置個(gè)位置j放置之放置之76764.1 8后問(wèn)題后問(wèn)題if(nb 0) then /nb=0時(shí)無(wú)安全位置，第時(shí)無(wú)安全位置，第k+1個(gè)皇后尚未放好個(gè)皇后尚未放好/在所有在所有nb個(gè)安全位置上，個(gè)安全位置上，(k+1)th皇后選擇位置皇后選擇位置j的概率為的概率為1/nb

45、kk+1；/try1.k+1是是(k+1)-promising tryk j；/放置放置(k+1)th個(gè)皇后個(gè)皇后 col col j ； diag45 diag45 j-k ； diag135 diag135 j+k ； /endif until （nb=0）or（k=8）；）；/當(dāng)前皇后找不到合適的位置或當(dāng)前皇后找不到合適的位置或try是是 / 8-promising時(shí)結(jié)束。時(shí)結(jié)束。 success （nb0）；）；77774.1 8后問(wèn)題后問(wèn)題v 分析分析設(shè)設(shè)p是成功的概率（一次成功）是成功的概率（一次成功） s：成功時(shí)搜索的結(jié)點(diǎn)的平均數(shù)：成功時(shí)搜索的結(jié)點(diǎn)的平均數(shù)(1個(gè)皇后放好算是搜索樹(shù)

46、上的個(gè)皇后放好算是搜索樹(shù)上的1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)) e：失敗時(shí)搜索的結(jié)點(diǎn)的平均數(shù)。：失敗時(shí)搜索的結(jié)點(diǎn)的平均數(shù)。顯然顯然s=9（空向量（空向量try算在內(nèi)）算在內(nèi)）, p和和e理論上難于計(jì)算，但實(shí)驗(yàn)用計(jì)算機(jī)可以計(jì)算出：理論上難于計(jì)算，但實(shí)驗(yàn)用計(jì)算機(jī)可以計(jì)算出：p=0.1293e=6.971在重復(fù)上述算法，直至成功時(shí)在重復(fù)上述算法，直至成功時(shí)(相當(dāng)于相當(dāng)于obstinate的時(shí)間），所搜索的的時(shí)間），所搜索的平均結(jié)點(diǎn)數(shù)：平均結(jié)點(diǎn)數(shù)：大大優(yōu)于回溯法，回溯法約為大大優(yōu)于回溯法，回溯法約為114個(gè)結(jié)點(diǎn)才能求出一個(gè)解。個(gè)結(jié)點(diǎn)才能求出一個(gè)解。ex.證明：當(dāng)放置（證明：當(dāng)放置（k+1)th皇后時(shí)，若有多個(gè)位置是開(kāi)放

47、的皇后時(shí)，若有多個(gè)位置是開(kāi)放的,則算法則算法queenslv選中其中任一位置的概率相等。選中其中任一位置的概率相等。(1) /55.927.tsp e p 78784.1 8后問(wèn)題后問(wèn)題v 問(wèn)題及改進(jìn)問(wèn)題及改進(jìn) 消極：消極：lv算法過(guò)于消極，一旦失敗，從頭再來(lái)算法過(guò)于消極，一旦失敗，從頭再來(lái) 樂(lè)觀：樂(lè)觀：回溯法過(guò)于樂(lè)觀，一旦放置某個(gè)皇后失敗，就進(jìn)回溯法過(guò)于樂(lè)觀，一旦放置某個(gè)皇后失敗，就進(jìn)行系統(tǒng)回退一步的策略，而這一步往往不一定有效。行系統(tǒng)回退一步的策略，而這一步往往不一定有效。 折中：折中：會(huì)更好嗎？一般情況下為此。會(huì)更好嗎？一般情況下為此。先用先用lv方法隨機(jī)地放置前若干個(gè)結(jié)點(diǎn)，例如方法隨機(jī)

48、地放置前若干個(gè)結(jié)點(diǎn)，例如k個(gè)。個(gè)。然后使用回溯法放置后若干個(gè)結(jié)點(diǎn)，但不考慮重放前然后使用回溯法放置后若干個(gè)結(jié)點(diǎn)，但不考慮重放前k個(gè)結(jié)個(gè)結(jié)點(diǎn)。點(diǎn)。若前面的隨機(jī)選擇位置不好，可能使得后面的位置不成功，若前面的隨機(jī)選擇位置不好，可能使得后面的位置不成功，如若前兩個(gè)皇后的位置是如若前兩個(gè)皇后的位置是1、3。隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平均時(shí)間就越少，隨機(jī)放置的皇后越多，則后續(xù)回溯階段的平均時(shí)間就越少，失敗的概率也就越大。失敗的概率也就越大。79794.1 8后問(wèn)題后問(wèn)題改進(jìn)算法改進(jìn)算法 折中算法只需將折中算法只需將queenslv的最后兩行改為：的最后兩行改為：until nb = 0 or

49、k = stepvegas；if （nb0) then /已隨機(jī)放好已隨機(jī)放好stepvegas個(gè)皇后個(gè)皇后 backtrace (k, col, diag45, diag135,success);else success false；stepvegas控制隨機(jī)放置皇后的個(gè)數(shù)，如何選擇？控制隨機(jī)放置皇后的個(gè)數(shù)，如何選擇？ 改進(jìn)算法的試驗(yàn)結(jié)果：改進(jìn)算法的試驗(yàn)結(jié)果：8080純回溯時(shí)間：純回溯時(shí)間：40msstepvegas=2 or 3：10ms（平均）（平均）純貪心純貪心lv：23ms（平均）（平均）結(jié)論：一半略少的皇后隨機(jī)放置較好。結(jié)論：一半略少的皇后隨機(jī)放置較好。stepvegasstepv

50、egasp ps se et t0 01 11141141141141 11 139.6339.6339.6339.632 20.8750.87522.5322.5339.6739.6728.2028.203 30.49310.493113.4813.4815.1015.1029.0129.014 40.26180.261810.3110.318.798.7935.1035.105 50.16240.16249.339.337.297.2946.9246.926 60.13570.13579.059.056.986.9853.5053.507 70.12930.12939 96.976.975

51、5.9355.938 80.12930.12939 96.976.9753.9353.93搜索的平均節(jié)點(diǎn)數(shù)完全回溯完全隨機(jī)81814.1 8后問(wèn)題后問(wèn)題-問(wèn)題1：為什么僅隨機(jī)放一個(gè)皇后，其效果就會(huì)大大優(yōu)于純回溯方法？82824.1 8后問(wèn)題后問(wèn)題-問(wèn)題2：預(yù)先隨機(jī)選幾個(gè)皇后放置為好？由于解缺乏規(guī)律性（至少在皇后數(shù)不等于4k+2，k為某整數(shù)時(shí)），故求出stepvegas的最優(yōu)值較難，但是找到一個(gè)較好（不一定是最優(yōu)）的stepvegas還是可以的。12皇后：stepvegasstepvegasp ps se et t時(shí)間時(shí)間0 01 1262262262262125ms125ms5 50.5039

52、0.503933.8833.8847.2347.2380.3980.3937ms37ms12120.04650.0465131310.210.2222.11222.11基本與純回溯相同基本與純回溯相同83834.1 8后問(wèn)題后問(wèn)題在在apple ii機(jī)器上，機(jī)器上，20個(gè)皇后：個(gè)皇后： 確定性的回溯算法：找到第一個(gè)解的時(shí)間大于確定性的回溯算法：找到第一個(gè)解的時(shí)間大于2個(gè)個(gè)小時(shí)。小時(shí)。 概率算法，隨機(jī)地放置前概率算法，隨機(jī)地放置前10個(gè)皇后：個(gè)皇后：5分半鐘找到分半鐘找到36個(gè)不同的解。個(gè)不同的解。后者找一個(gè)解比前者大約快后者找一個(gè)解比前者大約快1000倍！倍！-obstinate算法在何時(shí)無(wú)限

53、循環(huán)？算法在何時(shí)無(wú)限循環(huán)？當(dāng)問(wèn)題不存在解時(shí)。當(dāng)問(wèn)題不存在解時(shí)。對(duì)于對(duì)于n皇后，要求皇后，要求n=4，即問(wèn)題至少有一個(gè)解存在時(shí)，即問(wèn)題至少有一個(gè)解存在時(shí)，obstinate算法才有可能結(jié)束。算法才有可能結(jié)束。ex. 寫一算法，求寫一算法，求n=1220時(shí)最優(yōu)的時(shí)最優(yōu)的stepvegas值。值。84844.2 模模p平方根平方根1.定義定義1：設(shè)設(shè)p是一個(gè)奇素?cái)?shù)，若整數(shù)是一個(gè)奇素?cái)?shù)，若整數(shù)x1,p-1且存且存在一個(gè)整數(shù)在一個(gè)整數(shù)y，使，使則稱則稱x為模為模p的二次剩余（的二次剩余（quadratic residue），），若若y 1,p-1，則，則y稱為稱為x模模p的平方根。的平方根。v例：例：6

54、3是是55模模103的平方根，的平方根，55是模是模103的二次剩余。的二次剩余。2.定義定義2：若整數(shù)若整數(shù) ，且，且z不是模不是模p的二次的二次剩余，則剩余，則z是模是模p的非二次剩余。的非二次剩余。2(mod)xyp55mod10355263 mod1033969mod1035525563 (mod103),1,1zp85854.2 模模p平方根平方根3.定理定理1：任何一個(gè)模任何一個(gè)模p的二次剩余至少有兩個(gè)不同的平方根的二次剩余至少有兩個(gè)不同的平方根pf：設(shè)設(shè)x是模是模p的二次剩余，的二次剩余，y是是x模模p的平方根。的平方根。因?yàn)橐驗(yàn)楣使手灰C只要證p-yy且且1p-yp-1就可證明

55、就可證明p-y是不同于是不同于y的的x模模p的的另一個(gè)平方根。另一個(gè)平方根。p是奇數(shù)，是奇數(shù)， p-yy，否則，否則p是偶數(shù)。是偶數(shù)。另一方面，另一方面， 1yp-1，p-y p (p-1)=1 /yp-1 p-yp-1 /y12222()2(mod )pyppyyyp2() (mod)xpyp86864.2 模模p平方根平方根4.定理定理2：任一模任一模p的二次剩余至多有兩個(gè)不同的平方根的二次剩余至多有兩個(gè)不同的平方根pf：設(shè)設(shè)a和和b是是x模模p的平方根。的平方根。即即 成立。成立。若若k=0，則，則a=b若若k0，則，則ab不妨設(shè)不妨設(shè)ab. p (a-b)又又 ，由由th31.7知知即

56、即 即即 ， 也就是說(shuō)任意兩個(gè)不同的平方根，均只有也就是說(shuō)任意兩個(gè)不同的平方根，均只有b和和(p-b)兩種不同形式。兩種不同形式。220(mod)abp22|()pab22abk p222212(mod) ,abpak pr bk pr1 a bp |()()pab ab|()p a b()a bkp()2abp1k abpapb87874.2 模模p平方根平方根5.定理定理3：1到到p-1之間的整數(shù)恰有一半是模之間的整數(shù)恰有一半是模p的二次剩余的二次剩余.pf：由定理由定理1和定理和定理2知，任一模知，任一模p的二次剩余恰有兩個(gè)不同的的二次剩余恰有兩個(gè)不同的平方根，即：任取二次剩余平方根，即

57、：任取二次剩余 ，只有，只有y和和p-y這兩個(gè)不這兩個(gè)不同的平方根同的平方根 在在1,p-1中恰有中恰有(p-1)/2對(duì)不同的平方根，每對(duì)平方根對(duì)應(yīng)的對(duì)不同的平方根，每對(duì)平方根對(duì)應(yīng)的模模p的余數(shù)的余數(shù)x必定在必定在1,p-1中，即此區(qū)間上恰有中，即此區(qū)間上恰有(p-1)/2個(gè)模個(gè)模p的的二次剩余。二次剩余。6.定理定理4：對(duì)對(duì) ，p是任一奇素?cái)?shù)，有是任一奇素?cái)?shù)，有且且x是模是模p的二次剩余當(dāng)且僅當(dāng)?shù)亩问Ｓ喈?dāng)且僅當(dāng)pf：略（可用費(fèi)馬定理）略（可用費(fèi)馬定理）1,1xp1,1xp (1)/21(mod )pxp1,1y pyp22() (mod)ypyp(1)/21(mod )pxp88884.2

58、 模模p平方根平方根7.如何判定如何判定x是否為模是否為模p的二次剩余？的二次剩余？只要利用定理只要利用定理4和計(jì)算方冪模和計(jì)算方冪模 即可。即可。8.已知已知p是奇素?cái)?shù)，是奇素?cái)?shù)，x是模是模p的二次剩余，如何計(jì)算的二次剩余，如何計(jì)算x模模p的兩個(gè)平方根？的兩個(gè)平方根？n 當(dāng)當(dāng) 時(shí)，兩平方根易求，分別是時(shí)，兩平方根易求，分別是n 當(dāng)當(dāng) 時(shí)，沒(méi)有有效的確定性算法，只時(shí)，沒(méi)有有效的確定性算法，只能借助于能借助于las vegas算法。算法。(1)/4px(1)/2modpxp3(mod4)p1(mod4)p 89894.2 模模p平方根平方根9. las vegas算法用用 表示表示x的兩個(gè)平方根

59、中較小的一個(gè)。的兩個(gè)平方根中較小的一個(gè)。n def：模：模p乘法（類似于復(fù)數(shù)乘法乘法（類似于復(fù)數(shù)乘法） a，b，c，d0,p-1x()()mod()mod()mod()mod )mod/see p.863,(31.18)ab x cdxpacbdxadbcxpacbdxpadbcpxp式90904.2 模模p平方根平方根v例：設(shè)例：設(shè)由定理由定理4可知，可知，7是模是模53的二次剩余，求的二次剩余，求7模模53的平方根。的平方根。當(dāng)省略模當(dāng)省略模53符號(hào)時(shí)，符號(hào)時(shí)， 計(jì)算過(guò)程如下：計(jì)算過(guò)程如下：531(mod4),7.7px求 的平方根2671(mod53) /26=(53-1)/226(17

60、) mod5323(17)(17)(17)82 7(17)(17)(82 7)2210 717(2210 7)(2210 7)1816 717(1816 7)(1816 7)4946 717(17)(4946 7)042 717(042 7)(042 7)520 76121326（）（）（）（）91914.2 模模p平方根平方根注： 上例中， ， 由定理4知， 是模53的非二次剩余。 同樣可知 亦是模53的非二次剩余。26(17)mod53(042 7)(042 7)mod5326(17)1(mod53) 1726(1)/2p17(42 42 7mod530 7)mod53(12348mod5