Chap11. String Matching

Pattern matching algorithms

3. Boyer-Moore algorithm

The Boyer-Moore Algorithm

Algorithm BoyerMooreMatch(T, P, sigma)
	L <- lastOccurenceFunction(P, sigma)	// O(m+s) time
	i <- m - 1		// index of T
	j <- m - 1		// index of P
	repeat 
		if T[i] = P[j]	// match, Looking-glass heuristic
			if j = 0
				return i { match at i }
			else
				i <- i - 1
				j <- j - 1
		else		// mismatch, character-jump heuristic
			{ character-jump }	// Last-Occurence Function
			l <- L[T[i]]		// bad-character이 발생하는 위치
			i <- i + m – min(j, 1 + l)	// case1, case2의 minimum
			j <- m - 1		// j는 마지막 인덱스로 업데이트
	until i > n - 1
	return -1 { no match }

Case 1:bad-文字が同じか右側に表示されます.
1グリッドを右に移動(brute-forceのように)
ex) |m-j|=6-4=2

Case 2:bad-文字左側で発生
シフトaを整列させる
ex) |m-(l+1)|=6-(1+1)=4

Example

基本演算回数:13回
*KMPアルゴリズムにおけるBasic Operation演算回数:19回
KMPはBoyer‐Mooreのアルゴリズムよりも複雑である.
実際の実行時間Boyer-Mooreの方が高速

Analysis

Boyer-Moore'sアルゴリズム実行時間O(nm+s)
最悪の場合、caseはTとPの最初の文字(T=aa.a,P=baaa)にのみ一致する.
この場合、brute-forceと同様の操作を実行する
*画像やDNAなどのサイズが大きい場合は効率が低下しますが、English textでは効率が低下します

前処理パターンの情報があればO(nm)time
preprocessing: O(m+s) time, searching: O(nm) time
従って、O(nm+s)時間
Boyer-Mooreは最悪の場合の時間的複雑さは暴力に匹敵するが,平均的にBoyer-Mooreの実行速度はずっと速い.

Chap13. NP-Complete Problems

質問分類:class P/class NP/class NPC
open problem: P=NP ?

Class P and Class NP

Problems and Algorithms

各問題には複雑性があり、この問題を解決する可能性のあるすべてのアルゴリズムの中で最も優れたアルゴリズムの複雑性である.
Examples
無秩序アレイでの最大値の検索:omega(n)

an無秩序配列ソート:omega(nlogn)

問題の複雑さは入力に依存する

Optimization Problems vs Decision Problems

Optimization problems :
さまざまなソリューションで最適なソリューションを見つけるための問題
ex) shortest-path

Decision problems
YES/NOで回答できる質問
ex) path

Polynomial Time: Class P

Class P
:Polynomial time T(n)=O(nkn^knk)が実行可能な決定問題
複数の期間で解決できる決定問題のセット.
これまで見たアルゴリズムは多項式時間で解決でき,class Pに相当する
アルゴリズムが多項式時間内に実行できる場合、アルゴリズムは「有効」であり、この問題は「容易」である.
多項式時間は指数時間より優れている

Some Problems are Very Hard

多項式時間に解決可能なアルゴリズムが見つからない
Example 1::0/1 knapsack problem/NPC

問題
-ある洞窟にはn個の宝物(item)が存在し、iの1番目の物品はviv iviドルとwiw iwiの重量を示す(この場合viv ivi、wiw iwiは正の整数)
-スリのバッグにW(Wは整数)の重さしか入っていない場合、スリができるだけ高いものを入れたい場合、どれを持っていくべきですか?

条件
1.泥棒は物を持って行ってもいいし、物を置いてもいい

項の一部は

を取得できません.

一度以上持っていけない

最適化の問題
Kを超える利益を含めたい問題なら、decision problem
*分割Kanspackの問題では、プロジェクトの一部、class Pを取得できます.
Example 2::traveling salesperson problem(TSP)/NPC

問題
- input: complete weighted graph

の最低コストですべての頂点にアクセスするサイクルは?

最適化された最小コスト
すべての頂点に一度だけアクセスする重みがKより低いループがある場合、decision problem
*Euler tour問題では,入力に方向図が接続されている場合,各エッジは1回のみアクセスし,O(m)時間で解決し,クラスP
*undigraphが入力されている場合、すべてのedgeに2回アクセスするループがあります.
「これまで、この2つの問題を複数の期間で解決できるアルゴリズムは見つかっていません」
Example 3::判定不可問題(重要でない問題)
Turing machine halt(YES) or runs forever(NO), decision problem

Dealing with Hard Problems

多項式時間で解決しにくい問題に遭遇した場合,NPCの方法を証明する.

自責

下限証明-非一般

は他の人が問題を解決していないことを示しています