You are not logged in.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

41

Wednesday, March 16th 2005, 9:16pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Mar 16th 2005, 9:20pm)


Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

42

Wednesday, March 16th 2005, 9:37pm

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...

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

43

Thursday, March 17th 2005, 8:48am

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.

schmaidt

Junior Schreiberling

  • "schmaidt" is male

Posts: 159

Date of registration: Feb 25th 2004

Location: Hannover

Occupation: Aus Interesse

44

Thursday, March 17th 2005, 3:15pm

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?
"Man kann beweisen, daß der technische Fortschritt besser ist mit Zucker!"
Ionesco, Die kahle Sängerin

Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

45

Thursday, March 17th 2005, 3:43pm

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

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

46

Thursday, March 17th 2005, 3:45pm

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)?

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

47

Thursday, March 17th 2005, 3:48pm

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.

hohly

Trainee

  • "hohly" is male

Posts: 56

Date of registration: Oct 31st 2003

Location: Hannover

Occupation: frag mich net

48

Thursday, March 17th 2005, 4:23pm

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

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

49

Friday, March 18th 2005, 8:29am

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.

foxy

Praktikant

  • "foxy" is male

Posts: 13

Date of registration: Oct 29th 2004

50

Friday, March 18th 2005, 10:38pm

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.

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

51

Saturday, March 19th 2005, 12:58am

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.
tar: Anlegen eines leeren Archivs wird feige verweigert.

This post has been edited 2 times, last edit by "migu" (Mar 19th 2005, 1:05am)


schmaidt

Junior Schreiberling

  • "schmaidt" is male

Posts: 159

Date of registration: Feb 25th 2004

Location: Hannover

Occupation: Aus Interesse

52

Saturday, March 19th 2005, 5:15pm

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?
"Man kann beweisen, daß der technische Fortschritt besser ist mit Zucker!"
Ionesco, Die kahle Sängerin

schmaidt

Junior Schreiberling

  • "schmaidt" is male

Posts: 159

Date of registration: Feb 25th 2004

Location: Hannover

Occupation: Aus Interesse

53

Saturday, March 19th 2005, 5:20pm

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?
"Man kann beweisen, daß der technische Fortschritt besser ist mit Zucker!"
Ionesco, Die kahle Sängerin

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

54

Sunday, March 20th 2005, 11:58am

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?

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

55

Sunday, March 20th 2005, 2:29pm

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)
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

56

Sunday, March 20th 2005, 4:05pm

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

This post has been edited 1 times, last edit by "NullAhnung" (Mar 20th 2005, 4:05pm)


Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

57

Sunday, March 20th 2005, 4:52pm

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.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

This post has been edited 1 times, last edit by "Informatik Minister" (Mar 20th 2005, 4:54pm)


NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

58

Sunday, March 20th 2005, 6:05pm

Danke. Ich denke jetzt hab ichs verstanden.

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

59

Monday, March 21st 2005, 9:14am

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

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

60

Tuesday, March 22nd 2005, 12:44pm

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
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...