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 \to {i g a z, h a m i s}

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

Á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 $◻$ jellel jelölünk, például $x ◻ 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 ◻ N u l l = a$ , bármilyen $a \in A$ esetén.

Például:

$A = R, ◻ = +$ esetén $N u l l = 0$ .
$A = R, ◻ = \cdot$ esetén $N u l l = 1$ .
$A = S, ◻ = ∙$ esetében $N u l l =^{″}$ (üres sztring, $ε$ ).

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{aligned} R E D U C E (@ X, @ s) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : s \in A \\ s \leftarrow N u l l \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ s \leftarrow s ◻ x_{i} \\ RETURN (s) \end{aligned}

$⊳$ 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{aligned} EXISTS (@ X, @ v a n) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : V a n \in {i g a z, h a m i s} \\ i \leftarrow 1 \\ WHILE i \leq Hossz [X] AND \overset{―}{T (x_{i})} DO \\ INC (i) \\ v a n \leftarrow (i \leq Hossz [X]) \\ RETURN (v a n) \end{aligned}

A sorozat minden eleme $T$ tulajdonságú?

\begin{aligned} ALL (@ X, @ m i n d) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : m i n d \in {i g a z, h a m i s} \\ i \leftarrow 1 \\ WHILE i \leq Hossz [X] AND T (x_{i}) DO \\ INC (i) \\ m i n d \leftarrow (i > Hossz [X]) \\ RETURN (m i n d) \end{aligned}

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{aligned} FIND (@ X, @ i n d e x) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : i n d e x \in N \\ i \leftarrow 1 \\ WHILE \overset{―}{T (x_{i})} DO \\ INC (i) \\ i n d e x \leftarrow i \\ RETURN (i n d e x) \end{aligned}

Lineáris keresés¶

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

\begin{aligned} LINEAR_SEARCH (@ X, @ v a n, @ i n d e x) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : v a n \in {i g a z, h a m i s} \\ / / i n d e x \in N \\ i \leftarrow 1 \\ WHILE i \leq Hossz [X] AND \overset{―}{T (x_{i})} DO \\ INC (i) \\ v a n \leftarrow (i \leq Hossz [X]) \\ IF v a n \\ THEN i n d e x \leftarrow i \\ RETURN (v a n, i n d e x) \end{aligned}

Megszámlálás¶

A sorozatban a $T$ tulajdonságú elemek számát adja vissza.

\begin{aligned} COUNT (@ X, @ c o u n t) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : c o u n t \in Z \\ c o u n t \leftarrow 0 \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ IF T (x_{i}) \\ THEN INC (c o u n t) \\ RETURN (c o u n t) \end{aligned}

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{aligned} MAX (@ X, @ i n d e x) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : i n d e x \in N, a maximális elem indexe \\ i n d e x \leftarrow 1 \\ FOR i \leftarrow 2 TO Hossz [X] DO \\ IF x_{i} > x_{i n d e x} \\ THEN i n d e x \leftarrow i \\ RETURN (i n d e x) \end{aligned}

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

$⊳$ Hogyan kezelhető az üres sorozatok esete?

$⊳$ 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 \to B$ függvény formájában adhatjuk meg.

\begin{aligned} MAP (@ X, @ Y) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : Y s o r o z a t, y_{i} \in B \\ Hossz [Y] \leftarrow Hossz [X] \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ y_{i} \leftarrow f (x_{i}) \\ RETURN (Y) \end{aligned}

Kiválogatás¶

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

\begin{aligned} COLLECT (@ X, @ Y) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : Y s o r o z a t, y_{i} \in A \\ Hossz [Y] \leftarrow 0 \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ IF T (x_{i}) \\ THEN INC (Hossz [Y]) \\ y_{Hossz [Y]} \leftarrow x_{i} \\ RETURN (Y) \end{aligned}

$⊳$ 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{aligned} ASSORT (@ X, @ Y, @ Z) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / O u t p u t : Y s o r o z a t, y_{i} \in A \\ / / Z s o r o z a t, y_{i} \in A \\ Hossz [Y] \leftarrow 0 \\ Hossz [Z] \leftarrow 0 \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ IF T (x_{i}) \\ THEN INC (Hossz [Y]) \\ y_{Hossz [Y]} \leftarrow x_{i} \\ ELSE INC (Hossz [Z]) \\ z_{Hossz [Z]} \leftarrow x_{i} \\ RETURN (Y, Z) \end{aligned}

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{aligned} INTERSECTION (@ X, @ Y, @ Z) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / Y s o r o z a t, y_{i} \in A \\ / / O u t p u t : Z s o r o z a t, z_{i} \in A \\ Hossz [Z] \leftarrow 0 \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ j \leftarrow 1 \\ WHILE (j \leq Hossz [Y]) AND (x_{i} \neq y_{j}) DO \\ INC (j) \\ IF j \leq Hossz [Y] \\ THEN INC (Hossz [Z]) \\ z_{Hossz [Z]} \leftarrow x_{i} \\ RETURN (Z) \end{aligned}

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{aligned} UNION (@ X, @ Y, @ Z) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / Y s o r o z a t, y_{i} \in A \\ / / O u t p u t : Z s o r o z a t, z_{i} \in A \\ Hossz [Z] \leftarrow Hossz [X] \\ FOR i \leftarrow 1 TO Hossz [X] DO \\ z_{i} \leftarrow x_{i} \\ FOR j \leftarrow 1 TO Hossz [Y] DO \\ i \leftarrow 1 \\ WHILE (i \leq Hossz [X]) AND (x_{i} \neq y_{j}) DO \\ INC (i) \\ IF i > Hossz [X] \\ THEN INC (Hossz [Z]) \\ z_{Hossz [Z]} \leftarrow y_{j} \\ RETURN (Z) \end{aligned}

Összefuttatás¶

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

\begin{aligned} MERGE (@ X, @ Y, @ Z) \\ / / I n p u t : X s o r o z a t, x_{i} \in A \\ / / Y s o r o z a t, y_{i} \in A \\ / / O u t p u t : Z s o r o z a t, z_{i} \in A \\ Hossz [Z] \leftarrow 0 \\ i \leftarrow 1 \\ j \leftarrow 1 \\ WHILE i \leq Hossz [X] AND j \leq Hossz [Y] DO \\ INC (Hossz [Z]) \\ CASE \\ x_{i} < y_{j} : z_{Hossz [Z]} \leftarrow x_{i} \\ INC (i) \\ x_{i} = y_{j} : z_{Hossz [Z]} \leftarrow x_{i} \\ INC (i) \\ INC (j) \\ x_{i} > y_{j} : z_{Hossz [Z]} \leftarrow y_{i} \\ INC (j) \\ WHILE i \leq Hossz [X] DO \\ INC (Hossz [Z]) \\ z_{Hossz [Z]} \leftarrow x_{i} \\ INC (i) \\ WHILE j \leq Hossz [Y] DO \\ INC (Hossz [Z]) \\ z_{Hossz [Z]} \leftarrow y_{j} \\ INC (j) \\ RETURN (Z) \end{aligned}

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{array}{r} f (n) = {\begin{cases} n \cdot f (n - 1), & ha n > 1, \\ 1, & ha n = 1. \end{cases} \end{array}

Rekurzív változat:

\begin{aligned} FACTORIAL (n, @ r e s u l t) \\ / / I n p u t : n \in N \\ / / O u t p u t : r e s u l t \in N \\ IF n > 1 \\ THEN CALL FACTORIAL (n - 1, r e s u l t) \\ r e s u l t \leftarrow n \cdot r e s u l t \\ ELSE r e s u l t \leftarrow 1 \\ RETURN (r e s u l t) \end{aligned}

Fibonacci számsorozat¶

A Fibonacci sorozat $n$ -edik elemét szeretnénk kiszámolni.

\begin{aligned} F_{0} = 0 \\ F_{1} = 1 \\ \dots \\ F_{n} = F_{n - 2} + F_{n - 1} \end{aligned}

Rekurzív változat:

\begin{aligned} FIBONACCI (n, @ r e s u l t) \\ / / I n p u t : n \in N \\ / / O u t p u t : r e s u l t \in N \\ IF n \geq 2 \\ THEN CALL FIBONACCI (n - 2, a) \\ CALL FIBONACCI (n - 1, b) \\ r e s u l t \leftarrow a + b \\ ELSE r e s u l t \leftarrow n \\ RETURN (r e s u l t) \end{aligned}

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{aligned} BINARY_SEARCH (@ A, p, r, x, @ i n d e x) \\ / / I n p u t : A, rendezett sorozat \\ / / p, r \in N \\ / / x, a keresett elem \\ / / O u t p u t : i n d e x \in N_{0}, a keresett elem indexe \\ IF p + 1 < r \\ THEN q \leftarrow ⌊ \frac{p + r}{2} ⌋ \\ IF a_{q} = x \\ THEN i n d e x \leftarrow q \\ ELSE IF x < a_{q} \\ THEN CALL BINARY_SEARCH (A, p, q, x, i n d e x) \\ ELSE CALL BINARY_SEARCH (A, q, r, x, i n d e x) \\ ELSE i n d e x \leftarrow 0 \\ RETURN (i n d e x) \end{aligned}

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{array}{r} f (n) = {\begin{cases} 2 \cdot f (n - 3), & ha n > 20, \\ 5, & egyébként. \end{cases} \end{array}

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

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!