形式語言與自動機第一講

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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