spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hier sind ja auch einige hauptberufliche/studierte Informatiker vertreten und daher dachte ich mir, vielleicht weiss ja einer von euch Rat.

Wir haben eine Hausaufgabe (siehe Anhang), bei der ich nicht wirklich weiter komme. Eine 1-Band DTM (deterministische Turingmaschine) zur Bestimmung von Palindromen ist mit einer Laufzeit von O(n²) ja trivial. Auch wenn es in der Aufgabenstellung nicht steht, wird n hier die Eingabenlänge sein.
Jedoch finde ich keinen Weg, eine DTM zu bauen, die das ganze in der vorgegeben Laufzeit bestimmt. Ausserdem verwirrt mich das, mit dem beliebig kleinen Epsilon etwas. Ja, mir ist das Prinzip aus zB der Analysis bekannt, aber dadurch wird das n² ja extrem klein und irgendwie fast schon unnötig. Da ein Teil der Laufzeit O(n) ist, habe ich mir schon einige Verfahren überlegt, bei dem die DTM einmal(oder halt linear wachsend) über die Eingabe gehen muss und danach in sehr kleiner Zeit (epsilon*n²) bestimmen kann, ob es ein Palindrom ist oder nicht, aber alle Überlegungen liefen ins Leere. Wobei ich denke, dass es so im Prinzip laufen muss.
Die Sache mit den Zuständen und der Zustandsmenge ist sicherlich ein Tipp, welcher sich mir aber nicht wirklich erschliesst. Da wir idR ein binäres Alphabet für die Eingabe haben(sehr doof, dass es hier nicht genau spezifiziert ist), könnte man natürlich jede mögliche Kombination an Eingaben als Zustände codieren, aber dann wäre die Zustandsmenge ja auch irgendwie unendlich und das ist ja nicht möglich.

Kann mir hier vielleicht jemand mit Tipps weiterhelfen? Also das ist die Aufgabenstellung, mehr steht da nicht. Solltet ihr noch andere Definitonen oder so brauchen, einfach sagen

Schonmal danke für jeden, der versucht mir zu helfen

ERROR

Ich glaube nicht oder???

Das wäre auch irgendwie komisch, weil in der aller ersten Hausaufgabe dieses Semster hatten wir in dem Kurs eine Turingmaschine, die in quadratischer Laufzeit Palindrome entscheidet, die war sogar auf der Folie gegeben. Würde ich komisch finden, wenn wir jetzt genau das gleiche einfach aufstellen sollen?

Natürlich, jetzt wo ich es so sehe, stimme ich dir zu

Also wäre theoretisch der triviale Ansatz "i tes und n-i tes Zeichen gegeneinander prüfen"(in jedem neuen Schritt dann i+1) korrekt laut Aufgabenstellung. Aber wie gesagt, genau die DTM hatten wir bereits auf den Folien, das kann dann doch nicht die Lösung sein, oder?