1、東北師范大學(xué)計(jì)算機(jī)學(xué)院,課程介紹,授課類型Seminar & Lecture授課時(shí)間 (本學(xué)期) Per Weds 15:30-18:00? 考核方式 筆試+平時(shí)成績授課語言基本中文,東北師范大學(xué)計(jì)算機(jī)學(xué)院,Outline for this course,東北師范大學(xué)計(jì)算機(jī)學(xué)院,Outline today：,計(jì)算的意義?“算法”與“好的算法”NP完全性如何處理NP 完全問題新的計(jì)算

2、模型與希望,東北師范大學(xué)計(jì)算機(jī)學(xué)院,什么是可以計(jì)算的?什么是不可以 計(jì)算的?,算法的意義,東北師范大學(xué)計(jì)算機(jī)學(xué)院,例1：可滿足性（Satisfiability）問題,布爾變量集合布爾變量 和 稱為文字子句集合子句 是一些文字的析取（邏輯或）真值賦值給定U和C，是否存在滿足C的真值賦值？可滿足：C中所有的子句在 t 下為真計(jì)算復(fù)雜度：,,,,,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,例2：貨郎擔(dān)問題（Traveli

3、ng salesman problem),給定n個(gè)城市，任意兩個(gè)城市間有路相連，一個(gè)貨郎從一個(gè)城市出發(fā)，不重復(fù)的遍歷所有的城市并回到起點(diǎn)，求一條路程最短的路徑。加權(quán)完全圖　　　　， ， 　　　 ，求Hamilton圈　，使得計(jì)算復(fù)雜度：,,,,,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,指數(shù)災(zāi)難：計(jì)算量的指數(shù)增長,東北師范大學(xué)計(jì)算機(jī)學(xué)院,指數(shù)災(zāi)難能否避免？,SAT問題，貨郎擔(dān)問題，背包問題，圖著色問題，最長路徑問題，……是否對

4、于每個(gè)問題都有好的算法？什么是好的算法？什么是算法？,東北師范大學(xué)計(jì)算機(jī)學(xué)院,算法的定義,為實(shí)現(xiàn)某個(gè)任務(wù)而構(gòu)成的簡單指令集有窮的計(jì)算良過程通過有限多次運(yùn)算可以決定的過程,正確,直觀，非形式,東北師范大學(xué)計(jì)算機(jī)學(xué)院,算法的定義,希爾伯特第十問題（1900）設(shè)計(jì)一個(gè)算法來判斷多項(xiàng)式是否有整數(shù)根算法：通過有限多次運(yùn)算可以決定的過程Alan Turing & Alonzo Church（1936） 圖靈機(jī)程序算法：

5、圖靈機(jī)程序形式化的，精確的,東北師范大學(xué)計(jì)算機(jī)學(xué)院,圖靈機(jī)（Turing Machine),帶子可讀可寫無限長的帶子讀寫頭可左移右移,東北師范大學(xué)計(jì)算機(jī)學(xué)院,東北師范大學(xué)計(jì)算機(jī)學(xué)院,圖靈機(jī)（Turing Machine),TM運(yùn)行由 確定:當(dāng)前狀態(tài)為q，所讀字符為s ，讀寫頭不變， ， ，讀寫頭左移一格，s不

6、變， ，讀寫頭右移一格，s不變， 無定義，則停機(jī)Church-Turing論題：凡是可計(jì)算的過程都可用圖靈機(jī)實(shí)現(xiàn)；,,,,,,,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,其他圖靈機(jī)模型,“實(shí)際的”的圖靈機(jī)模型單帶圖靈機(jī)（1TM）多帶圖靈機(jī)（kTM）隨機(jī)存取機(jī)（RAM）“實(shí)際的”單位時(shí)間內(nèi)完成的工作量有一個(gè)多項(xiàng)式上界所有“實(shí)際的”計(jì)算模型多項(xiàng)式時(shí)間等價(jià),東北師范大學(xué)計(jì)

7、算機(jī)學(xué)院,好的算法——多項(xiàng)式時(shí)間算法,算法的時(shí)間復(fù)雜度指數(shù)時(shí)間多項(xiàng)式時(shí)間為什么是多項(xiàng)式而不是其他函數(shù)？常見的組合算法大致可分以上兩類與計(jì)算模型無關(guān)性,東北師范大學(xué)計(jì)算機(jī)學(xué)院,什么是算法？什么是好的算法？是否對于每個(gè)問題都有好的算法？,,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,P類（Polynomial),判定問題：只有肯定和否定兩種答案優(yōu)化問題可以化作判定問題處理P類具有多項(xiàng)式時(shí)間算法的判定問題形成的計(jì)算復(fù)雜性類猜測TSP

8、（Traveling salesman problem)不屬于P（J.Edmonds 1965）,東北師范大學(xué)計(jì)算機(jī)學(xué)院,非確定型算法,不現(xiàn)實(shí)的計(jì)算現(xiàn)實(shí)中的計(jì)算方式都是確定的解SAT問題的一個(gè)非確定型算法第一步：猜測一個(gè)變量的真值賦值；第二步：檢查該賦值是否滿足非確定型算法的計(jì)算時(shí)間：各種可能的計(jì)算過程的最短時(shí)間,東北師范大學(xué)計(jì)算機(jī)學(xué)院,非確定型圖靈機(jī)（NTM),猜想階段驗(yàn)證階段,猜想模塊,東北師范大學(xué)計(jì)算機(jī)學(xué)院,NTM

9、計(jì)算樹,,計(jì)算過程：從根到葉節(jié)點(diǎn)的路徑,東北師范大學(xué)計(jì)算機(jī)學(xué)院,東北師范大學(xué)計(jì)算機(jī)學(xué)院,NP類(Nondeterministic Polynomial ),NP問題：在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可驗(yàn)證的問題P類包含于NP類中NP類問題在確定圖靈機(jī)上指數(shù)時(shí)間可解非確定型圖靈機(jī)和確定型圖靈機(jī)的計(jì)算能力相當(dāng),東北師范大學(xué)計(jì)算機(jī)學(xué)院,計(jì)算難度比較的標(biāo)準(zhǔn),難易是比較而言的多項(xiàng)式時(shí)間歸約（Karp歸約

10、 1972)定義問題A多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問題B的特殊情況，則稱A可多項(xiàng)式歸約于B，記為轉(zhuǎn)化時(shí)間為多項(xiàng)式對于A的輸入I 的回答與其對應(yīng)的B的輸入 f(I) 一致,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,NP完全與NP-hard,NP完全問題：NP-hard問題：,,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,NP完全問題,第一個(gè)NP完全問題（Cook定理 1971）可滿足性問題是NP完全問題六個(gè)NP完全問題（Karp 1972)3SAT，3DM，V

11、C，團(tuán)，HC，劃分更多的NP完全問題1979年：300多個(gè)1998年：2000多個(gè),東北師范大學(xué)計(jì)算機(jī)學(xué)院,現(xiàn)在的估計(jì),如果 ，則指數(shù)災(zāi)難無法避免,P=?NP （P-NP問題）,P=NP,東北師范大學(xué)計(jì)算機(jī)學(xué)院,如何處理NP完全問題,實(shí)際的問題不會(huì)消失,油井勘探問題移動(dòng)通訊中的頻率分配問題,東北師范大學(xué)計(jì)算機(jī)學(xué)院,并行計(jì)算,以硬件設(shè)備換取時(shí)間存在著很多種并行計(jì)算模型理想模型PRAM可多項(xiàng)式時(shí)間解N

12、P完全問題實(shí)際中效果不好處理器數(shù)目是受限的現(xiàn)實(shí)的代價(jià)：通訊，同步，……分布式計(jì)算,東北師范大學(xué)計(jì)算機(jī)學(xué)院,算法的研究,隨機(jī)算法判定問題：以較大概率得到正確輸出輸出正確，但計(jì)算時(shí)間不定優(yōu)化問題：輸出解的性能不穩(wěn)定以較大概率得到性能好的解,東北師范大學(xué)計(jì)算機(jī)學(xué)院,算法的研究,完全算法利用某些策略減少計(jì)算量分支界限法（Branch and Bound）最壞情況時(shí)間復(fù)雜度是指數(shù)的近似算法不要最優(yōu)，只求較優(yōu)時(shí)間復(fù)雜度

13、較低,東北師范大學(xué)計(jì)算機(jī)學(xué)院,算法的研究,近似算法局部搜索遺傳算法模擬退火,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,TSP問題實(shí)驗(yàn)結(jié)果（實(shí)驗(yàn)環(huán)境：PII450雙CPU，256M內(nèi)存, Turbo Linux 4.0 ）,東北師范大學(xué)計(jì)算機(jī)學(xué)院,新的計(jì)算模型,生物計(jì)算DNA計(jì)算機(jī)量子計(jì)算量子計(jì)算機(jī),東北師范大學(xué)計(jì)算機(jī)學(xué)院,DNA計(jì)算,實(shí)驗(yàn)處理了7城市Hamilton路徑問題 L. Adleman 1994 可以多項(xiàng)式時(shí)間解所有的NP

14、問題Lipton R J 1995實(shí)驗(yàn)可以建立一個(gè)非確定型圖靈機(jī)Smith W, Schweitzer A. 1995,東北師范大學(xué)計(jì)算機(jī)學(xué)院,DNA計(jì)算的困難,操作的復(fù)雜性單元操作的時(shí)間代價(jià)高規(guī)模的限制處理的問題規(guī)模較小輸入輸出糾錯(cuò)的問題,東北師范大學(xué)計(jì)算機(jī)學(xué)院,量子計(jì)算,量子計(jì)算思想的提出Richard Feynman 1982量子圖靈機(jī)模型David Deutsch 1985Shor算法（Peter

15、 Shor 1994）多項(xiàng)式時(shí)間分解大數(shù)質(zhì)因子Grover 算法（Grover L. K. 1996）無序數(shù)據(jù)庫的搜索：,,,東北師范大學(xué)計(jì)算機(jī)學(xué)院,量子計(jì)算的困難,操作的復(fù)雜性單元操作的時(shí)間代價(jià)高規(guī)模的限制測量輸出糾錯(cuò)的問題,東北師范大學(xué)計(jì)算機(jī)學(xué)院,行之有效的方法：算法研究,東北師范大學(xué)計(jì)算機(jī)學(xué)院,推薦閱讀,計(jì)算機(jī)和難解性：NP完全性理論導(dǎo)引（Michael R. Garey&David S. Johnson