Funktion ϖ(a, b) < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:42 Mo 07.11.2011 | | Autor: | Deztiny |
| Aufgabe | 1. Rekursive Funktion
Gegeben sei folgende rekursiv de nierte Funktion ϖ(a, b) | a, b [mm] \in \IN_{0} [/mm] :
ϖ(0, b) = b2
ϖ(a, 0) = ϖ(1, a)
ϖ(a, a) = ϖ(a − 1, a + 1) | a ̸= 0
ϖ(a, b) = ϖ(a − 1,ϖ(b − 1, a − 1))
a) [10 Punkte] Implementieren Sie die Funktion in Ada.
b) [4 Punkte] Ermitteln Sie die Ergebnisse der Funktion ϖ für die nachfolgenden
Werte von a und b:
1.) a = 1, b = 3
2.) a = 2, b = 1
3.) a = 2, b = 2
4.) a = 4, b = 0 |
Hallo,
diese Aufgabe (ist zwar eine Programmieraufgabe), aber ich habe nicht mit der Implementierung Probleme, sondern mit dem Verständnis der gegebenen, rekursiven Funktion.
1.) Ich weiß nicht wieso, aber ich verstehe nicht, was eine Beispielfunktion:
f(x,0) = x ... bedeutet? (die 2 Parameter der Funktion (x,0) machen mir Schwierigkeiten.)
2.) Dann kommt noch hinzu, dass es Zuweisungen gibt, wie:
f(x,1) = f(0,x) ... ??? (auch hier verstehe ich nicht, wie ich das behandeln soll). Vor allem ist die Frage, ist das rekursiv in einer Art Reihenfolge dargestellt? also beginne ich oben mit Startwerten und arbeite dann Zeile für Zeile ab?
Kann mir jemand weiterhelfen, oder ein ähnliches Beispiel + Auswertung nennen? -Stehe echt auf dem Schlauch-
mfg,
Dezt
P.S.:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:29 Mo 07.11.2011 | | Autor: | Harris |
Hi!
First of all: was heißt b2? [mm] $b^2$, $2\cdot [/mm] b$ oder einfach nur b? Ich mache das hier mal nur mit $b$, sonst wirds zum Vorrechnen hier zu krass.
Erstmal: eine Funktion $f$ bildet einen Definitionsbereich (eine beliebige Menge) auf eine andere Menge ab. Ist der Bereich wie hier [mm] $\IN^2$, [/mm] so bekommt man als Eingabe zwei natürliche Zahlen und generiert hieraus eine natürliche Zahl.
Also: [mm] $f:IN^2\rightarrow\IN$ [/mm] ist in deinem Beispiel der Fall. Du bekommst zwei Zahlen als Eingabe und es kommt eine Zahl raus.
Regeln wie $f(a,0)=f(1,a)$ bedeuten Einfach nur, dass die Funktionswerte dieser beiden verschiedenen Eingaben übereinstimmen, man also problemlos gemäß deiner Regeln die Funktionswerte vertauschen kann, um ein Ergebnis zu bekommen.
Offensichtlich muss man anhand der Regeln versuchen, das erste Argument auf $0$ zu kriegen, da nur so das Endergebnis direkt ablesbar ist. Ein Berechnungsalgorithmus terminiert, da bei jeder Regel das erste Element um eins nach unten gezählt wird. Irgendwann erreicht es die 0.
Ich zeig dir mal ein Beispiel von $f(3,3)$:
f(3,3) (Regel 3)
=f(2,4) (Regel 4)
= f(1,f(3,1)) (Regel 4 innen)
= f(1,f(2,f(0,2))) (Regel 1 innen innen)
= f(1,f(2,2)) (Regel 3 innen)
= f(1,f(1,3)) (Regel 4 innen)
= f(1,f(0,f(2,0))) (Regel 1 innen)
= f(1,f(2,0)) (Regel 2 innen)
= f(1,f(1,2)) (Regel 4 innen)
= f(1,f(0,f(1,0))) (Regel 1 innen)
= f(1,f(1,0)) (Regel 2 innen)
= f(1,f(1,1)) (Regel 3 innen)
= f(1,f(0,2)) (Regel 1 innen)
= f(1,2) (Regel 4)
= f(0,f(1,0)) (Regel 1)
= f(1,0) (Regel 2)
= f(1,1) (Regel 3)
= f(0,2) (Regel 1)
= 2
So würde der Algorithmus arbeiten. Ein Quelltext mit Java wäre z.B.
public static int fs(int i, int j){
if (i==0) return j;
if (j==0) return fs(1,i);
if (i==j) return fs(i-1,i+1);
return fs(i-1,fs(j-1,i-1));
}
(ohne Abfrage einer Fehlerhaften Eingabe.
Ähnliche Funktionen sind z.B. die "Ackermann-Funktion". Diese ist in der theoretischen Informatik ein wichtiges Beispiel.
Variiert man das $b$ von oben zu [mm] $2\cdot [/mm] b$ oder gar zu [mm] $b^2$, [/mm] so wächst diese Funktion auch krass... Bei beiden Fällen bekomme ich z.B. bei der Eingabe von $f(9,9)$ einen Stackoverflow-Error.
Hoffe, ich konnte helfen!
Gruß, Harris
|
|
|
| |
|
> 1. Rekursive Funktion
> Gegeben sei folgende rekursiv defi nierte Funktion
> ϖ(a, b) | a, b [mm]\in \IN_{0}[/mm] :
> ϖ(0, b) = b2
das sollte wohl [mm] b^2 [/mm] heißen, oder ?
> ϖ(a, 0) = ϖ(1, a)
> ϖ(a, a) = ϖ(a − 1, a + 1) | a ̸= 0
... und hier ist wohl a≠0 gemeint ?
> ϖ(a, b) = ϖ(a − 1,ϖ(b − 1, a − 1))
Nennen wir die Funktion doch einfach f.
Für ihre Inputvariablen können wir ganz gut bei a und b
bleiben - oder meinetwegen x und y - oder i und j :
aber bitte nachher nicht dauernd die Bezeichnungen wechseln!
> a) Implementieren Sie die Funktion in Ada.
> b) Ermitteln Sie die Ergebnisse der Funktion ϖ
> für die nachfolgenden
> Werte von a und b:
> 1.) a = 1, b = 3
> 2.) a = 2, b = 1
> 3.) a = 2, b = 2
> 4.) a = 4, b = 0
> Hallo Deztiny,
>
> diese Aufgabe (ist zwar eine Programmieraufgabe), aber ich
> habe nicht mit der Implementierung Probleme, sondern mit
> dem Verständnis der gegebenen, rekursiven Funktion.
Am einfachsten stellst du dir die Funktion in Tabellenform
dar, wie in der Tabellenkalkulation. Dabei stehen z.B. die
a-Werte (Zeilennummern) in der senkrechten Spalte am
linken Rand und die b-Werte (Spaltennummern) in der
obersten waagrechten Zeile. Ins Tabellenfeld der Zeile
Nummer a und Spalte Nummer b soll nun der Funktions-
wert f(a,b) eingetragen werden. Dies kann nun nicht nach
der einfachen Reihenfolge (Zeile um Zeile) geschehen.
Die Reihenfolge des Ausfüllens ist mehr oder weniger
strikt durch die Rekursionsregeln vorgegeben. Das System
dieser Reihenfolge ist zunächst nicht ganz leicht zu
durchschauen.
Probiere es einfach einmal mittels Papier und Bleistift
aus. Die paar unter b) gefragten Werte kann man so
in relativ kurzer Zeit auch ohne Rechner ermitteln und
lernt dabei gleich etwas über die Struktur dieses
rekursiven Systems.
Es stellt sich dabei vielleicht auch noch die Frage, ob
das System der Regeln in sich selbst widersprüchlich
sein könnte. Wenn ja, warum; wenn nein, warum nicht ?
Ob man in Ada die Reihenfolge der Anwendung der
Rekursionsregeln selber planen muss oder dem Programm
überlassen kann, weiß ich nicht.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:49 Mo 07.11.2011 | | Autor: | Deztiny |
Erstmal: VIELEN DANK für die Aufklärung.
-WICHTIG: das soll heißen [mm] b^{2} [/mm] (und nicht einfach nur b)
Ich habe mich jetzt mit papier und kugelschreiber^^ drangesetzt, und bin stur die aufgaben durchgegangen!
Um zu checken, ob ich diese Funktionen nun wirklich richtig verstanden habe, wäre es nett, wenn mir jemand noch kurz ein feedback gibt, ob das auch stimmt :/ ?
also bei der b.)
1.) Ergebnis: 16 (also b = 4... mit 4²)
2.) Ergebnis: 4 (also b = 2... mit 2²)
3.) Ergebnis: 16 (wieder b = 4)
4.) Ergebnis: 256 (b = 16... 16² = 256)
Wenn das soweit ok ist, dann habe ich morgen beim "implementieren" in Ada zumindest keien Zweifel mehr.
@ Al-Chwarizmi
Das System scheint mir auf den ersten Blick (und erstes Rechnen) nicht widersprüchlich zu sein, da es ja tatsächlich durch Reduzierung des ersten "Parameters" a, immer zu einem Ende findet.
Natürlich können durch bereits höhere Abgabewerte annährend gewaltige Zahlen entstehen, aber das sei jetzt erstmal mein Problem :)
mfg,
Dezt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:28 Di 08.11.2011 | | Autor: | Deztiny |
Noch eine kleine Korrektur, hab eben schon das Programm geschrieben, und es hat meinen Denkfehler aufgeklärt^^
1.) = 256
2.) = 4
3.) = 256
4.) = 65536
Das hätte ich gerne korrigiert :) Wenn jemand die zeit hat!
Und nochmals ein großes Dankeschön!
mfg,
Dezt
|
|
|
| |
|
> 1.) = 256
> 2.) = 4
> 3.) = 256
> 4.) = 65536
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
stimmt alles !
LG
|
|
|
| |
|
> @ Al-Chwarizmi
> Das System scheint mir auf den ersten Blick (und erstes
> Rechnen) nicht widersprüchlich zu sein, da es ja
> tatsächlich durch Reduzierung des ersten "Parameters" a,
> immer zu einem Ende findet.
Wenn man die 4. Regel
f(a, b) = f(a − 1,f(b − 1, a − 1))
zum Beispiel auf das Paar (a,b)=(2,2) anwendet, so liefert
sie
f(2,2)=f(1,f(1,1))=f(1,4)=65536
Dies stimmt aber nicht überein mit der Rechnung nach Regel 3:
f(a,a)=f(a-1,a+1)
f(2,2)=f(1,3)=256
Also müsste doch z.B. bei der Regel 4 noch eine Einschränkung
wie etwa a≠b oder a<b stehen, damit dieser Widerspruch ausgeschlossen
wird. Eine solche Einschränkung ist aber nicht genannt.
Ob dies die einzige Quelle möglicher Widersprüche ist, habe
ich nicht untersucht.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:37 Di 08.11.2011 | | Autor: | Deztiny |
Okey,
aber so wie ich das verstanden habe, soll Regel 3 gerade "a = b" aussagen. Hoffe damit habe ich keinen gravierenen Fehler gemacht?
(ich habe f(a,a) einfach als kürzere schreibweise von f(a,b) | a = b, interpretiert)
+ Ich habe in meiner Ada Implementierung einfach genau die Reihenfolge benutzt, die nach Aufgabenstellung gegeben ist.
So ist der Fall a = 0 schon nach der ersten if-Abfrage abgefangen und ich bekomme ein Ergebnis für b². (Regel 3 kann nicht weiter verletzt werden, da es eben die 3te if-Abfrage ist, die gar nicht erst erfragt wird, wenn a = 0).
Ich halt die Augen offen, nach evtl. weiteren Widersprüchen (frage auch meine Komillitionen mal).
Regel 3 fängt also nach meienr Annahme "a = b" ab und damit kommt es in diesem Fall nie zu einer möglichen Verletzung der 4.Regel. (wenn man die Reihenfolge eben einhält).
Erläuterung: Über return ... wird die Funktion nach jeder if-Abfrage verlassen, und die Funktion startet von vorne bei Regel 1..2...
Vieland Dank für deine Zeit,
ich denke ich habe mit meiner jetzigen implementierung schon gute Aussichten.
P.S.: Wen die Ada implementierung sehr interessiert, der kann mir gerne schreiben, ich stell sie öffentlich oder schicke sie per PN. (oder PM)
mfg,
Dezt
|
|
|
| |
|
Hallo Deztiny,
ich habe festgestellt, dass diese rekursive Definition doch
wohl problematischer ist als zuerst gedacht.
Sofern die Regeln so stimmen:
R1: $\ f(0,b)\ =\ [mm] b^2$
[/mm]
R2: $\ f(a,0)\ =\ f(1,a)$ (falls a>0)
R3: $\ f(a,a)\ =\ f(a-1,a+1)$ (falls a>0)
R4: $\ f(a,b)\ =\ f(a-1,f(b-1,a-1))$ (falls a>0 und b>0 und a≠b)
dann gibt es z.B. bei der rekursiven Berechnung von f(2,4)
folgenden Konflikt:
$ f(2,4)\ =\ f(1,f(3,1))$ (nach R4)
Die Berechnung des darin vorkommenden Wertes f(3,1)
führt aber nach derselben Regel R4 auf:
$ f(3,1)\ =\ [mm] f(2,\underbrace{f(0,2)}_4)\ [/mm] =\ f(2,4)$
Zur Berechnung von f(2,4) ist also der Wert von f(3,1)
erforderlich, und umgekehrt. Mit anderen Worten heißt
dies, dass sich diese Werte durch die Rekursionsformeln
gar nicht ermitteln lassen.
Ich sehe jetzt zwei Möglichkeiten:
1.) die Aufgabe wurde nicht korrekt und vollständig
wiedergegeben
2.) das System der vorliegenden Rekursionsformeln
ist tatsächlich nicht vollständig - und möglicherweise
auch teilweise in sich widersprüchlich
LG Al-Chwarizmi
|
|
|
|
