Programozási tételek

1. Összegzés Legyen H egy tetszőleges halmaz, amelyen értelmezett az összeadás művelete. Tegyük

fel, hogy létezik neutrális eleme a H-nak az összeadásra nézve (jelölje ezt 0), valamint adott az f : ℤ → H függvény. Adott [m, n] ⊂ ℤ intervallumon összegezzük az f függvény értékeit! Legyen ∑_{i=m}^{n} f(i) = 0, ha n < m.

A =ℤ m×ℤ n×H s

B ={ℤ \atop m′}×{ℤ \atop n′}

Q : (m = m′ ∧ n = n′)

R : (Q ∧ s = ∑_{i=m′}^{n′} f(i))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ k ∈ [m..n] ∪ {m − 1} ∧ s = ∑_{i=m}^{k} f(i))

k, s := m − 1, 0 ; k < n ; \overline{\frac{s := s + f(k + 1)}{k := k + 1}}

2. Számlálás Legyen β : ℤ → 𝕃, m, n ∈ ℤ. Számoljuk meg, hány helyen igaz β az [m, n] ⊂ ℤ

intervallumban. Legyen ∑_{i=m}^{n} χ(β(i)) = 0, ha n < m.

A =ℤ m×ℤ n×{ℕ_{0} \atop s}

B ={ℤ \atop m′}×{ℤ \atop n′}

Q : (m = m′ ∧ n = n′)

R : (Q ∧ s = ∑_{i=m′}^{n′} χ(β(i)))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ k ∈ [m..n] ∪ {m − 1} ∧ s = ∑_{i=m}^{k} χ(β(i)))

ahol χ : 𝕃 → ℕ_{0}, χ(a) = \{ \begin{matrix}1 & , a =↑ \\ 0 & , a =↓ \end{matrix} .

k, s := m − 1, 0 ; k < n ; \overline{\  β(k + 1)  / ; \begin{aligned}s := s + 1 \\ & SKIP \end{aligned} ; k := k + 1}

3. Feltételes összegzés Legyen β : ℤ → 𝕃, f : ℤ → ℤ, m, n ∈ ℤ. Összegezzük az f függvény értékeit az [m..n]

intervallum azon pontjaiban, amelyekben β feltétel igaz. Legyen ∑_{i=m}^{n} χ(β(i)) ∗ f(i) = 0, ha n < m.

A =ℤ m×ℤ n×{ℕ_{0} \atop s}

B ={ℤ \atop m′}×{ℤ \atop n′}

Q : (m = m′ ∧ n = n)

R : (Q ∧ s = ∑_{i=m′}^{n′} χ(β(i)) ∗ f(i))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ k ∈ [m..n] ∪ {m − 1} ∧ s = ∑_{i=m}^{k} χ(β(i)) ∗ f(i))

k, s := m − 1, 0 ; k < n ; \overline{\  β(k + 1)  / ; \begin{aligned}s := s + f(k + 1) \\ & SKIP \end{aligned} ; k := k + 1}

4. Maximumkeresés

Legyen (H, ≤) egy tetszőleges halmaz és f : ℤ → H egy függvény. Keressük meg az f függvény maximumát és egy olyan helyet, ahol ezt a maximumértéket felveszi egy adott [m, n] ⊂ ℤ intervallumban.

A =ℤ m×ℤ n×H h×ℤ i

B ={ℤ \atop m′}×{ℤ \atop n′}

Q : (m = m′ ∧ n = n′ ∧ m ≤ n)

R : (Q ∧ i ∈ [m..n] ∧ f(i) = h ∧ ∀j ∈ [m..n] : f(j) ≤ f(i))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ k ∈ [m..n] ∧ i ∈ [m, k] ∧ f(i) = h ∧ ∀j ∈ [m, k] : f(j) ≤ f(i))

i, k, h := m, m, f(m) ; k ≠ n ; \overline{\begin{aligned}\ h ≤ f(k + 1) \\ & \ h ≥ f(k + 1) \end{aligned} ; \begin{aligned}i, h := k + 1, f(k + 1) \\ & SKIP \end{aligned} ; k := k + 1}

5. Feltételes maximumkeresés

Legyen (H, ≤) tetszőleges halmaz és f : Z → H egy függvény, m, n ∈ ℤ és β : ℤ → 𝕃. Határozzuk meg, hogy van-e az [m, n] intervallumban olyan i pont, ahol β(i) érvényes, és ha van ilyen pont, akkor határozzuk meg a [β] ∩ [m, n] halmaz felett az f függvény maximumát és a halmaz egy olyan pontját, ahol f a maximum értékét felveszi.

A =ℤ m×ℤ n×ℤ i×H h×𝕃 l

B ={ℤ \atop m′}×{ℤ \atop n′}

Q : (m = m′ ∧ n = n′)

R : (Q ∧ (l ↔ (∃i ∈ [m..n] : β(i))) ∧ (l → (ε(m, n, i) ∧ f(i) = h)))

ahol ε(m, k, i) : (i ∈ [m, k] ∧ β(i) ∧ ∀j ∈ [m, k] : (β(j) → f(j) ≤ f(i))).

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q∧k ∈ [m..n]∪{m−1}∧(l ↔ (∃i ∈ [m, k] : β(i)))∧(l → (ε(m, k, i)∧f(i) = h)))

k, l := m − 1, ↓ ; k < n ; \overline{\¬β(k + 1) \  β(k + 1) ∧ l  \  β(k + 1) ∧ ¬l ; SKIP \frac{\begin{aligned}\  h ≤ f(k + 1) \\ & \ h ≥ f(k + 1) \end{aligned}}{\begin{aligned}i, h := k + 1, f(k + 1) \\ & SKIP \end{aligned}} l, i, h :=↑, k + 1, f(k + 1) ; k := k + 1}

6. Lineáris keresés Legyen m ∈ ℤ, β : ℤ → 𝕃. Keressük meg azt a legkisebb β tulajdonságú egész számot,

amely nem kisebb mint m. 6.1.

A =ℤ m×ℤ i

B ={Z \atop m′}

Q : (m = m′ ∧ ∃j ≥ m : β(j)) R : (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j))

6.1.1. Lineáris keresés 1. változat Keressük a megoldást adó programot ciklus formában, ahol P : (Q ∧ i ≥ m ∧ ∀j ∈ [m, i) : ¬β(j))

i := m ; ¬β(i) ; \overline{i := i + 1}

6.1.2. Lineáris keresés 2. változat Keressük a megoldást adó programot ciklus formában, ahol P : (Q ∧ i ≥ m − 1 ∧ (∀j ∈ [m, i) : ¬β(j)) ∧ l = ∃j ∈ [m, i] : β(j))

i, l := m − 1, ↓ ; ¬l ; \overline{\frac{l := β(i + 1)}{i := i + 1}}

6.2.

Tegyük fel, hogy β = γ ∨ δ és létezik i ≥ m, hogy β(i). Keressük meg a legkisebb olyan i-t, amire i ≥ m és β(i), és adjuk meg azt is, hogy γ(i), illetve δ(i) igaz-e!

6.2.1. Lineáris keresés 3. változat

A =ℤ m×ℤ i×𝕃 u×𝕃 v

B ={ℤ \atop m′}

Q : (m = m′ ∧ ∃j ≥ m′ : β(j))

R : (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ ∧ (u ↔ γ(i)) ∧ (v ↔ δ(i)))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ i ≥ m − 1 ∧ (u ↔ (∃j ∈ [m, i] : γ(j))) ∧ (v ↔ (∃j ∈ [m, i] : δ(j))) ∧ ∧ ∀j ∈ [m, i) : ¬β(j))

.

i, u, v := m − 1, ↓, ↓ ; ¬u ∧ ¬v ; \overline{\frac{u, v := γ(i + 1), δ(i + 1)}{i := i + 1}}

Megjegyzés: Nyilvánvaló, hogy (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ (u ↔ γ(i)) ∧ (v ↔ δ(i))) ⇒ (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ (u ↔ γ(i))), valamint (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ (u ↔ γ(i)) ∧ (v ↔ δ(i))) ⇒ (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ (v ↔ δ(i))). Ezért a fenti program

R′ : (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ (u ↔ γ(i))),

illetve

R′ : (Q ∧ i ≥ m′ ∧ β(i) ∧ ∀j ∈ [m′, i) : ¬β(j) ∧ (u ↔ γ(i)))

feltétel mellett is megoldja a feladatot. 6.2.2. Lineáris keresés 2.8. változat

Legyen γ : ℤ → 𝕃, m, n ∈ ℤ. Adjuk meg, hogy van-e az [m..n] intervallumban olyan egész szám, amelyre γ igaz, és ha van, akkor keressük meg az első ilyen tulajdonságú helyet. Ez a 3. változat speciális esete δ(j) = (j ≥ n) választással. Ennek megfelelően a következők érvényesek:

A =ℤ m×ℤ n×ℤ i×𝕃 u

B ={ℤ \atop m′}×{ℤ \atop n′}

Q : (m = m′ ∧ n = n′)

R : (Q ∧ i ≥ m′ ∧ (γ(i) ∨ i ≥ n′) ∧ ((∀j ∈ [m′, i) : ¬γ(j)) ∧ (∀j ∈ [m′, i) : j < n)) ∧ ∧ (u ↔ γ(i)))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ m ≤ n ∧ i ≥ m − 1 ∧ (u ↔ (∃j ∈ [m, i] : γ(j))) ∧ ∧ ((∀j ∈ [m, i) : ¬γ(j)) ∧ (∀j ∈ [m, i) : j < n)))

\frac{\  m ≤ n  /}{i, u := m − 1, ↓ ; ¬u ∧ i < n ; \overline{\frac{u := γ(i + 1)}{i := i + 1}} ; i, u := m, γ(m)}

Ha valódi intervallumban keresünk, azaz

Q : (m = m′ ∧ n = n′ ∧ m ≤ n)

feltételből indulunk ki, akkor az előzőek alapján, a keresett program:

i, u := m − 1, ↓ ; ¬u ∧ i < n ; \overline{\frac{u := γ(i + 1)}{i := i + 1}}

Ebben az esetben könnyen belátható, hogy

(Q ∧ i ≥ m′ ∧ (γ(i) ∨ i ≥ n′) ∧ ((∀j ∈ [m′, i) : ¬γ(j)) ∧ (∀j ∈ [m′, i) : j < n)) ∧ ∧ (u ↔ γ(i))) ⇒ (Q ∧ (u ↔ ∃j ∈ [m′..n′] : γ(j)) ∧ (u → (i ∈ [m′..n′] ∧ γ(i) ∧ ∀j ∈ [m′..i) : ¬γ(j)))), valamint (Q ∧ i ≥ m′ ∧ (γ(i) ∨ i ≥ n′) ∧ ((∀j ∈ [m′, i) : ¬γ(j)) ∧ (∀j ∈ [m′, i) : j < n)) ∧ ∧ (u ↔ γ(i))) ⇒ (Q ∧ (u ↔ ∃j ∈ [m′..n′] : γ(j)) ∧ ∧(u → (i ∈ [m′..n′] ∧ γ(i) ∧ ∀j ∈ [m′..i) : ¬γ(j))) ∧ (¬u → i = n′)).

Tehát a fenti program R′ : (Q ∧ (u ↔ ∃j ∈ [m′..n′] : γ(j)) ∧ (u → (i ∈ [m′..n′] ∧ γ(i) ∧ ∀j ∈ [m′..i) : ¬γ(j)))),

valamint

R′ : (Q ∧ (u ↔ ∃j ∈ [m′..n′] : γ(j)) ∧ ∧(u → (i ∈ [m′..n′] ∧ γ(i) ∧ ∀j ∈ [m′..i) : ¬γ(j))) ∧ (¬u → i = n′))

feltételek mellett is megoldja a feladatot, ugyanakkor ez utóbbi feltételek direkt módon fejezi ki a megoldandó problémát. Természtesen ez utóbbi feltételekből kiindulva a levezetések a lineáris keresés 3. változatára történő visszautalás nélkül is elkészíthetőek.

7. Logaritmikus keresés

Legyen H egy olyan halmaz, amin értelmezve van egy rendezési reláció. Legyen f : ℤ → H monoton növekedő függvény. Döntsük el egy adott h ∈ H értékről, hogy felveszi-e azt az f függvény egy adott [m, n] ⊂ ℤ intervallumon, és ha igen, akkor adjuk meg egy olyan pontját, ahol a függvényérték h.

A =ℤ m×ℤ n×ℤ i×H h×𝕃 l

B ={ℤ \atop m′}×{ℤ \atop n′}×{H \atop h′}

Q : (m = m′ ∧ n = n′ ∧ h = h′ ∧ ∀j, k ∈ [m′..n′] : j ≤ k → f(j) ≤ f(k))

R : (Q ∧ l = (∃j ∈ [m′..n′] : f(j) = h′) ∧ (l → (i ∈ [m′..n′] ∧ f(i) = h′)))

Keressük a megoldást adó programot ciklus formában, ahol

P : (Q ∧ [u, v] ⊆ [m..n] ∧ ∀j ∈ [m..n] \ [u, v] : f(j) ≠ h ∧ (l → (i ∈ [u, v] ∧ f(i) = h)))

u, v, l := m, n, ↓ ; ¬l ∧ (u ≤ v) ; \overline{i := [(u + v)/2] ; \ f(i) < h \ f(i) > h \ f(i) = h ; u := i + 1  v := i − 1  l :=↑}

8. Speciális formában adott függvény értékének kiszámítása adott helyen

8.1. Függvénykompozícióval definiált függvény

Legyenek H_{1}, H_{2}, H_{3} tetszőleges halmazok, továbbá f : H_{1} → H_{3}, g : H_{1} → H_{2}, h : H_{2} → H_{3} olyan függvények, hogy f = h ∘ g. Határozzuk meg az f függvény v ∈ H_{1} helyen felvett értékét.

A ={H_{1} \atop v}×{H_{3} \atop z}

B ={H_{1} \atop v′}

Q : (v = v′)

R : (Q ∧ z = f(v′))

\frac{w := g(v)}{z := h(w)}

8.2. Esetszétválasztásos függvény

Legyen H egy tetszőleges halmaz, f : ℤ → H, h_{1},…, h_{k} : ℤ → H, π_{1},…, π_{k} : ℤ → 𝕃, amelyekre

f(i) := \{ \begin{matrix}h_{1}(i) & , ha π_{1}(i) \\ ⋮ & ⋮ \\ h_{k}(i) & , ha π_{k}(i) \end{matrix}

Határozzuk meg az f parciális függvény v helyen felvett értékét!

A =ℤ v×H z

B ={ℤ \atop v′}

Q : (v = v′ ∧ v′ ∈ ⋃_{j=1}^{k}[π_{j}])

R : (Q ∧ z = f(v′))

\frac{\ π_{1}(v)  \ … \ π_{k}(v)}{z := h_{1}(v)  …  z := h_{k}(v)}

8.3. Rekurzív formulával definiált függvény

Legyen H egy tetszőleges halmaz, k ∈ ℕ, f : ℤ → H, h : ℤ × H^{k} → H olyan függvények, hogy f(t_{0}) = f_{0}, f(t_{0} − 1) = f_{−1}, …, f(t_{0} − k + 1) = f_{−k+1} (t_{0} ∈ ℤ) és ∀i ≥ t_{0} : f(i + 1) = h(i + 1, f(i),…, f(i − k + 1)). Határozzuk meg az f függvény n > t_{0} helyen felvett értékét.

A =ℤ n×H z

B ={ℤ \atop n′}

Q : (n = n′ ∧ n ≥ t_{0})

R : (Q ∧ z = f(n′))

Keressük a megoldást adó programot ciklus formában, ahol P : (Q ∧ t_{0} ≤ i ≤ n ∧ z = f(i) ∧ z_{−1} = f(i − 1) ∧… ∧ z_{−k+1} = f(i − k + 1))

i, z, z_{−1}, .., z_{−k+1} := t_{0}, f_{0}, f_{−1}, .., f_{−k+1} ; i ≠ n ; \overline{\frac{z, z_{−1}, .., z_{−k+1} := h(i + 1, z,…, z_{−k+1}), z, .., z_{−k+2}}{i := i + 1}}

8.4. Elemenként feldolgozható függvény Legyenek E, F_{i} (i = 1,…, m) tetszőleges halmazok, m, n ∈ ℕ tetszőlegesek.

\begin{matrix}X = & X_{1} ×… × X_{n}  (X_{i} ⊆ 2^{E} (i = 1,…, n)) \\ Y = & Y_{1} ×… × Y_{m}  (Y_{i} ⊆ 2^{F_{i}} (i = 1,…, m)) \end{matrix}

Definíció: Azt mondjuk, hogy \overline{x}, \overline{\overline{x}} ∈ X teljesen diszjunkt felbontása x ∈ X-nek, ha i) ∀i ∈ [1, n] : x_{i} = \overline{x}_{i} ∪ \overline{\overline{x}}_{i} és ii) ∀i, j ∈ [1, n] : \overline{x}_{i} ∩ \overline{\overline{x}}_{j} = ∅.

Definíció: Legyen f : X → Y. Ha bármely x ∈ X bármely \overline{x}, \overline{\overline{x}} teljesen diszjunkt felbontására

i) f(\overline{x}) ∪ f(\overline{\overline{x}}) = f(x) és ii) f(\overline{x}) ∩ f(\overline{\overline{x}}) = (∅, ..., ∅), akkor f-et elemenként feldolgozhatónak nevezzük.

Megjegyzés:

1. Az ∪ és ∩ műveletek komponensenként értendők.

2. f(x) = (f_{1}(x),…, f_{m}(x)) jelölést alkalmazva, ahol

f_{j}(x) : X → Y_{j}, j = 1,…, m ,

könnyen látható, hogy az f_{1}(x),…, f_{m}(x) függvénnek mind elemenként feldolgozhatóak.

8.4.1. Egyváltozós egyértékű elemenkénti feldolgozás

Legyen f : X → Y (n = 1, m = 1) elemenként feldolgozható függvény. Határozzuk meg az f függvény értékét valamely x ∈ X pontban.

A =X x×Y y

B ={X \atop x′}

Q : (x = x′)

R : (y = f(x′))

Keressük a megoldást adó programot ciklus formában, ahol

P : (y ∪ f(x) = f(x′) ∧ y ∩ f(x) = ∅)

y := ∅ ; x ≠ ∅ ; \overline{e :∈ (x) ; y := y˜∪f(\{e\}) ; x := x ≃ \{e\}}

Megjegyzés: ˜∪ a diszjunkt unió, ≃ valamely halmaz és egy eleme, mint halmaz közötti különbség műveletét jejöli.

8.4.2. Kétváltozós egyértékű elemenkénti feldolgozás Legyen f : X → Y (n = 2, m = 1) elemenként feldolgozható függvény.

A ={X_{1} \atop x_{1}}×{X_{2} \atop x_{2}}×Y y

B ={X_{1} \atop x′_{1}}×{X_{2} \atop x′_{2}}

Q : (x_{1} = x′_{1} ∧ x_{2} = x′_{2}) R : (y = f(x′_{1}, x′_{2})) Keressük a megoldást adó programot ciklus formában, ahol P : (y ∪ f(x_{1}, x_{2}) = f(x′_{1}, x′_{2}) ∧ y ∩ f(x_{1}, x_{2}) = ∅)

y := ∅ ; x_{1} ≠ ∅ ∨ x_{1} ≠ ∅ ; \overline{e :∈ (x_{1} ∪ x_{2}) ; \ e ∈ x_{1} ∧ e ∉ x_{2} \ e ∉ x_{1} ∧ e ∈ x_{2} \ e ∈ x_{1} ∧ e ∈ x_{2} ; y, x_{1} := ; y˜∪f(\{e\}, ∅), ; x_{1} ≃ \{e\}  y, x_{2} := ; y˜∪f(∅, \{e\}), ; x_{2} ≃ \{e\}  y, x_{1}, x_{2} := ; y˜∪f(\{e\}, \{e\}), ; x_{1} ≃ \{e\}, ; x_{2} ≃ \{e\}}

8.4.3. Egyváltozós kétértékű elemenkénti feldolgozás

Legyen f : X → Y (n = 1, m = 2), elemenként feldolgozható függvény, f_{1} : X → Y_{1}, f_{2} : X → Y_{2}, f = (f_{1}, f_{2}).

A =X x×{Y_{1} \atop y_{1}}×{Y_{2} \atop y_{2}}

B ={X \atop x′}

Q : (x = x′) R : (y_{1} = f_{1}(x′) ∧ y_{2} = f_{2}(x′)) Keressük a megoldást adó programot ciklus formában, ahol P : (y_{1} ∪ f_{1}(x) = f_{1}(x′) ∧ y_{1} ∩ f_{1}(x) = ∅ ∧ y_{2} ∪ f_{2}(x) = f_{2}(x′) ∧ y_{2} ∩ f_{2}(x) = ∅)

y_{1}, y_{2} := ∅, ∅ ; x ≠ ∅ ; \overline{e :∈ (x) ; y_{1}, y_{2} := y_{1}˜∪f_{1}(\{e\}), y_{2}˜∪f_{2}(\{e\}) ; x := x ≃ \{e\}}

8.4.4. n változós, m értékű elemenkénti feldolgozás

Legyen f : X → Y (n, m ∈ ℕ), elemenként feldolgozható függvény, f_{1} : X → Y_{1},…, f_{n} : X → Y_{n}, f = (f_{1},…, f_{n}).

A ={X_{1} \atop x_{1}}× ⋯×{X_{n} \atop x_{n}} ×{Y_{1} \atop y_{1}}× ⋯×{Y_{m} \atop y_{m}}

B ={X_{1} \atop x′_{1}}× ⋯×{X_{n} \atop x′_{n}}

Q : (x_{1} = x′_{1} ∧ ⋯ ∧ x_{n} = x′_{n}) R : (y_{1} = f_{1}(x′_{1},…, x′_{n}) ∧ ⋯ ∧ y_{m} = f_{m}(x′_{1},…, x′_{n})) Keressük a megoldást adó programot ciklus formában, ahol P : (∀j ∈ [1..m] : (y_{j} ∪ f_{j}(x_{1},…, x_{n}) = f_{j}(x′_{1},…, x′_{n}) ∧ y_{j} ∩ f_{j}(x_{1},…, x_{n}) = ∅)

y_{1},…, y_{m} := ∅,…, ∅ ; ∨_{i=1}^{n}x_{i} ≠ ∅ ; \overline{e :∈ ( ⋃_{i=1}^{n} x_{i}) ; \… \  e ∈ x_{i_{1}} ∧… e ∈ x_{i_{k}} ∧ e ∉ x_{i_{k+1}} ∧ e ∉ x_{i_{n}}  \…; …  y_{1},…, y_{m}, x_{i_{1}},…, x_{i_{k}} := ; y_{1}˜∪f_{1}(sl(x, e)),…, y_{m}˜∪f_{m}(sl(x, e)), ; x_{i_{1}} ≃ \{e\},…, x_{i_{k}} ≃ \{e\}  …}

ahol i_{1},…, i_{k} ∈ {1,…, n} különbözőek, sl : X × E → X,

sl(x, e)_{i} = \{ \begin{matrix}\{e\}, & ha e ∈ x_{i} \\ ∅, & különben \end{matrix}

Az elágazás ”ágainak” száma 2^{n} − 1.