D120.de/forum

Es gilt O(m log m) = O(m log n), da m max. aus O(n^2) und log(n^2) = 2*log(n) wenn ich in Mathe richtig aufgepasst habe

Zu diesem Thema habe ich auch eine Frage: Wie werden die Kanten beim dualen Graphen im Falle von gerichteten Graphen gerichtet? Im Skript heisst es dazu auf Folie 312 "In the directed case, we orient e* = (f1, f2) in such a way that f1 is the face “to the right” when traversing the Jordan curve corr...

Warum ein Zyklus im Vorgängergraph zwangsläuig negative Länge hat, ist klar. Die Frage ist: WIE erkennt man einen Zyklus in O(n)? Kann man nicht argumentieren, dass der Vorgängergraph nur m=n-1 Kanten besitzt. Denn so ist er nach meinem Verständnis definiert (jedem Knoten wird ein Vorgänger eindeut...

Ich habe auch noch eine: Auf Folie 109 steht "Label setting algorithms are applicable only to directed acyclic graphs (DAGs) OR to graphs with non-negative arc lengths". Jedoch ist auf Folie 133 schon ein Beispiel angegeben für einen DAG wo Dijkstra nicht funktioniert, oder?

Also ich glaube dass der Graph links nicht ganz zum Ergebnis rechts passt. Die Kante (5,4) taucht im Topsort Graphen nicht auf, dafür aber Kanten (3,4) und (5,7) die der Graph links nicht enthält, oder sehe ich das falsch?

Bei deinem Beispiel hast du die Bipartition A={a,c,b} und B={e,d,f}. Jetzt hab ich angenommen es wurde bereits ein maximales matching gefunden. Hier zb die Kanten (c,e) und (b,d) (geht auch mit jedem anderen max. Matching). Jetzt musst du für jede Kante überlegen, welchen Knoten du in die Knotenüber...

Also ich habe angenommen, dass ich bereits ein Matching mit maximaler Kardinalität kenne (und natürlich die Bipartition) und daraus kann man dann ganz einfach eine minimale Knotenüberdeckung finden (man muss auf die M-alternierenden Pfade achten). Und in bipartiten Graphen ist -- wenn ich das in der...

Hallo, also ich kann dem ersten Beitrag zustimmen. Ich mache die Übungen meistens am Wochenende da ich während der Woche wegen Vorlesungen und Arbeiten nicht viel Zeit dafür habe. Bei mir geht das auch komplett dafür drauf zudem bin ich dann Montags noch nicht ganz mit allem fertig. Das Argument mit...

Mi., 16.01.2008, 15.00h – 16.00h, Raum A313 wurde in der Übung am Donnerstag bekanntgegeben

Also ich sehe das ähnlich. Die Klausuraufgaben fand ich auch sehr fair. Am Ende habe ich keine Zeit/Lust gehabt die NTP Werte auszurechnen und Induktion hab ich eigentlich keine gemacht, sondern ein Gegenbeispiel, aber bin mir auch gerade nicht mehr sicher wierum die Bedingung war.

Hallo,
gibt es eigentlich schon eine Bonusregelung für die Punkte in den theoretischen Übungsaufgaben? Es hieß ja am Anfang, das diese einen Bonus von einem 0.3 Notenschritt ausmachen. Wieviel Prozent der Punkte muss man denn dafür erreichen. Wäre halt schon gut zu wissen.

Kann auch folgendes kleines rmi Tutorial empfehlen, hat mir zumindest sehr geholfen http://www.mm.informatik.tu-darmstadt.d ... orial.html

Erstmal danke fuer die Antworten, hat mir sehr geholfen. Muss jetzt nicht richtig sein, was ich sage, aber anders kann ich mir auch keinen Reim darauf machen. Und (verblüffend ähnliche ^^) andere Foliensätze anderer Unis haben das eben so drin (FIFO -->g, kausal -->) So sehe ich das auch. Das einzig...

Ich verstehe den Unterschied zwischen FIFO und causal Multicast von Folie 51 nicht. Für mich sehen die Definitionen irgendwie gleich aus. Kann mir das vielleicht jemand mit eigenen Worten erklären? Wäre nett

Sollen bei der Aufgabe 2.2 a),b),c) jeweils alle Ereignispaare fuer die das zutrifft aufgeschrieben werden, oder reicht da jeweils ein Beispiel mit einem Paar?