RPN < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen Sie: [mm] $w=a_1...a_n\in(\IR\cup \{+,-, \*,/\})^\*$ [/mm] ist arithmetischer Ausdruck in umgekehrter PN genau dann, wenn gilt:
(a) [mm] $\forall1\le i0$ [/mm] und
(b) [mm] $\beta^\*(w)=1$
[/mm]
mit [mm] \beta(a)= \begin{cases} -1, & \mbox{falls } a\in\{+,-, \*,/\} \\ +1, & \mbox{sonst } \end{cases} [/mm] und [mm] \beta^\*(a_1...a_n)=\summe_{i=1}^{n}\beta(a_i) [/mm] |
Hallo liebe Leute,
Habe mal wieder ein kleines Problem mit obiger Aufgabe. Habe mich mit Präfix-, Infix- und Postfix-Notationen auseinandergesetzt (wobei ja Postfix die RPN also umgekehrte PN ist) und kann auch die Schritte zur Evaluation solcher Ausdrücke problemlos nachvollziehen. Nur habe ich mal wieder bei den theoretischen Bewesien keinen blassen Schimmer wie ich vorgehen soll. :-( Wäre super nett, wenn mir jemand von Euch weiterhelfen könnte.
Vielen Dank im voraus und liebe Grüße,
Janine
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Mo 12.06.2006 | | Autor: | Frank05 |
> (a) [mm]\forall1\le i0[/mm] und
> (b) [mm]\beta^\*(w)=1[/mm]
Vielleicht solltest du erstmal die Aufgabe korrekt wiedergeben. Es bringt wenig einen Allquantor über [mm]i[/mm] anzugeben, wenn in der Aussage dahinter kein [mm]i[/mm] vorkommt. Denn dann ist [mm]\beta^*(a_1...a_n)=\beta^*(w)[/mm] womit die Gleichung (b) die Gleichung (a) überflüssig macht und nur mit (b) kommt man da nicht weiter.
|
|
|
| |
|
| Aufgabe | Beweisen Sie: [mm] $w=a_1...a_n\in(\IR\cup \{+,-,\*,/\})^\*$ [/mm] ist arithmetischer Ausdruck in umgekehrter PN genau dann, wenn gilt:
(a) $ [mm] \forall1\le i0 [/mm] $ und
(b) $ [mm] \beta^\*(w)=1 [/mm] $
mit $ [mm] \beta(a)= \begin{cases} -1, & \mbox{falls } a\in\{+,-,\*,/\} \\ +1, & \mbox{sonst } \end{cases} [/mm] $ und $ [mm] \beta^\*(a_1...a_n)=\summe_{i=1}^{n}\beta(a_i) [/mm] $ |
Hey Frank,
danke für den Hinweis und danke, dass du dich mit meiner Aufgabe beschäftigt hast!  Habe mir beim Aufschreiben der Aufgabe wirklich große Mühe gegeben, aber dummerweise aus einem [mm] $a_i$ [/mm] ein [mm] $a_n$ [/mm] gemacht. Oben ist jetzt die absolut korrekte Aufgabenstellung erneut. Natürlich wäre mit einem $n$ im Index der komplette Satz (a) überflüssig.
Wäre super, wenn mir jemand bei dieser Aufgabe helfen könnte. Es ist eine Aufgabe von einem Übungsblatt mit insgesamt 7 Aufgaben. Die anderen konnte ich alle allein lösen. Diese theoretischen Beweisen fallen mir unheimlich schwer - schon alleine beim Verständis der Behauptung.
Liebe Grüße und vielen Dank im voraus!
Janine
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:57 Mo 12.06.2006 | | Autor: | Frank05 |
> Beweisen Sie: [mm]w=a_1...a_n\in(\IR\cup \{+,-,\*,/\})^\*[/mm] ist
> arithmetischer Ausdruck in umgekehrter PN genau dann, wenn
> gilt:
>
> (a) [mm]\forall1\le i0[/mm] und
> (b) [mm]\beta^\*(w)=1[/mm]
>
> mit [mm]\beta(a)= \begin{cases} -1, & \mbox{falls } a\in\{+,-,\*,/\} \\ +1, & \mbox{sonst } \end{cases}[/mm]
> und [mm]\beta^\*(a_1...a_n)=\summe_{i=1}^{n}\beta(a_i)[/mm]
> Hey Frank,
Hallo Janine,
> danke für den Hinweis und danke, dass du dich mit meiner
> Aufgabe beschäftigt hast! Habe mir beim Aufschreiben
> der Aufgabe wirklich große Mühe gegeben, aber dummerweise
> aus einem [mm]a_i[/mm] ein [mm]a_n[/mm] gemacht. Oben ist jetzt die absolut
> korrekte Aufgabenstellung erneut. Natürlich wäre mit einem
> [mm]n[/mm] im Index der komplette Satz (a) überflüssig.
So ist das eben wenn man exakt arbeiten will.. da kann einiges schiefgehen 
> Diese theoretischen Beweisen fallen mir unheimlich
> schwer - schon alleine beim Verständis der Behauptung.
Meistens ist es schon das Verständnis, welches die Lösung nach sich zieht. In diesem Fall sollte es helfen sich einmal ein paar Beispiele von Ausdrücken in RPN in Bezug auf diese Formeln zu überlegen.
Nehmen wir mal den Ausdruck E = 3 5 + 2 -
Man stellt fest, dass [mm]\beta(a_1) = 1, \beta(a_1, a_2) = 2, \beta(a_1,a_2,a_3) = 1, \beta(a_1,a_2,a_3,a_4)=2, \beta(E) = 1[/mm]. Offensichtlich stimmen also die beiden Aussagen. Wie kommt man nun darauf, was diese bedeuten könnten?
Wenn du dir mal überlegst, wie so ein Ausdruck in RPN ausgewertet wird, dann liegt dem ganzen ja ein Stack (Keller, Stapel) zugrunde. Zuerst werden da die beiden Zahlen 3 und 5 draufgeworfen, danach beide wieder runtergenommen und die 8 (3+5) kommt auf den Stack. Danach noch die 2 dazu und beide wieder runter und dafür die 6 (8-2) drauf. Was fällt auf, wenn man den Stack mit den Werten dieser [mm]\beta[/mm] Funktion vergleicht?
Richtig.. die [mm]\beta[/mm] Funktion gibt die Anzahl der auf dem Stack liegenden Elemente an.
Mit diesem Wissen sollte es schon viel leichter fallen die beiden Richtungen hier zu beweisen. Angenommen du hast einen korrekten Ausdruck in RPN. Dann weißt du auch, wie er sich beim Abarbeiten auf dem Stack verhält. Zum Beispiel muss am Anfang eine Zahl stehen, weil ja sonst nicht genug Operanden für eine Operation vorhanden wären. Demzufolge muss [mm]\beta(a_1)=1[/mm] gelten. Da alle Operationen binär sind muss noch ein zweiter Operand her. Danach können beliebig viele Operanden und Operationen folgen. Aber es gibt natürlich eine Einschränkung, da immer genug Operanden auf dem Stack verbleiben müssen, damit eine neue Operation folgen darf. Das verträgt sich ziemlich genau mit der Definition dieser [mm]\beta[/mm] Funktion.
In der anderen Richtung kannst du dir überlegen, welche Art von Ausdrücken du erzeugen kannst. Es muss z.B. gelten, dass [mm]\beta(a_1) > 0[/mm] ist, also insbesondere [mm]\beta(a_1) = 1[/mm], was nur mit einer Zahl zu Beginn machbar ist. Danach kann keine Operation folgen, da sonst die erste Bedingung verletzt wäre. Also hast du wieder zwei Operanden und kannst ausnutzen, dass Operationen gerade die Anzahl der auf dem Stack verbleibenden Operanden um eins erniedrigen. usw usf.
Ich denke du schaffst das schon diese Überlegungen in einen Beweis auszubauen und auch die zweite Bedingung ist recht einleuchtend, wenn du dir mal überlegst, was für korrekte Ausdrücke in RPN nach der Auswertung gelten sollte.
|
|
|
| |
|
Hey Frank,
vielen, vielen Dank für diese kompetente und sehr gut verständliche Erklärung!! Ich bin jetzt total erleuchtet - es ist ja so logisch. Habe zwar eine ganze Weile gebraucht, aber jetzt steht der Beweis und müsste auch in sich schlüssig sein.
Nochmals danke, du bist echt eine riesen Hilfe!!
LG Janine
|
|
|
|
