Grundlagen und Konzepte von Algorithmen

Was ist ein Algorithmus?

Ein Algorithmus ist eine endliche Menge von präzisen Anweisungen, die eine Aufgabe lösen, indem sie von einem Anfangszustand zu einem erkennbaren Endzustand übergehen.

Wie ist die Reihenfolge der Ausführung eines Algorithmus?

Die Reihenfolge der Ausführung ist fast immer entscheidend für den Ablauf. Im Allgemeinen wird davon ausgegangen, dass die Anweisungen explizit aufgeführt sind und von oben nach unten ausgeführt werden.

Nennen Sie Beispiele für Algorithmen?

• Lehrbücher (Handbücher)
• Euklids Algorithmus zur Berechnung des größten gemeinsamen Teilers (ggT) von zwei positiven ganzen Zahlen.
• Gauß-Verfahren zur Lösung linearer Gleichungssysteme.

Was ist eine Turing-Maschine?

Es ist ein Roboter, der sich auf einer linearen Abfolge von Daten bewegt. In jedem Augenblick kann die Maschine ein einzelnes Datum (in der Regel ein Zeichen) lesen und bestimmte Maßnahmen gemäß einer Tabelle durchführen, die den aktuellen Zustand (intern) und das zuletzt gelesene Datum berücksichtigt.

Welche Aktionen kann eine Turing-Maschine ausführen?

Sie kann neue Daten auf das Band schreiben, das Band in beide Richtungen bewegen und ihren internen Zustand ändern (aus einer endlichen Menge von Zuständen).

Wie definiert man einen Algorithmus?

Um einen Algorithmus so anzugeben, dass die Implementierung korrekt ist (d.h. genau das tut, was von ihm erwartet wird) und dass er wiederum mit verschiedenen Sprachen oder Werkzeugen umgesetzt werden kann, besteht eine Methode darin, seine Ein- und Ausgänge sowie die entsprechenden Vor- und Nachbedingungen festzulegen.

Was ist die Geschichte des Begriffs "Algorithmus"?

Der Name stammt vom Mathematiker Muhammad ibn Musa al-Chwarizmi. Seine Aufgabe war es, mathematische Konzepte zu vereinfachen, damit sie von mehr Menschen verstanden und angewendet werden konnten. Er erörterte auch Möglichkeiten zur Reduzierung von Rechenoperationen. Daher stammt das Wort "Algorithmus".

Was sind die wesentlichen Eigenschaften eines Algorithmus?

Der Informatiker Donald Knuth nannte folgende wesentliche Eigenschaften: Endlichkeit, Genauigkeit, Input, Output und Effizienz.

Was bedeutet Endlichkeit?

Ein Algorithmus muss immer nach einer endlichen Anzahl von Schritten terminieren (enden).

Was bedeutet Genauigkeit?

Jeder Schritt eines Algorithmus muss präzise definiert sein. Die durchzuführenden Operationen müssen in jedem Fall streng und eindeutig angegeben werden.

Was bedeutet Input (Eingabe)?

Ein Algorithmus hat null oder mehr Inputs (Eingaben): Die Mengen, die vor Beginn des Algorithmus oder dynamisch während des Algorithmus gegeben sind. Diese Inputs stammen aus bestimmten Mengen von Objekten.

Was bedeutet Output (Ausgabe)?

Ein Algorithmus verfügt über einen oder mehr Outputs (Ausgaben): Mengen, die in einer besonderen Beziehung zum Input stehen.

Was bedeutet Effizienz?

Es wird auch erwartet, dass ein Algorithmus hinreichend effizient ist, in dem Sinne, dass alle grundlegenden Operationen, die in einem Algorithmus durchgeführt werden, im Prinzip genau und in endlicher Zeit von einem Menschen mit Stift und Papier ausgeführt werden könnten.

Was kann ein Algorithmus berechnen?

Da jede endliche Menge abzählbar ist und jede ganze Zahl im Hinblick auf die Menge der natürlichen Zahlen ausgedrückt werden kann (unendlich, aber abzählbar; tatsächlich gibt es auch überabzählbare Mengen), berechnet ein Algorithmus im Wesentlichen Funktionen im Sinne von natürlichen Zahlen.

Wie nennt man Funktionen, die mit einem Algorithmus berechenbar sind?

Solche Funktionen nennt man berechenbar (partiell berechenbar oder total berechenbar, abhängig vom Definitionsbereich der Funktion).

Was sind partiell berechenbare Funktionen?

Eine Funktion ist partiell berechenbar, wenn sie für alle natürlichen Zahlen, die zu ihrem Definitionsbereich gehören (d.h. für die die Funktion definiert ist), ein Ergebnis in endlicher Zeit liefert, aber für Zahlen außerhalb ihres Definitionsbereichs nicht terminiert (kein Ergebnis liefert).

Was sind total berechenbare Funktionen?

Eine total berechenbare Funktion liefert immer ein Ergebnis für jeden Wert aus ihrem Definitionsbereich. Wie partielle Funktionen muss sie genau den Wert zurückgeben, der von der Funktion berechnet wird.

Wie können Algorithmen ausgedrückt werden?

• Natürliche Sprache
• Pseudocode
• Flussdiagramme
• Programmiersprachen

Was sind die Beschreibungsebenen eines Algorithmus?

• Beschreibung auf hoher Ebene
• Formale Beschreibung
• Implementierung

Erläutern Sie die Beschreibungsebenen.

Beschreibung auf hoher Ebene:

Das Problem wird festgelegt, ein mathematisches Modell und ein Algorithmus werden ausgewählt. Der Algorithmus wird mündlich erklärt, möglicherweise mit Abbildungen, wobei Details ausgelassen werden können.

Formale Beschreibung:

Pseudocode wird verwendet, um die Reihenfolge der Schritte zur Lösung des Problems zu beschreiben.

Implementierung:

Der Algorithmus wird in einer bestimmten Programmiersprache oder für ein beliebiges Objekt, das Anweisungen ausführen kann, ausgedrückt.

Was ist ein Flussdiagramm?

Ein Flussdiagramm ist eine grafische Darstellung eines Algorithmus oder eines Teils davon.

Nennen Sie Symbole für Flussdiagramme.

• Terminal (Start/Ende)
• Prozess
• Entscheidung
• Input/Output
• Verbindungslinie (Flusslinie)

Was ist Pseudocode?

Pseudocode ist eine künstliche und informelle Sprache, die Programmierern hilft, Algorithmen zu entwickeln.

Welche Arten von Algorithmen gibt es nach ihrer Funktion?

• Sortieralgorithmen
• Suchalgorithmen

Was ist ein Sortieralgorithmus?

Ein Algorithmus, der Elemente einer Liste oder eines Vektors in eine bestimmte Reihenfolge bringt, basierend auf einem Vergleichskriterium.

Welche Vergleichskriterien werden am häufigsten verwendet?

Am häufigsten sind die natürliche Ordnung und die lexikographische Ordnung.

Wie kann man Sortieralgorithmen klassifizieren?

Die häufigste Klassifizierung erfolgt nach dem Ort, an dem die Sortierung durchgeführt wird:

• a. Interne Sortieralgorithmen: Sortieren im Arbeitsspeicher des Computers.
• b. Externe Sortieralgorithmen: Sortieren auf externen Speichermedien wie einer Festplatte.

Gibt es weitere Klassifizierungen von Sortieralgorithmen?

Ja, zum Beispiel nach folgenden Kriterien:

• Stabilität
• Zeitkomplexität
• Speicherbedarf
• Sortiermethode (z.B. Vergleichssortierung, Verteilungssortierung)

Was ist ein Suchalgorithmus?

Ein Suchalgorithmus ist dazu bestimmt, ein bestimmtes Element innerhalb einer Datenstruktur zu finden.

Nennen Sie einige Entwurfstechniken für Algorithmen.

• Greedy-Algorithmen (gierig)
• Parallele Algorithmen
• Probabilistische Algorithmen
• Deterministische Algorithmen
• Nichtdeterministische Algorithmen

Welcher Algorithmus hat deterministisches Verhalten?

Ein deterministischer Algorithmus.

Wie funktioniert der Divide-and-Conquer-Algorithmus?

Er teilt das Problem in kleinere Teilprobleme auf, löst diese einzeln und kombiniert dann die Teillösungen zur Gesamtlösung des ursprünglichen Problems.

Wie funktioniert der Branch-and-Bound-Algorithmus?

Er basiert auf der Konstruktion eines Suchbaums, der implizit durch Verzweigung (Branching) erzeugt wird. Die Suche nach der besten Lösung wird durch Schranken (Bounding) gesteuert.

Welche Entwurfstechnik wählt immer die vielversprechendste Option?

Greedy-Algorithmen (gierig).

Was sind Metaheuristiken?

Metaheuristiken finden Näherungslösungen (die nicht unbedingt optimal sind) für Probleme, oft basierend auf vorherigem Wissen oder Erfahrung.

Zeit-Speicher-Kompromiss bei Algorithmen?

Dynamische Programmierung versucht, rechnerische Probleme durch Reduzierung der Zeitkosten auf Kosten des Speicherplatzes zu lösen.

Wie misst man die Effizienz von Algorithmen?

Man untersucht die benötigten Ressourcen (Speicher und Zeit), die der Algorithmus verbraucht.

Was leistet die Analyse von Algorithmen?

Die Analyse von Algorithmen wurde entwickelt, um Aussagen darüber zu treffen, wie sich der Zeit- und Speicherbedarf in Abhängigkeit von der Größe der Eingabedaten entwickelt.

Wie kann man einen Algorithmus ausdrücken oder kodieren?

Man kann ihn in Pseudocode schreiben oder eine Programmiersprache verwenden.