ENDLICHE AUTOMATEN (mit SUPER MARIO erklärt) | Theoretische Informatik
Vložit
- čas přidán 2. 07. 2024
- Inhalt 📚
Wie der Name bereits vermuten lässt, ist das Fach "Theoretische Informatik" sehr theoretisch. Umso wichtiger ist es, sich die abstrakten Konzepte anhand einfacher Beispiele zu verdeutlichen. Deshalb möchte ich dir in diesem Video anhand von Super Mario World erklären, was man unter einem endlichen Automaten (kurz EA) versteht und aus welchen Komponenten er besteht. Statt Zahlen und Buchstaben verwenden wir praktische Beispiele aus dem Gaming-Alltag.
- Einführung: 0:00
- Was ist ein endlicher Automat? 0:21
- Ein praktisches Beispiel: 0:42
- Komponenten eines endlichen Automaten: 1:26
- Formale Definition eines endlichen Automaten: 2:07
- Wie überprüft man, ob ein Wort Teil einer Sprache ist? 3:28
- Wörter mit einem Automaten erzeugen: 4:36
- Verständnisfragen: 5:15
- NFA vs. DFA: 5:27
- ENDE: 5:54
EQUIPMENT(*)
🎤 Mikrofon amzn.to/3N0CHCL
✂️ Schnittprogramm amzn.to/3CZ217J
💻 Mein Laptop amzn.to/3ikMd5V
🖥️ Bildschirm amzn.to/3ig3yN5
SUPPORT
► Patreon / florian_dalwigk
► PayPal
► Unterstütze mich durch einen Kauf auf Amazon. Für dich entstehen keine Mehrkosten! (*) amzn.to/3LgyglY
SOCIAL MEDIA
💬 Discord: / discord
💡 Website: www.florian-dalwigk.de
📱 TikTok: / florian.dalwigk
🤳 Instagram: / florian.dalwigk
🐦 Twitter: / florian_dalwigk
📧 E-Mail: mailto:info@florian-dalwigk.de
Das Spiel "Super Mario World" wurde von Nintendo entwickelt. Von dort stammen auch die hier im Video verwendeten Bilder der Spielfiguren und Items.
Video zur Chomsky-Hierarchie 📼 [Folgt]
NFA in DFA umwandeln 📼 • NFA in DFA umwandeln |...
NFA in DFA umwandeln (Beispiel) 📼 • NFA in DFA umwandeln (...
(*) Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
3. Ist ein mögliches Wort
Kürzestes: 🐢
Ich habe eigentlich keine Ahnung davon, aber ich finde du erklärst sehr gut
Richtig :) Und vielen Dank für dein Lob!
Coole Idee die "Super-Mario" Symbolik zu benutzen ;)
Danke ;) Fand ich an dieser Stelle passend!
Echt Klasse! Für einen Spätzünder in der Informatik (Ü30), wie ich einer bin, sind das echt tolle Beispiele! 😁
Toll, das freut mich 🙂
Es ist nie zu spät ;)
Super Video, lustiger weise haben wir das gerade im Unterricht (10. Klasse). Sehr gut verständlich !
Danke :)
Wow ich hab noch nie was davon gehört und du hast es mir in 5 min beigebracht! Super gut! 🐢
Gerne :)
Deine Erklärungen sind einfach immer klasse 👌🙏😀
Das freut mich, danke!
Super gut. Gefällt mir sehr :D
Das freut mich :)
Ich bin dir sooo dankbar, dass du das ganze so gut verpackt hast! Danke!
Sehr gerne :)
Super erklärt, sehr hilfreich.
Sympathisch und interessant, vielen Dank für die Freude und Hilfe! :)
Gerne doch :)
Hatten das gerade heute in der Vorlesung, war zwar schon klar doch dein Video hat das ganze nochmal verstärkt.
Wirklich? Was für ein Zufall ;)
Top! Großartig erklärt! Vielen Dank! :)
Gerne 🙃
Mega geiles Beispiel im Titelbild xD ... eig. sehr verständlich für alle und schon extrem selbsterklärend. Daumen hoch.
Danke dir :)
Mega starkes Video!
Eine spannende Aufgabe zum Überprüfen des Erlernten in einem zukünftigen Video/zukünftigen Challenge wäre die Interpretation eines "echten" endlichen Automaten.
Das hätte ich noch spannend gefunden und hätte mir als nicht-Informatiker beim Abspeichern des Erlernten geholfen, aber das hätte nicht auch noch alles ins Video gepasst.
Danke für die Anregungen!
Wie gut, dass ich darüber heute teilweise meine Vorabi Klausur geschrieben hab :D
Wie lief's?
@@Florian.Dalwigk Bestens, Info ist jetzt nie so ein großes Problem - bei dem Niveau aber auch kein Wunder :D
Super!
Vielen Dank für das Video. Schreibe in einem Monat die Klausur darüber, wäre cool wenn bis dahin weitere solcher Video kommen :D
Gerne! Dazu werden noch weitere Videos kommen. Ich wünsche dir viel Erfolg beim Lernen!
einfach klasse,,,sehr gut erkl'rt,, vielen vielen vielen dank Super Mario :)))))
😅
Du hast gerade meine info klausur morgen gerettet, danke!
Super :) Ich wünsche dir viel Erfolg!
Sehr schönes Beispiel !. Endlich ein endlichen Automat Verstanden xD
Nice, das freut mich :)
Richtig gut erklärt! Eben noch Fragezeichen vor den Augen durch die ganzen Symbole, jetzt Super Mario ;)
Hervorragend 😃
Danke hat gut in der Klausur geholfen 👍
Hervorragend, so soll es sein 😊
Dass hast du sehr gut erklärt!
Danke dir!
Danke für dieses Video
Gerne, freut mich, dass ich dir weiterhelfen konnte :)
Lange gehadert, endlich verstanden! Danke👍
Hervorragend, so soll es sein 😎
Weiß zwar schon wie Automaten funktionieren, jedoch fand ich die Mario Analogie einfach zu gut um es mir nicht anzuschauen.
Super :)
Meine Schüler schreiben gerade eine Kursarbeit mit diesem Beispiel ;) Danke für die Inspiration. Wobei ich näher an Super Mario World vorgegeben habe, dass Feuer-Mario durch Koopa direkt klein werden soll :D
Ah, wie cool 😎
Ehrenmann. Legenär erklärt
😊
Faszinierend
:)
Einfach gut, so verstehe auch ich das :-)
Perfekt
sehr informativ
Danke
Du rettest mein Studium 🙌🏽❤️❤️
:)
So gut!
😊
danke gut erklärt
Sehr gerne!
Ich glaube nur das 3. ist in der Supermariosprache, da 1. bei großem Mario endet und 2. bei kleiner Marioendet und damit beides nicht in einem endzustand endet. Das kürzeste Wort müsste Kooper sein.
Dem stimme ich voll und ganz zu
Stimmt!
@@marvjojo989 Ist korrekt :)
Toll, das war hilfreich ! Viele Grüße von der LMU München.
Vielen Dank :) Viele Grüße zurück!
@@Florian.Dalwigk Hast du auch Videos über HMM & Viterbi? Konnte da noch kein deutsches finden. Danke
Sehr geil!
:)
@@Florian.Dalwigk Kurze Frage: Darf dieser endliche Automat auch 2 Endzustände haben? Also beispielsweise mit dem Symbol "Flagge", wodurch das Level als bestanden gilt?
Kleiner, erwachsener und heißer Mario müssten dann diesen Pfeil zur Zustandsänderung mit der Flagge haben, aber sind 2 Endzustände grundsätzlich erlaubt?
👍
Gutes Video und schöner Vergleich.
Hilft wahrscheinlich Vielen, die das in der Schule haben.
Danke! Ja, das ist mein Ziel ;)
Danke dir für das video
Gerne!
Das kuerzte Wort ist: Cooper. Nochmal danke fuer das Video, ich habe es zum lernen fuer eine Klassenarbeit benutzt. Weiter so.
Viel Erfolg für die Klassenarbeit
stark
😁👍
Gutes Video!
Dankeschön!
Cooles Video und verständlich erklärt. Aber wozu benötigt man sowas in der Praxis?
Meine Lösungen:
_Bedeutung der Buchstaben ganz unten_
a) Verständnisfragen
1. F, K, P, F, K = Falsch
2. P, K = Falsch
3. F, K, F, K, K, K = Richtig
b) Kürzestes Wort
K
*Bedeutung der Buchstaben*
P = Pilz
F = Feuerblume
K = Koopa
Eis gutes Video! Passend für meine 6.-Klässler :)
6. Klasse?!
@@Florian.Dalwigk Automatentheorie kommt tatsächlich als Thema im Lehrbuch für die 5./6. Klasse vor (C.C.Buchner Verlag). Natürlich völlig "unmathematisch" und deswegen ist mir das Mario-Beispiel viel lieber, als Einstiegsbeispiel als "die Zustandstabelle eines Getränkeautomaten" o.Ä.
Ah, gut zu wissen, danke!
Super erklärt! Ich check nur überhaupt nicht, wie einen das beim Programmieren weiterbringen soll.
Das wird z. B. benötigt, um herauszufinden, ob ein Programm frei von Syntaxfehlern ist.
Danke für das Video! Nur eine Frage hätte ich noch: ,, Sind Automaten Graphen und die Mariozustandsmöglichkeiten sind damit Nodes?"
Ja, so kann man das auffassen.
Ich will im WS ein Informatikstudium anfangen. Der Prof meinte heute beim Tag der offenen Tür, dass endliche Automaten ein knackiges Thema seien, auf das man sich ggf vorbereiten sollte. Jetzt habe ich dein Video gesehen und sehe nicht viel mehr Lernaufwand als die "Grammatik" zu lernen. Ich hoffe ich werde nicht leichtsinnig xd
Und wie läuft es?
@@tungilgynch6044 ich skippe Mathe bisher komplett xD Der Rest läuft super
@@tungilgynch6044 danke der Nachfrage ig
das ist ein gutes video kamerade!
Vielen Dank :)
@@Florian.Dalwigk 2 auf Test nur mit Mario!
Richtig cool 😎 Herzlichen Glückwunsch!
Top, Video! Im Unterricht leider viel zu theoretisch erklärt wurden.
3. ist in der Super Mario Sprache + Ein einzelner Koopa ist das kürzeste Wort
Das freut mich :) Gern geschehen!
Genial! Kürzestes: Cooper! Ich nehme mal an, dass der Automat auch mehrere Enden haben kann, die ein Teil der Wortliste sein müssen. Dieses Denkkonzept gefällt mir sehr! Auch das, wie man das alles mithilfe von Super Mario verdeutlichen kann. Wie passen da invisibility Frames rein? Wäre das dann so, als gäbe es den Cooper nicht? (Wort Ignore certain Words of in-case-Wortliste?)
Danke dir. Könnte man so sehen. Invisible Frames wären in meinen Augen eher so etwas wie das leere Wort ;)
@@Florian.Dalwigk , das leere Wort? Moment: das kann es nicht sein. Es gibt noch das Wort Pit, das trotz der Invisibility-Frames zum letzten Wort führt… Nur Spaß, danke für die Denkanstöße! Ich sehe schon. Da kommt man vom hundertsten ins tausendste. Herrlich!
Kann man einen Webbrowser als Automaten bezeichnen und wenn ja, welcher Art?
Pünktlich zur Prüfung
Perfekt :)
5:20 Cooper
Yes
Coolll
:)
das kürzeste Wort ist die Nummer 2,richtig?
Ist bei dem dargestellten Automaten erlaubt, dass der große Mario einen weiteren Pilz ist (und einfach groß bleibt)? Also Zustand ändert sich nicht, wenn das nächste Event (hier "Pilz essen") eintritt oder muss hierfür explizit ein Pfeil auf den gleichen Zustand zeigen. Hier also Pfeil von großer Mario auf großer Mario und daneben ein Pilz.
Gehe ich mal von aus, meistens zeichnet man die auf sich selbst zeigenden Pfeile nicht auf.
Nunja, es steht nicht dort, also wäre es nicht erlaubt. Man könnte das aber ergänzen.
Ist das Prinzip auch auf Fpga s anwendbar?
Inwiefern?
Jetzt noch Kellerautomaten mit Mario bitte 😂
Kellerautomaten kommen demnächst ;)
Wann kommen die Linux Videos? Freu mich schon drauf.
Schon sehr bald. Ich arbeite aktuell an den ersten dreien.
Schön veranschaulicht!
Aber müsste nicht eigentlich noch beim Großen Mario eine Schleife mit einem Pilz sein? Wenn man einen zweiten Pilz aufsammelt bleibt man ja in dem Zustand
Könnte man hinzufügen, ja
Ich bin so froh das ich zur Wirtschaftsinformatik gewechselt bin und keine theoretische Informatik mehr brauch :-)
Bei welchem Info Studiengang braucht man denn theoretische Informatik? Wir machen den EA nämlich gerade in der Schule (:
30 Folien skip... Ich dank dir xD
Gerne :)
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?
Das kürzeste Wort wäre dann der Koopa ^^
Richtig!
3 ist richtig dass kürzeste Wort ist kooper
Ach ich schrieb gestern darüber eine Klausur geschrieben ;(
Schlechtes Timing - hab aber trotzdem alles eigentlich gewusst :d
Sorry :( Aber gut, dass du trotzdem wusstest, was zu tun ist ;)
@@Florian.Dalwigk es war sogar so ausführlich, dass ich vergaß wie man einen einfachen Satz baut! :D
Und was sind akzeptor und Transduktor? Was sind die unterschiede?
Detektor sagt mir nichts
@@Florian.Dalwigk ich meine natürlich Transduktor
Ah, das sagt mir etwas :)
@@Florian.Dalwigk könntest du mir erklären wie ein Transduktor funktioniert?
Wie werden nicht definierte Überführungsfunktionen gehandhahabt? Is das ein Syntax Error?
Was ist eine nicht definieren Übergangsfunktion?
@@Florian.Dalwigk in deinem Beispiel, wenn man als großer Mario einen Pilz sammelt
Achso. Ja, das ist dann ein Syntaxfehler.
gibt es eine Möglichkeit, meinen Code (zb Java) in so einen Automaten unzuwandeln?
Ja
wie denn? und geht das auch automatisiert?
@@Florian.Dalwigk
Passt jetzt nicht zum Thema des Videos, aber einen Vorteil bringen Klausuren von Zuhause aus schon:
Ich darf Entwicklungsumgebungen nutzen :D
Das kann ein Vor-, aber auch ein Nachteil sein!
Das kürzeste Wort ist ein Cooper: kleiner Mario -> tot
Na ja, in Super Mario World wird man nach einem Hit eigentlich sofort wieder klein, selbst mit Feuer Mario, aber die Erklärung hat auch gepasst, thx!
Gerne
Kürzeste Wort ist Cooper, glaube ich
Korrekt!
Lieber Florian, wo ist das Chomsky Video . ;)
Kommt noch
Übermorgen mündl. Abi 🥶
Ich drücke dir die Daumen 🤞
Wir benutzen dabei die NTPS Gramatik
ok
:)
(:
Dieser Super Mario wird nie ein Level schaffen, weil er immer von einem Koopa getötet werden muss
Das stimmt :( Hier muss noch etwas nachgebessert werden ;)
Ich nehme Nummer vier nur ein koppa 😁
3
👍
Kommentar für den Algorithmus
Antwort auf den Kommentar für den Algorithmus.
Ich finde es sehr traurig dass es Nur den Endzustand ‚tod‘ gibt
:(
Das kürzeste Wort: 🐢
Richtig!
Wieso können Dozenten ihre Skripte nicht so schreiben oder zumindest ein praktisches Beispiel wie dieses geben anstatt 10 Seiten lang wissenschaftliches Zeug zu labern, was niemand außer sie selbst versteht? Vielen Dank!
Sehr gerne 😊
Das kürzeste word ist ist : *Koopa*
Genau!
3 endet
?
Du bist Gott
😇
Kuhper
🐢
1:16 Das stimmt aber für die originale SNES Version gar nicht; man wird direkt klein. Deabonniert!
Da kann ich mich nur anschließen. Algorithmen verstehen lässt langsam nach, kaum aushaltbar.
@@tomchenkov4910 :(
Und was bringt mir das jetzt? Also nur mal so gefragt
Endliche Automaten sind ein Modellierungswerkzeug in der Informatik. Wenn man eine solche Modellierung versteht, kann man bestimmte Probleme einfacher lösen.
Eine theoretische Anwendung ist die Erkennung, ob ein bestimmtes Wort Teil einer (regulären) Sprache ist.
Spannender finde ich die Anwendung, eigene Automaten zu bauen. Z.B. könnte man damit einen Roboter programmieren, der einen Weg durch ein Labyrinth findet (oder die Wohnung reinigt).
Du bist Gott
Warum wusste ich das bisher noch nicht?