Algorithmus: Unterschied zwischen den Versionen

Zeile 9:

== Einführung ==

Zwei oft zu bewältigende Probleme in der Informatik sind das Suchen und das Sortieren von Objekten. Allerdings sind Algorithmen für Computer heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen.

Zwei oft zu bewältigende Probleme in der Informatik sind das [[Suchen]] und das [[Sortieren]] von [[Objekt|Objekten]]. Allerdings sind Algorithmen für Computer heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen.

Die Lösung komplexer Probleme sollte zuvor designed werden. Hierzu können Algorithmen vor der eigentlichen Programmierung in Ablaufplänen z.B. durch Modelle der UML oder Struktogramme visualisiert werden. Algorithmen werden in der Programmierung durch Kontrollstrukturen oder Rekursion implementiert.

Die Lösung komplexer Probleme sollte zuvor designed werden. Hierzu können Algorithmen vor der eigentlichen Programmierung in Ablaufplänen z.B. durch Modelle der [[UML]] oder [[Struktogramm|Struktogramme]] visualisiert werden. Algorithmen werden in der Programmierung durch [[Kontrollstruktur|Kontrollstrukturen]] oder [[Rekursion]] implementiert.

[[Datei:Übersicht Algorithmus.png|mini]]

Zeile 20:

=== Spezifikation ===

Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung werden Algorithmen mit Methoden realisiert. Die Schnittstelle der Methoden muss in der so genannten Signatur beschrieben werden.

Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung werden Algorithmen mit [[Methode|Methoden]] realisiert. Die Schnittstelle der Methoden muss in der so genannten [[Methodensignatur|Signatur]] beschrieben werden.

==== Eingabespezifikation ====

Zeile 60:

==== Laufzeit ====

Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die Laufzeit des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.

Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die [[Laufzeit]] des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.

Beispiel: Die Laufzeit eines Sortieralgorithmus ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5.

Beispiel: Die [[Laufzeit]] eines [[Sortieralgorithmus]] ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5.

Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge. Eine vorsortierte Liste stellt das Best Case Szenario dar. Also den günstigsten Fall für das gegebene Problem (hier das Sortieren von Zahlen). Eine sortierte Liste in umgekehrter Reihenfolge stellt das Worst Case Szenario dar. Hier ist der Aufwand am größten die Liste umzusortieren.

Zeile 70:

== Beispiel ==

Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache [~~https://de.wikipedia.org/wiki/Java_(Programmiersprache)~~ Java] der z.B. Bücher in einem Regal sortiert:

Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache [[Java]] der z.B. Bücher in einem Regal sortiert:

@@ Zeile 9: / Zeile 9: @@
 == Einführung ==
-Zwei oft zu bewältigende Probleme in der Informatik sind das Suchen und das Sortieren von Objekten. Allerdings sind Algorithmen für Computer heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen.
+Zwei oft zu bewältigende Probleme in der Informatik sind das [[Suchen]] und das [[Sortieren]] von [[Objekt|Objekten]]. Allerdings sind Algorithmen für Computer heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen.
-Die Lösung komplexer Probleme sollte zuvor designed werden. Hierzu können Algorithmen vor der eigentlichen Programmierung in Ablaufplänen z.B. durch Modelle der UML oder Struktogramme visualisiert werden. Algorithmen werden in der Programmierung durch Kontrollstrukturen oder Rekursion implementiert.
+Die Lösung komplexer Probleme sollte zuvor designed werden. Hierzu können Algorithmen vor der eigentlichen Programmierung in Ablaufplänen z.B. durch Modelle der [[UML]] oder [[Struktogramm|Struktogramme]] visualisiert werden. Algorithmen werden in der Programmierung durch [[Kontrollstruktur|Kontrollstrukturen]] oder [[Rekursion]] implementiert.
 [[Datei:Übersicht Algorithmus.png|mini]]
@@ Zeile 20: / Zeile 20: @@
 === Spezifikation ===
-Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung werden Algorithmen mit Methoden realisiert. Die Schnittstelle der Methoden muss in der so genannten Signatur beschrieben werden.
+Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung werden Algorithmen mit [[Methode|Methoden]] realisiert. Die Schnittstelle der Methoden muss in der so genannten [[Methodensignatur|Signatur]] beschrieben werden.
 ==== Eingabespezifikation ====
@@ Zeile 60: / Zeile 60: @@
 ==== Laufzeit ====
-Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die Laufzeit des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.
+Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die [[Laufzeit]] des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.
-Beispiel: Die Laufzeit eines Sortieralgorithmus ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5.
+Beispiel: Die [[Laufzeit]] eines [[Sortieralgorithmus]] ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5.
 Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge. Eine vorsortierte Liste stellt das Best Case Szenario dar. Also den günstigsten Fall für das gegebene Problem (hier das Sortieren von Zahlen). Eine sortierte Liste in umgekehrter Reihenfolge stellt das Worst Case Szenario dar. Hier ist der Aufwand am größten die Liste umzusortieren.
@@ Zeile 70: / Zeile 70: @@
 == Beispiel ==
-Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] der z.B. Bücher in einem Regal sortiert:
+Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache [[Java]] der z.B. Bücher in einem Regal sortiert: