View Full Version : [Frage] 4. Tutorium: poppendes obst ;)
ein_stein2000
06-05-2004, 20:36
hi!
leider bin i weiter hinten gesessen und hab net so ganz mitbekommen was der heute geredet hat, aber zum beispiel mit dem obst:
es geht um an stack (pop() und push()) ... und dafür soll man ah moore-schaltwerk machn
jetzt haben wir 2 obstsorten und der stack fast max. 3 kisten ... wie mach i das? wie isn das gemeint?
EDIT:
unten hab ich 2 beispiele gemacht
post#9 (http://hades.gothic.at/iforum/showpost.php?p=127861&postcount=9): 2 obstsorten, stack mit max. 3 elementen, nur push() realisiert
post#18 (http://hades.gothic.at/iforum/showpost.php?p=127899&postcount=18): 2 obstsorten, stack mit max 2 elementen, push() und pop() realisiert (da waren fehler drinn, bitte aktualisierte version anschaun)
also ich denke das wird folgendermaßen funktionieren:
als eingabe hat man zum beispiel push(apfel), pop(), push(birne), push(apfel)
und der automat soll zum beispiel nur folgenden stapel aktzeptieren wenn apfl, birne, birne drauf liegt.
eine mögliche eingabe wäre dann: push(birne), pop(), push(apfel), push(birne), push(apfel), pop(), push(birne)
allgemein geht man einfach her und schaut sich die eingabe an:
wenn push(apfel) wird eine kiste äpfel auf den stack gelegt, kommt dann eine birne wird verzweigt usw..
im prinzip wird bei zwei verschiedenen sorten ein binärbaum aufgebaut.
man markiert einfach den endzustand, der dann die geforderten kisten aufm stack enthält mit 1.
dann geht man einfach analog vor wie im tutorial durchgerechnet.
er hat gesagt der stack ist voll sobald 2 sachen, meinetwegen äpfel, drin sind - aber vielleicht hab ich mich ja verhört
nonamenobody
06-05-2004, 20:54
also ich denke das wird folgendermaßen funktionieren:
als eingabe hat man zum beispiel push(apfel), pop(), push(birne), push(apfel)
und der automat soll zum beispiel nur folgenden stapel aktzeptieren wenn apfl, birne, birne drauf liegt.
eine mögliche eingabe wäre dann: push(birne), pop(), push(apfel), push(birne), push(apfel), pop(), push(birne)
allgemein geht man einfach her und schaut sich die eingabe an:
wenn push(apfel) wird eine kiste äpfel auf den stack gelegt, kommt dann eine birne wird verzweigt usw..
im prinzip wird bei zwei verschiedenen sorten ein binärbaum aufgebaut.
man markiert einfach den endzustand, der dann die geforderten kisten aufm stack enthält mit 1.
dann geht man einfach analog vor wie im tutorial durchgerechnet.
Könntest du das bitte genauer ausführen? Ich hatte leider keine Zeit, in das Tutorium zu kommen, aber ich kann mir nicht wirklich vorstellen, wie ich mit Hilfe eines Moore-Schaltwerks viele verschiedene Zustände verwalten soll (damit das pop() funktioniert).
Danke und lg
Philipp
ok angenommen der automat akzeptiert folgenden stapel:
apfl, birne, birne (als ausgang erhalten wir dann = 1).
und als eingabe erhalten wir:
push(birne), pop(), push(apfel), push(birne), push(apfel), pop(), push(birne)
anfangs ist der stapel leer und wir sind im zustand "idle". kommt nun ein pop() befehl bleiben wir im zustand "idle" weil von nix kommt nix. nun muss unterschieden werden: push(birne) und push(apfl).
es kann als erste eingabe sowohl push(birne) als auch push(apfl) kommen, deshalb brauchen wir von idle zwei folgezustände: b und a und beide haben als ausgang = 0.
man muss noch das pop berücksichtigen, da man damit von b und a wieder zurück in den anfangszustand idle kommt.
in b und a muss man wieder berücksichtigen dass wieder push(birne) und push(apfl) kommen kann => wieder je zwei folgezustände für a und b die man einfach für a: aa und ab und für b: ba und bb nennt.
wiederum muss man die pops berücksichtigen mit denen man immer in den vorigen zustand zurück kommt (von dem her ist dieses beispiel sicher einfacher, da nur 1 zustand zurückgesprungen werden kann).
jetzt schauen wir wieder für aa, ab, ba, bb was geschieht wenn push(birne) und push(apfel) kommt.
aa: aaa, aab
ab: aba, abb
ba: baa, bab
bb: bba, bbb
und entsprechend wieder pops definieren.
da der automat nur folgenden stapel akzeptiert: apfl, birne, birne markieren wir abb (a -> b -> b) als endzustand mit 1.
ich hoff ich hab da nicht einen totalen blödsinn produziert aber so scheint mir das einfach am sinnvollsten und einleuchtestend.
hier noch ein aufbau des binärbaums (eigentlich der zustandsgraph) des stacks
nonamenobody
06-05-2004, 21:27
OK, du nimmst also bis zu drei Elemente auf und kannst sowohl Elemente hinzufügen (dann geht man in deiner Skizze nach unten) bzw. entfernen (dann geht man in deiner Skizze den letzten Pfeil nach oben zurück). "Gültiger Zustand" <=> "Output <= 1".
Danke, ich glaube, mir ist das jetzt klar. :thumb:
lg
Philipp
jo ich hab die pops jetzt nicht eingezeichnet wegen übersichtlichkeit, aber ich glaub ein stack is eh prinzipiell klar:
mit push(x) wird auf den stack einfach das element x draufgelegt und ist somit dann oberstest elemnt und mit pop() wird einfach das oberste element das zuletzt draufgelegt wurde entnommen.
i hob mir aba no nix überlegt was passiert, wenn no mehr push(x) machst wenn scho 3 kisten draufliegen... das is eben eine definitionssache. aber da ein stack meist nur begrenzt ist (in dem fall 3) würd es einen overflow geben oder einfach die operation ungültig sein, bzw wenn 3 kisten drauf sind einfach ein ergebnis herauskommen und ENDE.
ein_stein2000
06-05-2004, 21:31
war das ganze so gemeint? nähere beschreibung im anhang ...
EDIT: hab neue version upgeloaded ...
jo perfekt so hät ich mir das im prinzip auch vorgestellt
ein_stein2000
06-05-2004, 21:37
i mein i hab jetzt NUR push() realisiert bis maximum erreicht ist ... pop() dazunehmen, dann wirds wirklich riesig kompliziert ..
ja schon, aber ich glaub nicht dass sie einen so großen stack machen. wahrscheinlich mit tiefe 2 und 3 sorten. oder gleich nur mit tiefe 2 und 2 sorten reicht auch
nonamenobody
06-05-2004, 21:48
ja schon, aber ich glaub nicht dass sie einen so großen stack machen. wahrscheinlich mit tiefe 2 und 3 sorten. oder gleich nur mit tiefe 2 und 2 sorten reicht auch
Ich kann mir auch nicht vorstellen, dass sie zu viele Zustände + Eingänge machen werden. Du musst ja 2^(eingänge+zustands-ffs) Fälle betrachten, und das werden verdammt schnell verdammt viele. Bis 2^4 ist es halbwegs flott machbar und übersichtlich, außerdem funktioniert bei mehr als 4 Variablen ja auch das KV-Diagramm nicht mehr (!).
lg
Philipp
ja da können wir sicher beruhigt sein. der schildt is der humanste prof. den ich kenne (studiert ja nid umsonst theologie http://hades.gothic.at/iforum/images/smilies/wink.gif).
hmmmm, muss man nicht gleichzeitigkeit auch beachten? sowas in der art: was passiert wenn man apfel & birne gleichzeitig hinzugefügen mag?
im buch mit diesem automaten münzen ding beispiel musste man doch auch eine lösung dafür finden ..
i glab des kannst getrost vergessen, ausserdem gibts 100%ige gleichzeitigkeit eh nie. sonst musst halt über eine ebene springen und dadurch wird das diagramm verdammt kompliziert. ich denk nicht dass das gefordert wird.
hmmmm nagut ....
ärgere mich dass ich erst jetz darauf komme, wär vielleicht gut gewesen den tuti zu fragen ...
ein_stein2000
06-05-2004, 22:23
hmmmm, muss man nicht gleichzeitigkeit auch beachten? sowas in der art: was passiert wenn man apfel & birne gleichzeitig hinzugefügen mag?
im buch mit diesem automaten münzen ding beispiel musste man doch auch eine lösung dafür finden ..also das hab i eigentlich net berücksichtigt ...
aber jetzt im anhang: 2 obstsorten, stack mit 2 elementen, push() und pop()
über jedes feedback freue ich mich ...
es wäre wirklich unheimlich toll, wenn das ein tutor oda ein höhersemestriger mal checken würde :D
EDIT: hatte fehler im dokument (danke an boesie) ... maybe is da wer durcheinander gekommen ... die ausgebesserten sachen sind im dokument jetzt rot markiert ... folgenden scheiß hab i verzapft:
1. bei der übergangstabelle auf der seite 2 hab ich statt eingang zustand geschrieben, das hab i jetzt ausgebessert
2. i hab an fehler beim zustand "idle" in der grafik und auch in der tabelle gehabt
seh schon - hab mich da wo verrant - das müsste manauch nur berücksichtigen wenn man Apfel, Birne 01 .. usw. als bedingung ovn einem Zustand zum anderen hätt
nonamenobody
06-05-2004, 22:37
Ich kann mir nicht vorstellen, dass wirklich gleichzeitige Zustände in dieser Art auftreten können sollen. Wenn, dann sollte es voneinander unabhängige Eingangsvariablen geben, wodurch dann dem höheren Aufwand Rechnung getragen wird und der auch deutlicher wird.
lg
Philipp
ein_stein2000
06-05-2004, 22:42
Ich kann mir nicht vorstellen, dass wirklich gleichzeitige Zustände in dieser Art auftreten können sollen. Wenn, dann sollte es voneinander unabhängige Eingangsvariablen geben, wodurch dann dem höheren Aufwand Rechnung getragen wird und der auch deutlicher wird.
lg
Philippversteh i jetzt nit was du meinst :confused: erklärung plz
Ich denk das Ganze wird mit maximal 4 Variablen auskommen müssen (wegen KV-Diagramm), also vermutlich 3 Flip-Flops (max. 8 Zustände) + 1 Eingang (Apfel/Birne), sonst wirds zu kompliziert. Dann wäre für ein pop() kein Platz. Ist dann zwar kein richtiger Stack mehr, aber zumindest gibt's Vereinfachungen.
Kann natürlich auch sein, dass es mehr Eingänge gibt, vielleicht müssen wir ja nur die Übergangstabelle zeichnen ohne Vereinfachungen+PLA, aber das wird sich wohl erst am Samstag rausstellen.
jop, das hab ich mir grad auch überlegt und deshalb sowas soeben ausprobiert ;)
ein_stein2000
06-05-2004, 22:52
i glaub auch, dass wir codieren und max. übergangstabelle machen müssen ... glaubst was da für ah schas beim KV dann raus kommt :D
und wir kennen unseren helge: er mag sachen verbessern, die leicht und schnell gehn ... bei ner tabelle legt er schablone rüber und fertig ...
nonamenobody
06-05-2004, 23:16
versteh i jetzt nit was du meinst :confused: erklärung plz
Ich meinte, dass dann z.B. e1 == push(Apfel), e2 == push(birne), e3 == pop() gelten sollte. Dann kann innerhalb eines Taktzyklus z.B. e1 UND e2, d.h. füge Apfel und Birne hinzu, übergeben werden. Eine Situation wie 00 == pop(), 01 == push(Apfel) und push(Birne), 10 == push(Apfel), 11 == push(Birne) kann natürlich dasselbe und ist optimierter, aber auch wesentlich unübersichtlicher.
lg
Philipp
ein_stein2000
06-05-2004, 23:22
axo ... naja aber das is wirklich komplizierter dann ..
Headshot
07-05-2004, 09:24
...
über jedes feedback freue ich mich ...
...
hallo ein_stein2000!
war beim tutor nicht der zustand 1. zeile in der übergangsfkt. (in seinem Bsp. E) = LSB im KV-diagramm u. im PLA?
vielleicht bin ich da auch nur ein bisschen verwirrt... :confused:
lg
ein_stein2000
07-05-2004, 11:21
hallo ein_stein2000!
war beim tutor nicht der zustand 1. zeile in der übergangsfkt. (in seinem Bsp. E) = LSB im KV-diagramm u. im PLA?
vielleicht bin ich da auch nur ein bisschen verwirrt... :confused:
lg
sorry, i versteh net was du meinst ....
Sandalwood
07-05-2004, 13:29
hmmm .. es wär aber wirklich interssant, ob/wie wir einen stack_underflow/stack_overflow behandeln , müssen, denn mit nur einem ausgang kommt man dann sicher nicht mehr aus ... obwohl vermutlich bekommen wir eh einen theoretisch unbegrenzten stack, und müssen nur wenn eine gewünschte folge darin vorkommt eine 1 ausgeben, so wie beim beispiel im tut mi'm 1001, halt dass man den pop-befehl zusätzlich hat
Sandalwood
07-05-2004, 13:34
ooops ... *ggg* - ich zieh' meinen annahme mit dem "theoretisch unbegrenzten stack" zurück
ein_stein2000
07-05-2004, 13:36
ooops ... *ggg* - ich zieh' meinen annahme mit dem "theoretisch unbegrenzten stack" zurück
wie den das auf einmal? .... :D
aber i schätz das bsp wird eh net so schwer und außerdem soll es nur wenige punkte dafür geben laut tutor, darüber mach i mir keine sorgen :D
Headshot
07-05-2004, 13:39
sorry, i versteh net was du meinst ....
also ich meine, dass in deiner tabelle K das LSB ist u. beim tutor der eingang.
lg
Sandalwood
07-05-2004, 13:56
über jedes feedback freue ich mich ...
es würde reichen, wenn du bei jeder push operation 1 als zustandsübergang verwendest, bei jeder pop-operation 0, anstatt den zuständen "A", "B" einen Zustand "X" verwendest und anstatt den zuständen "AB", "AA", "BA", "BB" einen Zustand "XX" verwendest.
die seperaten pop-anweisungen für birne und apfel sind nicht notwendig. im buch wird zwar beim poppen ein argument übergeben - das beschreibt aber lediglich das register in das das gepoppte element geschrieben wird (S. 146 2. Absatz) - ich weiss, dass im beispiel proggram sachen wie pop_16(R2) etc stehen, das steht aber im widerspruch zu den Instruktionssequenzen und besagter Textstelle
mfg
ein_stein2000
07-05-2004, 14:22
hm ... jo du hast recht sandalwood, i hab das etwas zu komplex gemacht ... wobei falsch is ansich net ...
@headshot: i hab das no net ganz verstanden, was der tutor da gerede hat .. damit muss i mich noch beschäftigen ... aber so hats mehr sinn, wie ich es gemacht habe ... weil ich ja eingang habe (für mich jedenfalls)
Sandalwood
07-05-2004, 14:25
@einstein *gg* ich hab' ja auch nicht von falsch gesagt ;)
ein_stein2000
07-05-2004, 14:48
i will jetzt net spamen, aber maybe schaut sich net jeder bei jeder antwort den beitrag komplett neu an ... jedenfalls hab ich einen blödsinn beim 2ten beispiel verzapft und die fehler ausgebessert, siehe meinen post#18 (http://hades.gothic.at/iforum/showpost.php?p=127899&postcount=18)
meine 2 cent zur sache:
ich würd mir das ganze in etwa so vorstellen wie die überarbeitete version von ein_stein...
ABER ich glaub nicht dass es tatsächlich notwendig is ein eigenes pop für A (äpfel) und eines für B (birnen) zu haben. so wie ich stacks verstanden hab, kann man immer nur das oberste element poppen (immer diese zweideutigkeiten)...
jetzt meiner weisheit letzter schluss:
00 ... nix passiert (ähnlich wie beim 5-10cent-automaten im buch)
01 ... pushA
10 ... pushB
11 ... pop (und zwar das oberste element im stack)
mein problem bei der angabe is das ich bei sagen wi mal maximaler höhe von 2 elementen im stack auf eine FF-anzahl von 3 komme. PLUS 2 eingangssignale haben wir wiederrum 5 signale von denen die übergangsfunktion abhängt, was leider zuviel für eine vereinfachung mit KV-diagramm ist. und nur den automaten schreiben denke ich wird nicht verlangt sein, das wäre ja witzlos.
vielleicht kann man nur einen weg gehen und streicht dann 3 zustände... was weiß ich... irgendwelche ideen?
lg vertigo :coolgrim:
das kommt 100% zum test oder?
ein_stein2000
07-05-2004, 16:31
meine 2 cent zur sache:
ich würd mir das ganze in etwa so vorstellen wie die überarbeitete version von ein_stein...
ABER ich glaub nicht dass es tatsächlich notwendig is ein eigenes pop für A (äpfel) und eines für B (birnen) zu haben. so wie ich stacks verstanden hab, kann man immer nur das oberste element poppen (immer diese zweideutigkeiten)...
jetzt meiner weisheit letzter schluss:
00 ... nix passiert (ähnlich wie beim 5-10cent-automaten im buch)
01 ... pushA
10 ... pushB
11 ... pop (und zwar das oberste element im stack)
mein problem bei der angabe is das ich bei sagen wi mal maximaler höhe von 2 elementen im stack auf eine FF-anzahl von 3 komme. PLUS 2 eingangssignale haben wir wiederrum 5 signale von denen die übergangsfunktion abhängt, was leider zuviel für eine vereinfachung mit KV-diagramm ist. und nur den automaten schreiben denke ich wird nicht verlangt sein, das wäre ja witzlos.
vielleicht kann man nur einen weg gehen und streicht dann 3 zustände... was weiß ich... irgendwelche ideen?
lg vertigo :coolgrim:
der tutor hat jo gemein, dass KEIN komplettes beispiel kommt ... und i hab das oben auch scho erwähnt ... da wird sicha nur angabe kommen, dann automaten zeichnen, die zustände codiern und die übergangstabelle machn und fertig ...
dann noch ein KV anzuhängen würde wirklich ein chaos geben ... und da gibts einen haufen fehler die man machen kann => scheiße zu verbessern => helge denkt immer an "so wenig wie möglich arbeitn" ;)
abgesehen davon hab i scho vorhher irgendwo gesagt, dass fürs wegnehmen vom stack nur eine operation nötig ist und net 2 wie ichs gemacht habe ...
@tonio: i würd sagen zu 99% ;)
warum kommt ein bsp zum test, das wir nicht mal durchgenommen haben?
ein_stein2000
07-05-2004, 17:54
der tutor hat jo gemein, dass KEIN komplettes beispiel kommt ... und i hab das oben auch scho erwähnt ... da wird sicha nur angabe kommen, dann automaten zeichnen, die zustände codiern und die übergangstabelle machn und fertig ...
dann noch ein KV anzuhängen würde wirklich ein chaos geben ... und da gibts einen haufen fehler die man machen kann => scheiße zu verbessern => helge denkt immer an "so wenig wie möglich arbeitn" ;)
abgesehen davon hab i scho vorhher irgendwo gesagt, dass fürs wegnehmen vom stack nur eine operation nötig ist und net 2 wie ichs gemacht habe ...
@tonio: i würd sagen zu 99% ;)
warum net? vom prinzip her is es ja gleich ...
Hallo Leute
Muss man im Zustandsgraphen beim Idle Zustand auch berücksichtigen wenn ich gleich am Anfang versuche etwas rauszugeben also poppe, ich habe dann nämlich 11 Kanten und das kann ja wohl nicht sein"?
Meine Codierung ist pop 00, push 10 (für Äpfel) und push 11 (für Birnen)
Lg Isabella
Interessant wäre auch, was man jetzt genau ausgeben soll. Ein richtiger Stack würde ja nur bei einem pop() den Wert des gepoppten Elements (Apfel/Birne) ausgeben, dass ist aber imho mit einem Moore-Schaltwerk kaum zu realisieren, weil die Ausgabe dann nicht nur vom Zustand=Inhalt des Stacks abhängen würde, sondern auch von der Eingabe (push oder pop) (geht aber denk ich mit Mealy).
Ich will euch aber jetzt damit nicht verwirren, wahrscheinlich kommt's eh einfacher (z.B. Ausgabe, wenn Apfel oberstes Element ist).
Begrenzt ist der Stack 100%, ein endlicher Automat schafft das nämlich sonst gar nicht (s. TheoInf).
stack beispiele haben wir bei den 3 übungen (audimax) gar nicht durchgenommen. das kann gar nicht kommen!
das liegt vielleicht daran, dass das ganze kein stack beispiel ist sondern ein automaten-beispiel und deswegen sehr wohl kommen kann.
im grunde is es ja wurscht ob man jetzt fünfer und zehner wo rein haut oder äpfel und birnen, das prinzip ist das selbe.
meine 2 cent zur sache:
ich würd mir das ganze in etwa so vorstellen wie die überarbeitete version von ein_stein...
ABER ich glaub nicht dass es tatsächlich notwendig is ein eigenes pop für A (äpfel) und eines für B (birnen) zu haben. so wie ich stacks verstanden hab, kann man immer nur das oberste element poppen (immer diese zweideutigkeiten)...
jetzt meiner weisheit letzter schluss:
00 ... nix passiert (ähnlich wie beim 5-10cent-automaten im buch)
01 ... pushA
10 ... pushB
11 ... pop (und zwar das oberste element im stack)
mein problem bei der angabe is das ich bei sagen wi mal maximaler höhe von 2 elementen im stack auf eine FF-anzahl von 3 komme. PLUS 2 eingangssignale haben wir wiederrum 5 signale von denen die übergangsfunktion abhängt, was leider zuviel für eine vereinfachung mit KV-diagramm ist. und nur den automaten schreiben denke ich wird nicht verlangt sein, das wäre ja witzlos.
vielleicht kann man nur einen weg gehen und streicht dann 3 zustände... was weiß ich... irgendwelche ideen?
lg vertigo :coolgrim:
kann man eigentlich nicht statt zustand 00 01 uns soweiter nicht einfach zustand a / aa / b /bb und so weiter machen ? wäre doch viel übersichtlicher ! die zustände kann man ja benennen wie man will ! oder nicht ?
AmaNoGawa
07-05-2004, 22:20
ja kann man... *spam*
Interessant wäre auch, was man jetzt genau ausgeben soll. Ein richtiger Stack würde ja nur bei einem pop() den Wert des gepoppten Elements (Apfel/Birne) ausgeben, dass ist aber imho mit einem Moore-Schaltwerk kaum zu realisieren, weil die Ausgabe dann nicht nur vom Zustand=Inhalt des Stacks abhängen würde, sondern auch von der Eingabe (push oder pop) (geht aber denk ich mit Mealy).
Ich will euch aber jetzt damit nicht verwirren, wahrscheinlich kommt's eh einfacher (z.B. Ausgabe, wenn Apfel oberstes Element ist).
Begrenzt ist der Stack 100%, ein endlicher Automat schafft das nämlich sonst gar nicht (s. TheoInf).
Genau das dachte ich auch. Also Mealy hab ich gar nicht durchgelesen. :rolleyes:
Nein Mealy kommt nicht, zumindest nicht praktisch. Man (Frau;)) muss nur den unterschied zwischen mealy und Moore kennen.
mfg
sauzachn
08-05-2004, 01:02
was is der unterschied?
Mealy kann neben dem Zustand gleichzeitig auch noch den Eingang berücksichtigen.
kann man eigentlich nicht statt zustand 00 01 uns soweiter nicht einfach zustand a / aa / b /bb und so weiter machen ? wäre doch viel übersichtlicher ! die zustände kann man ja benennen wie man will ! oder nicht ?
das was ich da hingeschrieben hab sind ja auch nicht die zustände sondern die eingangssignale. und da bin ich mir fast sicher das nicht a und b daherkommt sondern (wie seit anfang des semesters) eher nullen und einser.
aber die zustände selber kannst benennen wie du willst. auch mit "zwetschgenknödel" :D
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.