Ich wette die Quote der bestandenen Prüfungen in der theoretischen Informatik hat enorm zugelegt seitdem es deine Videos gibt :D die Videos haben mir bisher schon extrem viel geholfen für diese doch sehr komplexen Themen zu verstehen
deine videos sind einfach vieeeeel zu krass. grad am theoretische Informatik lernen und jedes deiner Videos hilft mir weiter. gute erklärungen und gute qualität was Skizzen und Ton angeht gibt es nicht oft :)
Warum denn auch? Es gibt sehr wenige Leute, die sich mit diesen Themen beschäftigen, die meisten Unis haben (wenn überhaupt) Komplexitätstheorie erst im Master, soweit ich weiß und als Hobby ist das sicher auch nicht sehr beliebt...
@@JFkingW so ziemlich jeder meiner Freunde der iwas mit info studiert, hat das im Grundstudium (fh und uni), mich eingeschlossen. Ich hörs grad zur Wiederholung weil ich es nochmal im Master hab.
Mir fällt gerade auf, bei der Reduktion von NEAs zum GAP-Problem wurde ein Schritt vergessen. Zumindest wenn nicht NEAs bei mir anders definiert sind. So weit ich weis können NEAs mehrere Startzustände haben (der Beweis war also für DEAs). Die Reduktion für NEAs lässt sich allerdings leicht korrigieren indem man wie beim Endknoten einen Startknoten hinzufügt, der einen Übergang zu allen Startknoten des NEAs hat. Ich finde die Videos super. Ich habe gestern meine Theo 2 Prüfung geschrieben und finde das Thema jetzt so interessant, dass ich umbedingt mehr erfahren will und ich finde es gibt kein besserer Ort als hier. Dank deinem Kanal habe ich erst so richtig Reduktionen verstanden!
Ja, auch ich wollte Dich mal echt loben. Mit dem Skript hätte ich es keineswegs soweit schaffen können, die ganzen Zusammenhänge zu verstehen und die eigentlich interessanten Aussagen überhaupt treffen zu können. Wirklich sehr hilfreich Deine Videos. Ab den Untentscheidbarkeits-Problemen habe ich im Skript eigentlich gar nichts mehr verstanden.^^ Danke Dir für reines Verständnis rüber zu bringen.^^ Solltest vielleicht mal an einer Uni als Prof. arbeiten und intelligente Informatiker kommender Generationen zu schaffen.^^ 😉😉😉😉👍👍👍👍👍
Obwohl mündlich angedeutet: Man hätte bei der formalen Definition der Reduktion nochmal hinschreiben können, dass die Reduktionsfunktion auch *total* sein muss, nicht nur berechenbar. Aber Kleinigkeit. Hervorragendes Video!
Stimmt, das hätte man hinschreiben können. Allerdings ist es nicht wirklich notwendig, denn wenn man von einer Funktion f : A -> B spricht, dann meint man normalerweise immer, dass A der Definitionsbereich ist, d.h. jede Funktion ist "total" auf ihrem Definitionsbereich. In der theoretischen Informatik kommen auch öfter mal "partielle" Funktionen vor. Wenn man explizit sagt, dass f : A -> B eine partielle Funktion ist, dann meint man damit, dass der Definitionsbereich von f eine Teilmenge von A ist. Aber wenn man nicht dazu schreibt, ob die Funktion total oder partiell ist, dann meint man normalerweise total.
Super Videos... ich habe als Nicht-informatiker das erste Mal intuitiv verstanden, was NP versus P bedeutet ;-) Danke !!! Darf ich bitte fragen, mit welchem Zeichentool diese Videos erstellt werden (ohne Werbung zu machen)?
Also nochmal ums wirklich verstanden zu haben: Seien zwei A,B zwei Probleme. Es ist ein Lösungsansatz für B vorhanden, sei dieser mal die Funktion f(w). Wir können A jetzt auf B reduzieren wenn: 1. Wir transformieren den input von A so, dass dieser in f(w), d.h. der Lösung von B eingegeben kann und wir die gewünschten Resultate kriegen. 1A: Geschiet die Transformation in 1 in polynomialer Zeit, dann sprechen wir von einer Polynomialen Reduktion, stimmts? Hab ich das Korrekt verstanden?
Fast korrekt, du nutzt nur die Notationen falsch. Mit f bezeichnen wir die Reduktion, nicht den Algorithmus für B. Und f(w) ist keine Funktion, sondern das ist einfach ein Wort, nämlich die Ausgabe der Reduktionsfunktion f bei Eingabe w.
Müsste in der Definition bei 15:30 nicht auch stehen, dass: w !€ L1 f(w) !€ L2 ? Denn sonst wäre eine Funktion ja auch erlaubt, die aus jedem wort egal ob in L1 oder nicht L1 ein Wort macht, dass in L2 liegt
Die Bedingung, die Du nennst, stimmt, aber sie ist auch schon in der Definition im Video enthalten. Dort steht ja w ∈ L1 f(w) ∈ L2, also eine Implikation in beide Richtungen. Insbesondere die Implikation von rechts nach links, also wenn f(w) ∈ L2, dann muss w ∈ L1 sein. Man darf also nicht ein Wort w, das nicht in L1 liegt, auf ein Wort f(w) ∈ L2 abbilden.
Ich habe absolut keine Ahnung von Informatik. Ich schaue mir das an, weil ich von dieser Reduktion oft im Zusammenhang mit dem P vs NP Problem gehört habe und wollte es verstehen. Meine Frage ist: sollte ich als Laie dazu in der Lage sein, das alles zu verstehen, oder braucht man gewisse Grundlagen dafür?
Ich setze in meinen Videos nicht viele Vorkenntnisse voraus. Wenn Du die Serie von Anfang an ansiehst, dann sollte es auch völlig ohne Vorkenntnisse möglich sein, die Ideen und Intuitionen hinter P und NP zu verstehen.
Klasse Video. Dies war jetzt erst einmal zur Einleitung, um das Konzept einer Reduktion vorzustellen oder? Denn wenn eine Aufgabe dran kommen würde, müsste man das anders/ genauer aufschreiben oder?
Marc Stimmt, wenn man NEAs mit mehreren Startzuständen definiert, dann müsste man das so machen. Ich hatte vergessen zu sagen, dass meine NEAs immer nur einen Startzustand haben, dann muss man da keine Extraknoten für einführen.
@@NLogSpace Wow, deine Antwortgeschwindigkeit ist echt beeindruckend. Dankeschön. Die nächste frage kommt bestimmt, wenn ich bei NP-Vollständigkeit angekommen bin ^^
Hast du dir schon überlegt deine Videos auf Englisch zu machen? Würdest so viel mehr Studenten helfen können. Und deine deutschsprachigen Zuschauer können wahrscheinlich eh schon alle Englisch :D
Ja, ich will in Zukunft auch Videos auf englisch machen, aber hatte bisher nicht so die Motivation, weil es erst wieder sehr lange dauert, bis der Kanal dann Zuschauer findet.
Ich wette die Quote der bestandenen Prüfungen in der theoretischen Informatik hat enorm zugelegt seitdem es deine Videos gibt :D die Videos haben mir bisher schon extrem viel geholfen für diese doch sehr komplexen Themen zu verstehen
deine videos sind einfach vieeeeel zu krass. grad am theoretische Informatik lernen und jedes deiner Videos hilft mir weiter. gute erklärungen und gute qualität was Skizzen und Ton angeht gibt es nicht oft :)
Eigenartig, dass bisher nicht mehr Leute diese Videos geschaut und als grandios befunden haben. Klasse erklärt !
Warum denn auch? Es gibt sehr wenige Leute, die sich mit diesen Themen beschäftigen, die meisten Unis haben (wenn überhaupt) Komplexitätstheorie erst im Master, soweit ich weiß und als Hobby ist das sicher auch nicht sehr beliebt...
@@JFkingW so ziemlich jeder meiner Freunde der iwas mit info studiert, hat das im Grundstudium (fh und uni), mich eingeschlossen. Ich hörs grad zur Wiederholung weil ich es nochmal im Master hab.
Lel hab das im 2. Semester
War was Reduktion angeht krass verwirrt -> Habe dein Anfangsbeispiel angeschaut -> Mich wieder meiner Aufgabe gewidmet -> Durchbruch. Danke!!
Mir fällt gerade auf, bei der Reduktion von NEAs zum GAP-Problem wurde ein Schritt vergessen. Zumindest wenn nicht NEAs bei mir anders definiert sind. So weit ich weis können NEAs mehrere Startzustände haben (der Beweis war also für DEAs). Die Reduktion für NEAs lässt sich allerdings leicht korrigieren indem man wie beim Endknoten einen Startknoten hinzufügt, der einen Übergang zu allen Startknoten des NEAs hat.
Ich finde die Videos super. Ich habe gestern meine Theo 2 Prüfung geschrieben und finde das Thema jetzt so interessant, dass ich umbedingt mehr erfahren will und ich finde es gibt kein besserer Ort als hier.
Dank deinem Kanal habe ich erst so richtig Reduktionen verstanden!
Ich nutze eine Definition von NEA mit nur einem Startzustand. Ansonsten könnte man es genau so machen, wie Du sagst!
Super! Mein Prof machts auch nicht schlecht, aber das ist nochmals einfach und verständlicher! Echt gut aufs wesentliche "reduziert"
Unglaublich gut erklärt! Um einiges besser als mein Prof...
Ja, auch ich wollte Dich mal echt loben. Mit dem Skript hätte ich es keineswegs soweit schaffen können, die ganzen Zusammenhänge zu verstehen und die eigentlich interessanten Aussagen überhaupt treffen zu können. Wirklich sehr hilfreich Deine Videos. Ab den Untentscheidbarkeits-Problemen habe ich im Skript eigentlich gar nichts mehr verstanden.^^ Danke Dir für reines Verständnis rüber zu bringen.^^ Solltest vielleicht mal an einer Uni als Prof. arbeiten und intelligente Informatiker kommender Generationen zu schaffen.^^ 😉😉😉😉👍👍👍👍👍
Mit w und wbb einfach klasse!!! Endlich verstanden, Danke sehr!
Super Erklärung. Vielen Dank!
Obwohl mündlich angedeutet: Man hätte bei der formalen Definition der Reduktion nochmal hinschreiben können, dass die Reduktionsfunktion auch *total* sein muss, nicht nur berechenbar. Aber Kleinigkeit. Hervorragendes Video!
Stimmt, das hätte man hinschreiben können. Allerdings ist es nicht wirklich notwendig, denn wenn man von einer Funktion f : A -> B spricht, dann meint man normalerweise immer, dass A der Definitionsbereich ist, d.h. jede Funktion ist "total" auf ihrem Definitionsbereich. In der theoretischen Informatik kommen auch öfter mal "partielle" Funktionen vor. Wenn man explizit sagt, dass f : A -> B eine partielle Funktion ist, dann meint man damit, dass der Definitionsbereich von f eine Teilmenge von A ist. Aber wenn man nicht dazu schreibt, ob die Funktion total oder partiell ist, dann meint man normalerweise total.
omg deine Videos sind einfach mega
Sehr gute Videos bis jetzt. Gib mir mehr davon :D
gut erklärt, danke dir
Super Videos... ich habe als Nicht-informatiker das erste Mal intuitiv verstanden, was NP versus P bedeutet ;-) Danke !!!
Darf ich bitte fragen, mit welchem Zeichentool diese Videos erstellt werden (ohne Werbung zu machen)?
Das freut mich! :)
Das Tool heißt Xournal, ich nutze es unter Linux.
Also nochmal ums wirklich verstanden zu haben:
Seien zwei A,B zwei Probleme. Es ist ein Lösungsansatz für B vorhanden, sei dieser mal die Funktion f(w).
Wir können A jetzt auf B reduzieren wenn:
1. Wir transformieren den input von A so, dass dieser in f(w), d.h. der Lösung von B eingegeben kann und wir die gewünschten Resultate kriegen.
1A: Geschiet die Transformation in 1 in polynomialer Zeit, dann sprechen wir von einer Polynomialen Reduktion, stimmts?
Hab ich das Korrekt verstanden?
Fast korrekt, du nutzt nur die Notationen falsch. Mit f bezeichnen wir die Reduktion, nicht den Algorithmus für B. Und f(w) ist keine Funktion, sondern das ist einfach ein Wort, nämlich die Ausgabe der Reduktionsfunktion f bei Eingabe w.
@@NLogSpace Gut, da habe ich mich jetzt nicht an die notationen im Video gehalten.
Danke dir!
Müsste in der Definition bei 15:30 nicht auch stehen, dass:
w !€ L1 f(w) !€ L2
?
Denn sonst wäre eine Funktion ja auch erlaubt, die aus jedem wort egal ob in L1 oder nicht L1 ein Wort macht, dass in L2 liegt
Die Bedingung, die Du nennst, stimmt, aber sie ist auch schon in der Definition im Video enthalten. Dort steht ja w ∈ L1 f(w) ∈ L2, also eine Implikation in beide Richtungen. Insbesondere die Implikation von rechts nach links, also wenn f(w) ∈ L2, dann muss w ∈ L1 sein. Man darf also nicht ein Wort w, das nicht in L1 liegt, auf ein Wort f(w) ∈ L2 abbilden.
8:07 ist richtig gut, die vorherigen hab ich nicht so ganz verstanden
Bester Mann!
Ich habe absolut keine Ahnung von Informatik. Ich schaue mir das an, weil ich von dieser Reduktion oft im Zusammenhang mit dem P vs NP Problem gehört habe und wollte es verstehen. Meine Frage ist: sollte ich als Laie dazu in der Lage sein, das alles zu verstehen, oder braucht man gewisse Grundlagen dafür?
Ich setze in meinen Videos nicht viele Vorkenntnisse voraus. Wenn Du die Serie von Anfang an ansiehst, dann sollte es auch völlig ohne Vorkenntnisse möglich sein, die Ideen und Intuitionen hinter P und NP zu verstehen.
Klasse Video. Dies war jetzt erst einmal zur Einleitung, um das Konzept einer Reduktion vorzustellen oder? Denn wenn eine Aufgabe dran kommen würde, müsste man das anders/ genauer aufschreiben oder?
Kleine Frage:
Angenommen A
Meinst Du A
@@NLogSpace sorry natürlich
@@moritzschmidt8528 Nein, die Aussage gilt nicht, aber umgekehrt stimmt das: Wenn A
Ich hab zu Danken :)
Ich würde denken, dass man natürlich auch den Extraknoten s' für alle Startzustände hinzufügen müsste, weil es davon ja auch mehrere geben könnte. :)
Marc Stimmt, wenn man NEAs mit mehreren Startzuständen definiert, dann müsste man das so machen. Ich hatte vergessen zu sagen, dass meine NEAs immer nur einen Startzustand haben, dann muss man da keine Extraknoten für einführen.
Also verstehe ich es richtig, dass wenn ich beweisen möchte, dass mein Problem A nicht schwerer als ein Problem B ist (A
Genau, die Reduktion muss jede Eingabe von A in einer Eingabe von B umwandeln.
@@NLogSpace Wow, deine Antwortgeschwindigkeit ist echt beeindruckend. Dankeschön.
Die nächste frage kommt bestimmt, wenn ich bei NP-Vollständigkeit angekommen bin ^^
Scheiß die Wand an, bist du gut im Erklären Leif.
legende
Super
Hast du dir schon überlegt deine Videos auf Englisch zu machen? Würdest so viel mehr Studenten helfen können. Und deine deutschsprachigen Zuschauer können wahrscheinlich eh schon alle Englisch :D
Ja, ich will in Zukunft auch Videos auf englisch machen, aber hatte bisher nicht so die Motivation, weil es erst wieder sehr lange dauert, bis der Kanal dann Zuschauer findet.