Hausübung

Benutzeravatar
Shoggo
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 26. Okt 2005 19:23
Wohnort: Darmstadt

Hausübung

Beitrag von Shoggo »

Servus!

Was darf ich denn unter "keine unleserlichen, handschriftlichen Lösungen" verstehen?
Heisst das handschrfitlich ja, aber leserlich?
Oder generell nicht handschriftlich?
Shinson Hapkido - Bewegung für das Leben
Shinson Hapkido Trailer

SebFreutel
Computerversteher
Computerversteher
Beiträge: 317
Registriert: 30. Okt 2006 21:54

Re: Hausübung

Beitrag von SebFreutel »

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

kechler
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 21. Nov 2004 22:33
Wohnort: Darmstadt

Re: Hausübung

Beitrag von kechler »

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:
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.
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?
Vielen Dank im voraus!

Benutzeravatar
kahler
Computerversteher
Computerversteher
Beiträge: 351
Registriert: 17. Apr 2004 11:24

Re: Hausübung

Beitrag von kahler »

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

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Re: Hausübung

Beitrag von Christoph B »

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)

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: Hausübung

Beitrag von Red*Star »

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).
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Re: Hausübung

Beitrag von Christoph B »

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

js
Erstie
Erstie
Beiträge: 21
Registriert: 31. Mär 2006 15:12

Re: Hausübung

Beitrag von js »

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

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

Re: Hausübung

Beitrag von baerchen »

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!

Benutzeravatar
Tapion
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 14. Okt 2006 19:16
Wohnort: Darmstadt

Re: Hausübung

Beitrag von Tapion »

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.
WS 2010/11 - Tutor GDI 1
SS 2010 - Tutor FGI 1+2

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: Hausübung

Beitrag von Red*Star »

Christoph B hat geschrieben:Oder meinst du nich das Beispiel auf Seite 9 des "Graphen Tutorials" ?
Doch meine ich.
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

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Re: Hausübung

Beitrag von Edoat »

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.
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 ...
Ich sehe das genau so, man sollte einfach transitive Hülle schreiben.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Re: Hausübung

Beitrag von Christoph B »

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

Antworten

Zurück zu „Archiv“