Kapitel 9: Algorithmus-Design-Paradigmen

In den vorherigen Kapiteln haben wir eine Vielzahl von Algorithmen zur Lösung spezifischer Probleme wie Sortieren, Suchen, Graphendurchlauf und Textverarbeitung untersucht. Während diese Algorithmen in ihren Anwendungen und Implementierungen vielfältig sind, teilen viele von ihnen gemeinsame zugrunde liegende Gestaltungsprinzipien oder Paradigmen.

In diesem Kapitel werden wir drei grundlegende Algorithmus-Design-Paradigmen untersuchen: Teile und Herrsche, Gierige Algorithmen und Dynamische Programmierung. Diese Paradigmen bieten allgemeine Ansätze zur Problemlösung, die an eine Vielzahl von Problemen angepasst werden können. Durch das Verständnis dieser Paradigmen können wir Einblicke in die Struktur von Algorithmen gewinnen und neue Algorithmen für die Probleme entwickeln, denen wir begegnen.

Teile und Herrsche

Das Teile-und-Herrsche-Paradigma ist ein leistungsfähiger und weit verbreiteter Ansatz für die Entwicklung effizienter Algorithmen. Die Grundidee besteht darin, ein Problem in kleinere Teilprobleme aufzuteilen, diese Teilprobleme rekursiv zu lösen und dann ihre Lösungen zu kombinieren, um das ursprüngliche Problem zu lösen.

Ein typischer Teile-und-Herrsche-Algorithmus besteht aus drei Schritten:

Teile: Wenn das Problem klein genug ist, um direkt gelöst zu werden, löse es. Andernfalls teile das Problem in kleinere Teilprobleme auf.
Herrsche: Löse jedes Teilproblem rekursiv.
Kombiniere: Kombiniere die Lösungen der Teilprobleme, um die Lösung des ursprünglichen Problems zu erhalten.

Die Wirksamkeit von Teile-und-Herrsche-Algorithmen resultiert aus ihrer Fähigkeit, die Größe eines Problems in jedem rekursiven Schritt um einen konstanten Faktor zu reduzieren. Dies führt oft zu Algorithmen mit logarithmischer oder polylogarithmischer Laufzeit.

Mergesort: Ein klassischer Teile-und-Herrsche-Algorithmus

Eines der bekanntesten Beispiele für einen Teile-und-Herrsche-Algorithmus ist Mergesort, das wir in Kapitel 2 ausführlich behandelt haben. Erinnern Sie sich, dass Mergesort ein Array sortiert, indem es es in zwei Hälften teilt, jede Hälfte rekursiv sortiert und dann die sortierten Hälften zusammenführt.

Hier ist eine allgemeine Beschreibung des MHier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst blieb unverändert.

Mergesort-Algorithmus:

function mergesort(array):
    # Wenn das Array nur ein Element hat, geben wir es zurück
    if array.length <= 1:
        return array
    else:
        # Teile das Array in zwei Hälften
        mid = array.length / 2
        left = mergesort(array[0:mid])
        right = mergesort(array[mid:])
        # Kombiniere die sortierten Hälften
        return merge(left, right)

Die merge-Funktion kombiniert zwei sortierte Arrays zu einem einzelnen sortierten Array:

function merge(left, right):
    # Erstelle ein leeres Ergebnisarray
    result = []
    # Solange beide Arrays nicht leer sind
    while left is not empty and right is not empty:
        # Füge das kleinere Element zum Ergebnisarray hinzu
        if left[0] <= right[0]:
            append left[0] to result
            remove left[0] from left
        else:
            append right[0] to result
            remove right[0] from right
    # Füge die restlichen Elemente des linken Arrays zum Ergebnisarray hinzu
    append remaining elements of left to result
    # Füge die restlichen Elemente des rechten Arrays zum Ergebnisarray hinzu
    append remaining elements of right to result
    # Gebe das Ergebnisarray zurück
    return result

Die Divide-and-Conquer-Strategie ermöglicht es Mergesort, eine worst-case-Laufzeit von O(n log n) zu erreichen, was es zu einem der effizientesten allgemeinen Sortieralgorithmen macht.

Der Master-Satz

Die Laufzeit vieler Divide-and-Conquer-Algorithmen kann mithilfe des Master-Satzes analysiert werden, der eine allgemeine Formel für Rekurrenzen der Form

T(n) = aT(n/b) + f(n)

bereitstellt. Dabei ist a die Anzahl der rekursiven Aufrufe, n/b die Größe jedes Teilproblems und f(n) die Kosten für das Aufteilen des Problems und das Kombinieren der Ergebnisse.

Der Master-Satz besagt, dass die Lösung dieser Rekurrenz:

f(n) = O(n^(log_b(a) - ε)) für eine Konstante ε > 0 ist, dann ist T(n) = Θ(n^log_b(a)).
f(n) = Θ(n^log_b(a)) ist, dann ist T(n) = Θ(n^log_b(a) * log n).
f(n) = Ω(n^(log_b(a) + ε)) für eine Konstante ε > 0 ist und af(n/b) ≤ cf(n) für eine Konstante c < 1 und alle hinreichend großen n gilt, dann ist T(n) = Θ(f(n)).

Für Mergesort haben wir a = 2 (zwei rekursive Aufrufe), b = 2 (jedes Teilproblem ist halb so groß) und f(n) = Θ(n) (der Merge-Schritt benötigt lineare Zeit). Da log_2(2) = 1 ist, befinden wir uns in Fall 2 des Master-Satzes, und die Laufzeit ist Θ(n log n).

Andere Divide-and-Conquer-Algorithmen

Viele andere Algorithmen ...Hier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden die Kommentare übersetzt, der Code selbst blieb unverändert.

Algorithmen können mithilfe des Teile-und-Herrsche-Paradigmas entworfen werden. Einige bemerkenswerte Beispiele sind:

Quicksort: Ähnlich wie Mergesort ist Quicksort ein Sortieralgorithmus nach dem Teile-und-Herrsche-Prinzip. Er teilt das Array um ein Pivotelement auf, sortiert die Teilarrays links und rechts vom Pivot rekursiv und fügt die Ergebnisse zusammen.
Binärsuche: Der Binärsuche-Algorithmus zum Finden eines Elements in einem sortierten Array kann als Teile-und-Herrsche-Algorithmus betrachtet werden. Er vergleicht den Zielwert mit dem mittleren Element des Arrays und sucht rekursiv in der linken oder rechten Hälfte, je nach Vergleichsergebnis.
Karatsuba-Multiplikation: Dies ist ein Teile-und-Herrsche-Algorithmus zum Multiplizieren zweier n-stelliger Zahlen in O(n^log_2(3)) ≈ O(n^1.585) Zeit, was schneller ist als der traditionelle O(n^2)-Algorithmus.
Strassens Matrixmultiplikation: Strassens Algorithmus multipliziert zwei n × n-Matrizen in O(n^log_2(7)) ≈ O(n^2.807) Zeit, was eine Verbesserung gegenüber dem naiven O(n^3)-Algorithmus ist.

Diese Beispiele zeigen die Vielseitigkeit und Leistungsfähigkeit des Teile-und-Herrsche-Paradigmas für den Entwurf effizienter Algorithmen.

Gierige Algorithmen

Gierige Algorithmen sind eine Klasse von Algorithmen, die bei jedem Schritt die lokal optimale Wahl treffen in der Hoffnung, eine global optimale Lösung zu finden. Sie werden oft für Optimierungsprobleme verwendet, bei denen eine Lösung inkrementell durch eine Reihe von Entscheidungen aufgebaut wird, von denen jede zum Zeitpunkt der Entscheidung am besten erscheint.

Die Schlüsseleigenschaften gieriger Algorithmen sind:

Sie treffen bei jedem Schritt eine lokal optimale Wahl, ohne sich um zukünftige Konsequenzen zu kümmern.
Sie gehen davon aus, dass eine lokal optimale Wahl zu einer global optimalen Lösung führt.
Sie überdenken frühere Entscheidungen nicht.

Gierige Algorithmen sind oft einfach zu verstehen und zu implementieren und können sehr effizient sein. Sie liefern jedoch nicht immer die optimale Lösung, da die lokal optimalen Entscheidungen nicht zwangsläufig zur global optimalen Lösung führen.

Huffman-Codierung: Ein gieriger Algorithmus zur Datenkompression

HuffmanHier ist die deutsche Übersetzung der Markdown-Datei:

Huffman-Codierung, die wir in Kapitel 5 kennengelernt haben, ist ein gieriger Algorithmus zum Erstellen eines optimalen präfixfreien Codes zum Komprimieren von Daten. Der Algorithmus baut einen Binärbaum von unten nach oben auf und weist häufigeren Zeichen kürzere Bitfolgen zu.

Hier ist eine Hochebenen-Beschreibung des Huffman-Codierungs-Algorithmus:

Erstelle einen Blattknoten für jedes Zeichen und füge ihn zu einer Prioritätswarteschlange hinzu.
Solange es mehr als einen Knoten in der Warteschlange gibt:
- Entferne die beiden Knoten mit der niedrigsten Frequenz aus der Warteschlange.
- Erstelle einen neuen inneren Knoten mit diesen beiden Knoten als Kinder und mit einer Frequenz, die der Summe der Frequenzen der beiden Knoten entspricht.
- Füge den neuen Knoten zur Prioritätswarteschlange hinzu.
Der verbleibende Knoten ist der Wurzelknoten, und der Baum ist vollständig.

Die gierige Wahl besteht darin, immer die beiden Knoten mit der niedrigsten Frequenz zusammenzuführen. Diese lokal optimale Wahl führt zu einem global optimalen präfixfreien Code.

Hier ist ein Beispiel für die Huffman-Codierung in Aktion:

Angenommen, wir haben die folgenden Zeichenfrequenzen:

d: 1
e: 1

Hier ist der Huffman-Baum für dieses Beispiel:

      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Die resultierenden Huffman-Codes sind:

A: 00
B: 01
C: 10
D: 110
E: 111

Daher würde die ursprüngliche Zeichenkette "AAAABBBCCCDDDEEE" wie folgt codiert:

00000000010101101010110110110111111111

Die Huffman-Codierung erreicht Kompression, indem sie kürzere Codes für häufigere Symbole zuweist. Die Codes sind präfixfrei, d.h. kein Code ist Präfix eines anderen, was eine eindeutige Dekodierung ermöglicht.

LZW-Kompression

Die Lempel-Ziv-Welch (LZW)-Kompression ist ein wörterbuchbasierter Kompressionsalgorithmus, der während der Kompression ein Wörterbuch (oder Codebuch) von Zeichenketten aufbaut. LZW wird in Dateikompressionsprogrammen weit verbreitet eingesetzt und wurde im GIF-Bildformat verwendet.

Die Schlüsselidee hinter LZW ist es, Zeichenketten durch einzelne Codes zu ersetzen. Er liest die Eingabezeichenkette Zeichen für Zeichen und codiert die Zeichenkette in eine kompakte Darstellung, indem er jede feste Länge durch einen einzelnen Code ersetzt.Hier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst blieb unverändert.

LZW-Kompression mit variabler Länge. Je länger der String, desto mehr Platz wird durch die Codierung als einzelne Zahl gespart.

Hier ist eine schrittweise Beschreibung, wie die LZW-Kompression funktioniert:

Initialisiere das Wörterbuch, um alle Einzelzeichen-Strings zu enthalten.
Finde den längsten String W im Wörterbuch, der mit der aktuellen Eingabe übereinstimmt.
Gib den Wörterbuchindex für W als Ausgabe aus und entferne W aus der Eingabe.
Füge W gefolgt vom nächsten Symbol in der Eingabe zum Wörterbuch hinzu.
Gehe zu Schritt 2.

Betrachten wir ein Beispiel. Angenommen, wir wollen den String "ABABABABA" mit LZW komprimieren.

Initialisiere das Wörterbuch mit "A" und "B".
Der längste Match ist "A". Gib seinen Index (0) aus und entferne ihn aus der Eingabe. Das Wörterbuch enthält nun "A", "B" und "AB".
Der längste Match ist "B". Gib seinen Index (1) aus und entferne ihn aus der Eingabe. Das Wörterbuch enthält nun "A", "B", "AB" und "BA".
Der längste Match ist "AB". Gib seinen Index (2) aus und entferne ihn aus der Eingabe. Das Wörterbuch enthält nun "A", "B", "AB", "BA" und "ABA".
Der längste Match ist "ABA". Gib seinen Index (4) aus und entferne ihn aus der Eingabe. Das Wörterbuch enthält nun "A", "B", "AB", "BA", "ABA" und "ABAB".
Der längste Match ist "BA". Gib seinen Index (3) aus. Die Eingabe ist nun leer.

Die komprimierte Darstellung von "ABABABABA" ist somit die Folge der Indizes [1], die weniger Bits benötigt als die ursprüngliche ASCII-Darstellung.

Die Dekompression funktioniert ähnlich, aber in umgekehrter Reihenfolge:

Initialisiere das Wörterbuch mit allen Einzelzeichen-Strings.
Lies einen Code X aus der Eingabe.
Gib den String für X aus dem Wörterbuch aus.
Wenn der vorherige Code existiert, füge den vorherigen String, gefolgt vom ersten Zeichen des Strings für X, zum Wörterbuch hinzu.
Gehe zu Schritt 2.

Die LZW-Kompression ist einfach und schnell, was sie für viele Anwendungen zu einer guten Wahl macht. Sie hat jedoch auch einige Einschränkungen. Die Größe des Wörterbuchs kann recht groß werden und einen erheblichen Speicherverbrauch verursachen. Außerdem...Hier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurde der Code selbst nicht übersetzt, sondern nur die Kommentare.

Der Wörterbuch wird nach jedem Eingabeblock zurückgesetzt, was das Kompressionsverh

Trotz dieser Einschränkungen bleibt LZW ein beliebter und effektiver Kompressionsalgorithmus, insbesondere für Anwendungen, bei denen die Geschwindigkeit wichtiger ist als die Erzielung der höchstmöglichen Kompressionsraten.

Schlussfolgerung

In diesem Kapitel haben wir mehrere wichtige String-Verarbeitungsalgorithmen untersucht, darunter String-Sortierung, Tries, Substring-Suche, reguläre Ausdrücke und Datenkompression. Diese Algorithmen bilden die Grundlage für viele Anwendungen in der realen Welt und sind unerlässliche Werkzeuge für jeden Programmierer, der mit Textdaten arbeitet.

Wir haben zunächst die String-Sortierung besprochen, die optimierte Sortieralgorithmen sind, die die besonderen Eigenschaften von Strings ausnutzen. Key-Indexed Counting, LSD Radix Sort und MSD Radix Sort bieten effiziente Methoden zum Sortieren von Strings basierend auf ihren einzelnen Zeichen.

Als Nächstes haben wir Tries, eine baumähnliche Datenstruktur zum Speichern und Abrufen von Strings, untersucht. Tries ermöglichen schnelles Präfixmatching und werden häufig in Anwendungen wie Autovervollständigung und IP-Routing-Tabellen verwendet.

Substring-Suchalgorithen wie der Knuth-Morris-Pratt- und der Boyer-Moore-Algorithmus ermöglichen es uns, effizient nach Mustern in größeren Strings zu suchen. Diese Algorithmen haben zahlreiche Anwendungen in der Textbearbeitung, der Bioinformatik und dem Information Retrieval.

Reguläre Ausdrücke bieten eine leistungsfähige und flexible Möglichkeit, Zeichenfolgemuster zu beschreiben. Wir haben die grundlegende Syntax regulärer Ausdrücke besprochen und wie sie in verschiedenen Programmiersprachen und Tools für Musterabgleich und Zeichenfolgemanipulation verwendet werden können.

Schließlich haben wir Datenkompressionsalgorithmen untersucht, die die Größe von Daten durch Ausnutzung von Redundanz und Mustern im Eingabematerial reduzieren. Wir haben Run-Length Encoding, Huffman-Codierung und Lempel-Ziv-Welch-Kompression behandelt, von denen jede ihre eigenen Stärken und Anwendungen hat.

Das Verständnis dieser String-Verarbeitungsalgorithmen und Datenstrukturen ist entscheidend für jeden, derHier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst blieb unverändert.

Arbeiten mit textuellen Daten

Da die Menge an unstrukturierten Daten weiter wächst, wird die Fähigkeit, Zeichenketten effizient zu manipulieren, zu durchsuchen und zu komprimieren, immer wertvoller. Durch die Beherrschung der in diesem Kapitel behandelten Techniken werden Sie gut gerüstet sein, um eine Vielzahl von Herausforderungen bei der Zeichenkettenverarbeitung in Ihren eigenen Projekten und Anwendungen zu bewältigen.

# Zeichenkette umkehren
def reverse_string(s):
    return s[::-1]
 
# Zeichenkette auf Palindrom prüfen
def is_palindrome(s):
    return s == reverse_string(s)
 
# Zeichenkette auf Anagramm prüfen
def is_anagram(s1, s2):
    return sorted(s1) == sorted(s2)
 
# Zeichenkette komprimieren
def compress_string(s):
    compressed = ""
    count = 1
    for i in range(len(s)):
        if i == len(s) - 1 or s[i] != s[i + 1]:
            compressed += s[i] + str(count)
            count = 1
        else:
            count += 1
    return compressed if len(compressed) < len(s) else s
 
# Beispielverwendung der Funktionen
print(reverse_string("hello"))  # "olleh"
print(is_palindrome("racecar"))  # True
print(is_anagram("listen", "silent"))  # True
print(compress_string("aaaaabbbccd"))  # "a5b3c2d1"

Chapter 8 Algorithm Analysis Techniques Chapter 10 Intractable Problems and Approximation Algorithms