密碼學(xué)的計算復(fù)雜性理論課件

密碼學(xué)的計算復(fù)雜性理論幽默來自智慧，惡語來自無能密碼學(xué)的計算復(fù)雜性理論幽默來自智慧，惡語來自無能1口密碼學(xué)的計算復(fù)雜性理論口密碼學(xué)的計算復(fù)雜性理論2算法與算法復(fù)雜性口算法:求解某個問題的一系列具體步驟,可能一個問題有多種算法理解為求解該問題的計算機(jī)程序)?？诳山馀c不可解:如果一個算法能解決該問題的所有實例,則稱該算法能解答該問題。如果針對一個問題至少存在個算法可以解答該問題,則稱該問題是可解的。否則稱為該問題是不可解的。算法與算法復(fù)雜性3口算法的復(fù)雜性個算法的復(fù)雜性是由該算法所需要的最大運算時間和存儲空間來度量的。它們分別是規(guī)模為n(輸入數(shù)據(jù)的長度)的所有實例的時間和空間需求的平均值的函數(shù)7(n)和S(n)個算法的復(fù)雜性通常用符號“O”表示量級。好處在于它與處理系統(tǒng)無關(guān)(如:處理機(jī)速度、數(shù)據(jù)類型及表示)。f(m)=O(g(n)表示存在常數(shù)c和n,對所有n≥nf(n)≤cl(m)則稱函數(shù)f(m)當(dāng)n充分大時上有界,且g(是它的一個上界,記為f(n)=0(g(n))。即f(m)的階不高于g(n)的階。口算法的復(fù)雜性4口算法按復(fù)雜性分類多項式時間算法時間復(fù)雜性為O(n),k為常數(shù)。指數(shù)時間算法時間復(fù)雜性為O(),t為常數(shù),h(n)是多項式。當(dāng)h(n)大于常數(shù)小于線性函數(shù)時,稱為超多項式時間算法口算法按復(fù)雜性分類5例如:Hanoi塔問題算法的時間復(fù)雜度,可以用一個指數(shù)函數(shù)O(2)來表示,顯然,當(dāng)n很大(如10000時,計算機(jī)是無法處理的。相反,當(dāng)算法的時間復(fù)雜度的表示函數(shù)是一個多項式,如O(n2)時,則可以處理。因此,一個問題求解算法的時間復(fù)雜度大于多項式(如指數(shù)函數(shù))時,算法的執(zhí)行時間將隨n的增加而急劇增長,以致即使是中等規(guī)模的問題也不能求解出來,于是在計算復(fù)雜性中,將這一類問題稱為難解性問題。人工智能領(lǐng)域中的狀態(tài)圖搜索問題(解空間的表示或狀態(tài)空間搜索問題)就是一類典型的難解性問題。64個盤子例如:Hanoi塔問題算法的時間復(fù)雜度,可以用一個指數(shù)函數(shù)6NP問題與計算復(fù)雜性理論理自機(jī)←—m計算機(jī),并明究模型的性質(zhì)一論就的性可單現(xiàn)想計算機(jī)中,研究什論算mn可解的問題在實際計算機(jī)上理復(fù)么計算的資源消耗情況并根據(jù)一~論雜消耗情況對問題進(jìn)行分類性NP問題與計算復(fù)雜性理論7口圖靈機(jī)模型讀寫頭狀態(tài)控制器圖靈在1936年提出了著名的圖靈機(jī)模型(計算模型):n圖靈機(jī)由一個無限長的帶子(被劃分成均勻的方格)、一個磁帶讀/寫頭和一個有限狀態(tài)控制器組成。在每一步計算中,圖靈機(jī)從磁帶上讀出一個符號,并由有限狀態(tài)控制器決定是否在當(dāng)前的磁帶區(qū)上寫入不同的符號,然后決定是否需要將磁帶讀/寫頭向前或向后移動一位。當(dāng)前的計算機(jī),在理論上都是可以被圖靈機(jī)模擬的,其原理和圖靈機(jī)是相同的,甚至還包含了存儲程序的思想口圖靈機(jī)模型8口確定的圖靈機(jī):有無限讀寫能力的有限自動機(jī),每一步操作的結(jié)果唯一確定口非確定的圖靈機(jī):有無限讀寫能力的有限自動機(jī),每一步操作的結(jié)果有多種選擇口易解問題與難解問題:在確定圖靈機(jī)上用多項式時間可解的問題,稱為全體易解問題集合記為P。否則,稱為難解問題。在計算復(fù)雜性理論中,將所有可以在多項式時間內(nèi)求解的問題稱為P問題,而將所有在多項式時間內(nèi)可以驗證的問題稱為NP問題。由于P類問題采用的是確定性算法,NP類問題釆用的是非確定性算法,而確定性算法是非確定性算法的一種特例,因此,可以斷定PcNP?？诖_定的圖靈機(jī):有無限讀寫能力的有限自動機(jī),每9或者說:在非確定的圖靈機(jī)上用多項式時間可解的問題,稱為非確定型多項式時間可解問題,即NP問題。其含義是若機(jī)器猜測一個解,非確定的圖靈機(jī)就可以在多項式時間內(nèi)驗證它的正確性。(即:可以在多項式時間內(nèi)驗證某個解是否合法的問題)全體非確定型多項式時間可解類記作NP類。NP難問題:如果對于某個問題X,任意NP問題Y,可以在多項式時間內(nèi)轉(zhuǎn)換為(歸約)到ⅹ。通俗地講X至少和Y一樣難,則稱X是NP難的問題?；蛘哒f:10從前,有一個酷愛數(shù)學(xué)的年輕國王向鄰國一位聰明美麗的公主求婚。公主出了這樣一道題:求出48770428433377171的一個真因子。若國王能在一天之內(nèi)求出答案,公主便接受他的求婚。國王回去后立即開始逐個數(shù)地進(jìn)行計算,他從早到晩,共算了三萬多個數(shù),最終還是沒有結(jié)果。國王向公主求情,公主將答案相告:223092827是它的一個真因子。國王很快就驗證了這個數(shù)確能除盡48770428433377171。公主說:“我再給你一次機(jī)會,如果還求不出,將來你只好做我的證婚人了?！眹趿⒓椿貒?并向時任宰相的大數(shù)學(xué)家求教,大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個數(shù)為17位,則最小的一個真因子不會超過9位,于是他給國王出了一個主意:按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去,等公主給出數(shù)目后,立即將它們通報全國,讓每個老百姓用自己的編號去除這個數(shù),除盡了立即上報,賞金萬兩。最后,國王用這個辦法求婚成功。返回從前,有一個酷愛數(shù)學(xué)的年輕國王向鄰國一位聰明美麗11密碼學(xué)的計算復(fù)雜性理論課件12密碼學(xué)的計算復(fù)雜性理論課件13密碼學(xué)的計算復(fù)雜性理論課件14密碼學(xué)的計算復(fù)雜性理論課件15密碼學(xué)的計算復(fù)雜性理論課件16密碼學(xué)的計算復(fù)雜性理論課件17密碼學(xué)的計算復(fù)雜性理論課件18密碼學(xué)的計算復(fù)雜性理論課件19密碼學(xué)的計算復(fù)雜性理論課件20密碼學(xué)的計算復(fù)雜性理論課件21密碼學(xué)的計算復(fù)雜性理論課件22密碼學(xué)的計算復(fù)雜性理論課件23密碼學(xué)的計算復(fù)雜性理論課件24密碼學(xué)的計算復(fù)雜性理論課件25密碼學(xué)的計算復(fù)雜性理論課件26密碼學(xué)的計算復(fù)雜性理論課件27密碼學(xué)的計算復(fù)雜性理論課件28密碼學(xué)的計算復(fù)雜性理論課件29密碼學(xué)的計算復(fù)雜性理論課件30密碼學(xué)的計算復(fù)雜性理論課件31密碼學(xué)的計算復(fù)雜性理論課件32密碼學(xué)的計算復(fù)雜性理論課件33密碼學(xué)的計算復(fù)雜性理論課件34密碼學(xué)的計算復(fù)雜性理論課件35密碼學(xué)的計算復(fù)雜性理論課件36密碼學(xué)的計算復(fù)雜性理論課件3731、只有永遠(yuǎn)躺在泥坑里的人，才不會再掉進(jìn)坑里?！诟駹?/p>

32、希望的燈一旦熄滅，生活剎那間