fb18.de
/ Diplom Informatik
/ Unterbereich Grundstudium
/ Formale Informatik
F2 Aufgabenzettel 1
Jo, nach langer zeit wieder im Forum…gewollt oder ungewollt, das sei mal dahingestellt ;)
So, ich hab mir mal den ertsen Zettel für F2 angegugt, und ich bin schon mit der Präsenzaufgabe überfordert, kann mir die nochma jemand auf deutsch übersetzen?
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS03/F2/F2aufg01.pdf.gznaja und was die Übungs aufgaben angeht, das scheint schon eher meiner muttersprache nah zu kommen, allerdings würde ich gern wissen was ihr anderen euch unter diesem ominösen Zustandsübergangdiagramm (das wort iss schon scheisse ;) ) vorstellt. Im Skrpt sind dazu ja mehrere "Diagramme" abgebildet.
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS03/F2/f2slides1INTRO.pdf.gzthx im voraus
zu diagramm:
eine darstellung des automaten sollte so aussehen:
-----------
| |
| / |
| |
| / / |
| |
-----------
je nach kippstellung,
und das zustandsübergangsdiagramm besteht dann aus einigen
kippstellung -----------------> kippstellung
A, B oder C
zu 1:
das kann jeder andere auch nur interpretieren, das sind doch
alles verständliche sätze in deutschen(!) druckbuchstaben ;),
12 übungsgruppen, je 24 leute, 288 studierende, 50 wollen
einzelnd (in jeder übungsgruppe mindestens 1), der rest in
3er-gruppen, mehr steht da gar nicht
ja gut, thx
und nu zum wichtigsten,
nochma die fragestellung auf deutsch bitteschön ;)
frage 1.:
ist es möglich (bei allen möglichen verteilungen aller 288
leute auf die 12 gruppen), das einer der gruppenwilligen
nicht in eine gruppe kommt (= eine übungsgruppe enthaelt eine
nicht durch 3 teilbare anzahl an gruppenwilligen studenten)
frage 2:
was ist eine 'für die Gruppenarbeit förderlichste Verteilung
der Studierenden auf die Übungsgruppen'?,
ich definiere mal: eine verteilung, bei der die maximale
anzahl an 3er-gruppen (=MAX) erreicht wird
(am besten mal schauen, wie viele 3er-gruppen überhaupt
möglich sind bei 238 gruppenwilligen, und ob dies erreichbar
ist, oder wenn nicht, wie viele 3er-gruppen denn maximal
erreichbar sind)
und dann ist die frage ob es eine verteilung gibt mit der
gleichen anzahl MAX 3er gruppen, mit der einschränkung,
das bei dieser verteilung eine gruppe nur aus einzelwilligen
besteht
Also bei der 1 Ü-Aufgabe ist mit dem Zustandsübergangsdiagramm bestimmt das Diagramm auf S.4 im Skript gemeint. Er wird dort nur als Zustandsgraph bezeichnet, da er sich aber aus der Übergangsfunktion ableiten läßt, könnte man auch evtl. zu ihm Zustandsübergangsdigramm sagen.
Beispiel: Der in der Aufgabe gezeigte Automat hat den Zustand 001 oder 110 (je nachdem welche Bezeichnung Du der Hebelstellung gibst (S. 3)) im Binärcode. Umgerechnet in Dezi ist das entweder 1 oder 6, somit hätten wir hier Zustand:={z1 oder z6}, wenn Du in diesem Zustand gedanklich eine Kugel in den Automaten wirfst, dann ändert sich der Zustand, d.h. aus 001 oder 110 wird 111 oder 000 und soweiter. In diesem neuen Zustand wirfst Du wieder eine Kugel und soweiter. Der Graph dürfte dann so aus sehen, das Du die erreichten Zustände in Kreisen unter oder nebeneinander zeichnest und diese mit Pfeilen verbindest(neben den Pfeilen steht dann immer der Ausgang, also A, B oder C). Wenn Du nur diesen abgebildeten Zustand nimmst, dann erhälst Du nicht alle möglichen Zustände, da Du bei diesem Durchlauf irgendwann (nach 4 Durchläufen) am Anfangszustand bist. Wenn Du aber den Zustand 100, bzw. 011 (wie gesagt je nachdem welche Zahl 0 oder 1 Du welcher Hebelstellung gibst, erhälst Du dann halt 100 oder 011!) als Anfangszustand wählst, erhälst Du die restlichen Zustände, so das sich im Enteffekt zwei Graphen darstellen, vielleicht ist aus diesem Grund auch Zustandsübergangsdigramm gewählt worden und nicht Zustandsgraph, da ja beide unabhängig von einander Zustandsgraphen sind! (Mit anderen Worten sie sind nicht verbunden, wie auf S. 4)
LG Frischling
Ahm, am Ende der Vorlesung war ich nicht mehr ganz da. Kann mal jemand sagen bis wo ich im Skript maximal lesen sollte und welche Folie am Ende war?
Aufgabe 1.2
Wenn k=3 ist, heit das K={0,1,2,3} oder K={1,2,3,4}, wenn es doch heißt x kann auch 0 sein. Schnall ich nicht. In diesem Falle (der Aufgabe) muss es doch bei 1 beginnen, da das ja sonst nicht klappen würde…..
K={1,..,k} und k=3 -> K={1,..,3},
x=0 ist nicht erlaubt (da steht nur, dass das in normalen spielen mit drin ist ;) ),
aber das hat mit dem k-problem ja auch nix zu tun..
ach so in nem Dominospiel findet man die zahlen {0,1,2,3,4,5,7,8}, aber k=9. also kann ich das vergessen und auch mit x,y E {1…9}, also k=9 arbeiten. (is ja schon wichtig anzugeben, wegen der Steineanzahl)
ne, das ist dort eventuell ein bisschen missverständlich
ausgedrückt, aber offensichtlich so gemeint:
fürs zauberspiel: x,y e {1,..,k} (k-Satz)
in normalen domino-spielen: k=9 und 0 erlaubt, also x,y e {0,..,9}
aber für die aufgabe ist nicht interessant was in normalen
domino-spielen los ist, also nicht weiter beachten,
wichtig ist:
fürs zauberspiel: x,y e {1,..,k} (k-Satz)
jo so ungefähr meinte ich …. habs denn bedankt
Na toll, dass man ion der (iv) aufgabe erst zu lesen bekommt, dass Steine der Art |x|x| auch entfernt werden. Die hab ich jetzt in (i) und (ii) da gelassen…ist doch logischer die da zu lassen.
Na toll, dass man ion der (iv) aufgabe erst zu lesen bekommt, dass Steine der Art |x|x| auch entfernt werden.
Ne, das steht auch schon in der Aufgabenstellung:
Ein vollständiger k-Satz, k >= 2, von Spielsteinen besteht aus allen Steinen (x,y) mit x, y \in {1, 2, …, k} derart, dass 1 <= x < y <= k gilt.
Und aus x < y folgt automatisch x != y.
hat jemand einen ansatz für iii)????
Mal Dir mal (genau wie in Aufgabe 1.2.ii) den Graph für k=4 und k=6 auf, und schau Dir an, ob die Graphen einen Eulerschen Kreis bzw. (nach entfernen eines Steins / einer Kante) einen Eulerschen Kantenzug haben. Dann sollte man eigentlich sehen, warum das ganze für gerade k > 4 nicht funktionieren kann.
kannst du mir das genauer erklären ich seh da kein unterschied! Oder ich verstehe den Eulerschen Kreis nichT?! Kannst du das für etwas "nicht" mathematisch versierte nochmal erklären?
Mein Problem ist, wenn ich das mit dominosteinen ausprobiere, bekomme ich trotzdem eine Lösung auch wenn k>4 und gerade ist.
Was mache ich falsch?
Die Steine müßen ja x<y sein, aber beim anlegen ist das dann doch egal, oder? Das Beispiel bei der Aufgabe zeigt ja auch 2|3 3|1.
Ahh was funktioniert hier nicht?
sind die Eulerischen Kreise = die Eulerischen Linien (also das Brückenproblem im M1-Skript)?
LG Frischling
Mein Problem ist, wenn ich das mit dominosteinen ausprobiere, bekomme ich trotzdem eine Lösung auch wenn k>4 und gerade ist.
Was mache ich falsch?
Hmm… also irgendwas machst Du auf jedenfall falsch, für k=6 gibt es für den ZUSCHAUER keine Möglichkeit "aus dem angeblich vollständigen Satz der übrigen Steine eine zusammenhängende Kette zu legen."
sind die Eulerischen Kreise = die Eulerischen Linien (also das Brückenproblem im M1-Skript)?
Ja, mit Eulersche Kreise sind die Eulerschen Linien aus M1 gemeint.
Hmm… also irgendwas machst Du auf jedenfall falsch, für k=6 gibt es für den ZUSCHAUER keine Möglichkeit "aus dem angeblich vollständigen Satz der übrigen Steine eine zusammenhängende Kette zu legen."
wenn ein stein fehlt kann ja nie ein kreis gelegt werden,
aber mit stein klappt es bei geradem k auch nicht,
das ist ja hier die frage,
es gibt einen wichtigen satz, wann eulersche kreise in
graphen auftreten, den muss man im skript finden und hier
anwenden
Kannst du das für etwas "nicht" mathematisch versierte nochmal erklären?
hmm… wo genau hakts denn? Ich wollte jetzt eigentlich nicht meine komplette Lösung posten, dann geht ja der Witz verloren.
wenn ein stein fehlt kann ja nie eine kette gelegt werden,
Fehlt da ein "für gerade k" in dem Satz? Aber selbst wenn, für k=4 kann man auch eine Kette legen, nur das Ergebnis kann man nicht so leicht ablesen…
es gibt einen wichtigen satz, wann eulersche kreise in graphen auftreten, den muss man im skript finden und hier anwenden
*unterstreich* Ohne den Satz kommt man wirklich nicht weiter…
ne soll schon so, aber ich meinte mit 'kette' einen 'kreis' und du wohl korrekterweise nicht [img]
http://www.fb18.de/gfx/22.gif[/img]
und bei gerade k kann auch mit kompletten satz kein kreis gelegt werden, so in der art
ah, dann machts wieder Sinn, was Du da geschrieben hast [img]
http://www.fb18.de/gfx/10.gif[/img]
So sieht das bei mir aus, wenn ich k=6 habe:
Die einzige Bedingung, die sein muß (wie eigentlich immer) ist: es muß jede Zahl des k-Satzes min. 2. mal oder ansonsten immer in gerader Anzahl vorhanden sein.
Beispiel: Ich habe die Dominos 1|3, 1|4, 2|5, 3|6, 2|6, 4|5 daraus lege ich 1|33|66|22|55|44|1 Nehme ich nun einen Stein weg z.B. 6|2 => 2|55|44|11|33|6 und voila es funktioniert
Hmm habt Ihr eine Idee was hier falsch gelaufen ist?
Lg Frischling
Ps: im Aufgabenblatt haben die uns auch ein Beispiel gegeben, das mir sagt, das im Endeffekt bei dem legen der Dominos die Regel x<y nicht relevant ist. (2|3 3|1)
Ist es doch relevant, dann kann 1<=X<y<=k nicht funktionieren (z.B. k=3: 1|2 2|3 3|4(y>k darf nicht sein) 1|2 2|3 1|3 kann nicht gelegt werden).
Wenn die Zahlen keinen gleichen Partner auf einem 2. Stein haben gibt es auch Probleme)
Arrggg Hilfffffffeeeeeeeee!
bei k=6 hast du 15 steine
1|2 1|3 1|4 1|5 1|6
2|3 2|4 ...
...
...
und die bilden keinen kreis und deshalb funktioniert das spiel nicht
Hey,
kannst Du mir das nochmal für Doofe erklären, denn ich vermute, das hier mein Denkfehler lag. Ich hab k als eine Spielstein gesehen. Wie kommst Du auf k=6 sind 15 Steine?
Wofür steht den k?
LG Bianca
'ein vollständiger k-satz besteht aus ALLEN steinen x|y mit x,y e {1,..,k} 1<=x<y<=k'
das sind nun mal bei k=6
für x = 1 y= 2 oder 3 oder 4 oder 5 oder 6
für x = 2 y= 3 oder 4 oder 5 oder 6
für x = 3 y= 4 oder 5 oder 6
usw.
also insgesamt 15 stück:
1|2 1|3 1|4 1|5 1|6
2|3 2|4 2|5 2|6
3|4 3|5 3|6
4|5 4|6
5|6
Ok ich habe es glaube ich jetzt doch kapiert.
Also k steht nicht für ein Stein, sondern für die Möglichkeit, wie man die Zahlen auf einen Stein verteilen kann, wenn 1<=x<y<=k gilt.
Wie bei Dir schon angedeutet:
k= 3 => 1|2 1|3
2|3
Mit 3 läßt sich nix mehr machen, da 3|3 nicht sein darf, somit sind es bei k=3 in diesem Fall zwar auch 3 Steine, aber es könnten evtl. auch mehr Steine sein wie bei k=6 => 19 Steine. Grrr, das hab ich aber nicht aus dieser Aufgabe ablesen können, da aber sich somit die probleme lösen. Kommt das hin.
LG Frischling
Edit: Thanks, ich bin ja nun selber darauf gekommen, mein Posting hatte sich mit Deinem überschnitten.
ja ich weiss nich, die Frage mit dem 4 bleibt mir trozdem ein rätsel. Das funzt ja mit k=4 auch net, also wieso "wenn k>4 gerade ist"
Und falls mir das jemand erklären kann, gibts dann auch sonne Bedingung damits im (iv) klappt, zumindest hab ich als antwort das es klappt, nähmlich wenn k gerade.
ja ich weiss nich, die Frage mit dem 4 bleibt mir trozdem ein rätsel. Das funzt ja mit k=4 auch net, also wieso "wenn k>4 gerade ist"
Stimmt, so wie beschrieben funktioniert der Trick für k=4 nicht. Aber mit einer leichten Abwandlung funktioniert er wieder… (Hint: man schaue sich für k=4 den Graph an, und entferne eine Kante. Dann haben 2 Knoten geraden Grad und 2 Knoten ungeraden Grad)
Aber das ist eigentlich ein eher unwichtiges Detail, gefragt ist ja nur, warum es für ungerade k funktioniert, und warum es für gerade k > 4 nicht funktioniert.
Und falls mir das jemand erklären kann, gibts dann auch sonne Bedingung damits im (iv) klappt, zumindest hab ich als antwort das es klappt, nähmlich wenn k gerade.
In Aufgabe (iv) klappts auch wieder für ungerade k, der Magier muss nur etwas mehr bedenken.
der Magier muss nur etwas mehr bedenken.
Sorry aba da bin ich nich ganz mit dir einverstanden, den da es in dem Fall (iv) keine eulersche linie für ungerade k gibt, kann er den Trick so oda so ja auch nich realisieren (? ;) )
den da es in dem Fall (iv) keine eulersche linie für ungerade k gibt,
Es gibt eine!
huh?
also wenn ich nich alles falsch gemacht habe, dann hat im normal fall jeder knoten eines k satzes k-1 kanten, mit dem fall (x,x) dazu macht das dann k kanten für jeden knoten. wenn nun k ungerade, hat der graph keine eul. linie weil alle knoten ungeraden grades sind. ob du nun ein (x,x) stein oda ein anderen stein wegnimmst, da iss keine eul. linie zu sehen, zumindest nicht für meine augen.
(ich meins nich böse, nur ich seh halt wo da eine eul. linie geben kann)
also wenn ich nich alles falsch gemacht habe, dann hat im normal fall jeder knoten eines k satzes k-1 kanten, mit dem fall (x,x) dazu macht das dann k kanten für jeden knoten.
Nein, k+1, Schlingen zählen doppelt!
AAAAH damn, ich schlaumeier ;P
thx, hat ich ganz verplant :)
Dass mit der Eulerschen Linie mag zwar sein, aber die Frage ist ja, ob der Trick dann noch klappt und wenn der Magier dummerweise einen x|x Stein aus dem Beutel zieht, können die Zuschauer ohne Problem einen Kreis legen und er steht mit seinen beiden Zahlen am Ende der Kette ein wenig dumm da! Der Trick klappt dann also nur noch bedingt!
Oder wie seht ihr das?
hmpf… warum brech ich mir da 'nen Krampf ab mit "muss nur etwas mehr bedenken."? Weil ich eben NICHT die ganze Lösung posten wollte!
Dieser Punkteneid hier [img]
http://www.fb18.de/gfx/15.gif[/img] Was soll er denn bedenken, wenn er ohne hinzusehen einen Stein rauszieht? "uups, hab mich vergriffen, muss noch mal ziehen!" ? Das wäre aber ein Anfänger-Copperfield!
Dieser Punkteneid hier [img]http://www.fb18.de/gfx/15.gif[/img]
Ich wollte den anderen den Spass am selbermachen nicht verderben [img]
http://www.fb18.de/gfx/22.gif[/img]
Was soll er denn bedenken, wenn er ohne hinzusehen einen Stein rauszieht? "uups, hab mich vergriffen, muss noch mal ziehen!" ? Das wäre aber ein Anfänger-Copperfield!
Domino-Steine haben die Eigenschaft, dass man sie ziemlich gut ertasten kann [img]
http://www.fb18.de/gfx/15.gif[/img]
es wurde zwar versucht die Präsenzaufgabe zu übersetzen aber wirklich verstanden habe ich das nicht!
1. Teilaufgabe ist ganz klar JA, da die 50 "nicht-Willigen" nicht in die 12 Gruppen so aufteilbar sind dass die Anzahl derer glatt durch drei teilbar ist
Die 2. Teilaufgabe verstehe ich nun ganz und gar nicht!
Kannmir da denn Jemand weiterhelfen?
frage 2:
was ist eine 'für die Gruppenarbeit förderlichste Verteilung
der Studierenden auf die Übungsgruppen'?,
ich definiere mal: eine verteilung, bei der die maximale
anzahl an 3er-gruppen (=MAX) erreicht wird
(am besten mal schauen, wie viele 3er-gruppen überhaupt
möglich sind bei 238 gruppenwilligen, und ob dies erreichbar
ist, oder wenn nicht, wie viele 3er-gruppen denn maximal
erreichbar sind)
und dann ist die frage ob es eine verteilung gibt mit der
gleichen anzahl MAX 3er gruppen, mit der einschränkung,
das bei dieser verteilung eine gruppe nur aus einzelwilligen
besteht
mal ehrlich was kann man daran nicht verstehen?,
man schaut sich alle verteilungen der 288 leute an, bei denen
optimal viele (also ganz ganz viele) 3er gruppen entstehen,
und wenn bei diesen verteilungen eine dabei ist, bei der eine
übungsgruppe nur aus einzelnen besteht, ruft man laut JA, sonst NEIN ;),
darauf zu kommen ob ja oder nein ist ja durchaus aufwendig,
aber die aufgabe doch klar oder?
