Zeitkomplexität einer 1-B-DTM simulieren |
| 19.12.2013, 17:50 | Auf diesen Beitrag antworten » | ||
| yuro123 | Zeitkomplexität einer 1-B-DTM simulieren Hallo Leute 
Hab mal eine Frage wie man auf folgende Lösung kommt. Konnte nicht aus meinen Skripten rausfiltern.
Würde mich über jede Form von Hilfe freuen 
|
||
|
|
|||
| 19.12.2013, 19:03 | Auf diesen Beitrag antworten » | ||
| Karlito | Hallo yuro123, wie die 1-Band DTM konstruiert wird, welche eine n-Band DTM simuliert weiß ich momentan leider auch nicht mehr genau. Wikipedia verrät, dass der Aufwand immer quadratisch wächst. Dunkel aus meiner Erinnerung wird eine n-Band DTM durch eine Einband-DTM simuliert, indem jede Zelle nun ein 2n-Tupel hält, wobei jede 2. "Zeile" des Tupels die aktuelle Position des Lesekopfes auf dem simulierten Band darüber oder darunter hält. Der Mehraufwand entsteht nun dadurch, dass bei jeder Aktion immer erst das betroffene Tupel (in der sich der Marker für die aktuelle Position befindet) gefunden werden muss, und dass dieser Marker entsprechend der zu simulierenden DTM umgesetzt werden muss. Ich hoffe das reicht dir erstmal an Information. Wenn du es genauer wissen willst, dann würde ich dich an dieses Buch verweisen. Darin befindet sich eine detaillierte Beschreibung der Simulation. Edit: Tipp: Vielleicht gibt es das Buch ja auch bei Dir in der Uni-Bibo und da vielleicht sogar kostenfrei als Online-Version. Gruß, Karlito |
||
|
|