Kihagyás

1. gyakorlat

"Ne tévelyedjünk el, ez matematika óra." ~ Gregó

A feladat matematikai modellje

Állapottér

\[ x, y, z \in \R \]
\[ \{s:x, \; t:y, \; v:z\} \]
\[ \Updownarrow \]
\[ (x, y, z) \text{, de ez sorrend függő} \]

Az \(s\) változó egy \(x\) értéket vesz fel, a \(t\) változó egy \(y\) értéket, a \(v\) változó egy \(z\) értéket.

Az állapottér az össze állapotnak a halmaza:

\[ \{\{s:x, \; t:y, \; v:z\} \; |\; x, y, z \in \R\} = \]
\[ (s: \R, t: \R, v: \R) = A \]

\(a\) egy állapot. Pl. \(a \in A\) esetén \(s(a) = x\)

1. példa feladat

Egyenes vonalú egyenletes mozgást végző test sebességét kiszámolni

\[ v = \frac{s}{t} \]
\[ (120.0, 2.0) \rightarrow 60.0 \]
\[ (200.0, 0.5) \rightarrow 400.0 \]

Input adatokhoz rendelünk output adatokat

\[ f : \R \times \R \rightarrow \R \]
\[ D_f = \{(x, y) \in \R \times \R \; | \; x \geq 0 \; \land \; y > 0\} \]
\[ F(x,y) = \frac{x}{y} \]

De ezt nem fogjuk használni az órán.

A program működését akarjuk bizonyítnai matematikai módszerekkel.

Nem egyértelmű mindig, hogy mi in- és mi output.

Program szempontjából csak változók vannak. Ezek adják meg a program aktuális állapotát.

Programot hasonlítjuk össze a feladattal.

1. feladat állapottérrel

\[ (120.0, 2.0, 0.0) \to (120.0, 2.0, 60.0) \]

De ugyanígy

\[ (120.0, 2.0, *) \to (120.0, 2.0, 60.0) \]

Az output első két helyén is lehetne *: \((120.0, 2.0, *) \to (*, *, 60.0)\)

Nem feltétlenül determinisztikus.

Tehát ez nem egy függvény (\(F: A \rightarrow A\))

Hanem egy reláció (\(F \subset A \times A\))

A feladat egy leképezés.

\[ F = \left\{(a, c) \in A \times A \; | \; s(a) \geq 0 \land t(a) > 0 \land v(c)=\frac{s(a)}{t(a)}\right\} \]

Alternatív felírás következik

\[ D_f = \{a \in A \; | \; s(a) \ge 0 \; \land \; t(a) > 0\} \]
\[ \forall a \in D_f: F(a)=\{c \in A \; | \; v(c)=\frac{s(a)}{t(a)} \} \]

SZINTÉN alternatív felírás

\[ D_f = \{(x,y,z) \in A | x \ge 0 \; \land \; y > 0\} \]
\[ \forall (x, y, z) \in D_f:F((x, y, z))=\left\{\left(p, q, \frac xy\right) \in A\right\} \]

SZINTÉN SZINTÉN alternatív felírás

Gregó's favourite

(Csak a szükségesek vannak benne)

\[ F = \left\{(x,y,*) \rightarrow \left(*,*, \frac{x}{y}\right) \; | \; x \geq 0 \land y > 0\right\} \]

2. feladat

Egy összetett számnak adjuk meg egy valódi osztóját

Hány db adat van? 2 db.

  • Szám: \(n\)
  • osztó: \(d\)

Milyen típusúak?

  • \(n \in \N\)
  • \(d \in \N\)

Állapottér: adatok száma, nevük, típusuk

\[ A = (n: \N, d: \N) \]
\[ F = \{(x, *) \to (*, y) \; | \; x \text{ összetett} \land y | x \land y \neq 0 \land y \neq x\} \]

Ha nem kell ragaszkodni a \(n\)-hez, akkor eldobhetjuk. Az output érték kezdőállapota mindegy.

3. feladat

Döntsük el 2 természetes számról, hogy egyik osztója-e a másiknak

Hány adata van a feladatnak? Szám: \(n\), másik szám \(d\) és eredmény \(l\)

  • \(n \in \N\)
  • \(d \in \N\)
  • \(l \in \mathbb{L}\)

\(A = (n \in \N, d \in \N, l \in \mathbb{L})\)

Katie:

\(F = \{(x, y, *) \to (*, *, \text{x mod y} = 0) \; | \; x,y \in \N \; \land \; y \neq 0\}\)

Doboz:

\(F = \{(x, y, *) \to (*, *, y|x) \; | \; y \neq 0\}\)

4. feladat

Legyen 2 db változónk és cseréljük ki az értékeiket

Katie:

Hány adat van? Egyik: x, másik: y

\(A = x: \Z, y: \Z\)

\(F = {(x, y) \to (y, x)}\)

Doboz:

Két változó:

  • \(a \in \Z\)
  • \(b \in \Z\)
\[ A = (a: \Z, b: \Z) \]
\[ F=\{(x, y) \to (y, x)\} \]

A program

\(S \subset A \times (A \cup \{\text{fail}\})^{**}\)

A program állapothoz egy véges vagy végtelen állapot sorozatot rendel

5. ~~feladat~~ program

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

Struktogram

\(\left<\right>\): állapot sor

\[ (0, 0) \to \left<(0,0), (0,2)\right> \]
\[ (1,1) \to \left<(1, 1), (1, 2), (1, 3), (1,4), \ldots\right> \]
\[ (2,2) \to \left<(2,2), (2,2)\right> \]
\[ (3,3) \to \left<(3,3), (3,2), (3,3)\right> \]
\[ (4,4) \to \left<(4,4), (4,2)\right> \]

6. program

\[ A = (n: \N, d: \N) \]
d := n-1
while(n mod d != 0){
    d = d-1
}
\[ (6,8) \to \left<(6, 8), (6, 5), (6, 4), (6, 3) \right> \]
\[ (3,8) \to \left<(3,8), (3, 2), (3,1)\right> \]
\[ (2,8) \to (2, 8), (2, 1) \]
\[ (1,8) \to \left<(1,8), (1,0), \text{fail}\right> \]
\[ (0,8) \to \left<(0,8), \text{fail} \right> \]

\(D_s = A\)

A program bármely állapotból el tud indulni

7. feladat

\[ A=(x: \Z, \; y: \Z, \; z: \Z) \]
z := x
x := y
y := z
\[ \{x: 5, y: -2\} \to \left<\{x:5, \; y:-2\}, \{x:5, \; y:-2, \; z: 5\},\{x:-2, \; y:-2, \; z: 5\},\{x:-2, \; y:5\}\right> \]

Fogalmak a következő heti röpzhra

(todo: fogalom gyűjtemény)

  • állapot, állapottér
  • Mi a "feladat"?
    • állapottér feletti homogén binér reláció