Algorithmen und Datenstrukturen

Praktische Einführung und Programmierung

Stefan Bosse

Universität Koblenz - FB Informatik

1 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle ::

Formale Algorithmenmodelle

ad-dpunkt 6.1

2 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Als erstes formales Modell betrachten wir die sogenannten Registermaschinen. Registermaschinen befinden sich von der Abstraktion nahe an tatsächlichen Computern und bilden daher quasi eine Art »idealisierte« Version eines Prozessors mit Maschinencode-Steuerung.

Eine Registermaschine als Prozessor führt ein Maschinenprogramm aus, das als durchnummerierte Liste von Einzelschritten vorliegt (dies entspricht tatsächlichen Maschinenprogrammen in Rechnern). Die einzige Kontrollstruktur neben der durch die Nummerierung impliziten Sequenz bilden (bedingte) Sprünge, die es erlauben, an einer beliebigen Stelle des Programms mit der Ausführung weiterzufahren.

3 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Daten werden in einem direkt adressierbaren Speicher gehalten, der eine Abstraktion des bekannten Hauptspeichers darstellt.
- Als theoretisches Modell betrachten wir dabei einen beliebig großen, unbeschränkten Speicher. -
Arithmetische Manipulationen werden ausschließlich im Akkumulatorregister des Prozessors ausgeführt.

Diese (maschinennahe) Präzisierung des Algorithmenbegriffs werden wir nun als Registermaschinen exakt definieren. Diese stellen eine relativ simple Abstraktion der programmierbaren Rechner dar, so dass wir in den Bezeichnungen auf vertraute Begriffe der technischen Informatik zurückgreifen.

4 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Eine Registermaschine besteht aus den Registern

B, C0, C1, C2, …, Cn, …

und einem Programm.

Das Register B heißt Befehlszähler, C0 heißt Arbeitsregister oder Akkumulator und jedes der Register Cn, n ≥ 1 heißt Speicherregister.

Jedes Register enthält als Wert eine natürliche Zahl. Enthält das Register B die Zahl b und für n ≥ 0 das Register Cn die Zahl cn, so heißt das unendliche Tupel

(b, c0, c1, …, cn, …)

Konfiguration der Registermaschine.

Das Programm ist eine endliche Folge von Befehlen. Durch die Anwendung eines Befehls wird die Konfiguration der Registermaschine geändert.

Definition einer Registermaschine

5 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Befehle bewirken eine Änderung einer Konfiguration (Zustandsänderung ↦ Imperative Algorithmen!)

(b, c0, c1, … cn, …)

in die neue Konfiguration

(b′, c′0, c′1, …, c′n, …),

geschrieben als

(b, c0, c1, … cn, …) ↦ (b′, c′0, c′1, …, c′n, …),

an.

6 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Ein- und Ausgabebefehle einer Registermaschine

7 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Arithmetische Befehle von Registermaschinen

8 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Sprung- und Stoppbefehle einer Registermaschine

9 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Registermaschine

Architektur und Aufbau einer Registermaschine

10 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Beispiel 1

LOAD 1 DIV 2 MULT 2 STORE 3 LOAD 1 SUB 3 STORE 3 END

Ein einfaches Maschinenprogramm für die Registermaschine - eine reine lineare Sequenz

Stehen in den Registern zuerst die Zahlen

b = 1, c0 = 0, c1 = 32, c2 = 5, c3 = 0,

so ergibt sich diese Folge von Konfigurationen

(1, 0, 32, 5, 0, …) ↦ (2, 32, 32, 5, 0, …) 
                    ↦ (3, 6, 32, 5, 0, …)
                    ↦ (4, 30, 32, 5, 0, …) 
                    ↦ (5, 30, 32, 5, 30, …)
                    ↦ (6, 32, 32, 5, 30, …) 
                    ↦ (7, 2, 32, 5, 30, …)
                    ↦ (8, 2, 32, 5, 2, …),

womit der »stoppende« Befehl erreicht wird.

11 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Beispiel 1

Sind die Inhalte der Register dagegen

b = 1, c0 = 0, c1 = 100, c2 = 20, c3 = 0,

so ergibt sich folgende Folge von Konfigurationen

(1, 0, 100, 20, 0, …)  ↦ (2, 100, 100, 20, 0, …)
                       ↦ (3, 5, 100, 20, 0, …)
                       ↦ (4, 100, 100, 20, 0, …)
                       ↦ (5, 100, 100, 20, 100, …)
                       ↦ (6, 100, 100, 20, 100, …)
                       ↦ (7, 0, 100, 20, 100, …)
                       ↦ (8, 0, 100, 20, 0, …).

Allgemeiner lässt sich Folgendes feststellen. Wir betrachten eine Konfiguration, die durch

b = 1, c0 = 0, c1 = n, c2 = m, c3 = 0

gegeben ist, und nehmen an, dass n = q·m + r mit 0 ≤ r < m gilt, d.h., q = ⌊n/m⌋ ist das ganzzahlige Ergebnis der Division von n durch m und r ist der verbleibende Rest bei dieser Division.

12 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Beispiel 1

Dann ergibt sich immer die Folge

(1, 0, n, m, 0, …)  ↦ (2, n, n, m, 0, …)
                    ↦ (3, q, n, m, 0, …)
                    ↦ (4, q · m, n, m, 0, …)
                    ↦ (5, q · m, n, m, q · m, …)
                    ↦ (6, n, n, m, q · m, …)
                    ↦ (7, r, n, m, q · m, …)
                    ↦ (8, r, n, m, r, …).

Diese Berechnungsfolge der Registermaschine M1 berechnet also den ganzzahligen Rest der Division zweier natürlicher Zahlen.

13 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Registermaschine

Beispiel 2

1. CLOAD 1
2. STORE 3
3. LOAD 2
4. IF c0 = 0 GOTO 12
5. LOAD 3
6. MULT 1
7. STORE 3
8 .LOAD 2
9. CSUB 1
10 .STORE 2
11. GOTO 4
12. END

Mit Kontrollbefehlen und Verzweigung - jetzt werden die Adressen wichtig!

14 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

Bisher gabe es eine klassische von-Neumann Rechnerarchitektur bei der Registermaschine. Häufig werden aber Stackmaschinen als Virtuelle Maschinen verwendet.

Meistens gibt es keine reinen Stackmaschinen sondern eine Mischung aus einer Stack- und Registermaschinen.

Registermaschine: Alle Berechnungen laufen über einen Registerspeicher

Stackmaschine: Alle Berechnungen laufen über einen oder mehrere Stack(Stapel)speicher

15 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

Prinzipielle Architektur einer Stackmaschine mit einem Programmspeicher, Programmzähler PC und Stackzeiger SP

16 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

Die Continuum VM ist ein Beispiel für eine Stackmaschine.

Continuum ist eine virtuelle JavaScript-Maschine, die in JavaScript implementiert ist.

Sie setzt Bytecode aus Quellcode zusammen und führt ihn in einer ES6-Laufzeitumgebung aus.
Ein Assembler wird verwendet, um den AST in Bytecode und statische Skriptinformationen zu konvertieren.
Ein Codeobjekt enthält den kompilierten Bytecode eines Skripts.
- Es enthält auch die meisten statischen Semantiken, die von der Quelle abgeleitet wurden, z. B. gebundene Namen, Deklarationen, Importe / Exporte usw.

Vorteil: Codeobjekte können eine portable Form serialisierbar sein, so dass Code einmal kompiliert und dann in dieser Form weiterverteilt und ausgeführt werden kann.

17 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

Ein Skriptobjekt enthält alle statischen Informationen zu einem Codeabschnitt: die angegebenen Optionen, die Originalquelle, den AST, den Bytecode und den kompilierten Thunk (Operationssatz, ISA), der den Bytecode ausführt.
Skripte enthalten keine Laufzeitinformationen, sodass sie zwischen Realms portierbar sind und mehrmals ausgeführt werden können.

Das besondere von Continuum ist die enge Kopplung von Bytecode Instruktionen (die innerhalbe der VM ausgeführt werden) mit externen JavaScript Funktionen und Daten (z.B. Ein- und Ausgabe).

18 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

Prinzipielle Architekturder Continuum VM

19 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

Befehlssatz

ADD, AND, ARRAY, ARG, ARGS, ARGUMENTS, ARRAY_DONE, BINARY, BINDING, 
CALL, CASE, CLASS_DECL, CLASS_EXPR, COMPLETE, CONST, CONSTRUCT, DEBUGGER, 
DEFAULT, DEFINE, DUP, ELEMENT, ENUM, EXTENSIBLE, EVAL, FLIP, FUNCTION, 
GET, GET_GLOBAL, HAS_BINDING, HAS_GLOBAL, INC, INDEX, INTERNAL_MEMBER, 
ITERATE, JUMP, JEQ_NULL, JEQ_UNDEFINED, JFALSE, JLT, JLTE, JGT, JGTE, JNEQ_NULL, 
JNEQ_UNDEFINED, JTRUE, LET, LITERAL, LOG, LOOP, MEMBER, METHOD, MOVE, NATIVE_CALL, 
NATIVE_REF, OBJECT, OR, POP, POPN, PROPERTY, PROTO, PUT, PUT_GLOBAL, REF, REFSYMBOL,
REGEXP, REST, RETURN, ROTATE, SAVE, SCOPE_CLONE, SCOPE_POP, SCOPE_PUSH, SPREAD, 
SPREAD_ARG,    SPREAD_ARRAY, STRING, SUPER_ELEMENT, SUPER_MEMBER, SWAP, SYMBOL, 
TEMPLATE, THIS, THROW, TO_OBJECT, UNARY, UNDEFINED, UPDATE, VAR, WITH, YIELD

Der ISA Befehlsatz von Continuum: Doch schon umfangreicher als bei rein formalen Modellen und Maschinen!

20 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

Stackmaschine

ADD(context)
───────────────────────────────────────────────────────────
context.stack[context.sp - 1] += context.ops[context.ip][0]
DUP(context)
───────────────────────────────────────────────────────────
context.stack[context.sp] = context.stack[context.sp++ - 1]
LITERAL(context)
───────────────────────────────────────────────────────────
context.stack[context.sp++] = context.ops[context.ip][0]
JUMP(context)
───────────────────────────────────────────────────────────
context.ip = context.ops[context.ip][0]
JTRUE(context)
───────────────────────────────────────────────────────────
isTrue(context.stack[--context.sp])? context.ip = context.ops[context.ip][0]

Wirkung von einzelnen Bytecode Befehlen

21 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Stackmaschine

+</p>

22 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Abstrakte Maschine

Abstrakte Maschine

TODO

23 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Markov Algorithmen

Markov Algorithmen

TODO

24 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Church’sche These

Church’sche These

TODO

25 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Endliche Automaten

Endliche Automaten

TODO

AuD DP 17.4.1/17.4.2

26 / 27

Stefan Bosse - Algorithmen und Datenstrukturen - Modul M Formale Algorithmenmodelle :: Endliche Automaten

27 / 27