ฝัง
- เผยแพร่เมื่อ 15 ก.ย. 2024
- Wir sehen uns an, was nichtdeterministische Turingmaschinen (NTM) sind und was der Unterschied zu deterministischen Turingmaschinen ist. Außerdem gehen wir auf die Frage ein, warum man sich in der theoretischen Informatik überhaupt mit Nichtdeterminismus beschäftigt.
Ein Semester ist rum und ich habe die Theo-Inf Prüfung versemmelt. Ich bin echt froh, dass es deine Videos gibt und dass ich mir die Playlist gespeichert habe. Vielleicht hätte ich einfach alle Videos durchschauen müssen, da mir deine Übergänge/Zusammenhänge zwischen den einzelnen Themen helfen, dieses Modul endlich etwas zu verstehen 😁
Viel Erfolg beim nächsten Versuch!
Sehr praktisch und "aus der Sicht eines Studenten" erklärt. Wirklich sehr gut!
OMG ICH BIN SO GESPANNT
Prima. Sehr einfach. Danke
Gutes Video! Eine Anmerkung: Der „Baum“ der möglichen Schritte einer NTM ist eigentlich kein Baum, da Zyklen auftreten können (im einfachsten Fall eine „Endlosschleife“, aber auch längere Zyklen sind möglich).
Stimmt, danke für die Anmerkung!
Das Bild, das ich gezeichnet habe, könnte man so verstehen: Der Konfigurationsgraph ist, wie Du schon sagst, ein Graph, nicht unbedingt ein Baum. Die Knoten sind alle Konfiguration und man zeichnet eine Kante von k nach l, falls die Turingmaschine in einem Schritt von k nach l gelangen kann. Das Bild, das ich gezeichnet habe, entspricht nun dem "Tree-Unravelling" dieses Graphen von der Startkonfiguration aus, d.h. man zeichnet die Konfigurationen, die auf verschiedenen Wegen erreichbar sind als verschiedene Knoten.
Kuss für den Integralrechner.
einfach Danke !!!
Ich hätte ne Frage, du sagst das ein Wort akzeptiert wird falls es mindestens einen Weg gibt das Wort zu erkennen, warum wird denn dann bb nicht akzeptiert? Es gibt doch einen Pfad der in einem Endzustand landet.
Eine Berechnung ist nur akzeptierend, wenn die Turingmaschine in einem akzeptierenden Zustand anhält. Beim Wort bb erreicht die Maschine zwar zwischendurch einen akzeptierenden Zustand, läuft aber dann noch weiter und hält in einem verwerfenden Zustand.
Achso, also läuft die Maschine bis sie in einem Endzustand gerät von dem aus nichts mehr gelesen werden kann?
Sie läuft bis sie keinen Übergang mehr machen kann. Der Zustand, in dem sie dann anhält, muss nicht unbedingt ein Endzustand sein. Bei Eingabe bb hält sie beispielsweise nicht in einem Endzustand.
Ok jetzt ist es klar, Vielen Dank! und tolle Videoreihe :)
ES IST SO GEIL OMG
OMG ICH LIEBE DICH SO SEHR JAAAA
Ich habe eine Frage für die Beispiel 'aaba'. Nachdem der Kopfleser nach dritte 'b' geht, bleibt 'b' noch und bewegt nach links (b/b/L), warum ist das Weg akzeptiert ? trotzdem hat der Kopfleser die letzte 'a' nicht gelesen.
Die Turingmaschine muss das Wort nicht komplett lesen, um zu akzeptieren/verwerfen. Analogie bei "richtigen" Programmen: Man kann ja auch Programme schreiben, die nicht alle ihre Eingaben verwerten, z.B. ein Programm kriegt ein paar Zahlen als Eingabe und soll deren Produkt ausrechnen. Wenn nun die erste Zahl 0 ist, dann können wir sofort 0 zurückgeben. Dann haben wir nicht einmal alle Eingaben angesehen, aber haben die richtige Antwort zurückgegeben.
Ach so, Danke!
2mal so gut auf 2-facher Wiedergabegeschwindigkeit
sollen wie immer weiter Laufen bis wir keine Möglichkeit haben weiter zu laufen, da beim das lesen von wort bb einmal in aktzepierenden zustand gelanden wurde ?
Ich verstehe die Frage leider nicht ganz. Aber vielleicht ist das die Antwort: Die Berechnungen, die wir hier betrachten, sind immer maximale Berechnungen, d.h. wir laufen immer so lange weiter bis die TM anhält (weil sie keinen möglichen Übergang mehr hat). Wenn eine solche maximale Berechnung existiert, bei der die TM in einem akzeptierenden Zustand hält, dann wird das Wort akzeptiert. Andernfalls wird das Wort verworfen.
AABA
Ist es bewiesen dass es dieses Gerät nicht gibt?