Ackermann Funktion / Induktion < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:29 Fr 02.12.2005 | | Autor: | Nephilim |
also ich habe folgendes problem
gegeben ist die ackerman funktion:
(1)A(0,n) = n+1
(2)A(m,0) = A(m-1, 1) für m > 0
(3)A(m,n) = A(m-1, A(m, n-1) für m,n > 0
und folgende werte sind gegeben
A(0, n)
A(1, n) und A(2, n)
zuerst soll ich math. funktionen finden mit denen man die ackerman funktion berechnen kann
bei A(0, n) ist ja scho vorgegeben das es n+1 ist
bei A(1, n) wende ich einfach regel (2) n mal an mit es in der form
A(0, ......., A(0, A(1, 0))....)
und A(1, 0) ergibt 2
also kann man A(1, n) mit der funktion n + 2 brechnen
aber bei A(2, n) komm ich irgendwie nicht weiter
müsste nach dem selben schema ablaufen aber ich bekomm es nicht hin
ich weis nur das 2*n+3 rauskommen sollte
aber nicht wie man auf das 2*n kommt
dann wäre noch für A(1, n) und A(2, n) der beweis durch induktion gefragt
hoffe mir kann jemand helfen
diese frage wurde in keinem anderen forum gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:03 Sa 03.12.2005 | | Autor: | felixf |
> also ich habe folgendes problem
> gegeben ist die ackerman funktion:
>
> (1)A(0,n) = n+1
> (2)A(m,0) = A(m-1, 1) für m > 0
> (3)A(m,n) = A(m-1, A(m, n-1) für m,n > 0
>
> und folgende werte sind gegeben
> A(0, n)
> A(1, n) und A(2, n)
>
> zuerst soll ich math. funktionen finden mit denen man die
> ackerman funktion berechnen kann
>
> bei A(0, n) ist ja scho vorgegeben das es n+1 ist
> bei A(1, n) wende ich einfach regel (2) n mal an mit es in
> der form
> A(0, ......., A(0, A(1, 0))....)
> und A(1, 0) ergibt 2
> also kann man A(1, n) mit der funktion n + 2 brechnen
Genau.
> aber bei A(2, n) komm ich irgendwie nicht weiter
> müsste nach dem selben schema ablaufen aber ich bekomm es
> nicht hin
> ich weis nur das 2*n+3 rauskommen sollte
> aber nicht wie man auf das 2*n kommt
Nun, mach es genau wie vorhin:
A(2, n) = A(1, A(2, n-1)) mit Regel (3).
Jetzt weisst du, dass A(1, A(2, n-1)) = A(2, n-1) + 2 ist (nach dem was du grad gemacht hast). Also ist
A(2, n) = A(2, n-1) + 2.
Wenn du das mehrmals wiederholst bekommst du
A(2, n) = A(2, n-2) + 2*2 = A(2, n-3) + 2*3 = A(2, n-4) + 2*4 = ... = A(2, 0) + 2*n.
Nun ist A(2, 0) = A(1, 1) = 1 + 2 = 3, womit also A(2, n) = A(2, 0) + 2*n = 3 + 2*n ist!
> dann wäre noch für A(1, n) und A(2, n) der beweis durch
> induktion gefragt
>
> hoffe mir kann jemand helfen
Nunja, im Prinzip hast du es oben schon aufgeschrieben! Du zeigst erst A(1, n) = n+2 per Induktion: Angenommen, die Behauptung gilt fuer n, also A(1, n) = n+2. Dann ist A(1, n+1) = A(0, A(1, n)) = A(1, n) + 1. Per Induktionsvoraussetzung ist A(1,n) = n+2, womit A(1, n+1) = A(1, n) + 1 = n+2 + 1 = (n+1) + 2 ist.
Fuer A(2, n) machst du das jetzt genauso.
HTH Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:52 Sa 03.12.2005 | | Autor: | Nephilim |
ok ich denke jetzt hab ich im großen und ganzen vestanden wie man vorgeht
danke :)
|
|
|
|
