Hausübung
Hausübung
Servus!
Was darf ich denn unter "keine unleserlichen, handschriftlichen Lösungen" verstehen?
Heisst das handschrfitlich ja, aber leserlich?
Oder generell nicht handschriftlich?
Was darf ich denn unter "keine unleserlichen, handschriftlichen Lösungen" verstehen?
Heisst das handschrfitlich ja, aber leserlich?
Oder generell nicht handschriftlich?
-
- Computerversteher
- Beiträge: 317
- Registriert: 30. Okt 2006 21:54
Re: Hausübung
Im Allgemeinen soll es nicht handschriftlich sein sondern gedruckt, die erste Hausübung darf aber handschriftlich sein, weil das Graphen-Zeichnen sonst so umständlich sei, wurde heute gesagt
Re: Hausübung
Hallo zusammen,
ich habe auch eine Frage zur aktuellen Hausübung, Aufgabe 1.3 - Reflexive Transitive Closure:
Im Tutorial auf der Homepage werden beim Warshall-Algorithmus keine Wege der Länge 0 berücksichtigt. Diesbezüglich habe ich mal in den GDI2-Folien vom SS07 nachgeschaut, und dort wird folgendes gesagt:
Vielen Dank im voraus!
ich habe auch eine Frage zur aktuellen Hausübung, Aufgabe 1.3 - Reflexive Transitive Closure:
Im Tutorial auf der Homepage werden beim Warshall-Algorithmus keine Wege der Länge 0 berücksichtigt. Diesbezüglich habe ich mal in den GDI2-Folien vom SS07 nachgeschaut, und dort wird folgendes gesagt:
Kann mir jemand sagen, ob wir nun Wege der Länge 0, also Schlingen an jedem Knoten bzw. 1er auf der Diagonalen, mit berechnen sollen oder nicht?Transitive Hülle
• Zu einem Graphen G definiere analog zur Erreichbarkeitsmatrix die Matrix A* wie folgt:
– A* i,j = 1 falls i=j oder zwischen vi und vj existiert ein Weg in G
– A* i,j = 0 sonst
• A* ist die reflexive, transitive Hülle von A.
• A* ist im wesentlichen die Erreichbarkeitsmatrix von G, wobei auch Wege der Länge 0 berücksichtigt werden.
• Aus A* kann man den Graphen G* bilden. Wir nennen G* die reflexive, transitive Hülle (kurz: transitive Hülle, oder Hülle) von G.
Vielen Dank im voraus!
Re: Hausübung
Soweit ich das in der letzten Veranstaltung verstanden habe:
Schlingen und Wege der Länge 0 sollen betrachtet werden, sofern sie im Graph auch vorhanden sind.
Man kann jedoch nicht davon ausgehen, dass jeder Knoten automatisch auch mit sich selbst verbunden ist (Schlinge) und diese Verbindung die Länge 0 hat.
Schlingen und Wege der Länge 0 sollen betrachtet werden, sofern sie im Graph auch vorhanden sind.
Man kann jedoch nicht davon ausgehen, dass jeder Knoten automatisch auch mit sich selbst verbunden ist (Schlinge) und diese Verbindung die Länge 0 hat.
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d- s:+ a-- C++++ UL++++$ P+>+++ L++ E--- W+++$ N+ o+ K? w O M V- PS+ PE++ Y+ PGP- t--- 5--- X-- R tv b DI++ D+ G e h r y?+
------END GEEK CODE BLOCK------
Version: 3.1
GIT d- s:+ a-- C++++ UL++++$ P+>+++ L++ E--- W+++$ N+ o+ K? w O M V- PS+ PE++ Y+ PGP- t--- 5--- X-- R tv b DI++ D+ G e h r y?+
------END GEEK CODE BLOCK------
-
- Computerversteher
- Beiträge: 370
- Registriert: 15. Okt 2006 18:28
- Wohnort: Wiesbaden
- Kontaktdaten:
Re: Hausübung
wie kommst du denn darauf das diese wege nicht berücksichtig werden?
1. hab ich dazu nichs im tutorial gesehn (würde mich auch wundern)
2. Spielen doch gerade beim warshall algo die länge / gewichte der kanten keine rolle, sondern NUR das sie existieren (1 = weg existiert, 0 = weg existiert nicht)
1. hab ich dazu nichs im tutorial gesehn (würde mich auch wundern)
2. Spielen doch gerade beim warshall algo die länge / gewichte der kanten keine rolle, sondern NUR das sie existieren (1 = weg existiert, 0 = weg existiert nicht)
Re: Hausübung
Wie auch immer wir das in dieser Übung machen sollen, das online gestellte Beispiel ist in jedem Fall inkonsistent:
Eine "reflexive transitive Hülle", die nicht reflexiv ist, macht keinen Sinn (siehe S. 9 in den Informationen zum Floyd-Warshall-Algorithm auf der NCS-Homepage: Hier gehört eigentlich noch (3, 3) mit zur Hülle dazu, ist aber ausgelassen. Anders gesagt: Es ist tatsächlich die Erreichbarkeitsmatrix angegeben, nicht die rtH. Man müsste den Warshall-Algo eigentlich mit zusätzlichen Einsen auf der Hauptdiagonale der Adjazenzmatrix starten, um zur rtH zu kommen).
Eine "reflexive transitive Hülle", die nicht reflexiv ist, macht keinen Sinn (siehe S. 9 in den Informationen zum Floyd-Warshall-Algorithm auf der NCS-Homepage: Hier gehört eigentlich noch (3, 3) mit zur Hülle dazu, ist aber ausgelassen. Anders gesagt: Es ist tatsächlich die Erreichbarkeitsmatrix angegeben, nicht die rtH. Man müsste den Warshall-Algo eigentlich mit zusätzlichen Einsen auf der Hauptdiagonale der Adjazenzmatrix starten, um zur rtH zu kommen).
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.
- N.F.S. Grundtvig
ist wahre Aufklärung für die Verwandten des Erdreichs.
- N.F.S. Grundtvig
-
- Computerversteher
- Beiträge: 370
- Registriert: 15. Okt 2006 18:28
- Wohnort: Wiesbaden
- Kontaktdaten:
Re: Hausübung
hmm, weiso? stimmt doch?
es gibt keinen weg von 3 nach 3, weil 3 keine ausgehenden Kanten hat
alle andren "schleifen" der ref.trasn. Hülle sin angegeben.
Oder meinst du nich das Beispiel auf Seite 9 des "Graphen Tutorials" ?
es gibt keinen weg von 3 nach 3, weil 3 keine ausgehenden Kanten hat
alle andren "schleifen" der ref.trasn. Hülle sin angegeben.
Oder meinst du nich das Beispiel auf Seite 9 des "Graphen Tutorials" ?
Re: Hausübung
Hallo!
Ich hatte genau diese Problematik in der letzten Übung angesprochen und erklärt. Eine 1 existiert in der Matrix, wenn die jeweiligen Knoten mit Kanten, bzw. Schleifen verbunden sind. Falls eine Schleife an dem Knoten existiert, dann wird dieses durch eine 1 in der Matrix dargestellt. Falls auf der Diagonale eine 0 steht, so ist ein Knoten nicht wieder erreichbar, wenn man den selben Knoten als Startknoten gewählt hat.
Joachim
Ich hatte genau diese Problematik in der letzten Übung angesprochen und erklärt. Eine 1 existiert in der Matrix, wenn die jeweiligen Knoten mit Kanten, bzw. Schleifen verbunden sind. Falls eine Schleife an dem Knoten existiert, dann wird dieses durch eine 1 in der Matrix dargestellt. Falls auf der Diagonale eine 0 steht, so ist ein Knoten nicht wieder erreichbar, wenn man den selben Knoten als Startknoten gewählt hat.
Joachim
Re: Hausübung
die reflexive und transitive hülle würde aber schon per definition eine kante zum jeweiligen knoten selbst enthalten. in der aufgabenformulierung ist also vielleicht einfach ein unglücklicher begriff gewählt worden ...
We can do this the hard way or my way ...which is basically the same thing!
Re: Hausübung
Im Kontext der Netzwerke kann man sich durchaus auch selber überlegen, dass es sinnvoll ist, keine Schlaufen mit der Länge 0 anzunehmen.
Eine solche (reflexive) transitive Hülle gibt sonst nämlich keine Antwort mehr darauf, wie lange es mindestens dauert, bis auf eine Anfrage an ein Netz eine Antwort kommt.
Eine solche (reflexive) transitive Hülle gibt sonst nämlich keine Antwort mehr darauf, wie lange es mindestens dauert, bis auf eine Anfrage an ein Netz eine Antwort kommt.
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2
SS 2010 - Tutor FGI 1+2
Re: Hausübung
Doch meine ich.Christoph B hat geschrieben:Oder meinst du nich das Beispiel auf Seite 9 des "Graphen Tutorials" ?
js hat geschrieben:Hallo!
Ich hatte genau diese Problematik in der letzten Übung angesprochen und erklärt. Eine 1 existiert in der Matrix, wenn die jeweiligen Knoten mit Kanten, bzw. Schleifen verbunden sind. Falls eine Schleife an dem Knoten existiert, dann wird dieses durch eine 1 in der Matrix dargestellt. Falls auf der Diagonale eine 0 steht, so ist ein Knoten nicht wieder erreichbar, wenn man den selben Knoten als Startknoten gewählt hat.
Joachim
Ihr könnt für den Algorithmus ja von mir aus definieren, was ihr wollt, aber dann nennt es bitte nicht "reflexive" transitive Hülle. Eine reflexive Relation ist nach wie vor eine, in der für alle a aus der Trägermenge immer (a, a) Element der Relation ist.
Insofern ist die in der Grafik auf S. 9 [Website-Beispiel] dargestellte Hülle nicht reflexiv, ganz unabhängig davon ob genau dies oder ob das Gegenteil nun in in der Praxis Sinn macht oder nicht.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.
- N.F.S. Grundtvig
ist wahre Aufklärung für die Verwandten des Erdreichs.
- N.F.S. Grundtvig
Re: Hausübung
Red*Star hat geschrieben:Ihr könnt für den Algorithmus ja von mir aus definieren, was ihr wollt, aber dann nennt es bitte nicht "reflexive" transitive Hülle. [...]
Insofern ist die in der Grafik auf S. 9 [Website-Beispiel] dargestellte Hülle nicht reflexiv, ganz unabhängig davon ob genau dies oder ob das Gegenteil nun in in der Praxis Sinn macht oder nicht.
Ich sehe das genau so, man sollte einfach transitive Hülle schreiben.baerchen hat geschrieben:die reflexive und transitive hülle würde aber schon per definition eine kante zum jeweiligen knoten selbst enthalten. in der aufgabenformulierung ist also vielleicht einfach ein unglücklicher begriff gewählt worden ...
-
- Computerversteher
- Beiträge: 370
- Registriert: 15. Okt 2006 18:28
- Wohnort: Wiesbaden
- Kontaktdaten:
Re: Hausübung
ah stimmt, sry leute, hatte wohl die genaue Definition aus GDI2 verdrängt.
nach bisserl reinlesen u.a. in die alten GDI2 folien stimm ich aba nu zu: falsche bezeichnung
nach bisserl reinlesen u.a. in die alten GDI2 folien stimm ich aba nu zu: falsche bezeichnung