6. Elemi algoritmusok¶

Rendezési reláció

Egy olyan bináris rendezésről van szó, amely

reflexív,
tranzitív,
antiszimmetrikus.

Jellemzően teljes rendezést szoktunk vizsgálni, melyre teljesül a linearitás is.

A sorozatokról megköveteljük, hogy bármely két eleme összehasonlítható legyen.

Figyelem

Az, hogy egy sorozat elemein értelmezve van egy rendezési reláció, hogy vagy a sorozat rendezett, az két külön fogalom.

\(T\) tulajdonság

Jelölje \(A\) egy sorozat elemeinek a halmazát. \(T\) tulajdonság alatt egy olyan függvényt értünk, amely az \(A\) minden eleméhez hozzárendel egy logikai értéket.

\[T: A \rightarrow \{igaz, hamis\}\]

\[\begin{split}T(a) = \begin{cases} \text{igaz}, & \text{ha }a \in A\text{ egy }T\text{ tulajdonságú elem}, \\ \text{hamis}, & \text{egyébként.} \\ \end{cases}\end{split}\]

Általános bináris művelet jelölése

Az algoritmusok egy részében egy konkrét bináris művelet helyett egy általánosat adunk meg, amelyet egy \(\square\) jellel jelölünk, például \(x \square y\).

Null elem

Főként inicializálásnál hasznos, hogy ha az adott művelethez meg tudjuk adni a null elemet, amelyre teljesül, hogy \(a \square Null = a\), bármilyen \(a \in A\) esetén.

Például:

\(A = \mathbb{R}, \square = +\) esetén \(Null = 0\).
\(A = \mathbb{R}, \square = \cdot\) esetén \(Null = 1\).
\(A = S, \square = \bullet\) esetében \(Null = ''\) (üres sztring, \(\varepsilon\)).

Elemi algoritmusok¶

Sorozatszámítás¶

A sorozat értékeit egy értékben „összesíti”.
Szokás még aggregációnak, redukciónak is nevezni.

\[\begin{split}&REDUCE(@X, @s) \\ &// Input: X sorozat, x_i \in A \\ &// Output: s \in A \\ &s \leftarrow Null \\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO} \\ &\quad s \leftarrow s \square x_i \\ &\text{RETURN}(s) \\\end{split}\]

\(\rhd\) Adjuk meg a szumma, produktum és a szövegek összefűzésének esetét!

Eldöntés¶

Egy sorozat elemeit vizsgáljuk meg, hogy teljesül-e rájuk valamilyen \(T\) tulajdonság.
Tulajdonképpen 2 algoritmusról van szó, amelyeket együtt érdemes említeni.

Létezik a sorozatban \(T\) tulajdonságú elem?

\[\begin{split}&\text{EXISTS}(@X, @van) \\ &// Input: X sorozat, x_i \in A \\ &// Output: Van \in \{igaz, hamis\} \\ &i \leftarrow 1 \\ &\text{WHILE }i \leq \text{Hossz}[X]\text{ AND }\overline{T(x_i)}\text{ DO}\\ &\quad \text{INC}(i)\\ &van \leftarrow (i \leq \text{Hossz}[X])\\ &\text{RETURN}(van)\\\end{split}\]

A sorozat minden eleme \(T\) tulajdonságú?

\[\begin{split}&\text{ALL}(@X, @mind) \\ &// Input: X sorozat, x_i \in A \\ &// Output: mind \in \{igaz, hamis\} \\ &i \leftarrow 1 \\ &\text{WHILE }i \leq \text{Hossz}[X]\text{ AND }T(x_i)\text{ DO}\\ &\quad \text{INC}(i)\\ &mind \leftarrow (i > \text{Hossz}[X])\\ &\text{RETURN}(mind)\\\end{split}\]

Kiválasztás¶

Egy \(T\) tulajdonságú elemet keres meg a sorozatban.
Az elem értékét, vagy indexét is visszaadhatja. (Az index esetünkben informatívabb, ezért itt most azt fogjuk visszaadni.)
Feltételezzük, hogy biztosan van \(T\) tulajdonságú elem a sorozatban.

\[\begin{split}&\text{FIND}(@X, @index)\\ &// Input: X sorozat, x_i \in A\\ &// Output: index \in \mathbb{N}\\ &i \leftarrow 1\\ &\text{WHILE }\overline{T(x_i)}\text{ DO}\\ &\quad \text{INC}(i)\\ &index \leftarrow i\\ &\text{RETURN}(index)\\\end{split}\]

Lineáris keresés¶

Az elem létezésének vizsgálatát és indexének a keresését kombinálja.

\[\begin{split}&\text{LINEAR_SEARCH}(@X, @van, @index)\\ &// Input: X sorozat, x_i \in A\\ &// Output: van \in \{igaz, hamis\}\\ &// \quad index \in \mathbb{N}\\ &i \leftarrow 1\\ &\text{WHILE }i \leq \text{Hossz}[X]\text{ AND }\overline{T(x_i)}\text{ DO}\\ &\quad \text{INC}(i)\\ &van \leftarrow (i \leq \text{Hossz}[X])\\ &\text{IF }van\\ &\quad \text{THEN }index \leftarrow i\\ &\text{RETURN}(van, index)\\\end{split}\]

Megszámlálás¶

A sorozatban a \(T\) tulajdonságú elemek számát adja vissza.

\[\begin{split}&\text{COUNT}(@X, @count)\\ &// Input: X sorozat, x_i \in A\\ &// Output: count \in \mathbb{Z}\\ &count \leftarrow 0\\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO}\\ &\quad \text{IF }T(x_i)\\ &\quad \quad \text{THEN INC}(count)\\ &\text{RETURN}(count)\\\end{split}\]

Maximum kiválasztás¶

Feltételezzük, hogy a sorozat elemein értelmezve van egy teljes rendezés.
A maximális értékű elem indexével térünk vissza.
Feltételezzük, hogy a sorozatnak legalább egy eleme van.

\[\begin{split}&\text{MAX}(@X, @index)\\ &// Input: X sorozat, x_i \in A\\ &// Output: index \in \mathbb{N},\text{ a maximális elem indexe}\\ &index \leftarrow 1\\ &\text{FOR }i \leftarrow 2\text{ TO Hossz}[X]\text{ DO}\\ &\quad \text{IF }x_i > x_{index}\\ &\quad \quad \text{THEN }index \leftarrow i\\ &\text{RETURN}(index)\\\end{split}\]

\(\rhd\) Hogy ha több maximális értékű elem is van, akkor melyik indexe kerül visszaadásra?

\(\rhd\) Hogyan kezelhető az üres sorozatok esete?

\(\rhd\) Hasonlóképpen adjuk meg a minimum számítását is!

Másolás¶

A bemeneti sorozatot transzformálást követően egy kimeneti sorozatba másolja át.
A transzformációt egy \(f: A \rightarrow B\) függvény formájában adhatjuk meg.

\[\begin{split}&\text{MAP}(@X, @Y)\\ &// Input: X sorozat, x_i \in A\\ &// Output: Y sorozat, y_i \in B\\ &\text{Hossz}[Y] \leftarrow \text{Hossz}[X]\\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO}\\ &\quad y_i \leftarrow f(x_i)\\ &\text{RETURN}(Y)\\\end{split}\]

Kiválogatás¶

A bemeneti sorozatból kigyűjtjük a \(T\) tulajdonságú elemeket a kimeneti sorozatba.

\[\begin{split}&\text{COLLECT}(@X, @Y)\\ &// Input: X sorozat, x_i \in A\\ &// Output: Y sorozat, y_i \in A\\ &\text{Hossz}[Y] \leftarrow 0\\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO}\\ &\quad \text{IF }T(x_i)\\ &\quad \quad \text{THEN INC}(\text{Hossz}[Y])\\ &\quad \quad \quad \quad \quad y_{\text{Hossz}[Y]} \leftarrow x_i\\ &\text{RETURN}(Y)\\\end{split}\]

\(\rhd\) Hasonlóképpen adható algoritmus az indexek kigyűjtésére is.

Szétválogatás¶

A \(T\) és nem \(T\) tulajdonságú elemeket külön sorozatokba gyűjti.

\[\begin{split}&\text{ASSORT}(@X, @Y, @Z)\\ &// Input: X sorozat, x_i \in A\\ &// Output: Y sorozat, y_i \in A\\ &// \quad \quad Z sorozat, y_i \in A\\ &\text{Hossz}[Y] \leftarrow 0\\ &\text{Hossz}[Z] \leftarrow 0\\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO}\\ &\quad \text{IF }T(x_i)\\ &\quad \quad \text{THEN INC}(\text{Hossz}[Y])\\ &\quad \quad \quad \quad \quad y_{\text{Hossz}[Y]} \leftarrow x_i\\ &\quad \quad \text{ELSE INC}(\text{Hossz}[Z])\\ &\quad \quad \quad \quad \quad z_{\text{Hossz}[Z]} \leftarrow x_i\\ &\text{RETURN}(Y, Z)\\\end{split}\]

Metszet¶

A két bemeneti sorozatról feltételezzük, hogy azokban csak különböző elemek vannak.
Tulajdonképpen a halmaz sorozat implementációját használjuk.
A bemenetként adott halmazok metszetét adjuk meg kimenetként.

\[\begin{split}&\text{INTERSECTION}(@X, @Y, @Z)\\ &// Input: X sorozat, x_i \in A\\ &// \quad \quad \quad \; Y sorozat, y_i \in A\\ &// Output: Z sorozat, z_i \in A\\ &\text{Hossz}[Z] \leftarrow 0\\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO}\\ &\quad j \leftarrow 1\\ &\quad \text{WHILE }(j \leq \text{Hossz}[Y])\text{ AND }(x_i \neq y_j)\text{ DO}\\ &\quad \quad \quad \text{INC}(j)\\ &\quad \text{IF }j \leq \text{Hossz}[Y]\\ &\quad \quad \text{THEN INC}(\text{Hossz}[Z])\\ &\quad \quad \quad \quad \quad z_{\text{Hossz}[Z]} \leftarrow x_i\\ &\text{RETURN}(Z)\\\end{split}\]

Egyesítés¶

A két bemeneti sorozatról feltételezzük, hogy azokban csak különböző elemek vannak.
Tulajdonképpen a halmaz sorozat implementációját használjuk.
A bemenetként adott halmazok unióját adjuk meg kimenetként.

\[\begin{split}&\text{UNION}(@X, @Y, @Z)\\ &// Input: X sorozat, x_i \in A\\ &// \quad \quad \quad \; Y sorozat, y_i \in A\\ &// Output: Z sorozat, z_i \in A\\ &\text{Hossz}[Z] \leftarrow \text{Hossz}[X]\\ &\text{FOR }i \leftarrow 1\text{ TO Hossz}[X]\text{ DO}\\ &\quad z_i \leftarrow x_i\\ &\text{FOR }j \leftarrow 1\text{ TO Hossz}[Y]\text{ DO}\\ &\quad i \leftarrow 1\\ &\quad \text{WHILE }(i \leq \text{Hossz}[X])\text{ AND }(x_i \neq y_j)\text{ DO}\\ &\quad \quad \quad \text{INC}(i)\\ &\quad \text{IF }i > \text{Hossz}[X]\\ &\quad \quad \text{THEN INC}(\text{Hossz}[Z])\\ &\quad \quad \quad \quad \quad z_{\text{Hossz}[Z]} \leftarrow y_j\\ &\text{RETURN}(Z)\\\end{split}\]

Összefuttatás¶

Két szigorúan monoton növekvő sorozatot egy harmadik rendezett sorozatba futtatunk/fűzünk össze.

\[\begin{split}&\text{MERGE}(@X, @Y, @Z)\\ &// Input: X sorozat, x_i \in A\\ &// \quad \quad \quad \; Y sorozat, y_i \in A\\ &// Output: Z sorozat, z_i \in A\\ &\text{Hossz}[Z] \leftarrow 0\\ &i \leftarrow 1\\ &j \leftarrow 1\\ &\text{WHILE }i \leq \text{Hossz}[X]\text{ AND }j \leq \text{Hossz}[Y]\text{ DO}\\ &\quad \text{INC}(\text{Hossz}[Z])\\ &\quad \text{CASE}\\ &\quad \quad x_i < y_j: z_{\text{Hossz}[Z]} \leftarrow x_i\\ &\quad \quad \quad \quad \quad \quad \text{INC}(i)\\ &\quad \quad x_i = y_j: z_{\text{Hossz}[Z]} \leftarrow x_i\\ &\quad \quad \quad \quad \quad \quad \text{INC}(i)\\ &\quad \quad \quad \quad \quad \quad \text{INC}(j)\\ &\quad \quad x_i > y_j: z_{\text{Hossz}[Z]} \leftarrow y_i\\ &\quad \quad \quad \quad \quad \quad \text{INC}(j)\\ &\text{WHILE }i \leq \text{Hossz}[X]\text{ DO}\\ &\quad \text{INC}(\text{Hossz}[Z])\\ &\quad z_{\text{Hossz}[Z]} \leftarrow x_i\\ &\quad \text{INC}(i)\\ &\text{WHILE }j \leq \text{Hossz}[Y]\text{ DO}\\ &\quad \text{INC}(\text{Hossz}[Z])\\ &\quad z_{\text{Hossz}[Z]} \leftarrow y_j\\ &\quad \text{INC}(j)\\ &\text{RETURN}(Z)\\\end{split}\]

Iteráció és rekurzió¶

Amennyiben egy problémát vissza tudunk vezetni egy azonos jellegű, de kisebb méretű problémára, akkor használhatunk rekurziót.

Faktoriális számítása¶

\[\begin{split}f(n) = \begin{cases} n \cdot f(n - 1), & \text{ha } n > 1,\\ 1, & \text{ha } n = 1.\\ \end{cases}\end{split}\]

Rekurzív változat:

\[\begin{split}&\text{FACTORIAL}(n, @result)\\ &// Input: n \in \mathbb{N}\\ &// Output: result \in \mathbb{N}\\ &\text{IF }n > 1\\ &\quad \text{THEN CALL FACTORIAL}(n - 1, result)\\ &\quad \quad \quad \quad result \leftarrow n \cdot result\\ &\quad \text{ELSE }result \leftarrow 1\\ &\text{RETURN}(result)\\\end{split}\]

Fibonacci számsorozat¶

A Fibonacci sorozat \(n\)-edik elemét szeretnénk kiszámolni.

\[\begin{split}&F_0 = 0\\ &F_1 = 1\\ &\ldots\\ &F_n = F_{n - 2} + F_{n - 1}\\\end{split}\]

Rekurzív változat:

\[\begin{split}&\text{FIBONACCI}(n, @result)\\ &// Input: n \in \mathbb{N}\\ &// Output: result \in \mathbb{N}\\ &\text{IF }n \geq 2\\ &\quad \text{THEN CALL FIBONACCI}(n - 2, a)\\ &\quad \quad \quad \quad \text{CALL FIBONACCI}(n - 1, b)\\ &\quad \quad \quad \quad result \leftarrow a + b\\ &\quad \text{ELSE } result \leftarrow n\\ &\text{RETURN}(result)\\\end{split}\]

Bináris keresés¶

Feltételezzük, hogy van egy rendezett sorozatunk.
A lineáris kereséshez hasonlóan egy elemet szeretnénk megkeresni a sorozatban.

\[\begin{split}&\text{BINARY_SEARCH}(@A, p, r, x, @index)\\ &// Input: A, \text{rendezett sorozat}\\ &// \quad \quad \quad p, r \in \mathbb{N}\\ &// \quad \quad \quad x, \text{ a keresett elem}\\ &// Output: index \in \mathbb{N}_0, \text{a keresett elem indexe}\\ &\text{IF }p + 1 < r\\ &\quad \text{THEN }q \leftarrow \left\lfloor \dfrac{p + r}{2}\right\rfloor\\ &\quad \quad \quad \text{IF } a_q = x\\ &\quad \quad \quad \quad \text{THEN }index \leftarrow q\\ &\quad \quad \quad \quad \text{ELSE IF }x < a_q\\ &\quad \quad \quad \quad \quad \quad \quad \quad \text{THEN CALL BINARY_SEARCH}(A, p, q, x, index)\\ &\quad \quad \quad \quad \quad \quad \quad \quad \text{ELSE CALL BINARY_SEARCH}(A, q, r, x, index)\\ &\quad \text{ELSE }index \leftarrow 0\\ &\text{RETURN}(index)\\\end{split}\]

Kérdések¶

Hogyan írható fel a halmaz különbség, mint algoritmus?
Hogyan írható fel a szimmetrikus differencia képzés, mint algoritmus?
Hogyan írható fel a faktoriális számítása iteratív alakban?
Hogyan írható fel az \(n.\) Fibonacci szám kiszámítása iteratív alakban?
Hogyan írható fel a bináris keresés iteratív alakban?

Feladatok¶

Pszeudókód, folyamatábra¶

A következő feladatokat oldjuk meg a pszeudókód felírásával és a folyamatábra felrajzolásával! (Minden esetben egy-egy procedúrát adjunk meg!)

Cseréljük ki két változó értékét!
Számoljuk meg egy sorozatban a páros számok darabszámát!
Számoljuk ki egy sorozatban a páratlan számok összegét!
Határozzuk meg a negatív számok maximumát!
Vizsgáljuk meg, hogy egy sorozat tartalmaz-e egy bizonyos elemet!
Vizsgáljuk meg, hogy egy sorozat rendezett-e!
Ellenőrizzük, hogy egy sorozat minden eleme egyedi!
Egy sorozatból gyűjtsük ki azon elemeket, amelyek megegyeznek az indexükkel!
Számoljuk meg, hogy egy bináris vektorban mennyi 0 és 1 érték van!
Két azonos hosszúságú bemeneti sorozatot fűzzünk össze úgy, hogy az első sorozat elemei a páratlan, a második sorozat elemei a páros indexekre kerüljenek.

Rekurzív függvények, procedúrák¶

Adottak a következő függvények!

\[\begin{split}f(n) = \begin{cases} 2 \cdot f(n - 3), & \text{ha } n > 20, \\ 5, & \text{egyébként. } \end{cases}\end{split}\]

\[\begin{split}g(n) = \begin{cases} g(n - 1) + 4 \cdot g(n - 2), & n > 0, \\ 8, & \text{egyébként. } \end{cases}\end{split}\]

Számítsuk ki az \(f(30)\) és \(g(5)\) értékeket!

Számítsuk ki az \(\binom{5}{3}\) értékét!

Használjuk fel hozzá a következő rekurzív összefüggést!

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]

Adjuk meg a procedúra pszeudó kódját, folyamatábráját! Ábrázoljuk a rekurzív hívási fát!