計(jì)算機(jī)問題求解-算法在計(jì)算機(jī)科學(xué)中的地位

1、計(jì)算機(jī)問題求解 – 論題4-11 - 串匹配,2017年5月3日,檢查,模式P在文本T中以偏移3、11、35有效出現(xiàn)，是什么意思？如果我們說，一個(gè)有限自動(dòng)機(jī)M接受字符串w。這是什么意思？,問題1:什么是 string-matching problem, 直觀上? 形式上?,,最容易想到的算法,問題2:為什么稱它為“naïve”算法？,問題3：為什么在最壞情況下復(fù)雜度是平方級(jí)的？,,問題4：你能否說說na&

2、#239;ve算法有什么問題，為什么有可能改進(jìn)？,最容易想到的算法,逐位單字符比較,,問題5：Rabin-Karp算法的基本思想是什么？,,Preprocessing,問題6:Rabin-Karp算法是采用“預(yù)處理”方式的算法？何為“預(yù)處理”，這個(gè)算法預(yù)處理的結(jié)果是什么？,Matching,問題7：Rabin-Karp算法在“匹配”時(shí)拿什么與什么匹配？,這樣有什么問題？是如何解決的？,問題8:對T中每個(gè)長度為m的子串在匹配前都必

3、須計(jì)算它的“值”，這個(gè)計(jì)算是如何被“簡化”的？,遞推的方法,問題9：影響復(fù)雜度的關(guān)鍵是什么？,,問題10：這是書上開始介紹Rabin-Karp算法時(shí)的第一段話，現(xiàn)在你能解釋一下了嗎？,,有限狀態(tài)機(jī),問題11:你能將有限自動(dòng)機(jī)與字符串的識(shí)別聯(lián)系起來嗎?,欲匹配的pattern一定是可接受的“語句”的后綴！,Whenever its current state q is a member of A, the machine M has

4、 accepted the string read so far. An input that is not accepted is rejected.,,待匹配的pattern,問題12：你能否看出構(gòu)建自動(dòng)機(jī)的關(guān)鍵在哪里？,問題13：這個(gè)函數(shù)的“價(jià)值”在何處？,告訴我們“退”到那里。,,,如何構(gòu)建自動(dòng)機(jī),,問題14：?(Pqa)究竟怎么確定？,,后綴函數(shù)遞歸引理,問題15：你能解釋右邊的圖嗎？,確定?(Pqa)與x無關(guān)，即與T

5、無關(guān)。,可能需要代價(jià)m,問題16：能不能不計(jì)算轉(zhuǎn)換函數(shù)？,KMP算法的基本思想,很顯然，在我們只比較了5個(gè)字符，掌握了這些信息的基礎(chǔ)上：,偏移量s+1是必定是無效的！Why？,我們有沒有辦法確定哪個(gè)s’偏移量可能是有效偏移？,為什么要問這個(gè)問題？,找到那個(gè)計(jì)算最小的s’的線索,我們真正找的是P[1..k]在文本P[1..q]中的線索,s’ = s+(q-k),,,,,,,,模式的前綴函數(shù),,,,,KMP算法,KMP VS 有限狀態(tài)機(jī),