- 278
- 3 475 357
NLogSpace
Germany
Registrace 20. 10. 2013
Theoretische Informatik verstehen - Formalen Sprachen, Komplexität, Berechenbarkeit, Logik, Automatentheorie.
FAQ
Wie kann man mich kontaktieren?
kontakt_leifaktor_de (Die Unterstriche durch at und Punkt ersetzen.) Ich freue mich immer sehr über Feedback, Kritik und Themenvorschläge! Ich bekomme allerdings auch viele Fragen zu Hausaufgaben. Bitte nicht böse sein, aber ich bin leider sehr beschäftigt, daher antworte ich auf solche Anfragen nicht!
Wie kann man mich unterstützen?
Bewertungen/Kommentare/Weiterempfehlen
Ich antworte zwar meistens auf die Fragen, aber wenn nicht, dann vielleicht aus folgenden Gründen:
- Frage zu einem Detail im Video ohne Zeitstempel
- Frage zu deinen Hausaufgaben
- Frage nicht klar gestellt, grammatikalisch unklar o.ä.
- Frage bereits in anderem Kommentar beantwortet
- Die Antwort wird wirklich absolut klar aus dem Video.
FAQ
Wie kann man mich kontaktieren?
kontakt_leifaktor_de (Die Unterstriche durch at und Punkt ersetzen.) Ich freue mich immer sehr über Feedback, Kritik und Themenvorschläge! Ich bekomme allerdings auch viele Fragen zu Hausaufgaben. Bitte nicht böse sein, aber ich bin leider sehr beschäftigt, daher antworte ich auf solche Anfragen nicht!
Wie kann man mich unterstützen?
Bewertungen/Kommentare/Weiterempfehlen
Ich antworte zwar meistens auf die Fragen, aber wenn nicht, dann vielleicht aus folgenden Gründen:
- Frage zu einem Detail im Video ohne Zeitstempel
- Frage zu deinen Hausaufgaben
- Frage nicht klar gestellt, grammatikalisch unklar o.ä.
- Frage bereits in anderem Kommentar beantwortet
- Die Antwort wird wirklich absolut klar aus dem Video.
Ein Algorithmus für Primfaktorzerlegung (manim animation)
Nur ein kleines Projekt für mich, um manim (github.com/ManimCommunity) zu lernen. Eine Visualisierung von einem Algorithmus, der Primfaktorzerlegungen berechnet.
Der Algorithmus merkt sich die Darstellung der aktuellen Zahl zu verschiedenen Basen. Die Vielfachheit einer Primzahl p in der Primfaktorzerlegung von n ist einfach die Anzahl der Nullen am Ende der Darstellung der Zahl zur Basis p. Außerdem kann eine Zahl n höchstens einen Primfaktor haben, der größer ist als die Wurzel von n. Wenn wir also alle Faktoren von n finden, die kleiner oder gleich der Wurzel von n sind, dann können wir auch den verbleibenden Faktor (falls er existiert) finden, indem wir n durch alle gefundenen Faktoren teilen.
Code: github.com/NLogSpace/primeclock
Der Algorithmus merkt sich die Darstellung der aktuellen Zahl zu verschiedenen Basen. Die Vielfachheit einer Primzahl p in der Primfaktorzerlegung von n ist einfach die Anzahl der Nullen am Ende der Darstellung der Zahl zur Basis p. Außerdem kann eine Zahl n höchstens einen Primfaktor haben, der größer ist als die Wurzel von n. Wenn wir also alle Faktoren von n finden, die kleiner oder gleich der Wurzel von n sind, dann können wir auch den verbleibenden Faktor (falls er existiert) finden, indem wir n durch alle gefundenen Faktoren teilen.
Code: github.com/NLogSpace/primeclock
zhlédnutí: 702
Video
Alternierung #4 - ALogSpace = P
zhlédnutí 616Před rokem
Wir zeigen, dass ALogSpace = P ist. Also die Probleme, die mit einer alternierenden logarithmisch-platzbeschränkten Turingmaschine gelöst werden können, sind genau die Probleme, die mit einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Dabei spielt auch das alternierende Erreichbarkeitsproblem eine Rolle.
Alternierung #3 - AP = PSpace
zhlédnutí 275Před rokem
Wir zeigen, dass AP = PSpace ist, also die Probleme, die von einer polynomiell zeitbeschränkten alternierenden Turingmaschine gelöst werden, sind genau die Probleme, die von einer deterministischen polynomiell platzbeschränkten Turingmaschine gelöst werden können. Das ist ein interessanter Zusammenhang zwischen Alternierung, Zeitkomplexität und Platzkomplexität.
Alternierung #2 - Die Polynomielle Hierarchie mit alternierenden Turingmaschinen
zhlédnutí 223Před rokem
Wir sehen uns an, wie die Komplexitätsklassen der polynomiellen Hierarchie mit alternierenden Turingmaschinen (ATM) definiert werden können. Hierbei betrachten wir die Anzahl der Alternierungen als eine Ressource.
Alternierung #1 - Alternierende Turingmaschinen
zhlédnutí 465Před rokem
Alternierung ist eine Verallgemeinerung von Nichtdeterminismus. Wir sehen uns alternierende Turingmaschinen an.
Satz von Baker, Gill und Solovay
zhlédnutí 379Před rokem
Der Satz von Baker, Gill und Solovay besagt, dass es Orakel A und B gibt, sodass P^A=NP^A und P^B != NP^B ist. Eine wichtige Konsequenz daraus ist, dass ein Beweis für P versus NP nicht relativierbar sein kann. Das schließt gewisse elementare Beweistechniken aus, zum Beispiel Diagonalisierung.
Polyzeit-Hierarchie #4 - Vollständige Probleme
zhlédnutí 247Před rokem
Wir sehen uns Probleme an, die vollständig sind für Klassen in der Polynomialzeit-Hierarchie. Für jedes Sigma^p_k und Pi^p_k gibt es ein vollständiges Problem, welches eine Generalisierung von SAT (und Einschränkung von QBF) mit einer entsprechend langen Quantorenalternierung ist.
Polyzeit-Hierarchie #3 - Logische Charakterisierung
zhlédnutí 263Před rokem
Die Komplexitätsklassen in der Polynomialzeit-Hierarchie lassen sich sehr schön mit dem Allquantor und dem Existenzquantor beschreiben. Hier lernen wir diese Charakterisierung kennen, und beweisen, dass sie äquivalent zu der Definition via Orakel-Turingmaschinen ist.
Polyzeit-Hierarchie #2 - Definition der Polyzeit-Hierarchie mit Orakel-Turingmaschinen
zhlédnutí 401Před rokem
Wir definieren die Komplexitätsklassen der Polynomialzeit-Hierarchie durch Orakel-Turingmaschinen und überlegen uns verschiedene Eigenschaften dieser Klassen.
Polyzeit-Hierarchie #1 - Orakel-Turingmaschinen
zhlédnutí 1,1KPřed rokem
Die Polynomialzeit-Hierarchie (auch polynomielle Hierarchie genannt) ist eine Hierarchie von Komplexitätsklassen innerhalb von PSpace, die die Klassen NP und coNP verallgemeinern. In diesem Video lernen wir das Konzept von Orakel-Turingmaschinen kennen, mit denen die Klassen der Polynomialzeit-Hierarchie definiert werden können.
Schaltkreiskomplexität #15 - Untere Schranken
zhlédnutí 266Před rokem
Aus der Schaltkreiskomplexität ergibt sich ein Ansatz um P ungleich NP zu zeigen, nämlich indem man zeigt, dass es für SAT keine Schaltkreisfamilie polynomieller Größe gibt. In diesem Video sehen wir uns einige Resultate an, die hiermit in Verbindung stehen.
Constraint Satisfaction Probleme
zhlédnutí 812Před rokem
Constraint Satisfaction Probleme (CSP) sind eine große Teilklasse von NP, die unter anderem 3SAT, 2SAT, 2-Färbbarkeit und 3-Färbbarkeit enthält (sogar k-SAT und k-Färbbarkeit für jedes k). Wir sehen uns an, wie CSPs definiert sind, wie sie als Homomorphismenproblem aufgefasst werden können, und erwähnen einige Dichotomie-Resultate.
Ladners Theorem
zhlédnutí 454Před 2 lety
Ladners Theorem besagt, dass es NP-intermediate Probleme gibt, falls P ungleich NP ist. Das sind Probleme in NP, die weder NP-vollständig noch in P sind. Wir sehen uns einen Beweis einer etwas schwächeren Aussage an, und zwar: Wenn die exponential time hypothesis (ETH) gilt, dann gibt es NP-intermediate Probleme. Der Beweis beruht auf einem Padding-Argument.
Mahaneys Theorem
zhlédnutí 376Před 2 lety
Mahaneys Theorem besagt, dass keine spärliche Menge NP-vollständig ist, es sei denn P=NP. (There is no sparse NP-complete language unless P=NP.)
Die Isomorphie Vermutung für NP-Vollständigkeit
zhlédnutí 449Před 2 lety
Die Isomorphie Vermutung für NP-Vollständigkeit
Komplexitätstheorie - Inhaltsübersicht
zhlédnutí 524Před 2 lety
Komplexitätstheorie - Inhaltsübersicht
Schaltkreiskomplexität #14 - P-Vollständigkeit
zhlédnutí 430Před 2 lety
Schaltkreiskomplexität #14 - P-Vollständigkeit
DANKE
Ich verstehe die erste Aufgabe nicht ganz. Wenn i=0 ist, dann ist doch unser y = Epsilon. Hat das jemand verstanden?
@@aji2847 Die Frage wurde schon mehrfach in den Kommentaren beantwortet!
@@NLogSpace alles klar. Ich hatte vorher durchgescrollt und die Frage nicht auf Anhieb unter den Kommentaren gefunden
Nweirz.glamidna
😂i
Hast du deinen Doktor geschafft? Du solltest echt Prof werden! Man merkt, dass du Spaß an der Thematik hast und kannst es wirklich gut und entspannt erklären.
Im Jahr 2024 und du rettest mir den Arsch! Ich hoffe, dass ich am Montag bestehe
@@sirdjones2415 Viel Erfolg!
Unser prof hat einfach mal die wichtige information übersprungen dass A -> BC oder A -> a... kein wunder das ich das solange nicht gecheckt habe :')
Eine Millionen sind zu wenig.
Brutal erklärt
the return of the king
War etwas über 2h zu spät dran, aber mit 200% speed noch fast aufgeholt ^^ Danke, war interessant zu sehen wie schnell man sich so ein abstraktes Spiel selbst basteln kann. Werde mich deshalb bald selbst mal dran versuchen, wenn ich mehr Zeit habe
Hinweis: Im Juli 2024 wurde der Beweis erbracht, dass BusyBeaver(5) = 47.176.870. Dabei ist die Funktion gemeint, die hier im Video TIME genannt wurde. Weitere Infos: discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237
BB(5) ist gefunden worden!
@@guntherirlbeck8631 Ja, danke für den Hinweis! :)
Hallo, bei 17:16 : Gilt hier auch die Umkehrung, also eine Äquivalenzrelation? Ich meine bei allen drei Implikationen
Nein, die Umkehrungen gelten alle drei nicht. Man kann zum Beispiel jedes entscheidbare Problem auf das Halteproblem reduzieren, aber nicht umgekehrt.
die Rechnung von den beiden riesigen Zahlen am Anfang als du die Frage gestellt hast, hat mich zum lachen gebracht ahhahahah. Geiles Video!
hab mir auch gedacht, was wenn ich zwei ehrenlose Zahlen habe xDD
In einer Stunde Prüfung. Hoffentlich wird das was.
Du hast so ein tolles Talent, schwierige Dinge und absurde Konstruktionen verständlich zu machen. ❤
Es wäre schön gewesen, wenn das Beispiel auch eine nicht-deterministisch Turingmaschine gewesen wäre oder zumindest gesagt worden wäre, wie man es in die Grammatik schreibt, wenn ein Zustand zwischen zwei oder mehr Optionen wählen soll. Also ich kann mir denken, dass dann halt auf zwei verschiedene Optionen gezeigt wird wie bei S (Bsp.: S-> aA|a), aber eine Absicherung wäre nett. Noch eine Frage: Beim suchen nach spezifisch DTM umgewandelt zu einer Grammatik kommt nichts wirklich raus. Ist es weil Typ 0 Grammatiken von sich aus nicht-deterministisch sind und somit der Determinismus der anfänglichen TM irrelevant ist? Da wir hier einen DTM benutzt haben, denke ich, dass dies stimmen sollte.
Ja, mit einer "echten" NTM geht es so wie Du sagst.
Grüße raus an die Deutsche Nationalmannschaft :D
Geil, ich liebe diesen Spielvergleich :D
9:40 warum fragen für Erfüllbarkeit wir ob die Funktion immer 1 ausgibt? Ist das nicht Allgemeingültigkeit? Ich dachte man würde fragen, ob die Funktion immer 0 ausgibt. Dann ist sie nicht erfüllbar und dann drehen wir die Aussage um
An der Stelle geht es nicht um Erfüllbarkeit, sondern um Gültigkeit.
Was passiert, wenn man als Orakel die leere Menge nimmt?
Moin Reiner! Die leere Menge als Orakel ist nutzlos. Da die Sprache keine Wörter enthält, würde das Orakel immer "nein" antworten. Dann muss man das Orakel aber gar nicht erst befragen, man kann direkt deterministisch in den "nein"-Zustand übergehen. Somit ist P^ø = P und NP^ø = NP.
@@NLogSpace Die leere Menge als Orakel ist genau deshalb interessant, denn P^ø = NP^ø gdw. P = NP
Retter. Bester Mann wirklich, die ganzen Videos sind größte Hilfe für Theo, Danke 🙏!
super videos danke du rettest mir echt den arsch
Ich frage mich gerade, es gibt doch n! viele möglichkeiten die von einer NTM erraten werden kann. Im worst case würden wir ja alle durchgehen. Das ist doch dann nicht Polynomiell oder?
Richtig, n! ist nicht polynomiell. Aber die NTM geht nicht alle Möglichkeiten nacheinander durch, sondern sie "rät" eine der Möglichkeiten. Eine einzige Möglichkeit zu prüfen geht in polynomieller Zeit.
@@NLogSpace erstmal danke vielmals für die geilen Videos und du schnelle Antwort. Würde es aber, um in der Realität auf eine lösung zu kommen, nicht n! möglichkeiten geben die wir alle überprüfen wollen? z.B. wenn jede variation durchgeprüft wird weil es keinen akzeptierenden Pfad gäbe? Dann wäre die Laufzeit doch n!*p(n). liebe grüße
Wie fange ich denn an, wenn ich kein alleinstehendes Literal was wahr sein muss habe? Oder ist es dann einfach nicht möglich?
Wenn es kein solches Literal gibt, dann ist die Formel immer erfüllbar. Man setzt einfach alle Variablen auf false.
Danke für die schnelle Antwort❤ @@NLogSpace
Jahr 2024 und es hilft immernoch sehr vielen Informatikstudenten. Ich hatte das Thema kein Stück verstanden. 18 min bei dir und es hat klick gemacht. Deine Playlist ist bei uns schon eine generelle Empfehlung für unser Modul. Vielen, vielen, vielen Dank!
Sehr gut erklärt und verständlicher als unser Skript! Kannst du vielleicht auch Videos über Approximationsalgorithmen machen und wie man deren Approximationsfaktor ausrechnet und beweist?
Wenn ich ein Element finde, das sowohl NP Vollständig als auch coNP vollständig ist, dann folgt dass NP=coNP richtig?
Das wäre auch meine Frage. Wenn man doch davon ausgehen kann dass es wahrscheinlich Sprachen gibt, die sowohl in NP als auch in coNP sind, dann wären diese Sprachen (soweit ich das verstehe) sowohl auf NP-vollständige als auch auf coNP-vollständige Sprachen reduzierbar wodurch NP=coNP gelten würde, oder?
Wirklich hilfreich! Herzlichen Dank für Ihr verständliche Videos!
Genial
Vielen Dank für das Video
Wird es in Zukunft noch Übungen zu Erfüllbarkeit und Gültigkeit geben? :)
Danke fürs Video!
Großartiges Video, vielen Dank dafür.
ich liebe dich
alter warum lernt man das in einer tabelle?! deine Form ist gold wert!
Du solltest Dozent werden. In knapp 25min geschafft, was mein Dozent in einem Semester nicht konnte. Top Video!
ich verstehe nicht wie bei den primzahlen aus y^i da y*i wird, weil 3 hoch 3 ist ja nicht = 3 * 3
Weil du hier mit keinen Zahlen rechnest. y^15 würde bedeuten das da 15 mal a steht ^^.
was ist eigentlich i?
Danke sehr. Nur die Beispiele finde ich "zu einfach". Traps und edge cases sind leider nicht dabei. Es wäre z.B. schön gewesen, wenn dieses Beispiel gelöst wurde: (¬Q ∨ ¬P ∨ ¬T ∨ R) ∧ (P) ∧ (S) ∧ (¬R ∨ ¬Q ∨ ¬P) ∧ (T) ∧ (Q ∨ ¬P ∨ ¬T)
soooo gut
klasse!!!
Kuss, du machst alles zugänglich.
Von dem ersten Beispiel. Ist der erste Teil wenn man nach rechts geht bis zum Ende nicht unnötig? Können wir nicht nach dem ersten Zustand schon anfangen X's zu schreiben? Weil wir gehen einmal komplett nach rechts und dann nach links wieder bis zum Anfang... Wir können auch einfach ein Blank nach dem ersten Zustand lesen indem wir nach links gehen und dann nach rechts gehen und wo die Buchstaben sind X's schreiben. Oder irre ich mich? Danke für das Video.
BESTE !!
Ich habe so viele deiner Videos geschaut, warum sehe ich erst einen Tag vor der Klausur, dass du auch Aufgaben hast?!
Gibt es eine Sprache, die in AC_0 ist, aber nicht regulär ist?
Ja, zum Beispiel Wörter der Form 0^n 1^n, also die Sprache enthält die Wörter 01, 0011, 000111, 00001111, ...
@@NLogSpace Aha, ja danke!
darf man Klauseln mehrfach für resolutionsschritte nutzen?
"Ja, Voraussetzungen dürfen mehrfach genutzt werden 3:01 PM bei einer Resolution folgert ihr die ganze Zeit einfach weitere Fakten, die Fakten (bzw. Klauseln) die von Anfang an da waren sich also die ganze Zeit nutzbar" antwort meiner übungsleiterin^^
vielen Dank fürs Super Video! Eine Frage zu 10:50, könnte der 2. Ausdruck nicht auch aa(b*ca)^w sein? oder hat das einen Grund, warum du da b+ca in die Klammer geschrieben hast?