---

Geschrieben von 0664jester am 27.03.2014 um 21:14:

  laufzeit

Hallo,

Ich versuche die Laufzeit zu bestimmen. und habe dazu ein Zustandsdiagramm zu meiner Turingmaschine Count2 gezeichnet. Nun bin ich mir nicht sicher ob man count2 so zeigen kann, ob diese zur Klasse p gehört.

Lauzeit
COUNT2={a^n b^n|n>=0} ist entscheidbar da kontextfrei

1. schreibt eimal: start bei 'a', was mit blank überschrieben wird und geht bis zum ende
2. schreibt einmal: , wo der cursor sich vom ende zurueck bewegt, und überschreibt das 'b' dann tritt wieder fall eins ein.

ad 1: jeder durchlauf dauert O(n) schritte, immer 1 ziffer werden ueberschrieben, also hoechstesn n durchlaeufe ->O(n)
ad 2: lauft nur einmal ueber das Band O(n)

Gesamt: O(n)+O(n) = O(n) COUNT2 ϵ TIME(n)


Count2 e P
Die Klasse P ist die Menge aller Sprachen, die von einer DTM in polynomieller Zeit entschieden werden können

P = Uk TIME(n^k) Count2 e P

Unter Laufzeit einer deterministischen Turingmaschine (Entscheider) bei Eingabe w verstehen wir die Anzahl der Schritte, die diese Maschine ausführt, bis sie ein einen terminalen Zustand kommt. Gemessen wird die Laufzeit als Funktion t(n) bezüglich der Länge der Eingabe, also
worst case betrachtung
.Komplexitaet in O-Notation,
.asymptotische Abschaetzung der laufzeit, keine genaue bestimmungen

Die Komplexitätsklasse P gilt als Klasse der effizient
lösbaren Probleme/Sprachen


lg,
0664jester