Programmierung und Software-Entwicklung – Algorithmen und Sprachen

Darstellung von Algorithmen

Algorithmus: ein Verfahren, das prinzipiell von einer mechanisch arbeitenden Maschine durchgeführt werden kann;
exakt beschriebenes Verfahren inkl. genauer Festlegung von Eingabe/Ausgabe/Zwischenspeicherung von Daten usw., das Verfahren muss so genau ausformuliert sein, dass jeder ohne Rücksprache mit dem Autor den Algorithmus nachvollziehen kann

Pseudosprache:

Algorithmus erhält einen Bezeichner und ist Folge von Anweisungen
Variablen werden in einem declare-Teil vor dem Algorithmus deklariert
elementare Anweisungen: skip, x := a, read(x), write(x), halt, exit, Alg(a, b, c)
Ausdrücke: arithmetische, logische oder Zeichenausdrücke
Hintereinanderausführung/Trennung von Anweisungen mittels ;
Fallunterscheidung: if foo then A [else B] fi
Schleifen: while foo do A od, repeat A until foo,
for i := a [by x] to b do C od (i, a, b, x dürfen nicht verändert werden)

Kommentare beginnen mit --, ein Algorithmus hat die Form

program <Name> is
declare
   <Deklarationen>;
begin
   <Anweisungen>
end

Ablauf protokoll: Tabelle, die Spalten für Schrittnummer, ausgeführte Anweisung sowie alle Variablen nach Ausführung der Anweisung enthält (Ein-/Ausgabe werden gesondert notiert)

Charakteristika von Algorithmen

Eigenschaften: Algorithmus ist Vorschrift, die die Reihenfolge von Handlungen auf Daten beschreibt. Es muss gelten:

Daten sind „disket“ aufgebaut (mit endlich vielen digitalen Zeichen darstellbar)
Operationen sind „diskret“ aufgebaut
Vorschrift ist eine endliche Folge von Operationen/wird schrittweise abgearbeitet
eine Operation ist als Startoperation ausgezeichnet
für jede Operation ist direkt nach der Ausführung bekannt, welches die möglichen (endlich vielen) Folgeoperationen sind oder ob der Algorithmus terminiert
Eingabe ist eine Folge von Daten (auch unendlich oder leer)
die bis zu jedem Zeitpunkt bearbeitete Menge an Daten und durchgeführten Operationen ist endlich

Determinismus: Ein Verfahren, bei dem nach Abarbeitung jeder Operation feststeht, welche Operation als nächste ausgeführt wird, heißt deterministisch.
Sonst (falls mehrere Operationen alternativ zugelassen sind) heißt es nicht-deterministisch.

Terminierung: Ein Algorithmus/Programm terminiert für eine Eingabe \(u\), wenn der Algorithmus bei Eingabe von \(u\) nach endlich vielen Schritten anhält.
Ein Algorithmus terminiert stets, wenn er für alle möglichen Eingaben terminiert.

Unentscheidbare Probleme

Satz (Unlösbarkeit des Halteproblems): Es gibt keinen Algorithmus, der zu jedem beliebigen Algorithmus und jeder beliebigen Eingabe feststellen kann, ob dieser für diese Eingabe terminiert oder nicht (Halteproblem).

Gäbe es nämlich einen solchen Algorithmus \(H\), so könnte man auch einen Algorithmus \(J’\) konstruieren, der einen Algorithmus \(A\) übergeben bekommt, mit: Wenn \(A\) bei Eingabe von \(A\) selbst terminiert, so gehe in eine Endlosschleife, andernfalls verlasse den Algorithmus.

Was passiert beim Aufruf von \(J’\) mit \(J’\)? Würde \(J’\) terminieren, so würde \(J’\) in eine Endlosschleife gehen, also nicht terminieren. Würde \(J’\) nicht terminieren, so würde \(J’\) den Algorithmus verlassen, also terminieren. Widerspruch!

Grundlegende Datenbereiche

Elementare Datentypen: Dazu gehören Boolean (\(\mathbb {B}\)), Natural (\(\mathbb {N}_0\)), Integer (\(\mathbb {Z}\)), Real (\(\mathbb {R}\)) und Character (\(\mathbb {A}\)).

Darstellungen:

natürliche Zahlen: verschiedene Stellenwertsysteme möglich
(Dezimal-/Binär-/Oktal-/Hexadezimalsystem usw.)
ganze Zahlen: Zweierkomplementdarstellung (erstes Bit Vorzeichen)
rationale/reelle Zahlen: Festkommadarstellung (die letzten \(x\) Bit sind Nachkommastellen), Gleitkommadarstellung (\(z = m \cdot b^e\), \(m\) Mantisse, \(e\) Exponent bzgl. Basis \(b\)), Rundungsfehler

Realisierte Abbildung

Realisierte Abbildung: \(f_\pi : E \rightarrow A\) von der Eingabemenge \(E\) in die Ausgabemenge \(A\),
\(f_\pi (e) = \begin {cases} a & \text {falls } \pi \text { bei Eingabe von } e \text { mit der Ausgabe } a \text { terminiert} \\ \bot & \text {falls } \pi \text { bei Eingabe von } e \text { nicht terminiert} \end {cases}\)

Menge der berechenbaren Funktionen:
\(\mathcal {P}_{E,A} = \{f: E \rightarrow A \;|\; \text {es gibt ein Programm } \pi \text { mit } f_\pi = f\}\)

freies Monoid über \(\boldsymbol{M}\): \(M^\ast = \{a_1 a_2 \ldots a_n \;|\; n \in \mathbb {N}_0,\; a_i \in M\}\) (Menge der Wörter),
\(\varepsilon \) leeres Wort (Wort der Länge \(n=0\))

Menge der von Programmen berechenbaren Funktionen:
\(\mathcal {P} = \{f \;|\; \text {es gibt ein Programm } \pi \text { mit } f = f_\pi : D^\ast \rightarrow D^\ast \}\), wobei \(D\) die Menge aller darstellbaren Boolean-, Zeichen-, Ganzzahl- und Gleitkommazahl-Werte ist.

(Künstliche) Sprachen

Alphabet: Eine endliche, linear geordnete Menge \(A = \{a_1, \ldots , a_n\}\) (\(a_1 < \cdots < a_n\)) heißt (endliches) Alphabet.

Sprache: Jede Menge von Zeichenfolgen \(L\) über \(A\) heißt Sprache über dem Alphabet \(A\), d. h. \(L\) ist Sprache über \(A\) genau dann, wenn \(L \subseteq A^\ast \).

Wort: Ein Element \(w \in L \subseteq A^\ast \) einer Sprache heißt Wort.

Operationen mit Sprachen: Vereinigung \(L_1 \cup L_2\), Durchschnitt \(L_1 \cap L_2\),
Komplement \(A^\ast \setminus L\), Konkatenation \(L_1 \circ L_2 = \{uv \;|\;u \in L_1, v \in L_2\}\), Iteration \(L^\ast = \bigcup _{i \in \mathbb {N}_0} L^i\),
\(L^+ = \bigcup _{i \in \mathbb {N}} L^i\) (\(L^i = L \circ \cdots \circ L\)), Ergebnis ist wieder eine Sprache

Grammatiken

Kontextfreie Grammatik: Viertupel \(G = (V, \Sigma , P, S)\) mit

\(V\) nicht-leere endliche Menge (Nichtterminalzeichen),
\(\Sigma \) nicht-leere endliche Menge mit \(V \cap \Sigma = \emptyset \) (Terminalzeichen),
\(P \subset V \times (V \cup \Sigma )^\ast \) endliche Menge (Regeln oder Produktionen),
\(S \in V\) (Startsymbol).

Sei z. B. \(G_1 = (V_1, \Sigma _1, P_1, S_1)\) mit \(V_1 = \{S_1\}\) und \(\Sigma _1 = \{0, 1\}\). Man schreibt statt
\(P_1 = \{(S_1,\; 1), (S_1,\; S_{1}0), (S_1,\; S_{1}1)\}\) normalerweise \(P_1 = \{S_1 \rightarrow 1,\; S_1 \rightarrow S_{1}0,\; S_1 \rightarrow S_{1}1\}\).

Ableitungen: Sei \(G = (V, \Sigma , P, S)\) (kontextfreie) Grammatik. Auf \((V \cup \Sigma )^\ast \) werden definiert:

\(u \Rightarrow v \quad \Leftrightarrow \quad u = xAy, v = xwy\) mit \(x, y \in (V \cup \Sigma )^\ast \) und \((A, w) \in P\)
(\(v\) ist aus \(u\) in einem Schritt ableitbar)
\(u \Rightarrow ^\ast v \quad \Leftrightarrow \quad \) \(u = v\) oder \(u = z_0 \Rightarrow z_1 \Rightarrow \cdots \Rightarrow z_{k-1} \Rightarrow z_k = v\), \(z_i \in (V \cup \Sigma )^\ast \), \(k \ge 1\)
(\(v\) ist aus \(u\) ableitbar), „\(\Rightarrow ^\ast \)“ ist der reflexive und transitive Abschluss von „\(\Rightarrow \)“

Erzeugte Sprache: Die von einer (kontextfreien) Grammatik \(G = (V, \Sigma , P, S)\)
erzeugte Sprache ist die Menge \(L(G) = \{w \in \Sigma ^\ast \;|\; S \Rightarrow ^\ast w\}\). Eine Sprache \(L \subseteq \Sigma ^\ast \) heißt kontextfreie Sprache, falls es eine kontextfreie Grammatik \(G\) mit \(L(G) = L\) gibt.

Bäume: Man kann alle möglichen Ableitungen aus dem Startsymbol einer kontextfreien Grammatik als Baum darstellen. Dieser besteht aus Wurzel, Knoten, Blätter und Kanten. Jede Ableitung entspricht einem Pfad in dem Baum, alle Blätter bilden die erzeugte Sprache \(L(G)\).
Es kann auch die Ableitung eines bestimmten Worts als sog. Ableitungsbaum dargestellt werden, das dem Baum zugehörige Wort heißt dann das abgeleitete Wort des Ableitungsbaums.
Ableitungen eines bestimmten Worts mit gleichem Ableitungsbaum werden als gleich angesehen. Sie unterscheiden sich nur in der Reihenfolge, in der die Regeln auf die Nichtterminalzeichen angewendet werden.

Eindeutigkeit: Sei \(w \in L(G)\) ein Wort der erzeugten Sprache. \(w\) heißt eindeutig, wenn es genau einen Ableitungsbaum gibt, dessen abgeleitetes Wort \(w\) ist. Sonst heißt \(w\) mehrdeutig.
\(G\) heißt eindeutig, wenn alle Wörter \(w \in L(G)\) eindeutig sind. Sonst heißt \(G\) mehrdeutig.

(Kontextsensitive) Grammatik: \(G = (V, \Sigma , P, S)\) heißt (Chomsky-)Grammatik, wenn
\(P \subset V^+ \times (V \cup \Sigma )^\ast \) endliche Menge ist (ansonsten wie bei kontextfreier Grammatik).
Ableitungsrelationen und erzeugte Sprache sind analog wie bei kontextfreien Grammatiken definiert. Allerdings kann man einzelne Ableitungen nun nicht mehr als Baum darstellen, man muss dazu zu einer Netzstruktur greifen.

Backus-Naur-Form: Eine BNF ist ein Viertupel \((V, \Sigma , P, S)\) mit

\(V\) nicht-leere endliche Menge der Form \(<\!\!Zeichenkette\!\!>\) (Nichtterminalzeichen),
\(\Sigma \) nicht-leere endliche Menge mit \(V \cap \Sigma = \emptyset \) und \(| \notin \Sigma \) (Terminalzeichen),
\(P \subset V \{::=\} (V \cup \Sigma )^\ast (\{|\} (V \cup \Sigma )^\ast )^\ast \) endliche Menge (Regeln oder Produktionen),
\(S \in V\) (Startsymbol).

Syntaxdiagramme

Syntaxdiagramm: Jede BNF kann als sog. Syntaxdiagramm grafisch dargestellt werden. Dazu zeichnet man für jedes Nichtterminalzeichen ein Pfeildiagramm mit in Rechtecke eingerahmte Nichtterminal- und in Kreise eingerahmte Terminalzeichen.

Man kann ein Wort der BNF erzeugen, indem man das Diagramm des Startsymbols in Pfeilrichtung durchläuft. Trifft man auf ein Nichtterminalzeichen, so wird sein Diagramm an dieser Stelle „eingeklebt“. Trifft man auf ein Terminalzeichen, so fügt man es an die (anfangs leere) Ausgabe hinzu.

Alle möglichen, sich so ergebenden Ausgaben bilden die erzeugte Sprache.

Sprachen zur Beschreibung von Sprachen

Metasprache: Eine Metasprache ist eine Sprache, mit der man andere Sprachen beschreiben kann.

Es gibt die Ebenen Syntax (korrekter Aufbau der Wörter), Semantik (Bedeutungszuordnung zu jedem Wort/Satz) und Pragmatik (Beziehungen zwischen der Sprache und den Anforderungen).

Fast alle natürliche Sprachen (Deutsch, Englisch usw.) besitzen wie viele formale Sprachen die Eigenschaft, sich selbst beschreiben zu können. Bspw. kann man mit EBNF den Aufbau einer EBNF beschreiben. Allerdings kann nicht alles in EBNF beschrieben werden (Terminalzeichen müssen paarweise verschieden sein usw.).