Jak działają algorytmy
Chapter 9 Algorithm Design Paradigms Divide and Conquer

Rozdział 9: Paradygmaty projektowania algorytmów

W poprzednich rozdziałach zbadaliśmy szeroką gamę algorytmów służących do rozwiązywania konkretnych problemów, takich jak sortowanie, wyszukiwanie, przeszukiwanie grafu i przetwarzanie ciągów znaków. Chociaż te algorytmy różnią się zastosowaniami i implementacjami, wiele z nich podziela wspólne podstawowe zasady projektowania lub paradygmaty.

W tym rozdziale przyjrzymy się trzem podstawowym paradygmatom projektowania algorytmów: dziel i zwyciężaj, zachłanne algorytmy i programowanie dynamiczne. Te paradygmaty dostarczają ogólnych podejść do rozwiązywania problemów, które można dostosować do rozwiązywania szerokiej gamy problemów. Zrozumienie tych paradygmatów pozwoli nam wgląd w strukturę algorytmów i opracowywać nowe algorytmy dla problemów, z którymi się spotykamy.

Dziel i zwyciężaj

Paradygmat dziel i zwyciężaj jest potężnym i szeroko stosowanym podejściem do projektowania wydajnych algorytmów. Podstawowa idea polega na podzieleniu problemu na mniejsze podproblemy, rekursywnym rozwiązaniu tych podproblemów, a następnie połączeniu ich rozwiązań w celu rozwiązania oryginalnego problemu.

Typowy algorytm dziel i zwyciężaj składa się z trzech kroków:

  1. Dziel: Jeśli problem jest wystarczająco mały, aby można go było rozwiązać bezpośrednio, rozwiąż go. W przeciwnym razie podziel problem na mniejsze podproblemy.
  2. Zwyciężaj: Rekursywnie rozwiąż każdy podproblem.
  3. Łącz: Połącz rozwiązania podproblemów, aby uzyskać rozwiązanie oryginalnego problemu.

Skuteczność algorytmów dziel i zwyciężaj wynika z ich zdolności do zmniejszania rozmiaru problemu o stały czynnik w każdym rekursywnym kroku. Często prowadzi to do algorytmów o logarytmicznym lub wielologarytmicznym czasie działania.

Mergesort: Klasyczny algorytm dziel i zwyciężaj

Jednym z najbardziej znanych przykładów algorytmu dziel i zwyciężaj jest mergesort, który szczegółowo omówiliśmy w Rozdziale 2. Przypomnijmy, że mergesort sortuje tablicę, dzieląc ją na dwie połowy, rekursywnie sortując każdą połowę, a następnie łącząc posortowane połowy.

Oto wysokopoziomowy opis metody mergesort:Tutaj jest tłumaczenie na język polski:

Algorytm mergesort:

funkcja mergesort(tablica):
    jeśli długość tablicy <= 1:
        zwróć tablicę
    w przeciwnym razie:
        środek = długość tablicy / 2
        lewa = mergesort(tablica[0:środek])
        prawa = mergesort(tablica[środek:])
        zwróć merge(lewa, prawa)

Funkcja merge łączy dwie posortowane tablice w jedną posortowaną tablicę:

funkcja merge(lewa, prawa):
    wynik = []
    podczas gdy lewa nie jest pusta i prawa nie jest pusta:
        jeśli lewa[0] <= prawa[0]:
            dodaj lewa[0] do wyniku
            usuń lewa[0] z lewej
        w przeciwnym razie:
            dodaj prawa[0] do wyniku
            usuń prawa[0] z prawej
    dodaj pozostałe elementy lewej do wyniku
    dodaj pozostałe elementy prawej do wyniku
    zwróć wynik

Strategia podziału i zdobywania pozwala mergesortowi osiągnąć najgorszy przypadek czasu działania O(n log n), czyniąc go jednym z najbardziej wydajnych ogólnych algorytmów sortujących.

Twierdzenie Mistrza

Czas działania wielu algorytmów podziału i zdobywania można przeanalizować przy użyciu Twierdzenia Mistrza, które dostarcza ogólnego wzoru dla rekurencji w postaci:

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

Tutaj, a to liczba wywołań rekurencyjnych, n/b to rozmiar każdego podproblemu, a f(n) to koszt podziału problemu i połączenia wyników.

Twierdzenie Mistrza stwierdza, że rozwiązanie tej rekurencji jest:

  1. Jeśli f(n) = O(n^(log_b(a) - ε)) dla jakiejś stałej ε > 0, to T(n) = Θ(n^log_b(a)).
  2. Jeśli f(n) = Θ(n^log_b(a)), to T(n) = Θ(n^log_b(a) * log n).
  3. Jeśli f(n) = Ω(n^(log_b(a) + ε)) dla jakiejś stałej ε > 0, i jeśli af(n/b) ≤ cf(n) dla jakiejś stałej c < 1 i wszystkich wystarczająco dużych n, to T(n) = Θ(f(n)).

W przypadku mergesort, mamy a = 2 (dwa wywołania rekurencyjne), b = 2 (każdy podproblem ma połowę rozmiaru), i f(n) = Θ(n) (krok łączenia zajmuje liniowy czas). Ponieważ log_2(2) = 1, znajdujemy się w przypadku 2 Twierdzenia Mistrza, a czas działania wynosi Θ(n log n).

Inne Algorytmy Podziału i Zdobywania

Wiele innych alOto tłumaczenie na język polski:

Algorytmy mogą być zaprojektowane przy użyciu paradygmatu podziału i zdobywania. Niektóre z nich to:

  • Sortowanie szybkie (Quicksort): Podobnie jak sortowanie przez scalanie, sortowanie szybkie jest algorytmem sortującym opartym na podziale i zdobywaniu. Dzieli tablicę wokół elementu-pivota, rekurencyjnie sortuje podzbiory po lewej i prawej stronie pivota i łączy wyniki.

  • Wyszukiwanie binarne: Algorytm wyszukiwania binarnego do znajdowania elementu w posortowanej tablicy można traktować jako algorytm podziału i zdobywania. Porównuje wartość docelową ze środkowym elementem tablicy i rekurencyjnie przeszukuje lewą lub prawą połowę, w zależności od wyniku porównania.

  • Mnożenie Karatsuby: Jest to algorytm podziału i zdobywania do mnożenia dwóch liczb n-cyfrowych w czasie O(n^log_2(3)) ≈ O(n^1.585), co jest szybsze niż tradycyjny algorytm O(n^2).

  • Mnożenie macierzy Strassena: Algorytm Strassena mnoży dwie macierze n × n w czasie O(n^log_2(7)) ≈ O(n^2.807), poprawiając na naiwnym algorytmie O(n^3).

Te przykłady pokazują wszechstronność i moc paradygmatu podziału i zdobywania w projektowaniu wydajnych algorytmów.

Algorytmy zachłanne

Algorytmy zachłanne to klasa algorytmów, które w każdym kroku dokonują lokalnie optymalnego wyboru, mając nadzieję na znalezienie globalnie optymalnego rozwiązania. Są często używane do problemów optymalizacyjnych, gdzie rozwiązanie jest budowane krok po kroku poprzez podejmowanie serii wyborów, z których każdy wydaje się najlepszy w danym momencie.

Kluczowe cechy algorytmów zachłannych to:

  1. Dokonują lokalnie optymalnego wyboru w każdym kroku, nie martwiąc się o przyszłe konsekwencje.
  2. Zakładają, że lokalnie optymalny wybór doprowadzi do globalnie optymalnego rozwiązania.
  3. Nigdy nie rozważają ponownie wcześniejszych wyborów.

Algorytmy zachłanne są często łatwe do zrozumienia i implementacji, a także mogą być bardzo wydajne. Jednak nie zawsze prowadzą do optymalnego rozwiązania, ponieważ lokalne optymalne wybory mogą nie prowadzić do globalnie optymalnego rozwiązania.

Kodowanie Huffmana: Algorytm zachłanny do kompresji danych

Kodowanie HuffmanaOto tłumaczenie na język polski:

Kodowanie Huffmana, które poznaliśmy w Rozdziale 5, jest chciwym algorytmem do konstruowania optymalnego kodu prefiksowego do kompresji danych. Algorytm buduje drzewo binarne od dołu do góry, przypisując krótsze ciągi bitowe do częściej występujących znaków.

Oto wysokopoziomowy opis algorytmu kodowania Huffmana:

  1. Utwórz węzeł liściowy dla każdego znaku i dodaj go do kolejki priorytetowej.
  2. Dopóki w kolejce jest więcej niż jeden węzeł:
    • Usuń dwa węzły o najniższej częstotliwości z kolejki.
    • Utwórz nowy węzeł wewnętrzny z tymi dwoma węzłami jako dziećmi i z częstotliwością równą sumie częstotliwości dwóch węzłów.
    • Dodaj nowy węzeł do kolejki priorytetowej.
  3. Pozostały węzeł jest węzłem korzenia, a drzewo jest kompletne.

Chciwa decyzja polega na zawsze łączeniu dwóch węzłów o najniższej częstotliwości. Ta lokalnie optymalna decyzja prowadzi do globalnie optymalnego kodu prefiksowego.

Oto przykład kodowania Huffmana w działaniu:

Załóżmy, że mamy następujące częstotliwości znaków:

d: 1
e: 1

Oto drzewo Huffmana dla tego przykładu:

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

Wynikowe kody Huffmana to:

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

Zatem oryginalna sekwencja "AAAABBBCCCDDDEEE" zostałaby zakodowana jako:

00000000010101101010110110110111111111

Kodowanie Huffmana osiąga kompresję poprzez przypisywanie krótszych kodów do częściej występujących symboli. Kody są prefiksowe, co oznacza, że żaden kod nie jest prefiksem innego, co pozwala na jednoznaczne dekodowanie.

Kompresja LZW

Kompresja Lempel-Ziv-Welch (LZW) to algorytm kompresji oparty na słowniku, który buduje słownik (lub książkę kodową) ciągów znaków podczas kompresji danych wejściowych. LZW jest szeroko stosowany w narzędziach do kompresji plików i był używany w formacie obrazów GIF.

Kluczową ideą LZW jest zastępowanie ciągów znaków pojedynczymi kodami. Czyta on ciąg wejściowy znak po znaku i koduje go w zwartą reprezentację, zastępując każdy stały ciąg znaków pojedynczym kodem.Oto polski przekład pliku Markdown. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.

Kompresja LZW

LZW to algorytm kompresji bezstratnej o zmiennej długości kodu. Im dłuższy jest ciąg znaków, tym więcej miejsca można zaoszczędzić, kodując go jako pojedynczą liczbę.

Oto krok po kroku, jak działa kompresja LZW:

  1. Zainicjuj słownik, aby zawierał wszystkie pojedyncze znaki.
  2. Znajdź najdłuższy ciąg W w słowniku, który pasuje do bieżącego wejścia.
  3. Wyślij indeks słownika dla W do wyjścia i usuń W z wejścia.
  4. Dodaj W wraz z następnym symbolem w wejściu do słownika.
  5. Przejdź do kroku 2.

Rozważmy przykład. Załóżmy, że chcemy skompresować ciąg "ABABABABA" przy użyciu LZW.

  1. Zainicjuj słownik, aby zawierał "A" i "B".
  2. Najdłuższy pasujący ciąg to "A". Wyślij jego indeks (0) i usuń go z wejścia. Słownik teraz zawiera "A", "B" i "AB".
  3. Najdłuższy pasujący ciąg to "B". Wyślij jego indeks (1) i usuń go z wejścia. Słownik teraz zawiera "A", "B", "AB" i "BA".
  4. Najdłuższy pasujący ciąg to "AB". Wyślij jego indeks (2) i usuń go z wejścia. Słownik teraz zawiera "A", "B", "AB", "BA" i "ABA".
  5. Najdłuższy pasujący ciąg to "ABA". Wyślij jego indeks (4) i usuń go z wejścia. Słownik teraz zawiera "A", "B", "AB", "BA", "ABA" i "ABAB".
  6. Najdłuższy pasujący ciąg to "BA". Wyślij jego indeks (3). Wejście jest teraz puste.

Skompresowana reprezentacja "ABABABABA" to zatem sekwencja indeksów [1], która wymaga mniej bitów do reprezentacji niż oryginalna reprezentacja ASCII.

Dekompresja działa podobnie, ale w odwrotnym kierunku:

  1. Zainicjuj słownik, aby zawierał wszystkie pojedyncze znaki.
  2. Odczytaj kod X z wejścia.
  3. Wyślij ciąg dla X ze słownika.
  4. Jeśli istnieje poprzedni kod, dodaj poprzedni ciąg połączony z pierwszym znakiem ciągu dla X do słownika.
  5. Przejdź do kroku 2.

Kompresja LZW jest prosta i szybka, co czyni ją dobrym wyborem dla wielu zastosowań. Jednak ma ona również pewne ograniczenia. Rozmiar słownika może znacznie wzrosnąć, co spowoduje duże zużycie pamięci. Ponadto,Oto tłumaczenie na język polski:

Słownik resetuje się po każdym bloku danych wejściowych, co może zmniejszyć współczynnik kompresji dla małych plików.

Pomimo tych ograniczeń, LZW pozostaje popularnym i skutecznym algorytmem kompresji, szczególnie w zastosowaniach, gdzie szybkość jest ważniejsza niż osiągnięcie najwyższych możliwych współczynników kompresji.

Wniosek

W tym rozdziale zbadaliśmy kilka ważnych algorytmów przetwarzania ciągów znaków, w tym sortowanie ciągów znaków, drzewa tries, wyszukiwanie podciągów, wyrażenia regularne i kompresję danych. Te algorytmy stanowią podstawę wielu rzeczywistych aplikacji i są niezbędnymi narzędziami dla każdego programisty pracującego z danymi tekstowymi.

Rozpoczęliśmy od omówienia sortowania ciągów znaków, które są zoptymalizowanymi algorytmami sortowania wykorzystującymi specjalne właściwości ciągów znaków. Liczenie kluczy, sortowanie LSD radix i sortowanie MSD radix zapewniają wydajne metody sortowania ciągów znaków na podstawie ich poszczególnych znaków.

Następnie zbadaliśmy drzewa tries, strukturę danych drzewopodobną do przechowywania i pobierania ciągów znaków. Drzewa tries umożliwiają szybkie dopasowywanie prefiksów i są powszechnie używane w aplikacjach, takich jak autouzupełnianie i tablice routingu IP.

Algorytmy wyszukiwania podciągów, takie jak algorytmy Knutha-Morrisa-Pratta i Boyera-Moore'a, pozwalają nam wydajnie wyszukiwać wzorce w większych ciągach znaków. Te algorytmy mają liczne zastosowania w edycji tekstu, biologii obliczeniowej i wyszukiwaniu informacji.

Wyrażenia regularne zapewniają potężny i elastyczny sposób opisywania wzorców ciągów znaków. Omówiliśmy podstawową składnię wyrażeń regularnych i sposób ich wykorzystania do dopasowywania wzorców i manipulowania ciągami znaków w różnych językach programowania i narzędziach.

Wreszcie, zbadaliśmy algorytmy kompresji danych, które zmniejszają rozmiar danych poprzez wykorzystanie redundancji i wzorców w danych wejściowych. Omówiliśmy kodowanie długości serii, kodowanie Huffmana i kompresję Lempel-Ziv-Welch, z których każdy ma swoje mocne strony i zastosowania.

Zrozumienie tych algorytmów przetwarzania ciągów znaków i struktur danych jest kluczowe dla każdego, kto pracuje z danymi tekstowymi.Here is the Polish translation of the provided Markdown file, with the code left untranslated and only the comments translated:

Praca z danymi tekstowymi

Wraz ze stałym wzrostem ilości nieustrukturyzowanych danych, umiejętność efektywnego manipulowania, wyszukiwania i kompresowania ciągów znaków będzie stawać się coraz bardziej wartościowa. Opanowując techniki omówione w tym rozdziale, będziesz dobrze przygotowany do radzenia sobie z szerokim zakresem wyzwań związanych z przetwarzaniem ciągów znaków w swoich własnych projektach i aplikacjach.

# Przykład 1: Odwracanie ciągu znaków
def reverse_string(s):
    """
    Odwraca ciąg znaków.
    """
    return s[::-1]
 
# Przykład 2: Sprawdzanie palindromu
def is_palindrome(s):
    """
    Sprawdza, czy ciąg znaków jest palindromem.
    """
    return s == s[::-1]
 
# Przykład 3: Zliczanie wystąpień znaków
def count_chars(s):
    """
    Zlicza wystąpienia każdego znaku w ciągu znaków.
    """
    char_counts = {}
    for char in s:
        if char in char_counts:
            char_counts[char] += 1
        else:
            char_counts[char] = 1
    return char_counts
 
# Przykład 4: Kompresja ciągu znaków
def compress_string(s):
    """
    Kompresuje ciąg znaków, zastępując powtarzające się znaki ich liczbą.
    """
    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
Chapter 8 Algorithm Analysis TechniquesChapter 10 Intractable Problems and Approximation Algorithms