Algorithmen

Ein Algorithmus ist eine genaue Vorschrift, nach der ein gewisses System von Operationen in einer bestimmten Reihenfolge auszuführen ist und mit der man alle Aufgaben eines gegebenen Typs lösen kann. 

eine genaue Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen 

sind abstrakt, d.h. sprach- und maschinenunabhängig

mit Hilfe von Pseudocode formuliert

Leistungsmerkmale 

--> Rechenzeitaufwand / Laufzeit 

--> Speicherplatzaufwand im Zwischenspeicher 

--> Verständlichkeit (Klarheit) und Wartbarkeit 

--> leichte Verifizierbarkeit der Korrektheit 

--> leichte Implementierbarkeit 

--> Exaktheit

1. Die Reihe wird in aufsteigender Richtung durchlaufen 
2. Es werden immer zwei benachbarte Elemente betrachtet 
3. Wenn sie in falscher Ordnung stehen, werden sie vertauscht
4. Das letzte Element des vorherigen Durchlaufs muss nicht betrachtet werden, da es seine endgültige Position hat
5. Der Schritt wird solange wiederholt, bis die Reihe sortiert ist
6. Das größte Element gelangt nach dem ersten Durchlauf ans Ende

Für die formale Darstellung eines Algorithmus ist eine Menge von Elementaroperationen zu definieren, die vom jeweiligen Anwender verstanden und ausgeführt werden können.

Auf die Objekte soll mit Hilfe der Handlung eine Wirkung ausgeübt werden. Diese können abstrakter oder konkreter Natur sein.
 

Beteiligte Objekte werden „computerverständlich“ formuliert, indem man ihre Eigenschaften/Attribute durch Daten beschreibt.
 

Algorithmen werden mit Hilfe einer speziellen Beschreibungssprache für Algorithmen (Algorithm Definition Language, ADL), auch Pseudocode genannt, formuliert.

Die ADL beschränkt sich auf essenzielle Sprachkonstrukte und ähnelt natürlichen Sprachen 

Pseudocode kann textuell oder graphisch dargestellt werden
 

1. Formale Beschreibung der Problemstellung und Randbedingungen
2. Formulierung eines Algorithmus mit Hilfe der zur Verfügung stehenden Elementaroperationen
3. Der allgemein beschriebene Algorithmus wird durch die Implementierung in eine für den Rechner verständliche und ausführbare „Sprache“ übersetzt.

Sie beziehen sich ausschließlich auf den betrachteten Algorithmus, nicht jedoch auf das Problem oder dessen Spezifikation.

Beispiele:

Endlichkeit 

Determiniertheit/Determinismus 

Terminiertheit 

Parallelität

Sie sind dagegen für einen Algorithmus in Bezug auf die entsprechende Spezifikation erklärt.

Beispiele:

Korrektheit 

Effizienz

Ein Algorithmus muss endlich beschreibbar sein. Das heißt, er muss durch einen endlichen Text formulierbar sein.
 

• Die Bedingung der Endlichkeit bezieht sich auf die Beschreibung eines Algorithmus, nicht auf seine Ausführung.

• Die Beschreibung besteht aus endlich vielen elementaren Operationen.

Ein Algorithmus ist terminierend, wenn er für jede erlaubte Eingabe nach einer endlichen Zahl von Schritten zu einem Ergebnis kommt.
 

• Ein Algorithmus muss nach endlicher Zeit seine Aufgabe vollbringen oder kontrolliert enden.

• Jedoch kann die tatsächliche Zahl der ausgeführten Schritte dabei beliebig groß sein. 

• Im Allgemeinen ist es für jeden beliebigen Algorithmus nicht möglich zu entscheiden, ob dieser terminiert oder nicht. Viele Algorithmen sind zu komplex, als dass sie sich durch ein mathematisches Regelsystem beschreiben lassen. 

Ein Algorithmus ist determiniert, wenn er bei gleichen Parametern und Startwert stets das gleiche Resultat liefert.
 

• Durch die Eigenschaft der Determiniertheit wird die eindeutige Abhängigkeit der Ausgabedaten von den Eingabedaten gewährleistet. Somit ist es möglich Funktionen algorithmisch zu beschreiben. 

• Ein Algorithmus ist nicht determiniert, wenn gleiche Parameter und Startwerte zu unterschiedlichen Ergebnissen (Ausgaben) führen. Dies ist z.B. der Fall, wenn das Ergebnis (die Ausgabe) vom Zufall abhängt.
   

Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Ausführung maximal eine Möglichkeit der Programmfortsetzung existiert. 

• Das bedeutet, dass das Ergebnis jeder einzelnen Anweisung eindeutig ist und an jeder Stelle des Ablaufs feststeht, welcher Schritt als nächster auszuführen ist. Dadurch muss ein deterministischer Algorithmus zwingend determiniert sein. 

Ein Algorithmus heißt parallel, wenn er so in Teilaufgaben aufgeteilt ist, dass diese gleichzeitig durch verschiedene Prozessoren ausgeführt werden können. 

• Ein Prozessor(-kern) erlaubt nur das streng sequentielle Ausführen von Elementaroperationen. 
•  
• Mehrere Prozessoren oder Mehrkernprozessoren erlauben eventuell das gleichzeitige Ausführen verschiedener Teile eines Algorithmus.
   

Die Komplexität eines Algorithmus bezeichnet seinen maximalen Ressourcenbedarf (z.B. Rechenzeit, Speicherplatz). 

• Jede Elementaroperation (Zuweisung, Addition, Subtraktion, Multiplikation, Vergleich zweier Zahlen, etc.) benötigt genau einen Rechenschritt. 
• Aufwendige Operationen (z.B. Matrizenmultiplikation) werden nicht betrachtet, da diese auf Elementaroperationen zurückführbar sind. 
• Die Daten werden in einer einheitlichen Größe betrachtet. Das heißt, eine Speicherzelle fasst immer genau ein Datum.

1. Entwurf eines groben Algorithmus mit abstrakten Operationen und Datentypen.

2. Verfeinerung der im ersten Schritt benutzten Operationen. Das heißt Implementierung mit weniger abstrakten Operationen und Datentypen.

3. Wiederholung des Verfeinerungsschritts, bis man einen Algorithmus erhält, der nur die zur Verfügung stehenden Ablaufstrukturen und Elementaroperationen enthält.