Algorithmus - Versionsgeschichte

Thomas: /* Laufzeit */

2026-02-20T10:47:12Z

Laufzeit

← Nächstältere Version		Version vom 20. Februar 2026, 12:47 Uhr
Zeile 60:		Zeile 60:
	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 [[Laufzeitanalyse\|Laufzeit]] eines [[Sortieren\|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.		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.

Thomas: /* Laufzeit */

2026-02-20T10:46:16Z

Laufzeit

← Nächstältere Version		Version vom 20. Februar 2026, 12:46 Uhr
Zeile 64:		Zeile 64:
	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.		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.

	Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität in der so genannten Laufzeitanalyse.		Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität in der so genannten [[Laufzeitanalyse]].

	== Beispiel ==		== Beispiel ==

Thomas am 29. September 2025 um 12:47 Uhr

2025-09-29T12:47:52Z

← Nächstältere Version		Version vom 29. September 2025, 14:47 Uhr
Zeile 96:		Zeile 96:
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_SDM]]		[[Kategorie:FI_I_SDM]]
			[[Kategorie:FI_I_TP1]]

Flbkwikiadmin am 6. September 2025 um 09:17 Uhr

2025-09-06T09:17:53Z

← Nächstältere Version		Version vom 6. September 2025, 11:17 Uhr
Zeile 93:		Zeile 93:
	</syntaxhighlight>		</syntaxhighlight>

	[[Kategorie:~~Informatik~~]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_SDM]]		[[Kategorie:FI_I_SDM]]

Flbkwikiadmin am 6. September 2025 um 08:54 Uhr

2025-09-06T08:54:26Z

← Nächstältere Version		Version vom 6. September 2025, 10:54 Uhr
Zeile 1:		Zeile 1:
	~~= Algorithmen =~~

	Ein '''Algorithmus''' ist in der Informatik ein genau beschriebenes Verfahren zur Lösung eines gegebenen Problems. Ein '''Programm''' stellt die Übersetzung eines Algorithmus in eine vom Computer begreifbare und ausführbare Folge von Befehlen dar, an dessen Ende die Lösung eines Problems ausgegeben wird.		Ein '''Algorithmus''' ist in der Informatik ein genau beschriebenes Verfahren zur Lösung eines gegebenen Problems. Ein '''Programm''' stellt die Übersetzung eines Algorithmus in eine vom Computer begreifbare und ausführbare Folge von Befehlen dar, an dessen Ende die Lösung eines Problems ausgegeben wird.

Flbkwikiadmin am 6. September 2025 um 08:53 Uhr

2025-09-06T08:53:59Z

← Nächstältere Version		Version vom 6. September 2025, 10:53 Uhr
Zeile 94:		Zeile 94:
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			[[Kategorie:Informatik]]
			[[Kategorie:AHR_I_Informatik_LK]]
			[[Kategorie:FI_I_SDM]]

Thomas am 5. September 2025 um 08:40 Uhr

2025-09-05T08:40:29Z

← Nächstältere Version		Version vom 5. September 2025, 10:40 Uhr
Zeile 9:		Zeile 9:
	== Einführung ==		== 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]]		[[Datei:Übersicht Algorithmus.png\|mini]]

Zeile 20:		Zeile 20:
	=== Spezifikation ===		=== 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 ====		==== Eingabespezifikation ====
Zeile 60:		Zeile 60:
	==== Laufzeit ====		==== 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.		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 ==		== 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:

Thomas am 29. April 2025 um 07:04 Uhr

2025-04-29T07:04:24Z

← Nächstältere Version		Version vom 29. April 2025, 09:04 Uhr
Zeile 62:		Zeile 62:
	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.		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.
	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.		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.

Thomas am 29. April 2025 um 07:04 Uhr

2025-04-29T07:04:04Z

← Nächstältere Version		Version vom 29. April 2025, 09:04 Uhr
Zeile 20:		Zeile 20:
	=== Spezifikation ===		=== Spezifikation ===

	Für Algorithmen werden Schnittstellenspezifikationen benötigt. Sie regeln die Ein- und Ausgabe des Algorithmus. In der 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 Methoden realisiert. Die Schnittstelle der Methoden muss in der so genannten Signatur beschrieben werden.

	==== Eingabespezifikation ====		==== Eingabespezifikation ====

	Es muss genau spezifiziert sein, welche Eingabegrößen erforderlich sind und welche Anforderungen diesen Größen genügen müssen, damit das Verfahren funktioniert. In der Java Programmierung wird die Eingabespezifikation durch so genannte Eingabeparameter definiert.		Es muss genau spezifiziert sein, welche Eingabegrößen erforderlich sind und welche Anforderungen diesen Größen genügen müssen, damit das Verfahren funktioniert. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung wird die Eingabespezifikation durch so genannte Eingabeparameter definiert.

	==== Ausgabespezifikation ====		==== Ausgabespezifikation ====

	Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit welchen Eigenschaften bestimmt werden. In der Java Programmierung wird die Ausgabespezifikation durch den so genannten Ausgabeparameter definiert.		Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit welchen Eigenschaften bestimmt werden. In der [https://de.wikipedia.org/wiki/Java_(Programmiersprache) Java] Programmierung wird die Ausgabespezifikation durch den so genannten Ausgabeparameter definiert.

	=== Durchführbarkeit ===		=== Durchführbarkeit ===
Zeile 42:		Zeile 42:
	==== Determinismus und Determiniertheit ====		==== Determinismus und Determiniertheit ====

	Wenn der Ablauf zu jedem Zeitpunkt fest vorgeschrieben ist, ist der Algorithmus deterministisch (Determinismus). Für zwei gleiche Eingabegrößen werden ~~jedesmal~~ exakt die gleichen Rechenschritt in der identischen Reihenfolge durchlaufen. Jeder deterministische Algorithmus ist auch determiniert (Determiniertheit). Der Algorithmus ist determiniert, wenn dieser stets für die gleiche Eingabegröße die gleiche Ausgabegröße liefert! Aber ein determinierter Algorithmus, muss nicht deterministisch sein. Denn determinierte Algorithmen können für gleiche Eingabegrößen jedes Mal auf unterschiedlichen Wegen zum Ziel kommen; liefern aber jedes Mal das gleiche Ergebnis!		Wenn der Ablauf zu jedem Zeitpunkt fest vorgeschrieben ist, ist der Algorithmus deterministisch (Determinismus). Für zwei gleiche Eingabegrößen werden jedes Mal exakt die gleichen Rechenschritt in der identischen Reihenfolge durchlaufen. Jeder deterministische Algorithmus ist auch determiniert (Determiniertheit). Der Algorithmus ist determiniert, wenn dieser stets für die gleiche Eingabegröße die gleiche Ausgabegröße liefert! Aber ein determinierter Algorithmus, muss nicht deterministisch sein. Denn determinierte Algorithmen können für gleiche Eingabegrößen jedes Mal auf unterschiedlichen Wegen zum Ziel kommen; liefern aber jedes Mal das gleiche Ergebnis!

	=== Korrektheit ===		=== Korrektheit ===

Thomas am 29. April 2025 um 07:02 Uhr

2025-04-29T07:02:53Z

← Nächstältere Version		Version vom 29. April 2025, 09:02 Uhr
Zeile 71:		Zeile 71:
	== Beispiel ==		== Beispiel ==

	Das folgende Beispiel zeigt einen Algorithmus in der Programmiersprache Java der z.B. Bücher in einem Regal sortiert:		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: