python:prog

Häufig begegnen uns Beschreibungen von Verfahren und Vorgängen:

ein Kochrezept
eine Bedienungsanleitung
ein mathematisches Verfahren

Der arabische Mathematiker Abu Ja’far Mohammed ibn Musa al-Khowarizmi hat solche, speziell mathematische Verfahren in der ersten Hälfte des 9. Jahrhunderts beschrieben. Deshalb nennt man solche Beschreibungen von Vorgängen auch Algorithmus.

Definition:

Eigenschaften eines Algorithmus

Endlichkeit: Ein Algorithmus besteht aus endlich vielen Anweisungen.
Eindeutigkeit: Mit einer Anweisung ist auch die nächste Anweisung festgelegt. Gleiche Eingabedaten müssen zu gleichen Ausgabedaten führen.
Ausführbarkeit: Alle Anweisungen eines Algorithmus müssen für den Ausführenden verständlich und damit ausführbar sein.
Allgemeingültigkeit: Ein Algorithmus muss alle Probleme einer bestimmten Problemklasse lösen.
Terminiertheit: Ein Algorithmus muss nach endlich vielen Schritten eine Lösung gefunden haben. (In der theoretischen Informatik verzichtet man häufig auf diese Eigenschaft und betrachtet auch Algorithmen, die nicht terminieren.)

Darstellungsformen von Algorithmen

Ein Beispiel

Ein berühmter Algorithmus ist der Euklidische Algorithmus, mit dem man den größten gemeinsamen Teiler zweier natürlicher Zahlen a und b ermitteln kann. Dieser Algorithmus wird hier (in der Differenzvariante) in den verschiedenen Darstellungsformen präsentiert:

Beschreibung mit Hilfe der Umgangssprache:
1. Wenn a gleich b ist, dann ist a der gesuchte größte gemeinsame Teiler und der Algorithmus bricht ab; sonst:
2. Wenn a kleiner als b ist, werden die Werte von a und b vertauscht.
3. Wenn a größer als b ist, bildet man die Differenz c von a und b. a ergibt sich aus dem Wert von b, b ergibt sich aus dem Wert von c.
4. Weiter bei 1!
verbale formalisierte Beschreibung:
- Solange a ungleich b ist wiederhole:
  - Wenn a < b, dann vertausche die Werte von a und b.
  - Berrechne c = a - b.
  - Gebe a den Wert von b und b den Wert von c.
  - Gebe ggT = a aus.
Struktogramm:

Auf die einzelnen Struktogrammelemente wird bei den algorithmischen Kontrollstrukturen noch genauer eingegangen.
Programmablaufplan (Flussdiagramm):

Diese Darstellungsform soll nur der Vollständigkeit halber erwähnt werden. Es wird nicht genauer darauf eingegangen.

Computerprogramm:

Hier ist der Algorithmus in der Programmiersprache Python dargestellt. Die einzelnen Elemente des Programms werden noch behandelt.

euklid.py

a = int(input("a = "))
b = int(input("b = "))
while a != b:
    if a < b:
        c = a
        a = b
        b = c
    c = a - b
    a = b
    b = c
print("ggT:",a)

Algorithmischen Grundstrukturen

Computerprogramme und Programmiersprachen

Einteilung von Programmiersprachen

Einteilung nach historischer Entwicklung

Bei Machinensprachen (Programmiersprachen der 1. Generation) wird das Computerprogramm direkt in einer für den Prozessor des Computers ausführbaren Form (als duale oder hexadezimale Zahlen) eingegeben. Das Programm ist dann direkt ausführbar.
Bei Assemblersprachen (Programmiersprachen der 2. Generation) wird das Programm in einem sogenannten mnemonischen Code mit einem Texteditor erstellt. Die verwendeten Befehle entsprechen dem Befehlsvorrat einer bestimmten Prozessorarchitektur. Sie werden dann mit einem Programm, dem Assembler, in Maschinencode übersetzt.
Bei höheren Programmiersprachen (Programmiersprachen der 2. Generation) wird der Programmquelltext in einer für Menschen gut lesbaren Form in eine Textdatei geschrieben. Diese Datei kann dann auf verschiedene Arten (Siehe unten!) in eine für den Prozessor (Maschinencode) Form übersetzt.

Einteilung höherer Programmiersprachen nach der Art der Übersetzung

Compilersprachen: Hier übersetzt der Compiler zunächst das Programm in Maschinencode. Danach kann die Maschinencodedatei vom Computer ausgeführt werden. (z.B. C, C++, Delphi)
Interpretersprachen: Die Quelltextdatei wird zusammen dem Interpreter aufgerufen. Der Interpreter übersetzt jetzt den ersten Befehl in Maschinencode und führt ihn aus. Danach wird der nächste Befehl übersetzt und ausgeführt, usw., bis die gesamte Datei abgearbeitet ist. (z.B. Perl, Python, JavaScript)
Mischtypen Bei einigen Programmiersprachen (z.B. Java, C#) wird der Quelltext zunächst von einem Compiler in einen Zwischencode (Bytecode) übersetzt. Dieser Bytecode wird dann von einem Interpreter im jeweiligen Betriebssystem ausgeführt.
Bei einigen Interpretersprachen (z.B. Python) werden Bibliotheken von einem Precompiler zunächst in einen Zwischencode übersetzt, bevor die eigentliche Programmdatei vom Interpreter ausgeführt wird.

Einteilung höherer Programmiersprachen nach dem Programmierparadigma

Die folgende Übersicht zeigt eine mögliche Einteilung von Programmiersprachen nach ihrem Programmierparadigma. ³⁾

Imperative Sprachen bestehen aus einer Folge Befehlen die vom Computer nacheinander ausgeführt werden. man kann sie einteilen in:
- Prozedurale Sprachen: Das Programm besteht aus Anweisungen und algorithmischen Grundstrukturen. Das Gesamtproblem kann durch Prozeduren in kleinere Teilprobleme zerlegt werden. (Typische Vertreter: C, Turbo Pascal)
- Objektorientierte Sprachen: Das Programm besteht aus Objekten mit Attributen und Methoden. Für diese Objekte werden Klassen als Vorlagen definiert. (Typische Vertreter: Java C#)
Bei deklarativen Sprachen wird ein Problem und die Beziehungen zwischen den Teilproblemen beschrieben. In dieser Beschreibung steckt das Wissen zur Lösung des Problems. Man kann diese Sprachen einteilen in:
- Funktionale Sprachen: Das Programm besteht aus aufeinander bezogenen Funktionsdefinitionen. Es wird gestartet durch Funktionsaufrufe mit bestimmten Eingabedaten. Diese Eingabedaten werden durch Funktionsaufrufe in Ausgabedaten umgewandelt. (Typischer Vertrter: Haskell)
- Logische Sprachen: Das Programm besteht aus einer Niederschrift von Fakten und Regeln, wie aus den Fakten neue Fakten gewonnen werden können. Bei der Programmausführung werden Anfragen an das Programm gestellt die bestimmte Probleme, z.B. einen Beweis, lösen können. (z.B. Prolog)

Durch viele Programmiersprachen können mehrere Paradigmen umgesetzt werden. Eine kleine Übersicht gibt die nachfolgende Tabelle:

Sprache	prozedural	objektorientiert	funktional	logisch
C	X
C++	X	X
Java		X
Perl	X	X
Python	X	X	X
Haskell			X
Prolog				X

>> Workshop: Erstellen von Programmen in verschiedenen Programmiersprachen

¹⁾

Engelmann, Lutz (Hrsg.): Duden Informatik Lehrbuch S II, DUDEN PAETEC GmbH, Berlin 2006, S.30

²⁾

ebenda, S. 38

³⁾

ebenda

Inhaltsverzeichnis

Algorithmen und ihre Grundstrukturen