TODAS AS ATIVIDADES

Prévia do material em texto

Análise de algoritmos em problemas NP-completos 
 
Exercícios 
Respostas enviadas em: 08/03/2024 15:01 
1. 
Existe um grande debate sobre como tratar e resolver problemas NP- completos. As teorias 
existentes atualmente, desde a introdução do estudo executado por Stephen Cook (1971) e 
da prova teórica desenvolvida por Karp (1972), afirmam que é possível efetuar uma redução 
polinomial de um problema NP-completo para um problema pertencente à classe P. 
Considerando que esses estudos têm implicações importantes no que diz respeito à 
complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas. 
I. A descoberta desses grandes cientistas não implica necessariamente se ter P = NP, pois, 
para provar que P = NP, basta encontrar um algoritmo polinomial para um único problema 
NP-completo. 
PORQUE 
II. A descoberta dos cientistas mostrou que, uma vez que problemas NP-completos estão 
em NP, seu tempo de execução é polinomial. Porém, alguns problemas requerem mais 
tempo de execução para se chegar a uma solução exata. 
A respeito dessas asserções, assinale a opção correta: 
Resposta incorreta. 
A. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
Cook (1971) e Karp (1972) demonstraram que, para que um problema seja NP-completo, 
implica que P=NP encontre um algoritmo polinomial para um único problema NP-completo e 
considerando uma redução polinomial de um problema NP-completo. Por outro lado, os 
problemas NP-completos não têm tempo polinomial. Alguns problemas pertencentes à 
classe NP-completo podem ser reduzidos em tempo polinomial, mas, por causa de sua 
complexidade (ou tempo de execução), um problema pode requerer mais tempo de execução 
que outros. 
 
Você não acertou! 
B. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
Cook (1971) e Karp (1972) demonstraram que, para que um problema seja NP-completo, 
implica que P=NP encontre um algoritmo polinomial para um único problema NP-completo e 
considerando uma redução polinomial de um problema NP-completo. Por outro lado, os 
problemas NP-completos não têm tempo polinomial. Alguns problemas pertencentes à 
classe NP-completo podem ser reduzidos em tempo polinomial, mas, por causa de sua 
complexidade (ou tempo de execução), um problema pode requerer mais tempo de execução 
que outros. 
 
Resposta incorreta. 
C. 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
Cook (1971) e Karp (1972) demonstraram que, para que um problema seja NP-completo, 
implica que P=NP encontre um algoritmo polinomial para um único problema NP-completo e 
considerando uma redução polinomial de um problema NP-completo. Por outro lado, os 
problemas NP-completos não têm tempo polinomial. Alguns problemas pertencentes à 
classe NP-completo podem ser reduzidos em tempo polinomial, mas, por causa de sua 
complexidade (ou tempo de execução), um problema pode requerer mais tempo de execução 
que outros. 
 
Resposta incorreta. 
D. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
Cook (1971) e Karp (1972) demonstraram que, para que um problema seja NP-completo, 
implica que P=NP encontre um algoritmo polinomial para um único problema NP-completo e 
considerando uma redução polinomial de um problema NP-completo. Por outro lado, os 
problemas NP-completos não têm tempo polinomial. Alguns problemas pertencentes à 
classe NP-completo podem ser reduzidos em tempo polinomial, mas, por causa de sua 
complexidade (ou tempo de execução), um problema pode requerer mais tempo de execução 
que outros. 
 
Resposta correta. 
E. 
As asserções I e II são proposições falsas. 
Cook (1971) e Karp (1972) demonstraram que, para que um problema seja NP-completo, 
implica que P=NP encontre um algoritmo polinomial para um único problema NP-completo e 
considerando uma redução polinomial de um problema NP-completo. Por outro lado, os 
problemas NP-completos não têm tempo polinomial. Alguns problemas pertencentes à 
classe NP-completo podem ser reduzidos em tempo polinomial, mas, por causa de sua 
complexidade (ou tempo de execução), um problema pode requerer mais tempo de execução 
que outros. 
 
 
2. 
A redução polinomial pode ser definida como a possibilidade 
de selecionar um problema A, aplicar a ele uma transformação polinomial, por meio de um 
algoritmo em tempo polinomial determinístico, reduzindo a um problema B, em que uma 
solução 
para resolver B também resolve A. 
Com relação à redução no contexto de classes de problemas, 
analise o texto a seguir, completando suas lacunas: 
Sobre a redução, no contexto de classes de problemas, a classe de complexidade é o 
_______________ dos problemas NP, de maneira que todo problema em NP ______________, 
usando uma redução polinomial a um dos problemas de ________________. Pode-se dizer que 
problemas NP-completos são problemas mais ___________________de NP e muito 
provavelmente não formam parte de complexidade P. 
Assinale a alternativa que preenche corretamente as lacunas: 
Resposta incorreta. 
A. 
conjunto / se iguala / NP-completo/ difíceis. 
Sobre a redução, no contexto de classes de problemas, a classe de complexidade é 
o subconjunto dos problemas NP (porque NP-completo está contido na classe de problemas 
NP), de maneira que todo problema em NP se reduz (porque o processo de reduzir significa 
encontrar uma solução viável e polinomial para o problema), usando uma redução polinomial 
a um dos problemas de NP-completo (que são problemas com soluções obtidas por 
transformação polinomial). Pode-se dizer que problemas NP-completos são problemas 
mais difíceis de NP e muito provavelmente não formam parte de complexidade P (porque 
NP-completo está contido em NP, porém é intratável e comparado a problemas polinomiais 
simples, que são chamados de problemas de classe P). 
 
Resposta incorreta. 
B. 
subconjunto / se iguala / P / fáceis. 
Sobre a redução, no contexto de classes de problemas, a classe de complexidade é 
o subconjunto dos problemas NP (porque NP-completo está contido na classe de problemas 
NP), de maneira que todo problema em NP se reduz (porque o processo de reduzir significa 
encontrar uma solução viável e polinomial para o problema), usando uma redução polinomial 
a um dos problemas de NP-completo (que são problemas com soluções obtidas por 
transformação polinomial). Pode-se dizer que problemas NP-completos são problemas 
mais difíceis de NP e muito provavelmente não formam parte de complexidade P (porque 
NP-completo está contido em NP, porém é intratável e comparado a problemas polinomiais 
simples, que são chamados de problemas de classe P). 
 
Resposta incorreta. 
C. 
subconjunto / se reduz / NP / fáceis. 
Sobre a redução, no contexto de classes de problemas, a classe de complexidade é 
o subconjunto dos problemas NP (porque NP-completo está contido na classe de problemas 
NP), de maneira que todo problema em NP se reduz (porque o processo de reduzir significa 
encontrar uma solução viável e polinomial para o problema), usando uma redução polinomial 
a um dos problemas de NP-completo (que são problemas com soluções obtidas por 
transformação polinomial). Pode-se dizer que problemas NP-completos são problemas 
mais difíceis de NP e muito provavelmente não formam parte de complexidade P (porque 
NP-completo está contido em NP, porém é intratável e comparado a problemas polinomiais 
simples, que são chamados de problemas de classe P). 
 
Você acertou! 
D. 
subconjunto / se reduz / NP-completo / difíceis. 
Sobre a redução, no contexto de classes de problemas, a classe de complexidade é 
o subconjunto dos problemas NP (porque NP-completo está contido na classe de problemas 
NP), de maneira que todo problema em NP se reduz (porque o processo de reduzir significa 
encontrar uma solução viável e polinomial para o problema), usando uma redução polinomial 
a um dos problemas de NP-completo (que são problemas com soluções obtidas por 
transformação polinomial).Pode-se dizer que problemas NP-completos são problemas 
mais difíceis de NP e muito provavelmente não formam parte de complexidade P (porque 
NP-completo está contido em NP, porém é intratável e comparado a problemas polinomiais 
simples, que são chamados de problemas de classe P). 
 
Resposta incorreta. 
E. 
conjunto / se reduz / P/ difíceis. 
Sobre a redução, no contexto de classes de problemas, a classe de complexidade é 
o subconjunto dos problemas NP (porque NP-completo está contido na classe de problemas 
NP), de maneira que todo problema em NP se reduz (porque o processo de reduzir significa 
encontrar uma solução viável e polinomial para o problema), usando uma redução polinomial 
a um dos problemas de NP-completo (que são problemas com soluções obtidas por 
transformação polinomial). Pode-se dizer que problemas NP-completos são problemas 
mais difíceis de NP e muito provavelmente não formam parte de complexidade P (porque 
NP-completo está contido em NP, porém é intratável e comparado a problemas polinomiais 
simples, que são chamados de problemas de classe P). 
 
3. 
O problema de satisfatibilidade booleana (SAT) foi o primeiro problema identificado como 
pertencente à classe de complexidade NP-completo. 
Analise as afirmativas a seguir: 
I. O problema de satisfatibilidade booleana é o problema de determinar se existe 
determinada valoração para as variáveis de determinada fórmula booleana tal que essa 
valoração satisfaça essa fórmula em questão. 
II. O problema SAT é um problema de decisão de classe de complexidade polinomial que 
consiste em determinar a inexistência de alguma atribuição de valores verdade que 
satisfaça uma fórmula lógica na forma normal conjuntiva. 
III. Os problemas em P também podem ser reduzidos a SAT, mas, como já se conhece uma 
boa solução para problemas P, estes não são considerados parte de NP-completo. 
IV. O problema 3SAT é um caso especial ou uma variação do problema SAT original. Uma 
instância de 3SAT é uma expressão booleana em que cada clausula contém pelo menos três 
variáveis. 
Considerando o contexto apresentado, verifica-se que: 
Você não acertou! 
A. 
a afirmativa I é verdadeira. 
A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade 
para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A 
afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que 
consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça 
uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas 
P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois 
problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está 
errada, porque cada cláusula contém exatamente três variáveis. 
 
Resposta incorreta. 
B. 
a afirmativa III é verdadeira. 
A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade 
para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A 
afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que 
consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça 
uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas 
P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois 
problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está 
errada, porque cada cláusula contém exatamente três variáveis. 
 
Resposta correta. 
C. 
as afirmativas I e III são verdadeiras. 
A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade 
para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A 
afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que 
consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça 
uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas 
P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois 
problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está 
errada, porque cada cláusula contém exatamente três variáveis. 
 
Resposta incorreta. 
D. 
as afirmativas II, III e IV são verdadeiras. 
A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade 
para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A 
afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que 
consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça 
uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas 
P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois 
problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está 
errada, porque cada cláusula contém exatamente três variáveis. 
 
Resposta incorreta. 
E. 
as afirmativas I, II e III são verdadeiras. 
A alternativa I está correta, porque o problema SAT visa a encontrar uma solução verdade 
para dada fórmula booleana, e, caso encontrada, a fórmula é considerada “satisfatível”. A 
afirmativa II está incorreta, porque o SAT é um problema de decisão NP-completo que 
consiste em determinar a existência de alguma atribuição de valores verdade que satisfaça 
uma fórmula lógica na forma normal conjuntiva. A afirmativa III está correta, pois problemas 
P podem ser reduzidos usando SAT, mas essa redução se torna desnecessária, pois 
problemas P são determinísticos e aceitam uma solução polinomial. A afirmativa IV está 
errada, porque cada cláusula contém exatamente três variáveis. 
 
4. 
Um dos motivos de se usar algoritmos para tratar um problema de complexidade NP-
completo é que geralmente os problemas intratáveis ou difíceis são comuns na natureza e 
em diversas áreas do conhecimento, e os melhores algoritmos para problemas NP-
completos têm comportamento de pior caso exponencial no tamanho da entrada. De 
acordo com a teoria e os estudos efetuados sobre esses problemas, não é conhecida a 
existência de melhores algoritmos para se resolver um problema NP-completo. 
Analise as afirmativas a seguir e determine qual delas pode ser usada para resolver os 
problemas exponenciais: 
Resposta incorreta. 
A. 
É aconselhável usar um algoritmo de aproximação, pois ele é caracterizado pelo uso de um 
algoritmo que rapidamente encontra uma solução ótima, mas dentro de certo intervalo de 
erro. 
O aconselhável é que se use algoritmo parametrizado. Os algoritmos por aproximação não 
conseguem ter rapidez na determinação de uma solução, e os métodos probabilísticos 
geralmente apresentam bom resultado quando é apresentada a distribuição dos dados de 
entrada. Já casos particulares têm dificuldade em tratar de reconhecer soluções rápidas; 
geralmente é preferível utilizar heurísticas a esse modelo. Os algoritmos que usam 
heurísticas produzem soluções que se aproximam da solução ótima; eles não conseguem 
produzir uma solução ideal. Porém, o uso de algoritmos parametrizados cria um modelo 
adequado para a realidade dos cenários. Muitos problemas considerados intratáveis sob o 
ponto de vista teórico na prática são tratáveis por parâmetro fixo; logo, mostram-se boas 
soluções, pois somente terminam seu procedimento quando conseguem obter um resultado 
muito próximo ao resultado ótimo. 
 
Resposta incorreta. 
B. 
É melhor usar um método probabilístico, que se caracteriza pelo uso de um algoritmo que 
pode obter em média uma boa solução para um problema apresentado de uma distribuição 
de dados de entrada. 
O aconselhável é que se use algoritmo parametrizado. Os algoritmos por aproximação não 
conseguem ter rapidez na determinação de uma solução, e os métodos probabilísticos 
geralmente apresentam bom resultado quando éapresentada a distribuição dos dados de 
entrada. Já casos particulares têm dificuldade em tratar de reconhecer soluções rápidas; 
geralmente é preferível utilizar heurísticas a esse modelo. Os algoritmos que usam 
heurísticas produzem soluções que se aproximam da solução ótima; eles não conseguem 
produzir uma solução ideal. Porém, o uso de algoritmos parametrizados cria um modelo 
adequado para a realidade dos cenários. Muitos problemas considerados intratáveis sob o 
ponto de vista teórico na prática são tratáveis por parâmetro fixo; logo, mostram-se boas 
soluções, pois somente terminam seu procedimento quando conseguem obter um resultado 
muito próximo ao resultado ótimo. 
 
Resposta incorreta. 
C. 
Devem-se usar casos particulares, pois, quando se reconhecem casos particulares do 
problema para os quais existem soluções rápidas, fica mais fácil tratar os problemas NP-
completos. Porém, nem todos os problemas NP-completos têm bons casos particulares. 
O aconselhável é que se use algoritmo parametrizado. Os algoritmos por aproximação não 
conseguem ter rapidez na determinação de uma solução, e os métodos probabilísticos 
geralmente apresentam bom resultado quando é apresentada a distribuição dos dados de 
entrada. Já casos particulares têm dificuldade em tratar de reconhecer soluções rápidas; 
geralmente é preferível utilizar heurísticas a esse modelo. Os algoritmos que usam 
heurísticas produzem soluções que se aproximam da solução ótima; eles não conseguem 
produzir uma solução ideal. Porém, o uso de algoritmos parametrizados cria um modelo 
adequado para a realidade dos cenários. Muitos problemas considerados intratáveis sob o 
ponto de vista teórico na prática são tratáveis por parâmetro fixo; logo, mostram-se boas 
soluções, pois somente terminam seu procedimento quando conseguem obter um resultado 
muito próximo ao resultado ótimo. 
 
Você acertou! 
D. 
É melhor usar algoritmos parametrizados, porque conseguem capturar as diferenças de 
dificuldade entre problemas NPC, já que no desenvolvimento e análise de algoritmos a 
complexidade é descrita em termos do tamanho da entrada. 
O aconselhável é que se use algoritmo parametrizado. Os algoritmos por aproximação não 
conseguem ter rapidez na determinação de uma solução, e os métodos probabilísticos 
geralmente apresentam bom resultado quando é apresentada a distribuição dos dados de 
entrada. Já casos particulares têm dificuldade em tratar de reconhecer soluções rápidas; 
geralmente é preferível utilizar heurísticas a esse modelo. Os algoritmos que usam 
heurísticas produzem soluções que se aproximam da solução ótima; eles não conseguem 
produzir uma solução ideal. Porém, o uso de algoritmos parametrizados cria um modelo 
adequado para a realidade dos cenários. Muitos problemas considerados intratáveis sob o 
ponto de vista teórico na prática são tratáveis por parâmetro fixo; logo, mostram-se boas 
soluções, pois somente terminam seu procedimento quando conseguem obter um resultado 
muito próximo ao resultado ótimo. 
 
Resposta incorreta. 
E. 
É aconselhável usar algoritmos heurísticos, pois esse método consegue produzir algoritmos 
que melhoram as possíveis soluções, até encontrarem alguma solução que seja a ideal. 
Contudo, também não existem formas de se garantir a qualidade da resposta. 
O aconselhável é que se use algoritmo parametrizado. Os algoritmos por aproximação não 
conseguem ter rapidez na determinação de uma solução, e os métodos probabilísticos 
geralmente apresentam bom resultado quando é apresentada a distribuição dos dados de 
entrada. Já casos particulares têm dificuldade em tratar de reconhecer soluções rápidas; 
geralmente é preferível utilizar heurísticas a esse modelo. Os algoritmos que usam 
heurísticas produzem soluções que se aproximam da solução ótima; eles não conseguem 
produzir uma solução ideal. Porém, o uso de algoritmos parametrizados cria um modelo 
adequado para a realidade dos cenários. Muitos problemas considerados intratáveis sob o 
ponto de vista teórico na prática são tratáveis por parâmetro fixo; logo, mostram-se boas 
soluções, pois somente terminam seu procedimento quando conseguem obter um resultado 
muito próximo ao resultado ótimo. 
 
5. 
Quando se trabalha com problemas NP-completos, a complexidade está diretamente ligada 
ao contexto de classes de complexidade. Assim, é importante conhecer o quanto de tempo 
e recurso computacional será utilizado para desenvolver um algoritmo para resolver 
problemas. 
Por sempre estar dependendo da entrada, o esforço computacional para se resolver um 
problema da classe NP-completo é considerado exponencial. 
Logo, a teoria de algoritmos de aproximação é um ótimo método para a solução de 
problemas, pois: 
Resposta correta. 
A. 
um algoritmo de aproximação, embora não encontre a resposta correta sempre (encontra 
uma resposta aproximada), pode ser executado em tempo polinomial. 
É correto afirmar que um algoritmo de aproximação para um problema NP-completo é um 
algoritmo que gera soluções aproximadas, por ser executado dentro de um tempo 
polinomial. É incorreto dizer que um algoritmo de aproximação pode ou não fornecer 
garantias, porque o algoritmo por aproximação é uma alternativa para se encontrar soluções 
com um número de erros limitado, principalmente para problemas para os quais não existem 
algoritmos polinomiais exatos, com garantia de qualidade da solução esperada. É incorreto 
também afirmar que o algoritmo de aproximação deve ser utilizado somente para problemas 
de maximização, pois ele consegue encontrar uma solução muito próxima da solução ótima 
para toda instância do problema, não importando se a solução desejada é para um problema 
de maximização ou minimização. É incorreto afirmar que o tempo de execução é uma função 
da qualidade da solução, pois ele depende da complexidade do problema, conseguindo, 
nesse caso, fornecer uma solução aproximada com uma garantia, já que o algoritmo de 
aproximação não necessita de parametrização dos valores de entrada para ser executado. 
 
Você não acertou! 
B. 
um algoritmo de aproximação pode ou não fornecer garantias sobre a qualidade da solução 
encontrada. 
É correto afirmar que um algoritmo de aproximação para um problema NP-completo é um 
algoritmo que gera soluções aproximadas, por ser executado dentro de um tempo 
polinomial. É incorreto dizer que um algoritmo de aproximação pode ou não fornecer 
garantias, porque o algoritmo por aproximação é uma alternativa para se encontrar soluções 
com um número de erros limitado, principalmente para problemas para os quais não existem 
algoritmos polinomiais exatos, com garantia de qualidade da solução esperada. É incorreto 
também afirmar que o algoritmo de aproximação deve ser utilizado somente para problemas 
de maximização, pois ele consegue encontrar uma solução muito próxima da solução ótima 
para toda instância do problema, não importando se a solução desejada é para um problema 
de maximização ou minimização. É incorreto afirmar que o tempo de execução é uma função 
da qualidade da solução, pois ele depende da complexidade do problema, conseguindo, 
nesse caso, fornecer uma solução aproximada com uma garantia, já que o algoritmo de 
aproximação não necessita de parametrização dos valores de entrada para ser executado. 
 
Resposta incorreta. 
C. 
em um algoritmo de aproximação o tempo de execução pode ser uma função da qualidade 
da solução a ser encontrada. 
É correto afirmar que um algoritmo de aproximação para um problema NP-completo é um 
algoritmo que gera soluções aproximadas, por ser executado dentro de um tempo 
polinomial. É incorreto dizer que um algoritmo de aproximação pode ou não fornecer 
garantias, porque o algoritmo por aproximação é uma alternativa para se encontrar soluções 
com um número de erros limitado, principalmente para problemas para os quais não existem 
algoritmos polinomiais exatos, com garantia de qualidade da solução esperada. É incorreto 
também afirmar que o algoritmo de aproximação deve ser utilizadosomente para problemas 
de maximização, pois ele consegue encontrar uma solução muito próxima da solução ótima 
para toda instância do problema, não importando se a solução desejada é para um problema 
de maximização ou minimização. É incorreto afirmar que o tempo de execução é uma função 
da qualidade da solução, pois ele depende da complexidade do problema, conseguindo, 
nesse caso, fornecer uma solução aproximada com uma garantia, já que o algoritmo de 
aproximação não necessita de parametrização dos valores de entrada para ser executado. 
 
Resposta incorreta. 
D. 
um algoritmo de aproximação pode ser utilizado apenas em problemas de maximização, não 
sendo útil para problemas que buscam a minimização. 
É correto afirmar que um algoritmo de aproximação para um problema NP-completo é um 
algoritmo que gera soluções aproximadas, por ser executado dentro de um tempo 
polinomial. É incorreto dizer que um algoritmo de aproximação pode ou não fornecer 
garantias, porque o algoritmo por aproximação é uma alternativa para se encontrar soluções 
com um número de erros limitado, principalmente para problemas para os quais não existem 
algoritmos polinomiais exatos, com garantia de qualidade da solução esperada. É incorreto 
também afirmar que o algoritmo de aproximação deve ser utilizado somente para problemas 
de maximização, pois ele consegue encontrar uma solução muito próxima da solução ótima 
para toda instância do problema, não importando se a solução desejada é para um problema 
de maximização ou minimização. É incorreto afirmar que o tempo de execução é uma função 
da qualidade da solução, pois ele depende da complexidade do problema, conseguindo, 
nesse caso, fornecer uma solução aproximada com uma garantia, já que o algoritmo de 
aproximação não necessita de parametrização dos valores de entrada para ser executado. 
 
Resposta incorreta. 
E. 
um algoritmo de aproximação pode apenas ser utilizado para tratar problemas NP-completos 
que já tenham parametrização dos valores de entrada. 
É correto afirmar que um algoritmo de aproximação para um problema NP-completo é um 
algoritmo que gera soluções aproximadas, por ser executado dentro de um tempo 
polinomial. É incorreto dizer que um algoritmo de aproximação pode ou não fornecer 
garantias, porque o algoritmo por aproximação é uma alternativa para se encontrar soluções 
com um número de erros limitado, principalmente para problemas para os quais não existem 
algoritmos polinomiais exatos, com garantia de qualidade da solução esperada. É incorreto 
também afirmar que o algoritmo de aproximação deve ser utilizado somente para problemas 
de maximização, pois ele consegue encontrar uma solução muito próxima da solução ótima 
para toda instância do problema, não importando se a solução desejada é para um problema 
de maximização ou minimização. É incorreto afirmar que o tempo de execução é uma função 
da qualidade da solução, pois ele depende da complexidade do problema, conseguindo, 
nesse caso, fornecer uma solução aproximada com uma garantia, já que o algoritmo de 
aproximação não necessita de parametrização dos valores de entrada para ser executado. 
 
 
Análise de algoritmos em problemas NP 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:43 
1. 
Uma classe de problemas NP utiliza algoritmos determinísticos em tempo polinomial para 
verificar se uma solução pode ser válida para determinado problema. Os problemas do ciclo 
hamiltoniano, do caixeiro viajante, da coloração de grafos e da mochila booleana são 
exemplos de problemas da classe NP. 
Em relação a esses problemas, analise as seguintes afirmações: 
I. No ciclo hamiltoniano, o objetivo é encontrar um ciclo que passe por todos os vértices de 
um grafo independentemente do número de vezes que passe pelo vértice. 
II. Um dos problemas da classe NP caixeiro viajante busca uma rota para as cidades em 
determinado conjunto C cujo tamanho da rota seja maior ou igual a k. 
III. Em um grafo, os vértices precisam ter diferentes cores para que o problema de 
coloração de grafos seja válido. 
IV. O problema da mochila booleana tenta achar um valor máximo de objetos para colocar 
na mochila sem violar a capacidade desta. 
Está correto o que se afirma em: 
Resposta incorreta. 
A. 
II e III. 
A afirmação I está incorreta, pois um ciclo hamiltoniano consiste em encontrar um ciclo que 
passe por todos os vértices de um grafo uma única vez. A afirmação II está incorreta, pois o 
problema consiste em saber se existe uma rota para as cidades no conjunto C em que o 
tamanho seja menor ou igual a k. A afirmação III está correta, pois, para que o problema de 
coloração de grafos seja válido, é preciso que as pontas de determinada aresta tenham cores 
diferentes. A afirmação IV está correta, pois o problema da mochila booleana consiste em 
encontrar uma mochila de valor máximo sem ultrapassar o valor da mochila. 
 
Resposta incorreta. 
B. 
I e IV. 
A afirmação I está incorreta, pois um ciclo hamiltoniano consiste em encontrar um ciclo que 
passe por todos os vértices de um grafo uma única vez. A afirmação II está incorreta, pois o 
problema consiste em saber se existe uma rota para as cidades no conjunto C em que o 
tamanho seja menor ou igual a k. A afirmação III está correta, pois, para que o problema de 
coloração de grafos seja válido, é preciso que as pontas de determinada aresta tenham cores 
diferentes. A afirmação IV está correta, pois o problema da mochila booleana consiste em 
encontrar uma mochila de valor máximo sem ultrapassar o valor da mochila. 
 
Resposta correta. 
C. 
III e IV. 
A afirmação I está incorreta, pois um ciclo hamiltoniano consiste em encontrar um ciclo que 
passe por todos os vértices de um grafo uma única vez. A afirmação II está incorreta, pois o 
problema consiste em saber se existe uma rota para as cidades no conjunto C em que o 
tamanho seja menor ou igual a k. A afirmação III está correta, pois, para que o problema de 
coloração de grafos seja válido, é preciso que as pontas de determinada aresta tenham cores 
diferentes. A afirmação IV está correta, pois o problema da mochila booleana consiste em 
encontrar uma mochila de valor máximo sem ultrapassar o valor da mochila. 
 
Resposta incorreta. 
D. 
I, II e IV. 
A afirmação I está incorreta, pois um ciclo hamiltoniano consiste em encontrar um ciclo que 
passe por todos os vértices de um grafo uma única vez. A afirmação II está incorreta, pois o 
problema consiste em saber se existe uma rota para as cidades no conjunto C em que o 
tamanho seja menor ou igual a k. A afirmação III está correta, pois, para que o problema de 
coloração de grafos seja válido, é preciso que as pontas de determinada aresta tenham cores 
diferentes. A afirmação IV está correta, pois o problema da mochila booleana consiste em 
encontrar uma mochila de valor máximo sem ultrapassar o valor da mochila. 
 
Você não acertou! 
E. 
I, II, III e IV. 
A afirmação I está incorreta, pois um ciclo hamiltoniano consiste em encontrar um ciclo que 
passe por todos os vértices de um grafo uma única vez. A afirmação II está incorreta, pois o 
problema consiste em saber se existe uma rota para as cidades no conjunto C em que o 
tamanho seja menor ou igual a k. A afirmação III está correta, pois, para que o problema de 
coloração de grafos seja válido, é preciso que as pontas de determinada aresta tenham cores 
diferentes. A afirmação IV está correta, pois o problema da mochila booleana consiste em 
encontrar uma mochila de valor máximo sem ultrapassar o valor da mochila. 
 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:43 
2. 
A classe de complexidade NP contém a classe de linguagens que são verificadas por um 
algoritmo de tempo polinomial, ou seja, uma linguagem L pertence a NP se, e somente se, 
existir um algoritmo de tempo polinomial com entradas A e c (constante), de forma que L = 
{x ∈ {0, 1}*: existe um certificado y com |y| = O(|x|c) tal que A (x, y) = 1}. 
Com base nessas informações, assinale a alternativa correta: 
Você acertou!A. 
O algoritmo A verifica, em tempo polinomial, a linguagem L. 
O algoritmo A verifica a linguagem L em tempo polinomial. Se existir um certificado para 
determinada solução, é possível verificar se o certificado é adequado ao tamanho da entrada 
para o problema em tempo polinomial. Como dito no enunciado, uma linguagem L pertence a 
NP se, e somente se, existir um algoritmo de tempo polinomial com entradas A e c 
(constante). A questão é se, e somente se, existir um algoritmo de tempo polinomial 
independentemente das entradas. 
 
Resposta incorreta. 
B. 
Um certificado não garante uma solução para determinado problema. 
O algoritmo A verifica a linguagem L em tempo polinomial. Se existir um certificado para 
determinada solução, é possível verificar se o certificado é adequado ao tamanho da entrada 
para o problema em tempo polinomial. Como dito no enunciado, uma linguagem L pertence a 
NP se, e somente se, existir um algoritmo de tempo polinomial com entradas A e c 
(constante). A questão é se, e somente se, existir um algoritmo de tempo polinomial 
independentemente das entradas. 
 
Resposta incorreta. 
C. 
Dependendo das entradas do algoritmo polinomial, a linguagem L pode não pertencer à 
classe NP. 
O algoritmo A verifica a linguagem L em tempo polinomial. Se existir um certificado para 
determinada solução, é possível verificar se o certificado é adequado ao tamanho da entrada 
para o problema em tempo polinomial. Como dito no enunciado, uma linguagem L pertence a 
NP se, e somente se, existir um algoritmo de tempo polinomial com entradas A e c 
(constante). A questão é se, e somente se, existir um algoritmo de tempo polinomial 
independentemente das entradas. 
 
Resposta incorreta. 
D. 
A classe NP contém todas as linguagens que têm um certificado que garante a solução de um 
problema. 
O algoritmo A verifica a linguagem L em tempo polinomial. Se existir um certificado para 
determinada solução, é possível verificar se o certificado é adequado ao tamanho da entrada 
para o problema em tempo polinomial. Como dito no enunciado, uma linguagem L pertence a 
NP se, e somente se, existir um algoritmo de tempo polinomial com entradas A e c 
(constante). A questão é se, e somente se, existir um algoritmo de tempo polinomial 
independentemente das entradas. 
 
Resposta incorreta. 
E. 
O algoritmo A não verifica, em tempo polinomial, a linguagem L. 
O algoritmo A verifica a linguagem L em tempo polinomial. Se existir um certificado para 
determinada solução, é possível verificar se o certificado é adequado ao tamanho da entrada 
para o problema em tempo polinomial. Como dito no enunciado, uma linguagem L pertence a 
NP se, e somente se, existir um algoritmo de tempo polinomial com entradas A e c 
(constante). A questão é se, e somente se, existir um algoritmo de tempo polinomial 
independentemente das entradas. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:43 
3. 
Analisar a complexidade de um problema computacional é definir o algoritmo que tem o 
melhor resultado em relação ao consumo de tempo em função do tamanho da sua entrada, 
no pior caso, na resolução de determinado problema. Porém, ainda não foram descobertos 
os melhores algoritmos para resolver muitos problemas computacionais. 
Sobre a análise de complexidade de problemas NP, avalie as seguintes asserções e a relação 
proposta entre elas: 
I. A complexidade assintótica de ordem exponencial – O(cn) representa a melhor solução 
para os problemas da classe NP. 
PORQUE 
II. Os algoritmos de complexidade O(cn) são conhecidos como um problema não tratável se 
a solução para determinado problema contém o melhor resultado. 
A respeito dessas asserções, assinale a alternativa correta: 
Resposta incorreta. 
A. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
A asserção I é uma proposição falsa, uma vez que a classe NP utiliza algoritmos com 
complexidade assintótica de ordem exponencial – O(cn), c> 1, mas não se pode garantir que 
essa escolha seja a melhor solução encontrada. A asserção II é uma proposição verdadeira, 
pois, caso um algoritmo de complexidade O(cn) seja a melhor solução para determinado 
problema, então esse problema é conhecido como problema não tratável. Problema não 
tratável é um algoritmo de ordem exponencial que tem alto custo computacional, contendo a 
melhor solução para o problema. 
 
Resposta incorreta. 
B. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
A asserção I é uma proposição falsa, uma vez que a classe NP utiliza algoritmos com 
complexidade assintótica de ordem exponencial – O(cn), c> 1, mas não se pode garantir que 
essa escolha seja a melhor solução encontrada. A asserção II é uma proposição verdadeira, 
pois, caso um algoritmo de complexidade O(cn) seja a melhor solução para determinado 
problema, então esse problema é conhecido como problema não tratável. Problema não 
tratável é um algoritmo de ordem exponencial que tem alto custo computacional, contendo a 
melhor solução para o problema. 
 
Resposta incorreta. 
C. 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
A asserção I é uma proposição falsa, uma vez que a classe NP utiliza algoritmos com 
complexidade assintótica de ordem exponencial – O(cn), c> 1, mas não se pode garantir que 
essa escolha seja a melhor solução encontrada. A asserção II é uma proposição verdadeira, 
pois, caso um algoritmo de complexidade O(cn) seja a melhor solução para determinado 
problema, então esse problema é conhecido como problema não tratável. Problema não 
tratável é um algoritmo de ordem exponencial que tem alto custo computacional, contendo a 
melhor solução para o problema. 
 
Você acertou! 
D. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
A asserção I é uma proposição falsa, uma vez que a classe NP utiliza algoritmos com 
complexidade assintótica de ordem exponencial – O(cn), c> 1, mas não se pode garantir que 
essa escolha seja a melhor solução encontrada. A asserção II é uma proposição verdadeira, 
pois, caso um algoritmo de complexidade O(cn) seja a melhor solução para determinado 
problema, então esse problema é conhecido como problema não tratável. Problema não 
tratável é um algoritmo de ordem exponencial que tem alto custo computacional, contendo a 
melhor solução para o problema. 
 
Resposta incorreta. 
E. 
As asserções I e II são proposições falsas. 
A asserção I é uma proposição falsa, uma vez que a classe NP utiliza algoritmos com 
complexidade assintótica de ordem exponencial – O(cn), c> 1, mas não se pode garantir que 
essa escolha seja a melhor solução encontrada. A asserção II é uma proposição verdadeira, 
pois, caso um algoritmo de complexidade O(cn) seja a melhor solução para determinado 
problema, então esse problema é conhecido como problema não tratável. Problema não 
tratável é um algoritmo de ordem exponencial que tem alto custo computacional, contendo a 
melhor solução para o problema. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:43 
4. 
Os problemas da classe NP utilizam algoritmos de verificação em tempo polinomial. Uma 
classe polinomial tem complexidade de tempo O(p(n)), em que p(n) é um polinômio e n é o 
tamanho da entrada. Além disso, a classe NP utiliza algoritmos não determinísticos que 
usam a função escolhe (X) com a complexidade de tempo O(1) e os comandos sucesso e 
insucesso também com a complexidade de tempo O(1). 
Em relação à análise de algoritmo dos problemas NP, analise as seguintes afirmações: 
I. A complexidade do problema do caixeiro viajante é O(c), e a solução encontrada obteve o 
melhor resultado. 
II. A complexidade do problema de coloração de grafos é O(P(x)), uma vez que a solução do 
problema se dá em tempo polinomial. 
III. O objetivo do problema do caixeiro viajante é percorrer a rota de menor custo, não 
sendo necessário analisar (n-1)! possibilidades de rota; logo, a complexidade é O(c). 
IV. O problema da mochila utilizaum algoritmo não determinístico, cuja complexidade de 
tempo do problema é O(n), sendo n o tamanho da entrada. 
Está correto o que se afirma em: 
Resposta incorreta. 
A. 
I, II e III. 
A afirmação I está incorreta, pois o problema do caixeiro viajante é um problema NP 
(problema não determinístico polinomial), cuja complexidade é O(cn), uma vez que a melhor 
solução encontrada não foi provada ser a melhor solução. A afirmação II está correta, pois o 
problema de coloração de grafos é um problema NP (problema não determinístico 
polinomial), e a verificação da solução se dá em tempo polinomial; logo, a complexidade é 
O(P(x)). A afirmação III está incorreta, pois o objetivo do problema do caixeiro viajante é 
percorrer a rota de menor custo, sendo necessário analisar (n-1)! possibilidades de rota; logo, 
a complexidade é exponencial O(cn). A afirmação IV está correta, uma vez que o problema da 
mochila também é considerado um problema NP, usa um algoritmo não determinístico, e sua 
complexidade é O(n), sendo que n representa o tamanho da entrada. 
 
Resposta correta. 
B. 
II e IV. 
A afirmação I está incorreta, pois o problema do caixeiro viajante é um problema NP 
(problema não determinístico polinomial), cuja complexidade é O(cn), uma vez que a melhor 
solução encontrada não foi provada ser a melhor solução. A afirmação II está correta, pois o 
problema de coloração de grafos é um problema NP (problema não determinístico 
polinomial), e a verificação da solução se dá em tempo polinomial; logo, a complexidade é 
O(P(x)). A afirmação III está incorreta, pois o objetivo do problema do caixeiro viajante é 
percorrer a rota de menor custo, sendo necessário analisar (n-1)! possibilidades de rota; logo, 
a complexidade é exponencial O(cn). A afirmação IV está correta, uma vez que o problema da 
mochila também é considerado um problema NP, usa um algoritmo não determinístico, e sua 
complexidade é O(n), sendo que n representa o tamanho da entrada. 
 
Resposta incorreta. 
C. 
II e III. 
A afirmação I está incorreta, pois o problema do caixeiro viajante é um problema NP 
(problema não determinístico polinomial), cuja complexidade é O(cn), uma vez que a melhor 
solução encontrada não foi provada ser a melhor solução. A afirmação II está correta, pois o 
problema de coloração de grafos é um problema NP (problema não determinístico 
polinomial), e a verificação da solução se dá em tempo polinomial; logo, a complexidade é 
O(P(x)). A afirmação III está incorreta, pois o objetivo do problema do caixeiro viajante é 
percorrer a rota de menor custo, sendo necessário analisar (n-1)! possibilidades de rota; logo, 
a complexidade é exponencial O(cn). A afirmação IV está correta, uma vez que o problema da 
mochila também é considerado um problema NP, usa um algoritmo não determinístico, e sua 
complexidade é O(n), sendo que n representa o tamanho da entrada. 
 
Você não acertou! 
D. 
I, III e IV. 
A afirmação I está incorreta, pois o problema do caixeiro viajante é um problema NP 
(problema não determinístico polinomial), cuja complexidade é O(cn), uma vez que a melhor 
solução encontrada não foi provada ser a melhor solução. A afirmação II está correta, pois o 
problema de coloração de grafos é um problema NP (problema não determinístico 
polinomial), e a verificação da solução se dá em tempo polinomial; logo, a complexidade é 
O(P(x)). A afirmação III está incorreta, pois o objetivo do problema do caixeiro viajante é 
percorrer a rota de menor custo, sendo necessário analisar (n-1)! possibilidades de rota; logo, 
a complexidade é exponencial O(cn). A afirmação IV está correta, uma vez que o problema da 
mochila também é considerado um problema NP, usa um algoritmo não determinístico, e sua 
complexidade é O(n), sendo que n representa o tamanho da entrada. 
 
Resposta incorreta. 
E. 
I, II, III e IV. 
A afirmação I está incorreta, pois o problema do caixeiro viajante é um problema NP 
(problema não determinístico polinomial), cuja complexidade é O(cn), uma vez que a melhor 
solução encontrada não foi provada ser a melhor solução. A afirmação II está correta, pois o 
problema de coloração de grafos é um problema NP (problema não determinístico 
polinomial), e a verificação da solução se dá em tempo polinomial; logo, a complexidade é 
O(P(x)). A afirmação III está incorreta, pois o objetivo do problema do caixeiro viajante é 
percorrer a rota de menor custo, sendo necessário analisar (n-1)! possibilidades de rota; logo, 
a complexidade é exponencial O(cn). A afirmação IV está correta, uma vez que o problema da 
mochila também é considerado um problema NP, usa um algoritmo não determinístico, e sua 
complexidade é O(n), sendo que n representa o tamanho da entrada. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:43 
5. 
Uma questão em aberto no ramo da complexidade, em Ciência da Computação, é verificar 
se a classe P é igual à classe NP (P = NP) ou diferente (P ≠ NP). 
Sobre o problema P vs. NP, avalie as seguintes asserções e a relação proposta entre elas: 
I. O problema P vs. NP verifica se uma linguagem L que executa em um algoritmo não 
determinístico em tempo polinomial poderá ser executada, também em tempo polinomial, 
por algum algoritmo determinístico. 
PORQUE 
II. Os elementos da classe P resolvem problemas em tempo polinomial usando algoritmos 
determinísticos de forma eficiente. 
A respeito dessas asserções, assinale a alternativa correta: 
Resposta incorreta. 
A. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
A asserção I é verdadeira, pois o problema P vs. NP consiste em determinar se toda 
linguagem aceita por determinado algoritmo não determinístico em tempo polinomial 
também será aceita por algum algoritmo determinístico em tempo polinomial. A asserção II 
também é verdadeira, pois a classe P resolve problemas de decisão por meio de algoritmos 
determinísticos em tempo polinomial de forma eficiente. Dessa forma, as asserções I e II são 
proposições verdadeiras, mas a II não é uma justificativa correta da I, visto que nesta se fala 
do problema P vs. NP, e naquela se fala apenas da classe P; então, os problemas não se 
complementam. 
 
Você acertou! 
B. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
A asserção I é verdadeira, pois o problema P vs. NP consiste em determinar se toda 
linguagem aceita por determinado algoritmo não determinístico em tempo polinomial 
também será aceita por algum algoritmo determinístico em tempo polinomial. A asserção II 
também é verdadeira, pois a classe P resolve problemas de decisão por meio de algoritmos 
determinísticos em tempo polinomial de forma eficiente. Dessa forma, as asserções I e II são 
proposições verdadeiras, mas a II não é uma justificativa correta da I, visto que nesta se fala 
do problema P vs. NP, e naquela se fala apenas da classe P; então, os problemas não se 
complementam. 
 
Resposta incorreta. 
C. 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
A asserção I é verdadeira, pois o problema P vs. NP consiste em determinar se toda 
linguagem aceita por determinado algoritmo não determinístico em tempo polinomial 
também será aceita por algum algoritmo determinístico em tempo polinomial. A asserção II 
também é verdadeira, pois a classe P resolve problemas de decisão por meio de algoritmos 
determinísticos em tempo polinomial de forma eficiente. Dessa forma, as asserções I e II são 
proposições verdadeiras, mas a II não é uma justificativa correta da I, visto que nesta se fala 
do problema P vs. NP, e naquela se fala apenas da classe P; então, os problemas não se 
complementam. 
 
Resposta incorreta. 
D. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
A asserção I é verdadeira, pois o problema P vs. NP consiste em determinar se toda 
linguagem aceita por determinado algoritmo não determinístico em tempo polinomial 
também será aceita por algum algoritmo determinístico em tempopolinomial. A asserção II 
também é verdadeira, pois a classe P resolve problemas de decisão por meio de algoritmos 
determinísticos em tempo polinomial de forma eficiente. Dessa forma, as asserções I e II são 
proposições verdadeiras, mas a II não é uma justificativa correta da I, visto que nesta se fala 
do problema P vs. NP, e naquela se fala apenas da classe P; então, os problemas não se 
complementam. 
 
Resposta incorreta. 
E. 
As asserções I e II são proposições falsas. 
A asserção I é verdadeira, pois o problema P vs. NP consiste em determinar se toda 
linguagem aceita por determinado algoritmo não determinístico em tempo polinomial 
também será aceita por algum algoritmo determinístico em tempo polinomial. A asserção II 
também é verdadeira, pois a classe P resolve problemas de decisão por meio de algoritmos 
determinísticos em tempo polinomial de forma eficiente. Dessa forma, as asserções I e II são 
proposições verdadeiras, mas a II não é uma justificativa correta da I, visto que nesta se fala 
do problema P vs. NP, e naquela se fala apenas da classe P; então, os problemas não se 
complementam. 
 
 
Análise de algoritmos em problemas P 
Exercícios 
Respostas enviadas em: 08/03/2024 14:37 
1. 
Confira o enunciado: 
Clique aqui 
 
Resposta correta. 
A. 
Esse algoritmo Insert-Sort executa as instruções, no pior caso, em tempo O(n2), portanto 
pertence à classe polinomial. 
O algoritmo Insert-Sort executa, no seu pior caso, em O(n2), portanto pertence à classe P 
(polinomial). Os algoritmos que pertencem à classe polinomial são capazes de executar em 
O(nk); qualquer tempo acima disso torna o algoritmo não polinomial. Apesar de ele pertencer 
à classe P, o tempo de execução desse algoritmo pode ser melhorado. A pesquisa binária 
trabalha com divisão e conquista, portanto apresenta tempo de 
execução nlogn; consequentemente, pode melhorar o tempo de execução do algoritmo Insert 
Sort. No entanto, os fatores constantes do Insert-Sort o tornam mais rápido para um pequeno 
valor de entrada (n). Assim, faz sentido usar o algoritmo Insert-Sort quando os subproblemas 
se tornam suficientemente pequenos. O algoritmo Insert-Sort, comparado com o Merge-Sort, 
será mais eficiente que este último no melhor caso, pois o Insert-Sort consegue executar 
nessa situação O(n). 
 
Resposta incorreta. 
B. 
Esse algoritmo Insert-Sort pertence à classe P, e uma melhora no tempo de execução desse 
algoritmo torna-se dispensável. 
O algoritmo Insert-Sort executa, no seu pior caso, em O(n2), portanto pertence à classe P 
(polinomial). Os algoritmos que pertencem à classe polinomial são capazes de executar em 
O(nk); qualquer tempo acima disso torna o algoritmo não polinomial. Apesar de ele pertencer 
à classe P, o tempo de execução desse algoritmo pode ser melhorado. A pesquisa binária 
trabalha com divisão e conquista, portanto apresenta tempo de 
execução nlogn; consequentemente, pode melhorar o tempo de execução do algoritmo Insert 
Sort. No entanto, os fatores constantes do Insert-Sort o tornam mais rápido para um pequeno 
valor de entrada (n). Assim, faz sentido usar o algoritmo Insert-Sort quando os subproblemas 
se tornam suficientemente pequenos. O algoritmo Insert-Sort, comparado com o Merge-Sort, 
será mais eficiente que este último no melhor caso, pois o Insert-Sort consegue executar 
nessa situação O(n). 
 
Resposta incorreta. 
C. 
A pesquisa binária não pode melhorar o tempo de execução no pior caso do Insertion-Sort, 
pois tem tempo de execução Θ(n3). 
O algoritmo Insert-Sort executa, no seu pior caso, em O(n2), portanto pertence à classe P 
(polinomial). Os algoritmos que pertencem à classe polinomial são capazes de executar em 
O(nk); qualquer tempo acima disso torna o algoritmo não polinomial. Apesar de ele pertencer 
à classe P, o tempo de execução desse algoritmo pode ser melhorado. A pesquisa binária 
trabalha com divisão e conquista, portanto apresenta tempo de 
execução nlogn; consequentemente, pode melhorar o tempo de execução do algoritmo Insert 
Sort. No entanto, os fatores constantes do Insert-Sort o tornam mais rápido para um pequeno 
valor de entrada (n). Assim, faz sentido usar o algoritmo Insert-Sort quando os subproblemas 
se tornam suficientemente pequenos. O algoritmo Insert-Sort, comparado com o Merge-Sort, 
será mais eficiente que este último no melhor caso, pois o Insert-Sort consegue executar 
nessa situação O(n). 
 
Resposta incorreta. 
D. 
Sabe-se que o método de ordenação Merge-Sort executa, no seu melhor caso, O(nlogn); 
portanto, esse algoritmo sempre será melhor que o algoritmo Insert-Sort. 
O algoritmo Insert-Sort executa, no seu pior caso, em O(n2), portanto pertence à classe P 
(polinomial). Os algoritmos que pertencem à classe polinomial são capazes de executar em 
O(nk); qualquer tempo acima disso torna o algoritmo não polinomial. Apesar de ele pertencer 
à classe P, o tempo de execução desse algoritmo pode ser melhorado. A pesquisa binária 
trabalha com divisão e conquista, portanto apresenta tempo de 
execução nlogn; consequentemente, pode melhorar o tempo de execução do algoritmo Insert 
Sort. No entanto, os fatores constantes do Insert-Sort o tornam mais rápido para um pequeno 
valor de entrada (n). Assim, faz sentido usar o algoritmo Insert-Sort quando os subproblemas 
se tornam suficientemente pequenos. O algoritmo Insert-Sort, comparado com o Merge-Sort, 
será mais eficiente que este último no melhor caso, pois o Insert-Sort consegue executar 
nessa situação O(n). 
 
Você não acertou! 
E. 
Esse algoritmo ordenação por inserção executa as instruções no pior caso em tempo O(2n ), 
portanto pertence à classe polinomial. 
O algoritmo Insert-Sort executa, no seu pior caso, em O(n2), portanto pertence à classe P 
(polinomial). Os algoritmos que pertencem à classe polinomial são capazes de executar em 
O(nk); qualquer tempo acima disso torna o algoritmo não polinomial. Apesar de ele pertencer 
à classe P, o tempo de execução desse algoritmo pode ser melhorado. A pesquisa binária 
trabalha com divisão e conquista, portanto apresenta tempo de 
execução nlogn; consequentemente, pode melhorar o tempo de execução do algoritmo Insert 
Sort. No entanto, os fatores constantes do Insert-Sort o tornam mais rápido para um pequeno 
valor de entrada (n). Assim, faz sentido usar o algoritmo Insert-Sort quando os subproblemas 
se tornam suficientemente pequenos. O algoritmo Insert-Sort, comparado com o Merge-Sort, 
será mais eficiente que este último no melhor caso, pois o Insert-Sort consegue executar 
nessa situação O(n). 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:37 
2. 
A busca em profundidade Depth-First Search (DFS) em um grafo consiste em um algoritmo 
usado para realizar uma busca ou travessia em grafo, visitando todos os seus vértices. 
Intuitivamente, o algoritmo começa em um nó e explora tanto quanto possível cada um dos 
seus ramos antes de retroceder. À medida que percorre o grafo, o algoritmo marca cada 
vértice de cinza e depois de preto. Quando descobre um novo vértice, o algoritmo marca o 
vértice de cinza; quando termina de visitar todos os vizinhos do vértice, o algoritmo marca 
o vértice de preto. O algoritmo recebe um grafo G representado por um vetor Adj de listas 
de adjacência. 
Observe o algoritmo a seguir: 
Busca-em-Profundidade (G) 
1 para cada v em V(G) 
2 cor[v] ← branco 
3 para cada v em V(G) 
4 se cor[v] = branco 
5 DFS (G, v) 
Fonte: Feofiloff, 2020 
 
A rotina recursiva DFS tem acesso a um vetor cor que atribui um rótulo branco, cinza ou 
preto a cada vértice do grafo. A rotina recebe um vértice branco v e determina o conjunto 
adjacente do vértice. 
 
DFS(G, v) 
6 cor[v] ← cinza 
7 para cada w em Adj[v] faça 
8 se cor[w] = branco 
9 então DFS (G, w) 
10 cor[v] ← preto 
Fonte: Feofiloff, 2020 
Ao final da execução do algoritmo Busca-em-Profundidade, todos os vértices do grafo 
estarão pretos. Diante do exposto, marque a alternativa correta: 
Resposta incorreta. 
A. 
De acordo com a complexidade de tempo desse algoritmo,é possível determinar que ele 
está em P. Cada vértice do grafo passado para o algoritmo DFS (linha 9) é O (1). A lista de 
adjacência de cada vértice percorrido uma vez é O(1); nesse caso, a complexidade total é 
O(1) ou constante. 
A complexidade de tempo do algoritmo é O(v+e), em que v é o número de vértices e e é o 
número de arestas, ou seja, linear; dessa forma, esse algoritmo pertence à classe P. Dado que 
um grafo apresenta uma lista de vértices que precisam ser visitados, não há como a 
complexidade ser O(1). Dada a complexidade de tempo do algoritmo, é trivial identificar a 
classe que é executável em tempo polinomial (classe P). 
 
Você acertou! 
B. 
De acordo com a complexidade de tempo desse algoritmo, é possível determinar que ele 
está em P. Cada vértice do grafo passado para o algoritmo DFS (linha 9) é O (v). A lista de 
adjacência de cada vértice percorrido uma vez é O(e); nesse caso, a complexidade total é 
O(v+e). 
A complexidade de tempo do algoritmo é O(v+e), em que v é o número de vértices e e é o 
número de arestas, ou seja, linear; dessa forma, esse algoritmo pertence à classe P. Dado que 
um grafo apresenta uma lista de vértices que precisam ser visitados, não há como a 
complexidade ser O(1). Dada a complexidade de tempo do algoritmo, é trivial identificar a 
classe que é executável em tempo polinomial (classe P). 
 
Resposta incorreta. 
C. 
De acordo com a complexidade de tempo desse algoritmo, é possível determinar que ele não 
pertence à classe P. Cada vértice do grafo passado para o algoritmo DFS (linha 9) é O (1). A 
lista de adjacência de cada vértice percorrido uma vez é O(1); nesse caso, a complexidade 
total é O(1) ou constante. 
A complexidade de tempo do algoritmo é O(v+e), em que v é o número de vértices e e é o 
número de arestas, ou seja, linear; dessa forma, esse algoritmo pertence à classe P. Dado que 
um grafo apresenta uma lista de vértices que precisam ser visitados, não há como a 
complexidade ser O(1). Dada a complexidade de tempo do algoritmo, é trivial identificar a 
classe que é executável em tempo polinomial (classe P). 
 
Resposta incorreta. 
D. 
De acordo com a complexidade de tempo desse algoritmo, é possível determinar que ele 
está não está em P. Cada vértice do grafo passado para o algoritmo DFS (linha 9) é O(n). A 
lista de adjacência de cada vértice percorrido uma vez é O(v); nesse caso, a complexidade 
total é O(v). 
A complexidade de tempo do algoritmo é O(v+e), em que v é o número de vértices e e é o 
número de arestas, ou seja, linear; dessa forma, esse algoritmo pertence à classe P. Dado que 
um grafo apresenta uma lista de vértices que precisam ser visitados, não há como a 
complexidade ser O(1). Dada a complexidade de tempo do algoritmo, é trivial identificar a 
classe que é executável em tempo polinomial (classe P). 
 
Resposta incorreta. 
E. 
Avaliando a complexidade de tempo do algoritmo DFS, não é possível determinar se ele 
pertence à classe P, pois ele deve ser implementando em uma linguagem de programação e 
testado com entradas de vários tamanhos. 
A complexidade de tempo do algoritmo é O(v+e), em que v é o número de vértices e e é o 
número de arestas, ou seja, linear; dessa forma, esse algoritmo pertence à classe P. Dado que 
um grafo apresenta uma lista de vértices que precisam ser visitados, não há como a 
complexidade ser O(1). Dada a complexidade de tempo do algoritmo, é trivial identificar a 
classe que é executável em tempo polinomial (classe P). 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:37 
3. 
Historicamente, a expressão algoritmo eficiente é associada aos algoritmos de complexidade 
polinomial. 
Diante disso, julgue as alternativas a seguir e marque a correta: 
Resposta incorreta. 
A. 
O campo de complexidade computacional normalmente classifica os algoritmos pelo grau de 
dificuldade. Dificuldade é descrita em termos de tempo necessário para projetar esses 
algoritmos. 
O campo de complexidade computacional classifica problemas pelo grau de dificuldade em 
resolvê-los. "Dificuldade", nesse sentido, é descrita em termos de esforço computacional 
necessário para o algoritmo mais eficiente para determinado problema. Em geral, designam-
se os problemas resolvíveis em tempo polinomial como tratáveis, ou fáceis. Tipo de problema 
computacional em que é necessário determinar a melhor solução possível entre todas as 
soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em 
tempo polinomial. Algoritmos não polinomiais (que não pertencem à classe P) podem levar 
séculos para serem executados, mesmo para entradas de tamanho reduzido. 
 
Resposta incorreta. 
B. 
O tipo de problema computacional em que é necessário determinar a melhorsolução possível 
entre todas as soluções viáveis usando a força bruta é considerado tratável. 
O campo de complexidade computacional classifica problemas pelo grau de dificuldade em 
resolvê-los. "Dificuldade", nesse sentido, é descrita em termos de esforço computacional 
necessário para o algoritmo mais eficiente para determinado problema. Em geral, designam-
se os problemas resolvíveis em tempo polinomial como tratáveis, ou fáceis. Tipo de problema 
computacional em que é necessário determinar a melhor solução possível entre todas as 
soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em 
tempo polinomial. Algoritmos não polinomiais (que não pertencem à classe P) podem levar 
séculos para serem executados, mesmo para entradas de tamanho reduzido. 
 
Você acertou! 
C. 
Se um algoritmo apresentar complexidade polinomial, ele é dito tratável ou resolvível em 
tempo polinomial, também conhecido como tratável ou fácil. 
O campo de complexidade computacional classifica problemas pelo grau de dificuldade em 
resolvê-los. "Dificuldade", nesse sentido, é descrita em termos de esforço computacional 
necessário para o algoritmo mais eficiente para determinado problema. Em geral, designam-
se os problemas resolvíveis em tempo polinomial como tratáveis, ou fáceis. Tipo de problema 
computacional em que é necessário determinar a melhor solução possível entre todas as 
soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em 
tempo polinomial. Algoritmos não polinomiais (que não pertencem à classe P) podem levar 
séculos para serem executados, mesmo para entradas de tamanho reduzido. 
 
Resposta incorreta. 
D. 
Algoritmos polinomiais (que pertencem à classe P) podem levar séculos para serem 
executados, mesmo para entradas de tamanho reduzido. 
O campo de complexidade computacional classifica problemas pelo grau de dificuldade em 
resolvê-los. "Dificuldade", nesse sentido, é descrita em termos de esforço computacional 
necessário para o algoritmo mais eficiente para determinado problema. Em geral, designam-
se os problemas resolvíveis em tempo polinomial como tratáveis, ou fáceis. Tipo de problema 
computacional em que é necessário determinar a melhor solução possível entre todas as 
soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em 
tempo polinomial. Algoritmos não polinomiais (que não pertencem à classe P) podem levar 
séculos para serem executados, mesmo para entradas de tamanho reduzido. 
 
Resposta incorreta. 
E. 
Se um algoritmo apresentar complexidade polinomial, ele é dito intratável, ou seja, não 
existem recursos de hardware suficientes para executá-lo. 
O campo de complexidade computacional classifica problemas pelo grau de dificuldade em 
resolvê-los. "Dificuldade", nesse sentido, é descrita em termos de esforço computacional 
necessário para o algoritmo mais eficiente para determinado problema. Em geral, designam-
se os problemas resolvíveis em tempo polinomial como tratáveis, ou fáceis. Tipo de problema 
computacional em que é necessário determinar a melhor solução possível entre todas as 
soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em 
tempo polinomial. Algoritmos não polinomiais (que não pertencemà classe P) podem levar 
séculos para serem executados, mesmo para entradas de tamanho reduzido. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:37 
4. 
P é a classe de problemas que são decidíveis em tempo polinomial. Essa classe é importante 
porque P corresponde aproximadamente à classe de problemas que são realisticamente 
solúveis em um computador. 
Marque a sentença verdadeira: 
Resposta incorreta. 
A. 
A classe P é relevante do ponto de vista prático; por exemplo, quando um problema tem 
tempo de execução de n100,é provável que tenha uso prático, o que ocorre frequentemente 
em problemas reais. 
Quando se avalia um algoritmo, pode-se dar um limitante superior polinomial (geralmente 
em notação O) sobre o número de estágios que o algoritmo usa quando ele roda sobre uma 
entrada de determinado tamanho k. Quando se avaliam as etapas individuais de um 
algoritmo, todas as etapas devem ser executadas em tempo polinomial para garantir a 
implementação nesse tempo. Por determinístico, entende-se que o algoritmo pode predizer 
o seu comportamento: para as mesmas entradas de um problema, há sempre as mesmas 
saídas. É improvável que um tempo de execução de n100 tenha algum uso prático, apesar de 
ser da classe P. Na realidade, poucos problemas reais dessa classe requererem um tempo tão 
alto de execução. 
 
Resposta incorreta. 
B. 
Quando se avalia um algoritmo para mostrar que ele polinomial, primeiro deve-se dar um 
limitante superior exponencial sobre o número de estágios em que algoritmo roda. Assim, 
garante-se que não irá exceder o tempo polinomial. 
Quando se avalia um algoritmo, pode-se dar um limitante superior polinomial (geralmente 
em notação O) sobre o número de estágios que o algoritmo usa quando ele roda sobre uma 
entrada de determinado tamanho k. Quando se avaliam as etapas individuais de um 
algoritmo, todas as etapas devem ser executadas em tempo polinomial para garantir a 
implementação nesse tempo. Por determinístico, entende-se que o algoritmo pode predizer 
o seu comportamento: para as mesmas entradas de um problema, há sempre as mesmas 
saídas. É improvável que um tempo de execução de n100 tenha algum uso prático, apesar de 
ser da classe P. Na realidade, poucos problemas reais dessa classe requererem um tempo tão 
alto de execução. 
 
Resposta incorreta. 
C. 
Quando se avalia um algoritmo para mostrar que ele é polinomial, avaliam-se as etapas 
individuais na descrição do algoritmo; assim, se alguma das etapas pode ser implementada 
em tempo polinomial, garante-se a implementação em tempo polinomial. 
Quando se avalia um algoritmo, pode-se dar um limitante superior polinomial (geralmente 
em notação O) sobre o número de estágios que o algoritmo usa quando ele roda sobre uma 
entrada de determinado tamanho k. Quando se avaliam as etapas individuais de um 
algoritmo, todas as etapas devem ser executadas em tempo polinomial para garantir a 
implementação nesse tempo. Por determinístico, entende-se que o algoritmo pode predizer 
o seu comportamento: para as mesmas entradas de um problema, há sempre as mesmas 
saídas. É improvável que um tempo de execução de n100 tenha algum uso prático, apesar de 
ser da classe P. Na realidade, poucos problemas reais dessa classe requererem um tempo tão 
alto de execução. 
 
Você acertou! 
D. 
A classe P é relevante do ponto de vista prático. Quando um problema está em P, tem-se um 
método de resolvê-lo que roda em tempo nk para alguma constante k. Se esse tempo de 
execução é prático, depende de k e da aplicação. 
Quando se avalia um algoritmo, pode-se dar um limitante superior polinomial (geralmente 
em notação O) sobre o número de estágios que o algoritmo usa quando ele roda sobre uma 
entrada de determinado tamanho k. Quando se avaliam as etapas individuais de um 
algoritmo, todas as etapas devem ser executadas em tempo polinomial para garantir a 
implementação nesse tempo. Por determinístico, entende-se que o algoritmo pode predizer 
o seu comportamento: para as mesmas entradas de um problema, há sempre as mesmas 
saídas. É improvável que um tempo de execução de n100 tenha algum uso prático, apesar de 
ser da classe P. Na realidade, poucos problemas reais dessa classe requererem um tempo tão 
alto de execução. 
 
Resposta incorreta. 
E. 
P é uma referência a tempo determinístico polinomial; por determinístico entende-se que 
existe um “adivinho” (ou “oráculo”): se existir uma solução, o algoritmo não determinístico 
simplesmente a “adivinha”. 
Quando se avalia um algoritmo, pode-se dar um limitante superior polinomial (geralmente 
em notação O) sobre o número de estágios que o algoritmo usa quando ele roda sobre uma 
entrada de determinado tamanho k. Quando se avaliam as etapas individuais de um 
algoritmo, todas as etapas devem ser executadas em tempo polinomial para garantir a 
implementação nesse tempo. Por determinístico, entende-se que o algoritmo pode predizer 
o seu comportamento: para as mesmas entradas de um problema, há sempre as mesmas 
saídas. É improvável que um tempo de execução de n100 tenha algum uso prático, apesar de 
ser da classe P. Na realidade, poucos problemas reais dessa classe requererem um tempo tão 
alto de execução. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:37 
5. 
Confira o enunciado: 
Clique aqui 
 
Resposta correta. 
A. 
Esse algoritmo é responsável por calcular o somatório de 0 até n(a) e pertence à classe P. 
Esse algoritmo é responsável por calcular o somatório de 0 até n(a) e está na classe P. A 
implementação não recursiva para esse problema teria como complexidade de tempo O(n) 
ou por meio de fórmula fechada em tempo constante O(1). A implementação recursiva desse 
algoritmo tem complexidade O(n). 
 
Resposta incorreta. 
B. 
A implementação não recursiva para esse problema teria como complexidade de tempo 
O(n2), pertencendo a P. 
Esse algoritmo é responsável por calcular o somatório de 0 até n(a) e está na classe P. A 
implementação não recursiva para esse problema teria como complexidade de tempo O(n) 
ou por meio de fórmula fechada em tempo constante O(1). A implementação recursiva desse 
algoritmo tem complexidade O(n). 
 
Resposta incorreta. 
C. 
A implementação recursiva é preferida por ser simples de implementar e apresentar 
complexidade O(n2); também pertence a P. 
Esse algoritmo é responsável por calcular o somatório de 0 até n(a) e está na classe P. A 
implementação não recursiva para esse problema teria como complexidade de tempo O(n) 
ou por meio de fórmula fechada em tempo constante O(1). A implementação recursiva desse 
algoritmo tem complexidade O(n). 
 
Você não acertou! 
D. 
A implementação recursiva é preferida por ser simples de implementar apesar de apresentar 
complexidade O(2n); não pertence a P. 
Esse algoritmo é responsável por calcular o somatório de 0 até n(a) e está na classe P. A 
implementação não recursiva para esse problema teria como complexidade de tempo O(n) 
ou por meio de fórmula fechada em tempo constante O(1). A implementação recursiva desse 
algoritmo tem complexidade O(n). 
 
Resposta incorreta. 
E. 
Esse algoritmo é responsável por calcular fatorial de 0 até n(a) e pertence à classe P. 
Esse algoritmo é responsável por calcular o somatório de 0 até n(a) e está na classe P. A 
implementação não recursiva para esse problema teria como complexidade de tempo O(n) 
ou por meio de fórmula fechada em tempo constante O(1). A implementação recursiva desse 
algoritmo tem complexidade O(n). 
 
Projetos de algoritmos 
Exercícios 
Respostas enviadas em: 08/03/2024 14:21 
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 podemapenas 
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: 
Resposta incorreta. 
A. 
Apenas as afirmativas II e III estão corretas. 
Apenas as afirmativas III e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo de 
divisão e conquista desmembra um problema em partes menores e utiliza a recursividade 
como base. A afirmativa II é incorreta, pois as soluções encontradas são chamadas 
de soluções ótimas, já que contêm um valor ótimo, sendo o valor mínimo ou máximo o que 
satisfaz à resolução do problema. A afirmativa III é correta, pois o algoritmo de Dijkstra e a 
programação de linha de montagem são exemplos de algoritmos da programação dinâmica. A 
afirmativa IV é correta, pois o algoritmo de divisão e conquista é lento no pior caso, e pode 
até ocorrer estouro de memória em virtude da recursividade. 
 
Você não acertou! 
B. 
Apenas as afirmativas I e IV estão corretas. 
Apenas as afirmativas III e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo de 
divisão e conquista desmembra um problema em partes menores e utiliza a recursividade 
como base. A afirmativa II é incorreta, pois as soluções encontradas são chamadas 
de soluções ótimas, já que contêm um valor ótimo, sendo o valor mínimo ou máximo o que 
satisfaz à resolução do problema. A afirmativa III é correta, pois o algoritmo de Dijkstra e a 
programação de linha de montagem são exemplos de algoritmos da programação dinâmica. A 
afirmativa IV é correta, pois o algoritmo de divisão e conquista é lento no pior caso, e pode 
até ocorrer estouro de memória em virtude da recursividade. 
 
Resposta correta. 
C. 
Apenas as afirmativas III e IV estão corretas. 
Apenas as afirmativas III e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo de 
divisão e conquista desmembra um problema em partes menores e utiliza a recursividade 
como base. A afirmativa II é incorreta, pois as soluções encontradas são chamadas 
de soluções ótimas, já que contêm um valor ótimo, sendo o valor mínimo ou máximo o que 
satisfaz à resolução do problema. A afirmativa III é correta, pois o algoritmo de Dijkstra e a 
programação de linha de montagem são exemplos de algoritmos da programação dinâmica. A 
afirmativa IV é correta, pois o algoritmo de divisão e conquista é lento no pior caso, e pode 
até ocorrer estouro de memória em virtude da recursividade. 
 
Resposta incorreta. 
D. 
Apenas as afirmativas I, II e IV estão corretas. 
Apenas as afirmativas III e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo de 
divisão e conquista desmembra um problema em partes menores e utiliza a recursividade 
como base. A afirmativa II é incorreta, pois as soluções encontradas são chamadas 
de soluções ótimas, já que contêm um valor ótimo, sendo o valor mínimo ou máximo o que 
satisfaz à resolução do problema. A afirmativa III é correta, pois o algoritmo de Dijkstra e a 
programação de linha de montagem são exemplos de algoritmos da programação dinâmica. A 
afirmativa IV é correta, pois o algoritmo de divisão e conquista é lento no pior caso, e pode 
até ocorrer estouro de memória em virtude da recursividade. 
 
Resposta incorreta. 
E. 
As afirmativas I, II, III e IV estão corretas. 
Apenas as afirmativas III e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo de 
divisão e conquista desmembra um problema em partes menores e utiliza a recursividade 
como base. A afirmativa II é incorreta, pois as soluções encontradas são chamadas 
de soluções ótimas, já que contêm um valor ótimo, sendo o valor mínimo ou máximo o que 
satisfaz à resolução do problema. A afirmativa III é correta, pois o algoritmo de Dijkstra e a 
programação de linha de montagem são exemplos de algoritmos da programação dinâmica. A 
afirmativa IV é correta, pois o algoritmo de divisão e conquista é lento no pior caso, e pode 
até ocorrer estouro de memória em virtude da recursividade. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:21 
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: 
Resposta incorreta. 
A. 
Apenas as afirmativas I, II e III estão corretas. 
Apenas as afirmativas II e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo 
guloso utiliza a solução de determinado momento, sem explorar as demais soluções. A 
afirmativa II é correta, pois os problemas da mochila fracionária e os algoritmos de Prim e 
Kruskal podem ser aplicados utilizando algoritmos gulosos. A afirmativa III é incorreta, pois o 
algoritmo guloso é simples e rápido, porém, em determinados problemas, não 
consegue encontrar uma solução ótima. A afirmativa IV é correta, uma vez que o algoritmo 
guloso, após a escolha de uma solução, não volta atrás. 
 
Resposta correta. 
B. 
Apenas as afirmativas II e IV estão corretas. 
Apenas as afirmativas II e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo 
guloso utiliza a solução de determinado momento, sem explorar as demais soluções. A 
afirmativa II é correta, pois os problemas da mochila fracionária e os algoritmos de Prim e 
Kruskal podem ser aplicados utilizando algoritmos gulosos. A afirmativa III é incorreta, pois o 
algoritmo guloso é simples e rápido, porém, em determinados problemas, não 
consegue encontrar uma solução ótima. A afirmativa IV é correta, uma vez que o algoritmo 
guloso, após a escolha de uma solução, não volta atrás. 
 
Você não acertou! 
C. 
Apenas as afirmativas II e III estão corretas. 
Apenas as afirmativas II e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo 
guloso utiliza a solução de determinado momento, sem explorar as demais soluções. A 
afirmativa II é correta, pois os problemas da mochila fracionária e os algoritmos de Prim e 
Kruskal podem ser aplicados utilizando algoritmos gulosos. A afirmativa III é incorreta, pois o 
algoritmo guloso é simples e rápido, porém, em determinados problemas, não 
consegue encontrar uma solução ótima. A afirmativa IV é correta, uma vez que o algoritmo 
guloso, após a escolha de uma solução, não volta atrás. 
 
Resposta incorreta. 
D. 
Apenas as afirmativas I, III e IV estão corretas. 
Apenas as afirmativas II e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo 
guloso utiliza a solução de determinado momento, sem explorar as demais soluções. A 
afirmativa II é correta, pois os problemas da mochila fracionária e os algoritmos de Prim e 
Kruskal podem ser aplicados utilizando algoritmos gulosos. A afirmativa III é incorreta, pois o 
algoritmo guloso é simples e rápido, porém, em determinados problemas, não 
consegue encontrar uma solução ótima. A afirmativa IV é correta, uma vez que o algoritmo 
guloso, após a escolha de uma solução, não volta atrás. 
 
Resposta incorreta. 
E. 
As afirmativas I, II, III e IV estão corretas. 
Apenas as afirmativas II e IV estão corretas. A afirmativa I é incorreta, pois o algoritmo 
guloso utiliza a solução de determinado momento, sem explorar as demais soluções. A 
afirmativa II é correta, pois os problemas da mochila fracionária