Wow, ich hätte niemals gedacht noch einen deutschen Kanal zu diesen Themenbereichen zu finden. Bitte mach weiter, ich hoffe du weißt wie sehr du Studenten damit weiterhilfst. Hier nochmal ein sehr großer Dank an dich und deine Arbeit, Hut ab. Sobald ich die Klausur fertig habe, lasse ich definitiv eine Spende da, unabhängig davon wie meine Klausur verlief ;)
Moin nlogspace, wollte dir mal herzlichst danke sagen. Durch deine Videoreihe über Formale Sprachen, Berechenbarkeit und Komplexität habe ich meine Klausur mit 2,0 bestanden. Ich und weitere Kommilitonen danken dir. DANKE für deine Videos und mach weiter so.
Du rettest mir gerade meine KlausurenLernPhase für Algorithmen und Datenstrukturen XD DANKE DANKE DANKE!!!!! Da starrt man Ewigkeiten auf das Skript und hört sich die Vorlesung wieder und wieder an, dabei geht es so einfach....wenn man sich in einem Bruchteil der Zeit deine Videos ansieht.
OMG!! Ich habe gerade gesehen, dass du viiiiiiieeeeele neue Videos hochgeladen hast!! Ich hatte letztes Jahr mal bei dir angefragt (anderer Account)! Vielen Dank für die Mühe die du dir machst! Ich "freue" mich jetzt schon darauf durch dich die ganze Schose zu verstehen! Gerade Reduktion ist mir ein Dorn im Auge! Dann noch die Entscheidbarkeit und sogar Klausuraufgaben!! Es ist mein Drittversuch und ich bin mega nervös, aber ich hoffe mit deinen Videos zu diesen komplexen und schwierigen Themen werde ich es schaffen! Nochmal Danke für deine Mühe, ab heute werde ich die Videos nochmal neu durchgehen! Ich hoffe du bringst noch mehr raus, denn am 13.08. ist meine Klausur. Ich will aber keinen Druck ausüben und ich weiß, dass diese Art von Videos wenig Traffic bekommt.. leider! Umso geiler, dass du soooviele Videos neu herausgebracht hast! Sei versichert, dass wenigstens einer die verschlingen wird :)
Hallo Leifaktor! Suuuuupppppeeeerrrr Job den du da machst! Ich hoffe sehr das du die Serie weiter fortführst, dass hat mir unheimlich viel geholfen das Thema überhaupt zu verstehen und ich bin mir ganz sicher, dass es nicht nur mir so geht. Zu einem gibt es nahe zu nichts darüber auf UA-cam. Die Aufrufe werden sich von Semester zu Semester stetig steigen. Daumen hoch!!
@@JFkingW nein natürlich nicht, haha, du hast mich nicht verstanden. Clique soll abstrakt den Stoff von der Klausur darstellen. Man lernt genau den Stoff und dann frägt der Dozent genau das ab, was man nicht gelernt hat. Also IS. Verstanden ? :D
Sehr schönes Video und schöne Reihe, vielen Dank! Ich möchte nur anmerken, man hätte noch die direkte Reduktion von SAT auf CLIQUE darstellen können, weil es sich an der Stelle wirklich anbietet. Im Endeffekt nimmt man einfach den komplementären Graphen vom Independent Set und sucht dann eine maximale Clique (Größe: Anzahl der Variablen). Da die einzelnen Variablen innerhalb einer Klausel nicht miteinander verbunden wären, müsste eine maximale Clique alle Klauseln "abgrasen". Und da im komplementären Graphen z.B. x und -x nicht miteinander verbunden wären, würde eine maximale Clique alle Variablen beinhalten müssen. Die umgekehrte Reduktion (Clique zu SAT) ist schon ziemlich unangenehm, weil sehr viel konstruiert werden muss. Keine leichte Übungsaufgabe.
ich finds so schade, dass in den uni-Vorlesungen nie was über die Geschichte hinter diesen "Entdeckungen" erzählt wird, weil ich voll neugierig wäre, wie derjenige darauf kam!
Hätte man dann den Graphen bei der Reduktion von 3SAT auf Clique so aufgebaut, dass die Kanten der Knoten zu allen Knoten gehen mit denen kein Konflikt herscht(also z.b. x -> y) und man dann auch genau die wählt wo eine Verbindung besteht im Gegensatz zu Independent Set wo man die genommen hat, wo keine Verbindung existiert? Und bei denen innerhalb einer Klausel hätte man dann einfach keine Verbindung gezogen oder, damit immer noch jeweils ein Term pro Klausel erfüllt ist, oder?
Genau, bei der Reduktion auf Clique würde man das Komplement des Graphen nehmen. Also die Knotenmenge ist die gleiche, aber man zeichnet genau die Kanten ein, die es bei der Reduktion auf Independent Set nicht gibt.
Hallo, kann man das Independent set oder das Clique Problem auf das K-Stern Problem reduzieren? Also zeigen, dass das K-Stern Problem NP vollständig ist. Gesucht ist dabei ein Sterngraph mit K Spitzen, sodass die Spitzen des Sterns untereinander nicht verbunden sind.
Die Spitzen des Sterns bilden also eine Independent Set, das ist schonmal ein guter Zusammenhang. Wenn wir nun von Independent Set auf K-Stern reduzieren wollen, dann müssen wir quasi nur noch das Zentrum des Sterns künstlich hinzufügen. D.h. die Reduktion sieht so aus: Gegeben die Eingabe für Independent Set, also ein Graph G und eine Zahl k. Wir fügen einen neuen Knoten v zu G hinzu und verbinden v mit jedem Knoten aus G durch eine Kante. Dieser neue Graph heißt dann G'. Die Ausgabe der Reduktion ist der Graph G' und die gleiche Zahl k. Wenn es nun in G eine Independent Set der Größe k gibt, dann gibt es in G' einen Stern mit k Spitzen, nämlich die Knoten der Independent Set als Spitzen und v als Zentrum. Umgekehrt: Wenn es in G' einen Stern mit k Spitzen gibt, dann ist keine dieser Spitzen v sein, denn v ist ja mit allen Knoten verbunden. Die k Spitzen existieren also auch alle in G und bilden dort eine Independent Set der Größe k.
Hallo, vielen Dank für die tolle Videos, sie lösen echt langsam ein großes Problem, das ich mit theoretischer Informatik seit ein Paar Semester habe. keep up the good work! Ich hätte aber eine Frage zu diesem Video und zwar müssen nicht bei einer Reduktion alle Belegungen, die 3-SAT erfüllen auch independent set erfüllen? Wenn ja, dann ist 3-SAT z.B. mit dieser Belegung (w, x, y, z) = (0, 0, 0, 1) hier erfüllt aber independent set aufgrund der zusätzlichen Kanten innerhalb der Klauseln nicht, da (¬y ∨ z ∨¬w ) = (1 ∨ 1 ∨ 1) ∉ ind.set Oder habe ich etwas verpasst?
Bei der Reduktion von 3-SAT auf INDSET übersetzen wir eine aussagenlogische Formel in einen Graphen und eine Zahl. Ich nehme an, du beziehst dich auf die Formel, die ich im Video benutzt habe? Dort ist die von Dir genannte Belegung eine erfüllende Belegung. Und man findet in dem Graphen auch eine entsprechende independent set der Größe 5, man kann nämlich aus jeder Dreiergruppe von Knoten einen auswählen (in jeder Dreiergruppe kommt entweder ¬w oder ¬x oder ¬y oder z vor).
Wie sollte die o.g. Belegung bei INDSET funktionieren, wenn wir im Graph genau pro Klauselmenge nur ein einziges Literal mit dem Wert 1 erlauben? hier bin ich leider immer noch verwirrt
Ghaiss Shami Ich verstehe immer noch nicht, worauf sich deine Frage bezieht. Die Reduktion übersetzt jede aussagenlogische Formel (in 3KNF) in einen Graphen G und eine Zahl k. Wenn die Formel erfüllbar ist, dann hat der resultierende Graph G eine Independent Set der Größe k und wenn die Formel unerfüllbar ist, dann hat der Graph G keine independent set der Größe k. Du hast die Belegung (w,x,y,z)=(0,0,0,1) erwähnt, aber über welche Formel sprichst Du? Die aus dem Video? Dann würde der Graph genau so aussehen wie im Video (denn der Graph hängt nur von der Formel ab, nicht von der Belegung) und wir finden dort auch eine Independent set der Größe 5, die aus der von dir genannten Belegung hervorgeht. Oder sprichst Du über eine andere Formel?
Ja die Formel vom Video, aber mit 0001 statt 1100 (was Du im Video erwähnt hast) für wxyz. Was ich leider nicht so ganz verstehe ist, dass beim Graph irgendwie jetzt die ganzen "oder" Beziehungen zwischen den Lateralen zu "XOR" geworden sind. Ich habe was ich meine hier besser gezeichnet: awwapp.com/b/uw82szwqu/
Ghaiss Shami Das was du als XOR innerhalb einer Dreiergruppe bezeichnest ist kein Problem. Der Graph ist ja keine Formel mehr und es geht nicht mehr um Erfüllbarkeit. Im Graphen interessiert uns nur, ob es eine independent set der Größe 5 gibt, und die gibt es: Du hast in deiner Zeichnung alle Knoten, die in Frage kommen, blau markiert und man sieht, dass in jeder Dreiergruppe mindestens ein Knoten blau markiert ist. Die Kanten innerhalb einer Dreiergruppe zwingen uns dazu, aus jeder Dreiergruppe genau einen Knoten auswählen. Natürlich kann es mehrere Möglichkeiten innerhalb einer Dreiergruppe geben (z.B. bei ¬y ∨ z ∨¬w sind alle drei Knoten möglich), aber die independent set soll nicht mehrere aus der selben Dreiergruppe auswählen dürfen. Denn die Größe haben wir festgelegt auf 5 (Anzahl der Klauseln). Wenn es eine independent set der Größe 5 gibt, dann müssen diese 5 Knoten aus den 5 verschiedenen Dreiergruppen kommen und das heißt, dass in jeder Klausel mindestens ein Literal vorhanden ist, das die Formel erfüllt.
Wow, ich hätte niemals gedacht noch einen deutschen Kanal zu diesen Themenbereichen zu finden.
Bitte mach weiter, ich hoffe du weißt wie sehr du Studenten damit weiterhilfst.
Hier nochmal ein sehr großer Dank an dich und deine Arbeit, Hut ab.
Sobald ich die Klausur fertig habe, lasse ich definitiv eine Spende da, unabhängig davon wie meine Klausur verlief ;)
Moin nlogspace, wollte dir mal herzlichst danke sagen. Durch deine Videoreihe über Formale Sprachen, Berechenbarkeit und Komplexität habe ich meine Klausur mit 2,0 bestanden. Ich und weitere Kommilitonen danken dir. DANKE für deine Videos und mach weiter so.
Du rettest mir gerade meine KlausurenLernPhase für Algorithmen und Datenstrukturen XD DANKE DANKE DANKE!!!!! Da starrt man Ewigkeiten auf das Skript und hört sich die Vorlesung wieder und wieder an, dabei geht es so einfach....wenn man sich in einem Bruchteil der Zeit deine Videos ansieht.
Danke, freut mich das zu lesen!
OMG!! Ich habe gerade gesehen, dass du viiiiiiieeeeele neue Videos hochgeladen hast!! Ich hatte letztes Jahr mal bei dir angefragt (anderer Account)! Vielen Dank für die Mühe die du dir machst! Ich "freue" mich jetzt schon darauf durch dich die ganze Schose zu verstehen! Gerade Reduktion ist mir ein Dorn im Auge! Dann noch die Entscheidbarkeit und sogar Klausuraufgaben!! Es ist mein Drittversuch und ich bin mega nervös, aber ich hoffe mit deinen Videos zu diesen komplexen und schwierigen Themen werde ich es schaffen!
Nochmal Danke für deine Mühe, ab heute werde ich die Videos nochmal neu durchgehen! Ich hoffe du bringst noch mehr raus, denn am 13.08. ist meine Klausur. Ich will aber keinen Druck ausüben und ich weiß, dass diese Art von Videos wenig Traffic bekommt.. leider! Umso geiler, dass du soooviele Videos neu herausgebracht hast! Sei versichert, dass wenigstens einer die verschlingen wird :)
haste den drittversuch bestanden?
Iwould kujeti know that as well@@lukagoalvic4084
Hallo Leifaktor! Suuuuupppppeeeerrrr Job den du da machst! Ich hoffe sehr das du die Serie weiter fortführst, dass hat mir unheimlich viel geholfen das Thema überhaupt zu verstehen und ich bin mir ganz sicher, dass es nicht nur mir so geht. Zu einem gibt es nahe zu nichts darüber auf UA-cam. Die Aufrufe werden sich von Semester zu Semester stetig steigen. Daumen hoch!!
Dozent: Clique kommt dran
Klausur: IS wird abgefragt
..
es bezieht sich alles auf den Inhalt :D
Lol euer Prof sagt welche Probleme dran kommen?
@@JFkingW nein natürlich nicht, haha, du hast mich nicht verstanden.
Clique soll abstrakt den Stoff von der Klausur darstellen. Man lernt genau den Stoff und dann frägt der Dozent genau das ab, was man nicht gelernt hat. Also IS. Verstanden ? :D
Sehr schönes Video und schöne Reihe, vielen Dank!
Ich möchte nur anmerken, man hätte noch die direkte Reduktion von SAT auf CLIQUE darstellen können, weil es sich an der Stelle wirklich anbietet. Im Endeffekt nimmt man einfach den komplementären Graphen vom Independent Set und sucht dann eine maximale Clique (Größe: Anzahl der Variablen). Da die einzelnen Variablen innerhalb einer Klausel nicht miteinander verbunden wären, müsste eine maximale Clique alle Klauseln "abgrasen". Und da im komplementären Graphen z.B. x und -x nicht miteinander verbunden wären, würde eine maximale Clique alle Variablen beinhalten müssen.
Die umgekehrte Reduktion (Clique zu SAT) ist schon ziemlich unangenehm, weil sehr viel konstruiert werden muss. Keine leichte Übungsaufgabe.
Exakt diese Reduktion kam letztes Jahr in der Klausur dran und ich hab dank dir volle Punktzahl auf die Aufgabe bekommen :D
Welche genau die von SAT auf CLIQUE?
ich finds so schade, dass in den uni-Vorlesungen nie was über die Geschichte hinter diesen "Entdeckungen" erzählt wird, weil ich voll neugierig wäre, wie derjenige darauf kam!
Hätte man dann den Graphen bei der Reduktion von 3SAT auf Clique so aufgebaut, dass die Kanten der Knoten zu allen Knoten gehen mit denen kein Konflikt herscht(also z.b. x -> y) und man dann auch genau die wählt wo eine Verbindung besteht im Gegensatz zu Independent Set wo man die genommen hat, wo keine Verbindung existiert? Und bei denen innerhalb einer Klausel hätte man dann einfach keine Verbindung gezogen oder, damit immer noch jeweils ein Term pro Klausel erfüllt ist, oder?
Genau, bei der Reduktion auf Clique würde man das Komplement des Graphen nehmen. Also die Knotenmenge ist die gleiche, aber man zeichnet genau die Kanten ein, die es bei der Reduktion auf Independent Set nicht gibt.
Hallo, kann man das Independent set oder das Clique Problem auf das K-Stern Problem reduzieren? Also zeigen, dass das K-Stern Problem NP vollständig ist. Gesucht ist dabei ein Sterngraph mit K Spitzen, sodass die Spitzen des Sterns untereinander nicht verbunden sind.
Die Spitzen des Sterns bilden also eine Independent Set, das ist schonmal ein guter Zusammenhang. Wenn wir nun von Independent Set auf K-Stern reduzieren wollen, dann müssen wir quasi nur noch das Zentrum des Sterns künstlich hinzufügen. D.h. die Reduktion sieht so aus: Gegeben die Eingabe für Independent Set, also ein Graph G und eine Zahl k. Wir fügen einen neuen Knoten v zu G hinzu und verbinden v mit jedem Knoten aus G durch eine Kante. Dieser neue Graph heißt dann G'. Die Ausgabe der Reduktion ist der Graph G' und die gleiche Zahl k. Wenn es nun in G eine Independent Set der Größe k gibt, dann gibt es in G' einen Stern mit k Spitzen, nämlich die Knoten der Independent Set als Spitzen und v als Zentrum. Umgekehrt: Wenn es in G' einen Stern mit k Spitzen gibt, dann ist keine dieser Spitzen v sein, denn v ist ja mit allen Knoten verbunden. Die k Spitzen existieren also auch alle in G und bilden dort eine Independent Set der Größe k.
Es ist wahrhaft faszinierend und elegant. Schade, dass ich es studiere, sonst wäre es echt mein Hobby.
Hallo,
vielen Dank für die tolle Videos, sie lösen echt langsam ein großes Problem, das ich mit theoretischer Informatik seit ein Paar Semester habe. keep up the good work!
Ich hätte aber eine Frage zu diesem Video und zwar müssen nicht bei einer Reduktion alle Belegungen, die 3-SAT erfüllen auch independent set erfüllen?
Wenn ja, dann ist 3-SAT z.B. mit dieser Belegung (w, x, y, z) = (0, 0, 0, 1) hier erfüllt aber independent set aufgrund der zusätzlichen Kanten innerhalb der Klauseln nicht, da (¬y ∨ z ∨¬w ) = (1 ∨ 1 ∨ 1) ∉ ind.set
Oder habe ich etwas verpasst?
Bei der Reduktion von 3-SAT auf INDSET übersetzen wir eine aussagenlogische Formel in einen Graphen und eine Zahl. Ich nehme an, du beziehst dich auf die Formel, die ich im Video benutzt habe? Dort ist die von Dir genannte Belegung eine erfüllende Belegung. Und man findet in dem Graphen auch eine entsprechende independent set der Größe 5, man kann nämlich aus jeder Dreiergruppe von Knoten einen auswählen (in jeder Dreiergruppe kommt entweder ¬w oder ¬x oder ¬y oder z vor).
Wie sollte die o.g. Belegung bei INDSET funktionieren, wenn wir im Graph genau pro Klauselmenge nur ein einziges Literal mit dem Wert 1 erlauben? hier bin ich leider immer noch verwirrt
Ghaiss Shami Ich verstehe immer noch nicht, worauf sich deine Frage bezieht. Die Reduktion übersetzt jede aussagenlogische Formel (in 3KNF) in einen Graphen G und eine Zahl k. Wenn die Formel erfüllbar ist, dann hat der resultierende Graph G eine Independent Set der Größe k und wenn die Formel unerfüllbar ist, dann hat der Graph G keine independent set der Größe k. Du hast die Belegung (w,x,y,z)=(0,0,0,1) erwähnt, aber über welche Formel sprichst Du? Die aus dem Video? Dann würde der Graph genau so aussehen wie im Video (denn der Graph hängt nur von der Formel ab, nicht von der Belegung) und wir finden dort auch eine Independent set der Größe 5, die aus der von dir genannten Belegung hervorgeht. Oder sprichst Du über eine andere Formel?
Ja die Formel vom Video, aber mit 0001 statt 1100 (was Du im Video erwähnt hast) für wxyz.
Was ich leider nicht so ganz verstehe ist, dass beim Graph irgendwie jetzt die ganzen "oder" Beziehungen zwischen den Lateralen zu "XOR" geworden sind.
Ich habe was ich meine hier besser gezeichnet:
awwapp.com/b/uw82szwqu/
Ghaiss Shami Das was du als XOR innerhalb einer Dreiergruppe bezeichnest ist kein Problem. Der Graph ist ja keine Formel mehr und es geht nicht mehr um Erfüllbarkeit. Im Graphen interessiert uns nur, ob es eine independent set der Größe 5 gibt, und die gibt es: Du hast in deiner Zeichnung alle Knoten, die in Frage kommen, blau markiert und man sieht, dass in jeder Dreiergruppe mindestens ein Knoten blau markiert ist. Die Kanten innerhalb einer Dreiergruppe zwingen uns dazu, aus jeder Dreiergruppe genau einen Knoten auswählen. Natürlich kann es mehrere Möglichkeiten innerhalb einer Dreiergruppe geben (z.B. bei ¬y ∨ z ∨¬w sind alle drei Knoten möglich), aber die independent set soll nicht mehrere aus der selben Dreiergruppe auswählen dürfen. Denn die Größe haben wir festgelegt auf 5 (Anzahl der Klauseln). Wenn es eine independent set der Größe 5 gibt, dann müssen diese 5 Knoten aus den 5 verschiedenen Dreiergruppen kommen und das heißt, dass in jeder Klausel mindestens ein Literal vorhanden ist, das die Formel erfüllt.
könntest du auch die Reduktionen mathematisch beweisen? Also mit Methoden wie pol. Verifizierer usw.? Wäre mir sehr hilfreich
Ich brauche Independent Set zu lernen !