Die Suche ergab 20 Treffer

von Andi
9. Feb 2009 19:53
Forum: Effiziente Graphenalgorithmen
Thema: Laufzeitkomplexitäten von MST-Algorithmen
Antworten: 2
Zugriffe: 195

Re: Laufzeitkomplexitäten von MST-Algorithmen

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 :)
von Andi
8. Feb 2009 13:07
Forum: Effiziente Graphenalgorithmen
Thema: Planare Graphen
Antworten: 4
Zugriffe: 261

Re: Planare Graphen

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...
von Andi
7. Feb 2009 12:01
Forum: Effiziente Graphenalgorithmen
Thema: Fragen zu Kapitel 4
Antworten: 14
Zugriffe: 692

Re: Fragen zu Kapitel 4

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...
von Andi
3. Feb 2009 22:10
Forum: Effiziente Graphenalgorithmen
Thema: Fragen zu Kapitel 4
Antworten: 14
Zugriffe: 692

Re: Fragen zu Kapitel 4

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?
von Andi
3. Feb 2009 12:26
Forum: Effiziente Graphenalgorithmen
Thema: Kanten beim Topsort
Antworten: 4
Zugriffe: 229

Re: Kanten beim Topsort

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?
von Andi
26. Jan 2009 21:06
Forum: Effiziente Graphenalgorithmen
Thema: Übung 9, Aufgabe 4 (Knotenüberdeckung)
Antworten: 5
Zugriffe: 628

Re: Übung 9, Aufgabe 4 (Knotenüberdeckung)

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...
von Andi
26. Jan 2009 17:44
Forum: Effiziente Graphenalgorithmen
Thema: Übung 9, Aufgabe 4 (Knotenüberdeckung)
Antworten: 5
Zugriffe: 628

Re: Übung 9, Aufgabe 4 (Knotenüberdeckung)

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...
von Andi
24. Nov 2008 20:54
Forum: Effiziente Graphenalgorithmen
Thema: Arbeitsaufwand der Übungen
Antworten: 5
Zugriffe: 401

Re: Arbeitsaufwand der Übungen

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...
von Andi
13. Jan 2008 17:25
Forum: Archiv
Thema: Klausurergebnisse hängen aus
Antworten: 7
Zugriffe: 982

Re: Klausurergebnisse hängen aus

Mi., 16.01.2008, 15.00h – 16.00h, Raum A313 wurde in der Übung am Donnerstag bekanntgegeben
von Andi
20. Dez 2007 06:51
Forum: Archiv
Thema: Klausur
Antworten: 3
Zugriffe: 1217

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.
von Andi
7. Dez 2007 11:40
Forum: Archiv
Thema: Bonus theoretische Übungsaufgaben
Antworten: 3
Zugriffe: 1133

Bonus theoretische Übungsaufgaben

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.
von Andi
27. Nov 2007 20:50
Forum: Archiv
Thema: brauche dringend Hilfe
Antworten: 4
Zugriffe: 881

Kann auch folgendes kleines rmi Tutorial empfehlen, hat mir zumindest sehr geholfen http://www.mm.informatik.tu-darmstadt.d ... orial.html
von Andi
13. Nov 2007 20:19
Forum: Archiv
Thema: FIFO vs. Causal Multicast
Antworten: 12
Zugriffe: 1518

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...
von Andi
11. Nov 2007 16:13
Forum: Archiv
Thema: FIFO vs. Causal Multicast
Antworten: 12
Zugriffe: 1518

FIFO vs. Causal Multicast

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 :)
von Andi
29. Okt 2007 11:17
Forum: Archiv
Thema: Aufgabe 2.1
Antworten: 3
Zugriffe: 836

Aufgabe 2.1

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?

Zur erweiterten Suche