4 Projetos de algoritmos

Prévia do material em texto

Projetos de algoritmos
APRESENTAÇÃO
No projeto de algoritmos, são utilizadas técnicas de otimização capazes de encontrar uma 
solução ótima para problemas com características distintas. Para isso, os algoritmos precisam ser 
eficientes em tempo de execução para garantir um bom resultado.
Um exemplo seria a estratégia de divisão e conquista, que divide um problema em partes 
menores e cada parte é tratada de forma individual e independente, e as soluções encontradas em 
cada parte são combinadas para disponibilizar a solução final do problema. Uma das aplicações 
da estratégia divisão e conquista é encontrar o maior ou o menor valor em um vetor.
Nesta Unidade de Aprendizagem, você vai conhecer os métodos para projetar algoritmos e 
como os algoritmos de divisão e conquista, algoritmo guloso, programação dinâmica e 
programação de aproximação se comportam na resolução de problemas de otimização. Além 
disso, você irá estudar as soluções de problemas de aproximação, como a cobertura de vértices e 
o problema de soma de subconjuntos.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Descrever os métodos para projetar algoritmos.•
Demonstrar os métodos de projeto de algoritmos.•
Identificar soluções de problemas de aproximação.•
DESAFIO
O algoritmo guloso utiliza a melhor solução em determinado momento, sem explorar as demais 
soluções, e, após a escolha da melhor solução, não volta atrás. Um algoritmo guloso faz 
escolhas gulosas em cada passo e garante sua eficiência. 
INFOGRÁFICO
O algoritmo de divisão e conquista decompõe um problema em partes menores, e cada parte é 
tratada de forma individual e independente. 
Um dos algoritmos que utiliza esse método é o Quicksort, que tem 
o objetivo de ordenar um conjunto de elementos considerando os elementos menores e maiores 
do conjunto em relação ao pivô.
No Infográfico a seguir, você irá conhecer o algoritmo Quicksort, 
que utiliza a técnica de divisão e conquista.
CONTEÚDO DO LIVRO
A otimização de problemas é um dos tópicos tratados no projeto de algoritmos e tem o objetivo 
de minimizar ou maximizar a solução ótima de acordo com o problema a ser tratado para 
problemas de diferentes tipos, incluindo os problemas NP-completos. Existem métodos que 
auxiliam na solução desses problemas, encontrando resultados ótimos e satisfatórios para a 
solução final.
No capítulo Projeto de algoritmos, da obra Análise de algoritmos, base teórica desta Unidade de 
Aprendizagem, serão apresentados os métodos para projetar algoritmos e como esses métodos 
se comportam na resolução de distintos problemas de otimização. Você também irá aprender 
como os algoritmos de aproximação conseguem encontrar soluções aproximadas para os 
problemas de cobertura de vértices e o problema de soma de subconjuntos.
Boa leitura.
ANÁLISE DE 
ALGORITMOS
Cynthia da Silva Barbosa
Projetos de algoritmos
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
  Descrever métodos para projetar algoritmos.
  Demonstrar os métodos de projeto de algoritmos.
  Identificar soluções de problemas por aproximação. 
Introdução
Para projetar algoritmos eficientes, são utilizados métodos de otimização 
que auxiliam na solução de problemas com características distintas, como 
os algoritmos de divisão e conquista, algoritmo guloso, programação 
dinâmica e programação de aproximação. As soluções de problemas de 
aproximação minimizam ou maximizam os resultados de acordo com as 
características do problema. 
Para exemplificar, imagine o caso em que um cliente realiza uma 
compra em um supermercado e efetua o pagamento em dinheiro nos 
guichês automáticos. Nesse caso, a devolução do troco pode ser feita 
utilizando um algoritmo guloso, que iniciaria pela maior nota e, por último, 
liberaria as moedas. No caso da programação dinâmica, um problema 
em que pode ser aplicado seria o da mochila booleana, onde é inserida a 
maior quantidade de objetos, de acordo com o peso e o valor de cada um.
Neste capítulo, você vai estudar sobre os métodos para projetar algo-
ritmos, os métodos de projeto de algoritmos e as soluções de problemas 
de aproximação.
1 Métodos para projetar algoritmos
Os métodos para projetar algoritmos são aplicados em diversos problemas de 
otimização e utilizam procedimentos matemáticos para a solução de problemas. 
As técnicas utilizadas para a análise e o projeto de algoritmos são divisão e 
conquista, algoritmo guloso, programação dinâmica e programação de apro-
ximação, todas detalhadas a seguir (CORMEN et al., 2009).
Divisão e conquista
A estratégia de divisão e conquista decompõe um problema em partes menores 
(divisão), e cada parte é tratada de forma individual e independente (conquista). 
As soluções encontradas em cada parte são combinadas para disponibilizar a 
solução fi nal do problema (combinação). Trata-se, portanto, de uma estratégia 
baseada na recursividade. 
Para que a estratégia de divisão e conquista seja eficiente, é preciso que a 
etapa de divisão e a etapa de combinação sejam rápidas. Uma vantagem dessa 
estratégia é que o tempo de execução é facilmente determinado. Desvantagens 
incluem os fatos de que ela é lenta no pior caso e de que pode ocorrer estouro 
de memória em função da recursividade.
Exemplos de estratégias de divisão e conquista incluem:
  pesquisa em árvore binária;
  ordenação rápida (quicksort);
  ordenação por intercalação (mergesort);
  algoritmo da mediana.
Programação dinâmica
A programação dinâmica auxilia na resolução de problemas de otimização 
combinatória e permite que sejam descobertas as melhores escolhas para 
um problema. Além disso, na programação dinâmica, os subproblemas não 
são independentes, e cada subproblema é resolvido apenas uma vez, tendo 
sua solução armazenada em uma tabela para evitar a recursão. As soluções 
encontradas são chamadas de soluções ótimas, pois contêm um valor ótimo, 
sendo o valor mínimo ou máximo que satisfaz a resolução do problema.
Projetos de algoritmos2
A estratégia da programação dinâmica segue quatro passos (CORMEN 
et al., 2009):
1. Diferenciar a estrutura de uma solução ótima.
2. Resolver de forma recursiva o valor de uma solução ótima.
3. Calcular o valor de uma solução ótima utilizando o processo de baixo 
para cima.
4. Criar uma solução ótima baseada nas soluções calculadas.
Os passos 1, 2 e 3 compõem a estrutura da programação dinâmica de um 
problema. O passo 4 é executado para auxiliar com dados adicionais, que 
contribuem para encontrar a solução ótima.
A programação dinâmica utiliza uma subestrutura ótima; ou seja, a solução 
ótima encontrada inclui as soluções ótimas encontradas nos subproblemas.
Estes são alguns exemplos das estratégias utilizadas pela programação 
dinâmica:
  programação de linha de montagem;
  multiplicação de cadeia de matrizes;
  algoritmo da subsequência crescente máxima;
  algoritmo de Dijkstra.
Algoritmos gulosos
O algoritmo guloso é uma técnica que defi ne a solução ótima no momento, 
levando em consideração os critérios locais para encontrar a solução ótima 
global. O algoritmo guloso é simples e rápido, mas, em determinados proble-
mas, não consegue encontrar uma solução ótima. 
Os algoritmos gulosos são míopes, uma vez que as decisões tomadas são 
baseadas na iteração corrente, independentemente das soluções futuras. Além 
disso, os algoritmos gulosos não voltam atrás na escolha da solução. 
O algoritmo guloso segue os seguintes passos (CORMEN et al., 2009):
1. Determinar a subestrutura ótima do problema.
2. Desenvolver uma solução recursiva.
3. Demonstrar que uma das soluções ótimas é a escolha gulosa.
3Projetos de algoritmos
4. Mostrar que os subproblemas induzidos para a escolha gulosa são 
vazios, com exceção de um subproblema.
5. Desenvolver um algoritmo recursivo implementando a solução gulosa.
6. Alterar um algoritmo recursivo para um algoritmo interativo.
Exemplosdo algoritmo guloso incluem:
  problema da mochila fracionária;
  problema da árvore de Huffman;
  problema do escalonamento de intervalos;
  algoritmos de Prim e Kruskal.
Você sabe quais são as diferenças entre algoritmo guloso e algoritmo de programação 
dinâmica? Conforme Feofiloff (2015), o algoritmo guloso:
  utiliza a solução em determinado momento, sem explorar as demais soluções;
  é rápido;
  após a escolha de uma melhor solução, não volta atrás.
Por sua vez, o algoritmo de programação dinâmica:
  verifica todas as soluções de forma eficiente;
  é lento;
  após a escolha de uma melhor solução, pode rever a escolha da solução.
Programação de aproximação
Os algoritmos de aproximação foram desenvolvidos para suprir a impossibilidade 
de solucionar problemas de otimização NP-difíceis. Os algoritmos de aproxi-
mação não criam uma solução ótima, mas produzem soluções que pertencem 
a determinado fator de solução ótima, conhecida como solução aproximada. 
(MIYAZAWA, [2020?]). Para problemas de otimização, o algoritmo de aproxi-
mação é efi ciente e disponibiliza uma boa solução (CARVALHO et al., 2020).
Segundo Cormen et al. (2009), existem três abordagens para aprimorar 
um algoritmo para um problema NP-completo:
Projetos de algoritmos4
1. Se os dados de entrada são pequenos, o algoritmo com tempo de exe-
cução exponencial se adéqua ao problema.
2. É possível separar problemas importantes para resolvê-los em tempo 
polinomial.
3. Soluções aproximadas podem ser encontradas em tempo polinomial.
Estes são alguns exemplos do algoritmo de aproximação:
  problema de cobertura de vértices;
  métodos combinatórios;
  métodos de programação linear;
  problema de soma de subconjuntos.
2 Demonstração dos métodos de projeto 
de algoritmos
Nesta seção, você descobrirá como aplicar os algoritmos divisão e conquista, 
guloso, programação dinâmica e de aproximação.
Divisão e conquista
Um dos algoritmos utilizados para demonstrar o método de divisão e conquista 
é o Mergesort, cujo objetivo é ordenar um vetor por intercalação. O Mergesort 
pode ser resolvido utilizando o algoritmo de divisão e conquista.
Suponha que seja necessário reordenar um vetor A[p..r] A [39, 13, 25, 84, 
51, 29, 32, 56] em ordem crescente. Note que p ≤ q < r:
p q q + 1 r
39 13 25 84 51 29 32 56
O algoritmo de divisão e conquista supõe que p < r utilizando a recursão, 
conforme exemplo apresentado no algoritmo da Figura 1 (FEOFILOFF, 2015). 
O algoritmo Intercala (passo 5) é apresentado na Figura 3.
5Projetos de algoritmos
Figura 1. Algoritmo Mergesort.
Fonte: Adaptada de Feofiloff (2015).
Para compreender o funcionamento do algoritmo Mergesort (Figura 1), 
observe a representação dos passos de execução do algoritmo sobre um vetor 
de exemplo, representado na Figura 2. O algoritmo Mergesort divide o vetor 
inicial em dois vetores menores (dividir), que, por sua vez, são divididos em 
outros dois vetores (dividir). Depois, os vetores menores são ordenados de 
forma recursiva (conquistar). O resultado em cada vetor menor é combinado 
(combinar) para compor a solução final: ordenação do vetor inicial.
Figura 2. Ordenação utilizando o Mergesort.
O algoritmo Intercala é responsável por pegar os vetores crescentes A[p..q] e 
A[q+1..r] e ordená-los de forma crescente utilizando um vetor auxiliar B. Nas linhas 
6 e 7, o vetor é ordenado de p até q. Nas linhas 8 e 9, o vetor é ordenado de q+1 até 
r. Nas linhas 12 a 17, a ordenação é refinada e armazenada no vetor original A.
Projetos de algoritmos6
Figura 3. Algoritmo Intercala.
Fonte: Adaptada de Feofiloff (2015).
Programação dinâmica
Para demonstrar o funcionamento do algoritmo de programação dinâmica, 
será apresentado o produto de n matrizes (ZIVIANI, 2007).
Considere a matriz M = M1 × M2 × ... × Mn, onde Mi é uma matriz com 
di – 1 linhas e di colunas. A ordem da multiplicação pode gerar grandes 
implicações na quantidade total de operações de adição e multiplicação para 
obter M.
Para exemplificar, veja o produto M = M1[10, 20] × M2[20, 50] × M3[50, 1] 
× M4[1, 100], onde as dimensões de cada matriz estão representadas entre col-
chetes. Na matriz M, existem as seguintes possibilidades para gerar o produto:
1. M = M1 × (M2 × (M3 × M4))
2. M = (M1 × (M2 × M3)) × M4
Na opção 1, requer 125.000 operações, enquanto, na opção 2, requer 2.200. 
O objetivo é minimizar a quantidade de operações realizadas (ZIVIANI, 2007).
7Projetos de algoritmos
A programação dinâmica computa os valores de mij em ordem crescente 
das diferenças nos subscritos e tenta encontrar uma solução ótima sem a 
necessidade de gerar todas as possibilidades de produtos entre a matriz M.
Seja mij menor custo para computar Mi × Mi+1 × · · · × Mj, para 1 ≤ i ≤ j 
≤ n. A recursividade do menor custo do produto de Mi,j é:
onde:
  mik é o custo mínimo para calcular M’ = Mi × Mi+1 × · · · × Mk;
  mk+1,j é o custo mínimo para calcular M’’ = Mk+1 × Mk+2 × · · · × Mj;
  di−1dkdj é o custo de multiplicar M’[di−1, dk] por M’’[dk, dj];
  mij, j > i é o custo mínimo de todos os valores possíveis de k entre i e 
j − 1, da soma dos três termos.
O algoritmo que resolve o problema de produto de matrizes é apresentado 
na Figura 4. 
Figura 4. Algoritmo produto de matrizes.
Fonte: Adaptada de Cormen et al. (2009).
Projetos de algoritmos8
O pseudocódigo leva em consideração uma matriz Ai com dimensões di–1 
× di para i = 1,2,3..., n. A entrada para o algoritmo é uma sequência d = {d0, 
d1, ..., dn}, onde comprimento [d]= n+1. Uma matriz auxiliar m[1..n, 1..n] é 
utilizada para armazenar os custos m[i,j] e uma tabela auxiliar s[1..n, 1..n] que 
registra qual índice de k chegou no custo ótimo do cálculo m[i,j]. A tabela s é 
usada para construir uma tabela ótima. A equação apresentada anteriormente 
mostra o custo m[i,j] para calcular o produto de matrizes para j–i+1 matrizes.
Nas linhas 2 e 3, são calculadas o custo mínimo de m[i,i] 0, onde i = 1, 
2, 3, ..., n. Nas linhas 4 a 12, são calculados os custos mínimos utilizando 
a recursividade: m[i, i+1] para i = 1, 2, ..., n–1. Em cada fase, o custo m[i,j] 
calculado nas linhas 9 a 12 depende da entrada da tabela m[i,k] e m[k + 1,j]. 
A matriz S contém o resultado da solução ótima (CORMEN et al., 2009).
Após a execução do programa, este foi o resultado encontrado para a matriz 
M = M1[10, 20] × M2[20, 50] × M3[50, 1] × M4[1, 100]:
m11 = 0 m22 = 0 m33 = 0 m44 = 0
m12 = 10.000 m23 = 1.000 m34 = 5.000
m13 = 1.200 m24 = 3.000
m14 = 2.200
O produto da matriz m12 representa a multiplicação de M1 × M2 e possui 
10.000 operações (custo do produto de matrizes), de acordo com a multiplicação: 
10 (linhas de M1) × 20 (linhas de M1) × 50 (colunas de M2). O produto da 
matriz m23 representa a multiplicação de M2 × M3 e possui 1.000 operações, 
de acordo com a multiplicação: 20 (linhas de M2) × 50 (linhas de M2) × 1 
(coluna de M3). 
O produto da matriz m34 representa a multiplicação de M3 × M4 e possui 
5.000 operações, de acordo com a multiplicação: 50 (linhas de M3) × 1 (linhas 
de M3) × 100 (colunas de M4). No caso de m13, deve ser definida a ordem de 
multiplicar da matriz M1 até M3: se será feita a multiplicação entre (M1 × 
(M2 × M3)) ou entre ((M1 × M2) × M3). Se a multiplicação for entre (M1 × 
(M2 × M3)), na tabela consta o custo de multiplicar M2 × M3 (m23) = 1.000 + 
(10 (linhas de M1) × 20 (linhas de M1 × 1 (colunas de M2, M3)), totalizando 
1.200 operações. Se for utilizar o produto entre ((M1 × M2) × M3), o custo será: 
10.000 (m12) + (10 (linhas de M1, M2) × 50 (linhas de M1, M2 × 1 (colunas de 
M3)), totalizando 10.500 operações. Assim, para obter o menor custo, basta 
multiplicar (M1 × (M2 × M3)). 
9Projetos de algoritmos
No caso de m24, deve ser definida qual será a ordem de multiplicar da 
matriz M2 até M4: se será feita a multiplicação entre (M2 × (M3 × M4)) 
ou entre ((M2 × M3) × M4). No caso, o menor custo é obtido multiplicando 
((M2 × M3) × M4): 1.000 (m23) + (20 (linhas de M2, M3) × 1 (linhas de M2,M3 × 100 (colunas de M4)), totalizando 3.000 operações. 
No caso de m14, a melhor ordem para multiplicar da matriz M1 até M4 é 
(M1 × ( M2 × M3)) e, em seguida, (M13 × M4), totalizando 1.200 operações.
Algoritmos gulosos
Para demonstrar o funcionamento do algoritmo guloso, será apresentado o 
problema da mochila fracionária, conforme apresentado em Feofi loff (2015). 
O problema da mochila fracionária permite carregar objetos com pesos e 
valores distintos, com o objetivo de carregar a mochila com o maior número 
de objetos, segundo sua capacidade.
Para exemplificar, são apresentados os vetores naturais (p1, p2, … , pn), 
que representa o vetor de pesos dos objetos, (v1, v2, … , vn), que representa um 
vetor de valores dos objetos, e um número natural c, referente à capacidade da 
mochila. O objetivo é achar um vetor racional (x1, x2, … , xn) que maximize 
x * v sob as restrições x * p ≤ c e 0 ≤ xi ≤ 1 para todo i. 
O algoritmo guloso que resolve o problema da mochila fracionária é apre-
sentado na Figura 5. 
Figura 5. Algoritmo guloso resolvendo o problema 
da mochila fracionária.
Fonte: Adaptada de Feofiloff (2015).
Projetos de algoritmos10
O algoritmo leva em consideração a ordem dos objetos 1, 2, … , n. O al-
goritmo determina que os objetos estejam em ordem crescente do valor por 
unidade de peso. A cada objeto inserido na mochila, o peso do objeto é de-
crementado de sua capacidade total (linhas 1 a 4).
A cada iteração, o algoritmo guloso pega o objeto de maior peso entre os 
disponíveis e não se preocupa com o que acontecerá futuramente, além de 
não se arrepender de suas escolhas. 
Programação de aproximação
Para demonstrar o funcionamento do algoritmo de aproximação, será apresen-
tado o problema da mochila booleana, conforme Feofi loff (2015). O problema 
da mochila booleana consiste em defi nir quais itens serão inseridos na mochila 
de acordo com o peso de cada item e com a capacidade da mochila.
Para exemplificar, são apresentados os números naturais (p1, p2, … , pn), 
que representa os pesos dos objetos, (v1, v2, … , vn), que representa os valo-
res dos objetos, e um número natural c, referente à capacidade da mochila. 
O objetivo é achar um valor máximo de um subconjunto X de {1, … , n} que 
maximize v(X) com a restrição p(X) ≤ c. 
O algoritmo de aproximação que resolve o problema da mochila booleana 
é apresentado na Figura 6. 
Figura 6. Algoritmo de aproximação resolvendo o 
problema da mochila booleana.
Fonte: Adaptada de Feofiloff (2015).
11Projetos de algoritmos
O algoritmo de aproximação cria uma mochila que pode não conter o 
valor máximo, mas contém, pelo menos, metade do valor máximo. Além 
disso, o algoritmo possui características gulosas; ou seja, escolhe os objetos 
com o maior valor. Nesse exemplo, os dados de entrada do algoritmo estão 
em ordem decrescente de valor. Nas linhas 3 a 5, o algoritmo encontra o 
maior k tal que p1+ … +pk−1 ≤ c.
O algoritmo da MOCHILA-QUASE-ÓTIMA resulta em uma solução de 
aproximação de 50% do ótimo.
3 Soluções de problemas de aproximação
As soluções de problemas de aproximação garantem uma solução ótima den-
tro do aceitável e são conhecidas como solução aproximada para problemas 
NP-completo. Se um problema de otimização possui soluções com custo 
positivo, as soluções aproximadas podem ser de minimização ou maximização, 
dependendo do problema (CORMEN et al., 2009).
Nesta seção, serão apresentadas as soluções de problemas de aproximação 
para os problemas de cobertura de vértices e o problema de soma de subcon-
juntos (CORMEN et al., 2009).
Problema de cobertura de vértices
O problema de cobertura de vértices de um grafo é um conjunto de vértices 
que incide pelo menos a uma aresta do conjunto. O objetivo é encontrar uma 
cobertura de vértices mínima ou cobertura de vértice ótima de um grafo. 
Para exemplifi car o funcionamento do algoritmo de aproximação APROXI-
MAÇÃO_COBERTURA_VÉRTICE (apresentado na Figura 8), considere os 
grafos apresentados na Figura 7.
Projetos de algoritmos12
Figura 7. Operação do algoritmo de aproximação resolvendo o problema de cobertura 
de vértices.
Fonte: Adaptada de Cormen et al. (2009).
O grafo de entrada G (Figura 7a) possui 7 vértices e 8 arestas. O algoritmo 
seleciona a aresta (b, c) para iniciar (Figura 7b). Os vértices b e c são inseridos 
no conjunto C com os vértices que estão sendo criados. As arestas (a, b), (c, 
e) e (c, d) que estão tracejadas são removidas por estarem cobertas por um 
vértice em C. A aresta (e, f ) é selecionada (Figura 7c). Os vértices e e f são 
inseridos a C. A aresta (d, g) é escolhida (Figura 7d). Os vértices d e g são 
inseridos a C. O conjunto C contém a cobertura dos vértices gerados pelo 
algoritmo APROXIMAÇÃO_COBERTURA_VÉRTICE, com seis vértices: 
b, c, d, e, f, g e h (Figura 7e). A Figura 7f mostra a cobertura ótima para o 
problema com três vértices: b, d e e.
13Projetos de algoritmos
O algoritmo de aproximação possui, como entrada, um grafo não orientado 
G e, como saída, devolve uma cobertura de vértices ótima (Figura 8). Na 
linha 1, a variável C é inicializada com 0. A variável C contém a cobertura 
de vértices que serão criados. Na linha 2 E’, recebe uma cópia do conjunto 
de arestas E[G] do grafo. Nas linhas 3 a 6, seleciona uma aresta (u, v) de E’, 
insere suas extremidades u e v em C e remove todas arestas em E’ que estão 
cobertas por u ou v. 
Figura 8. Algoritmo de aproximação resolvendo o problema de cobertura de vértices.
Fonte: Adaptada de Cormen et al. (2009).
Problema de soma de subconjuntos
O problema de soma de subconjuntos (subset sum) é um par (S, t) que consiste 
em um conjunto de números inteiros S {x1, x2, ...., xn} e precisa verifi car se 
existe um subconjunto de S que adicione exatamente o valor de destino t. 
Para exemplifi car, imagine um caminhão que não pode transportar uma carga 
maior que t quilos e possui n diferentes tipos de caixas para transportar, e 
que cada caixa pesa xi quilos. O objetivo é carregar o caminhão com a carga 
mais pesada sem ultrapassar a carga máxima que um caminhão consegue 
transportar (CORMEN et al., 2009).
Projetos de algoritmos14
Será apresentado um algoritmo (SOMA_SUBCONJUNTOS (S, t)) de 
tempo exponencial para calcular soma de subconjuntos, ilustrado na Figura 9. 
Para calcular a soma dos subconjuntos, para cada subconjunto de S’ de S, a 
soma dos elementos em S’ não pode exceder t.
Figura 9. Algoritmo de aproximação resolvendo o problema de soma 
de subconjuntos.
Fonte: Adaptada de Cormen et al. (2009).
O algoritmo SOMA_SUBCONJUNTOS (S, t) recebe como entrada um 
conjunto S = {x1, x2, ...., xn} e um valor t. O algoritmo calcula a lista Li, soma 
dos subconjuntos de {x1, x2, ...., xi} que não excedam o valor t, e retorna o valor 
máximo em Ln. Se L = (1, 2, 3, 5, 9), então L+2 = (3, 4, 5, 7, 11). O procedimento 
MERGE-LISTS (L, L’) retorna a lista ordenada das listas L e L’ retirando os 
valores duplicados.
Neste capítulo, vimos que os algoritmos de projeto de algoritmos podem 
ser usados para diversos problemas de otimização e contribuem para encontrar 
soluções ótimas de um problema. Para cada problema, existe um algoritmo 
específico. Além disso, existem diversas soluções propostas para solucionar 
problemas de aproximação NP-completos, como os algoritmos de aproximação 
de cobertura de vértices e soma de subconjuntos.
15Projetos de algoritmos
CARVALHO, M. H. et al. Uma introdução sucinta a algoritmos de aproximação. [S. l. : s. 
n.]: 2001. Disponível em: https://www.ime.usp.br/~cris/aprox/livro.pdf. Acesso em: 
4 ago. 2020.
CORMEN, T. H. et al. Introduction to algorithms. 3. ed. Cambridge (MA): MIT Press, 2009.
FEOFILOFF, P. Aulas: análise de algoritmos. In: INSTITUTO de Matemática e Estatística da 
USP. São Paulo, 13 abr. 2015. Disponível em: https://www.ime.usp.br/~pf/analise_de_al-
goritmos/lectures.html. Acesso em: 4 ago. 2020.
MIYAZAWA, F. K. Algoritmos de aproximação. In: INSTITUTO de Computação da Uni-
versidade de Campinas.Campinas, [2020?]. Disponível em: https://www.ic.unicamp.
br/~fkm/problems/algaprox.html. Acesso em: 4 ago. 2020.
ZIVIANI, N. Projeto de algoritmos com implementações em Java e C++. São Paulo: Cengage 
Learning, 2007. 
Os links para sites da web fornecidos neste capítulo foram todos testados, e seu fun-
cionamento foi comprovado no momento da publicação do material. No entanto, a 
rede é extremamente dinâmica; suas páginas estão constantemente mudando de 
local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade 
sobre qualidade, precisão ou integralidade das informações referidas em tais links.
Projetos de algoritmos16
DICA DO PROFESSOR
A programação dinâmica permite que as melhores escolhas para um problema sejam 
encontradas. Para isso, a programação dinâmica utiliza o princípio da otimalidade. O princípio 
da otimalidade pode ser definido como: entre um conjunto de soluções ótimas, cada solução em 
um subconjunto também deve ser ótima.
Na Dica do Professor, você irá conhecer o princípio da otimalidade aplicado na programação 
dinâmica.
Conteúdo interativo disponível na plataforma de ensino!
 
EXERCÍCIOS
1) Os métodos para projetar algoritmos são aplicados em diversas aplicações e 
problemas de otimização e utilizam procedimentos matemáticos para solução de 
problemas. Em relação às técnicas divisão e conquista e programação dinâmica, 
analise as afirmações a seguir:
I. O algoritmo de divisão e conquista é baseado na objetividade de tempo e divide em 
partes menores um problema.
II. As soluções ótimas encontradas pelo algoritmo da programação dinâmica podem 
apenas minimizar o resultado de acordo com o problema.
III. Fazem parte dos algoritmos que compõem a programação dinâmica o algoritmo 
de Dijkstra e a programação de linha de montagem.
IV. Por utilizar a recursividade, o algoritmo de divisão e conquista pode ser lento no 
pior caso e pode impactar a performance do computador.
Agora, assinale a alternativa que apresenta a resposta correta:
A) 
Apenas as afirmativas II e III estão corretas.
B) 
Apenas as afirmativas I e IV estão corretas.
C) 
Apenas as afirmativas III e IV estão corretas.
D) 
Apenas as afirmativas I, II e IV estão corretas.
E) 
As afirmativas I, II, III e IV estão corretas.
2) O algoritmo guloso é uma técnica que define a solução ótima no momento, levando 
em consideração os critérios locais para encontrar a solução ótima global. Em relação 
aos algoritmos gulosos, analise as afirmações a seguir:
I. O algoritmo guloso leva em consideração todas as soluções possíveis para 
determinado problema antes de escolher a solução final.
II. São exemplos de algoritmos gulosos: problema da mochila fracionária e os 
algoritmos de Prim e Kruskal.
III. O algoritmo guloso é simples e lento, porém consegue sempre encontrar uma 
solução ótima para todos os problemas de otimização.
IV. Uma vez definida uma solução, o algoritmo guloso não retrocede em sua escolha.
Agora, assinale a alternativa que apresenta a resposta correta:
A) 
Apenas as afirmativas I, II e III estão corretas.
B) 
Apenas as afirmativas II e IV estão corretas.
C) 
Apenas as afirmativas II e III estão corretas.
D) 
Apenas as afirmativas I, III e IV estão corretas.
E) 
As afirmativas I, II, III e IV estão corretas.
As soluções de problemas de aproximação garantem uma solução ótima dentro do 
aceitável e são conhecidas como soluções aproximadas para problemas, em que não 
são encontrados resultados em um tempo polinomial por meio de algoritmos 
deterministas (NP-completo).
Considerando o contexto apresentado, avalie as seguintes asserções sobre as soluções 
de problemas de aproximação:
3) 
will-
Destacar
will-
Destacar
I. As soluções aproximadas podem ser de minimização ou maximização se o 
problema tiver um custo positivo.
PORQUE
II. A solução para o problema de cobertura de vértices tem o objetivo de maximizar o 
maior número de arestas de um grafo.
A respeito dessas asserções, assinale a opção correta:
A) 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
B) 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
C) 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D) 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E) 
As asserções I e II são proposições falsas.
4) Os algoritmos de aproximação foram desenvolvidos para suprir a necessidade de 
solucionar problemas de otimização NP-difíceis. Em relação aos problemas de 
cobertura de vértices e ao problema de soma de subconjuntos, analise as afirmações a 
seguir:
I. O algoritmo aplicado ao problema de soma de subconjuntos tolera pequenas 
variações em relação ao valor total de uma carga.
II. Para que o resultado do algoritmo do problema de cobertura de vértices seja 
válido, é preciso que tenha pelo menos uma referência em uma aresta do conjunto.
III. A saída do algoritmo de cobertura de vértices retorna uma saída de vértice ótima 
e remove todas as arestas que não foram referenciadas no conjunto.
IV. Uma das etapas do algoritmo aplicado ao problema de soma de subconjuntos é 
ordenar a lista de valores e manter os valores duplicados, garantindo a segurança do 
resultado.
Agora, assinale a alternativa que apresenta a resposta correta:
A) 
Apenas as afirmativas I e II estão corretas.
will-
Destacar
B) 
Apenas as afirmativas III e IV estão corretas.
C) 
Apenas as afirmativas II e III estão corretas.
D) 
Apenas a afirmativa II está correta.
E) 
As afirmativas I, II, III e IV estão corretas.
5) Para problemas de otimização, o algoritmo de aproximação é eficiente e disponibiliza 
uma boa solução para o problema. Considerando o contexto apresentado, avalie as 
seguintes asserções sobre o algoritmo de aproximação:
I. Os algoritmos de aproximação geram uma solução ótima, conhecida como solução 
próxima e produzem resultados que estão inseridos em um conjunto de soluções 
ótimas.
PORQUE
II. Um exemplo de algoritmo de aproximação seria o problema da mochila booleana, 
que define os elementos que serão inseridos na mochila de acordo com a sua 
capacidade.
A respeito dessas asserções, assinale a opção correta:
A) 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
B) 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
C) 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D) 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E) 
As asserções I e II são proposições falsas.
NA PRÁTICA
A automatização de processos industriais garante a agilidade e a eficiência dos serviços 
prestados. Para isso, podem ser utilizadas diversas técnicas de otimização de processos, como 
divisão e conquista, algoritmos gulosos e programação dinâmica, por exemplo, de acordo com o 
will-
Destacar
will-
Destacar
problema a ser tratado.
Neste Na Prática, você conhecerá um consultor de desenvolvimento de sistemas que trabalha em 
uma multinacional e que irá resolver o problema do algoritmo guloso configurado na esteira 
automática de separação de produtos.
SAIBA +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Algoritmo guloso
Neste vídeo, é apresentado um exemplo didático do funcionamento do algoritmo guloso.
Conteúdo interativo disponível na plataforma de ensino!
Análise do algoritmo Mergesort
Neste link, é apresentado como o algoritmo Mergesort resolve a ordenação por intercalação.
Conteúdo interativo disponível na plataforma de ensino!