Como os Algoritmos Funcionam
Chapter 9 Algorithm Design Paradigms Divide and Conquer

Capítulo 9: Paradigmas de Projeto de Algoritmos

Nos capítulos anteriores, exploramos uma ampla variedade de algoritmos para resolver problemas específicos, como ordenação, busca, travessia de grafos e processamento de strings. Embora esses algoritmos sejam diversos em suas aplicações e implementações, muitos deles compartilham princípios ou paradigmas de design subjacentes comuns.

Neste capítulo, vamos examinar três paradigmas fundamentais de design de algoritmos: divisão e conquista, algoritmos gulosos e programação dinâmica. Esses paradigmas fornecem abordagens gerais de resolução de problemas que podem ser adaptadas para resolver uma vasta gama de problemas. Ao compreender esses paradigmas, podemos obter insights sobre a estrutura dos algoritmos e desenvolver novos algoritmos para os problemas que encontramos.

Divisão e Conquista

O paradigma de divisão e conquista é uma abordagem poderosa e amplamente utilizada para projetar algoritmos eficientes. A ideia básica é dividir um problema em subproblemas menores, resolver esses subproblemas recursivamente e, em seguida, combinar suas soluções para resolver o problema original.

Um típico algoritmo de divisão e conquista consiste em três etapas:

  1. Divisão: Se o problema for pequeno o suficiente para ser resolvido diretamente, resolva-o. Caso contrário, divida o problema em subproblemas menores.
  2. Conquista: Resolva recursivamente cada subproblema.
  3. Combinação: Combine as soluções dos subproblemas para obter a solução do problema original.

A eficácia dos algoritmos de divisão e conquista decorre de sua capacidade de reduzir o tamanho de um problema por um fator constante em cada etapa recursiva. Isso geralmente leva a algoritmos com tempos de execução logarítmicos ou polilogatítmicos.

Mergesort: Um Algoritmo Clássico de Divisão e Conquista

Um dos exemplos mais conhecidos de um algoritmo de divisão e conquista é o mergesort, que estudamos em detalhes no Capítulo 2. Lembre-se de que o mergesort ordena um array dividindo-o em duas metades, ordenando recursivamente cada metade e, em seguida, mesclando as metades ordenadas.

Aqui está uma descrição de alto nível do mAlgoritmo de mergesort:

função mergesort(array):
    se o tamanho do array for menor ou igual a 1:
        retorne o array
    senão:
        meio = tamanho do array / 2
        esquerda = mergesort(array[0:meio])
        direita = mergesort(array[meio:])
        retorne mesclar(esquerda, direita)

A função mesclar combina dois arrays ordenados em um único array ordenado:

função mesclar(esquerda, direita):
    resultado = []
    enquanto esquerda não estiver vazio e direita não estiver vazio:
        se o primeiro elemento de esquerda for menor ou igual ao primeiro elemento de direita:
            adicione o primeiro elemento de esquerda ao resultado
            remova o primeiro elemento de esquerda
        senão:
            adicione o primeiro elemento de direita ao resultado
            remova o primeiro elemento de direita
    adicione os elementos restantes de esquerda ao resultado
    adicione os elementos restantes de direita ao resultado
    retorne o resultado

A estratégia de divisão e conquista permite que o mergesort alcance um tempo de execução no pior caso de O(n log n), tornando-o um dos algoritmos de ordenação mais eficientes de propósito geral.

O Teorema do Mestre

O tempo de execução de muitos algoritmos de divisão e conquista pode ser analisado usando o Teorema do Mestre, que fornece uma fórmula geral para recorrências da forma:

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

Aqui, a é o número de chamadas recursivas, n/b é o tamanho de cada subproblema, e f(n) é o custo de dividir o problema e combinar os resultados.

O Teorema do Mestre afirma que a solução para essa recorrência é:

  1. Se f(n) = O(n^(log_b(a) - ε)) para alguma constante ε > 0, então T(n) = Θ(n^log_b(a)).
  2. Se f(n) = Θ(n^log_b(a)), então T(n) = Θ(n^log_b(a) * log n).
  3. Se f(n) = Ω(n^(log_b(a) + ε)) para alguma constante ε > 0, e se af(n/b) ≤ cf(n) para alguma constante c < 1 e todos os n suficientemente grandes, então T(n) = Θ(f(n)).

Para o mergesort, temos a = 2 (duas chamadas recursivas), b = 2 (cada subproblema é metade do tamanho), e f(n) = Θ(n) (a etapa de mesclagem leva tempo linear). Como log_2(2) = 1, estamos no caso 2 do Teorema do Mestre, e o tempo de execução é Θ(n log n).

Outros Algoritmos de Divisão e Conquista

Muitos outros alAqui está a tradução em português do arquivo markdown, com os comentários traduzidos, mas o código não traduzido:

Algoritmos de Divisão e Conquista

Os algoritmos podem ser projetados usando o paradigma de divisão e conquista. Alguns exemplos notáveis incluem:

  • Quicksort: Assim como o mergesort, o quicksort é um algoritmo de ordenação de divisão e conquista. Ele particiona o array em torno de um elemento pivô, ordena recursivamente os subarrays à esquerda e à direita do pivô e concatena os resultados.

  • Busca binária: O algoritmo de busca binária para encontrar um elemento em um array ordenado pode ser visto como um algoritmo de divisão e conquista. Ele compara o valor alvo com o elemento do meio do array e pesquisa recursivamente a metade esquerda ou direita, dependendo da comparação.

  • Multiplicação de Karatsuba: Este é um algoritmo de divisão e conquista para multiplicar dois números de n dígitos em O(n^log_2(3)) ≈ O(n^1.585) tempo, que é mais rápido do que o algoritmo tradicional de O(n^2).

  • Multiplicação de matrizes de Strassen: O algoritmo de Strassen multiplica duas matrizes n × n em O(n^log_2(7)) ≈ O(n^2.807) tempo, melhorando o algoritmo ingênuo de O(n^3).

Esses exemplos demonstram a versatilidade e o poder do paradigma de divisão e conquista para projetar algoritmos eficientes.

Algoritmos Gulosos

Algoritmos gulosos são uma classe de algoritmos que fazem a escolha localmente ótima em cada etapa, com a esperança de encontrar uma solução globalmente ótima. Eles são frequentemente usados para problemas de otimização onde uma solução é construída incrementalmente, fazendo uma série de escolhas, cada uma das quais parece a melhor no momento.

As principais características dos algoritmos gulosos são:

  1. Eles fazem uma escolha localmente ótima em cada passo, sem se preocupar com as consequências futuras.
  2. Eles assumem que uma escolha localmente ótima levará a uma solução globalmente ótima.
  3. Eles nunca reconsideram escolhas anteriores.

Os algoritmos gulosos são frequentemente simples de entender e implementar, e podem ser muito eficientes. No entanto, eles nem sempre produzem a solução ótima, pois as escolhas localmente ótimas podem não levar à solução globalmente ótima.

Codificação de Huffman: Um Algoritmo Guloso para Compressão de Dados

HuffmanAqui está a tradução em português do arquivo markdown, com os comentários traduzidos, mas o código não traduzido:

A codificação de Huffman, que encontramos no Capítulo 5, é um algoritmo guloso para construir um código prefixo-livre ótimo para comprimir dados. O algoritmo constrói uma árvore binária de baixo para cima, atribuindo sequências de bits mais curtas a caracteres mais frequentes.

Aqui está uma descrição de alto nível do algoritmo de codificação de Huffman:

  1. Crie um nó folha para cada caractere e adicione-o a uma fila de prioridade.
  2. Enquanto houver mais de um nó na fila:
    • Remova os dois nós de menor frequência da fila.
    • Crie um novo nó interno com esses dois nós como filhos e com frequência igual à soma das frequências dos dois nós.
    • Adicione o novo nó à fila de prioridade.
  3. O nó restante é o nó raiz, e a árvore está completa.

A escolha gulosa é sempre mesclar os dois nós de menor frequência. Essa escolha localmente ótima leva a um código prefixo-livre globalmente ótimo.

Aqui está um exemplo da codificação de Huffman em ação:

Suponha que tenhamos as seguintes frequências de caracteres:

d: 1
e: 1

Aqui está a árvore de Huffman para este exemplo:

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

Os códigos de Huffman resultantes são:

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

Então a string original "AAAABBBCCCDDDEEE" seria codificada como:

00000000010101101010110110110111111111

A codificação de Huffman alcança a compressão atribuindo códigos mais curtos a símbolos mais frequentes. Os códigos são prefixo-livres, o que significa que nenhum código é prefixo de outro, permitindo a decodificação inequívoca.

Compressão LZW

A compressão Lempel-Ziv-Welch (LZW) é um algoritmo de compressão baseado em dicionário que constrói um dicionário (ou codebook) de strings durante a compressão da entrada. O LZW é amplamente usado em utilitários de compressão de arquivos e foi usado no formato de imagem GIF.

A ideia-chave por trás do LZW é substituir strings de caracteres por códigos únicos. Ele lê a string de entrada caractere por caractere e codifica a string em uma representação compacta, substituindo cada sequência fixa deAqui está a tradução em português deste arquivo markdown. Para o código, não traduzi o código, apenas os comentários.

Compressão LZW com código de comprimento variável. Quanto maior a string, mais espaço é economizado ao codificá-la como um único número.

Aqui está uma descrição passo a passo de como funciona a compressão LZW:

  1. Inicialize o dicionário para conter todas as strings de um único caractere.
  2. Encontre a string mais longa W no dicionário que corresponda à entrada atual.
  3. Emita o índice do dicionário para W na saída e remova W da entrada.
  4. Adicione W seguido do próximo símbolo na entrada ao dicionário.
  5. Vá para a Etapa 2.

Vamos considerar um exemplo. Suponha que queiramos comprimir a string "ABABABABA" usando LZW.

  1. Inicialize o dicionário para conter "A" e "B".
  2. A correspondência mais longa é "A". Emita seu índice (0) e remova-o da entrada. O dicionário agora contém "A", "B" e "AB".
  3. A correspondência mais longa é "B". Emita seu índice (1) e remova-o da entrada. O dicionário agora contém "A", "B", "AB" e "BA".
  4. A correspondência mais longa é "AB". Emita seu índice (2) e remova-o da entrada. O dicionário agora contém "A", "B", "AB", "BA" e "ABA".
  5. A correspondência mais longa é "ABA". Emita seu índice (4) e remova-o da entrada. O dicionário agora contém "A", "B", "AB", "BA", "ABA" e "ABAB".
  6. A correspondência mais longa é "BA". Emita seu índice (3). A entrada agora está vazia.

A representação comprimida de "ABABABABA" é, portanto, a sequência de índices[1], que requer menos bits para representar do que a representação ASCII original.

A descompressão funciona de maneira semelhante, mas em ordem inversa:

  1. Inicialize o dicionário para conter todas as strings de um único caractere.
  2. Leia um código X da entrada.
  3. Emita a string para X do dicionário.
  4. Se o código anterior existir, adicione a string anterior concatenada com o primeiro caractere da string para X ao dicionário.
  5. Vá para a Etapa 2.

A compressão LZW é simples e rápida, tornando-a uma boa escolha para muitas aplicações. No entanto, ela possui algumas limitações. O tamanho do dicionário pode crescer bastante, consumindo uma quantidade significativa de memória. Além disso,Aqui está a tradução em português do arquivo Markdown, com os comentários do código traduzidos:

o dicionário é redefinido após cada bloco de entrada, o que pode reduzir a taxa de compressão para arquivos pequenos.

Apesar dessas limitações, o LZW continua sendo um algoritmo de compressão popular e eficaz, particularmente para aplicações em que a velocidade é mais importante do que alcançar as maiores taxas de compressão possíveis.

Conclusão

Neste capítulo, exploramos vários algoritmos importantes de processamento de strings, incluindo ordenação de strings, tries, pesquisa de substrings, expressões regulares e compressão de dados. Esses algoritmos formam a base para muitas aplicações do mundo real e são ferramentas essenciais para qualquer programador que trabalhe com dados textuais.

Começamos discutindo a ordenação de strings, que são algoritmos de ordenação otimizados que aproveitam as propriedades especiais das strings. Contagem por índice de chave, ordenação radix LSD e ordenação radix MSD fornecem métodos eficientes para ordenar strings com base em seus caracteres individuais.

Em seguida, examinamos as tries, uma estrutura de dados em árvore para armazenar e recuperar strings. As tries permitem correspondência rápida de prefixos e são comumente usadas em aplicações como autocompletar e tabelas de roteamento IP.

Algoritmos de pesquisa de substrings, como os algoritmos de Knuth-Morris-Pratt e Boyer-Moore, nos permitem pesquisar eficientemente padrões em strings maiores. Esses algoritmos têm inúmeras aplicações em edição de texto, biologia computacional e recuperação de informações.

As expressões regulares fornecem uma maneira poderosa e flexível de descrever padrões de strings. Discutimos a sintaxe básica das expressões regulares e como elas podem ser usadas para correspondência de padrões e manipulação de strings em várias linguagens de programação e ferramentas.

Finalmente, exploramos algoritmos de compressão de dados, que reduzem o tamanho dos dados explorando a redundância e os padrões dentro da entrada. Abordamos a codificação por comprimento de sequência, a codificação de Huffman e a compressão de Lempel-Ziv-Welch, cada uma com suas próprias forças e aplicações.

Entender esses algoritmos e estruturas de dados de processamento de strings é crucial para qualquer pessoa que trabalheAqui está a tradução em português do arquivo Markdown, com os comentários traduzidos, mas o código mantido no original:

Trabalhando com dados textuais

À medida que a quantidade de dados não estruturados continua a crescer, a capacidade de manipular, pesquisar e comprimir strings de forma eficiente se tornará cada vez mais valiosa. Ao dominar as técnicas abordadas neste capítulo, você estará bem equipado para enfrentar uma ampla gama de desafios de processamento de strings em seus próprios projetos e aplicações.

# Exemplo de manipulação de strings
text = "O rápido cachorro marrom salta sobre o cão preguiçoso."
print(text.upper())  # Imprime o texto em maiúsculas
print(text.replace("cachorro", "gato"))  # Substitui "cachorro" por "gato"
 
# Exemplo de pesquisa em strings
if "preguiçoso" in text:
    print("A palavra 'preguiçoso' foi encontrada no texto.")
else:
    print("A palavra 'preguiçoso' não foi encontrada no texto.")
 
# Exemplo de compressão de strings
import zlib
compressed_text = zlib.compress(text.encode())
print(len(text), "bytes ->", len(compressed_text), "bytes")
Chapter 8 Algorithm Analysis TechniquesChapter 10 Intractable Problems and Approximation Algorithms