Fachrat Informatik - Forum

Quoted

Original von Uprooter
zu ü 11 aufg 2, da sie falsch formuliert wurde, heisst es, dass die jetzt gar nicht mehr vorkommen kann in der klausur?

Du solltest dich von der Vorstellung lösen, daß in der Klausur nur Übungsaufgaben reproduziert werden.

So wie ich Niklas kenne wird es genug Aufgaben in der Klausur geben, die zwar Übungsaufgaben ähneln, aber trotzdem das Verständnis der dahinterliegenden Konzepte verlangen.

Was ich damit sagen will: Die Frage "Kommt Aufgabe xy dran?" ist ziemlich sinnlos, besser ist die Frage "Kommen die Themen aus der Vorlesung dran, die in Aufgabe xy behandelt werden?" -- und die Antwort auf solche Fragen sind in der Regel "Ja". In diesem Fall sogar besonders, da es um die Analyse eines vorgegebenen Sortieralgorithmus ging. Das ist IMHO bestimmt Klausurstoff.

ja aber ist die einzige aufgabe dieser art, die auch in der stundenübung nicht behandelt wurde(oder?) und wozu es auch keine musterlösung gibt...

Quoted

Original von Uprooter
ja aber ist die einzige aufgabe dieser art, die auch in der stundenübung nicht behandelt wurde(oder?) und wozu es auch keine musterlösung gibt...

So direkt wurde das nicht behandelt, das stimmt. Aber grundsätzlich gilt, was Joachim geschrieben hat: Algorithmenanalyse, speziell von Sortieralgorithmen, ist wichtig. Um Aufgabe 11/2 besser zu verstehen (trotz falscher Formulierung), sieh Dir bitte das Kapitel über Bucketsort im Skript an. Desweiteren kannst Du auch die Aufgabe 11/2 aus einem der vorigen Semester bearbeiten.

Übrigens geht es mir nicht darum, hier jemanden als "dumm" abzustempeln. Ich würde mich nur freuen, wenn jeder, bevor er eine Frage formuliert, das zur verfügung stehende Material studiert. In der Frage sollte dann auch zum Ausdruck kommen, welche Quellen bereits gelesen (aber evtl. nicht verstanden) wurden.

Also z.B.: "Ich habe die Definition der B+-Bäume gelesen, aber mir scheint, dass für einen gegebenen Baum mehrere Ordnungen zutreffen könnten."

anstatt: "Ich verstehe nicht, was die Ordnung ist."

Das gilt übrigens allgemein als guter Ton in allen Foren. Allzuoft werden nämlich Fragen von der Art gestellt: "Ich weiß, dass die Antwort auf meine Frage in Dokument XY steht, aber ich möchte, dass ihr das für mich lest und es mir dann erklärt." Es ist keine Schande, etwas nicht zu verstehen, nur sich nicht bemüht zu haben.

Ich habe da mal eine andere Frage. Um vorab gleich einmal Entwarnung zu geben (*g*): Ich habe die Kapitel im Skript zur Graphentheorie gelesen und meiner Meinung nach auch verstanden. Dies wollte mich an der letzten freiwilligen Übung überprüfen. Aber: Es ist keine Musterlösung da. Falls es die nicht gibt, dann hier mal meine Ergbenisse zum Vergleich mit hoffentlich anderen:

1a) freie Bäume sind: alpha, beta, gamma ,delta
1b) Cliquen sind: gamma, delta, epsilon, zeta
1c) zyklenfrei: alpha, beta, gamma, delta, eta, theta
2a) Wenn man nach deren Abfolge im Alphabet mit 1,2,3,... nummeriert:
0010100
0010001
1100101
0000101
0011010
0000100
0111000
2b) l_A=(F,G), l_E=(f,r), l_F=(A,E,L,R), l_G=(A,R,L), l_L=(F,G,O), l_O=(L), l_R=(E,F,G)
2c) Bei der Breitensuche habe ich folgenden Durchlauf: A-F-G-E-R-L-O
2d) Bei der Tiefensuche habe ich diesen Durchlauf: A-F-L-G-R-E-O

Habt ihr das auch?

wann ist ein ungerichteter graph zyklenfrei bzw wann ist er zyklisch? wann ist ein gerichteter baum ne clique?

Hm, bei Breiten- und Tiefensuche habe ich andere Ergebnisse. Hast Du daran gedacht, dass bei mehreren Möglichkeiten der alphabetisch nächste Knoten zuerst besucht wird (wg. Reihenfolge im Speicher)?

Quoted

Original von Uprooter
wann ist ein ungerichteter graph zyklenfrei[...]?

Wenn es keinen injektiven Kantenweg von einem Knoten auf sich selbst gibt.

Quoted

wann ist ein gerichteter baum ne clique?

Nie. Ein Baum ist immer zyklenfrei und somit nie kantenvollständig.

@ np kannst du vlt die ergebnisse für üb13 reinposten ?

Quoted

Original von hohly
@ np kannst du vlt die ergebnisse für üb13 reinposten ?

Ich hatte gestern folgende Ergebnisse:
Breitendurchlauf: AFGELRO
Tiefendurchlauf: AFERLOG

Ohne Gewähr, da ich es nicht nochmal nachgeprüft habe.

Leute, die Musterlösung von der Übung 13 steht teilweise schon seit ca. 2 Jahre lang im Netz (DuA WS02/03).

Nur die letzte Aufgabe (so ein Rätsel zwischen Spaniern & Insulanern) fehlt uns noch. Weiß jemand wie man die lösen kann??oder was für Schlüsselwort?hab schon die ganze Zeit mit Google gesucht,aber ohne Erfolg.

Quoted

Original von foxy
Nur die letzte Aufgabe (so ein Rätsel zwischen Spaniern & Insulanern) fehlt uns noch. Weiß jemand wie man die lösen kann??oder was für Schlüsselwort?hab schon die ganze Zeit mit Google gesucht,aber ohne Erfolg.

Das ist eine erfundene Aufgabe, die man aber mit dem Vorlesungsstoff leicht lösen kann. Stichwort: freier Baum

zu a) einfach der Reihe nach eine Kante entfernen bis der Graph in zwei Teilgraphen zerfällt. Dabei ist darauf zu achten, nur unnötige Kanten zu entfernen, also solche, die Zyklen im Graph verursachen. Es gewinnt, wer die letzte Kante entfernte, bevor der Graph in zwei Teilgraphen zerfällt (klar).

zu b) Der Ausgangsgraph hat 21 Knoten und 30 Kanten. Ein spannender Baum des Graphen hat somit genau 20 Kanten. Daraus folgt, dass 10 Kanten entfernt werden dürfen, bevor der Graph zerfällt. Also verliert derjenige, der anfängt, weil er die elfte Kante entfernen muss.

Quoted

Original von np

Quoted

Original von hohly
@ np kannst du vlt die ergebnisse für üb13 reinposten ?

Ich hatte gestern folgende Ergebnisse:
Breitendurchlauf: AFGELRO
Tiefendurchlauf: AFERLOG

Ohne Gewähr, da ich es nicht nochmal nachgeprüft habe.

Also, das stimmt doch nicht, oder? Also in der Stundenübung heißt es bei Tiefendurchlauf: Beginne mit einem noch nicht besuchten Knoten. Besuche seinen ersten Nachbarn, dann dessen ersten Nachbarn ... dann den zweiten Nachbarn, dann dessen ersten Nachbarn ...

So, und das angewendet auf den Graph ergibt doch (mit alphabetischer Sortierung): A-F-E-R-G-L-O

Also der erste Nachbar von R ist doch G, oder?

Quoted

Original von foxy
Leute, die Musterlösung von der Übung 13 steht teilweise schon seit ca. 2 Jahre lang im Netz (DuA WS02/03).

Ja, aber die hat mal mit der von diesem Semester außer dem Thema Graphentheorie nichts gemeinsam, oder gucke ich irgendwo falsch?

Skript Beispiel 7.9:
Wie komme ich da auf f? Die Erklärung versteh ich irgendwie nicht. Wann ein Knoten grau gefärbt wird ist klar, aber wann ist er denn schwarz gefärbt?

Quoted

Original von NullAhnung
Skript Beispiel 7.9:
Wie komme ich da auf f? Die Erklärung versteh ich irgendwie nicht. Wann ein Knoten grau gefärbt wird ist klar, aber wann ist er denn schwarz gefärbt?

Du nimmst den gerichteten Graph aus Beispiel 7.8 und durchläufst ihn per Tiefendurchlauf. Dabei zählst du die Zeitschritte, wobei der Übergang von einem Knoten zum nächsten (oder eben vorherigem, falls du zurücklaufen musst, da ein Knoten keine nicht markierten Nachfolger hat) einem Schritt entspricht. d(u) ist dann dieser Zähler, wenn du zum ersten Mal einen Knoten u findest. f wird für einen Knoten u gesetzt, wenn alle seine Nachfolger gefunden wurden, du also nie wieder zu diesem Knoten beim Durchlauf zurückkehren wirst.

Der Durchlauf ist dann:
4-7-3-2-1-5-1-2-6-2-3-7-4-8-4-fertig = 16 Schritte

(Beispiel 7.9 aus dem Skript vom 18.11.2002, aber dürfte das gleiche sein)

Kann es sein dass dann im Skript die Werte für u=5 und u=6 vertauscht sind?

Quoted

Original von NullAhnung
Kann es sein dass dann im Skript die Werte für u=5 und u=6 vertauscht sind?

Bei mir sind
pred[5]=1
d[5]=6
f[5]=7
pred[6]=5
d[6]=9
f[6]=10

und das stimmt so (siehe mein Durchlauf oben).
4-7-3-2-1-5-1-2-6-2-3-7-4-8-4-fertig

Bei dem Durchlauf haben beide Knoten keine unmarkierten Nachfolger, also ist f (finished) der beiden Knoten genau d+1. Ein Schritt nachdem man die Knoten entdeckt hat, ist man mit ihnen fertig und wandert als nächstes "einen Schritt nach oben".

Der Durchlauf ist natürlich nur einer von mehreren möglichen Durchläufen bei der Tiefensuche.

Danke. Ich denke jetzt hab ichs verstanden.

Quoted

Original von schmaidt

Quoted

Original von np

Quoted

Original von hohly
@ np kannst du vlt die ergebnisse für üb13 reinposten ?

Ich hatte gestern folgende Ergebnisse:
Breitendurchlauf: AFGELRO
Tiefendurchlauf: AFERLOG

Ohne Gewähr, da ich es nicht nochmal nachgeprüft habe.

Also, das stimmt doch nicht, oder? Also in der Stundenübung heißt es bei Tiefendurchlauf: Beginne mit einem noch nicht besuchten Knoten. Besuche seinen ersten Nachbarn, dann dessen ersten Nachbarn ... dann den zweiten Nachbarn, dann dessen ersten Nachbarn ...

So, und das angewendet auf den Graph ergibt doch (mit alphabetischer Sortierung): A-F-E-R-G-L-O

Also der erste Nachbar von R ist doch G, oder?

Ja, du hast natürlich recht. Daher ja ohne Gewähr.

Hier ist übrigens die richtige Lösung:
http://www.gdv.uni-hannover.de/download.…b/blatt12_l.pdf

Moin,

kann mir bitte mal jemand sagen, was nochmal 'relativ prim' bedeutet? hab das irgendwie in den Gängen meines Gehirns vergessen und find es nimmer.

Danke schonmal