Konzepte der Programmierung 09.10.

2023

Algorithmen

Bernhard Westfechtel
Angewandte Informatik I
Universität Bayreuth

Bernhard Westfechtel Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Erinnerung

Ein Algorithmus ist ein schrittweises,

präzises Verfahren zur Lösung eines Problems.

Algorithmus zur Berechnung des GGT

Eingaben: natürliche Zahlen a, b

1. Setze m  a, n  b
2. Ist m < n, so vertausche m und n
3. Berechne r  m  n
4. Setze m  n, n  r
5. Ist r ≠ 0, weiter mit Schritt 2
Ausgabe: m = ggT(a, b)

Bernhard Westfechtel 2 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A1 Relation zwischen Eingaben und Ausgaben

Ein Algorithmus beschreibt eine Relation über dem Kreuzprodukt

einer Eingabe- und einer Ausgabemenge. Dadurch werden für jede
Eingabe die zulässigen Ausgaben festgelegt.

I Eingabemenge
O Ausgabemenge
IO Kreuzprodukt
I  O = {(i, o) | i  I  o  O}
RIO Ein-/Ausgaberelation

[Echtle 2000]

Bernhard Westfechtel 3 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A2 Wohldefinierte Elementaroperationen

Ein Algorithmus setzt sich aus wohldefinierten Elementaroperationen

zusammen, die auf einer geeigneten „Maschine“ ausführbar sind.

A3 Festlegung der Reihenfolge

Ein Algorithmus legt die Reihenfolge der Schritte fest, wobei jeder
Schritt genau eine Elementaroperation umfasst.

[Echtle 2000]

Bernhard Westfechtel 4 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A4 Endlichkeit der Beschreibung

Ein Algorithmus hat eine Beschreibung endlicher Länge.

A5 Endlicher Speicher

Ein Algorithmus benutzt nur endlich viele Speicherplätze zur Ablage

von Zwischenergebnissen.

[Echtle 2000]

Bernhard Westfechtel 5 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A6 Terminierung

Für jede Eingabe endet die Ausführung des Algorithmus nach

endlich vielen Schritten.

A7 Begrenzte Schrittanzahl

Für jede Eingabe wird die zugehörige Ausgabe spätestens nach

Ausführung einer vorgegebenen Schrittanzahl s geliefert.

[Echtle 2000]

Bernhard Westfechtel 6 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A8 Determiniertheit

Die Ein-/Ausgaberelation ist rechtseindeutig (d.h. eine Funktion).

Jeder Eingabe wird genau eine Ausgabe zugeordnet.

R ist rechtseindeutig 
(i, o)  R  (i, o´)  R  o = o´

A9 Determinismus

In jedem Zustand, der bei Ausführung des Algorithmus erreicht

wird, ist jeweils nur ein einziger Folgeschritt ausführbar.

[Echtle 2000]

Bernhard Westfechtel 7 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Beispiel für Indeterminiertheit

Frings Ludwig 15.04.74

Meier Thomas 17.03.79

Meier Anja 11.12.81

Cremer Carola 23.01.78

Sortieren
nach dem Nachnamen

Cremer Carola 23.01.78 Cremer Carola 23.01.78

Frings Ludwig 15.04.74 Frings Ludwig 15.04.74

Meier Anja 11.12.81 Meier Thomas 17.03.79

Meier Thomas 17.03.79 Meier Anja 11.12.81

Bernhard Westfechtel 8 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Determinismus: Beispiele [Echtle 2000]

Deterministischer Algorithmus
1. Lies Eingaben x und y
2. Falls x  y: weiter mit Schritt 3,
falls x > y: weiter mit Schritt 4
3. Setze a  y  x, weiter mit Schritt 5
4. Berechne a  x  y
5. Schreibe Ausgabe a
Ziel: Berechnung des
„Abstands“ von x und y
(|x – y|)
Indeterministischer Algorithmus
1. Lies Eingaben x und y, weiter mit Schritt 2 oder 3
2. Berechne a  x  y, weiter mit Schritt 4
3. Berechne a  y  x
4. Falls a  0: weiter mit Schritt 5,
falls a < 0: weiter mit Schritt 6
5. Setze b  a, weiter mit Schritt 7
6. Berechne b  -a
7. Schreibe Ausgabe b

Bernhard Westfechtel 9 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A10 Korrektheit

Sei S die Spezifikation eines Algorithmus A, d.h. die Beschreibung

der Relation, die A berechnen soll (S  I  O). Ferner sei R die
tatsächlich von A berechnete Relation (R  I  O).

A heißt korrekt bezüglich der Spezifikation S 

1. Berechnete Werte für zulässige Eingaben sind korrekt:
i  dom S  (i, o)  R  (i, o)  S
2. Für jede zulässige Eingabe wird ein Wert berechnet:
dom S  dom R

dom S = {i  I | es gibt ein o  O: (i, o)  S}

(Definitionsbereich, „domain“)
[Echtle 2000]

Bernhard Westfechtel 10 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Beispiel: GGT
- I ℕ  ℕ Menge aller Paare natürlicher Zahlen
- O ℕ
- S  (ℕ  ℕ  ℕ
m, n , ggt  S 
m, n, ggt  ℕ  ggt ist größter gemeinsamer Teiler von m und n
- dom S ℕℕ
- Anforderungen an die von einem Algorithmus berechnete Relation R
o Jeder berechnete Wert ist korrekt:
m, n  dom S  m, n , ggt  R  m, n , ggt  S
o Jeder verlangte Wert wird berechnet:
m, n  dom S  m, n  dom R

Bernhard Westfechtel 11 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A11 Allgemeinheit

Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine
Klasse von Problemen.

A12 Änderbarkeit

Ein Algorithmus soll sich leicht modifizieren lassen, um ihn an eine

veränderte Aufgabenstellung anzupassen.

A13 Verständlichkeit

Ein Algorithmus soll leicht verständlich und gut dokumentiert sein.

[Echtle 2000]

Bernhard Westfechtel 12 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Eigenschaften von Algorithmen

A14 Ausführungseffizienz

Für eine gegebene Eingabe soll die Anzahl der benötigten Schritte
( Laufzeiteffizienz) und Speicherplätze ( Speicherplatzeffizienz)
möglichst gering sein.

A15 Programmiereffizienz

Ein Algorithmus soll eine möglichst kurze Beschreibung haben.

A16 Robustheit

Ein Algorithmus soll sich möglichst auch dann wohldefiniert verhalten,

wenn eine unzulässige Eingabe (die nicht Element der Eingabemenge
ist) vorliegt.
[Echtle 2000]

Bernhard Westfechtel 13 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Beispiel zur Robustheit

- In vielen Programmiersprachen (einschließlich) gibt es keinen
Datentyp für natürliche Zahlen, sondern nur einen Datentyp für
ganze Zahlen
- Robustheit: Falls der Algorithmus eine natürliche Zahl als Eingabe
erwartet und eine negative ganze Zahl als Eingabe erhält, sollte er
sich wohldefiniert verhalten
- Beispiel GGT
o Für negative Eingaben sollte ein Wert zurückgeliefert werden,
der einen Fehler signalisiert (z.B. -1)
o Ohne die Eingaben zu prüfen, würde der Algorithmus zur
Berechnung des GGT für negative Eingaben nicht terminieren
 Beispiel: GGT(-5, 15) = GGT(15, -5) = GGT(-5, 20) =
GGT(20, -5) = GGT(-5, 25) = …

Bernhard Westfechtel 14 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Zusammenfassung der Eigenschaften

- „Muss“-Eigenschaften - „Soll“-Eigenschaften
o A1: Relation Ein-/Ausgaben o A11: Allgemeinheit
o A2: Wohldefinierte o A12: Änderbarkeit
Elementaroperationen o A13: Verständlichkeit
o A3: Festlegung der Reihenfolge o A14: Ausführungseffizienz
o A4: Endlichkeit der o A15: Programmiereffizienz
Beschreibung o A16: Robustheit
o A5: Endlichkeit des Speichers
o A10: Korrektheit

- „Kann“-Eigenschaften
o A6: Terminierung
o A7: Begrenzte Schrittanzahl
o A8: Determiniertheit
o A9: Determinismus

Bernhard Westfechtel 15 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Bestandteile von Algorithmen

Algorithmus = Daten + Anweisungen

Daten Anweisungen
1. Setze m  a, n  b
Eingaben 2. Ist m < n, so vertausche m und n Zuweisungen
a, b 3. Berechne r  m - n mn
Variablen 4. Setze m  n, n  r Bedingungen
m, n, r 5. Ist r ≠ 0, weiter mit Schritt 2 m<n
Ausgaben 6. Das Ergebnis ist ggt  m Sprünge
ggt „weiter mit …“

[Mössenböck 2014]

Bernhard Westfechtel 16 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Daten
Name Behälter Wert

a 15
Eingaben
b 55

m 15 55 15 40 15 25 15 10 5

Variablen n 55 15 40 15 25 15 10 5 5

r 40 25 10 5 5 0

Ausgaben ggt 5

Bernhard Westfechtel 17 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Variablen
Mathematik Informatik

Eine Variable steht für Eine Variable ist ein

einen unbekannten, aber benannter Behälter für einen
konstanten Wert veränderlichen Wert

Beispiel Beispiel

x, y  R : m 15 m
n 55
( x  y ) 2  x 2  2 xy  y 2 n

Vertausche
m und n

m 15 55 m

[Mössenböck 2014] n 55 15 n

Bernhard Westfechtel 18 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Wertzuweisungen

Eine Wertzuweisung (kurz: Zuweisung)

berechnet den Wert eines Ausdrucks und legt
ihn in einer Variablen ab.

Variable Zuweisungs- Ausdruck

(linke Seite) zeichen (rechte Seite)

rmn

Zuweisung und Gleichheit

sind sorgfältig zu unterscheiden!

[Mössenböck 2014]
Beispiel: i  i + 1 erhöht den Wert von i um 1

Bernhard Westfechtel 19 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Kontrollfluss

Der Kontrollfluss regelt die

Reihenfolge der Ausführung von Anweisungen

Startknoten Endknoten Elementare Anweisung

Start
A
Stop

... Flussdiagramme

T(rue) F(alse) M(…)

B?

Vereinigung Verzweigung Methoden-

aufruf
Bernhard Westfechtel 20 Angewandte Informatik I
Konzepte der Programmierung 09.10.2023

Sequenzen und Verzweigungen

Vertauschen zweier Variablen Distanz zweier Variablen

Start Start

x = 0, y = 1
T(rue) F(alse)
hx x<y

Verzweigung
x = 0, y = 1, h = 0
Sequenz

xy abs  y  x abs  x  y

x = 1, y = 1, h = 0

yh

x = 1, y = 0, h = 0

Stop Stop

Bernhard Westfechtel 21 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Schleifen
Start

Fakultät fak  1

1 n 1
n!  i1
n(n  1)! sonst
n!  n(n  1)!
 n(n  1)(n  2)!
... F
i<n
n
 n!  i T
i 1
ii+1

fak  fak * i Stop

Bernhard Westfechtel 22 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Bestandteile einer Schleife

Eingang

F
Bedingung i<n Ausgang
T

ii+1

Rumpf
fak  fak * i

Bernhard Westfechtel 23 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Berechnungsbeispiel
Start
Durchlauf n i fak
fak  1 0 5 1 1
1 5 2 2
i1 2 5 3 6
3 5 4 24
4 5 5 120

F
i<n
T
ii+1

fak  fak * i Stop

Bernhard Westfechtel 24 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Methoden

Eine Methode ist eine benannte Folge von

Anweisungen, die logisch zusammengehören und
eine bestimmte Teilaufgabe erledigen.

Ein Methodenaufruf bewirkt die Ausführung

einer Methode und behandelt diese als eine
atomare Einheit.

Start
Kleinstes gemeinsames
Vielfaches Berechne ggt(a, b)

ab
kgv(a, b)  kgv  a*b/ggt
ggt (a, b)
Stop

Bernhard Westfechtel 25 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Rekursion

Eine Methode, die sich selbst aufruft, nennt man

rekursiv.
Rekursion führt ein Berechnungsproblem auf ein Problem
gleicher Art für einen einfacheren Fall zurück.

Start Beispiel:
fak(5) = 5 * fak(5-1) =
T F
n1 5 * fak(4) = 5 * 4 * fak(3) =
5 * 4 * 3 * fak(2) =
5 * 4 * 3 * 2 * fak(1) =
fak  1 Berechne fak(n – 1)
5*4*3*2*1=
5*4*3*2=
fak  n * fak(n  1) 5*4*6=
5 * 24 =
Stop Stop 120
Bernhard Westfechtel 26 Angewandte Informatik I
Konzepte der Programmierung 09.10.2023

Struktogramme
- Struktogramme basieren auf der strukturierten Programmierung
o In Flussdiagrammen lassen sich beliebige Sprünge darstellen
o Struktogramme erzwingen wohldefinierte Kontrollstrukturen
 Jede Kontrollstruktur hat genau einen Ein- bzw. Ausgang
 Kontrollstrukturen lassen sich 1:1 in Java abbilden
o In einem Struktogramm wird jede Anweisung durch ein Rechteck
dargestellt
o Jedes Rechteck repräsentiert entweder eine elementare oder
eine zusammengesetzte Anweisung
o Struktogramme unterstützen folgende Kontrollstrukturen
 Sequenz
 Bedingte Anweisung (Verzweigung)
 Schleife

Bernhard Westfechtel 27 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Kontrollstrukturen
Sequenz Bedingte Anweisung Schleife
A1 T B F B
A2 A1 A2 A

Struktogramm

Flussdiagramm

B
A1 T F
F
A1 A2 B
A2
T
A

Bernhard Westfechtel 28 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Beispiel
Start Flussdiagramm Struktogramm

fak  1

i1 fak  1
i1
i<n
ii+1
F
i<n fak  fak * i
T
ii+1

fak  fak * i Stop

Bernhard Westfechtel 29 Angewandte Informatik I

Konzepte der Programmierung 09.10.2023

Zusammenfassung
- Ein Algorithmus ist ein schrittweises, präzises Verfahren zur Lösung
eines Problems
- Die Eigenschaften eines Algorithmus lassen sich in drei Kategorien
aufteilen („Muss“, „Kann“ und „Soll“)
- Eigenschaften von in dieser Vorlesung behandelten Algorithmen
o Alle „Muss“-Eigenschaften (inkl. Korrektheit)
o Terminierung (für zulässige Eingaben)
o Determiniertheit
o Determinismus

- Algorithmen lassen sich unterschiedlich notieren

o Strukturierter Text
o Graphisch: Flussdiagramme oder Struktogramme

Bernhard Westfechtel 30 Angewandte Informatik I