Kihagyás

2. gyakorlat

A Program

A program definíciója

\(S \subseteq A \times (\overline{A} \cup \{fail\})^{**}\)

\(\overline{A}\):

  • \(A\) és egyéb komponensek (segédváltozóknak)
  • \(\overline{A} = \bigcup B \quad\quad A < B\)

Az állapot elemeihez rendel hozzá a halmaz elemeiből képzett véges vagy végtelen sorozatokat

Program kritériumjai

  1. A programnak minden állapotból el kell tudnia indulni
\[ \Updownarrow \]

"Minden állapot kiinduló állapot."

\[ \Updownarrow \]

\(\mathcal{D}_S = A\)

  1. A végrahajtás első állapota a kiinduló állapot.
  2. A \(fail\) csak egy végrehajtás végén lehet
  3. A végrehajtás utolsó állapota \(A\)-beli, vagy \(fail\)

Program függvény

Megmutatja, hogy az adott program honnan, hova tud eljutni

\(P(S)\) - Az S program programfüggvénye

Szintén homogén, binér reláció: \(P(S) \subseteq A \times A\)

A programnak csak a helyes működését írja le.

  • Végtelen ciklussal rendelkező állapotra nem
  • \(fail\)-re jutó állapotra nem

Például:

  • \(P(S) = \{0 \to 0, 1 \to 1 \; 2, 4 \to 2\}\)

Valójában nem függvény, mert nem determinisztikus, nem egyértelmű.

  • De így marad a fogalom ~~(mert begyöpösödött oktatók)~~
  • Egyszerűen legacy ~~(ez is)~~.

A program megoldja-e a feladatot? Összehasonlítjuk a feladatot és a program függvényt.

É.T.: \(D_{P(S)} = \{a \in A \; | \; S(a) \subseteq (\overline A)^*\}\)

Nem tartalmazhat fail-t és nem lehet végtelen

\(P(S)(a) = \{c \in A \; | \; \exists \alpha \in S(a)\}\)

Ahol \(\alpha _ {|\alpha|} = c\)

\(D_{P(S)} = \{0,1,4\}\)

\(P(S)(0) = \{0\}\)

\(P(S)(1) = \{1,2\}\)

\(P(S)(4) = \{2\}\)

Megoldás

A program akkor oldja meg a feladatot, hogy ha programot elindítjuk a feladat kezdőállapotaiból, akkor a program terminál, és ott, ahova a feladat képez.

  1. \(D_F \subseteq D_{P(S)}\)
  2. \(\forall a \in D_{F}: P(S)(a) \subseteq F(a)\)
  3. Ha a program "megtalája" a feladat legalább egy megoldását

Például: Az előbb használt program, és az \(F=\{(0,0),(0,1),(1,2),(1,4)\}\) feladat

\(\{0,1\} = D_F \subseteq D_{P(S)} = \{0,1,4\}\)

\(\{0\} = P(S)(0) \subseteq F(0) = \{0,1\}\)

\(\{1,2\} = P(S)(1) \not\subseteq F(1) = \{2,4\}\)

Tehát ez a program nem oldja meg a feladatot.

Példa 1

Program

\(A = [1..5]\)

\(S = \{(a, <a>)\} \cup \{(a, <a, \; a+1>) \; | \; a \leq 4\} \cup \{(a, <a,a,\dots>) \; | \; a = 3\}\)

  • Az első reláció: \(a\)-hoz rendelje hozzá az \(a\)-t tartalmazó listát
  • A második reláció: \(a\)-hoz rendelje hozzá a \(<a, a+1>\) listát, ha \(a \leq 4\)
  • A harmadik reláció: \(a\)-hoz hozzárendeli az \(a\)-kat tartalmazó végtelen listát, ha \(a=3\)

a. \(S(3) = \{<3>, <3,4>, <3, 3, 3, \ldots>\}\)

b. \(|S| = 10 = 2 + 2 + 3 + 2 + 1\)

c. \(D_{P(S)} = \{1,2,4,5\}\)

(3 esetén végtelen ciklusba fut)

d. \(P(S)(3) = \varnothing\)

e. \(|P(S)| = 7\)

  • \(P(S)=\{1 \to 1 \; 2, 2 \to 2 \; 3, 4 \to 4 \;5, 5 \to 5\}\)

f. Feladatok amiket megold ez a program:

  • \(P(S)\)
  • \(\varnothing\)
  • \(F = \{1 \to 1, 1 \to 2, 1 \to 3\}\)

Az üres feladatot minden program megoldja.

Példa 2

\(A = [-5..\infin)\)

A programot jelöljük \(S\)-sel

while a != 10:
    a := a + sgn(a) # előjel függvény

Próba futtatások:

  • \(12 \to <12, 13, 14, \dots>\)
  • \(10 \to <10>\)
  • \(6 \to <6, 7, 8, 9, 10>\)
  • \(0 \to <0, 0, \dots>\)
  • \(-3 \to <-3, -4, -5, \; fail>\)

Mi a program függvény?

É.T.: \(D_{P(S)} = [1..10]\)

Képhalmaz: \(\forall a \in D_{P(S)} : P(S)(a) = \{10\}\)

Példa 3

Határozzuk meg egy összetett természetes számnek egy valódi természetes osztóját

\(A = (n: \N, d: \N)\)

\(F = \{(x, *) \to (*, y) \; | \; x \text{ összetett} \land y | x \land y \ne 1 \land y \ne x\}\)

d = 2
while n%d != 0:
    d = d + 1

\(D_F = \{(x, *) | x \text{ összetett}\}\)

\(F(x, *) = \{(*, y) | y | x \; \land \; y \neq 1 \; \land \; y \neq x\}\)

\(D_{P(S)} = \{(x, *) \; | \; x \neq 1\}\)

  • \(n=1\) esetén a program végtelen ciklusba kerül, hiszen semelyik \(\geq2\) szám nem osztója az 1-nek

\(P(S)(x, *) = \{(x, y) \; | \; y=min\{z \in \N\ \; | \; z|x \land 1 > 1\} \}\)

  1. \(D_F \subseteq D_{P(S)}\)
  2. \(\forall (x, *) \in D_F:P(S)(x, *) \subseteq F(x, *)\)
    • A legkisebb közös osztó IS egy osztó, úgyhogy megoldja a feladatot.

Példa 4

\(A = (n: \N, d: \N)\)

d \in {n-1, n-2}
while n mod d != 0:
    d := d-1

\(D_{P(S)} = \{(x, *) \; | \; x \geq 3 \}\)

\(P(S)(x, *) = \{(x, y) \; | \; y = max\{z \in \N \; | \; z | x \; \land \; z < x\}\}\)

Fogalmak (kövi heti röpzh-ra)

  • állapot
  • állapottér
  • program
  • program függvény
  • megoldás