elte-ik-pti-bsc-zarovizsga/14. Alapvető algoritmusok/14. Alapvető algoritmusok.tex

\documentclass[margin=0px]{article}

\usepackage{listings}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{float}
\usepackage[a4paper, margin=0.7in]{geometry}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{t1enc}
\usepackage{fancyhdr}
\usepackage{setspace}

\onehalfspacing

\newenvironment{tetel}[1]{\paragraph{#1 \\}}{}

\pagestyle{fancy}
\lhead{\it{PTI BSc Záróvizsga tételek}}
\rhead{14. Alapvető algoritmusok}

\title{\textbf{{\Large ELTE IK - Programtervező Informatikus BSc} \vspace{0.2cm} \\ {\huge Záróvizsga tételek}} \vspace{0.3cm} \\ 14. Alapvető algoritmusok}
\author{}
\date{}

\begin{document}
\maketitle

\begin{tetel}{Alapvető algoritmusok és adatszerkezetek}
    Függvények aszimptotikus viselkedése, algoritmusok hatékonysága. Összehasonlító rendezések (beszúró, összefésülő, gyors- és kupacrendezés), maximális műveletigény alsó korlátja. Rendezés lineáris időben (bucket, leszámláló és radix rendezés). Adattömörítés (naiv, Huffman, LZW). Mintaillesztés (brute-force, quicksearch, KMP).
\end{tetel}

\section{Függvények aszimptotikus viselkedése, algoritmusok hatékonysága}
TODO

\section{Összehasonlító rendező algoritmusok (buborék és beszúró rendezés, ill. verseny, kupac, gyors és összefésülő rendezés)}

Buborék- és beszúró rendezés klasszikusak, $n^2$-es műveletigényűek, a többi hatékony, $n\log(n)$-es idejűek.

\subsection{Buborékrendezés}

A legnagyobb értéket cserékkel a végéig felbuborékozza, ezt minden ciklus végén elhagyjuk. A gyakorlatban nem használják.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/Buborekrendezes.png}
    \caption{Buborékrendezés}
\end{figure}

\subsection{Beszúró rendezés}

Kis $n$-re (kb 30) ez a rendezés a legjobb. \\
Itt az elemmozgatás mindig 1 értékadás (buborékrendezésnél a csere 3 értékadás). Listára is implementálni lehet, ez esetben a pointereket állítjuk át, az elemek helyben maradnak. \\
$A[1..j]$ rendezett, $j=1..n$.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/Beszurorend.jpg}
    \caption{Beszúró rendezés}
\end{figure}

\subsection{Versenyrendezés}

Gyakorlatban nem használják. \\
Teljes bináris fa az alapja, egy versenyfa. Szintfolytonosan ábrázoljuk tömbösen.\\
\begin{enumerate}
    \item A versenyfa kitöltése (a verseny lejátszása). Maximum a gyökérben, ennek kiírása az outputra.
    \item $(n-1)$-szer
          \begin{itemize}
              \item[a)] gyökérben szereplő maximális elem helyének megkeresése a levélszinten és $-\infty$ írása a helyére
              \item[b)] az egészet újrajátsszuk (azt az ágat, ahol volt) $\to$ 2. legjobb feljut a gyökérbe
          \end{itemize}
\end{enumerate}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/Versenyrend.jpg}
    \includegraphics[width=0.3\textwidth]{img/VFaKitolt.jpg}
    \includegraphics[width=0.3\textwidth]{img/VFaMax.jpg}
    \caption{Versenyrendezés}
\end{figure}

\subsection{Kupacrendezés}

\begin{enumerate}
    \item Kezdő kupac kialakítása. Rendezetlen input tömbből tartalmi invariánst készítünk, ami már kupac struktúrájú. Elv: cserékkel lesüllyesztjük az elemet a nagyobb gyerek irányába, ha kisebb a nagyobbik gyereknél. A süllyesztés eljuthat ahhoz a csúcshoz, amelynek nincs jobb gyereke.
    \item $(n-1)$-szer
          \begin{itemize}
              \item[a)] gyökérelem és az alsó szint jobb szélső (=utolsó) aktív elemének cseréje, és a csere után lekerült elem inaktívvá tétele
              \item[b)] a gyökérbe került elem süllyesztése az aktív kupacon
          \end{itemize}
\end{enumerate}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/Kezdokupac.jpg}
    \includegraphics[width=0.3\textwidth]{img/Sully.jpg}
    \includegraphics[width=0.3\textwidth]{img/KupacRend.jpg}
    \caption{Kupacrendezés}
\end{figure}

A kezdőkupac kialakításánál, és a ciklus közben a süllyesztés módja kicsit különbözik, hiszen az első esetben a változó elem süllyed le a teljes kupacon, a másodikban a gyökér süllyed az aktív kupacon. A képen látható algoritmus mindkét műveletet teljesíti.

\subsection{Gyorsrendezés}

Elve: véletlenül választunk egy elemet. A nála kisebb elemeket tőle balra, a nagyobbakat jobbra rakjuk, az elemet berakjuk a két rész közé. Rekurzív algoritmus.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/GyorsRend.jpg}
    \includegraphics[width=0.3\textwidth]{img/Helyrevisz.jpg}
    \caption{Gyorsrendezés}
\end{figure}

\subsection{Összefésülő rendezés}

Alapja: 2 rendezett sorozat összefésülése. Ezt alkalmazhatjuk felülről lefelé (rekurzív) vagy alulról felfelé (iteratív), ez utóbbit szekvenciális fájloknál.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/OFRend.jpg}
    \caption{Összefésülő rendezés}
\end{figure}

\section{A műveletigény alsó korlátja összehasonlító rendezésekre}

\subsection{Műveletigény}

Kijelöljük a domináns műveleteket, és az $n$ inputméret függvényében hányszor hajtódnak végre, ezt nézzük. Jelölés általánosan $T(n)$, de lehet konkrétan is, pl $Cs(n)$ [csere]. $mT(n)$ a minimális műveletigény, $MT(n)$ a maximális és $AT(n)$ az átlagos.
\begin{itemize}
    \item[$\Theta$]: nagyságrendileg azonos, két konstans közé beszorítható
    \item[$\mathcal{O}$]: nagyságrendi felső becslés, $o$: nincs megengedve az egyenlőség
    \item[$\Omega$]: nagyságrendi alsó becslés, $\omega$: nincs megengedve az egyenlőség
\end{itemize}

\subsection{Alsókorlát}

Például: $n$ elem maximumkiválasztása legalább $(n-1)$ összehasonlítást igényel. Bizonyítása: Ha ennél kevesebb összehasonlítás lenne, akkor legalább 1 elem kimaradt, és ezzel ellentmondásba kerülhetünk. \\
\textit{Döntési fa}: Algoritmus $n$ méretű inputra. Kiegyenesednek a ciklusok véges hosszú lánccá, a végrehajtás nyoma egy fa struktúrát ad. Tökéletes fa: minden belső pontnak 2 gyereke van. Ennél az algoritmusnál nincs jobb, mert $2^{h(t)} \geq n!$, összehasonlító rendezés esetén, $n!$ input.

\subsection{Alsókorlát legrosszabb esetben}

Tétel: $MO_R(n) = \Omega(n\log{n})$ A legkedvezőtlenebb permutációra legalább $n\log{n}$ összehasonlítás. Bizonyítás: $\log_2{n!} \leq n\log_2{n} = \Omega(n\log{n})$, és $MO_R(n)=h(t) \geq \log_2{n!}$ (lemma miatt) $\Rightarrow$ $MO_R(n)=\Omega(n\log{n})$.

\subsection{Alsókorlát átlagos esetben}

Legyen minden input egyformán valószínű ($\frac{1}{n!}$). \\
$AO_R(n) = \frac{1}{n!}\sum_{p \in Perm(n)}{O_R(p)}$, és könnyű belátni, hogy $\sum_{p}{O_R(p)} = lhsum(h(t_R(n)))$ [levél-magasság-összeg]. \\
Lemma: Az $n!$ levelet tartalmazó tökéletes fák közül azokra a legkisebb az $lhsum(h(t_R(n)))$ érték, amelyek majdnem teljesek. \\
Tétel: $AO_R(n) = \Omega(n\log{n})$.

\section{Rendezés lineáris időben (bucket-, leszámláló- és radix rendezés)}
\subsection{Bucket rendezés}
A bucket rendezés egy olyan rendezési algoritmus, amelyet általában egyenletesen elosztott értékekkel dolgozó adatsorok rendezésére használnak.
\begin{itemize}
    \item A bemeneti adatsorban meghatározunk egy tartományt vagy intervallumot, amelyben az értékek eloszlása közel azonos. Ez a tartomány általában a minimális és maximális érték közötti intervallum.
    \item Létrehozunk egy vagy több "vödröt" vagy "bucketet", amelyek a tartományon belül helyezkednek el. A vödrök száma lehet állandó vagy változó, és attól függ, hogy milyen módon osztjuk el a tartományt.
    \item Az adatokat a megfelelő vödrökbe helyezzük a kulcsuk alapján. Ez történhet például a kulcsérték egészrészének kiszámításával vagy a hash függvény segítségével.
    \item Minden vödörben levő adatsort rendezünk. Ez a rendezési lépés lehet bármely más rendezési algoritmus alkalmazása, például beszúrási rendezés vagy gyorsrendezés.
    \item Az egyes vödrökből származó rendezett adatsorokat összevonjuk, hogy előálljon a rendezett kimeneti adatsor.
\end{itemize}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{img/bucket.png}
\end{figure}

\subsection{Leszámláló rendezés}
A leszámláló rendezés egy hatékony és stabil (az azonos értékű elemek sorrendjét megőrző) lineáris időkomplexitású rendezési algoritmus.
\begin{itemize}
    \item Először meghatározzuk a bemeneti adatsor legnagyobb és legkisebb értékét, hogy meghatározzuk a tartományt, amelyben az értékek eloszlanak. Ez a lépés szükséges ahhoz, hogy létrehozhassunk egy leszámláló tömböt, amely tartalmazza a különböző értékek előfordulási számát.
    \item Létrehozunk egy leszámláló tömböt, amelynek mérete a tartomány méretével egyezik meg. A leszámláló tömb minden eleme kezdetben 0.
    \item Végigmegyünk a bemeneti adatsoron, és minden elem előfordulását megszámoljuk a leszámláló tömbben. Az elemeket a leszámláló tömb indexével azonosítjuk.
    \item A leszámláló tömbben frissítjük az elemek előfordulási számát azzal, hogy hozzáadjuk az előző elem előfordulási számát. Ez a lépés segít abban, hogy meghatározzuk az adott elem végleges helyét a rendezett adatsorban.
    \item Végigmegyünk újra a bemeneti adatsoron, és minden elemet a leszámláló tömb alapján beszúrunk a rendezett adatsor megfelelő pozíciójába. Eközben a leszámláló tömbből csökkentjük az adott elem előfordulási számát, hogy kezeljük az esetleges azonos értékeket.
    \item Az eredményül kapott rendezett adatsor a bemeneti adatsor rendezett változata.
\end{itemize}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.6\textwidth]{img/counting_sort.png}
\end{figure}

\subsection{Radix rendezés}
A radix rendezés egy hatékony, stabil és nem összehasonlító rendezési algoritmus, amelyet általában egész számok rendezésére alkalmaznak.
\begin{itemize}
    \item Először meghatározzuk a bemeneti adatsor legnagyobb értékét. Ez szükséges ahhoz, hogy meghatározzuk, hány számjegyet kell figyelembe venni a rendezés során.
    \item Kezdjük a rendezést a legkisebb számjegytől (legkevésbé jelentős) a legnagyobbig (legjelentősebb). Ez lehet az egységjegy, tizedesjegy, százalékjegy stb.
    \item A bemeneti adatsort rendezzük a jelenlegi számjegy szerint. Ez általában egy stabilitást megőrző rendezési algoritmus, például beszúrási rendezés vagy leszámláló rendezés alkalmazásával történik.
    \item A rendezett adatsort átrendezzük és elhelyezzük az eredményül kapott sorrendben. Ez a lépés a stabilitást biztosítja, hogy az azonos értékű elemek sorrendje ne változzon.
    \item Ismételjük meg a 2-4 lépéseket az összes számjegyre, a legkevésbé jelentőstől a legjelentősebbig. Ezáltal az adatsorban a rendezés minden számjegy szerint megtörténik.
    \item Az eredményül kapott rendezett adatsor a bemeneti adatsor rendezett változata.
\end{itemize}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.6\textwidth]{img/radix_example.png}
    \caption{Példa, mivel jobban érthető mint az algo}
\end{figure}

\section{Adattömörítések}
\subsection{Naiv adattömörítés}
A tömörítendő szöveget karakterenként, fix hosszúságú bitsorozatokkal kódoljuk.
$\sum$ = $\sigma$ 1, $\sigma$2, . . . , $\sigma$i az ábécé.

Egy-egy karakter $\lceil$lg d$\rceil$ bittel kódolható, ui. $\lceil$lg d$\rceil$ de biten 2
\textsuperscript{$\lceil$lg d$\rceil$} de különböző bináris kód ábrázolható, és 2\textsuperscript{$\lceil$ lg d$\rceil$} $\geqslant$  d > 2\textsuperscript{$\lceil$ lg d$\rceil$-1}
, azaz $\lceil$lg d$\rceil$ biten ábrázolható
d-féle különböző kód, de eggyel kevesebb biten már nem.
$In : \sum \langle \rangle$  a tömörítendő szöveg. n = |In| jelöléssel n * $\lceil$lg d$\rceil$ bittel kódolható.
Pl. az ABRAKADABRA szövegre d = 5 és n = 11, ahonnét a tömörített
kód hossza $11 * \lceil lg 5 \rceil = 11 * 3 = 33$ bit. (A 3-bites kódok közül tetszőleges 5
kiosztható az 5 betűnek.) A tömörített fájl a kódtáblázatot is tartalmazza.
A fenti ABRAKADABRA szöveg kódtáblázata lehet pl. a következő:

\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/naiv_table.png}
\end{figure}

\subsection{Huffman-algoritmus}
A Huffman-algoritmussal való tömörítés lényege, hogy a gyakrabban előforduló elemeket (karaktereket) rövidebb, míg a ritkábban előfordulókar hosszabb kódszavakkal kódoljuk.

Ehhez tisztában kell lennünk az egyes karakterek gyakoriságával (vagy relatív gyakoriságával). Ezek alapján  egy ún. Huffman-fát építünk, melyben az éleket a kód betűivel címkézzük, a fa levelein a kódolandó betűk helyezkednek el, a gyökérből a levelekig vezető út címkéi alapján rajuk össze a kódszavakat.\\

\noindent
Az algoritmus (spec. bináris Huffman fára):
\begin{enumerate}
    \item A kódolandó szimbólumokat gyakoriságaik alapján sorba rendezzük.
    \item A következő redukciós lépéseket addig hajtjuk végre, míg egy csoportunk marad.
    \item Kiválasztjuk az utolsó két elemet (legritkább), összevonjuk őket egy új csoportba, és ennek a csoportnak a gyakorisága a gyakoriságok összege lesz.
    \item A csoportot visszahelyezzük a rendezett sorba (gyakoriság alapján rendezve).
    \item A csoportból új csúcsot képezünk, mely csúcs az őt alkotó két elem szülője lesz.
\end{enumerate}

\noindent
Példa:\\
Legyen a következő 5 betű, mely a megadott gyakorisággal fordul elő:\\

\begin{tabular}{|c|c|c|c|c|}
    \hline A & B & C & D & E \\
    \hline 5 & 4 & 3 & 2 & 1 \\
    \hline
\end{tabular}\\

Ekkor a redukciós lépések a következők:

\begin{itemize}
    \item \begin{tabular}{|c|c|c|c|}
              \hline A & B & C & D, E \\
              \hline 5 & 4 & 3 & 3    \\
              \hline
          \end{tabular}

    \item \begin{tabular}{|c|c|c|}
              \hline C, D, E & A & B \\
              \hline 6       & 5 & 4 \\
              \hline
          \end{tabular}

    \item \begin{tabular}{|c|c|}
              \hline A , B & C, D, E \\
              \hline 9     & 6       \\
              \hline
          \end{tabular}

    \item \begin{tabular}{|c|}
              \hline A , B , C, D, E \\
              \hline 15              \\
              \hline
          \end{tabular}
\end{itemize}

A huffman-fa a XY. ábrán látható.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/Huffman_fa.png}
    \caption{Huffman-fa példa}
    \label{fig:Huffman_fa}
\end{figure}

Tehát a kódszavak:

\begin{tabular}{|c|c|c|c|c|}
    \hline A  & B  & C  & D   & E   \\
    \hline 00 & 01 & 10 & 110 & 111 \\
    \hline
\end{tabular}
\subsection{LZW-algoritmus}
Az LZW (Lempel-Ziv-Welch) tömörítésnek a lényege, hogy egy szótárat bővítünk folyamatosan, és az egyes kódolandó szavakhoz szótárindexeket rendelünk.
\begin{description}
    \item[Kódolás] \hfill \\
        A kódolás algoritmusa a következő lépésekből áll:
        \begin{enumerate}
            \item A szótárt inicializáljuk az összes 1 hosszú szóval
            \item \label{itm:szotar} Kikeressük a szótárból a leghosszabb, jelenlegi inputtal összeillő $W$ sztringet
            \item $W$ szótárindexét kiadjuk, és $W$-t eltávolítjuk az inputról
            \item A $W$ szó és az input következő szimbólumának konkatenációját felvesszük a szótárba
            \item A \ref{itm:szotar}. lépéstől ismételjük
        \end{enumerate}
    \item[Dekódolás] \hfill \\
        A dekódolás során is építenünk kell a szótárat. Ezt már azonban csak a dekódolt szöveg(rész) segítségével tudjuk megtenni, mivel egy megkapott kód dekódolt szava és az utána lévő szó első karakteréből áll össze a szótár következő eleme.

        Tehát a dekódolás lépései:
        \begin{enumerate}
            \item Kikeressük a kapott kódhoz tartozó szót a szótárból ($u$), az output-ra rakjuk
            \item Kikeressük a következő szót ($v$) a szótárból, az első szimbólumát $u$-hoz konkatenálva a szótárba rakjuk a következő indexszel.
            \item Amennyiben már nincs következő szó, dekódolunk, de nem írunk a szótárba.
        \end{enumerate}

        Megtörténhet az az eset, hogy mégis kapunk olyan kódszót, mely még nincs benne a szótárban. Ez akkor fordulhat elő, ha a kódolásnál az aktuálisan szótárba írt szó következik.\\

        Példa:

        Szöveg: AAA\\
        Szótár: A - 1

        Ekkor a kódolásnál vesszük az első karaktert, a szótárbeli indexe 1, ezt kiküldjük az outputra. A következő karakter A, így AA-t beírjuk a szótárba 2-es indexszel. Az első karaktert töröljük az inputról. Addig olvasunk, míg szótárbeli egyezést találunk, így AA-t olvassuk (amit pont az előbb raktunk be), ennek indexe 2, tehát ezt küldjük az outputra. AA-t töröljük az inputról, és ezzel végeztünk is. Az output: 1,2

        Dekódoljuk az 1,2 inputot! Jelenleg a szótárban csak A van 1-es indexszel. Vegyük az input első karakterét, az 1-et, ennek szótárbeli megfelelője A. Ezt tegyük az outputra. A következő index a 2, de ilyen bejegyzés még nem szerepel a szótárban. \\

        Ebben az esetben a dekódolásnál, egy trükköt vetünk be. A szótárba írás pillanatában még nem ismert a beírandó szó utolsó karaktere (A példában A-t találtuk, de nem volt 2-es bejegyzés). Ekkor ?-et írunk a szótárba írandó szó utolsó karakterének helyére. (Tehát A? - 2 kerül a szótárba). De mostmár tudni lehet az új bejegyzés első betűjét ( A? - 2 az új bejegyzés, ennek első betűje A). Cseréljük le a ?-et erre a betűre. (Tehát AA - 2 lesz a szótárban).
\end{description}
\section{Mintaillesztés}
\subsection{Brute-force mintaillesztés}
A brute force algoritmus egy egyszerű, de nem mindig hatékony módszer, amelyet problémák megoldására alkalmaznak. A brute force megközelítés során az algoritmus minden lehetséges lehetőséget kipróbál a probléma megoldására, majd megtalálja a helyes eredményt.

\begin{itemize}
    \item Meghatározzuk a probléma lehetséges megoldási területét. Ez lehet egy adott adatsor, egy meghatározott intervallum, vagy egyéb feltétel alapján meghatározott értékek.
    \item Generáljuk az összes lehetséges kombinációt vagy lehetőséget a megoldási területen. Ez lehet például egy iteráció, amely végigmegy minden lehetséges értéken vagy kombináción.
    \item Ellenőrizzük minden lehetséges kombináció vagy lehetőség esetén, hogy az adott megoldás kielégíti-e a probléma feltételeit vagy kritériumait.
    \item Tároljuk el a helyes megoldásokat, vagy válasszuk ki a legjobb eredményt a probléma alapján.
\end{itemize}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/brute_force.png}
\end{figure}

\subsection{Knuth-Morris-Pratt algoritmus}
A Knuth-Morris-Pratt eljárásnak a Brute-Force (hasonlítsuk össze, toljunk egyet, stb..) módszerrel szemben az az előnye, hogy egyes esetekben, ha a mintában vannak ismétlődő elemek, akkor egy tolásnál akár több karakternyit is ugorhatunk.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/KMP_sample.png}
    \caption{KMP algoritmus több karakter tolás estén}
    \label{fig:KMP_sample}
\end{figure}

Az ugrás megállapítását a következőképp tesszük: Az eddig megvizsgált egyező mintarész elején (prefix) és végén (suffix) olyan kartersorozatot keresünk, melyek megegyeznek. Ha találunk ilyet, akkor a mintát annyival tolhatjuk, hogy az elején lévő része ráilleszkedjen a végén levőre.

Azt, hogy ez egyes esetekben mekkorát tolhatunk nem kell minden elromlás alkalmával vizsgálni. Ha a mintára önmagával lefuttatjuk az algoritmus egy módosított változatát (\ref{fig:KMP_initnext}. ábra), kitölthetünk egy tömböt, mely alapján a tolásokat végezni fogjuk.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/KMP_initnext.jpg}
    \caption{KMP tolásokat szabályzó tömb kitöltése}
    \label{fig:KMP_initnext}
\end{figure}

Az algoritmus (ld \ref{fig:KMP}. ábra):
\begin{itemize}
    \item Két indexet $i$ és $j$ futtatunk a szövegen illetve a mintán.
    \item Ha az $i+1$-edik és $j+1$-edik karakterek megegyeznek, akkor léptetjük mind a kettőt.
    \item Ha nem egyeznek meg, akkor:
          \begin{itemize}
              \item Ha a minta első elemét vizsgáltuk, akkor egyet tolunk a mintán, magyarul a minta indexe marad az első betűn, és a szövegben lévő indexet növeljük eggyel ($i=i+1$)
              \item Ha nem a minta első elemét vizsgáltuk, akkor annyit tolunk, amennyit szabad. Ez azt jelenti, hogy csak a mintán lévő indexet helyezzük egy kisebb helyre ($j = next[j]$)
          \end{itemize}
    \item Addig megyünk, míg vagy a minta, vagy a szöveg végére nem érünk. Ha a minta végére értünk, akkor megtaláltuk a mintát a szövegben, ha a szöveg végére értünk, akkor pedig nem.
\end{itemize}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/KMP.jpg}
    \caption{KMP algoritmus}
    \label{fig:KMP}
\end{figure}
\subsection{Boyer-Moore  | Quick search algoritmus}
Míg a KMP algoritmus az elromlás helye előtti rész alapján döntött a tolásról, addig a QS a minta utáni karakter alapján. Tehát elromlás esetén:
\begin{itemize}
    \item Ha a minta utáni karakter benne van a mintában, akkor jobbról az első előfordulására illesztjük. (\ref{fig:BoyerMoore_shift1}. ábra)
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.4\textwidth]{img/BoyerMoore_shift1.png}
              \caption{QS - eltolás ha a minta utáni karakter benne van a mintában}
              \label{fig:BoyerMoore_shift1}
          \end{figure}
    \item Ha a minta utáni karakter nincs benne a mintában, akkor a mintát ezen karakter után illesztjük. (\ref{fig:BoyerMoore_shift2}. ábra)
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.6\textwidth]{img/BoyerMoore_shift2.png}
              \caption{QS - eltolás ha a minta utáni karakter nincs benne a mintában}
              \label{fig:BoyerMoore_shift2}
          \end{figure}
\end{itemize}

Az eltolás kiszámítását megint elő lehet segíteni egy tömbbel, most azonban, mivel nem a minta az érdekes, és nem tudjuk pontosan mely karakterek szerepelnek a szövegben, így a tömbbe az egész abc-t fel kell vennünk (\ref{fig:BoyerMoore_initshift}. ábra)

\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/BoyerMoore_initshift.jpg}
    \caption{QS - Az eltolást elősegítő tömb ($Shift['a'...'z']$) konstruálása}
    \label{fig:BoyerMoore_initshift}
\end{figure}

Az algoritmus (ld. \ref{fig:BoyerMoore}. ábra):
\begin{itemize}
    \item Két indexet $k$ és $j$ futtatunk a szövegen illetve a mintán.
    \item Ha a szöveg $k+j$-edik eleme megegyezik a minta $j$-edik karakterével, akkor léptetjük $j$-t (mivel a szövegben $k+j$-edik elemet nézzük, így elég $j$-t növelni).
    \item Ha nem egyeznek meg, akkor:
          \begin{itemize}
              \item Ha a minta már a szöveg végén van ($k=n-m$), akkor csak növeljük $k$-t eggyel, ami hamissá teszi a ciklus feltételt.
              \item Ha még nem vagyunk a szöveg végén $k$-t toljuk annyival, amennyivel lehet (ezt az előre beállított $Shift$ tömb határozza meg). És a $j$-t visszaállítjuk 1-re.
          \end{itemize}
    \item Addig megyünk, míg vagy a minta végére érünk $j$-vel, vagy a mintát továbbtoltuk a szöveg végénél. Előbbi esetben egyezést találtunk, míg az utóbbiban nem.
\end{itemize}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{img/BoyerMoore.jpg}
    \caption{QS}
    \label{fig:BoyerMoore}
\end{figure}
\subsection{Rabin-Karp algoritmus}
A Rabin-Karp algoritmus lényege, hogy minden betűhöz az ábécéből egy számjegyet rendelünk, és a keresést számok összehasonlításával végezzük. Világos, hogy ehhez egy ábécé méretnek megfelelő számrendszerre lesz szükségünk. A szövegből mindig a minta hosszával egyező részeket szelünk ki, és ezeket hasonlítjuk össze.\\

\noindent
Példa:\\
Minta: BBAC $\rightarrow$ 1102 \\
Szöveg: DACABBAC $\rightarrow$ 30201102, amiből a következő számokat állítjuk elő: 3020, 0201, 2011, 0110, 1102\\

\noindent
A fent látható szeletek lesznek az $s_i$-k.\\

\noindent
Az algoritmus működéséhez azonban számos apró ötletet alkalmazunk:
\begin{enumerate}
    \item A minta számokká alakítását Horner-módszer segítségével végezzük.
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.3\textwidth]{img/RK_Horner.jpg}
              \caption{RK - Horner-módszer}
              \label{fig:RK_Horner}
          \end{figure}
          Az $ord()$ függvény az egyes betűknek megfelelő számot adja vissza. A $d$ a számrendszer alapszáma.
    \item A szöveg mintával megegyező hosszú szeleteinek ($s_i$) előállítása: \\
          $s_0$-t a Horner-módszerrel ki tudjuk számolni. Ezek után $s_{i+1}$ a következőképp számolandó:
          \[s_{i+1} = (s_i - ord(S[i])\cdot d^{m-1})\cdot d  + ord(S[i+1])\]
          \textit{Magyarázat: $s_i$ elejéről levágjuk az első számjegyet ($s_i - ord(S[i])\cdot d^{m-1}$), majd a maradékot eltoljuk egy helyiértékkel (szorzás $d$-vel), végül az utolsó helyiértékre beírjuk a következő betűnek megfelelő számjegyet ($+ord(S[i+1])$)}

          Példa:

          Az előző példa szövegével és mintájával ($d=10$ elemű ábécé és $m=4$ hosszú minta): \\
          $s_0 = 3020$, ekkor: $s_{0+1} = s_1 = (3020 - ord(D) \cdot 10^3)\cdot 10 + ord(B) = (3020-3000)\cdot 10 +1 = 0201$
    \item Felmerülhet a kérdés, hogy az ilyen magas alapszámú számrendszerek nem okoznak-e gondot az ábrázolásnál? A kérdés jogos. Vegyük a következő életszerű példát:

          4 bájton ábrázoljuk a számainkat ($2^{32}$). Az abc legyen 32 elemű ($d=32$), a minta 8 hosszú ($m=8$). Ekkor a $d^{m-1}$ kiszámítása: $32^7 = (2^5)^7 = 2^{35}$ , ami már nem ábrázolható 4 bájton.

          Ennek kiküszöbölésére vezessünk be egy nagy $p$ prímet, melyre $d\cdot p$ még ábrázolható. És a műveleteket számoljuk {\it mod p}. Ekkor természetesen a kongruencia miatt lesz olyan eset, amikor az algoritmus egyezést mutat, mikor valójában nincs. Ez nem okoz gondot, mivel ilyen esetben karakterenkénti egyezést vizsgálva ezt a problémát kezelni tudjuk. (Fordított eset nem fordul elő tehát nem lesz olyan eset, mikor karakterenkénti egyezés van, de numerikus nincs). [Ha $p$ kellően nagy, a jelenség nagyon ritkán fordul elő.]

    \item A {\it mod p} számítás egy másik problémát is felvet. Ugyanis a kivonás alkalmával negatív számokat is kaphatunk.

          Például: Legyen $p=7$, ekkor, ha $ord(S[i]) = 9$, akkor előző számítás után $s_i = 2...$, de ebből $ord(S[i])\cdot d^{m-1} = 9\cdot 10^3 = 9000$-et vonunk ki negatív számot kapunk.

          Megoldásként $s_{i+1}$-et két lépésben számoljuk:
          \[s := (s_i+d\cdot p - ord(S[i])\cdot d^{m-1}) \quad mod \quad p \]
          \[s_{i+1} := (s\cdot d + ord(S[i+1])) \quad mod \quad p \]
\end{enumerate}
A fentiek alapján az algoritmus a következő (ld. \ref{fig:RK}. ábra)
\begin{enumerate}
    \item Kiszámoljuk $d^{m-1}$-et ($dm1$)
    \item Egy iterációban meghatározzuk Horner-módszerrel a minta számait ($x$) és $s_0$-t
    \item Ellenőrizzük, hogy egyeznek-e
    \item Addig számolgatjuk $s_i$ értékét míg a minta nem egyezik $s_i$-vel, vagy a minta a szöveg végére nem ért.
\end{enumerate}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{img/RK.jpg}
    \caption{RK}
    \label{fig:RK}
\end{figure}

\end{document}