TEMAT 1. Omówić składniki funkcji. Jest to funkcja opisująca czas działania algorytmu rekurencyjnego. O(1) dla n<=0 - jest to stały czas (klasa O(1)) potrzebny na rozwiązanie problemu - przypadek gdy rozmiar podproblemu jest mały. 2T(n/2)+O(n) - złożoność dla n>a związana z podziałem problemu na 2 podproblemy o rozmiarze n/2 każdy 2*T(n/2), O(n) jest to czas dzielenia problemu na 2 podproblemy i/lub czas scalania rozwiązań. Przykładem algorytmu jest sortowanie przez scalanie. Dla n=1 ciąg jest posortowany i złożoność jest klasy O(1). W przeciwnym wypadku rozpatruje się trzy etapy...

TEMAT 2. Problem plecakowy. Problem plecakowy jest przykładem algorytmów „zachłannych”. Problem plecakowy możemy podzielić na 2 problemy: dyskretny i ciągły. W problemie tym chodzi o wypełnienie plecaka przedmiotami niepodzielnymi - dyskretny, podzielnymi - ciągły, tak aby zabrać optymalnie najwięcej najwartościowszych przedmiotów. W klasie zagadnień podobnych chodzi o to, czy wybór optymalnej lokalnie drogi prowadzi do optymalnego globalnie rozwiązania.

TEMAT 3. Notacje. O - opis pesymistycznego czasu działania f(n)<=c*g(n) dla n>n₀. Jest niejednoznaczna - brak sposobów i kryteriów co do wyznaczania wartości c i n₀. Własności:

• przechodniość;

• f(n) + g(n) też O(h(n));

• f(n)=an^k jest O(n^k), f(n)=n^k jest O(n^k+1) dla i>0;

• f(n)=cg(n) jest O(g(n)).

Notacja ta jest dobra z punktu widzenia bezpieczeństwa, gorzej nie będzie. Jest to szacowanie bezpieczne ze względu na strukturę danych. Notacja ta jest powszechnie stosowana do wyznaczania złożoności asymptotycznej, tzn szacowania szybkości wzrostu funkcji. Ω - określa asymptotycznie dolną granicę szacowania f(n)>=c*g(n) - lepiej być nie może. Dla dowolnych danych algorytm nie będzie działał szybciej niż Ω(n). Θ - dokładne obustronne asymptotycznie oszacowanie - pasmowe, c1*g(n)<=f(n)<=c2*g(n). Ta notacja jest najdokładniejsza i szacuje dokładnie czas działania. Θ jest silniejsza od O - Θ implikuje O.

Przyczyną powstania notacji jest potrzeba posiadania uniwersalnego narzędzia do szacowania efektywności działania algorytmu jako zależności między rozmiarem danych wejściowych n a czasem jego przetwarzania. Notacje dają nam możliwość przewidzenia jaki algorytm jest najodpowiedniejszy do danego zadania, jak zachowuje się dla zbioru danych o rozmiarze n.

TEMAT 4. Tablica Pascala. Algorytm ten prezentuje klasę zagadnień związanych z technologią projektowania dynamicznego. Oznacza to tabelaryczną metodę rozwiązywania problemów. Wykorzystuje korzyści z rekurencyjnego formułowania podproblemu bez używania rekurencji w procesie jego implementacji. Strategia p.d. zakłada jednorazowe rozwiązanie każdego podproblemu i zapisanie jego wyniku w tabeli - nie trzeba wiele razy liczyć tego samego. Aby technika ta była efektywna problem powinien mieć optymalną podstrukturę - podproblemy powinny mieć dużo wspólnych podproblemów, które są obliczane tylko raz. Algorytm wypełniania tablicy Pascala w każdym kroku korzysta z już obliczonych wartości podproblemów umieszczonych w tabeli co jest zgodne z ideą.

TEMAT 5. Złożoność obliczeniowa. Złożoność obliczeniowa algorytmu jest to liczba zasobów potrzebnych do wykonania algorytmów. Może być oczekiwana (dla danych typowych) i pesymistyczna (najgorszych). Złożoność obliczeniowa jest miarą efektywności algorytmu. Miarą złożoności obliczeniowej algorytmu numerycznego może być liczba wykonywanych operacji zmiennoprzecinkowych. Za poj. operację zmiennoprz. uważa się sumę, różnicę, iloczyn oraz iloraz dwóch liczb rzeczywistych. W wielu przypadkach algorytm zawiera rekurencyjne wywołanie samego siebie. Wówczas obliczenia związane z wyznaczaniem klasy algorytmu (czasu jego działania) można sprowadzić do rozwiązania równania rekurencyjnego. Jeżeli jest ono podane w postaci zwięzłego wzoru, to jedną z technik rozwiązania jest metoda iteracyjna rozwijająca równanie do sumy np. przez podstawienie n=2^k, a następnie ograniczenie składników otrzymanej sumy.

TEMAT 6. Fibonacci. Wyznaczanie ciągu liczb Fibonacciego metodą rekurencyjna jest niesamowicie proste w implementacji lecz rekurencja pociąga za sobą duże koszta związane z kolejnymi wywołaniami ponieważ, aby obliczyć Fib(5) musimy obliczyć Fib(3) i Fib(4) a z kolei do obliczenia Fib(4) potrzebne jest obliczenie Fib(3). Ogólnie dla Fib(n) wartość Fib(3) będzie liczona Fib(n-2) razy. Związane to jest z tym, że nie pamiętamy wyników podproblemów, powtarzamy te same obliczenia. Liczba wywołań i czas działania rosną wykładniczo. Lepiej jest zapamiętywać wyniki kolejnych obliczeń w pamięci - algorytm iteracyjny który wykonuje n-2 przebiegi pętli o stałej długości wykonania. Jak widać pomimo prostoty implementacji algorytmu rekurencyjnego jego przydatność jest niewielka ze względu na nieefektywną dekompozycję problemu - rekurencja nie zawsze jest optymalna.

TEMAT 7. Typy rekurencji:

• zagnieżdżona - występuje wówczas gdy funkcja jest zdefiniowana za pomocą samej siebie oraz jeżeli użyta jest jako jeden z parametrów;

• końcowa - gdy występuje tylko jedno wywołanie rekurencyjne na samym końcu funkcji. Jest więc ostatnią wykonywaną instrukcją, a wcześniej nie było innego wywołania rekurencyjnego;

• pośrednia - gdy funkcja wywołuje siebie poprzez łańcuch wywołań innych funkcji;

• z dodatkowym parametrem domyślnym, który służy do przekazywania elementów wyniku końcowego - unika się przekazywania wyników do góry przez kolejne poziomy rekurencyjne.

Stosowanie algorytmów rekurencyjnych jest uzasadnione gdy problem jest zdefiniowany w sposób rek., trzeba jednak wziąć pod uwagę strukturę i kompozycję problemu ponieważ wywołania rekurencyjne są dosyć zasobożerne i dla źle uwarunkowanych problemów (liczby Fibonacciego) ich użycie jest wręcz nie wskazane. Wniosek: unikać rekurencji jeśli istnieje oczywiste rozwiązanie iteracyjne.

TEMAT 8. Metody projektowania algorytmów.

Dziel i zwyciężaj - istotą jest podział problemu na mniejsze o tej samej strukturze. Podział stosuje się aż do otrzymania zadania o bardzo małym rozmiarze którego rozwiązanie będzie oczywiste. Następnie łączy się rozwiązania wszystkich podproblemów w całość. Biorąc pod uwagę istotę tej struktury od razu nasuwa się myśl że tworzone wg tej idei algorytmy będą miały rekurencyjną istotę, czyli gdy problem jest scharakteryzowany rekurencyjnie i gdy problem nie ma nieefektywnej dekompozycji.

Algorytmy zachłanne - w każdym kroku wybierają najlepszą lokalnie drogę nie analizując jej pod względem przyszłych wyborów. Działają wg idei, że suma optymalnych lokalnie rozwiązań da optymalne globalne rozwiązanie. Jednak ta metoda nie gwarantuje optymalnych rozwiązań, nadaje się do pewnej klasy problemów optymalizacyjnych - znalezienie najkrótszej drogi w grafie, optymalna kolejność wykonywania pewnych czynności. Najlepiej stosować wtedy, gdy optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.

Programowanie dynamiczne - wiąże się z wykorzystaniem tabelarycznej metody rozwiązań podproblemów i wykorzystaniem formułowania rekurencyjnego problemu, ale bez użycia rekurencji w procesie jego implementacji. Istotą jest jednorazowe rozwiązanie danego podproblemu i zapamiętanie wyniku w tabeli, w celu wyeliminowania powtórnego obliczania tego samego, gdyby zaszła taka konieczność. Liczenie rozpoczynamy od najmniejszych podproblemów poprzez coraz większe zapamiętując po drodze wcześniejsze rozwiązania. Wybieramy gdy mamy problem o strukturze rekurencyjnej, ale nie nadający się ze względu na dużo wywołań do implementacji rekurencyjnej.

Algorytm z powrotami - istotą jest poszukiwanie rozwiązań pośród całego zbioru możliwych przypadków. Metoda polega na systematycznym testowaniu wszystkich wyjść z sytuacji, w miarę jak przekonujemy się że niektóre nie prowadzą do celu. Należy pamiętać wszystkie wykonane ruchy, by móc wrócić z sytuacji bez wyjścia i próbować innych dróg we wcześniejszych sytuacjach. Aby nie przeglądać wszystkich stanów można posłużyć się funkcją oceniającą, ułatwiającą inteligentny wybór. Metodę można stosować gdy metodą prób i błędów chcemy dojść do jakiegoś rozwiązania i mamy możliwość cofnięcia decyzji.

TEMAT 9. Dziel i zwyciężaj. Istotą jest podział problemu na mniejsze o tej samej strukturze. Podział stosuje się aż do otrzymania zadania o bardzo małym rozmiarze którego rozwiązanie będzie oczywiste. Następnie łączy się rozwiązania wszystkich podproblemów w całość. Często problem zapisany jest w postaci rekurencyjnej tzn. algorytm wywołuje sam siebie. Wówczas strategia często jest stosowana wg schematu:

DZIEL - podział problemu na mniejsze

ZWYCIĘŻAJ - rozwiąż mniejszy problem rekurencyjny

SCAL - łączenie rozwiązanych problemów.

Przykładem może być wyszukiwanie binarne polegające na wyszukiwaniu elementu w uporządkowanym ciągu lub sortowanie przez scalanie (MergeSort), polegające na podzieleniu sortowanej tablicy na małe podtablice i na takich podtablicach wykonujemy sortowanie po czym wynik scalamy.

TEMAT 10. Algorytmy zachłanne - w każdym kroku wybierają najlepszą lokalnie drogę nie analizując jej pod względem przyszłych wyborów. Działają wg idei, że suma optymalnych lokalnie rozwiązań da optymalne globalne rozwiązanie. Jednak ta metoda nie gwarantuje optymalnych rozwiązań, nadaje się do pewnej klasy problemów optymalizacyjnych - znalezienie najkrótszej drogi w grafie, optymalna kolejność wykonywania pewnych czynności. Najlepiej stosować wtedy, gdy optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.

Jako przykład może służyć algorytm do rozwiązywania problemu kasjera. W każdym ruchu algorytmu stara się wydać jak największy możliwy nominał - wybiera optymalną lokalnie drogę (dokonywany wybór nie zależy od przyszłych wyborów). Innym przykładem może być problem wyboru zajęć dla których przydzielona zostanie sala wykładowa, w której tylko jedno zajęcie może odbywać się w danej chwili. Problem wyboru zajęć sprowadza się do wyboru największego podzbioru parami zgodnych zajęć. Istotą algorytmu jest wybieranie zawsze zajęć mających najwcześniejszy czas zakończenia wśród zajęć, które mogą być dołączone do zbioru. Taki wybór w każdym kroku maksymalizuje ilość wolnego czasu pozostającego do dyspozycji.

TEMAT 11. Programowanie dynamiczne - wiąże się z wykorzystaniem tabelarycznej metody rozwiązań podproblemów i wykorzystaniem formułowania rekurencyjnego problemu, ale bez użycia rekurencji w procesie jego implementacji. Istotą jest jednorazowe rozwiązanie danego podproblemu i zapamiętanie wyniku w tabeli, w celu wyeliminowania powtórnego obliczania tego samego, gdyby zaszła taka konieczność. Liczenie rozpoczynamy od najmniejszych podproblemów poprzez coraz większe zapamiętując po drodze wcześniejsze rozwiązania.

Wybieramy gdy mamy problem o strukturze rekurencyjnej, ale nie nadający się ze względu na dużo wywołań do implementacji rekurencyjnej.

Jako przykład może posłużyć obliczanie ciągu Fibonacciego. Użyty został tu wzór rekurencyjny, ale algorytm jest zwykły iteracyjny i polega na tym że kolejny wyraz tablicy jest obliczany w pętli poprzez dodawanie dwóch poprzednich - metoda tabelaryczna. Innym przykładem może być algorytm wypełniania tablicy Pascala który w pierwszej pętli wypełnia pierwszą kolumnę i przekątną jedynkami, a następnie posługując się wcześniej wypełnionymi elementami tablicy wypełnia kolejne elementy w rekurencyjny sposób: element jest sumą dwóch sąsiadujących z nim powyższych elementów.

TEMAT 12. Misjonarz i ludożerca. Problem ten reprezentuje klasę algorytmów z powrotami, których istotą jest poszukiwanie rozwiązania pośród całego zbioru możliwych przypadków. Algorytm systematycznie testuje wszystkie drogi wyjścia z danego stanu pamiętając wszystkie ruchy i odwiedzane stany, aby w przypadku trafienia na ślepy zaułek można się było cofnąć do poprzednich stanów i wypróbować inną drogę. Algorytm rozwiązujący ten problem będzie się starał znaleźć rozwiązanie, lecz gdy jedna z obranych dróg okaże się zła to cofnie się i będzie próbował innej drogi. Jeżeli w ogóle stan okaże się nie do przyjęcia to cofnie się do poprzedniego i tam spróbuje inaczej rozwiązać problem. Czasami jest możliwe wybranie inteligentne drogi posługując się funkcją oceniającą, obliczającą prawdopodobieństwo sukcesu dla danej drogi.

TEMAT 13. Problem hetmanów. Należy ustawić na szachownicy 8 hetmanów tak aby żaden z nich nie szachował innych. Umieszczamy pierwszego hetmana na szachownicy, potem 2-go tak aby nie szachował 1-ego, potem 3-ego itd. Niech i-ty hetman nie da się ustawić bez kolizji. Wówczas zmieniamy pozycję poprzedniego tj. i-1 tak długo aż uda się umieścić i-tego bezkolizyjnie. Jeśli to nie pomaga wracamy do i-2, i-3 i rozpoczynamy od nowa. Rekurencyjnie problem można zapisać w postaci algorytmu:

Hetman(row)

for każda pozycja col w rzędzie row

if pozycja col nie jest szachowana then

{ umieść kolejnego hetmana na col

if row<8 Hetman(row+1)

else Drukuj_Wynik }

else Usuń_Hetmana z pozycji col

TEMAT 14. Sortowanie przez wstawianie polega na podziale tablicy na dwa podciągi x[1;i-1] uporządkowany i x[i+1;n] - nieuporządkowany. Zaczynając od drugiego elementu do n przenosimy elementy z podciągu nieuporządkowanego do uporządkowanego wstawiając w odpowiednie miejsce. Czas sortowania (złożoność) jest klasy O(n), gdy ciąg jest uporządkowany gdyż wymaga to n-1 porównań, ponieważ z lewej strony będzie element mniejszy i 2*(n-1) przypisań elementu do klucza i z klucza, co daje nam ogólną złożoność O(n). Gdy tablica jest posortowana odwrotnie wymaga to dla każdego kroku od i=2 do n: 2 przesunięć (klucz) + i-porównań (ponieważ element zawsze trzeba będzie wstawić na pierwszą pozycję) + też i-przesunięć z tego samego powodu - zawsze przesuwamy wszystkie elementy w ciągu uporządkowanym, czyli:

Przesunięcia:

Porównania:

Co daje nam złożoność O(n²) dla obu odwołań.

TEMAT 15. Dowieść, że sortowanie przez wstawianie połówkowe jest efektywniejsze niż proste wstawianie. W metodzie tej wykorzystuje się fakt, że ciąg wynikowy jest zawsze uporządkowany, zatem szukanie miejsca wstawienia nowego elementu można przeprowadzić metodą podobną do przeszukiwania binarnego, co daje nam zmniejszenie liczby porównań ponieważ w metodzie zwykłego wstawiania porównywaliśmy aż do znalezienia miejsca - czasami tyle porównań ile elementów podciągu - suma od i=1 do n z i - tyle porównań. W zwykłej metodzie złożoność dla porównań była równa: (suma od i=1 do n z i)=0,5(n²+n) ->O(n²), zaś dla tej metody wykonamy najwyżej (n-1)*log(n) porównań ponieważ główna pętla wykonuje się n-1 razy a złożoność wyszukiwania binarnego jest klasy O(log(n)), co daje nam klasę O(n*log(n)) dla porównań.

TEMAT 16. BubbleSort i ShakerSort - porównanie. Istotą sortowania bąbelkowego jest porównywanie i zmiana par sąsiadujących tak długo aż elementy będą posortowane, sprowadza to się do przebiegania tablicy (n-1) razy i za każdym razem wynoszenia „najlżejszego” elementu - maksymalnie (suma od i=1 do n z i) - tyle porównań i przestawień. Metoda ma dwie istotne wady: 1. częste są niepotrzebne przebiegi gdy tablica jest posortowana; 2. jest bardzo wrażliwa na konfigurację danych. Błędy te zostały poprawione w metodzie przez wytrząsanie: 1. przełączanie kierunku przeglądania tablicy - łagodzi niekorzystne konfiguracje danych; 2. zapamiętanie indeksu ostatniej permutacji (k=j) - pozwala ograniczać zbędne przebiegi, gdyż wszystkie obiekty poniżej tego indeksu (k) są uporządkowane; 3. zapamiętanie czy w trakcie dokonano jakichkolwiek permutacji - przejście w którym nie ma zmian wskazuje, że proces sortowania może być zakończony.

TEMAT 17. BubbleSort - przyczyny powstania ShakerSort.

for i=2 to n do - BubbleSort

For j=n downto i do

If X[j-1]>X[j] then

X[j-1] ←→ X[j]

ShakerSort

lewy←2; prawy←n

k←n

repeat

for j← prawy downto lewy do

if X[j-1]>X[j] then

X[j-1] ←→ X[j]

k←j

lewy←k+1

for j←lewy to prawy do

if X[j-1]>X[j] then

X[j-1] ←→X[j]

K←j

prawy←k-1

until lewy>prawy

Algorytm Shaker Sort jest poprawionym algorytmem bąbelkowym, zostały tutaj wyeliminowane wady bąbelkowego: 1. puste przebiegi, poprzez zapamiętywanie czy miało miejsce przestawienie (jeśli nie to już posortowany) i jest zapamiętywany indeks ostatniego przestawienia - k, ponieważ obiekty poniżej tego indeksu są już uporządkowane i nie trzeba ich sprawdzać. 2. drugą poprawką jest przełączanie kierunku przeglądania tablicy - algorytm jest mniej wrażliwy na konfigurację danych.

TEMAT 18. Sortowanie Shella. Istotą tego sortowania jest sortowanie podtablic z elementów odległych od siebie o krok k, który to w kolejnych etapach jest zmniejszany aż do wartości 1, kiedy to następuje zwykłe sortowanie zwykłych elementów. Np. dla tablicy 8-elementowej kolejne kroki mogą wynosić 4, 2, 1 chociaż niekoniecznie muszą to być potęgi dwójki. Na każdym etapie sortowanie może przebiegać według zwykłych algorytmów: przez wstawianie lub bąbelkowego co daje nam możliwość co najmniej dwóch implementacji: 1. w której alg. sort. to alg. bąbelkowy; 2. w której alg. sort. to alg. sort. przez wstawianie. Pomimo że metoda ta w implementacji z Bubblesort różni się tylko pętlą sterującą długością kroku k, to średnia efektywność tej metody jest szacowana na n^1.5 a sortowania bąbelkowego na n².

TEMAT 19a. QuickSort - jest algorytmem opartym na strategii dziel i zwyciężaj. Wybieramy jeden element ze zbioru - osiowy, i tworzymy dwa podzbiory o elementach nie większych i nie mniejszych od wybranego elementu. Proces ten powtarzamy dla obydwu podzbiorów itd. aż wszystkie podzbiory będą podzielone co oznacza że zbiór został posortowany. Istotnym elementem jest funkcja podziału realizująca przekształcenie tablicy na dwie podtablice. Algorytm ten ponieważ jest oparty na strategii dziel i zwyciężaj można implementować w postaci rekurencyjnej pod warunkiem że nie jest w procedurze tworzona kopia sortowanej tablicy. Średnia złożoność tego algorytmu jest rzędu n*log(n), ale dla przypadków: gdy element osiowy jest zawsze największy (lewy podzbiór zawiera n-1 elementów, a prawy 1, musimy dokonać n-takich podziałów) i gdy tablica jest uporządkowana odwrotnie to efektywność spada do O(n). Jak widać efektywność jest w dużej mierze uzależniona od wyboru elementu osiowego i od struktury danych.

TEMAT 19b. Quicksort - istotne elementy, funkcja podziału. Strategią realizowaną przez QuickSort jest dziel i zwyciężaj. Jako istotny element tej strategii można podać zasadę działania algorytmu. Dzieli on tablice poprzez wybór elementu osiowego na dwie podtablice o mniejszych i większych elementach i podział ten wykonuje dalej na otrzymanych podtablicach (DZIEL). Gdy wszystkie podtablice są podzielone na jednoelementowe zbiory, to wtedy zbiór jest posortowany (ZWYCIĘŻAJ). Dochodzi do tego jeszcze charakterystyczna dla tej klasy algorytmów rekurencyjna implementacja.

Przeglądanie dwustronne. 1. ustawiamy dwa wskaźniki na końcach zbioru. 2. wybieramy element osiowy z tablicy - np. środkowy 3. przeglądamy tablicę przesuwając wskaźniki aż znajdziemy z prawej element mniejszy a z lewej większy od osiowego. 4. jeśli lewy wskaźnik mniejszy od prawego to zmieniamy elementy miejscami i przesuwamy dalej wskaźniki. 5. kontynuujemy 3 i 4 aż do skrzyżowania się wskaźników. 6. możemy zmienić element osiowy z prawym wskaźnikiem aby element osiowy nie wszedł do podtablicy.

Przeglądanie jednostronne (lewostronne). 1. Ustaw wartość osiową - pierwszy element i wskaźnik na drugim elemencie. i - indeks przeglądający tablice z lewej do prawej, k - indeks elementu osiowego, k=1, v=x[k], i=2 2. Zwiększaj i - przeglądaj szukając elementu mniejszego od elementu osiowego, jeśli tak to wymień element x[++k] z x[i] znalezionym. 3. kontynuuj przeglądanie i++. 4. na koniec zmień element osiowy x[1] i x[k].

TEMAT 20. Sortowanie przez zliczanie. Metoda ta polega na zliczaniu ile jest elementów jest mniejszych od określonej liczby zbioru do posortowania. Znając tę liczbę znamy dokładnie pozycję tej liczby w ciągu posortowanym. Istotnym założeniem jest to że zbiór elementów do sortowania to liczby całkowite z przedziału (1,k) i k jest z góry znane. W metodzie tej wykorzystujemy 3 tablice: A[n] - z danymi wejściowymi o rozmiarze n, B[n] - zwracana tablica z posortowanymi danymi, C[n] - tablica robocza pamiętająca liczbę elementów mniejszych lub większych od danej liczby. Algorytm wykonuje się właściwie w 3 pętlach: 1. rozpatrujemy kolejno elementy tablicy A i w tablicy C o indeksie równym wartości tablicy A[i] dodajemy 1 - otrzymamy ile jest wystąpień danej wartości w tablicy A. 2. w drugiej pętli tworzymy ciąg kumulacyjny z elementów tablicy C i wynik zapisujemy w C. 3. W tej pętli przeglądamy tablicę A od końca i wartość A[i] jest indeksem do tablicy C, a z kolei wartość C[A[i]] jest indeksem tablicy B pod który wstawiamy A[i], po wykonaniu tej operacji zmniejszamy C[A[i]]--1 i przeglądamy tablicę A w ten sam sposób do początku. Gdy go osiągniemy to posortowaliśmy. Złożoność O(n).

TEMAT 21. Stos - liniowa struktura danych umożliwiająca zapis i odczyt informacji tylko z jednego końca (LIFO) - strategia przypomina stos kartek papieru. Funkcję które testują i modyfikują stan stosu:

Initialize(stos) - inicjalizacja (opróżnienie stosu);

Empty(stos) - test czy obszar stosu jest pusty;

Full(stos) - testowanie czy obszar stosu jest zajęty;

Push(stos) - umieszcza element na szczycie stosu;

Pop(stos) - pobiera (usuwa) element ze szczytu stosu.

TopS - wskaźnik stosu - gdy implementacja tablicowa to można go umieścić w zerowej komórce tablicy tzn. S[0]<- Top. Lepiej użyć struktury o dwóch polach - jedno przechowuje informację o wierzchołku stosu, drugie właściwe dane. Implementacja w tablicy wnosi silne ograniczenia na typ elementu wstawianego do stosu. Może to być tylko element int lub char, gdyż zawartość komórki S[0] jest zwiększana lub zmniejszana przez funkcje Push() i Pop(). W przypadku danych typu char rozmiar stosu jest ograniczony do 255 elementów. Stos może być zbudowany na bazie struktur listowych. Operacje Push() i Pop() są realizowane na głowie kolejki.

TEMAT 22. Kolejka - jest strukturą, w której element dodaje się (wstawia) na koniec kolejki - ogon, a usuwa się z początku - głowy. FIFO. Funkcje niezbędne do funkcjonowania:

InitializeQ(Q) - inicjalizacja (opróżnienie) kolejki;

EmptyQ(Q) - testowanie czy obszar kolejki jest pusty;

FullQ(Q) - testowanie czy obszar kolejki jest pełny;

Enq(el,Q) - umieszcza element na końcu kolejki, w ogonie;

Deq(Q) - pobiera (usuwa) elementy kolejki z głowy.

Kolejkę n-1 elementów może implementować tablica Q[1,n]. Zmienna HeadQ identyfikuje głowę kolejki (jej początek). Zmienna TailQ podaje kolejną wolną pozycję do której można wstawić nowy element. Wolne miejsca wykorzystuje się do dalszego wstawiania elementów przez co koniec kolejki może znaleźć się na początku tablicy. Jest to przypadek cyklicznej tablicy Q implementowanej przy tablicy jednowymiarowej po indeksie n następuje 1. HeadQ=TailQ+1 - kolejka pełna.

TEMAT 23. Lista - struktura wiązana w której następny element nie musi przylegać do poprzedniego. Elementy ułożone liniowo w porządku określonym przez wskaźniki dowiązania, a nie indeksy danych. Dowiązanie jest dodatkową informacją przechowywaną w każdym węźle wskazującą gdzie jest przechowywany następny element. Wstawiając nowy element do listy należy zmienić wartość dowiązania aby w nowym elemencie wskazywano na następny. Bardzo często maksymalny rozmiar listy nie jest znany w trakcie projektowania. Jeżeli nie jest znane dokładne zapotrzebowanie na pamięć należy stosować technikę dynamicznego przydziału pamięci. Język C++ udostępnia funkcje realizujące ten cel. Każdy element listy jednokierunkowej stanowi strukturę o dwóch polach: pole danych (dane) i dowiązanie (next) będące wskaźnikiem następnego elementu listy. Ostatni element listy zawiera pusty wskaźnik NULL. Dostęp do całej listy umożliwia wskaźnik do pierwszego elementu (Head/L). Przeszukiwanie listy - chodzenie za wskaźnikiem w polu next. Aby usunąć element należy znać wskaźnik do usuwanego elementu oraz wskaźnik do elementu go poprzedzającego w którym należy zmodyfikować pole next tak aby nie wskazywało elementu usuniętego. Aby wstawić nowy element do listy należy utworzyć przestrzeń pamięciową używając na przykład operatora wrk=new(typelist), który zwróci adres nowego węzła poprzez wskaźnik wrk. Następnie znaleźć węzeł na który chcemy wstawić nowy i zmienić jego pole next na wartość wrk. Nowy węzeł jest wstawiony jeśli jego pole next zawiera wartość pola next pola poprzedniego. Wskaźnik next nowo wstawionego elementu musi wskazywać na następny element (może być NULL).

TEMAT 24. Lista dwukierunkowa umożliwia przeglądanie w bobu kierunkach i składa się z trzech pól: pole danych, dowiązanie do elementu następnego - next, dowiązanie do elementu poprzedniego - prev. Jeżeli a jest elementem bieżącym to next[a] jest adresem elementu następnego zaś prev[a] poprzedniego. Jeżeli prev[a]=NULL to a jest pierwszym elementem na liście i stanowi głowę. Jeżeli next[a]=NULL - a jest ostatnim na liście i stanowi ogon. Zmienna FirstL wskazuje na pierwszy element listy L. Jeżeli FirstL=NULL to lista jest pusta. Procedura szukaj poszukuje pierwszego elementu o wartości elementu na liście L z wykorzystaniem algorytmu liniowego przeglądania. Zwraca wskaźnik do tego elementu lub NULL jeżeli elementu nie ma na liście. Pesymistyczny czas szukania wynosi O(n). Procedura wstaw dołącza element na początek listy. Przed wstawieniem należy zainicjalizować pole nowego rekordu np. instrukcją new. Czas działania O(1). Procedura usuń usuwa element z listy L przez modyfikowanie wartości odpowiednich wskaźników. Jeżeli do listy dołożymy dodatkowy rekord WrtL (o polach jak pozostałe) to można wyeliminować zmienną FirstL wskazującą na pierwszy element. Powstaje cykliczna lista dwukierunkowa, w której węzeł WrtL znajduje się między głową a ogonem. Next[WrtL]->głowa. Prev[WrtL]->ogon. List apusta to oba pola WrtL=NULL. Wartownik nie zmienia złożoności ale upraszcza warunki brzegowe - zmniejsza ogon. W przypadku pracy z dużą ilością małych list, korzyści z użycia wartowników nie są oczywiste, gdyż blokują oni znaczny obszar pamięci.

TEMAT 25. Drzewa (BST) - struktura w której dwa dowolne węzły może łączyć jedna ścieżka. Drzewo uporządkowane - drzewo w którym ustalona jest kolejność następników. Drzewo binarne - drzewo w którym każdy węzeł ma co najwyżej dwóch synów, a każdy syn jest opisany jako lewy lub prawy. Drzewo binarne w rekurencji: 1. nie zawiera żadnych wezłów. 2. składa się z trzech rozłącznych części: korzenia, lewego drzewa binarnego, prawego drzewa binarnego. Pełne drzewo binarne o wysokości h ma 2^h-1 węzłów wewnętrznych. Wysokość drzewa binarnego zawierającego n węzłów wewnętrznych wynosi co najmniej log(n) a co najwyżej (n-1).

Implementacje: 1. tablicowa - wymaga przypisania każdemu węzłowi struktury trzypolowej złożonej z pola danych, dwóch pól zawierających indeksy komórek w których umieszczono lewego i prawego syna. Korzeń tradycyjnie umieszcza się w komórce numer zero. 2. dynamiczna dla drzewa binarnego wymaga zdefiniowania dla każdego węzła struktury składającej się z trzech pól oraz podania wskaźnika do głowy węzła.

Drzewo BST= d. Binarne+: wartości w lewym poddrzewie<klucza i wartości w prawym poddrzewie>klucza. Wartości kluczy w BST nie powinny się powtarzać.

Wyszukiwanie węzła w drzewie BST można zrealizować mając dany wskaźnik do korzenia drzewa, poprzez funkcje rekurencyjne lub iteracyjne o czasie O(h). Proces wyszukiwania rozpoczyna się od korzenia schodząc stopniowo w dół drzewa. Implementacja iteracyjna procedury SearchTree jest zazwyczaj czytelniejsza i efektywniejsza.

TEMAT 26. Przechodzenie drzewa BST. - jest to proces odwiedzania każdego węzła w drzewie tylko raz. Potencjalnie liczba możliwych dróg dla n-węzłowego drzewa wynosi n-silnia. Mamy praktycznie dwie klasy przechodzenia: wszerz i w głąb.

Wszerz - rozpoczynamy od korzenia, przesuwamy się w dół na kolejne poziomy przeglądając od lewej do prawej. Implementacja przy pomocy kolejki. Po dotarciu do węzła - jego synowie na koniec kolejki, odwiedzany jest węzeł z początku kolejki, wtedy synowie odwiedzeni zostaną dopiero po przejściu wszystkich węzłów z danego poziomu. W polu danych kolejki - adresy.

W głąb - zaczynając od korzenia przechodzi się maksymalnie w lewo, cofa się do rozgałęzienia, krok w prawo i maksymalnie w lewo. Węzły można odwiedzać przed marszem w dół lub po powrocie - 6 wariantów.

inOrder LvR - węzeł wizytowany po przejściu lewego poddrzewa a przed przejściem prawego

preOrder vLR - węzeł wizytowany przed odwiedzeniem poddrzew

postOrder LRv - węzeł wizytowany po przejściu poddrzew.

Metoda inOrder wypisze elementy drzewa BST w porządku rosnącym.

Wstawianie i usuwanie elementów z drzewa BST wymaga często przeorganizowania jego struktury, tak aby zachowana została własność BST.

Wstawianie elementu a polega na przekazaniu do stosownej funkcji rekordu z nowym węzłem nw. Poszukiwanie węzła do wstawienia rozpoczyna się od korzenia i przebiega wzdłuż ścieżek w dół drzewa aż do napotkania węzła nie mającego odpowiedniego syna - jest to poszukiwane miejsce.

Usuwanie. 3 przypadki usuwania węzła uw: 1. Jeżeli węzeł uw nie ma syna to zostaje usunięty i u jego ojca[uw] wstawiany jest wskaźnik do uw równy NULL. 2. Jeżeli węzeł uw ma jednego syna to uw zostaje wycięty przez uaktualnienie wskaźników między jego ojcem a synem. 3. Jeżeli uw ma dwóch synów to wyizolowany zostaje węzeł y będący następnikiem uw i nie mający lewego syna. Następnie węzeł y zastępuje węzeł uw. Usuwanie elementów z drzewa BST wymaga często przeorganizowania jego struktury, tak aby zachowana została własność BST.

TEMAT 27. Rodzaje drzew - usuwanie.

Drzewo binarne - drzewo w którym każdy węzeł ma co najwyżej dwóch synów, a każdy syn jest opisany jako lewy lub prawy.

Drzewo BST= drzewo binarne+: wartości w lewym poddrzewie<klucza i wartości w prawym poddrzewie>klucza. Wartości kluczy w BST nie powinny się powtarzać. Usuwanie. 3 przypadki usuwania węzła uw: 1. Jeżeli węzeł uw nie ma syna to zostaje usunięty i u jego ojca[uw] wstawiany jest wskaźnik do uw równy NULL. 2. Jeżeli węzeł uw ma jednego syna to uw zostaje wycięty przez uaktualnienie wskaźników między jego ojcem a synem. 3. Jeżeli uw ma dwóch synów to wyizolowany zostaje węzeł y będący następnikiem uw i nie mający lewego syna. Następnie węzeł y zastępuje węzeł uw.

Kopiec - jest drzewem binarnym o następujących właściwościach: 1. wartość klucza w każdym węźle jest nie mniejsza niż klucze u jego potomków; 2. Wszystkie liście drzewa leżą na co najwyżej dwóch sąsiednich poziomach; 3. liście na ostatnim poziomie szczelnie wypełniają lewą część drzewa. Usuwanie elementu z kopca polega na usunięciu elementu o maksymalnym kluczu. Usuwany jest korzeń i w jego miejsce wstawiany jest ostatni liść. Powoduje to destrukcję kopca. W celu przywrócenia własności kopca należy dokonać przestawień idąc od korzenia w dół.

Wstawianie elementu do kopca - polega na dodaniu liścia z kluczem, przesuwaniu klucza „w” w górę po ścieżce, dopóki nie dojdzie do korzenia lub nie trafi na ojca o wartości nie mniejszej od w. Przechodząc przez kolejne węzły zamienia się nowy węzeł z jego ojcem.

TEMAT 28. Różnice między BST a B-drzewami. Algorytmy usuwania. B-drzewo rzędu m jest drzewem poszukiwań binarnych rzędu m o własnościach: 1. korzeń ma co najmniej dwa poddrzewa o ile nie jest liściem. 2. Wszystkie liście są na jednym poziomie, wynikającym z wysokości drzewa. 3. B-drzewo jest zawsze przynajmniej w połowie zapełnione i z natury swojej niskie. Dla dostatecznie dużego rzędu m, wysokość B-drzewa jest mała, przy dużej liczbie kluczy. Metodyka szukania klucza w obu drzewach jest bardzo podobna.

Usuwanie.- BST 3 przypadki usuwania węzła uw: 1. Jeżeli węzeł uw nie ma syna to zostaje usunięty i u jego ojca[uw] wstawiany jest wskaźnik do uw równy NULL. 2. Jeżeli węzeł uw ma jednego syna to uw zostaje wycięty przez uaktualnienie wskaźników między jego ojcem a synem. 3. Jeżeli uw ma dwóch synów to wyizolowany zostaje węzeł y będący następnikiem uw i nie mający lewego syna. Następnie węzeł y zastępuje węzeł uw. Usuwanie elementów z drzewa BST wymaga często przeorganizowania jego struktury, tak aby zachowana została własność BST.

Usuwanie - B-drzewa. Usuwając należy zwracać uwagę aby każdy węzeł był wypełniony co najmniej w połowie. Implikuje to czasami konieczność sklejania węzłów.

TEMAT 29a. Kopiec. Przywracanie własności. Kopiec - jest drzewem binarnym o następujących właściwościach: 1. wartość klucza w każdym węźle jest nie mniejsza niż klucze u jego potomków; 2. Wszystkie liście drzewa leżą na co najwyżej dwóch sąsiednich poziomach; 3. liście na ostatnim poziomie szczelnie wypełniają lewą część drzewa

W trakcie operacji na kopcach może zdarzyć się że drzewo binarne utraci własność kopca. Funkcja HeapDown, przywraca ją powodując spłynięcie klucza K[i] w dół kopca, aby poddrzewo zaczepione w węźle „i” stało się kopcem. W każdym kroku działania HeapDown poszukiwana jest wartość max. pośród dzieci węzła „i”. Indeks wartości max pamiętany jest w ind_max. Jeżeli K[i] jest największe to jest ok. W przeciwnym razie zamiana K[i] z K[ind_max]. Teraz bada się czy poddrzewo doczepione do K[ind-max] spełnia własność kopca. Jeśli nie to funkcja HeapDown wykonywana jest rekurencyjnie na tym poddrzewie.

TEMAT 29b. Kopiec - wstawianie, usuwanie. Wstaw: dodaj nowy liść z kluczem w do drzewa; przesuwaj klucz w w górę po ścieżce tak długo dopóki nie dojdzie do korzenia lub nie natrafi na ojca o wartości nie mniejszej od w; przechodząc przez kolejne węzły zamień nowy węzeł z jego ojcem. Usuń: pod pojęciem usuwanie elementu z kopca rozumie się usunięcie elementu o maksymalnym kluczu. Usuwany jest korzeń i w jego miejsce wstawiany ostatni liść. Powoduje to destrukcję kopca. W celu przywrócenia własności kopca należy dokonać przestawień idąc od korzenia w dół.

TEMAT 29c. Kopiec jako kolejka priorytetowa. Jednym z istotnych i najbardziej naturalnych zastosowań kopca są kolejki priorytetowe. Kolejka p. jest strukturą danych, służącą do przechowywania zbioru R rekordów. Każdy rekord ma przyporządkowany klucz, identyfikujący go jednoznaczni. Podstawowe operacje: Insert(xr,R) - wstawianie rekordu xr do zbioru R; Maximum(R) - zwraca rekord o największym kluczu; DelMax(R) - zwraca rekord o największym kluczu następnie usuwa go ze zbioru R; Empty(R) - zwraca zero gdy kolejka pusta. Tablicę K[1..n] nie będącą kopcem można przekształcić w kopiec, wykorzystując funkcję HeapDown. Założeniem jest fakt że wszystkie elementy podtablicy K[|_n/2_|+1..n] są liśćmi drzewa, a tym samym jednoelementowym kopcem. Zachodzi wstępujące przekształcenie tablicy K. Każde wywołanie HeapDown realizowane jest w czasie O(log(n)). Liczba wywołań może sięgnąć O(n). Stąd bardzo pesymistyczny czas budowania kopca wynosi O(nlog(n)).

TEMAT 29d. Sortowanie przez kopcowanie. Polega na sukcesywnej zamianie wierzchołka kopca (wartości maksymalnej) z jego ostatnim elementem i przywracanie własności kopca nowo powstałemu drzewu binarnemu. Pierwszy krok to zbudowanie kopca na tablicy wejściowej. Aktualny wierzchołek kopca zamieniany jest z n-tą pozycją tablicy K - zmniejszany jest rozmiar stosu nK. Przywracana jest następnie własność kopca poprzez HeapDown. Proces powtarza się aż do otrzymania kopca o rozmiarze 2. T(n)=O(nlog(n)). Sortowanie przez kopcowanie jest niestabilne. Gwarantuje jednak posortowanie elementów na miejscu i czas sortowania nie zależy od konfiguracji danych wejściowych.

TEMAT 30. B-drzewo rzędu m jest drzewem poszukiwań binarnych rzędu m o własnościach: 1. korzeń ma co najmniej dwa poddrzewa o ile nie jest liściem. 2. Wszystkie liście są na jednym poziomie, wynikającym z wysokości drzewa. 3. B-drzewo jest zawsze przynajmniej w połowie zapełnione i z natury swojej niskie. Dla dostatecznie dużego rzędu m, wysokość B-drzewa jest mała, przy dużej liczbie kluczy. B-drzewa mają na celu zredukowanie obciążeń wynikających z czasu dostępu do danych w strukturach pamięci zewnętrznej. Liczba kluczy w węźle jest zmienna i zależy od rozmiaru klucza, jak też od struktury danych. Postać węzła ma charakter struktury o polach: 1. liczba zmiennych w węźle 2. zmienna logiczna leaf[x] - czy węzeł jest liściem. 3. tablica zawierająca klucze, 4. tablica zawierająca wskaźniki do poddrzew.

Szukanie w B-drzewie odbywa się podobnie jak w BST. W każdym węźle należy dokonać wyboru poddrzewa (dla m kluczy w węźle jest do wyboru m+1 poddrzew). Dane wejściowe: wskaźnik do węzła x oraz poszukiwany klucz k, znajdujący się w poddrzewie o korzeniu x. Szukamy w węźle najmniejszego indeksu dla którego wk<=key_i[x]. Jeżeli nie znajdzie to i=m[x]+1. Jeżeli znaleziono klucz to koniec, jeżeli nie gdy węzeł liściem - brak klucza lub pobranie z dysku odpowiedniego syna.

TEMAT 31. Wstawianie klucza do B-drzewa. 1. Jeżeli liść nie jest pełny to wstawianie klucza do B-drzewa rozpoczyna się od umieszczenia go w liściu. 2. Jeżeli liść jest pełny generowany jest nowy liść a klucze dzielone są po połowie między stary i nowy. Ostatni klucz nowego liścia przenoszony zostaje do ojca (jeżeli jest wolne miejsce). 3. Jeżeli ojciec jest pełny to proces podziału węzła jest kontynuowany aż do korzenia. Jeżeli w korzeniu nie ma miejsca to tworzony jest nowy korzeń i brat istniejącego korzenia. Następuje dodanie dwóch nowych węzłów do B-drzewa oraz wzrost jego wysokości.

TEMAT 32. Usuwanie klucza z B-drzewa. Należy zwracać uwagę aby każdy węzeł był wypełniony co najmniej w połowie. Implikuje to czasami konieczność sklejania węzłów. 1. Usuwanie klucza z liścia - jeżeli po usunięciu klucza k liść jest wypełniony co najmniej w połowie to należy jedynie przesunąć w lewo klucze większe niż k. 2. Usuwanie klucza z liścia - jeśli liść ma lewego lub prawego brata o wypełnieniu większym niż połowa to następuje przeniesienie klucza z ojca do liścia oraz od brata do ojca. 3. Usuwanie klucza z liścia - jeżeli po usunięciu klucza z liścia wystąpił w nim niedobór a liczba kluczy u jego braci jest nie większa niż połowa możliwości to liść i brat są sklejane. Rozdzielający je klucz u ojca jest przesuwany do liścia a brat ulega zniszczeniu. Jeżeli u ojca wystąpi niedobór to jest on traktowany jak liść i czynność powtarza się aż do usunięcia niedoboru przez scalenie. 4. Usuwanie klucza z węzła wewnętrznego - usuwany klucz zastępowany jest następnikiem (poprzednikiem) przy czym musi znajdować siew liściu. W kolejnym etapie następnik usuwany jest z liścia zgodnie ze wcześniejszą procedurą. Złożoność: procedura usuwania wymaga O(h) operacji dyskowych i O(ph)=O(plog_p(n)) czasu procesora.

TEMAT 33. Graf G=(N,E) składa się ze skończonego zbioru N węzłów oraz zbioru E krawędzi. Każdą krawędź E stanowi para węzłów zatem E jest zbiorem par (u,v) zaś (u),(v) stanowią elementy zbioru N. Mówimy że wierzchołek v jest sąsiedni do wierzchołka u. Graf skierowany - każda krawędź jest uporządkowaną parą węzłów. Graf nieskierowany - każda krawędź jest nieuporządkowaną parą węzłów. Nie mogą wystąpić pętle, zatem każda krawędź zawiera dwa różne wierzchołki. Graf rzadki - graf dla którego |N|<<|E|². Graf gęsty - gdy |N| jest bliskie |E|².

TEMAT 34. Implementacja grafu. 1. Macierzy sąsiedztwa - macierz kwadratowa o wymiarze określonym liczbą węzłów. Element macierzy przyjmuje wartość 1 jeżeli istnieje krawędź od węzła w kolumnie do węzła w wierszu. 2. Lista sąsiedztwa- przechowywanie są listy sąsiadów każdego węzła bądź z użyciem tablic lub jaka zwykłe listy wiązane. Problem najkrótszej ścieżki: dany jest ważony graf skierowany G=(N,E) z funkcją wagową w:ER przyporządkowującą krawędziom wagi o wartościach rzeczywistych. Dany jest wyróżniony wierzchołek s∈N zwany źródłem. Dla dowolnego wierzchołka v∈N należy znaleźć najkrótszą ścieżkę z s do v. Wagą ścieżki p=<v₀,v₁,..,v_k> jest suma wag tworzących ją krawędzi:
Wagę najkrótszej ścieżki z wierzchołka u do wierzchołka v określa zależność: δ(u)=min{w(p):uv} jeżeli istnieje ścieżka z u do v, w przeciwnym razie δ(u)=∝. Najkrótszą ścieżką z wierzchołka u do v jest każda ścieżka p z u do v dla której w(p)=δ(u,v). Problem minimalnego drzewa rozpinającego w grafie spójnym - wyznaczenie drzewa T łączącego wszystkie wierzchołki, którego łączna waga jest najmniejsza (np. łączenie końcówek układów elektronicznych aby uzyskać minimalną długość ścieżek). Problem ten można modelować spójnym grafem nieskierowanym G=(N,E) w którym N jest zbiorem końcówek zaś E jest zbiorem możliwych połączeń między parami końcówek. Do każdej krawędzi (u,v) przypisana jest waga w(u,v) określająca długość potrzebnego przewodu do połączenia wierzchołków u i v. Rozwiązaniem problemu jest znalezienie acyklicznego podzbioru T⊆E który łączy wszystkie wierzchołki i którego łączna waga określona zależnością:
jest najmniejsza.

TEMAT 36. Algorytm Knutha-Morrisa-Pratta. Jest to zmodyfikowany algorytm naiwny w ten sposób że wzorzec nie zawsze jest przesuwany o jeden i wykonywane są testy zgodności lecz przesunięcie wzorca jest wyznaczane na podstawie informacji o liczbie q zgodnych znaków wzorca i tekstu, oraz na podstawie analizy struktury wzorca. Informacje wynikające z analizy wzorca są przechowywane w tablicy Π[q], w której to zapisane jest jaki najdłuższy prefiks jest jednocześnie sufiksem q-pierwszych znaków wzorca. Np. w=ababa Π[4]=2 ponieważ dwie litery ab są jednocześnie i przedrostkiem i przyrostkiem. Zatem algorytm ten działa prawie jak naiwny, dla q=1, lecz gdy napotka zgodność Wzorca z Tekstem na q>1 znakach to wtedy obliczane jest przesunięcie s^→=s+(q-Π[q]), gdzie s jest aktualną pozycją początku wzorca względem tekstu. Pozwala to uniknąć wielu niepotrzebnych sprawdzeń. Największy zysk jest osiągany przy tekstach o dużym stopniu samopowtarzalności. Pozwala to uzyskać czas O(n+m), m - długość wzorca, przy czasie działania algorytmu naiwnego O(n²).

TEMAT 37. Algorytm Rabina-Karpa. Algorytm ten opiera się na zmianie tekstu złożonego z k-symboli na k-cyfrową liczbę. Możemy przyjąć że każdy symbol jest cyfrą w systemie o podstawie d co oznacza że mamy d-elementowy alfabet Ω={0,1,....,d-1}. Dla danego ciągu n-znaków możemy obliczyć jego interpretację liczbową korzystając np. ze schematu Hornera. Na tej samej zasadzie możemy obliczyć wartość m znaków tekstu, przy określonym przesunięciu. To pozwala nam znaleźć wystąpienie W w T w czasie O(n+m).

TEMAT 38. Algorytm „Brute-Force”. Jako założenia przyjmujemy jednoznacznie zdefiniowany alfabet Ω, tekst o długości n zapisany w tablicy T[n], zaś wzorzec o długości m jest zawarty w tablicy W[m]. Wzorzec występuje w tekście z przesunięciem s, gdy 0<=s<=n-m, oraz T[1+s,s+m]=W[1,m]. W tym, algorytmie dla przesunięcia od s=0 do s=n-m jest sprawdzana zgodność m-znaków wzorca z s+m znakami tekstu, gdy się nie zgadzają to przesunięcie jest zwiększane o jeden.

---