形式語言與自動(dòng)機(jī)第一講東北師范大學(xué)計(jì)算機(jī)學(xué)院第一頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院課程介紹授課類型 Seminar&Lecture授課時(shí)間(本學(xué)期) PerWeds15:30-18:00?考核方式 筆試+平時(shí)成績(jī)授課語言 基本中文第二頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院Outlineforthiscourse抽象模型變種對(duì)應(yīng)語言相當(dāng)于程序或算法備注自動(dòng)機(jī)不確定NFA正則語言3型If,case,goto,無變量（內(nèi)存）無數(shù)組下推機(jī)不確定下推機(jī)前后文無關(guān)語言，2型增加：堆棧。仍無變量（內(nèi)存）無數(shù)組不確定線性界限下推機(jī)前后文有關(guān)語言1型語言一定停機(jī)的圖靈機(jī)XXX的圖靈機(jī)多帶,隨機(jī)，有界遞歸語言族增加數(shù)組，變量，內(nèi)存保證了不會(huì)死循環(huán)圖靈機(jī)0型，遞歸可枚舉輸入在語言外時(shí)，可能死循環(huán)，數(shù)學(xué)模型，簡(jiǎn)潔，易分析不要程序細(xì)節(jié)，易于分析本質(zhì)第三頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院Outlinetoday：計(jì)算的意義?“算法”與“好的算法”NP完全性如何處理NP完全問題新的計(jì)算模型與希望第四頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院什么是可以計(jì)算的?什么是不可以計(jì)算的?算法的意義第五頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院例1：可滿足性（Satisfiability）問題布爾變量集合布爾變量和稱為文字子句集合子句是一些文字的析?。ㄟ壿嫽颍┱嬷蒂x值給定U和C，是否存在滿足C的真值賦值？可滿足：C中所有的子句在t下為真計(jì)算復(fù)雜度：第六頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院例2：貨郎擔(dān)問題

（Travelingsalesmanproblem)給定n個(gè)城市，任意兩個(gè)城市間有路相連，一個(gè)貨郎從一個(gè)城市出發(fā)，不重復(fù)的遍歷所有的城市并回到起點(diǎn)，求一條路程最短的路徑。加權(quán)完全圖，，，求Hamilton圈

，使得計(jì)算復(fù)雜度：第七頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院指數(shù)災(zāi)難：計(jì)算量的指數(shù)增長(zhǎng)第八頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院指數(shù)災(zāi)難能否避免？SAT問題，貨郎擔(dān)問題，背包問題，圖著色問題，最長(zhǎng)路徑問題，……是否對(duì)于每個(gè)問題都有好的算法？什么是好的算法？什么是算法？第九頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院算法的定義為實(shí)現(xiàn)某個(gè)任務(wù)而構(gòu)成的簡(jiǎn)單指令集有窮的計(jì)算良過程通過有限多次運(yùn)算可以決定的過程正確直觀，非形式第十頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院算法的定義希爾伯特第十問題（1900）設(shè)計(jì)一個(gè)算法來判斷多項(xiàng)式是否有整數(shù)根算法：通過有限多次運(yùn)算可以決定的過程AlanTuring&AlonzoChurch（1936）圖靈機(jī)程序算法：圖靈機(jī)程序形式化的，精確的第十一頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院圖靈機(jī)（TuringMachine)帶子可讀可寫無限長(zhǎng)的帶子讀寫頭可左移右移有限狀態(tài)控制器1111110000000BBB1…………第十二頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院第十三頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院圖靈機(jī)（TuringMachine)TM運(yùn)行由確定:當(dāng)前狀態(tài)為q，所讀字符為s，讀寫頭不變，，，讀寫頭左移一格，s不變，，讀寫頭右移一格，s不變，無定義，則停機(jī)Church-Turing論題：凡是可計(jì)算的過程都可用圖靈機(jī)實(shí)現(xiàn)；第十四頁，共四十一頁，2022年，8月28日東北師范大學(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à)第十五頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院好的算法——多項(xiàng)式時(shí)間算法算法的時(shí)間復(fù)雜度指數(shù)時(shí)間多項(xiàng)式時(shí)間為什么是多項(xiàng)式而不是其他函數(shù)？常見的組合算法大致可分以上兩類與計(jì)算模型無關(guān)性第十六頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院什么是算法？什么是好的算法？是否對(duì)于每個(gè)問題都有好的算法？第十七頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院P類 （Polynomial) 判定問題：只有肯定和否定兩種答案優(yōu)化問題可以化作判定問題處理P類具有多項(xiàng)式時(shí)間算法的判定問題形成的計(jì)算復(fù)雜性類猜測(cè)TSP（Travelingsalesmanproblem)不屬于P（J.Edmonds1965）第十八頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院非確定型算法不現(xiàn)實(shí)的計(jì)算現(xiàn)實(shí)中的計(jì)算方式都是確定的解SAT問題的一個(gè)非確定型算法第一步：猜測(cè)一個(gè)變量的真值賦值；第二步：檢查該賦值是否滿足非確定型算法的計(jì)算時(shí)間：各種可能的計(jì)算過程的最短時(shí)間第十九頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院非確定型圖靈機(jī)（NTM)猜想階段驗(yàn)證階段有限狀態(tài)控制器1111110000000BBB1…………猜想模塊第二十頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院NTM計(jì)算樹計(jì)算過程：從根到葉節(jié)點(diǎn)的路徑第二十一頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院第二十二頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院NP類(NondeterministicPolynomial)NP問題：在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可驗(yàn)證的問題P類包含于NP類中NP類問題在確定圖靈機(jī)上指數(shù)時(shí)間可解非確定型圖靈機(jī)和確定型圖靈機(jī)的計(jì)算能力相當(dāng)?shù)诙摚菜氖豁摚?022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院計(jì)算難度比較的標(biāo)準(zhǔn)難易是比較而言的多項(xiàng)式時(shí)間歸約（Karp歸約1972)定義問題A多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問題B的特殊情況，則稱A可多項(xiàng)式歸約于B，記為轉(zhuǎn)化時(shí)間為多項(xiàng)式對(duì)于A的輸入I的回答與其對(duì)應(yīng)的B的輸入f(I)一致第二十四頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院NP完全與NP-hardNP完全問題：NP-hard問題：第二十五頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院NP完全問題第一個(gè)NP完全問題（Cook定理1971）可滿足性問題是NP完全問題六個(gè)NP完全問題（Karp1972)3SAT，3DM，VC，團(tuán)，HC，劃分更多的NP完全問題1979年：300多個(gè)1998年：2000多個(gè)第二十六頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院現(xiàn)在的估計(jì)如果，則指數(shù)災(zāi)難無法避免P=?NP（P-NP問題）P=NPPNPCNP第二十七頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院如何處理NP完全問題實(shí)際的問題不會(huì)消失油井勘探問題移動(dòng)通訊中的頻率分配問題第二十八頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院并行計(jì)算以硬件設(shè)備換取時(shí)間存在著很多種并行計(jì)算模型理想模型PRAM可多項(xiàng)式時(shí)間解NP完全問題實(shí)際中效果不好處理器數(shù)目是受限的現(xiàn)實(shí)的代價(jià)：通訊，同步，……分布式計(jì)算第二十九頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院算法的研究隨機(jī)算法判定問題：以較大概率得到正確輸出輸出正確，但計(jì)算時(shí)間不定優(yōu)化問題：輸出解的性能不穩(wěn)定以較大概率得到性能好的解第三十頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院算法的研究完全算法利用某些策略減少計(jì)算量分支界限法（BranchandBound）最壞情況時(shí)間復(fù)雜度是指數(shù)的近似算法不要最優(yōu)，只求較優(yōu)時(shí)間復(fù)雜度較低第三十一頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院算法的研究近似算法局部搜索遺傳算法模擬退火

第三十二頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院TSP問題實(shí)驗(yàn)結(jié)果

（實(shí)驗(yàn)環(huán)境：PII450雙CPU，256M內(nèi)存,TurboLinux4.0）InstanceEAX-h+ILKPattern1名稱Pcb442507782050778(0)57.0(0.005)2050778(0)13.11(0.10)Att532276862027686(0)36.14(0.01)2027686(0)51.52(0.026)Rat7838806208806(0)26.66(0.01)208806(0)46.32(0.019)Fl1577222492022249(0)589.1(0.95)2022249(0)97.4(0.035)Pr23923780320378161(0)624.6(0.94)0378224(0)642.0(1.65)Fl379528772028783(0)1488.2(5.2)028788(0)1103.4(14.3)第三十三頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院新的計(jì)算模型生物計(jì)算DNA計(jì)算機(jī)量子計(jì)算量子計(jì)算機(jī)第三十四頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院DNA計(jì)算實(shí)驗(yàn)處理了7城市Hamilton路徑問題

L.Adleman1994可以多項(xiàng)式時(shí)間解所有的NP問題LiptonRJ1995實(shí)驗(yàn)可以建立一個(gè)非確定型圖靈機(jī)SmithW,SchweitzerA.1995第三十五頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院DNA計(jì)算的困難操作的復(fù)雜性單元操作的時(shí)間代價(jià)高規(guī)模的限制處理的問題規(guī)模較小輸入輸出糾錯(cuò)的問題第三十六頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院量子計(jì)算量子計(jì)算思想的提出RichardFeynman1982量子圖靈機(jī)模型DavidDeutsch1985Shor算法（PeterShor1994）多項(xiàng)式時(shí)間分解大數(shù)質(zhì)因子Grover算法（GroverL.K.1996）無序數(shù)據(jù)庫的搜索：第三十七頁，共四十一頁，2022年，8月28日東北師范大學(xué)計(jì)算機(jī)學(xué)院量子計(jì)算的困難操作的復(fù)雜性單元操作的時(shí)間代價(jià)高規(guī)模的限制測(cè)量輸出糾錯(cuò)的問題第三十八頁，共四十一頁，2022年，