Danke für die super Videos zu NP-Härte beweisen!! Könntest du die Tage noch den Beweis, dass das Rucksack Problem NP-vollständig ist hochladen? Schreibe in etwa einer Woche die Klausur und wäre dir mega dankbar!
Mannomann, da kommen ja jetzt einige Videos in so kurzer Zeit. Echt klasse! Danke für deine Arbeit! Ich hoffe es kommen noch ein paar Videos :) Hättest du evtl. noch ein paar allgemeine Tips für eine handelsübliche Klausur? Da ich bei der Klausur schonmal durchgefallen bin, wäre ich für jeden Tip dankbar.
Hm, ich habe noch die Reduktion von Clique auf Indenpendent Set im Kopf...da sagen wir ja, dass wir den Komplementärgraphen bilden, also die Kanten invertieren. Wenn ich mir nun vorstelle, dass wir von Clique zu Ind. Set reduzieren und die Parameter n=3 Knoten und k=3 sind (3-Clique in einem Graph mit 3 Knoten) ... dann werden ja die Kanten zwischen den Knoten alle entfernt... Dementsprechend wäre das Independent Set dann 3 Knoten OHNE Kanten... ist das ein Spezialfall? Weil wenn ich nun k' = #Knoten - k mache .... wäre ja dann 3-3 = 0. 0 Knotenüberdeckungen, sinnvoll, da keine Kanten vorhanden, aber die Reduktion von Indenpendent Set zu Knotenüberdeckung wäre ja dann nicht mehr gegeben, da wir ja dann die Ja-Instanz von Ind. Set auf eine Nein-Instanz bei Knotenüberdeckung abbilden? Anderes Beispiel wäre: Ein Graph ohne Kanten, es ist also egal wie viele der vorhandenen Knoten ich markiere, es ist immer ein Independent Set (Da keine Kanten zwischen den Knoten) ... wenn ich nun n=5 habe und k=3 dann würde ich erwarten das ich nun eine k' = 5 - 3 = 2 Knotenüberdeckung erhalten kann... Geht aber nicht, da garkeine Kanten vorhanden sind. Oder muss das Independent Set maximal sein? (Wofür dann der Parameter k?) Wo ist mein Denkfehler?
Flo S Ein Graph ohne Kanten und k=0 ist eine Ja-Instanz für Vertex Cover. Man wählt also keine Knoten aus, aber damit hat man alle Kanten abgedeckt, denn es gibt ja keine Kanten. Auch im zweiten Beispiel ist das ok: Man wählt von den 5 Knoten irgendwelche 2 aus, damit hat man ein Vertex Cover. Denn wenn es gar keine Kanten gibt, sind immer alle Kanten abgedeckt.
Sehr gut erklärt. Viel viel viel.... besser als der Prof an der technischen Hochschule. Daumen hoch und weiter so!
In einigen Wochen stehen die Klausuren an. Für theoretische Informatik kann ich super deine Videos zur Wiederholung nutzen, Danke!
Welche Uni?
Danke für die super Videos zu NP-Härte beweisen!! Könntest du die Tage noch den Beweis, dass das Rucksack Problem NP-vollständig ist hochladen? Schreibe in etwa einer Woche die Klausur und wäre dir mega dankbar!
Sadorah Tut mir Leid, das Video zum Rucksackproblem schaffe ich bis nächste Woche nicht, wird noch ein bisschen dauern.
Super Video wie immer!
Mannomann, da kommen ja jetzt einige Videos in so kurzer Zeit. Echt klasse! Danke für deine Arbeit!
Ich hoffe es kommen noch ein paar Videos :)
Hättest du evtl. noch ein paar allgemeine Tips für eine handelsübliche Klausur? Da ich bei der Klausur schonmal durchgefallen bin, wäre ich für jeden Tip dankbar.
Ich hoffe es kommen bald mehr.. 🙊 nächste Woche ist es soweit.
Genial
Hm, ich habe noch die Reduktion von Clique auf Indenpendent Set im Kopf...da sagen wir ja, dass wir den Komplementärgraphen bilden, also die Kanten invertieren. Wenn ich mir nun vorstelle, dass wir von Clique zu Ind. Set reduzieren und die Parameter n=3 Knoten und k=3 sind (3-Clique in einem Graph mit 3 Knoten) ... dann werden ja die Kanten zwischen den Knoten alle entfernt... Dementsprechend wäre das Independent Set dann 3 Knoten OHNE Kanten... ist das ein Spezialfall? Weil wenn ich nun k' = #Knoten - k mache .... wäre ja dann 3-3 = 0. 0 Knotenüberdeckungen, sinnvoll, da keine Kanten vorhanden, aber die Reduktion von Indenpendent Set zu Knotenüberdeckung wäre ja dann nicht mehr gegeben, da wir ja dann die Ja-Instanz von Ind. Set auf eine Nein-Instanz bei Knotenüberdeckung abbilden?
Anderes Beispiel wäre: Ein Graph ohne Kanten, es ist also egal wie viele der vorhandenen Knoten ich markiere, es ist immer ein Independent Set (Da keine Kanten zwischen den Knoten) ... wenn ich nun n=5 habe und k=3 dann würde ich erwarten das ich nun eine k' = 5 - 3 = 2 Knotenüberdeckung erhalten kann... Geht aber nicht, da garkeine Kanten vorhanden sind. Oder muss das Independent Set maximal sein? (Wofür dann der Parameter k?)
Wo ist mein Denkfehler?
Flo S Ein Graph ohne Kanten und k=0 ist eine Ja-Instanz für Vertex Cover. Man wählt also keine Knoten aus, aber damit hat man alle Kanten abgedeckt, denn es gibt ja keine Kanten. Auch im zweiten Beispiel ist das ok: Man wählt von den 5 Knoten irgendwelche 2 aus, damit hat man ein Vertex Cover. Denn wenn es gar keine Kanten gibt, sind immer alle Kanten abgedeckt.
Ah, okay, ich verstehe. Vielen Dank für die Antwort!