Friedhelm Meyer auf der Heide 1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätNotationen

A = ist eine endliche, nichtleere menge, ein sog. Alphabet.

ist die Menge aller Worte der Länge n über A.

besteht nur aus dem leeren Wort.

},....,,{ 21 laaa

},....{ 321 AaaaaaA inn

}{0 A

m

n

nm

n

n

n

n AAAAAA010

* ,,

Friedhelm Meyer auf der Heide 2

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätNotationen

,Für

ist eine Sprache über A,

Ihr Komplement

*AL

LAL *

ionKonkatenatdieistAFür *,

aaaa nn 10 ,

Friedhelm Meyer auf der Heide 3

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätFormalisierungen des Begriffs „Algorithmus“

- Programmiersprache mit vollständiger, formaler

Syntax- und Semantik-Beschreibung, z.B.

Java, C, Pascal, Algol

- zu kompliziert, um formal zu argumentieren –

- einfache Rechenmodelle oder Kalküle, die „das gleiche

können wie z. B. Java-Programme“

Turingmaschinen, Registermaschinen,

-Rekusivität, uniforme Schaltkreisfamilien, …

Friedhelm Meyer auf der Heide 4

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätTuringmaschinen

Friedhelm Meyer auf der Heide 5

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätTuringmaschinen

Eine (deterministische 1-Band) Turingmaschine (DTM) ist beschrieben durch

M = (Q, ). Dabei sind Q, endliche, nichtleere Mengen.

1.Q ist die Zustandsmenge.

s, der Startzustand, qaccept , der akzeptierend Zustand, und qreject , der ablehnende Zustand, sind in Q, qaccept und qreject sind verschieden.

2. ist das Eingabealphabet, das Bandalphabet.

t und sind in , aber nicht in

3 Q - {qaccept, qreject} Q {R, L} ist die Übergangsfunktion.

4. Das Startsymbol ist die linke Begrenzung des Bandes, es wird nie gelöscht oder an anderer Stelle geschrieben, es wir nie versucht, Zellen links von ihm zu benutzen.

Friedhelm Meyer auf der Heide 6

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätKonfiguration

Momentaufnahme einer TM

Bei Bandinschrift

( beginnt mit ,

hinter nur t, Zustand q,

Kopf auf erstem Zeichen von :

Konfiguration k = q

Friedhelm Meyer auf der Heide 7

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätNachfolgekonfiguration

K1, K2 seien Konfigurationen, K1 = q , K2 = ‘ q‘ ‘

K2 ist direkte Nachfolgekonfiguration von K1, K1 ` K2,

falls gilt:

K2 entsteht aus K1 durch Ausführung des

(eindeutigen) in K1 erlaubten Rechenschritts.

Welcher ist das? (Sei = a, = b )

(q, b) = (q‘, b‘, R), falls K2 = b‘ q‘

oder

(q, b) = (q‘, b‘, L), falls K2 = q‘ a b‘

Friedhelm Meyer auf der Heide 8

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätRechnungen

- K0 ` K1 ` … ` Ki ist eine Rechnung der Länge i,

- Ki ist i-te Nachfolgekonfiguration von K0, K0 Ki

- Falls K‘ für irgendein i die i-te Nachfolge-konfiguration von K ist: K K‘

Friedhelm Meyer auf der Heide 9

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätAkzeptieren, Entscheiden

- Startkonfiguration von DTM M gestartet mit

- M akzeptiert

- M lehnt ab

Def:

Friedhelm Meyer auf der Heide 10

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätEntscheidbar, rekursiv aufzählbar, berechenbar

Friedhelm Meyer auf der Heide 11

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und KomplexitätBeispiel