35 (580)

46. Podać algorytm „naiwny" wyszukiwania wzorca w tekście. Jaka jest jego złożoność?

/ - ustalony, skończony zbiór symboJi (liter) ~ -alfabet, ciągli symboli - tekst lub słowo. Długość tekstu to liczba jego symboli. Jeżeli długość tekstu = 0. to jest to słowo puste. Długość tekstu x oznaczamy \x\.

Podstawowym problemem dotyczącym tekstów jest problem wyszukiwania wzorca - WW. Problem WW poleg3 na znalezieniu wszystkich wystąpteń tekstu x, zwanego wzorcem, w tekście y.

Przyjmujemy, że ixi - m_t lyl = n oraz n > m

Algorytm N .nańvn/:

^YP*

zeksZ : array(l..n] of er.ar; wzr-zzez : array [ 1 . * m ) od" cź<£r;

functicn KysruAriw&rii*_n&±: irc-ger; var j : incegez;

begin

i : - 1; [i - wskaźnik w- tekście} j : * i ; (j - wskaźnik we wzorcu} rep-ea c

if se.ksc(i) = wzorzec [j j then i : = i -i- i ;

J • ~ 3“ - * ei

^— **'

end-if ;

entil ij > or (i > n) ;

IjC j > s. tber.

recurn(i-aj;

eisa

re tum ii;; {wzorca nie zruiicźonu (/ - // + I)}

Tp^(n) = 0(n^:)

T(n) = O(n)

Przypadek pesymistyczny: wzorzec = '00000001 *, tekst = ' ‘000...01' (52 zera). Wykonujemy 7*(52-7) = 2‘.5 porównań

T^_s(n_rm) = (n - m) ■ m + m = 0(n • mj

Szacunek średniej Złożoności dla alfabetu dwuelementowego. Ni eon x i y będą tekstami. Prawdopodobieństwo, ze test    = y[i+j+1] jest pozytywny wynosi 'A. WiYc oczekiwana (b. testów, które

wykurzmy dla ustalonego / nie przekracza 2. Średnia złożoność (mierzona Ib. porównań) algorytmu /V n;e przekracza więc 2/r Dla większej Ib. liter jest analogicznie.

51. O mówić /uwf algorytmu zachłannego na przykładzie projektowania sekwencji zmiany świateł na skrzyżowaniu. Na czym polega problem kolorowania grafu ?

Otói jeśli chodzi o problem kolorowania grafów to mamy ru do czynienia z problemem, który nie jest sprawą jednoznacznie rozwiązywalną. Pojęcie rozwiązywdności pojawia się tutaj w kontekście znalezienia w szybki sposób jedynego słusznego i poprawnego rozwiązania. Biorąc pod uwagę grafy jako twory matematyczne nie możemy dyskutować o rozwiązaniach jednoznacznych. Wynika to ze złożoności pesymistycznej rozważanego problemu. Dla grafów problem kolorowania jest rzędu O(n). Dlatego