Ackermannfunktion < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:48 Mi 27.12.2006 | | Autor: | snuggels |
| Aufgabe | Gegeben ist folgende Variante der Ackermannfunktion
A(x,y) = max(x,y) falls x*y = 0
A(x,y) = A(x-1, x+A(x,y-1)) sonst;
Berechnen Sie A( 0, y ) ; A( 1, y ) ; A( 2, y ) ; A( 3 , 2 ) und A( 4, 1 ).
Lösung
A( 0, y ) = max( 0, y ) = y
A( 0, y ) = y
A( 1, y ) = A(1-1,1+A(1,y-1)) = A(0,1+A(1,y-1)) = max(0,1+A(1,y-1))
A( 1, y ) = 1+A(1,y-1) = 1 + A(0,y) = 1 + max(0,y)
A( 1, y ) = 1 + y
A( 2, y ) = A(2-1,2+A(2,y-1)) = A(1,2+A(2,y-1) = A(0,2+A(2,y-1)+1) = max(0,2+A(2,y-1)
A( 2, y ) = 2+A(2,y-1)+1 = 3+A(2,y-1)
A( 2, 0 ) = 2
A( 2, y ) = 3y + 2
A( 3, y ) = A(3-1,3+A(3,y-1)) = A(2,3+A(3,y-1) = 3(3+A(3,y-1)+2
A( 3, y ) = 9+3A(3,y-1)+2 = 11+3A(3,y-1)
A( 3, y )+α = 3[A(3,y-1)+α]+11-3α+α = 3[A(3,y-1)+α]+11-2α → α = 11/2
A( 3, 0 )+11/2 = W+α = 3 + 11/2 = 17/2
A( x, y ) = (W+α) * Fy-α
A( 3, y ) = 17/2 * 3y 11/2
A( 4, 0 ) = 4
A( 4, 1 ) = A(4-1,4+A(4,1-1)) = A(3,4+A(4,0)) = A(3,4+4) = A(3,8)
A( 4, 1 ) = 17/2 * 38 11/2
A( 4, 1 ) = 55763
|
Meine Frage wäre, wie man von:
A( 2, y ) = 2+A(2,y-1)+1 = 3+A(2,y-1)
A( 2, 0 ) = 2
auf folgende Lösung kommt:
A( 2, y ) = 3y + 2
Ich würde mich freuen, wenn mir jemand erklären könnte, welche Regel man hier anwendet.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Aufgabe | Für die Variante der Ackermannfunktion
A(x,y) = max(x,y) falls x*y = 0
A(x,y) = A(x-1, y+A(x,y-1)) falls x>0 und y>0
Bestimme man die Funktionen A(0,y) und A(1,y), und die Werte A(2,0), A(2,1) bis A(2,4) und A(3,1)
Lösung 3.3 ohne Musterlösung !!!
A( 0, y ) = max(0,y)
A( 0, y ) = y
A( 1, 0 ) = 1
A( 1, y ) = A(1-1,y+A(1,y-1)) = A(0,y+A(1,y-1) = max(0,y+A(1,y-1) = y+A(1,y-1)
A( 1, y ) = y+A(0,y) = y+max(0,y) = y+y
A( 1, y ) = 2y
A( 2, 0 ) = max(2,0) = 2
A( 2, 1 ) = A(2-1,y+A(2,1-1) = A(1,1+A(2,0) = 2+2A(2,0) = 2+2*2
A( 2, 1 ) = 6
A( 2, 2 ) = A(2-1,2+A(2,2-1) = A(1,2+A(2,1) = 4+2A(2,1) = 4+2*6
A( 2, 2 ) = 16
A( 2, 3 ) = A(2-1,3+A(2,3-1) = A(1,3+A(2,2) = 6+2A(2,2) = 6+2*16
A( 2 ,3 ) = 38
A( 2, 4 ) = A(2-1,4+A(2,4-1) = A(1,4+A(2,3) = 8+2A(2,3) = 8+2*38
A( 2, 4 ) = 84
A( 3, 0 ) = max(0,3) = 3
A( 3, 1 ) = A(3-1,1+A(3,1-1)) = A(2,1+A(3,0)) = A(2,1+3) = A(2,4)
A( 3, 1 ) = 84
|
Ist die Lösung für die obige Aufgabe richtig? Ich bin mir nicht sicher ob ich die Regeln richtig angewendet habe.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
|
| |
|
| Aufgabe | Für die Variante der Ackermannfunktion
A(x,y) = 1+max(x,y) falls x*y = 0
A(x,y) = [mm] x^2*A(x-1,A(x,y-1)) falls [/mm] x > 0 und y > 0;
bestimme man die Funktionen A( 0, y ), A( 1, y ), A( 2, y ) und die Werte A( 3 , 0 ),
A( 4, 0 ), A( 3, 1 ) und A( 3, 2 ).
Lösung
A( 0, y ) = 1+y
A( 1, y ) = 1^2A(1-1,A(1,y-1)) = A(0,A(1,y-1)) = 1+A(1,y-1) = 1+A(0,y) = 1+1+y
A( 1, y ) = 2+y
A( 2, y ) = 2^2A(2-1,A(2,y-1)) = 4A(1,A(2,y-1)) = 4(2+A(2,y-1) = 8+4A(2,y-1)
A( 2, y ) = 8+4A(1,y) = 8+4(2+y) = 8+8+4y = 16+y
A( 3, 0 ) = 1+3 = 4
A( 4, 0 ) = 1+4 = 5
A( 3, 1 ) = 3^2A(3-1,A(3,y-1)) = 9A(2,A(3,y-1)) = 9(16+A(3,y-1) = 144 + 9A(3,y-1)
α-Trick
A( 3, 1 ) + α = 9[A(3,y-1)+ α]+144-9α+α
A( 3, 1 ) + α = 9[A(3,y-1)+ α]+144-8α → α = 144/8 = 18
A( 3, 0 ) + 18 = 4 + 18 = 22
A( x, y) = (4+18)*9y-18 = 22*9y-18
A( 3, y) = 22*9y-18
A( 3, 1 ) = 22*91-18 = 180
A( 3, 2 ) = 22*92-18 = 1764
|
Ist die Lösung der Aufgabenstellung richtig? Ich bin mir nicht sicher ob ich die Regeln der Ackermannfunkton richtig angewendet habe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Sa 27.01.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:59 Mi 27.12.2006 | | Autor: | felixf |
Hallo!
> Meine Frage wäre, wie man von:
>
> A( 2, y ) = 2+A(2,y-1)+1 = 3+A(2,y-1)
> A( 2, 0 ) = 2
>
> auf folgende Lösung kommt:
>
> A( 2, y ) = 3y + 2
Einfach per Induktion nach $y$: Der Induktionsanfang $y = 0$ folgt aus $A(2, 0) = 2 = 3 [mm] \cdot [/mm] 0 + 2$ und der Induktionsschritt aus $A( 2, y ) = 3+A(2,y-1)$.
LG Felix
|
|
|
|
