Laufzeit Turingmaschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Wie lange läuft eine Turingmaschine, die ein Wort auf Palindrom überprüfen will? |
Die Turingmaschine startet am Anfang des Wortes, entfernt den ersten Buchstaben, läuft zum Ende des Wortes, überprüft auf Gleichheit. Bei Gleichheit wird auch der letzte Buchstabe gelöscht und man geht zurück zum Anfang des jetzt verkleinerten Wortes, anschließend macht man wieder das Gleiche. Stimmen die Buchstaben nicht überein, so kommt man in einen ungültigen Zustand, der die Turingmaschine stoppt.
Folgendes hätte ich mir überlegt: Zum Vor- und Zurücklaufen benötigt die Turingmaschine im ersten Schritt 2 * Wortlänge (=n) Zeit. Im nächsten Schritt 2(n-2), da 2 Buchstaben weggefallen sind, usw ... Insgesamt wird das Wort n/2 mal verkleinert. Somit bekäme man als Laufzeit (n/2) * (2n - x) [mm] \in [/mm] O(n²). x steht dabei für die ganzen weggefallenen Buchstaben, die hier bei der Kalkülberechnung weniger relevant sind.
Kommt [mm] \in [/mm] O(n²) hin?
Danke für die Hilfe
GHoernle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:44 Di 24.08.2010 | | Autor: | felixf |
Moin!
> Wie lange läuft eine Turingmaschine, die ein Wort auf
> Palindrom überprüfen will?
> Die Turingmaschine startet am Anfang des Wortes, entfernt
> den ersten Buchstaben, läuft zum Ende des Wortes,
> überprüft auf Gleichheit. Bei Gleichheit wird auch der
> letzte Buchstabe gelöscht und man geht zurück zum Anfang
> des jetzt verkleinerten Wortes, anschließend macht man
> wieder das Gleiche. Stimmen die Buchstaben nicht überein,
> so kommt man in einen ungültigen Zustand, der die
> Turingmaschine stoppt.
>
> Folgendes hätte ich mir überlegt: Zum Vor- und
> Zurücklaufen benötigt die Turingmaschine im ersten
> Schritt 2 * Wortlänge (=n) Zeit. Im nächsten Schritt
> 2(n-2), da 2 Buchstaben weggefallen sind, usw ... Insgesamt
> wird das Wort n/2 mal verkleinert. Somit bekäme man als
> Laufzeit (n/2) * (2n - x) [mm]\in[/mm] O(n²). x steht dabei für
> die ganzen weggefallenen Buchstaben, die hier bei der
> Kalkülberechnung weniger relevant sind.
>
> Kommt [mm]\in[/mm] O(n²) hin?
Ja, das Argument kann man aber noch etwas genauer (und mathematisch korrekter) ausfuehren: die Laufzeit ist [mm] $\sum_{k=0}^{\lceil n/2 \rceil} [/mm] 2 (2 k) = 4 [mm] \frac{\lceil n/2 \rceil (\lceil n/2 \rceil + 1)}{2} \le [/mm] n (n/2 + 1) = [mm] \frac{1}{2} n^2 [/mm] + n [mm] \in O(n^2)$.
[/mm]
LG Felix
|
|
|
|
