Algorithmen und Datenstrukturen

Praktische Einführung und Programmierung

Stefan Bosse

Universität Koblenz - FB Informatik

1 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen ::

Darstellung von Algorithmen

Diagramme und Pseudonotation

  1. Flussdiagramme: Beschreiben das Verhalten von Algorithmen durch Abläufe;

  2. Struktugramme: Beschreibt strukturelle Eigenschaften von Algorithmen;

  3. Pseudonotation: Teils Verhaltens, teils strukturelle Beschreibung.

2 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Darstellungsformen von Algorithmen

Darstellungsformen von Algorithmen

Um Algorithmen allgemeinverständlich auszudrücken, ohne den Adressatenkreis auf eine Programmiersprache einzugrenzen, werden häufig Programmiersprachen-unabhängige Ausdrucksformen gewählt. Neben

  • dem Programmablaufplan (PAP, DIN 66001),

  • dem Nassi-Shneiderman-Diagramm (“Struktogramm”, DIN 66261),

  • oder dem UML-Aktivitäts-Diagramm (siehe gesonderter Artikel)

ist dies v.a. auch eine natürlichsprachlich vereinfachte und syntaxfreie Form des Programmcodes - der Pseudocode.

3 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Geläufige Pseudocode-Notationen

Geläufige Pseudocode-Notationen

Für Pseudocode gibt es kein festes einheitliches Regelwerk, vielmehr muss eine für den Adressatenkreis passende Variante gewählt werden: Häufig wird eine geläufige Programmiersprache vereinfacht.

Beispielhaft werden hier drei Varianten vorgestellt, die häufig eingesetzt werden:

  • JANA: Insbesondere für Entwickler*innen mit Java/C/C++/C#-Kenntnissen leicht verständliche Notation (Java-Based Abstract Notation for Algorithms)

  • Pseudo-Pascal: An die Programmiersprache Pascal angelehnte Variante (v.a. in älteren Lehrwerken verbreitet)

  • deutsches Pseudo-Pascal (eigene Namensschöpfung): eine eingedeutschte Pseudo-Pascal-Variante, die vor allem im Bereich der Fachinformatiker*innen-Ausbildung verwendet wird (da die IHK sie in den Prüfungen und Beispiellösungen verwendet).

4 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Geläufige Pseudocode-Notationen

Alle diese Varianten lassen sich mit etwas Übung gleichwertig nutzen. Ungeübt ist es empfehlenswert, nahe an einer vertrauten Programmiersprache zu bleiben. Man sollte dann allerdings aufpassen, dass man auf den Einsatz von Sprachkonstrukten verzichtet, die es nur in bestimmten Programmiersprachen gibt (z.B. Lambda-Ausdrücke, Annotations, Dekorator, bestimmte Iterations- Bedingungsabkürzungen).

  • Auch der Einsatz von "gsprochener" Sprache ist möglich, d.h., die Beschreibung eines komplexen Ablaufs in Sätzen, wie z.B. "Iterative Berechnung von f(x) mit variabler Schrittweite"
5 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Wesentliche Eigenschaften von Pseudocode

Wesentliche Eigenschaften von Pseudocode

Wichtig bei der Erstellung von Pseudocode ist:

  • Verständlichkeit des Pseudocodes ist wichtiger als starre Konventionen!

  • Unnötige Details vermeiden: das Offensichtliche kann als bekannt vorausgesetzt werden!

  • Im Kontext bleiben: Wer ist Adressat und in welcher Problemdomäne befindet man sich? Wem beantworte man mit dem Pseudocode welche Frage?

  • Stimmige Abstraktionsgrade wählen: Baut der Abstraktionsgrad einer Operationen auf den Abstraktionsgrad des umgebenden Moduls auf? Das Single Layer of Abstraction (SLA)-Prinzip gilt auch für Pseudocode!

6 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Notationen für Algorithmen

Die derzeit verwendeten „halbformalen“ Mittel zur Beschreibung von Algorithmen benutzen die Grundelemente, die man in den meisten (höheren) Programmiersprachen findet. Dabei gibt es an C angelehnte verbale Beschreibungen (oft „Pseudocode“ genannt) und graphische Beschreibungen (Nassi-Shneiderman Diagramme oder Programmablaufpläne).

  • Wir legen fest: Jeder Algorithmus soll nur mit Hilfe der folgenden Bausteine konstruiert werden (Stichwort: „strukturierte Programmierung“).

Statt Jana wird rein prozedurales JavaScript als Notation verwendet.

7 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Sequenz

Die einzelnen Teilalgorithmen werden hintereinander in der Reihenfolge ausgeführt, in der sie aufgeschrieben sind:

Flussdiagramm

Struktugramm

Pseudonotation

i1; i2; i3
{ i1; i2; i3 }
{ 
  i1
  i2 
  i3 
}
8 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Verzweigung

Wenn die Bedingung B erfüllt ist, so wird der "ja-Teilalgorithmus“ ausgeführt, sonst (also wenn die Bedingung nicht erfüllt ist) der nein-Teilalgorithmus. Es werden nie beide Teilalgorithmen ausgeführt:

Flussdiagramm

Struktugramm

Pseudonotation

if (B) I1
if (B) I1 
  else I2
9 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Fallunterscheidung

Eine Spezialform der Verzweigung ist die Fallunterscheidung. Wenn die Auswertung des Ausdrucks A den Wert i ergibt, dann wird der Teilalgorithmus I ausgeführt. Wenn kein passender Teilalgorithmus I existiert, dann wird der Teilalgorithmus "default" ausgeführt:

Flussdiagramm

Struktugramm

Pseudonotation

switch (A) {
  case V1: I1
  case V2: I2
  default: I0
}
10 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Abweisende Schleife

Hier wird der Teilalgorithmus S (= Scheifenkörper / Schleifenrumpf) solange ausgeführt, wie die Bedingung B erfüllt ist. Der Name abweisende Schleife kommt daher, dass die Bedingung zu Beginn getestet und der Schleifenrumpf evtl. nicht ausgeführt wird:

Flussdiagramm

Struktugramm

Pseudonotation

while (B) {
  I
}
11 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Nichtabweisende Schleife

Hier wird erst der Teilalgorithmus S (= Scheifenkörper / Schleifenrumpf) ausgeführt und dann die Bedingung B geprüft. Damit ist auch die Bezeichnung nichtabweisende Schleife plausibel, denn der Teilalgorithmus S wird auf jeden Fall einmal ausgeführt:

Flussdiagramm

Struktugramm

Pseudonotation

do {
  I
} while (B)
12 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Zählschleife

Bei der Zählschleife wird der Schleifenindex i vom Startwert hin zum Endwert inkrementiert. Dabei wird der Teilalgorithmus S (= Scheifenkörper) jedesmal durchlaufen. Der Unterschied zur abweisenden und nichtabweisende Schleife ist, dass schon zu Beginn die Anzahl der Schleifendurchläufe fest steht:

Flussdiagramm

Struktugramm

Pseudonotation

for(i=a;i<=b;i=i+c) {
  I
}
13 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Funktion

Funktionen sind benannte Anweisungsblöcke mit Ein- und Ausgabeparametern:

Flussdiagramm

Struktugramm

Pseudonotation

function f (a,b,c) {
  I
  return d
}
X=f(V1,V2,V3)
14 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Notationen für Algorithmen

Datenstrukturen (Records)

Java

class Data {
  type1 el1;
  type2 el2;
  void Data(type1 v1,type2 v2,..) {
    el1=v1;
    el2=v2;
    ...
  }
  public foo() {
    this...
  }
  ...
}
Data data = new Data(v1,v2,..);
data.el1 = ..
.. = data.el2
data.foo(..)..
..

Pseudonotation

{
  el1:v1,
  el2:v2,
  ..
}
function Data(v1,v2) {
  return {
    el1:v1,
    el2:v2,
    ..
  }
}
function foo(data) {
}
data=Data(v1,v2,..)
data.el1 = .. ; .. =  data.el2 ..
15 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Beispiel Flussdiagramm und Struktugramm

Beispiel Flussdiagramm und Struktugramm

Max(A,B,C) Berechnung

16 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Beispiel Pseudonotation

Beispiel Pseudonotation

function max(a,b,c) {
  if (a>b) {
    if (a>c) return a
    else     return c
  } else if (a<b) {
    if (b>c) return b
    else     return c 
  }
}
print(max(10,34,12))
17 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Beispiel Ausführbar

Beispiel Ausführbar

+

18 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Beispiel Unübersichtlich

Beispiel Unübersichtlich

Struktugramme werden schnell unübersichtlich (ebenso Flussdiagramme)

19 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Mengen und Mengenoperationen

Mengen und Mengenoperationen

Häufig werden in der Algorithmik Mengen von Werten verarbeitet. Z.B. alle Elemente eines Arrays oder einer Liste. Hier bietet sich die Kurznotation der Mengenlehre (Mathematik) an.

Es ist sehr schwer den fundamentalen Begriff der Menge mathematisch exakt zu definieren. Aus diesem Grund soll uns hier die von Cantor im Jahr 1895 gegebene Erklärung genügen, da sie für unsere Zwecke völlig ausreichend ist:

(Georg Cantor) Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohl unterschiedenen Objekten m unsrer Anschauung oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen. Menge

Mengen sind immer ungeordnet, die Reihenfolge der Elemente spielt keine Rolle!

20 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Mengen und Mengenoperationen

Mengen und Mengenoperationen

Sei M eine beliebige Menge, dann ist

  • a ∈ M ⇒ a ist ein Element der Menge M ,
  • a ∉ M ⇒ a ist kein Element der Menge M ,
  • M ⊆ N ⇒ aus a ∈ M folgt a ∈ N (M ist Teilmenge von N),
  • M ⊈ N ⇒ es gilt nicht M ⊆ N. Gleichwertig: es gibt ein a ∈ M mit a ∉ N (M ist keine Teilmenge von N) und
  • M ⊂ N ⇒ es gilt M ⊆ N und M ≠ N (M ist echte Teilmenge von N )
21 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Definition spezieller Mengen

Definition spezieller Mengen

Spezielle Mengen können auf verschiedene Art und Weise definiert werden, wie z.B.

  • durch Angabe von Elementen: So ist {a1, ... , an} die Menge, die aus den Elementen a1, ... , an besteht, oder
  • durch eine Eigenschaft E: Dabei ist {a | E(a)} die Menge aller Elemente a, die die Eigenschaft E besitzen, z.B. a>0.

Mengen, die durch eine Eigenschaft E definiert sind:

  • {n | n ∈ N und n ist durch 3 teilbar}
  • {n | n ∈ N und n ist Primzahl und n ≤ 40}
  • ∅ =def {a | a ≠ a} (die leere Menge)
22 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Operationen auf Mengen

Operationen auf Mengen

Seien A und B beliebige Mengen, dann ist

  • A ∩ B =def {a | a ∈ A und a ∈ B} (Schnitt von A und B),
  • A ∪ B =def {a | a ∈ A oder a ∈ B} (Vereinigung von A und B),
  • A \ B =def {a | a ∈ A und a ⊈ B} (Differenz von A und B),
  • A =def M \ A (Komplement von A bezüglich einer festen Grundmenge M) und
  • P(A) =def {B | B ⊆ A} (Potenzmenge von A).

Zwei Mengen A und B mit A ∩ B = ∅ nennt man disjunkt.

23 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Elementare Logik

Elementare Logik

Auch Aussagenlogik findet Eingang in Pseudonotation und kann mit der Mengenlehre kombinierbar sein.

Aussagen sind entweder wahr (≜ 1) oder falsch (≜ 0).

Zusätzlich werden noch die Quantoren ∃ („es existiert“) und ∀ („für alle“) verwendet, die z.B. wie folgt gebraucht werden können

  • ∀x : P (x) bedeutet "Für alle x gilt die Aussage P(x)".
  • ∃x : P (x) bedeutet "Es existiert ein x, für das die Aussage P(x) gilt".

Üblicherweise lässt man sogar den Doppelpunkt weg und schreibt statt ∀x : P (x) vereinfachend ∀xP (x).

24 / 25

Stefan Bosse - Algorithmen und Datenstrukturen - Modul PN Darstellung von Algorithmen :: Iteratoren

Iteratoren

Iterationen über Mengen (oder Listen und Arrays) können ebenfalls in einer Pseudonotation mit "Für alle" Logikoperator ausgedrückt werden:

for (x in X) { ... } 
for (x of X) { ... }
for (x=1;x≤n;x++) { ... }
∀index(x) ∈ X do ...
∀x ∈ X do ...
∀x ∈ { 1,2,3,..,n } do ...
25 / 25