Beweise zu Speicheroperationen pop push

Question

Es gelten für Stapelspeicher folgende Operationen:

pop(m) soll das oberste Element e eines nicht leeren Stapels m entfernen und den neuen Stapel m' zurück geben.

push(m,e) soll ein neues Datenelement e ∈ ℤ ganz oben in den Stapel m einfügen und den resultierenden Stapel zurück geben.

Die Aufgabe:

Für genau welche Stapel m, bzw. e ∈ ℤ gelten die folgenden Aussagen?

a) pop(push(m,e)) = m

Begründen Sie.

b) push(pop(m),e) = m

Beweisen Sie, dass Ihre Anforderungen an m notwendig ist sind.

c) Beweisen Sie, dass Ihre Anforderungen an m bzw. e aus Teilaufgabe b) hinreichend sind.

Sie dürfen hierzu ohne Beweis verwenden, dass gilt:

• m = m´ gilt genau für alle Stapel m, m´, mit Mm = Mm´ (Mm = { (a,m(a)) I m(a) ≠ kein Element}
• (A ∪ B) \ B = A für disjunkte Mengen A, B
• (A \ B) ∪ B = (A ∪ B) für beliebige Mengen A, B
• m´(0) = m(0) − 1 für nichtleere Stapel m und m´ = pop(m)

Also zur a) habe ich gedacht, dass die Aussage "(A ∪ B) \ B = A für disjunkte Mengen A, B" gilt aber in der Aufgabenstellung steht explizit, für welche Stapel m, bzw. e. Das gilt doch für alle m und e oder nicht? Hat jemand einen Tipp für mich zur a) oder zu den anderen Teilaufgaben? Was wird mit hinreichend/notwendig gemeint?

Answer 1

Antwort mit KI erzeugt

Bewerte die Aussagen zu Speicheroperationen pop push

a) pop(push(m,e)) = m

Um diese Aussage zu begründen, betrachten wir zuerst, was die angegebenen Operationen tun. Die Operation push(m,e) fügt das Element \(e\) in den Stapel \(m\) ein und gibt einen neuen Stapel zurück, in dem \(e\) das oberste Element ist. Führt man unmittelbar darauf die Operation pop aus, wird \(e\) wieder vom Stapel entfernt. Der zurückgegebene Stapel ist wieder \(m\).

Das heißt, unabhängig davon, wie der Stapel \(m\) aussieht oder welchen Wert das Element \(e \in \mathbb{Z}\) hat, wird nach dem Hinzufügen eines Elements zu einem Stapel und dem anschließenden Entfernen desselben Elements der ursprüngliche Stapel \(m\) wiederhergestellt. Diese Eigenschaft gilt für alle Stapel \(m\) und für alle ganzen Zahlen \(e\), da die Operationen push und pop so definiert sind, dass sie direkt gegenüberliegende Effekte haben, solange der Stapel nicht leer ist.

b) push(pop(m),e) = m

Diese Aussage ist nicht allgemein gültig und hängt von den Eigenschaften des Stapels \(m\) ab.

1. Notwendige Bedingungen für \(m\): Der Stapel \(m\) muss mindestens ein Element enthalten. Ein leerer Stapel kann nicht gepoppt werden, sodass die Operation pop(m) undefiniert wäre und somit die linke Seite der Gleichung nicht sinnvoll ist.
2. Für die Aussage „hinreichend“ sind zusätzliche Überlegungen nötig. Nehmen wir an, \(m\) ist nicht leer, und wir führen die Operation pop aus, erstellen damit einen neuen Stapel \(m'\), bei dem das oberste Element entfernt wurde. Wenn wir nun ein beliebiges Element \(e\) mit push auf \(m'\) hinzufügen, erhalten wir nicht unbedingt den ursprünglichen Stapel \(m\) zurück, es sei denn, \(e\) ist genau das Element, das zuvor durch pop entfernt wurde.

Das heißt, notwendige Bedingungen für \(m\) sind, dass \(m\) nicht leer ist, und eine hinreichende Bedingung ist, dass \(e\) das Element sein muss, das durch pop(m) entfernt wurde, damit \(push(pop(m),e) = m\) gilt.

c) Beweisen Sie, dass Ihre Anforderungen an m bzw. e aus Teilaufgabe b) hinreichend sind.

Wenn \(m\) mindestens ein Element enthält und \(e\) das Element ist, welches durch pop(m) entfernt wurde, dann garantiert die Operation push(pop(m),e) durch ihre Definition die Wiederherstellung des ursprünglichen Stapels \(m\).

1. Sei \(m\) ein Stapel mit mindestens einem Element.
2. \(pop(m)\) erzeugt einen neuen Stapel \(m'\), indem das oberste Element \(e\) von \(m\) entfernt wird.
3. \(push(m', e)\) fügt \(e\) wieder ganz oben auf den Stapel \(m'\) hinzu. Da \(e\) das vorher durch pop entfernte oberste Element von \(m\) ist, wird der ursprüngliche Zustand von \(m\) wiederhergestellt.

Da die Operationen pop und push genau definieren, wie Elemente entfernt und hinzugefügt werden, und keine anderen Veränderungen am Stapel vornehmen, ist die Anforderung, dass \(e\) das durch pop entfernte Element sein muss, hinreichend für die Gleichheit \(push(pop(m),e) = m\).