Hilfe zur Klausuraufgabe Klausur Sep 2010 (SS 2010)

Ottokarotto

Ottokarotto

Ort
Am Fuße der Schwäbischen Alb
Hochschulabschluss
Diplom
2. Hochschulabschluss
Bachelor of Science
Studiengang
M.Sc. Wirtschaftswissenschaft
ECTS Credit Points
120 von 120
Will ich mal den Anfang machen ( obwohl noch nicht fertig ):

1)
a) zyklenfrei
b) 4 Pfeile ( Zyklus aus 5 Knoten und 4 Pfeilen )
c) (1) <->(2)<-(3)<->(4)<-(5)
d) 120 ( wenn man die rotationssymetrischen alle mitzählt )
Beispiel wäre: |_| ; Z ; |/_
e) ähnlich zu einer späteren Klausuraufgabe
f) ja; Begründung?.... weil eine Einfärbung mit 2 Farben alternierend möglich ist?... ( Spoiler zu Aufgabe 5 )

2)
Dijkstra.... oder was anderes....
Gesamtkilometer: 37, gespart 45
3)
Abteilung E mit Gesamt"kosten" von 22800 ( bissle gemein, wenn man erst die anderen Summen berechnet, ... unendlicher Rechenaufwand, wie in der Schule :(
b) habe ich aus Faulheit noch nicht gemacht

4) muß noch

5)
a)
Tiefensuche: A - b - E - c - G - d - H - i... zurück und von d - K - f
b)
Breitensuche:
1) A
2) b d
3) E ; G ,H, K
4) c , f ; I
...hoffentlich kann man das überhaupt lesen später ...
c) bipartit

soweit, so gut ( oder schlecht? )
 
Ottokarotto schrieb:
Will ich mal den Anfang machen ( obwohl noch nicht fertig ):

1)
a) zyklenfrei
b) 4 Pfeile ( Zyklus aus 5 Knoten und 4 Pfeilen )
c) (1) <->(2)<-(3)<->(4)<-(5)
d) 120 ( wenn man die rotationssymetrischen alle mitzählt )
Beispiel wäre: |_| ; Z ; |/_
e) ähnlich zu einer späteren Klausuraufgabe
f) ja; Begründung?.... weil eine Einfärbung mit 2 Farben alternierend möglich ist?... ( Spoiler zu Aufgabe 5 )
Zum Vergrößern anklicken....

1b) 5 Pfeile, wenn es ein Zyklus sein soll

1d) Bsp. sind ok, aber wie kommst du auf 120?
Ich habe irgendwo gefunden, dass die Anzahl Gerüste von vollst. Graphen n^(n-2) ist

1e)
die Aufgabe war zwar 9/12 ähnlich wieder dran, aber vllt. sollten wir doch mal darüber sprechen, denn ich finde die Zusammenhangskomponenten sind (für mich) nicht so leicht verständlich
Zyklen: 1-2-4-1, 3-6-3, 8-10-8, 1-2-5-4-1
schwache ZHK: jeder Unterdigraph (Knoten 1...7 und 8...10)
starke ZHK: Knoten 1,2,3,4,5,6,8,10 und Senke 9
Was ist mit Knoten 7?

1f)
bipartit, weil sich die Knotenmenge so in 2 nichtleere Teilmengen zerlegen lässt, dass jeder Knoten der einen Teilmenge mit einem Knoten der anderen Teilmenge verbunden ist (Teilmengen R={1,5,6,8} und S={2,3,4,7})
 
Ottokarotto schrieb:
2)
Dijkstra.... oder was anderes....
Gesamtkilometer: 37, gespart 45
Zum Vergrößern anklicken....

m.E. ist nach Minimalgerüst und nicht nach kürzesten Wegen gefragt. Zitat: "... die Gesamtlänge... möglichst kurz ist" Also nicht, dass jeder Weg möglicht kurz ist

Habe deshalb Kruskal oder/und Prim angewandt und spare bei Kruskal 45 und bei Prim 43.
 
Ottokarotto schrieb:
3)
Abteilung E mit Gesamt"kosten" von 22800 ( bissle gemein, wenn man erst die anderen Summen berechnet, ... unendlicher Rechenaufwand, wie in der Schule :(
b) habe ich aus Faulheit noch nicht gemacht
Zum Vergrößern anklicken....

komme bei a) auf 23.000 für E

b) 2. Standort ist D, der A bis D beliefert
 
Ottokarotto schrieb:
5)
a)
Tiefensuche: A - b - E - c - G - d - H - i... zurück und von d - K - f
b)
Breitensuche:
1) A
2) b d
3) E ; G ,H, K
4) c , f ; I
...hoffentlich kann man das überhaupt lesen später ...
c) bipartit
Zum Vergrößern anklicken....

bei b) und c) stimme ich zu. aber a) habe ich anders

a)
ich expandiere von a aus d und b, also kann d nicht an g "hängen"
und f wird von e aus expandiert
also:
a: exp. d und b
b: exp. e
e: exp. c und f
c: exp. g
g: exp. i
i: exp. h
zurück zu e
gehe zu f
exp. k
zurück zu a
gehe zu d
Ende

bei der Breitensuche in b) habe ich noch angegeben (gezeichnet), dass d an a, e,g,h,k an d und c,f, i an e hängen

{Korrektur: s. Beitrag 18}
 
Es gibt ja noch ein 5d)
1. Schritt (vorgegeben): f_alt = 2 f_neu=6, delta=4, e=0,45, keine Akzeptanz
2. Schritt: gleiche Ausgangssit. wie im 1. Schritt, also f_alt=2, jetzt f zur Menge K hinzugefügt, f_neu=0, delta = -2 Akz.
3. Schritt: keine Änd. mehr, delta = 0, opt. Lös.
 
Aufgabe 4
a) möglichst hohe TK (unendlich, zumindest größer als alle vorhandenen TK)
b)
1. B1-H2 = 350
2. B3-h2 = 420
3. B3-H1 = 140
4. B2-H1 = 490
5. b2-H3 = 210 (fiktiv)

c) TK = 5810 (inkl. fiktive Liefermenge, da vereinbart)
B2 würde die 210 an H2 liefern, da die TK zu H2 (4) geringer als zu H1 (6) sind
 
Aufgabe 1
übliche Probleme bei starker und schwacher Zh; d weiß ich auch nicht wieso 120
Aufgabe 2
Kruskal mit auch 45 km
Aufgabe 3
auch 23000 und bei b Standort D (Aufgabe wie in der Schule, als ob man nachfragen muss,ob alle mit dem Taschenrechner umgehen können);
Aufgabe 4
bei b Transportplan klar; bei c Kosten von 5600 ohne den fiktiven Transport; und wenn ich zuordnen müsste dann nach H2, da dort die Kosten am geringsten
Aufgabe 5
a. meine Reihenfolge lautet a-b-e-f-k-c-h-i-d-g; b Reihenfolge a-b-d-c-e-h-g-k-f-i
d. meine letzte Nachbarlösung lautet R=a c f g h und K=b d e i k; aber da gibt es ja wohl mehrere Möglichkeiten des Umfärbens
 
MIJM schrieb:
Aufgabe 5
a. meine Reihenfolge lautet a-b-e-f-k-c-h-i-d-g; b Reihenfolge a-b-d-c-e-h-g-k-f-i
d. meine letzte Nachbarlösung lautet R=a c f g h und K=b d e i k; aber da gibt es ja wohl mehrere Möglichkeiten des Umfärbens
Zum Vergrößern anklicken....

Mit a und b bin ich nicht einverstanden. Könnten wir ja noch mal besprechen. Bei d gibts mehrere Mögl., ob deine stimmig ist, habe ich jetzt nicht geprüft.
 
also:
a: exp. d und b
b: exp. e
e: exp. c und f
c: exp. g
g: exp. i
i: exp. h
zurück zu e
gehe zu f
exp. k
zurück zu a
gehe zu d
Ende
Zum Vergrößern anklicken....

gleich mal nachhaken...
Tiefensuche bedeutet aber doch, daß ich eben nur eine Möglichkeit expandiere, solange, wie es geht... in einer Sackgasse zurückgehe, solange bis eine neue Möglichkeit auftaucht und dann von dort weiter.

deswegen würde ich von a nur b expandieren...in Deiner Schreibweise:
a: exp b: exp e: exp c: exp h: exp d: exp h: exp i. ... g ist schon expandiert, deswegen gehts jetzt zurück zu... d: exp k: exp f END.
 
Ottokarotto schrieb:
gleich mal nachhaken...
Tiefensuche bedeutet aber doch, daß ich eben nur eine Möglichkeit expandiere, solange, wie es geht... in einer Sackgasse zurückgehe, solange bis eine neue Möglichkeit auftaucht und dann von dort weiter.

deswegen würde ich von a nur b expandieren...in Deiner Schreibweise:
a: exp b: exp e: exp c: exp h: exp d: exp h: exp i. ... g ist schon expandiert, deswegen gehts jetzt zurück zu... d: exp k: exp f END.
Zum Vergrößern anklicken....

Das ist ein gutes Arg., ich hätte in Informatik auch so expandiert. Aber schau mal Bsp. S. 29 ff. (KE3) an. An die Sichtweise des LS sollte man sich zumindest in Klausuren halten.
 
Danke für den Tip - da würde ich allerdings sagen, daß die Grafik nicht mit dem Text korrespondiert ( also die Tiefensuche...! )
Knoten 2 und 5 würden m.E. gar nie besucht werden, müßten demzufolge auch auf der Grafik nicht eingezeichnet werden.

Das wäre mal 'ne Frage an den Lehrstuhl - die haben sich ja noch nicht mit Aktionismus hervorgetan bisher ;)
 
Habe die Tiefensuche lexikographisch gemacht. Irgendeine Reihenfolge denke ich sollte es geben.
Also von a aus zwei Möglichkeiten, nehme b, dann e, dann f, dann k, fertig.
zurück zu c, dann g, dann i, fertig.
zurück zu d, dann h.
 
Bei Tiefensuche muss ich doch aber zuerst einen Ast bis zum Ende fertigmachen, und dann wieder von oben anfangen:thumbsdown: es ist zum Haareraufen.
 
Sorry, Zitat zu kurz, ich meine in e darfst Du nicht f sonder c nehmen, denn wenn Du eine Wahl hast ( und du hast in e 3 Möglickeiten : c, d, f ) muß die die lexikographisch kleinste Möglichkeit wählen .... ( so sehe ich das.. )
 
MIJM schrieb:
Habe die Tiefensuche lexikographisch gemacht. Irgendeine Reihenfolge denke ich sollte es geben.
Also von a aus zwei Möglichkeiten, nehme b, dann e, dann f, dann k, fertig.
zurück zu c, dann g, dann i, fertig....
Zum Vergrößern anklicken....

Warum nach i "fertig" und nicht noch h? "Lexikographisch" bedeutet doch nur die Reihenfolge der Wahl, wenn man mehrere Alternativen hat. Aber bei i habe ich nur h und muss es nehmen, auch wenn h im Alphabet vor i kommt. Ansonsten ist die Tiefensuche ja schwachsinnig.
 
Zur Aufgabe 5a):
Beim Vergleich mit dem Skript (dort steigende Zahlen) habe ich nicht auf last in - first out und die lexikogr. Ordnung beachtet.

Jetzt: abdeghkfic

a exp. b, d
d (last in) exp. e,g,h,k
k (last in) exp. f (ende)
h exp. i (ende)
g exp. c (ende)


5b)

hier first in - first out
abdeghkcfi

a exp.b,d
b exp. e
d exp. d,h,k
e exp. c,f
g exp. i

d)
1. IS: Fneu=4 (nicht 6!) deshalb akzept.
2. IS: f in K, fneu=4 delta = 0, e ist 1 akzept.
3. IS: e in R, fneu=0 delta=-4 akzept.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben