Algorithmen

Was ist ein Algorithmus?

(in Arbeit)

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems, welche aus endlich vielen wohldefinierten Einzelschritten besteht.

Die Entdeckung oder Erfindung von Algorithmen wird auf al-Chwarizmi zurückgeführt, der sich mit alltäglichen mathematischen Problemen beschäftigt hat.

Eigenschaften eines guten Algorithmus

• Der Algorithmus ist korrekt.
• Der Algorithmus ist konsistent und in sich geschlossen: Alle Fälle sind abgedeckt.
• Der Algorithmus ist effizient (höheres Niveau).

Darstellungen von Algorithmen

• natürliche Sprache
• graphisch: Flussdiagramme, Struktogramme
• Pseudo-Code
• Maschinencode
• …

Zur graphischen Darstellung

• Es gibt einen Anfangs- und Endknotenpunkt
• Es gibt einen Block von Operationen, das ist der Verarbeitungsteil.
  • aus diesem Block kann nur ein eindeutiges Ergebnis weitergegeben werden.
• Es gibt ein Unterprogramm.
• Bedingung, die wahr/falsch prüft.
• Ein/Ausgabe
• Verbindungen

Operationen

• x = 7 bedeutet x ist 7, Gleichheit, für 6 = 7 kann man eine wahre oder falsche Aussage erhalten (Gleichung ungültig)
• x := 7 bedeutet x soll 7 sein.
• x == 7 ist eine Abfrage (nur Informatik), fast wie = . Es bedeutet Ist x gleich 7 oder nicht? Die Prüfung gibt dann einen Wahrheitswert (True oder False bzw. 1 oder 0) zurück.

Beispiel: Euklidischer Algorithmus

Mit diesem Algorithmus kann man den ggT von zwei oder mehr Zahlen finden. Dies macht man mithilfe der Primfaktorzerlegung. Wenn man beispielswiese den ggT(60,24) bestimmen möchte, geht man so vor.

Dieser Algorithmus ist allerdings zu komplex für die Programmierung. Einfacher ist dieser Ansatz:

\begin{equation*}
   ggT(x,y) =
   \begin{cases}
     \text{nicht definiert }   & \text{für } x=y=0 \\
     ggT(x-y,y) & \text{für } x > y \\
     x & \text{für } x = y\\
     x & \text{für } x \neq 0  \wedge y = 0 \\
   \end{cases}
\end{equation*}

Diese Gleichung ist rekursiv, lässt sich durch Programmierung jedoch iterativ anlegen. Man kann den Algorithmus auch einfach per Hand testen. Probiere wir es mal für die Zahlen 442 und 136 aus, du wirst überrascht sein, wie einfach das geht. Versuche mal nachzuvollziehen, was da genau vorsichgeht:

ggT(442,136)\\
=ggT(442-136,136)\\
=ggT(306,136)\\
=ggT(170,136)=ggT(34,136)\\
=ggT(34,136-34)=ggT(34,102)=ggT(34,68)=ggT(34,34)=34

Algorithmen in Assembler-Code

Dieser Code bestimmt den ggT mit Assembler-Code. Er hat aber eine Lücke, was den Fall ggT(0;0) betrifft.

0: INI
1: STA 00
2: INI
3: STA 01
4: LDA 00
5: SBA 01
6: AZJ,EQ 14
7: LDA 00
8: SBA 01
9: AZJ,GR 17
10: LDA 01
11: SBA 00
12: STA 01
13: UJP 04
14: LDA 00
15: OUI
16: STP
17: LDA 00
18: SBA 01
19: STA 00
20: UJP 04

0: INI
1: STA 0
2: ENA 1
3: SBA 0
4: AZJ,EQ 19
5: ENA 2
6: STA 1
7: LDA 0
8: MDA 1
9: AZJ,EQ 20
10: ENA 1
11: STA 1
12: ENA 3
13: MUA 0
14: ADA 1
15: STA 0
16: LDA 0
17: OUI
18: UJP 2
19: STP
20: ENA 2
21: STA 1
22: LDA 0
23: DVA 1
24: STA 0
25: UJP 16

Beispiel goto-Programmierung

//Eingabe x (Register x,y,z)

1: y:=0
2: z:= 1
3: if x ≤ y goto 7
4: y := succ(y)
5: z := succ(z)
6: goto 3
7: x := y

//Ausgabe x

Das ergibt die neue Funktion pred(n), mit der ich den Vorgänger einer Zahl bestimmen kann:

\begin{equation*}
   pred(n) =
   \begin{cases}
      n-1 & \text{falls } n≥1\\
      0 & \text{sonst } (n=0)
   \end{cases}
\end{equation*}

Beim goto sind beliebig Sprünge erlaubt.