Algorithmus: Definition, Beispiele, Turing-Maschine, Berechenbarkeit

Was ist ein Algorithmus?

Ein Algorithmus ist eine endliche, wohl definierte Folge von genauen Anweisungen, die eine Aufgabe löst. Ausgehend von einem gegebenen Anfangszustand führt der Algorithmus eine Reihe von Schritten aus und erreicht in erkennbarer endlicher Zeit einen Endzustand.

Was ist die Ausführungsreihenfolge eines Algorithmus?

Die Reihenfolge der Ausführung ist für die Funktion eines Algorithmus meist entscheidend. Allgemein wird angenommen, dass die Anweisungen explizit angegeben sind und in einer bestimmten Reihenfolge, typischerweise von oben nach unten, abgearbeitet werden.

Geben Sie Beispiele für Algorithmen

• Lehralgorithmen (z. B. Beispiele in Lehrbüchern)
• Euklids Algorithmus zur Berechnung des größten gemeinsamen Teilers (ggT) zweier positiver ganzer Zahlen
• Gaußsches Verfahren zur Lösung eines linearen Gleichungssystems

Wem wird die Entwicklung des digitalen Computers zugeschrieben und warum?

Alan Mathison Turing (1912–1954), ein bedeutender britischer Mathematiker und Logiker, entwickelte das theoretische Modell der Turing-Maschine. Dieses Modell ist grundlegend für die formale Auffassung des Rechnens. Zu seinen Ehren trägt das Modell seinen Namen: die Turing-Maschine.

Was macht die Turing-Maschine?

Eine Turing-Maschine arbeitet mit einem Band, auf dem sich eine lineare Folge von Symbolen befindet. Zu jedem Zeitpunkt kann die Maschine genau ein Bandzeichen lesen, einen Schritt ausführen (z. B. Schreiben, Bewegen des Lesekopfs) und ihren Zustand gemäß einer Übergangstabelle ändern.

Welche Aktionen kann eine Turing-Maschine durchführen?

• Ein Symbol lesen
• Ein Symbol schreiben oder überschreiben
• Den Lesekopf nach links oder rechts bewegen
• Den Zustand innerhalb einer endlichen Menge von Zuständen ändern

Wie gibt man einen Algorithmus an?

Um einen Algorithmus so anzugeben, dass er implementierbar ist, definiert man Eingaben und Ausgaben sowie die notwendigen Voraussetzungen (Preconditions) und Nachbedingungen (Postconditions). Die Beschreibung kann in unterschiedlichen Sprachen und Notationen erfolgen, etwa in natürlicher Sprache, Pseudocode oder Programmiersprachen.

8) Wie ist die Geschichte des Algorithmus?

Der Begriff leitet sich vom Namen des persischen Mathematikers Muhammad ibn Musa al-Chwarizmi (al-Khwarizmi) ab. Seine Arbeiten trugen zur Vereinfachung arithmetischer Verfahren bei und beschrieben Rechenregeln. Das lateinisierte Wort algorismus bzw. algorithmus entwickelte sich im Laufe der Zeit zu dem heutigen Begriff "Algorithmus" und umfasst inzwischen alle endlichen Verfahren zur Lösung von Problemen.

9) Welche Anforderungen an einen Algorithmus gibt es?

Wichtige Eigenschaften eines Algorithmus sind:

• Endlichkeit: Der Algorithmus muss nach endlich vielen Schritten abbrechen.
• Präzision: Jeder Schritt muss eindeutig und genau definiert sein.
• Eingabe: Ein Algorithmus hat null oder mehrere Eingaben.
• Ausgabe: Ein Algorithmus liefert eine oder mehrere Ausgaben.
• Effektivität: Alle Operationen müssen praktisch ausführbar sein (z. B. mit Stift und Papier in endlicher Zeit).

10) Was bedeutet Endlichkeit?

Ein Algorithmus muss immer terminiert werden, das heißt nach einer endlichen Anzahl einfacher Schritte zum Halt kommen.

11) Was bedeutet Präzision?

Jeder Schritt eines Algorithmus muss so präzise formuliert sein, dass die auszuführenden Operationen in jeder Situation eindeutig sind.

12) Was bedeutet Eingabe?

Ein Algorithmus hat null oder mehrere Eingaben: die Werte oder Daten, die dem Algorithmus vor Beginn oder während seiner Ausführung gegeben werden. Diese Eingaben stammen aus bestimmten Mengen von Objekten.

13) Was ist der Ausgang (Ausgabe)?

Ein Algorithmus besitzt eine oder mehrere Ausgaben: die Mengen von Werten, die als Ergebnis der Verarbeitung der Eingaben erzeugt werden.

14) Was bedeutet Wirksamkeit?

Wirksamkeit bedeutet, dass alle im Algorithmus verwendeten Operationen so grundlegend sind, dass sie in endlicher Zeit von einem Menschen mit Stift und Papier ausgeführt werden können.

15) Wie wird eine Berechnung formalisiert?

Da die Menge der endlichen Anweisungen abzählbar ist und jede ganze Zahl durch eine endliche Folge natürlicher Zahlen darstellbar ist, berechnen im Wesentlichen alle Algorithmen Funktionen über natürlichen Zahlen. Formal berechnet ein Algorithmus eine Funktion, die von natürlichen Zahlen in natürliche Zahlen abbildet.

16) Wie nennt man Funktionen, die durch einen Algorithmus berechnet werden?

Solche Funktionen heißen berechenbar. Man unterscheidet teilweise berechenbare (partiell berechenbare) und total berechenbare (vollständig berechenbare) Funktionen, je nachdem, ob die Funktion für alle Eingabewerte definiert ist oder nur für einige.

17) Was sind teilweise berechenbare Funktionen?

Eine Funktion ist teilweise berechenbar, wenn es einen Algorithmus gibt, der für Eingabewerte aus dem Definitionsbereich in endlicher Zeit ein Ergebnis liefert, für Eingabewerte außerhalb des Definitionsbereichs jedoch nicht terminiert (d. h. unendlich lange läuft).

18) Was sind völlig (total) berechenbare Funktionen?

Eine Funktion ist total berechenbar, wenn ein Algorithmus für jeden möglichen Eingabewert in endlicher Zeit ein Ergebnis liefert. Jeder Algorithmus, der für alle Eingaben terminiert, berechnet eine totale Funktion.

19) In welchen Formen kann man Algorithmen ausdrücken?

Algorithmen können in natürlicher Sprache, in Pseudocode, als Flussdiagramm oder in Programmiersprachen dargestellt werden.

20) Welche Beschreibungsebenen eines Algorithmus gibt es?

Man unterscheidet drei Ebenen:

• Hochlevel-Beschreibung: Formulierung des Problems, Auswahl eines mathematischen Modells, verbale Beschreibung des Algorithmus mit möglichen Abbildungen und Auslassung technischer Details.
• Formale Beschreibung: Ausführlichere Darstellung (z. B. Pseudocode), die die Abfolge von Schritten für die Lösung beschreibt.
• Implementation: Umsetzung des Algorithmus in einer Programmiersprache, die getestet und ausgeführt werden kann.

22) Was ist ein Flussdiagramm?

Ein Flussdiagramm ist eine grafische Darstellung eines Algorithmus oder eines Teils davon, in der Abläufe durch Symbole und Verbindungen visualisiert werden.

23) Welche Symbole gibt es im Flussdiagramm?

Typische Symbole sind: Terminal (Start/Ende), Prozess (Anweisung), Entscheidungsfeld (Bedingung), Ein- und Ausgabe sowie Flusslinien zur Verbindung der Elemente.

24) Was ist Pseudocode?

Pseudocode ist eine künstliche, informelle Sprache, die dazu dient, Algorithmen für Programmierer verständlich und unabhängig von einer konkreten Programmiersprache darzustellen.

25) Welche Arten von Algorithmen gibt es hinsichtlich ihrer Funktion?

Beispiele für Algorithmentypen sind Sortieralgorithmen und Suchalgorithmen.

26) Wofür ist ein Sortieralgorithmus verantwortlich?

Ein Sortieralgorithmus ordnet die Elemente einer Liste oder eines Vektors in eine bestimmte Reihenfolge.

27) Welche Ordnungsrelationen werden verwendet?

Man verwendet numerische Ordnung, lexikographische Reihenfolge oder andere definierte Ordnungsrelationen.

28) Wie kann man Sortieralgorithmen klassifizieren?

Sortieralgorithmen lassen sich u. a. klassifizieren nach:

• Intern (Arbeiten im Hauptspeicher)
• Extern (Arbeiten mit externen Speichermedien, z. B. Festplatten)
• Besteingefährdung: adaptiv, wenn die Eingabe bereits teilweise sortiert ist
• Worst-Case: Verhalten bei umgekehrt sortierter Eingabe
• Stabilität: Erhält die relative Reihenfolge gleichwertiger Elemente oder nicht

29) Zusammenfassung der Klassifikation von Sortieralgorithmen

Interne vs. externe Sortierung, adaptive vs. nicht adaptive Algorithmen sowie stabile vs. instabile Verfahren sind gängige Unterscheidungen.

30) Was ist ein Suchalgorithmus?

Ein Suchalgorithmus ist so konzipiert, dass er ein bestimmtes Element innerhalb einer Datenstruktur auffindet.

31) Nennen Sie einige algorithmische Techniken

Typische Techniken sind:

• Greedy-Algorithmen (gierig)
• Parallele Algorithmen
• Probabilistische und nichtdeterministische Algorithmen
• Divide and Conquer (Teile und Herrsche)
• Metaheuristiken
• Dynamische Programmierung
• Backtracking (Zurückverfolgen)

32) Welcher Algorithmustyp verhält sich linear?

Deterministische Algorithmen können eine lineare Laufzeit haben, je nach Arbeitsaufwand in Bezug auf die Eingabegröße.

33) Wie funktioniert Divide and Conquer?

Die Methode teilt das Problem in disjunkte Teilprobleme, löst jedes Teilproblem rekursiv und kombiniert die Teillösungen zu einer Gesamtlösung.

34) Wie arbeitet ein Branch-and-Bound-Algorithmus?

Branch-and-Bound basiert auf dem impliziten Erzeugen von Lösungen in einem Suchbaum und auf gezielter, kontrollierter Rückverfolgung (Pruning), um die besten Lösungen zu ermitteln.

35) Wann wählt man die vielversprechendsten Elemente aus?

Das Prinzip der Wahl des jeweils vielversprechendsten Elements wird bei greedy (gierigen) Algorithmen angewandt.

36) Was leisten metaheuristische Algorithmen?

Metaheuristiken liefern meist approximative Lösungen für Optimierungsprobleme, oft ohne Garantie auf optimale Lösungsfindung, aber mit guter Praxisnähe und Flexibilität.

37) Welcher Algorithmus tauscht Zeit gegen Raum?

Beispiele sind dynamische Programmierung und Memoisierung, bei denen mehr Speicheraufwand verwendet wird, um die Laufzeit zu reduzieren.

38) Welche Maße gibt es zur Bewertung der Effizienz von Algorithmen?

Man betrachtet vor allem Ressourcen wie Laufzeit (Zeitkomplexität) und Speicherverbrauch (Speicherkomplexität).

39) Was untersucht die Analyse von Algorithmen?

Die Analyse von Algorithmen ermittelt, wie sich Aufwand an Zeit und Speicher in Funktion der Eingabegröße entwickelt, etwa mittels asymptotischer Notation (O, Θ, Ω).

40) Wie kann man einen Algorithmus ausdrücken oder kodieren?

Algorithmen lassen sich in Pseudocode beschreiben, in einfacher natürlicher Sprache oder direkt in Programmiersprachen. Pseudocode dient häufig als Zwischenschritt, der dann in konkrete Programmiersprachen umgesetzt wird.