- 128
- 146 137
Prof. Markus
Приєднався 22 жов 2020
Vorlesungen zum Studium der Informatik, auf deutsch, präsentiert von Markus Krötzsch, Professor für Wissensbasierte Systeme, TU Dresden
Themen sind vor allem Grundlagen wie formale Sprachen, endliche Automaten, Grammatiken, Turingmaschinen, mathematische Logik, Komplexität, Unentscheidbarkeit ... also all die interessanten Dinge, wegen denen man Informatik studiert.
Themen sind vor allem Grundlagen wie formale Sprachen, endliche Automaten, Grammatiken, Turingmaschinen, mathematische Logik, Komplexität, Unentscheidbarkeit ... also all die interessanten Dinge, wegen denen man Informatik studiert.
Logik höherer Ordnung (und Datalog)
Bisher haben wir Prädikatenlogik *erster Stufe* kennengelernt. In diesem Video erkläre ich kurz, was Prädikatenlogik zweiter Stufe ist und wozu diese Erweiterung nützlich sein kann. Dabei sehen wir auch, wie man durch diese Erweiterung auch Datalog-Programme wieder natürlich als logische Formeln auffassen kann, für die wir bei der Anfragebeantwortung ein logisches Auswertungsproblem (Model Checking) auf einer endlichen Interpretation (Datenbank) lösen.
► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html
► Vorlesungsfolien zum Download: iccl.inf.tu-dresden.de/web/TheoLog2021 (22. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dresden.de/web/TheoLog
► Fehler gefunden? Issues melden auf github: github.com/knowsys/TheoLog
► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html
► Vorlesungsfolien zum Download: iccl.inf.tu-dresden.de/web/TheoLog2021 (22. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dresden.de/web/TheoLog
► Fehler gefunden? Issues melden auf github: github.com/knowsys/TheoLog
Переглядів: 894
Відео
Auswertung von Datalog
Переглядів 6103 роки тому
Datalog-Programme lassen sich recht einfach direkt auswerten, indem man solange Regeln anwendet, bis keine neuen Fakten mehr abgeleitet werden können. Diese Idee liefert einen ersten (wenn auch unoptimierten) Algorithmus, den man als eine Variante der prädikatenlogischen Resolution auffassen kann. Die so ermittelten Schlüsse kann man sich auch gut mit Hilfe von Ableitungsbäumen veranschaulichen...
Rekursion, Prädikatenlogik und Datalog
Переглядів 4793 роки тому
Rekursion ist ein wichtiges Feature in Abfragesprachen moderner Datenbanken, das aber in Prädikatenlogik nicht ausgedrückt werden kann. Oder geht das nicht vielleicht doch? Die Diskussion dieser Frage führt uns den Unterschied zwischen Auwertungsproblem (Model Checking) und logischen Schließen (Entailment) noch einmal vor Augen. Am Ende definieren wir Datalog, und zwar zunächst als Fragment der...
Prädikatenlogik und Datenbanken (2)
Переглядів 3003 роки тому
Wir wollen noch zeigen, dass das Auswertungsproblem der Prädikatenlogik (und damit auch die Anfragebeantwortung in Datenbanken) PSpace-vollständig sind, was man leicht durch Reduktion von TrueQBF zeigen kann. Zum Schluss schauen wir noch einmal auf die Grenzen der Ausdrucksstärke von Prädikatenlogik als Anfragesprache. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXz...
Prädikatenlogik und Datenbanken (1)
Переглядів 4623 роки тому
Prädikatenlogische Formeln und (endliche) Interpretationen entsprechen Datenbankanfragen und Datenbankinstanzen. Aus dieser Beobachtung kann man einige Einsichten ableiten, zum Beispiel dass Anfragebeantwortung viel mit dem logischen Auswertungsproblem (Model Checking) zu tun hat. Letztere Beobachtung ist auch ein sinnvoller Ansatz zur Untersuchung der Komplexität dieser praktisch wichtigen Ope...
Prädikatenlogik mit endlichen Modellen
Переглядів 9803 роки тому
Wird Prädikatenlogik einfacher, wenn man statt der bisher vewendeten unendlichen Interpretationen nur noch endliche Interpretationen als Modell zulässt? Macht das überhaupt einen Unterschied für die Semantik? Und was hat das ganze mit Datenbanken zu tun? Diese Fragen sollen in diesem Video beantwortet werden. Wir lernen dabei auch den Satz von Trakhtenbrot kennen. ► Playliste für diesen Videoku...
Die Vollständigkeit der prädikatenlogischen Resolution
Переглядів 6373 роки тому
Endlich schließen wir den Beweis der Vollständigkeit der Resolution ab. Die wenselithce Idee dabei ist es, die Vollständigkeit der aussagenlogischen Resolution auf Herbrandexpansionen in die Ebene der Prädikatenlogik zu "heben": das sogenannte Lifting-Lemma. Aus dem abgeschlossenen Vollständigkeitsbeweis können wir dann noch die Kompaktheit der Prädikatenlogik (erster Stufe) folgern und erste G...
Herbrandexpansionen: Prädikatenlogik auf Aussagenlogik reduzieren
Переглядів 1,1 тис.3 роки тому
Herbrands Idee von "Semantik durch Syntax" lässt sich weiter anwenden, um die Erfüllbarkeit prädikatenlogischer Formeln auf Aussagenlogik zu reduzieren. Außerdem erzähle ich noch die interessante Geschichte hinter der Fotografie Herbrands, welche ich schon im letzten Video gezeigt hatte. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html ► Vorlesungsfolien...
Herbrandmodelle
Переглядів 1,8 тис.3 роки тому
Um die Vollständigkeit der Resolution zu zeigen, wollen wir zunächst von den ziemlich allgemeinen und komplizierten Interpretationen der Prädikatenlogik zu einer einfacheren "syntaktischen" Art von Modellen wecheln: den Herbrandmodellen. Trotz ihrer sehr speziellen Form sind sie in der Lage, die Erfüllbarkeit von Formeln in Skolemform zu charakterisieren. ► Playliste für diesen Videokurs: ua-ca...
Korrektheit der Resolution
Переглядів 4703 роки тому
Der Resolutionssatz stellt die Vollständigkeit und Korrektheit des im letzten Video vorgestellten Algorithmus fest. Ihn zu beweis, wird noch einige Videos in Anspruch nehmen. Die Korrektheit ist dabei der vergleichweise einfache Teil, den wir schon in diesem kurzen Video zeigen können. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html ► Vorlesungsfolien z...
Der Resolutionsalgorithmus
Переглядів 1,7 тис.3 роки тому
Wir schauen uns an, wie Resolution in der Prädikatenlogik funktioniert. Dazu bespreche ich kurz die Unifikation von Atomen und erkläre dann die Resolutionsregel. An einem Beispiel sehen wir, wieso man während der Resolution Varianten bilden muss. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html ► Vorlesungsfolien zum Download: iccl.inf.tu-dresden.de/web/...
Der Unifikationsalgorithmus
Переглядів 1,6 тис.3 роки тому
Zum Lösen von Unifikationsproblemen gibt es einen einfachen Algorithmus, den wir in diesem Video kennenlernen. Wir beweisen außerdem, dass der Algorithmus wie gewünscht funktioniert und zeigen dadurch nebenbei, dass jedes lösbare Unifikationsproblem auch einen allgemeinsten Unifikator hat. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html ► Vorlesungsfoli...
Substitutionen und Unifikation
Переглядів 1,6 тис.3 роки тому
Die wichtigste Neuigkeit beim prädikatenlogischen Schließen im Vergleich zur Aussagenlogik sind die neu hinzugekommenen Terme (aus Variablen, Konstanten und Funktionen). Um mit ihnen logische Schlüsse zu ziehen, müssen wir manchmal Variablen ersetzen (substituieren) damit Terme und letztlich Atome gleich gemacht (unifiziert) werden. Die Grundlagen dazu erklärt dieses Video. ► Playliste für dies...
Die Klauselform in der Prädikatenlogik
Переглядів 1,2 тис.3 роки тому
Im letzten Schritt unserer syntaktischen Vorbereitung auf den Resolutionsalgorithmus wandeln wir die Formel in konjunktive Normalform (KNF) um. Diese kann man dann vereinfacht als Klauselform schreiben. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7XhF-sAU8z4FtL7V9uefCXzW9Z9rk5c.html ► Vorlesungsfolien zum Download: iccl.inf.tu-dresden.de/web/TheoLog2021 (17. Vorlesung) ► Aktuelle und f...
Existenzquantoren entfernen mit Skolemfunktionen
Переглядів 1 тис.3 роки тому
Existenzquantoren lassen sich mithilfe von Funktionen ausdrücken. Diese sogenannte Skolemisierung (nach Thoralf Skolem, 1920) ist ein wichtiger Vorbereitungsschritt für den Resolutionsalgorithmus. Dazu führen wir noch kurz Funktionssymbole in die Prädikatenlogik ein und besprechen, inwiefern sich dadurch (nicht) die Ausdrucksstärke erhöht. ► Playliste für diesen Videokurs: ua-cam.com/play/PLz7X...
Die Negationsnormalform in der Prädikatenlogik
Переглядів 1,1 тис.3 роки тому
Die Negationsnormalform in der Prädikatenlogik
Prädikatenlogisches Schließen ist semi-entscheidbar
Переглядів 3293 роки тому
Prädikatenlogisches Schließen ist semi-entscheidbar
Prädikatenlogisches Schließen ist unentscheidbar
Переглядів 5213 роки тому
Prädikatenlogisches Schließen ist unentscheidbar
Logisch Schließen mit Gleichheit (Teil 2)
Переглядів 5003 роки тому
Logisch Schließen mit Gleichheit (Teil 2)
Ausagenlogische Gesetze in der Prädikatenlogik
Переглядів 6833 роки тому
Ausagenlogische Gesetze in der Prädikatenlogik
Logische Grundbegriffe verstehen mit ein bisschen Modelltheorie
Переглядів 1,3 тис.3 роки тому
Logische Grundbegriffe verstehen mit ein bisschen Modelltheorie
Komplexitätstheorie: Ausblick (und Komplexitäten einiger Spiele)
Переглядів 2933 роки тому
Komplexitätstheorie: Ausblick (und Komplexitäten einiger Spiele)
PSpace-Vollständigkeit 2: Das Spiel Geography
Переглядів 3083 роки тому
PSpace-Vollständigkeit 2: Das Spiel Geography
PSpace-Vollständigkeit 1: TrueQBF und Savitchs Middle-First Suche
Переглядів 3553 роки тому
PSpace-Vollständigkeit 1: TrueQBF und Savitchs Middle-First Suche
PSpace: Schwerer als NP (aber leichter als Schach)
Переглядів 4593 роки тому
PSpace: Schwerer als NP (aber leichter als Schach)
Guten Tag Herr Krötzsch, ich mag Ihren Präsemtationsstil sehr. Es ist immer alles notwendige dabei (man muss nicht extra mitdenken, bei diesen nicht-perfekt-zugänglichen Themen). Haben Sie in Ihren Videos zufällig auch ein/zwei Worte über das Gap-Theorem verloren? Wenn ja wo? Beste Grüße 🙏
Warum genau 2^Q? Warum nicht 3^Q oder 4^Q.
Was ist bei 3:50 mit "Siehe Vorlesung 2" gemeint? Im zweiten Video der "Automaten und Sprachen" Playlist kommt das gar nicht vor.
Ihre Videos sind toll! Obwohl ich nicht an der TU Dresden studiere, setze ich mich mit dieser Vorlesung auseinander. Ich wünschte, die Lehre an meiner Universität wäre so gut wie die Ihre...
Dankeschön, sehr hilfreich
super erklärt. vielen Dank. hat mir bei der Klausurvorbereitung enorm geholfen
Können Sie Ratschläge dazu geben, wie man bei Reduktionsbeweisen vorgeht zuerst?
bitte machen sie eine einfache pruefung
Ich küsse dein kopf
Sie sind zwar nicht mein Professor, aber ich verstehe durch Sie die Sachen sehr gut und besser als durch meinen Professor. Dennoch würde ich Sie gerne fragen, ob solche Beweise auch in Klausuren geführt werden müssen?
In Ebbinghaus (Einführung in die math. Logik, 6. Aufl., S. 34) lese ich folgende Definition: Φ ⊨ ϕ :gdw. jede Interpretation, die Modell von Φ ist, ist auch Modell von ϕ. Das kann man doch umformen: Φ ⊨ ϕ :gdw. jedes Modell von Φ ist auch Modell von ϕ. Richtig? Dann muss aber auch gelten, dass ⊨ ϕ :gdw. jedes Modell ist auch Modell von ϕ. Richtig?
Ja, wenn jedes Model ein Model von ϕ ist, dann nennt man ϕ auch eine Tautologie
Danke für diese gesamte Videoreihe!!
danke wie immer für deine tolle erklärungen prof. markus ! Du hilfst mir immer wieder! :)
Vielen Dank für das Video!
Thumb up fuer die ganze Playlist und Prof Markus!!! Thumb down fuer das Kommentar fuer Horst Muller. Ich fuer meinen Teil bin "Hobby Mathematiker" und schaue mir die Videos freiwillig an. Ich schätze es sehr, dass ich vor meinem smartTV auf der Coach sitzen kann, mit meinem Kaffee in der Hand und die Videos zurück spielen kann, falls ich etwas nicht verstehe. Und das ganze noch gratis, ohne nach Dresden fahren zu muessen, oder Studiengebuehren zahlen zu muessen. (auch gleich gut fuers Klima) Herrn Muller kann ich nur empfehlen sich doch andere Sachen anzuschauen, wenn er an Logik nicht interessiert ist. Und einfach nicht darüber nachzudenken, dass alle Katzen Videos auf UA-cam nur moeglich sind weil es Leute gibt, die schon vor hundert(en) Jahren rein zum Spass über solche Ding nachgedacht haben, wo das Ganze wirklich noch 100% theoretisch war. Herrn Kroetsch, kann ich nur bitten vielleicht auch die anderen Vorlesungen hochzuladen. Ich zumindest wuerde es sehr zu schätzen wissen.
Sie sind ein Ehrenmann
126 + 12 + 7 + 5 +1 = 151 Bei einer Befragung von 152 Experten? Bin jetzt gerade mit der Playlist fertig geworden. War super interessant! Danke
Vielen Dank! Sehr hilfreich.
Es macht wirklich einfach Spaß ihnen Zuzuschauen, vielen Dank!
Ihr Video hat sogar Brasilien erreicht! Vielen Dank für dieses wunderbare Inhalt!
17:00 - Lösungsvorschlag: Bei Kontextsensitiven Sprachen ist die Ableitung oft von den Sachen, die schon abgeleitet wurden abhängig. Bei einer Linksableitung könnte man zuerst zu einer bestimmten Produktionsregel gelangen, die eventuell bei einer Rechtsableitung erst später käme und dabei eventuell eine verschieden Produktionsregel triggert.
Habe jetzt gemerkt dass Sie Sekunden danach die Erklärung geben XD
Habe riesiges Lerngefühl bei diesen Videos! Man versteht was passiert und man kann es danach auch selbst erklären. Wünschte alle Unis hätten ein*e Prof so wie Sie.
Vielen Dank für die ausführliche Erklärung! Auf UA-cam findet man so viele Videos über dieses Thema aber keins ist so methodisch und aufklärend wie Ihres.
Vielen Dank für dieses Video. Habe endlich gut verstehen können was die Klasse NP ist und auch woher die Frage NP=CO-NP kommt. Werde es jetzt auf jeden Fall richtig in meiner Klausur antworten können. Tolle Videos!
Sehr gutes Video danke fürs erklären!
<3
Sie sind der absolute Wahnsinn, dankeschön :D
Super Video
Wirklich gut erklärendes video, und auch sehr toll, dass es den kram über git gibt. In Kiel macht man momentan parallel Prolog, und die Technik am Ende um Funktionen über Prädikate zu implementieren hat in meinem Gehirn eine tolle Brücke dazu geschaffen. Danke :)
Vielen Dank für dieses großartige Video, es hat mir wirklich sehr geholfen!
Dank Ihnen schaffe ich die Prüfung an meiner Uni. Vielen Dank!
Hallo Herr Prof. Markus, Ich habe eine Bitte könnten sie das Vorgehen erklären wie man von einer KF-Sprache z.b. a*n x b*n *c*n+m zu einem Kellerautomaten kommt? Vielen Dank.
Ihr Kanal ist goldwert!
Sehr gutes Video :)
Bzgl. Zeitmaschine: Die Paradoxie entsteht nur, wenn man annimmt, dass es nur eine Zeitlinie gibt. Nimmt man aber an, dass es mehrere Zeitlinien parallel gibt, kommt es nie zu einem Paradox. Darüber hinaus existiert die Zeit nur in unserer Realität. Interessant wird es, wenn man annimmt, dass alles was geschehen ist, gerade geschieht oder noch geschehen wird, zur selben Zeit (jetzt) geschieht, nur eben verschoben. Vergleichbar mit einer Papierrolle, bei der die aufgewickelte Papierbahn die Zeit darstellt und alles was geschieht gleichzeitig entlang des Radius geschieht.
Ich finde, didaktisch sehr gut erklärt. Von mir ein Daumen rauf. 👍
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?
Gelingt es dir denn wenigstens schon, Logiken niederer Ordnung in der Praxis anzuwenden? Wie schaut es aus beim Rasenmähen (kriegst du da die Kurve?) oder noch simpler: schaffst du es alleine, dir die Schnürsenkel_InInnen zu binden? Jedenfalls scheinen die meisten Kenner von Logiken "höherer Ordnung" in Dummbatzhausen-Süd angesiedelt zu sein, die regelmäßig schon nach wenigen Metern Entfernung nicht den Weg zurück zum eigenen Heim finden.
ProgrammiererInInnen? Seufz, waren das noch Zeiten, als es nur Studenten und Studerpel gab, die dann bestens konditioniert von den Unitäten in die Freiheit entlassen wurden, um ohne jedes praktische Wissen ihren Job von der Pike auf zu erlernen (wenn sie nicht schon nach kurzer Zeit wegen erwiesener Dummheit gefeuert wurden). Übrigens scheint eine deiner WasserhähnInInnen zu tropfen - oder was sind das für Hintergrundgeräusche?
Gutes Video! Sollte es (hoffentlich nicht) Thema in meiner morgigen Prüfung sein, hab ich zumindest wenigstens kein kein-Plan. 😅
Hallo Herr Krötzsch, vielen Dank für Ihre Videos, die haben mich echt durch die Klausur gerettet!
es ist keineswegs langweilig. Sie haben die besten videos über manche Themen aus Logik auf deutsch. Wenn jemand was besseres findet, linkt es mir in die Kommentare)))
www.youtube.com/@NLogSpace/videos Ähnlich gut, oftmals ein nicht ganz so theoretischer Ansatz aber auf gleichem Niveau.
In der Beschreibung heißt es: "Die Antwort wird lauten: zur Turingmaschine.". Aber die wird in dem Video gar nicht erwähnt :p
Ab 29:00: Warum liegt v |uw| mal vor und wie wird daraus im nächsten Schritt a^(|v|+1)|uw|, insbesondere wo kommt das +1 her?
Ich bedanke mich für die ausführliche deutliche Erklärung.
Ah yes UA-cam, let's watch this logic programming (I guess?) video in German, nice recommendation for a non-German speaker
True, but isn't it also reassuring that Google does not know you as well as they think they do? Of course, they have to go with what they get from you, e.g., by trying to judge your interests by whether you comment on a video or not ;-) Or maybe they do know you after all - which percentage of UA-cam's audience could identify propositional Horn logic as a form of logic programming? Anyway, at TU Dresden, we also have many free logic-related lectures in English (carefully separated from this German channel); see iccl.inf.tu-dresden.de/web/Courses/en
@@prof.markus6569 I've heard about Horn logic in a propositional logic book from Kazimierz Kuratowski and on some random forum in my endless search for help in bug-fixing, but I'm not a mathematician or a computer scientist, I don't know where UA-cam got this from 😄 Anyways, thanks for the suggestion and good luck in your work!
Why is this in my reccommended?
Vielen Dank für die guten Erklärungen.
Danke sehr! Das Video hat mir sehr geholfen :)
Danke ! Tolles Video