Blatt 5, Aufgabe 4

Aufgabe 4 ist für mich leider vollkommen unverständlich.
Für einige Erläuterungen, Hinweise wäre ich dankbar.

Mit freundlichen Grüßen
Rainer Schmidt

Bei "vollkommen unverständlich" ist es schwierig, eine konkrete Antwort zu geben, aber ich versuch mal die Aufgabe nochmal neu in Worte zu fassen, vielleicht hilft das ja...

Es geht um die Länge (=die Anzahl der Zeichen) von Booleschen Ausdrücken, in denen neben den Booleschen Operatoren (+, *, nicht) und den Konstanten (0, 1) noch Klammern ( (, ) ) und die Variablen x1-xn aus einer Menge Xn vorkommen können (wobei jede dieser Variable als ein Zeichen zählt, und der Index also nicht seperat gezählt wird). Außerdem sollen sie vollständig geklammert sein, d.h. (xi + xj) und (xi * xj) MÜSSEN paarweise geklammert sein, auch wenn man normalerweise die Klammern zur besseren Lesbarkeit weglassen kann.

Erst soll man also für die Variablen x1, x2 alle Ausdrücke angegeben werden, deren Länge <= 5 ist (eigentlich reine Fleißarbeit) und dann im Pseudocode* einen Algorithmus finden, der für eine beliebige Variablenmenge alle Ausdrücke bis zu einer bestimmten Menge <= einer gegebenen Länge L sind.

*Pseudocode sieht in etwa so aus, wie die anziehen-Prozedur unten, allerdings ist das, soweit ich weiß, keine Konvention, es ist also nicht so tragisch, wenn man seinen Pseudocode etwas anders formuliert - es geht nur darum, dass der Algorithmus eben "wie programmiert" beschrieben wird, und nicht in Worten ausformuliert.

Ich hoffe, das hat etwas geholfen, bei weiteren Unklarheiten können wir sonst ja auch am Mittwoch nochmal drüber reden.

Sehr geehrte Frau Winterer,

besten Dank für Ihre Antwort.

Ich habe den ersten Teil Ihrer Antwort wie folgt verstanden:
Angenommen, es gebe die Variablen a und b, die Verknüpfungen + und *, die Negation -, die Konstanten 0 und 1 und, natürlich, die Klammern.
Dann wäre, bei einer maximalen Länge von 6, folgender Ausdruck zu berücksichten: (a+-b), der Ausdruck (-a+-b) aber nicht, da die Länge 7 beträgt.

Zum zweiten Teil Ihrer Antwort:
Der Pseudocode soll also eine Liste von, nach den Regeln, möglichen Ausdrücken ausgeben. Dazu benötigt er als Input die Menge der Variablen, die Menge der sonstigen Zeichen (+*- ...) und die maximale Länge.

Habe ich Ihre Antwort so richtig verstanden?

Mit freundlichen Grüßen
Rainer Schmidt

Ja, genau so ist es gemeint!

Rainer Schmidt schrieb:
-------------------------------------------------------
> Angenommen, es gebe die Variablen a und b, die
> Verknüpfungen + und *, die Negation -, die
> Konstanten 0 und 1 und, natürlich, die Klammern.
> Dann wäre, bei einer maximalen Länge von 6,
> folgender Ausdruck zu berücksichten: (a+-b), der
> Ausdruck (-a+-b) aber nicht, da die Länge 7
> beträgt.

Prinzipiell ist es so zu verstehen, ABER VORSICHT:
(a+ -b) bzw. (-a + -b) sind keine gültigen Booleschen Ausdrücke! Die Regeln besagen: wenn b Boolescher Ausdruck, dann ist "(-b)" auch Boolescher Ausdruck. Entsprechend wären (a+(-b)) und ((-a) + (-b)) Boolsche Ausdrücke (mit Länge 8 bzw. 11)

Wobei die "Menge der sonstigen Zeichen" ja fest ist und nicht mehr extra als Parameter übergeben werden muss (es muss dem Algorithmus ja auch bekannt sein, welche Stelligkeit die Operatoren haben, wie man mit Klammern umgehn muss, etc...)...oder?



3 mal bearbeitet. Zuletzt am 23.11.2009 11:42 von Leonore Winterer.

Bis auf das bei vollständig geklammerten Ausdrücken auch die Negation geklammert werden muss.
Also im ob geposteten Beispiel: (a+(-b)), ((-a)+(-b)) und somit die Länge beider Ausdrücke > 6
Gruß
Simon