Vorlesung 12 Merkelt
Aus ProgrammingWiki
Inhaltsverzeichnis |
Folie 12
$f(x,y)$ = $\begin{cases} min~(z + 1)^2 > x & ,falls~(z + 1)^2 > x~existiert\\ y + 1 & ,sonst \end{cases}$
$f(19,19)$ = $\begin{cases} min~(z + 1)^2 > 19 & ,falls~(z + 1)^2 > 19~existiert\\ 20 & ,sonst \end{cases}$
Das kleinste $z \in \N$, welches die Bedingung erfüllt ist $z = 4$, da
- $z = 0 \curvearrowright 1^2 = 1$, zu klein
- $z = 1 \curvearrowright 2^2 = 4$, zu klein
- $z = 2 \curvearrowright 3^2 = 9$, zu klein
- $z = 3 \curvearrowright 4^2 = 16$, zu klein
- $z = 4 \curvearrowright 5^2 = 25$, erfüllt die Bedingung
$f(19,19) = 4 = \lfloor \sqrt{19} \rfloor$
Folie 24
$µf(10)~=~0$
$µf(5)~=~\perp$
$µf(x)$ = $\begin{cases} 0 & ,wenn~x~gerade\\ \perp & ,sonst \end{cases}$
Folie 26
$h_1(10)~=~0$
$h_1(5)~=~1$
$h_1(x)$ = $\begin{cases} 0 & ,wenn~x~gerade\\ 1 & ,sonst \end{cases}$
Folie 28
$h_2(10)~=~100$
$h_2(5)~=~25$
$h_2(x)$ = $x^2$
Folie 30
$h_3(10)~=~0$
$h_3(5)~=~0$
$h_3(x)$ = $0$
Folie 32
Schema:
$\mu{}f(x)$ = $\begin{cases} \textrm{das kleinste } \_\_\_\_\_ & ,\textrm{mit } \_\_\_\_\_ = 0, \textrm{wenn }\\ & \textrm{(1) so ein } \_\_ \textrm{ existiert und} \\ & \textrm{(2) } \_\_\_\_\_\_ \textrm{ für alle } \_\_ \leq \_\_ \textrm{ definiert ist;} \\ \perp & ,sonst \end{cases}$
Schema (2)
$\mu{}f(x)$ = $\begin{cases} \textrm{das kleinste } z \in \N & ,\textrm{mit } g(x,z) = 0, \textrm{wenn }\\ & \textrm{(1) so ein } z \textrm{ existiert und} \\ & \textrm{(2) } g(x,i) \textrm{ für alle } i \leq z \textrm{ definiert ist;} \\ \perp & ,sonst \end{cases}$
$g(x,n)$ ist zu definieren
Die beiden Bedingungen können durch zwei Hilfsfunktionen sicher gestellt werden und anschließend durch eine Multiplikation und verknüpft werden.
$prim?(x)$ = $\begin{cases} 1 & ,\textrm{wenn } y \textrm{ Primzahl}\\ 0 & ,sonst \end{cases}$
$gt(x,y)$ = $\begin{cases} 1 & ,y \gt x\\ 0 & ,sonst \end{cases}$
Daraus kann folgende Funktion entwickelt werden:
$\mu{}f(x,y)$ = $\begin{cases} \textrm{das kleinste } z \in \N & ,\textrm{mit } prim?(y) \cdot gt(y,x) \dot - z = 0, \textrm{wenn }\\ & \textrm{(1) so ein } z \textrm{ existiert und} \\ & \textrm{(2) } prim?(y) \cdot gt(y,x) \dot - i = 0 \textrm{ für alle } i \leq z \textrm{ definiert ist;} \\ \perp & ,sonst \end{cases}$
