Permutation (Stack)

Celina · Anmeldungsdatum: 28.05.2005 Beiträge: 2

Hi,
das ist eine Aufgabe aus meinem theoretische Informatik Übungsblatt.
In der Vorlesung haben wir gerade über Bäume und Grahpen gemacht.
Jetzt bekommen wir so eine Aufgabe. Ich kann diese Aufgabe nicht zu unserer Thematik zuordnen und weiß auch nicht wie ich anfangen soll.
Wird irjend jemand schlau mit dieser Aufgabe und kann mir helfen??

Es sei ein Stack gegeben, der in aufsteigender Reihenfolge mit den ersten n natürlichen Zahlen gefüllt wird: Push(1), Push(2),…., Push(n) .

Es werden nun zusätzlich n Pop-Anweisungen betrachtet, wobei ein Pop-Befehl nur bei einem momentan nichtleeren Keller zulässig ist. (für n=3 ist beispielsweise die Folge Push(1),
Pop, Push(2), Push(3), Pop, Pop möglich, nicht aber Push(1), Pop, Pop, Push(2),Push(3),Pop.)
Die bei der Pop-Anweisung entnommenen Zahlen bilden eine Permutation (p1,..,pn) von (1,…,n). ( Beispielsweise erzeugt die erste Befelsfolge die Permutation (1,3,2), also p1=1,
p2=3 und p3=2.) Zeigen sie:

(a) Die Permutation (3,1,2) kann mit dem obigen Verfahren nicht produziert werden.
(b) Eine Permutation (p1,…,pn) ist genau dann erzeugbar, falls es keine Indizes i<j<k
Mit pj < pk < pi gibt.
(c) Es lässt sich in Linearzeit überprüfen, ob eine gegebene Permutation mit dem obigen
Verfahren erzeugt werden kann.

Sh0rty · Anmeldungsdatum: 29.05.2005 Beiträge: 4 Wohnort: NRW

Hmmm...also ich mach mal was zu a):

Es ist zu zeigen, dass die Permutation (3,1,2) mit dem obigen Verfahren nicht produziert werden kann:

(3,1,2) heisst der 1. POP-Befehl holt die Zahl 3, der 2. POP-Befehl die 1 und der 3. POP-Befehl die 2:
Die Zahl 3 kann erst entnommen werden, nachdem sie mittels des PUSH-Befehls auf den Stack gelegt worden ist, also nach PUSH(3).
D.h. unsere Folge fängt so an: PUSH(1), PUSH(2), PUSH(3), POP(3)
jetzt haben wir die 3 an erste Stelle wie gefordert und auf dem Stack sind noch 1 und 2 und zwar in der Reihenfolge erst die 1 und dann die 2. D.h. mit dem nächsten POP-Befehl können wir nur die 2 runterholen und DANACH erst die 1.
D.h. (3,2,1) ist möglich aber (3,1,2) nicht.

Hoffe das war so einigermassen verständlich, wenn du was zu der Aufgabe generell nicht verstehst musst du nur genau sagen was das wäre z.B. ob du weisst was ein Stack(=Keller=LIFO-Prinzip) ist oder wass ne Permutation(=Umordnung) ist etc...

MfG
Shoddy

Celina · Anmeldungsdatum: 28.05.2005 Beiträge: 2

Hallo,

danke für deine Erklärung.
Ich habe es verstanden!!
die Aufgabe a ist dem nach ein Beispiel für die Aufgabe b. Kann man das denn nicht mit einem Gegenbeispiel lösen!?
Oder muß man das mit Vollständiger Induktion oder so was ähnliches lösen.
Für diesen Aufgabenteil gibt es 3 Punkte und für a nur 1 Punkt, deshalb glaube ich mit dem Gegenbeispiel ist zu einfach, oder ??

Mfg
Celina

Gast

Um eine Behauptung zu widerlegen reicht ein Gegenbeispiel aus, das stimmt schon. Aber ich denke mal die Behauptung in b) stimmt hier, so dass es kein Gegenbeispiel geben wird traurig

. (Wenn die erste mit pop entnommene Zahl die grösste in der Permutation ist, dann muss die 2. mit pop entnommene Zahl die nächstkleinere sein - siehe auch a) als Beispiel für n=3.)

Also ehrlich gesagt weiss ich bei der Aufgabe b) auch nicht weiter (schäm unglücklich

), aber ich hab dir mal was rausgesucht was dir vllt. helfen kann:

http://www.math.tu-berlin.de/~felsner/Lehre/ProgMeth/Ueb/stack-permut.pdf

Ansonsten findet sich bei Google http://www.google.de/search?hl=de&q=Stack+%2BPermutationen&btnG=Suche&meta=lr%3Dlang_de noch weiteres Material was vllt weiterhilft.

mfg
Shoddy

P.S: Vllt könntest du die Lösung wenn ihr mal ne Musterlösung oder so dazu bekommt hier posten, würd mcih interessieren Augenzwinkern

Sh0rty · Anmeldungsdatum: 29.05.2005 Beiträge: 4 Wohnort: NRW

Ach shit...war nich eingeloggt Augenzwinkern

In dem oben geposteten PDF Dokument findet sich z.B. auch ein Beweis zu folgendem: