Reduktionen: Theoretische Informatik (einfach erklärt!)
Vložit
- čas přidán 28. 07. 2024
- 💠 Mein komplettes Produktivitätssystem: fokus.so
Reduktionen sind ein wichtiges Hilfsmittel in der theoretischen Informatik, besonders für Berechenbarkeit und Komplexität. Sie erlauben es einem, die Schwierigkeit eines neuen Problems einzuordnen, indem man es mit anderen, bekannten Problemen in Bezug bringt.
Ein häufiges Beispiel sind Reduktionen vom berühmten Halteproblem. In diesem Video gehe ich nicht im Detail auf das Halteproblem selbst ein, sondern möchte vor allem eine gute Intuition für das Reduktionsprinzip vermitteln. Um Reduktionen zu verstehen, braucht es kaum Vorkenntnisse.
Ich erkläre Reduktionen zunächst anhand von zwei Programmierbeispielen. Anschließend kommt der wichtigste Teil, wo ich erkläre, wie Reduktionen benutzt werden, um die Schwierigkeit unbekannter Probleme zu beweisen. Am Ende gehe ich auf ein alternatives, stärkeres Reduktionsprinzip ein. Diese stärkeren Reduktionen, die oft als Many-One Reduktionen bezeichnet werden, sind häufig Gegenstand der Theorievorlesung im Informatikstudium.
Da ich in diesem Video nicht erklären wollte, was Turing-Maschinen sind und wie das Halteproblem funktioniert, gebe ich kein Beispiel für eine Reduktion vom Halteproblem. Auf Wunsch können wir das in einem separaten Video besprechen.
In jedem Fall hoffe ich, dass dieses Video häufige Denkfehler aufklärt (als Übungsleiter an der Uni musste habe ich häufig erlebt, dass Studenten in die falsche Richtung reduzieren) und eine gute Vorbereitung/Begleitung für das Material einer typischen theoretischen Informatikklausur bietet.
Um tiefer in die Materie einzudringen, solltest du mehr zu den folgenden Themen lesen:
* Halteproblem
* Turing-Maschine
* Entscheidbarkeit
* P-NP-Problem
📢 Zuschauerumfrage: forms.gle/p8xZt3Ag2LYZGewq9
💌 Newsletter: niklassteenfatt.com/
Timestamps:
0:00 - Intro und Versprechen
0:41 - Einführung
2:38 - Beispiele in Python
6:39 - Schwierigkeit von Problemen
8:11 - Reduktion als Schwierigkeitsbeweis
10:02 - Wichtig: Reduktionsrichtung
12:02 - Reduktion als Widerspruchsbeweis
14:52 - Starke Reduktionen
15:41 - Mini-Übungsaufgabe
16:44 - Versprechen gehalten?
Jetzt deine Ziele erreichen: fokus.so - Věda a technologie
Wer guckt das Video noch in 2023? Ich habe inzwischen übrigens mein komplettes Produktivitätssystem veröffentlicht: fokus.so
Boss, danke dir
@@sillomo524 Hier🙋♂. Danke hat geholfen!
Yessir
Guck mir das jetzt 2024 an
@@KillaFromErzurum same here
Ich finde es spannend (und gleichzeitig traurig), dass ich so häufig Videos und Artikel finde, die Dinge so viel besser erklären als Dozenten. Prof: vier Vorlesungen, drei Übungsaufgaben und die wenigsten haben es wirklich verstanden. Wirklich Fähiger CZcamsr: 17 Minuten 23 Sekunden geballte, simple, griffige, verständliche und korrekte Erklärungen anhand derer es die meisten wahrscheinlich verstanden haben. Wirklich gutes Video!
Vorlesungen und Skripte sind oftmals sehr formal und auf Intuition wird recht wenig eingegangen. Das heißt nicht, dass eine formale Abhandlung schlecht ist, sie sind eher hilfreich, da man detailierter und präziser auf ein Problem/Thema eingeht. Das aber leider nur unter der Voraussetzung, dass man etwas im Prinzip schon verstanden hat.
Man merkt das oft bei Themen, die man erstmals nicht verstanden hat, dann aber zurückblickt (bspw. zur Klausurvorbereitung) und alles viel klarer erscheint. Deswegen find ich sogar beides in Kombination optimal: eine intuitive Einführung und dann nochmal formal drübergehen.
Du musst beachten, dass Erklärvideos manchmal so verständlich erscheinen, da sie falsche Vereinfachungen benutzen. Ein berühmtes Beispiel, das auch Gegenstand physikdidaktischer Forschung war, ist u.a. das Video zu Kräften von "Physik - simpleclub". SimpleClub ist extrem beliebt unter Schülerinnen und Schülern für einfache und verständliche Erklärungen, die ihnen aber nur deshalb so leicht und verständlich vorkommen, da sie häufig an falsche bzw. nicht völlig korrekte Alltagsvorstellungen appellieren.
Das hier gezeigte Video ist super und davon nicht betroffen!
Ich hätte nicht gedacht, dass ich währrend ich Kekse futter und halb konzentriert zuhöre tatsächlich Reduktion verstehe. Die Codebeispiele haben der ganzen Theorie etwas richtig handfestes gegeben. Wenn du noch mehr theoretische Tutorials machst, werde ich sie mir auf jeden Fall alle reinziehen. Dieser Channel ist eine Goldgrube.
Same here mehr davon ganz dringend benötigt
Waren die Erklärungen verständlich? Welches Thema soll ich als Nächstes machen?
vll unterschied zwischen np-vollständig und np-schwer :D ah und Lernvideos zu Approximationsalgorithmus gibt es auch kaum im Internet... wäre cool wenn du die Lücke füllen würdest. Danke!
Machen Sie komplett Playlist für Theoretische Informatik 😍 . Sie können es sehr gut erklären.👍 Dankeschön
Ein Video über die Riemannsche Vermutung wäre hammer! =)
Mir erscheint es immer noch etwas willkürlich das halteproblem auf irgendein anderes Problem zu reduzieren wo ist mein Denkfehler? Den Kommentar mit auf zwei Zahlen Multiplikation reduzieren habe ich zwar gesehen aber noch sehr unklar.
Und konkrete Reduktionsprobleme als Beispiele durchspielen wäre ein Lebensretter
Reduktionen, beste Samstagabend- Unterhaltung 😁
Freue mich über jedes Video von dir :)
Ich kann mir auch nichts Besseres vorstellen! :D
Freut mich, dass dir die Videos gefallen!
Bitte bitte mehr davon! Gerne über Komplexitätsthemen
Yes please
Niklas top. Ich möchte mehr sehen. Als Mathematiker in der Finanzbranche der ab und zu mit Code zu tun hat sind deine Inhalte ideal und deine Gedankengänge glasklar. Mach weiter so, top!
Hab zwar als Physiker nicht viel mit theoretischer Informatik am hut aber das video fand ich extrem spannend!!! Bitte mehr davon!
Wirklich ein super Video! Gerne mehr in diese Richtung du trägst mich durch Theo2!
Sehr cooles Video. Werden mit jedem Mal besser ❤️
Danke Niklas! Tolle Erklärung
Sehr gutes Video! Ich habe das Thema zwar schon vorher verstanden, bin mittlerweile im Master, aber eine kleine Wiederholung tut immer gut :) Ich finde es sehr gut, dass du das Thema anhand von Python-Code erklärt hast. Das macht das ganze nochmal verständlicher und nicht so dröge.
Ich weiß nicht, ob du den deutschen Kanal NLogSpace kennst, aber der hat mir damals bei dem Thema Reduktionen sehr geholfen. Auf dem Kanal befinden sich zu jedem Thema der Theoretischen Informatik aus dem Bachelorstudium und darüber hinaus Videos (Formale Sprachen, Turing-Maschine, Automaten, Pumping-Lemma, Berechenbarkeit, Komplexität, P/NP, Logik, ...).
Freut mich zu hören! Ja, den Kanal hab ich auch schon gefunden bei meiner Recherche nach anderen Informatikkanälen. :)
Danke für die gute Erklärung!
War nun vier mal in FGI dabei und hab doch noch was gelernt ;)
Du könntest nochmal ein Video zu P/NP machen, ich glaube das wäre auch interessant.
Schön zu hören! Und gute Idee mit P/NP. :)
@@NiklasSteenfatt hast du schon ein video dazu 🙏
Interesantes Video, danke dafür.
Danke :D Gerne mehr davon
War auch als absoluter Informatik-Unwissender sehr gut verständlich.
Mach weiter so. Danke.
Danke, das war hilfreich!
Super Video, vielen Dank! Das Prinzip habe ich jetzt eindeutig verstanden, vor allem auch was man worauf reduzieren muss und warum. Nach meiner Vorlesung Theoretische Informatik hatte ich da leider nur Fragezeichen im Kopf...
Ein zweiter Teil zu dem Video mit einem konkreten Beispiel, WIE die tatsächliche Reduktion dann aussehen kann, wäre super! :)
Ich kann irgendwann mal ein Video mit ein paar konkreten Reduktionsbeispielen machen. In den Lehrbüchern findet man natürlich auch etliche Beispiele, die du dann hoffentlich nach diesem Video schon etwas besser nachvollziehen kannst. :)
@@NiklasSteenfattbisschen spät aber hast du Lektüretipps? Bestenfalls mit mathematischen Fokus
@@NiklasSteenfatt🎉
Geniales Video!
Gut erklärt. Ich schau mir ein Video von dir an und hab es viel besser Verstanden als bei den Erklärungen des Profs, wo man so gut wie gar nichts verstanden hat. Die Profs setzen voraus, als müsste man die Sachen schon alles. So kommt es mir zum Teil vor. Wahrscheinlich machen die die Jobs einfach schon zu lange, so das Sie nicht nachvollziehen können wie es für Leute ist, die die Themen das erste mal hören.
goated video, in der vorlesung so lala verstanden, jetzt aber richtig
Super. Hab ich verstanden
Vielen Dank, ich fand es sehr verständlich:)
Freut mich zu hören!
Cooles video auf alle fälle. Es hat mir sehr geholfen. Ich hätte gerne noch ein beispiel mit dem halteproblem oder PCP gesehen
Ich bin erst 13, jedoch muss ich sagen das Reduktionen sehr interessant sind und du es sehr schön erklärt hast, ich danke dir!
Starke Videos
sehr gut!
gutes video!
Ist es verwegen zu sagen dass man es auf Anhieb verstanden hat?
Muchas gracias
neune_eingabe+=1 so einfach?
Hallo, bin ich im Fach "Theoretische Informatik" stecken geblieben. Ich bräuchte Hilfe bei DEAs/NEAs/Kellerautomaten und Turingmaschinen d.h. jemand, der Coach ist oder Nachhilfe im Bereich gibt? (Die Theorie habe ich viele Male durchgearbeitet, brauche aber Übungen und jemanden zur Seite, um zu sehen was ich falsche mache). An wen könnte ich mich da am besten wenden?
Ich würde auch sowas echt benötigen, warst du mittlerweile fündig ?
Ja, war verständlich :)
Ich find das echt interessant obwohl ich noch gar kein Plan von theoretischer Informatik (bin Abiturient) hab... ist das normal das man das erst ein paar mal durchgehen muss ums zu checken? xD
Ja ein paar mal ist gut
CAP Theorem! In der Praxis super notwendig.
Gute Idee!
Für mich wirkt Reduktion sehr willkürlich, weil auf mich wirkt das so als könnte ich doch das Halte Problem auf jedes beliebige (auch ein lösbares) Problem reduzieren und hätte eine Widerspruch.
wo ist mein Denkfehler?
Hey Fabian! Wenn das so wirkt, probier's doch mal aus! Wie würdest du zum Beispiel das Halteproblem auf das Problem, zwei Zahlen miteinander zu multiplizieren, reduzieren?
@@NiklasSteenfatt Danke für die Antwort, auf die Idee das so zu betrachten wäre ich nie gekommen. Das hilft mir tatsächlich ziemlich weiter, genau diese Aussage hätte ich mir in meiner Vorlesung erhofft.
Wo ist mein Denkfehler dass ich da noch nicht durchschaue bei der Aussage ?
14:27 wieso P oder NP.. ist NP nicht P? Wenn nicht, beweise es :P
Dein Versprechen hast du gehalten
Das man niemals eine Methode finden kann, die das Halteproblem entscheidet (also eine TM die bei jeder möglichen Eingabe anhält oder verwirft), hängt aber auch daran, ob die Church-Turing-These wahrr ist.
Und zu was für einem Schluss kommt man?
@@tangerinegames4515 Das fast alles, was wir über theoretische Informatik wissen, an dieser These hängt und es, falls sie falsch sein sollte, scheinbar eine große unentdeckte Welt der Informatik gibt? Oder worauf willst du hinaus?
@@nitsuj1001 Yes haha darauf wollte ich hinaus danke sehr.
@@tangerinegames4515 Haha youre welcome
Lernst du auch grad fuer reduktionen?@@nitsuj1001
Kannst du mal ein Video machen in dem du erklärst was int, Bool usw. Ist?
SPOILER ALERT 15:41 ..................................................................................................................................................................................................................................................................................................................................................................
-> n = n + 1 bevor die blackbox aufgerufen wird :) sehr gutes und anschaulich simples Video! Toll gemacht!
PS.: Ich finde als Merkhilfe bei Reduktionen das kleiner-gleich Zeichen mit Teilmenge von/enthalten in zu ersetzen sehr viel intuitiver [ - was wahrscheinlich ursprünglich so erdacht war, aber das Zeichen war wohl zu unpassend/mathematisch inkorrekt für etwas, das nicht konkret Mengenlehre ist, daher wurde es vielleicht zu "kleiner-gleich" statt "Teil(menge) von" verändert (ich weiß nicht, ob das stimmt, aber nur so ist für mich das kleiner-gleich logisch lesbar).]
Viele Grüße
Fun fact: Tatsächlich sind für Mathematiker kleiner-gleich und teilmenge-von letztlich zwei Seiten der selben Medaille. Die natürlichen Zahlen sind, wenn man etwas tiefer in die theoretischen Grundlagen der Mathematik eintaucht, nichts anderes als eine Folge von Mengen.
Schreib das Zeichen also gerne spitz, rund oder eckig, wie es dir am liebsten ist! Hauptsache, für den Leser ist klar, dass es um Reduktionen geht. :)
Niklas Steenfatt Das gibt auch Sinn 🙂 finde nur bei Reduktion das kleiner gleich etwas unintuitiv, aber streng gesehen macht hier die Teilmenge weniger Sinn. 😄 Mit der Folge von Mengen zur Definition der natürlichen Zahlen meinst du wahrscheinlich von Neumanns Modell der natürlichen Zahlen. Das ist eine sehr sinnvolle und grundlegende Definition, welche die durch die Peano-Axiome gegebene Logik, finde ich, und die „Natur“ der natürlichen Zahlen
schön veranschaulicht 🙂 viele Grüße und weiter so mit dem Videos!