Hoe algoritmes werken
Chapter 9 Algorithm Design Paradigms Divide and Conquer

Hoofdstuk 9: Algoritme Ontwerp Paradigma's

In de vorige hoofdstukken hebben we een breed scala aan algoritmen onderzocht voor het oplossen van specifieke problemen, zoals sorteren, zoeken, graaftransitie en tekstverwerking. Hoewel deze algoritmen divers zijn in hun toepassingen en implementaties, delen veel van hen gemeenschappelijke onderliggende ontwerpprincipes of paradigma's.

In dit hoofdstuk zullen we drie fundamentele algoritme-ontwerpparadigma's onderzoeken: verdeel en heers, greedy algoritmen en dynamisch programmeren. Deze paradigma's bieden algemene benaderingen voor probleemoplossing die kunnen worden aangepast om een breed scala aan problemen op te lossen. Door deze paradigma's te begrijpen, kunnen we inzicht krijgen in de structuur van algoritmen en nieuwe algoritmen ontwikkelen voor de problemen die we tegenkomen.

Verdeel en Heers

Het verdeel en heers paradigma is een krachtige en veel gebruikte aanpak voor het ontwerpen van efficiënte algoritmen. Het basisidee is om een probleem op te splitsen in kleinere deelproblemen, deze deelproblemen recursief op te lossen en vervolgens hun oplossingen te combineren om het oorspronkelijke probleem op te lossen.

Een typisch verdeel en heers algoritme bestaat uit drie stappen:

  1. Verdeel: Als het probleem klein genoeg is om direct op te lossen, los het dan op. Anders, verdeel het probleem in kleinere deelproblemen.
  2. Verover: Los elk deelprobleem recursief op.
  3. Combineer: Combineer de oplossingen van de deelproblemen om de oplossing van het oorspronkelijke probleem te verkrijgen.

De effectiviteit van verdeel en heers algoritmen komt voort uit hun vermogen om de grootte van een probleem in elke recursieve stap met een constante factor te verminderen. Dit leidt vaak tot algoritmen met logaritmische of polylogaritmische uitvoeringstijden.

Mergesort: Een Klassiek Verdeel en Heers Algoritme

Een van de bekendste voorbeelden van een verdeel en heers algoritme is mergesort, die we in detail hebben bestudeerd in Hoofdstuk 2. Zoals u zich herinnert, sorteert mergesort een array door deze in twee helften te verdelen, elke helft recursief te sorteren en vervolgens de gesorteerde helften samen te voegen.

Hier volgt een hoog-niveau beschrijving van de mHier is de Nederlandse vertaling van het Markdown-bestand:

Mergesort-algoritme:

function mergesort(array):
    if array.length <= 1:
        return array
    else:
        mid = array.length / 2
        left = mergesort(array[0:mid])
        right = mergesort(array[mid:])
        return merge(left, right)

De samenvoegen-functie combineert twee gesorteerde arrays in één enkele gesorteerde array:

function merge(left, right):
    result = []
    while left is not empty and right is not empty:
        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
    append remaining elements of left to result
    append remaining elements of right to result
    return result

De verdeel-en-heers-strategie stelt mergesort in staat om een worst-case uitvoeringstijd van O(n log n) te bereiken, waardoor het een van de meest efficiënte algemene sorteeralgoritmen is.

De Masterstelling

De uitvoeringstijd van veel verdeel-en-heers-algoritmen kan worden geanalyseerd met behulp van de Masterstelling, die een algemene formule biedt voor herhalingen van de vorm:

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

Hier is a het aantal recursieve oproepen, n/b de grootte van elk deelprobleem, en f(n) de kosten van het opdelen van het probleem en het combineren van de resultaten.

De Masterstelling stelt dat de oplossing voor deze herhaling:

  1. Als f(n) = O(n^(log_b(a) - ε)) voor een constante ε > 0, dan T(n) = Θ(n^log_b(a)).
  2. Als f(n) = Θ(n^log_b(a)), dan T(n) = Θ(n^log_b(a) * log n).
  3. Als f(n) = Ω(n^(log_b(a) + ε)) voor een constante ε > 0, en als af(n/b) ≤ cf(n) voor een constante c < 1 en alle voldoende grote n, dan T(n) = Θ(f(n)).

Voor mergesort hebben we a = 2 (twee recursieve oproepen), b = 2 (elk deelprobleem is half zo groot), en f(n) = Θ(n) (de samenvoegstap neemt lineaire tijd). Aangezien log_2(2) = 1, vallen we in geval 2 van de Masterstelling, en de uitvoeringstijd is Θ(n log n).

Andere verdeel-en-heers-algoritmen

Veel andere alHier is de Nederlandse vertaling van het Markdown-bestand:

Algoritmen kunnen worden ontworpen met behulp van het verdeel-en-heers-paradigma. Enkele opmerkelijke voorbeelden zijn:

  • Quicksort: Net als mergesort is quicksort een verdeel-en-verover-sorteeralgoritme. Het verdeelt de array rond een pivotelement, sorteert de subarrays links en rechts van de pivot recursief en concateneert de resultaten.

  • Binair zoeken: Het binaire zoekalgoritme voor het vinden van een element in een gesorteerde array kan worden beschouwd als een verdeel-en-verover-algoritme. Het vergelijkt de doelwaarde met het middelste element van de array en zoekt recursief in de linker- of rechterhelft, afhankelijk van de vergelijking.

  • Karatsuba-vermenigvuldiging: Dit is een verdeel-en-verover-algoritme voor het vermenigvuldigen van twee n-cijferige getallen in O(n^log_2(3)) ≈ O(n^1.585) tijd, wat sneller is dan het traditionele O(n^2)-algoritme.

  • Strassen's matrixvermenigvuldiging: Het algoritme van Strassen vermenigvuldigt twee n × n-matrices in O(n^log_2(7)) ≈ O(n^2.807) tijd, wat een verbetering is op het naïeve O(n^3)-algoritme.

Deze voorbeelden demonstreren de veelzijdigheid en kracht van het verdeel-en-verover-paradigma voor het ontwerpen van efficiënte algoritmen.

Greedy Algoritmen

Greedy algoritmen zijn een klasse van algoritmen die op elk moment de lokaal optimale keuze maken in de hoop een globaal optimale oplossing te vinden. Ze worden vaak gebruikt voor optimalisatieproblemen waarbij een oplossing stapsgewijs wordt opgebouwd door een reeks keuzes te maken, waarbij elke keuze op dat moment de beste lijkt.

De belangrijkste kenmerken van greedy algoritmen zijn:

  1. Ze maken op elke stap een lokaal optimale keuze, zonder zich zorgen te maken over toekomstige gevolgen.
  2. Ze veronderstellen dat een lokaal optimale keuze zal leiden tot een globaal optimale oplossing.
  3. Ze heroverwegen nooit eerdere keuzes.

Greedy algoritmen zijn vaak eenvoudig te begrijpen en te implementeren, en kunnen zeer efficiënt zijn. Ze leveren echter niet altijd de optimale oplossing op, omdat de lokaal optimale keuzes niet altijd leiden tot de globaal optimale oplossing.

Huffman-codering: Een Greedy Algoritme voor Gegevenscompressie

HuffmanHier is de Nederlandse vertaling van het bestand:

Codering, die we in Hoofdstuk 5 tegenkwamen, is een gretig algoritme voor het construeren van een optimale prefix-vrije code voor het comprimeren van gegevens. Het algoritme bouwt een binaire boom van onderaf naar boven, waarbij kortere bitreeksen worden toegewezen aan meer frequente tekens.

Hier volgt een hoog-niveau beschrijving van het Huffman-coderingsalgoritme:

  1. Maak een bladknoop voor elk teken en voeg deze toe aan een prioriteitswachtrij.
  2. Zolang er meer dan één knoop in de wachtrij staat:
    • Verwijder de twee knopen met de laagste frequentie uit de wachtrij.
    • Maak een nieuwe interne knoop met deze twee knopen als kinderen en met een frequentie gelijk aan de som van de frequenties van de twee knopen.
    • Voeg de nieuwe knoop toe aan de prioriteitswachtrij.
  3. De resterende knoop is de wortelknoop, en de boom is compleet.

De gretige keuze is om altijd de twee knopen met de laagste frequentie samen te voegen. Deze lokaal optimale keuze leidt tot een globaal optimale prefix-vrije code.

Hier is een voorbeeld van Huffman-codering in actie:

Stel dat we de volgende teken-frequenties hebben:

d: 1
e: 1

Hier is de Huffman-boom voor dit voorbeeld:

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

De resulterende Huffman-codes zijn:

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

Dus de oorspronkelijke string "AAAABBBCCCDDDEEE" zou worden gecodeerd als:

00000000010101101010110110110111111111

Huffman-codering bereikt compressie door kortere codes toe te wijzen aan meer frequente symbolen. De codes zijn prefix-vrij, wat betekent dat geen enkele code een prefix is van een andere, waardoor ondubbelzinnige decodering mogelijk is.

LZW-compressie

Lempel-Ziv-Welch (LZW)-compressie is een op woordenboek gebaseerd compressie-algoritme dat een woordenboek (of codeboek) van strings opbouwt tijdens het comprimeren van de invoer. LZW wordt veel gebruikt in bestandscompressie-hulpprogramma's en werd gebruikt in het GIF-beeldformaat.

Het sleutelprincipe achter LZW is het vervangen van tekenreeksen door enkele codes. Het leest de invoerstring teken voor teken en codeert de string in een compacte representatie door elke vaste lengteHier is de Nederlandse vertaling van het bestand:

ngth code met een variabele-lengte code. Hoe langer de tekenreeks, hoe meer ruimte wordt bespaard door deze als één getal te coderen.

Hier is een stap-voor-stap beschrijving van hoe LZW-compressie werkt:

  1. Initialiseer het woordenboek om alle enkelteken-tekenreeksen te bevatten.
  2. Vind de langste tekenreeks W in het woordenboek die overeenkomt met de huidige invoer.
  3. Geef de woordenboekindex voor W als uitvoer en verwijder W uit de invoer.
  4. Voeg W gevolgd door het volgende symbool in de invoer toe aan het woordenboek.
  5. Ga naar Stap 2.

Laten we een voorbeeld bekijken. Stel dat we de tekenreeks "ABABABABA" willen comprimeren met LZW.

  1. Initialiseer het woordenboek met "A" en "B".
  2. De langste overeenkomst is "A". Geef de index (0) ervan als uitvoer en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B" en "AB".
  3. De langste overeenkomst is "B". Geef de index (1) ervan als uitvoer en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B", "AB" en "BA".
  4. De langste overeenkomst is "AB". Geef de index (2) ervan als uitvoer en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B", "AB", "BA" en "ABA".
  5. De langste overeenkomst is "ABA". Geef de index (4) ervan als uitvoer en verwijder het uit de invoer. Het woordenboek bevat nu "A", "B", "AB", "BA", "ABA" en "ABAB".
  6. De langste overeenkomst is "BA". Geef de index (3) ervan als uitvoer. De invoer is nu leeg.

De gecomprimeerde weergave van "ABABABABA" is dus de reeks indexen [1], wat minder bits vereist dan de oorspronkelijke ASCII-weergave.

Decompressie werkt op een vergelijkbare manier, maar in omgekeerde volgorde:

  1. Initialiseer het woordenboek om alle enkelteken-tekenreeksen te bevatten.
  2. Lees een code X uit de invoer.
  3. Geef de tekenreeks voor X uit het woordenboek als uitvoer.
  4. Als de vorige code bestaat, voeg dan de vorige tekenreeks samengevoegd met het eerste teken van de tekenreeks voor X toe aan het woordenboek.
  5. Ga naar Stap 2.

LZW-compressie is eenvoudig en snel, waardoor het een goede keuze is voor veel toepassingen. Het heeft echter ook enkele beperkingen. De grootte van het woordenboek kan aanzienlijk toenemen, waardoor een significant geheugengebruik ontstaat. Bovendien...Hier is de Nederlandse vertaling van het bestand:

het woordenboek wordt na elke invoerblok gereset, wat de compressieratio voor kleine bestanden kan verlagen.

Ondanks deze beperkingen blijft LZW een populair en effectief compressie-algoritme, vooral voor toepassingen waar snelheid belangrijker is dan het bereiken van de hoogst mogelijke compressieverhoudingen.

Conclusie

In dit hoofdstuk hebben we verschillende belangrijke string-verwerkingsalgoritmen onderzocht, waaronder string sorts, tries, substring zoeken, reguliere expressies en gegevenscompressie. Deze algoritmen vormen de basis voor veel real-world toepassingen en zijn essentiële tools voor elke programmeur die met tekstuele gegevens werkt.

We zijn begonnen met het bespreken van string sorts, die geoptimaliseerde sorteeralgoritmen zijn die gebruik maken van de speciale eigenschappen van strings. Key-indexed counting, LSD radix sort en MSD radix sort bieden efficiënte methoden voor het sorteren van strings op basis van hun individuele tekens.

Vervolgens hebben we tries onderzocht, een boomachtige gegevensstructuur voor het opslaan en ophalen van strings. Tries maken snel voorvoegselzoeken mogelijk en worden veel gebruikt in toepassingen zoals automatisch aanvullen en IP-routingtabellen.

Substring zoekalgoritmen, zoals de Knuth-Morris-Pratt- en Boyer-Moore-algoritmen, stellen ons in staat om efficiënt naar patronen binnen grotere strings te zoeken. Deze algoritmen hebben talrijke toepassingen in tekstbewerking, computationele biologie en informatiewinning.

Reguliere expressies bieden een krachtige en flexibele manier om string patronen te beschrijven. We hebben de basissyntaxis van reguliere expressies besproken en hoe ze kunnen worden gebruikt voor patroonherkenning en string manipulatie in verschillende programmeertalen en tools.

Ten slotte hebben we gegevenscompressie-algoritmen onderzocht, die de grootte van gegevens verkleinen door redundantie en patronen binnen de invoer te benutten. We hebben run-length encoding, Huffman-codering en Lempel-Ziv-Welch-compressie behandeld, waarvan elk zijn eigen sterke en zwakke punten heeft.

Het begrijpen van deze string-verwerkingsalgoritmen en gegevensstructuren is cruciaal voor iedereen dieHier is de Nederlandse vertaling van het bestand:

Werken met tekstuele gegevens

Naarmate de hoeveelheid ongestructureerde gegevens blijft groeien, zal het vermogen om strings efficiënt te manipuleren, doorzoeken en comprimeren alleen maar waardevoller worden. Door de technieken die in dit hoofdstuk worden behandeld, zult u goed uitgerust zijn om een breed scala aan string-verwerkingsuitdagingen in uw eigen projecten en toepassingen aan te pakken.

# Voorbeeld: Omgaan met strings in Python
my_string = "Hello, World!"
print(my_string)  # Uitvoer: Hello, World!
 
# Lengte van een string ophalen
print(len(my_string))  # Uitvoer: 13
 
# Een substring extraheren
substring = my_string[7:12]
print(substring)  # Uitvoer: World
 
# Een string splitsen op basis van een scheidingsteken
words = my_string.split(", ")
print(words)  # Uitvoer: ['Hello', 'World!']
 
# Een string vervangen
new_string = my_string.replace("World", "Python")
print(new_string)  # Uitvoer: Hello, Python!
 
# Een string omzetten naar hoofdletters of kleine letters
print(my_string.upper())  # Uitvoer: HELLO, WORLD!
print(my_string.lower())  # Uitvoer: hello, world!
Chapter 8 Algorithm Analysis TechniquesChapter 10 Intractable Problems and Approximation Algorithms