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áriae 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. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:21 
3. 
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: 
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: 
Resposta incorreta. 
A. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. 
A resposta correta é dizer que a asserção I é uma proposição verdadeira, e a II é uma 
proposição falsa. A asserção I é verdadeira, pois, se um problema de otimização apresenta 
soluções com custo positivo, as soluções aproximadas podem ser de minimização ou 
maximização, dependendo do problema. A asserção II é falsa, pois o objetivo é encontrar 
uma cobertura de vértices mínima ou cobertura de vértices ótima de um grafo. 
 
Você não acertou! 
B. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. 
A resposta correta é dizer que a asserção I é uma proposição verdadeira, e a II é uma 
proposição falsa. A asserção I é verdadeira, pois, se um problema de otimização apresenta 
soluções com custo positivo, as soluções aproximadas podem ser de minimização ou 
maximização, dependendo do problema. A asserção II é falsa, pois o objetivo é encontrar 
uma cobertura de vértices mínima ou cobertura de vértices ótima de um grafo. 
 
Resposta correta. 
C. 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
A resposta correta é dizer que a asserção I é uma proposição verdadeira, e a II é uma 
proposição falsa. A asserção I é verdadeira, pois, se um problema de otimização apresenta 
soluções com custo positivo, as soluções aproximadas podem ser de minimização ou 
maximização, dependendo do problema. A asserção II é falsa, pois o objetivo é encontrar 
uma cobertura de vértices mínima ou cobertura de vértices ótima de um grafo. 
 
Resposta incorreta. 
D. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
A resposta correta é dizer que a asserção I é uma proposição verdadeira, e a II é uma 
proposição falsa. A asserção I é verdadeira, pois, se um problema de otimização apresenta 
soluções com custo positivo, as soluções aproximadas podem ser de minimização ou 
maximização, dependendo do problema. A asserção II é falsa, pois o objetivo é encontrar 
uma cobertura de vértices mínima ou cobertura de vértices ótima de um grafo. 
 
Resposta incorreta. 
E. 
As asserções I e II são proposições falsas. 
A resposta correta é dizer que a asserção I é uma proposição verdadeira, e a II é uma 
proposição falsa. A asserção I é verdadeira, pois, se um problema de otimização apresenta 
soluções com custo positivo, as soluções aproximadas podem ser de minimização ou 
maximização, dependendo do problema. A asserção II é falsa, pois o objetivo é encontrar 
uma cobertura de vértices mínima ou cobertura de vértices ótima de um grafo. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:21 
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: 
Você não acertou! 
A. 
Apenas as afirmativas I e II estão corretas. 
Apenas a afirmativa II está correta. A afirmativa I é incorreta, pois os algoritmos de 
aproximação utilizados no problema de soma de subconjuntos devem ser menores ou iguais 
ao valor t. A afirmativa II é correta, pois o problema de cobertura de vértices de um grafo é 
um conjunto de vértices que incide pelo menos a uma aresta do conjunto. A afirmativa III é 
incorreta, pois, como saída, o algoritmo de cobertura de vértices devolve uma cobertura de 
vértices ótima, mas remove as arestas da cópia do conjunto E’. A afirmativa IV é incorreta, 
pois o algoritmo aplicado ao problema de soma de subconjuntos ordena as 
listas L e L’ retirando os valores duplicados. 
 
Resposta incorreta. 
B. 
Apenas as afirmativas III e IV estão corretas. 
Apenas a afirmativa II está correta. A afirmativa I é incorreta, pois os algoritmos de 
aproximação utilizados no problema de soma de subconjuntos devem ser menores ou iguais 
ao valor t. A afirmativa II é correta, pois o problema de cobertura de vértices de um grafo é 
um conjunto de vértices que incide pelo menos a uma aresta do conjunto. A afirmativa III é 
incorreta, pois, como saída, o algoritmo de cobertura de vértices devolve uma cobertura de 
vértices ótima, mas remove as arestas da cópia do conjunto E’. A afirmativa IV é incorreta, 
pois o algoritmo aplicado ao problema de soma de subconjuntos ordena as 
listas L e L’ retirando os valores duplicados. 
 
Resposta incorreta. 
C. 
Apenas as afirmativas II e III estão corretas. 
Apenas a afirmativa II está correta. A afirmativa I é incorreta, pois os algoritmos de 
aproximação utilizados no problema de soma de subconjuntos devem ser menores ou iguais 
ao valor t. A afirmativa II é correta, pois o problema de cobertura de vértices de um grafo é 
um conjunto de vértices que incide pelo menos a uma aresta do conjunto. A afirmativa III é 
incorreta, pois, como saída, o algoritmo de cobertura de vértices devolve uma cobertura de 
vértices ótima, mas remove as arestas da cópia do conjunto E’. A afirmativa IV é incorreta, 
pois o algoritmo aplicado ao problema de soma de subconjuntos ordena as 
listas L e L’ retirando os valores duplicados. 
 
Resposta correta. 
D. 
Apenas a afirmativa II está correta. 
Apenas a afirmativa II está correta. A afirmativa I é incorreta, pois os algoritmos de 
aproximação utilizados no problema de soma de subconjuntos devem ser menores ou iguais 
ao valor t. A afirmativa II é correta, pois o problema de cobertura de vértices de um grafo é 
um conjunto de vértices que incide pelo menos a uma aresta do conjunto. A afirmativa III é 
incorreta, pois, como saída, o algoritmo de cobertura de vértices devolve uma cobertura de 
vértices ótima, mas remove as arestas da cópia do conjunto E’. A afirmativa IV é incorreta, 
pois o algoritmo aplicado ao problema de soma de subconjuntos ordena as 
listas L e L’ retirando os valores duplicados. 
 
Resposta incorreta. 
E. 
As afirmativas I, II, III e IV estão corretas. 
Apenas a afirmativa II está correta. A afirmativa I é incorreta, pois os algoritmos de 
aproximação utilizados no problema de soma de subconjuntos devem ser menores ou iguais 
ao valor t. A afirmativa II é correta, pois o problema de cobertura de vértices de um grafo é 
um conjuntode vértices que incide pelo menos a uma aresta do conjunto. A afirmativa III é 
incorreta, pois, como saída, o algoritmo de cobertura de vértices devolve uma cobertura de 
vértices ótima, mas remove as arestas da cópia do conjunto E’. A afirmativa IV é incorreta, 
pois o algoritmo aplicado ao problema de soma de subconjuntos ordena as 
listas L e L’ retirando os valores duplicados. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:21 
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: 
Resposta incorreta. 
A. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. 
A resposta correta é dizer que a asserção I é uma proposição falsa, e a II é uma proposição 
verdadeira. A asserção I é falsa porque os algoritmos de aproximaçã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. A asserção II é verdadeira, pois o problema da mochila 
booleana é um exemplo de algoritmo de aproximação e consiste em definir quais itens serão 
inseridos na mochila de acordo com o peso de cada item e com a capacidade da mochila. 
 
Você não acertou! 
B. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. 
A resposta correta é dizer que a asserção I é uma proposição falsa, e a II é uma proposição 
verdadeira. A asserção I é falsa porque os algoritmos de aproximaçã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. A asserção II é verdadeira, pois o problema da mochila 
booleana é um exemplo de algoritmo de aproximação e consiste em definir quais itens serão 
inseridos na mochila de acordo com o peso de cada item e com a capacidade da mochila. 
 
Resposta incorreta. 
C. 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
A resposta correta é dizer que a asserção I é uma proposição falsa, e a II é uma proposição 
verdadeira. A asserção I é falsa porque os algoritmos de aproximaçã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. A asserção II é verdadeira, pois o problema da mochila 
booleana é um exemplo de algoritmo de aproximação e consiste em definir quais itens serão 
inseridos na mochila de acordo com o peso de cada item e com a capacidade da mochila. 
 
Resposta correta. 
D. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
A resposta correta é dizer que a asserção I é uma proposição falsa, e a II é uma proposição 
verdadeira. A asserção I é falsa porque os algoritmos de aproximaçã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. A asserção II é verdadeira, pois o problema da mochila 
booleana é um exemplo de algoritmo de aproximação e consiste em definir quais itens serão 
inseridos na mochila de acordo com o peso de cada item e com a capacidade da mochila. 
 
Resposta incorreta. 
E. 
As asserções I e II são proposições falsas. 
A resposta correta é dizer que a asserção I é uma proposição falsa, e a II é uma proposição 
verdadeira. A asserção I é falsa porque os algoritmos de aproximaçã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. A asserção II é verdadeira, pois o problema da mochila 
booleana é um exemplo de algoritmo de aproximação e consiste em definir quais itens serão 
inseridos na mochila de acordo com o peso de cada item e com a capacidade da mochila. 
 
Problema da maioria 
Exercícios 
Respostas enviadas em: 08/03/2024 14:13 
1. 
A pesquisa de padrões é um problema importante na ciência da computação. Quando se 
procura por uma sequência no arquivo de 
bloco de notas/palavra, navegador ou banco de dados, algoritmos 
de pesquisa de padrões são usados para mostrar os resultados da pesquisa. O algoritmo de 
Boyer-Moore compara o padrão com o texto da direita para a esquerda. Se o símbolo de 
texto comparado ao símbolo do padrão mais à direita não ocorrer no padrão, o padrão 
poderá ser deslocado por m posições atrás desse símbolo de texto. 
Quais tabelas de troca de caracteres o algoritmo de busca de Boyer-Moore usa? 
Resposta correta. 
A. 
Tabelas de deslocamento de caracteres bons e ruins. 
O algoritmo de pesquisa de Boyer-Moore usa tabelas de deslocamento de caracteres bons e 
ruins, enquanto o algoritmo de pesquisa rápida usa apenas tabelas de deslocamento de 
caracteres ruins. 
 
Você não acertou! 
B. 
Tabelas de turno de próximo caractere. 
O algoritmo de pesquisa de Boyer-Moore usa tabelas de deslocamento de caracteres bons e 
ruins, enquanto o algoritmo de pesquisa rápida usa apenas tabelas de deslocamento de 
caracteres ruins. 
 
Resposta incorreta. 
C. 
Tabelas de deslocamento com caracteres incorretos. 
O algoritmo de pesquisa de Boyer-Moore usa tabelas de deslocamento de caracteres bons e 
ruins, enquanto o algoritmo de pesquisa rápida usa apenas tabelas de deslocamento de 
caracteres ruins. 
 
Resposta incorreta. 
D. 
Tabelas de turno de próximo caractere. 
O algoritmo de pesquisa de Boyer-Moore usa tabelas de deslocamento de caracteres bons e 
ruins, enquanto o algoritmo de pesquisa rápida usa apenas tabelas de deslocamento de 
caracteres ruins. 
 
Resposta incorreta. 
E. 
Não utiliza nenhuma tabela. 
O algoritmo de pesquisa de Boyer-Moore usa tabelas de deslocamento de caracteres bons e 
ruins, enquanto o algoritmo de pesquisa rápida usa apenas tabelas de deslocamento de 
caracteres ruins. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:13 
2. 
O algoritmo de Boyer-Moore é considerado o algoritmo de correspondência de string mais 
eficiente em aplicativos comuns, como, por exemplo, editores de texto e substituições de 
comandos. O motivo é que ele é o mais rápido quando o alfabeto é de tamanho moderado e 
o padrão é relativamente longo. Um problema típico seria: dado um texto txt[0, ..., n-1] e 
um padrão pat[0, ..., m-1], escrever uma função de pesquisa(char pat [], char txt []) que 
imprima todas as ocorrências de pat[] no txt[], assumindo que n> m. 
Exemplo: 
Entrada: txt[]= "Este é um texto de teste." 
pat[]="teste" 
Saída: Padrão encontrado no índice 19. 
Qual é o pior caso de tempo de execução na fase de pesquisa do algoritmo de Boyer-
Moore? 
Resposta incorreta. 
A. 
O(n). 
Se o padrão ocorrer no texto, o pior caso de execução do algoritmo de Boyer-Moore é 
O(mn). 
 
Você acertou! 
B. 
O(mn). 
Se o padrão ocorrer no texto, o pior caso de execução do algoritmo de Boyer-Moore é 
O(mn). 
 
Resposta incorreta. 
C. 
O(n log n). 
Se o padrão ocorrer no texto, o pior caso de execução do algoritmo de Boyer-Moore é 
O(mn). 
 
Resposta incorreta. 
D. 
O(log n). 
Se o padrão ocorrer no texto, o pior caso de execução do algoritmo de Boyer-Moore é 
O(mn). 
 
Resposta incorreta. 
E. 
O(m+n). 
Se o padrão ocorrer no texto, o pior caso de execução do algoritmo de Boyer-Moore é 
O(mn). 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:13 
3. 
A análise de tempo de execução de algoritmos é um parâmetro importante para se 
determinar a eficiência e a usabilidade de um algoritmo. 
O algoritmo que tem a maior complexidade do tempo de execução é: 
Resposta incorreta. 
A. 
O(log n). 
Um algoritmo fatorial O(n!). O tempo de execuçãocresce mais rápido e se torna inutilizável 
rapidamente para pequenos valores de n. 
 
Resposta incorreta. 
B. 
O(n). 
Um algoritmo fatorial O(n!). O tempo de execução cresce mais rápido e se torna inutilizável 
rapidamente para pequenos valores de n. 
 
Você acertou! 
C. 
O(n!). 
Um algoritmo fatorial O(n!). O tempo de execução cresce mais rápido e se torna inutilizável 
rapidamente para pequenos valores de n. 
 
Resposta incorreta. 
D. 
O(n log n). 
Um algoritmo fatorial O(n!). O tempo de execução cresce mais rápido e se torna inutilizável 
rapidamente para pequenos valores de n. 
 
Resposta incorreta. 
E. 
O(nc). 
Um algoritmo fatorial O(n!). O tempo de execução cresce mais rápido e se torna inutilizável 
rapidamente para pequenos valores de n. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:13 
4. 
A complexidade algorítmica está preocupada com a rapidez ou lentidão de determinado 
algoritmo. Define-se complexidade como uma função numérica T(n) tempo versus o 
tamanho da entrada n. 
O(1) descreve que tipo de complexidade do algoritmo? 
Resposta incorreta. 
A. 
Linear. 
O(1), diz-se que um algoritmo é executado em tempo constante se exigir a mesma 
quantidade de tempo, independentemente do tamanho da entrada. Diz-se que um algoritmo 
é executado em tempo linear se a execução do tempo for diretamente proporcional ao 
tamanho da entrada, ou seja, o tempo cresce linearmente à medida que o tamanho da 
entrada aumenta. Diz-se que um algoritmo é executado em tempo logarítmico se a execução 
do tempo for proporcional ao logaritmo do tamanho da entrada. Diz-se que um algoritmo é 
executado em tempo quadrático se a execução do tempo for proporcional ao quadrado do 
tamanho da entrada. 
 
Resposta incorreta. 
B. 
Quadrática. 
O(1), diz-se que um algoritmo é executado em tempo constante se exigir a mesma 
quantidade de tempo, independentemente do tamanho da entrada. Diz-se que um algoritmo 
é executado em tempo linear se a execução do tempo for diretamente proporcional ao 
tamanho da entrada, ou seja, o tempo cresce linearmente à medida que o tamanho da 
entrada aumenta. Diz-se que um algoritmo é executado em tempo logarítmico se a execução 
do tempo for proporcional ao logaritmo do tamanho da entrada. Diz-se que um algoritmo é 
executado em tempo quadrático se a execução do tempo for proporcional ao quadrado do 
tamanho da entrada. 
 
Resposta incorreta. 
C. 
Logarítima. 
O(1), diz-se que um algoritmo é executado em tempo constante se exigir a mesma 
quantidade de tempo, independentemente do tamanho da entrada. Diz-se que um algoritmo 
é executado em tempo linear se a execução do tempo for diretamente proporcional ao 
tamanho da entrada, ou seja, o tempo cresce linearmente à medida que o tamanho da 
entrada aumenta. Diz-se que um algoritmo é executado em tempo logarítmico se a execução 
do tempo for proporcional ao logaritmo do tamanho da entrada. Diz-se que um algoritmo é 
executado em tempo quadrático se a execução do tempo for proporcional ao quadrado do 
tamanho da entrada. 
 
Você acertou! 
D. 
Constante. 
O(1), diz-se que um algoritmo é executado em tempo constante se exigir a mesma 
quantidade de tempo, independentemente do tamanho da entrada. Diz-se que um algoritmo 
é executado em tempo linear se a execução do tempo for diretamente proporcional ao 
tamanho da entrada, ou seja, o tempo cresce linearmente à medida que o tamanho da 
entrada aumenta. Diz-se que um algoritmo é executado em tempo logarítmico se a execução 
do tempo for proporcional ao logaritmo do tamanho da entrada. Diz-se que um algoritmo é 
executado em tempo quadrático se a execução do tempo for proporcional ao quadrado do 
tamanho da entrada. 
 
Resposta incorreta. 
E. 
Polinomial. 
O(1), diz-se que um algoritmo é executado em tempo constante se exigir a mesma 
quantidade de tempo, independentemente do tamanho da entrada. Diz-se que um algoritmo 
é executado em tempo linear se a execução do tempo for diretamente proporcional ao 
tamanho da entrada, ou seja, o tempo cresce linearmente à medida que o tamanho da 
entrada aumenta. Diz-se que um algoritmo é executado em tempo logarítmico se a execução 
do tempo for proporcional ao logaritmo do tamanho da entrada. Diz-se que um algoritmo é 
executado em tempo quadrático se a execução do tempo for proporcional ao quadrado do 
tamanho da entrada. 
 
Exercícios 
Respostas enviadas em: 08/03/2024 14:13 
5. 
Existem vários tipos de algoritmos e diversas técnicas para melhorar 
o desempenho dos algoritmos. Ao usar essa técnica, divide-se um problema em 
subproblemas. Quando a solução para cada subproblema está pronta, são combinados os 
resultados dos subproblemas para resolver o problema principal. 
Essa técnica é conhecida como: 
Resposta incorreta. 
A. 
técnica de dividir e combinar. 
Na técnica de dividir e conquistar, o problema em questão é dividido em subproblemas 
menores, e, em seguida, cada problema é resolvido independentemente. Quando se continua 
dividindo os subproblemas em subproblemas ainda menores, pode-se chegar a um estágio 
em que não é possível mais divisão. O menor subproblema "atômico" possível (frações) é 
resolvido. A solução de todos os subproblemas é finalmente mesclada para obter a solução 
de um problema original. 
 
Resposta incorreta. 
B. 
técnica de soma. 
Na técnica de dividir e conquistar, o problema em questão é dividido em subproblemas 
menores, e, em seguida, cada problema é resolvido independentemente. Quando se continua 
dividindo os subproblemas em subproblemas ainda menores, pode-se chegar a um estágio 
em que não é possível mais divisão. O menor subproblema "atômico" possível (frações) é 
resolvido. A solução de todos os subproblemas é finalmente mesclada para obter a solução 
de um problema original. 
 
Resposta incorreta. 
C. 
técnica de divisão. 
Na técnica de dividir e conquistar, o problema em questão é dividido em subproblemas 
menores, e, em seguida, cada problema é resolvido independentemente. Quando se continua 
dividindo os subproblemas em subproblemas ainda menores, pode-se chegar a um estágio 
em que não é possível mais divisão. O menor subproblema "atômico" possível (frações) é 
resolvido. A solução de todos os subproblemas é finalmente mesclada para obter a solução 
de um problema original. 
 
Resposta incorreta. 
D. 
técnica de combinação. 
Na técnica de dividir e conquistar, o problema em questão é dividido em subproblemas 
menores, e, em seguida, cada problema é resolvido independentemente. Quando se continua 
dividindo os subproblemas em subproblemas ainda menores, pode-se chegar a um estágio 
em que não é possível mais divisão. O menor subproblema "atômico" possível (frações) é 
resolvido. A solução de todos os subproblemas é finalmente mesclada para obter a solução 
de um problema original. 
 
Você acertou! 
E. 
técnica de dividir e conquistar. 
Na técnica de dividir e conquistar, o problema em questão é dividido em subproblemas 
menores, e, em seguida, cada problema é resolvido independentemente. Quando se continua 
dividindo os subproblemas em subproblemas ainda menores, pode-se chegar a um estágio 
em que não é possível mais divisão. O menor subproblema "atômico" possível (frações) é 
resolvido. A solução de todos os subproblemas é finalmente mesclada para obter a solução 
de um problema original. 
 
Problema da mochila 
 
Exercícios 
Respostas enviadas em: 07/03/2024 13:15 
1. 
Diversas estratégias já foram desenvolvidas para se obter, de modo eficiente, soluções de 
qualidade para o problema da mochila. Uma dessas estratégias é conhecida como "Gulosa", 
e os principais passos dela são apresentados no algoritmo a seguir. 
As entradas do algoritmo são: P (vetor de pesos dos itens), V (vetor de valores dos itens), Q 
(vetor de quantidades de cópias de cada item), C (capacidade da mochila). O algoritmo 
retorna uma lista contendo os itens que compõem a solução ótima. 
 
Indique a alternativa que completa corretamente o trecho de código (3) do algoritmo, 
considerando o problemada mochila limitado. 
Resposta correta. 
A. 
qtd = Qi 
enquanto Pi + pesoMochila <= C e qtd > 0 faça 
Adicionar item i à solução S 
pesoMochila = pesoMochila + Pi 
qtd = qtd - 1 
fim enquanto 
Como se trata da versão limitada do problema da mochila, é preciso contabilizar o número de 
cópias de cada item i que estão sendo inseridas na mochila até o limite Qi. 
Para isso, uma variável auxiliar qtd pode ser usada (qtd = Qi). Então, se o peso do item a ser 
inserido não excede a capacidade da mochila (Pi + pesoMochila <= C), e se o número de 
cópias do item i ainda não atingiu o seu limite (qtd > 0), nesse caso, mais uma cópia do 
item i pode ser inserida na mochila. 
Feito isso, o peso da mochila precisa ser atualizado (pesoMochila = pesoMochila + Pi), e o 
número de cópias disponíveis do item i precisa também ser decrementado (qtd = qtd - 1). 
 
Resposta incorreta. 
B. 
se Qi > 0 então 
enquanto Pi + pesoMochila <= C faça 
Adicionar item i à solução S 
pesoMochila = pesoMochila + Pi 
fim enquanto 
fim se 
Como se trata da versão limitada do problema da mochila, é preciso contabilizar o número de 
cópias de cada item i que estão sendo inseridas na mochila até o limite Qi. 
Para isso, uma variável auxiliar qtd pode ser usada (qtd = Qi). Então, se o peso do item a ser 
inserido não excede a capacidade da mochila (Pi + pesoMochila <= C), e se o número de 
cópias do item i ainda não atingiu o seu limite (qtd > 0), nesse caso, mais uma cópia do 
item i pode ser inserida na mochila. 
Feito isso, o peso da mochila precisa ser atualizado (pesoMochila = pesoMochila + Pi), e o 
número de cópias disponíveis do item i precisa também ser decrementado (qtd = qtd - 1). 
 
Resposta incorreta. 
C. 
qtd = Qi 
enquanto Pi <= C e qtd > 0 faça 
Adicionar item i à solução S 
pesoMochila = pesoMochila + Pi 
fim enquanto 
Como se trata da versão limitada do problema da mochila, é preciso contabilizar o número de 
cópias de cada item i que estão sendo inseridas na mochila até o limite Qi. 
Para isso, uma variável auxiliar qtd pode ser usada (qtd = Qi). Então, se o peso do item a ser 
inserido não excede a capacidade da mochila (Pi + pesoMochila <= C), e se o número de 
cópias do item i ainda não atingiu o seu limite (qtd > 0), nesse caso, mais uma cópia do 
item i pode ser inserida na mochila. 
Feito isso, o peso da mochila precisa ser atualizado (pesoMochila = pesoMochila + Pi), e o 
número de cópias disponíveis do item i precisa também ser decrementado (qtd = qtd - 1). 
 
Resposta incorreta. 
D. 
se Pi + pesoMochila <= C faça 
Adicionar item i à solução S 
pesoMochila = pesoMochila + Pi 
fim enquanto 
Como se trata da versão limitada do problema da mochila, é preciso contabilizar o número de 
cópias de cada item i que estão sendo inseridas na mochila até o limite Qi. 
Para isso, uma variável auxiliar qtd pode ser usada (qtd = Qi). Então, se o peso do item a ser 
inserido não excede a capacidade da mochila (Pi + pesoMochila <= C), e se o número de 
cópias do item i ainda não atingiu o seu limite (qtd > 0), nesse caso, mais uma cópia do 
item i pode ser inserida na mochila. 
Feito isso, o peso da mochila precisa ser atualizado (pesoMochila = pesoMochila + Pi), e o 
número de cópias disponíveis do item i precisa também ser decrementado (qtd = qtd - 1). 
 
Você não acertou! 
E. 
qtd = Qi 
enquanto Pi + pesoMochila <= C faça 
Adicionar item i à solução S 
pesoMochila = pesoMochila + Pi 
qtd = qtd - 1 
fim enquanto 
Como se trata da versão limitada do problema da mochila, é preciso contabilizar o número de 
cópias de cada item i que estão sendo inseridas na mochila até o limite Qi. 
Para isso, uma variável auxiliar qtd pode ser usada (qtd = Qi). Então, se o peso do item a ser 
inserido não excede a capacidade da mochila (Pi + pesoMochila <= C), e se o número de 
cópias do item i ainda não atingiu o seu limite (qtd > 0), nesse caso, mais uma cópia do 
item i pode ser inserida na mochila. 
Feito isso, o peso da mochila precisa ser atualizado (pesoMochila = pesoMochila + Pi), e o 
número de cópias disponíveis do item i precisa também ser decrementado (qtd = qtd - 1). 
 
Exercícios 
Respostas enviadas em: 07/03/2024 13:15 
2. 
Um algoritmo de força bruta aplicado ao problema da mochila 0-1 é uma estratégia que 
_______. No entanto, sua viabilidade é indicada para instâncias _______, pois, para um 
problema de apenas 10 itens, o algoritmo faz a avaliação de _______ soluções possíveis. 
Assinale a alternativa que preenche corretamente as lacunas: 
Resposta incorreta. 
A. 
encontra uma solução razoável / reais / 20. 
A estratégia de força bruta garante a solução ótima para o problema da mochila, uma vez 
que todas as soluções possíveis são testadas. Em virtude disso, seu emprego é inviável em 
problemas reais da indústria ou em contextos que demandem alto desempenho. Logo, a sua 
aplicabilidade é recomendada para instâncias de pequeno porte. Como ela utiliza apenas dois 
vetores auxiliares (de pesos e valores de cada item), seu consumo de memória computacional 
também é bem reduzido. Apesar disso, como ela avalia todas as combinações de solução 
(2n possibilidades), seu desempenho é extremamente reduzido. Por exemplo, para uma 
instância de 10 itens, ela executa 210 = 1.024 avaliações. 
 
Você acertou! 
B. 
garante a solução ótima / de pequeno porte / 1.024. 
A estratégia de força bruta garante a solução ótima para o problema da mochila, uma vez 
que todas as soluções possíveis são testadas. Em virtude disso, seu emprego é inviável em 
problemas reais da indústria ou em contextos que demandem alto desempenho. Logo, a sua 
aplicabilidade é recomendada para instâncias de pequeno porte. Como ela utiliza apenas dois 
vetores auxiliares (de pesos e valores de cada item), seu consumo de memória computacional 
também é bem reduzido. Apesar disso, como ela avalia todas as combinações de solução 
(2n possibilidades), seu desempenho é extremamente reduzido. Por exemplo, para uma 
instância de 10 itens, ela executa 210 = 1.024 avaliações. 
 
Resposta incorreta. 
C. 
é aplicada na indústria / de tamanho ilimitado / 200. 
A estratégia de força bruta garante a solução ótima para o problema da mochila, uma vez 
que todas as soluções possíveis são testadas. Em virtude disso, seu emprego é inviável em 
problemas reais da indústria ou em contextos que demandem alto desempenho. Logo, a sua 
aplicabilidade é recomendada para instâncias de pequeno porte. Como ela utiliza apenas dois 
vetores auxiliares (de pesos e valores de cada item), seu consumo de memória computacional 
também é bem reduzido. Apesar disso, como ela avalia todas as combinações de solução 
(2n possibilidades), seu desempenho é extremamente reduzido. Por exemplo, para uma 
instância de 10 itens, ela executa 210 = 1.024 avaliações. 
 
Resposta incorreta. 
D. 
encontra a melhor solução / que demandam alto desempenho / 1.024. 
A estratégia de força bruta garante a solução ótima para o problema da mochila, uma vez 
que todas as soluções possíveis são testadas. Em virtude disso, seu emprego é inviável em 
problemas reais da indústria ou em contextos que demandem alto desempenho. Logo, a sua 
aplicabilidade é recomendada para instâncias de pequeno porte. Como ela utiliza apenas dois 
vetores auxiliares (de pesos e valores de cada item), seu consumo de memória computacional 
também é bem reduzido. Apesar disso, como ela avalia todas as combinações de solução 
(2n possibilidades), seu desempenho é extremamente reduzido. Por exemplo, para uma 
instância de 10 itens, ela executa 210 = 1.024 avaliações. 
 
Resposta incorreta. 
E. 
demanda muito recurso de memória / de pequeno porte / 10.240. 
A estratégia de força bruta garante a solução ótima para o problema da mochila, uma vez 
que todas as soluções possíveis são testadas. Em virtude disso, seu emprego é inviável em 
problemas reais da indústria ou em contextos que demandem alto desempenho. Logo, a sua 
aplicabilidade é recomendada para instâncias de pequeno porte. Como ela utiliza apenas dois 
vetores auxiliares(de pesos e valores de cada item), seu consumo de memória computacional 
também é bem reduzido. Apesar disso, como ela avalia todas as combinações de solução 
(2n possibilidades), seu desempenho é extremamente reduzido. Por exemplo, para uma 
instância de 10 itens, ela executa 210 = 1.024 avaliações. 
 
Exercícios 
Respostas enviadas em: 07/03/2024 13:15 
3. 
A programação dinâmica é uma estratégia mais elaborada para resolução do problema da 
mochila. Embora seja simples de se implementar computacionalmente, exige bom 
conhecimento da natureza do problema. Quanto a essa abordagem para solução do 
problema da mochila, marque V para verdadeiro, e F para falso, para os seguintes itens: 
( ) Os casos em que a mochila está inicialmente vazia são contemplados pela atribuição do 
valor zero à primeira coluna da estrutura de matriz. 
( ) Para instâncias em que a capacidade da mochila é igual ao número n de itens, o algoritmo 
executa n2 + 2n operações de atribuição à estrutura de matriz. 
( ) As capacidades variadas da mochila, até seu valor limite, são representadas em cada 
linha i da estrutura de matriz, em que a primeira capacidade (i = 0) tem sempre valor nulo. 
( ) O algoritmo computacional é recursivo em razão de essa abordagem depender da 
identificação de uma relação de recorrência para o problema. 
Assinale a alternativa que apresenta a sequência correta: 
Resposta incorreta. 
A. 
V - V - V - F. 
A primeira afirmação é falsa, porque as colunas da estrutura de matriz representam valores 
de capacidade da mochila, e não itens a serem inseridos nela. Os casos em que nenhum item 
está dentro da mochila são indicados pelas linhas da matriz. 
A segunda afirmação é verdadeira, porque, nessa situação, a matriz envolvida será quadrada, 
ou seja, mesmo número de linhas e colunas. Então, sua primeira linha (tamanho n) e sua 
primeira coluna (tamanho n) serão inicializadas com 0, ou seja, n + n = 2n atribuições. Os dois 
laços aninhados executarão n*n = n2 atribuições, o que totaliza n2 + 2n operações de 
atribuição. 
A terceira afirmação é falsa, porque as múltiplas capacidades da mochila consideradas para 
os subproblemas de tamanho menor são representadas pelas colunas da estrutura de matriz. 
A última afirmação é falsa, porque, embora a abordagem dependa da identificação de uma 
relação de recorrência para o problema, o algoritmo computacional não é recursivo, e sim 
iterativo. 
 
Resposta incorreta. 
B. 
F - F - F - V. 
A primeira afirmação é falsa, porque as colunas da estrutura de matriz representam valores 
de capacidade da mochila, e não itens a serem inseridos nela. Os casos em que nenhum item 
está dentro da mochila são indicados pelas linhas da matriz. 
A segunda afirmação é verdadeira, porque, nessa situação, a matriz envolvida será quadrada, 
ou seja, mesmo número de linhas e colunas. Então, sua primeira linha (tamanho n) e sua 
primeira coluna (tamanho n) serão inicializadas com 0, ou seja, n + n = 2n atribuições. Os dois 
laços aninhados executarão n*n = n2 atribuições, o que totaliza n2 + 2n operações de 
atribuição. 
A terceira afirmação é falsa, porque as múltiplas capacidades da mochila consideradas para 
os subproblemas de tamanho menor são representadas pelas colunas da estrutura de matriz. 
A última afirmação é falsa, porque, embora a abordagem dependa da identificação de uma 
relação de recorrência para o problema, o algoritmo computacional não é recursivo, e sim 
iterativo. 
 
Resposta correta. 
C. 
F - V - F - F. 
A primeira afirmação é falsa, porque as colunas da estrutura de matriz representam valores 
de capacidade da mochila, e não itens a serem inseridos nela. Os casos em que nenhum item 
está dentro da mochila são indicados pelas linhas da matriz. 
A segunda afirmação é verdadeira, porque, nessa situação, a matriz envolvida será quadrada, 
ou seja, mesmo número de linhas e colunas. Então, sua primeira linha (tamanho n) e sua 
primeira coluna (tamanho n) serão inicializadas com 0, ou seja, n + n = 2n atribuições. Os dois 
laços aninhados executarão n*n = n2 atribuições, o que totaliza n2 + 2n operações de 
atribuição. 
A terceira afirmação é falsa, porque as múltiplas capacidades da mochila consideradas para 
os subproblemas de tamanho menor são representadas pelas colunas da estrutura de matriz. 
A última afirmação é falsa, porque, embora a abordagem dependa da identificação de uma 
relação de recorrência para o problema, o algoritmo computacional não é recursivo, e sim 
iterativo. 
 
Você não acertou! 
D. 
V - F - F - V. 
A primeira afirmação é falsa, porque as colunas da estrutura de matriz representam valores 
de capacidade da mochila, e não itens a serem inseridos nela. Os casos em que nenhum item 
está dentro da mochila são indicados pelas linhas da matriz. 
A segunda afirmação é verdadeira, porque, nessa situação, a matriz envolvida será quadrada, 
ou seja, mesmo número de linhas e colunas. Então, sua primeira linha (tamanho n) e sua 
primeira coluna (tamanho n) serão inicializadas com 0, ou seja, n + n = 2n atribuições. Os dois 
laços aninhados executarão n*n = n2 atribuições, o que totaliza n2 + 2n operações de 
atribuição. 
A terceira afirmação é falsa, porque as múltiplas capacidades da mochila consideradas para 
os subproblemas de tamanho menor são representadas pelas colunas da estrutura de matriz. 
A última afirmação é falsa, porque, embora a abordagem dependa da identificação de uma 
relação de recorrência para o problema, o algoritmo computacional não é recursivo, e sim 
iterativo. 
 
Resposta incorreta. 
E. 
V - V - F - F. 
A primeira afirmação é falsa, porque as colunas da estrutura de matriz representam valores 
de capacidade da mochila, e não itens a serem inseridos nela. Os casos em que nenhum item 
está dentro da mochila são indicados pelas linhas da matriz. 
A segunda afirmação é verdadeira, porque, nessa situação, a matriz envolvida será quadrada, 
ou seja, mesmo número de linhas e colunas. Então, sua primeira linha (tamanho n) e sua 
primeira coluna (tamanho n) serão inicializadas com 0, ou seja, n + n = 2n atribuições. Os dois 
laços aninhados executarão n*n = n2 atribuições, o que totaliza n2 + 2n operações de 
atribuição. 
A terceira afirmação é falsa, porque as múltiplas capacidades da mochila consideradas para 
os subproblemas de tamanho menor são representadas pelas colunas da estrutura de matriz. 
A última afirmação é falsa, porque, embora a abordagem dependa da identificação de uma 
relação de recorrência para o problema, o algoritmo computacional não é recursivo, e sim 
iterativo. 
 
Exercícios 
Respostas enviadas em: 07/03/2024 13:15 
4. 
Apesar de o problema da mochila ter uma primeira formulação conhecida como 0-1, ou 
booleana, diversas outras versões foram propostas. Sobre as diferentes variações do 
problema da mochila, 
leia as afirmativas a seguir: 
I. As frações de cada item que podem ser consideradas no problema 
da mochila 0-1 possibilitam que cada fração represente um novo item 
a ser avaliado. 
II. O uso de um algoritmo guloso que considera a razão valor do item/peso do item como 
critério de ordenação não seria viável 
para o problema da soma de subconjuntos. 
III. O problema da mochila inteira pode ser reduzido ao problema 
da mochila limitada defindo-se um número específico de cópias possíveis para cada item 
possível para a mochila. 
IV. Uma estratégia de inserção "tudo ou nada" — todas as cópias de um item são inseridas 
ou nenhuma — permite que o problema da mochila limitado seja tratado como mochila 0-1. 
Quais estão corretas? 
Resposta incorreta. 
A. 
I e II. 
Afirmação I é falsa, porque o problema da mochila 0-1 não considera frações de itens, e sim 
apenas itens completos. Logo, ou um item é inserido completamente, ou não é inserido. 
Afirmação II é verdadeira, porque, no problema da soma de subconjuntos, o peso e o valor 
do item são os mesmos. Logo, a razão valor/peso terá valor 1 para todos os itens. Nesse 
caso, a ordenação requerida pela estratégia gulosa não terá efeito. 
Afirmação III é verdadeira,porque a diferença entre as duas versões é apenas no número 
infinito de cópias permitido na mochila inteira, enquanto na versão limitada, um número 
específico de cópias é informado. 
Afirmação IV é verdadeira, porque, com essa estratégia de inserção,o peso pi e o valor vi de 
cada item i tendo bicópias iguais podem ser redefinidos como p'i = bi*pi e v'i = bi*vi. Nesse caso, 
o problema da mochila limitada é mapeado para uma mochila 0-1 considerando cada 
item i como tendo peso p'i e valor v'i . 
 
Você não acertou! 
B. 
II e IV. 
Afirmação I é falsa, porque o problema da mochila 0-1 não considera frações de itens, e sim 
apenas itens completos. Logo, ou um item é inserido completamente, ou não é inserido. 
Afirmação II é verdadeira, porque, no problema da soma de subconjuntos, o peso e o valor 
do item são os mesmos. Logo, a razão valor/peso terá valor 1 para todos os itens. Nesse 
caso, a ordenação requerida pela estratégia gulosa não terá efeito. 
Afirmação III é verdadeira, porque a diferença entre as duas versões é apenas no número 
infinito de cópias permitido na mochila inteira, enquanto na versão limitada, um número 
específico de cópias é informado. 
Afirmação IV é verdadeira, porque, com essa estratégia de inserção,o peso pi e o valor vi de 
cada item i tendo bicópias iguais podem ser redefinidos como p'i = bi*pi e v'i = bi*vi. Nesse caso, 
o problema da mochila limitada é mapeado para uma mochila 0-1 considerando cada 
item i como tendo peso p'i e valor v'i . 
 
Resposta incorreta. 
C. 
I, II e III. 
Afirmação I é falsa, porque o problema da mochila 0-1 não considera frações de itens, e sim 
apenas itens completos. Logo, ou um item é inserido completamente, ou não é inserido. 
Afirmação II é verdadeira, porque, no problema da soma de subconjuntos, o peso e o valor 
do item são os mesmos. Logo, a razão valor/peso terá valor 1 para todos os itens. Nesse 
caso, a ordenação requerida pela estratégia gulosa não terá efeito. 
Afirmação III é verdadeira, porque a diferença entre as duas versões é apenas no número 
infinito de cópias permitido na mochila inteira, enquanto na versão limitada, um número 
específico de cópias é informado. 
Afirmação IV é verdadeira, porque, com essa estratégia de inserção,o peso pi e o valor vi de 
cada item i tendo bicópias iguais podem ser redefinidos como p'i = bi*pi e v'i = bi*vi. Nesse caso, 
o problema da mochila limitada é mapeado para uma mochila 0-1 considerando cada 
item i como tendo peso p'i e valor v'i . 
 
Resposta correta. 
D. 
II, III e IV. 
Afirmação I é falsa, porque o problema da mochila 0-1 não considera frações de itens, e sim 
apenas itens completos. Logo, ou um item é inserido completamente, ou não é inserido. 
Afirmação II é verdadeira, porque, no problema da soma de subconjuntos, o peso e o valor 
do item são os mesmos. Logo, a razão valor/peso terá valor 1 para todos os itens. Nesse 
caso, a ordenação requerida pela estratégia gulosa não terá efeito. 
Afirmação III é verdadeira, porque a diferença entre as duas versões é apenas no número 
infinito de cópias permitido na mochila inteira, enquanto na versão limitada, um número 
específico de cópias é informado. 
Afirmação IV é verdadeira, porque, com essa estratégia de inserção,o peso pi e o valor vi de 
cada item i tendo bicópias iguais podem ser redefinidos como p'i = bi*pi e v'i = bi*vi. Nesse caso, 
o problema da mochila limitada é mapeado para uma mochila 0-1 considerando cada 
item i como tendo peso p'i e valor v'i . 
 
Resposta incorreta. 
E. 
II e III. 
Afirmação I é falsa, porque o problema da mochila 0-1 não considera frações de itens, e sim 
apenas itens completos. Logo, ou um item é inserido completamente, ou não é inserido. 
Afirmação II é verdadeira, porque, no problema da soma de subconjuntos, o peso e o valor 
do item são os mesmos. Logo, a razão valor/peso terá valor 1 para todos os itens. Nesse 
caso, a ordenação requerida pela estratégia gulosa não terá efeito. 
Afirmação III é verdadeira, porque a diferença entre as duas versões é apenas no número 
infinito de cópias permitido na mochila inteira, enquanto na versão limitada, um número 
específico de cópias é informado. 
Afirmação IV é verdadeira, porque, com essa estratégia de inserção,o peso pi e o valor vi de 
cada item i tendo bicópias iguais podem ser redefinidos como p'i = bi*pi e v'i = bi*vi. Nesse caso, 
o problema da mochila limitada é mapeado para uma mochila 0-1 considerando cada 
item i como tendo peso p'i e valor v'i . 
 
Exercícios 
Respostas enviadas em: 07/03/2024 13:15 
5. 
Instâncias pequenas do problema da mochila possibilitam que diferentes estratégias de 
solução sejam mais bem compreendidas. Seja o problema da mochila 0-1 com capacidade C 
= 50kg, três itens precisam ser inseridos na mochila, conforme detalhado a seguir: 
(P: peso, V: valor) 
Item 1: P = 10kg, V = $60 
Item 2: P = 20kg, V = $100 
Item 3: P = 30kg, V = $120 
Assinale a alternativa correta a respeito da solução do problema: 
Resposta incorreta. 
A. 
Adicionando os itens na ordem em que aparecem, todos caberão na mochila, e a solução 
ótima será obtida. 
Se for feita uma inserção sequencial na ordem em que os itens aparecem, apenas os dois 
primeiros itens caberão, totalizando 30kg. O mesmo acontece se aplicada uma estratégia 
gulosa considerando a ordenação pela razão r = valor/peso: apenas o item 1 (r = 6) e o item 2 
(r = 5) serão inseridos, totalizando os mesmos 30kg. Considerando uma modificação do 
problema em que infinitas cópias seriam aceitas, a solução ótima seria obtida com a inserção 
de 5 cópias do item 1, totalizando um valor de $300. Porém, se a modificação do problema 
envolver um número de cópias correspondente ao índice do item, ainda assim a solução 
obtida (duas cópias de 2 e uma cópia de 1, totalizando $260) será inferior que a obtida por 
meio de um número infinito de cópias. Por sua vez, uma inserção em ordem decrescente de 
valor (itens 3 e 2, totalizando $220) obtém a mesma solução que um algoritmo de força bruta 
que testa todas as soluções, conforme mostrado a seguir: 
1. Item 1: $60 
2. Itens 1, 2: $160 
3. Itens 1, 2, 3: viola capacidade 
4. Item 2: $100 
5. Itens 2, 3: $220 (melhor solução) 
6: Item 3: $120 
 
Você não acertou! 
B. 
Aplicando uma estratégia gulosa que considera uma ordenação de itens baseada na razão 
valor/peso, a solução ótima é obtida. 
Se for feita uma inserção sequencial na ordem em que os itens aparecem, apenas os dois 
primeiros itens caberão, totalizando 30kg. O mesmo acontece se aplicada uma estratégia 
gulosa considerando a ordenação pela razão r = valor/peso: apenas o item 1 (r = 6) e o item 2 
(r = 5) serão inseridos, totalizando os mesmos 30kg. Considerando uma modificação do 
problema em que infinitas cópias seriam aceitas, a solução ótima seria obtida com a inserção 
de 5 cópias do item 1, totalizando um valor de $300. Porém, se a modificação do problema 
envolver um número de cópias correspondente ao índice do item, ainda assim a solução 
obtida (duas cópias de 2 e uma cópia de 1, totalizando $260) será inferior que a obtida por 
meio de um número infinito de cópias. Por sua vez, uma inserção em ordem decrescente de 
valor (itens 3 e 2, totalizando $220) obtém a mesma solução que um algoritmo de força bruta 
que testa todas as soluções, conforme mostrado a seguir: 
1. Item 1: $60 
2. Itens 1, 2: $160 
3. Itens 1, 2, 3: viola capacidade 
4. Item 2: $100 
5. Itens 2, 3: $220 (melhor solução) 
6: Item 3: $120 
 
Resposta incorreta. 
C. 
Se infinitas cópias de cada item puderem ser inseridas, a solução ótima terá valor $280 e 
será composta dos itens {2, 1, 1, 1}. 
Se for feita uma inserção sequencial na ordem em que os itens aparecem, apenas os dois 
primeiros itens caberão, totalizando 30kg. O mesmo acontece se aplicada uma estratégia 
gulosa considerando a ordenação pela razão r = valor/peso: apenas o item 1 (r = 6) e o item 2 
(r = 5) serão inseridos, totalizando os mesmos 30kg. Considerando uma modificação do 
problema em que infinitas cópias seriamaceitas, a solução ótima seria obtida com a inserção 
de 5 cópias do item 1, totalizando um valor de $300. Porém, se a modificação do problema 
envolver um número de cópias correspondente ao índice do item, ainda assim a solução 
obtida (duas cópias de 2 e uma cópia de 1, totalizando $260) será inferior que a obtida por 
meio de um número infinito de cópias. Por sua vez, uma inserção em ordem decrescente de 
valor (itens 3 e 2, totalizando $220) obtém a mesma solução que um algoritmo de força bruta 
que testa todas as soluções, conforme mostrado a seguir: 
1. Item 1: $60 
2. Itens 1, 2: $160 
3. Itens 1, 2, 3: viola capacidade 
4. Item 2: $100 
5. Itens 2, 3: $220 (melhor solução) 
6: Item 3: $120 
 
Resposta incorreta. 
D. 
Se for permitido um número de cópias igual ao índice do item (item i dispõe de i cópias), 
então a solução obtida será melhor que um número ilimitado de cópias. 
Se for feita uma inserção sequencial na ordem em que os itens aparecem, apenas os dois 
primeiros itens caberão, totalizando 30kg. O mesmo acontece se aplicada uma estratégia 
gulosa considerando a ordenação pela razão r = valor/peso: apenas o item 1 (r = 6) e o item 2 
(r = 5) serão inseridos, totalizando os mesmos 30kg. Considerando uma modificação do 
problema em que infinitas cópias seriam aceitas, a solução ótima seria obtida com a inserção 
de 5 cópias do item 1, totalizando um valor de $300. Porém, se a modificação do problema 
envolver um número de cópias correspondente ao índice do item, ainda assim a solução 
obtida (duas cópias de 2 e uma cópia de 1, totalizando $260) será inferior que a obtida por 
meio de um número infinito de cópias. Por sua vez, uma inserção em ordem decrescente de 
valor (itens 3 e 2, totalizando $220) obtém a mesma solução que um algoritmo de força bruta 
que testa todas as soluções, conforme mostrado a seguir: 
1. Item 1: $60 
2. Itens 1, 2: $160 
3. Itens 1, 2, 3: viola capacidade 
4. Item 2: $100 
5. Itens 2, 3: $220 (melhor solução) 
6: Item 3: $120 
 
Resposta correta. 
E. 
A solução obtida por um algoritmo de força bruta é a mesma obtida por uma inserção em 
ordem decrescente de valor. 
Se for feita uma inserção sequencial na ordem em que os itens aparecem, apenas os dois 
primeiros itens caberão, totalizando 30kg. O mesmo acontece se aplicada uma estratégia 
gulosa considerando a ordenação pela razão r = valor/peso: apenas o item 1 (r = 6) e o item 2 
(r = 5) serão inseridos, totalizando os mesmos 30kg. Considerando uma modificação do 
problema em que infinitas cópias seriam aceitas, a solução ótima seria obtida com a inserção 
de 5 cópias do item 1, totalizando um valor de $300. Porém, se a modificação do problema 
envolver um número de cópias correspondente ao índice do item, ainda assim a solução 
obtida (duas cópias de 2 e uma cópia de 1, totalizando $260) será inferior que a obtida por 
meio de um número infinito de cópias. Por sua vez, uma inserção em ordem decrescente de 
valor (itens 3 e 2, totalizando $220) obtém a mesma solução que um algoritmo de força bruta 
que testa todas as soluções, conforme mostrado a seguir: 
1. Item 1: $60 
2. Itens 1, 2: $160 
3. Itens 1, 2, 3: viola capacidade 
4. Item 2: $100 
5. Itens 2, 3: $220 (melhor solução) 
6: Item 3: $120 
 
Introdução à análise assintótica 
Exercícios 
Respostas enviadas em: 06/03/2024 15:41 
1. 
O comportamento assintótico de funções pode ser expresso de forma precisa por meio do 
usa da notação O. Sobre essa técnica utilizada para indicar o limite superior de funções, veja 
as afirmativas a seguir: 
I. 2n+1 = O(2n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)) 
III. 22n = O(2n) 
IV. 6n3 = O(n2) 
Quais estão corretas? 
Você acertou! 
A. 
I e II. 
I. 2n+1 = O(2n) 
Verdadeira, pois 2n+1 = 2 · 2n = 2 · O(2n) = O(2n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)) 
Verdadeira, pois, para c e m positivos, tem-se f(n) <= ch(n), com n > m, e para c' e m', tem-
se g(n) <= c'h(n), com n > m'. Tomando-se n > max{m, m'}, pode-se afirmar que f(n) + g(n) <= 
ch(n) + c'h(n). Então, f(n) + g(n) <= (c + c')h(n) para todo n > max{m, m'}, o que corresponde 
exatamente a afirmar que f(n) + g(n) = O(h(n)). 
III. 22n = O(2n) 
Falsa, pois, se fosse verdade, então 
22n <= c2n, para algum c, n0 > 0 e todo n > n0 
2nlog2(2) <= log2c + nlog2(2) 
2n <= log2c + n 
n <= log2c. Porém, não existe uma constante c que satisfaça essa desigualdade. 
 
IV. 6n3 = O(n2) 
Falsa, pois, se fosse verdade, então 6n3 <= cn2 para c e m > 0 e todo n > m. Isso implicaria 
que 6n <= c (dividindo-se a desigualdade por n2). Porém, não existe constante c que satisfaça 
essa desigualdade. 
 
Resposta incorreta. 
B. 
II e IV. 
I. 2n+1 = O(2n) 
Verdadeira, pois 2n+1 = 2 · 2n = 2 · O(2n) = O(2n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)) 
Verdadeira, pois, para c e m positivos, tem-se f(n) <= ch(n), com n > m, e para c' e m', tem-
se g(n) <= c'h(n), com n > m'. Tomando-se n > max{m, m'}, pode-se afirmar que f(n) + g(n) <= 
ch(n) + c'h(n). Então, f(n) + g(n) <= (c + c')h(n) para todo n > max{m, m'}, o que corresponde 
exatamente a afirmar que f(n) + g(n) = O(h(n)). 
III. 22n = O(2n) 
Falsa, pois, se fosse verdade, então 
22n <= c2n, para algum c, n0 > 0 e todo n > n0 
2nlog2(2) <= log2c + nlog2(2) 
2n <= log2c + n 
n <= log2c. Porém, não existe uma constante c que satisfaça essa desigualdade. 
 
IV. 6n3 = O(n2) 
Falsa, pois, se fosse verdade, então 6n3 <= cn2 para c e m > 0 e todo n > m. Isso implicaria 
que 6n <= c (dividindo-se a desigualdade por n2). Porém, não existe constante c que satisfaça 
essa desigualdade. 
 
Resposta incorreta. 
C. 
I, II e III. 
I. 2n+1 = O(2n) 
Verdadeira, pois 2n+1 = 2 · 2n = 2 · O(2n) = O(2n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)) 
Verdadeira, pois, para c e m positivos, tem-se f(n) <= ch(n), com n > m, e para c' e m', tem-
se g(n) <= c'h(n), com n > m'. Tomando-se n > max{m, m'}, pode-se afirmar que f(n) + g(n) <= 
ch(n) + c'h(n). Então, f(n) + g(n) <= (c + c')h(n) para todo n > max{m, m'}, o que corresponde 
exatamente a afirmar que f(n) + g(n) = O(h(n)). 
III. 22n = O(2n) 
Falsa, pois, se fosse verdade, então 
22n <= c2n, para algum c, n0 > 0 e todo n > n0 
2nlog2(2) <= log2c + nlog2(2) 
2n <= log2c + n 
n <= log2c. Porém, não existe uma constante c que satisfaça essa desigualdade. 
 
IV. 6n3 = O(n2) 
Falsa, pois, se fosse verdade, então 6n3 <= cn2 para c e m > 0 e todo n > m. Isso implicaria 
que 6n <= c (dividindo-se a desigualdade por n2). Porém, não existe constante c que satisfaça 
essa desigualdade. 
 
Resposta incorreta. 
D. 
II, III e IV. 
I. 2n+1 = O(2n) 
Verdadeira, pois 2n+1 = 2 · 2n = 2 · O(2n) = O(2n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)) 
Verdadeira, pois, para c e m positivos, tem-se f(n) <= ch(n), com n > m, e para c' e m', tem-
se g(n) <= c'h(n), com n > m'. Tomando-se n > max{m, m'}, pode-se afirmar que f(n) + g(n) <= 
ch(n) + c'h(n). Então, f(n) + g(n) <= (c + c')h(n) para todo n > max{m, m'}, o que corresponde 
exatamente a afirmar que f(n) + g(n) = O(h(n)). 
III. 22n = O(2n) 
Falsa, pois, se fosse verdade, então 
22n <= c2n, para algum c, n0 > 0 e todo n > n0 
2nlog2(2) <= log2c + nlog2(2) 
2n <= log2c + n 
n <= log2c. Porém, não existe uma constante c que satisfaça essa desigualdade. 
 
IV. 6n3 = O(n2) 
Falsa, pois, se fosse verdade, então 6n3 <= cn2 para c e m > 0 e todo n > m. Isso implicaria 
que 6n <= c (dividindo-se a desigualdade por n2). Porém, não existe constante c que satisfaça 
essa desigualdade. 
 
Resposta incorreta. 
E. 
II e III. 
I. 2n+1 = O(2n) 
Verdadeira, pois 2n+1 = 2 · 2n = 2 · O(2n) = O(2n) 
II. Se f(n) = O(h(n)) e g(n) = O(h(n)), então f(n) + g(n) = O(h(n)) 
Verdadeira, pois, para c e m positivos, tem-se f(n) <= ch(n), com n > m, e para c' e m', tem-
se g(n) <= c'h(n), com n > m'. Tomando-se n > max{m, m'}, pode-se afirmar que f(n) + g(n) <= 
ch(n) + c'h(n). Então, f(n) + g(n) <= (c + c')h(n) para todo n > max{m, m'}, o que correspondeexatamente a afirmar que f(n) + g(n) = O(h(n)). 
III. 22n = O(2n) 
Falsa, pois, se fosse verdade, então 
22n <= c2n, para algum c, n0 > 0 e todo n > n0 
2nlog2(2) <= log2c + nlog2(2) 
2n <= log2c + n 
n <= log2c. Porém, não existe uma constante c que satisfaça essa desigualdade. 
 
IV. 6n3 = O(n2) 
Falsa, pois, se fosse verdade, então 6n3 <= cn2 para c e m > 0 e todo n > m. Isso implicaria 
que 6n <= c (dividindo-se a desigualdade por n2). Porém, não existe constante c que satisfaça 
essa desigualdade. 
Exercícios 
Respostas enviadas em: 06/03/2024 15:41 
2. 
Um modelo largamente utilizado para a subsidiar a análise da eficiência de algoritmos é 
conhecido como modelo de computação RAM. 
Com base nesse modelo e na função Misterio abaixo, marque V para verdadeiro e F para 
falso para os itens a seguir. 
 
função Misterio(n) 
 // n é um número inteiro não negativo 
 S = 0 
 para i = 0 até n faça 
 S = S + i * i 
 fim para 
 retorna S 
fim função 
 
 
( ) A operação básica de comparação do algoritmo precisa considerar a precedência de 
operadores aritméticos. 
( ) A função executa n + 1 operações básicas para qualquer entrada de tamanho n. 
( ) Considerando a complexidade de melhor caso da função, ela apresenta mais eficiência 
que no pior caso. 
( ) Em comparação com a complexidade de pior caso da busca sequencial, ambas as funções 
apresentam a mesma eficiência. 
Feito isso, assinale a alternativa que apresenta a sequência correta: 
Resposta incorreta. 
A. 
V - V - V - F. 
(F) A operação básica de comparação do algoritmo precisa considerar a precedência de 
operadores aritméticos. Falsa, porque a operação elementar básica da função é corresponde 
a uma adição e a uma multiplicação. 
(F) A função executa n + 1 operações básicas para qualquer entrada de tamanho n. Falsa, 
porque a função executa uma adição e uma multiplicação para cada uma da n iterações, 
totalizando 2n operações. Porém, há ainda uma atribuição inicial (S = 0), o que resulta em 2n 
+ 1 operações básicas. 
(F) Considerando a complexidade de melhor caso da função, ela apresenta mais eficiência 
que no pior caso. Falsa, porque ambas as complexidades de melhor e pior caso são da ordem 
de O(n); logo, apresentam a mesma relação de eficiência. 
(V) Em comparação com a complexidade de pior caso da busca sequencial, ambas as funções 
apresentam a mesma eficiência. Verdadeiro, porque a complexidade de pior caso da busca 
sequencial é O(n), o que corresponde à mesma ordem de complexidade da função. 
 
Você acertou! 
B. 
F - F - F - V. 
(F) A operação básica de comparação do algoritmo precisa considerar a precedência de 
operadores aritméticos. Falsa, porque a operação elementar básica da função é corresponde 
a uma adição e a uma multiplicação. 
(F) A função executa n + 1 operações básicas para qualquer entrada de tamanho n. Falsa, 
porque a função executa uma adição e uma multiplicação para cada uma da n iterações, 
totalizando 2n operações. Porém, há ainda uma atribuição inicial (S = 0), o que resulta em 2n 
+ 1 operações básicas. 
(F) Considerando a complexidade de melhor caso da função, ela apresenta mais eficiência 
que no pior caso. Falsa, porque ambas as complexidades de melhor e pior caso são da ordem 
de O(n); logo, apresentam a mesma relação de eficiência. 
(V) Em comparação com a complexidade de pior caso da busca sequencial, ambas as funções 
apresentam a mesma eficiência. Verdadeiro, porque a complexidade de pior caso da busca 
sequencial é O(n), o que corresponde à mesma ordem de complexidade da função. 
 
Resposta incorreta. 
C. 
F - V - F - F. 
(F) A operação básica de comparação do algoritmo precisa considerar a precedência de 
operadores aritméticos. Falsa, porque a operação elementar básica da função é corresponde 
a uma adição e a uma multiplicação. 
(F) A função executa n + 1 operações básicas para qualquer entrada de tamanho n. Falsa, 
porque a função executa uma adição e uma multiplicação para cada uma da n iterações, 
totalizando 2n operações. Porém, há ainda uma atribuição inicial (S = 0), o que resulta em 2n 
+ 1 operações básicas. 
(F) Considerando a complexidade de melhor caso da função, ela apresenta mais eficiência 
que no pior caso. Falsa, porque ambas as complexidades de melhor e pior caso são da ordem 
de O(n); logo, apresentam a mesma relação de eficiência. 
(V) Em comparação com a complexidade de pior caso da busca sequencial, ambas as funções 
apresentam a mesma eficiência. Verdadeiro, porque a complexidade de pior caso da busca 
sequencial é O(n), o que corresponde à mesma ordem de complexidade da função. 
 
Resposta incorreta. 
D. 
V - F - F - V. 
(F) A operação básica de comparação do algoritmo precisa considerar a precedência de 
operadores aritméticos. Falsa, porque a operação elementar básica da função é corresponde 
a uma adição e a uma multiplicação. 
(F) A função executa n + 1 operações básicas para qualquer entrada de tamanho n. Falsa, 
porque a função executa uma adição e uma multiplicação para cada uma da n iterações, 
totalizando 2n operações. Porém, há ainda uma atribuição inicial (S = 0), o que resulta em 2n 
+ 1 operações básicas. 
(F) Considerando a complexidade de melhor caso da função, ela apresenta mais eficiência 
que no pior caso. Falsa, porque ambas as complexidades de melhor e pior caso são da ordem 
de O(n); logo, apresentam a mesma relação de eficiência. 
(V) Em comparação com a complexidade de pior caso da busca sequencial, ambas as funções 
apresentam a mesma eficiência. Verdadeiro, porque a complexidade de pior caso da busca 
sequencial é O(n), o que corresponde à mesma ordem de complexidade da função. 
 
Resposta incorreta. 
E. 
V - V - F - F. 
(F) A operação básica de comparação do algoritmo precisa considerar a precedência de 
operadores aritméticos. Falsa, porque a operação elementar básica da função é corresponde 
a uma adição e a uma multiplicação. 
(F) A função executa n + 1 operações básicas para qualquer entrada de tamanho n. Falsa, 
porque a função executa uma adição e uma multiplicação para cada uma da n iterações, 
totalizando 2n operações. Porém, há ainda uma atribuição inicial (S = 0), o que resulta em 2n 
+ 1 operações básicas. 
(F) Considerando a complexidade de melhor caso da função, ela apresenta mais eficiência 
que no pior caso. Falsa, porque ambas as complexidades de melhor e pior caso são da ordem 
de O(n); logo, apresentam a mesma relação de eficiência. 
(V) Em comparação com a complexidade de pior caso da busca sequencial, ambas as funções 
apresentam a mesma eficiência. Verdadeiro, porque a complexidade de pior caso da busca 
sequencial é O(n), o que corresponde à mesma ordem de complexidade da função. 
 
Exercícios 
Respostas enviadas em: 06/03/2024 15:41 
3. 
Considerando a função f(n) = 5n2 + 2n + 4, pode-se afirmar que ela é dominada 
assintoticamente pela função g(n) = _____. Isso quer dizer que existem constantes 
positivas c e m tais que, para n => m, é válido que _____.Valores de c e m que validam essa 
inequação são _____, respectivamente. 
Assinale a alternativa que preenche corretamente as lacunas. 
Resposta incorreta. 
A. 
n3/ |f(n)| <= c · |g(n)| / 1 e 4 
Pode-se afirmar que g(n) = n3 domina f(n), pois existem c e m positivos tais que |f(n)| <= c · 
|g(n)|. De fato, é verdadeiro que 5n2 + 2n + 4 <= 5n3+ 2n3 + 4n3 = 11n3. Logo, tomando-se c 
= 11 e m = 1, tem-se que |f(n)| <= c · |g(n)| para todo n > m. Se os valores de c = 1 e m = 
4 fossem utilizados, não seria possível afirmar que f(n) é dominada assintoticamente por n3, 
pois, para n = 5 > m, f(n) = 125 + 10 + 4 > 125 = g(n). Além disso, não é possível encontrar 
uma constante c positiva que torne as desigualdades 5n2 + 2n + 4 <= cn2 e 5n2 + 2n + 4 
<= cn verdadeiras. Portanto, f(n) não é dominada assintoticamente nem por g(n) = n2, nem 
por g(n) = n. 
 
Resposta incorreta. 
B. 
n2/ |g(n)| <= c · |f(n)| / 1 e 0 
Pode-se afirmar que g(n) = n3 domina f(n), pois existem c e m positivos tais que |f(n)| <= c · 
|g(n)|. De fato, é verdadeiroque 5n2 + 2n + 4 <= 5n3+ 2n3 + 4n3 = 11n3. Logo, tomando-se c 
= 11 e m = 1, tem-se que |f(n)| <= c · |g(n)| para todo n > m. Se os valores de c = 1 e m = 
4 fossem utilizados, não seria possível afirmar que f(n) é dominada assintoticamente por n3, 
pois, para n = 5 > m, f(n) = 125 + 10 + 4 > 125 = g(n). Além disso, não é possível encontrar 
uma constante c positiva que torne as desigualdades 5n2 + 2n + 4 <= cn2 e 5n2 + 2n + 4 
<= cn verdadeiras. Portanto, f(n) não é dominada assintoticamente nem por g(n) = n2, nem 
por g(n) = n. 
 
Você acertou! 
C. 
n3 / |f(n)| <= c · |g(n)| / 11 e 1 
Pode-se afirmar que g(n) = n3 domina f(n), pois existem c e m positivos tais que |f(n)| <= c · 
|g(n)|. De fato, é verdadeiro que 5n2 + 2n + 4 <= 5n3+ 2n3 + 4n3 = 11n3. Logo, tomando-se c 
= 11 e m = 1, tem-se que |f(n)| <= c · |g(n)| para todo n > m. Se os valores de c = 1 e m = 
4 fossem utilizados, não seria possível afirmar que f(n) é dominada assintoticamente por n3, 
pois, para n = 5 > m, f(n) = 125 + 10 + 4 > 125 = g(n). Além disso, não é possível encontrar 
uma constante c positiva que torne as desigualdades 5n2 + 2n + 4 <= cn2 e 5n2 + 2n + 4 
<= cn verdadeiras. Portanto, f(n) não é dominada assintoticamente nem por g(n) = n2, nem 
por g(n) = n. 
 
Resposta incorreta. 
D. 
n / |f(n)| <= c · |g(n)| / 11 e 1 
Pode-se afirmar que g(n) = n3 domina f(n), pois existem c e m positivos tais que |f(n)| <= c · 
|g(n)|. De fato, é verdadeiro que 5n2 + 2n + 4 <= 5n3+ 2n3 + 4n3 = 11n3. Logo, tomando-se c 
= 11 e m = 1, tem-se que |f(n)| <= c · |g(n)| para todo n > m. Se os valores de c = 1 e m = 
4 fossem utilizados, não seria possível afirmar que f(n) é dominada assintoticamente por n3, 
pois, para n = 5 > m, f(n) = 125 + 10 + 4 > 125 = g(n). Além disso, não é possível encontrar 
uma constante c positiva que torne as desigualdades 5n2 + 2n + 4 <= cn2 e 5n2 + 2n + 4 
<= cn verdadeiras. Portanto, f(n) não é dominada assintoticamente nem por g(n) = n2, nem 
por g(n) = n. 
 
Resposta incorreta. 
E. 
n2/ |f(n)| <= c · |g(n)| / 1 e 0 
Pode-se afirmar que g(n) = n3 domina f(n), pois existem c e m positivos tais que |f(n)| <= c · 
|g(n)|. De fato, é verdadeiro que 5n2 + 2n + 4 <= 5n3+ 2n3 + 4n3 = 11n3. Logo, tomando-se c 
= 11 e m = 1, tem-se que |f(n)| <= c · |g(n)| para todo n > m. Se os valores de c = 1 e m = 
4 fossem utilizados, não seria possível afirmar que f(n) é dominada assintoticamente por n3, 
pois, para n = 5 > m, f(n) = 125 + 10 + 4 > 125 = g(n). Além disso, não é possível encontrar 
uma constante c positiva que torne as desigualdades 5n2 + 2n + 4 <= cn2 e 5n2 + 2n + 4 
<= cn verdadeiras. Portanto, f(n) não é dominada assintoticamente nem por g(n) = n2, nem 
por g(n) = n. 
 
Exercícios 
Respostas enviadas em: 06/03/2024 15:41 
4. 
A avaliação das complexidades de melhor e pior caso está vinculada aos passos executados 
por um algoritmo e pela operação elementar básica considerada. Seja a 
função EncontraMaior, que retorna o maior elemento de um vetor de números não 
negativos: 
 
 
função EncontraMaior(vetor) 
 maior = -1 
 para pos = 1 até n faça // n é o tamanho do vetor 
 se maior < vetor[pos] então 
 maior = vetor[pos] 
 fim se 
 fim para 
 retorna maior 
fim função 
 
 
Assinale a alternativa que indica as complexidades de melhor e pior caso do algoritmo, 
considerando a operação elementar básica como a atribuição à variável maior. 
Resposta incorreta. 
A. 
Melhor caso: O(1); pior caso: O(n2). 
Considerando a operação básica de atribuição, o melhor caso vai ocorrer quando o vetor 
está ordenado de forma decrescente. Assim, além da atribuição inicial (maior = -1), apenas 
uma nova atribuição acontecerá quando a primeira posição do vetor for verificada. Logo, o 
melhor caso tem complexidade O(1). Em contrapartida, o pior caso acontecerá quando o 
vetor estiver ordenado de forma crescente. Nesse caso, a variável maior receberá um novo 
valor a cada posição verificada do vetor. Logo, para um vetor de tamanho n, serão 
executadas n + 1 atribuições, ou seja, a complexidade do pior caso é O(n). 
 
Resposta incorreta. 
B. 
Melhor caso: O(1); pior caso: O(1). 
Considerando a operação básica de atribuição, o melhor caso vai ocorrer quando o vetor 
está ordenado de forma decrescente. Assim, além da atribuição inicial (maior = -1), apenas 
uma nova atribuição acontecerá quando a primeira posição do vetor for verificada. Logo, o 
melhor caso tem complexidade O(1). Em contrapartida, o pior caso acontecerá quando o 
vetor estiver ordenado de forma crescente. Nesse caso, a variável maior receberá um novo 
valor a cada posição verificada do vetor. Logo, para um vetor de tamanho n, serão 
executadas n + 1 atribuições, ou seja, a complexidade do pior caso é O(n). 
 
Resposta incorreta. 
C. 
Melhor caso: O(n2); pior caso: O(n2). 
Considerando a operação básica de atribuição, o melhor caso vai ocorrer quando o vetor 
está ordenado de forma decrescente. Assim, além da atribuição inicial (maior = -1), apenas 
uma nova atribuição acontecerá quando a primeira posição do vetor for verificada. Logo, o 
melhor caso tem complexidade O(1). Em contrapartida, o pior caso acontecerá quando o 
vetor estiver ordenado de forma crescente. Nesse caso, a variável maior receberá um novo 
valor a cada posição verificada do vetor. Logo, para um vetor de tamanho n, serão 
executadas n + 1 atribuições, ou seja, a complexidade do pior caso é O(n). 
 
Você acertou! 
D. 
Melhor caso: O(1); pior caso: O(n). 
Considerando a operação básica de atribuição, o melhor caso vai ocorrer quando o vetor 
está ordenado de forma decrescente. Assim, além da atribuição inicial (maior = -1), apenas 
uma nova atribuição acontecerá quando a primeira posição do vetor for verificada. Logo, o 
melhor caso tem complexidade O(1). Em contrapartida, o pior caso acontecerá quando o 
vetor estiver ordenado de forma crescente. Nesse caso, a variável maior receberá um novo 
valor a cada posição verificada do vetor. Logo, para um vetor de tamanho n, serão 
executadas n + 1 atribuições, ou seja, a complexidade do pior caso é O(n). 
 
Resposta incorreta. 
E. 
Melhor caso: O(n); pior caso: O(n2). 
Considerando a operação básica de atribuição, o melhor caso vai ocorrer quando o vetor 
está ordenado de forma decrescente. Assim, além da atribuição inicial (maior = -1), apenas 
uma nova atribuição acontecerá quando a primeira posição do vetor for verificada. Logo, o 
melhor caso tem complexidade O(1). Em contrapartida, o pior caso acontecerá quando o 
vetor estiver ordenado de forma crescente. Nesse caso, a variável maior receberá um novo 
valor a cada posição verificada do vetor. Logo, para um vetor de tamanho n, serão 
executadas n + 1 atribuições, ou seja, a complexidade do pior caso é O(n). 
 
Exercícios 
Respostas enviadas em: 06/03/2024 15:41 
5. 
A notação O, juntamente com outras duas notações complementares (ômega e teta), 
possibilita descrever o comportamento assintótico de funções de maneira precisa. 
Sejam as funções f(n) = 6n2 e g(n) = n2log2(n), assinale a alternativa que expressa 
corretamente a relação assintótica entre as duas funções. 
Resposta incorreta. 
A. 
g(n) é um limite inferior para f(n). 
É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)). Para isso, é 
preciso provar que existem c e m positivos tais que, para todo n > m, é verdadeiro que f(n) <= 
cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2, tem-se que 6 <= clog2(n). Tomando-se c = 
6 e m = 1, essa desigualdade é satisfeita. Portanto, g(n) é limite superior para f(n). Resta 
verificar se g(n) também é um limite superior para f(n). Nesse caso, seria verdadeiro que 
n2log2(n) <= c'6n2, com c' positivo e n > m' > 0. De maneira análoga, obtém-se que og2(n) <= 
6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'. Portanto, g(n) 
não é um limite superior para f(n). Consequentemente, g(n) também não é um limite justo 
para f(n). 
 
Resposta incorreta. 
B. 
g(n) é um limite justo paraf(n). 
É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)). Para isso, é 
preciso provar que existem c e m positivos tais que, para todo n > m, é verdadeiro que f(n) <= 
cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2, tem-se que 6 <= clog2(n). Tomando-se c = 
6 e m = 1, essa desigualdade é satisfeita. Portanto, g(n) é limite superior para f(n). Resta 
verificar se g(n) também é um limite superior para f(n). Nesse caso, seria verdadeiro que 
n2log2(n) <= c'6n2, com c' positivo e n > m' > 0. De maneira análoga, obtém-se que og2(n) <= 
6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'. Portanto, g(n) 
não é um limite superior para f(n). Consequentemente, g(n) também não é um limite justo 
para f(n). 
 
Resposta incorreta. 
C. 
f(n) é um limite superior para g(n). 
É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)). Para isso, é 
preciso provar que existem c e m positivos tais que, para todo n > m, é verdadeiro que f(n) <= 
cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2, tem-se que 6 <= clog2(n). Tomando-se c = 
6 e m = 1, essa desigualdade é satisfeita. Portanto, g(n) é limite superior para f(n). Resta 
verificar se g(n) também é um limite superior para f(n). Nesse caso, seria verdadeiro que 
n2log2(n) <= c'6n2, com c' positivo e n > m' > 0. De maneira análoga, obtém-se que og2(n) <= 
6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'. Portanto, g(n) 
não é um limite superior para f(n). Consequentemente, g(n) também não é um limite justo 
para f(n). 
 
Resposta incorreta. 
D. 
f(n) é um limite justo para g(n). 
É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)). Para isso, é 
preciso provar que existem c e m positivos tais que, para todo n > m, é verdadeiro que f(n) <= 
cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2, tem-se que 6 <= clog2(n). Tomando-se c = 
6 e m = 1, essa desigualdade é satisfeita. Portanto, g(n) é limite superior para f(n). Resta 
verificar se g(n) também é um limite superior para f(n). Nesse caso, seria verdadeiro que 
n2log2(n) <= c'6n2, com c' positivo e n > m' > 0. De maneira análoga, obtém-se que og2(n) <= 
6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'. Portanto, g(n) 
não é um limite superior para f(n). Consequentemente, g(n) também não é um limite justo 
para f(n). 
 
Você acertou! 
E. 
g(n) é um limite superior para f(n). 
É correto afirmar que g(n) é um limite superior para f(n), ou seja, f(n) = O(g(n)). Para isso, é 
preciso provar que existem c e m positivos tais que, para todo n > m, é verdadeiro que f(n) <= 
cg(n). Então, dividindo-se 6n2 <= cn2log2(n) por n2, tem-se que 6 <= clog2(n). Tomando-se c = 
6 e m = 1, essa desigualdade é satisfeita. Portanto, g(n) é limite superior para f(n). Resta 
verificar se g(n) também é um limite superior para f(n). Nesse caso, seria verdadeiro que 
n2log2(n) <= c'6n2, com c' positivo e n > m' > 0. De maneira análoga, obtém-se que og2(n) <= 
6c', mas não existe constante c' que satisfaça a desigualdade para todo n > m'. Portanto, g(n) 
não é um limite superior para f(n). Consequentemente, g(n) também não é um limite justo 
para f(n). 
 
Teorema mestre 
Exercícios 
Respostas enviadas em: 06/03/2024 14:39 
1. 
Relações de recorrência possibilitam que um problema seja modelado a partir de si próprio, 
considerando instâncias de menor tamanho. Esse é o caso da sequência de números S = (1, 
2, 22, 23, ..., 2n, ...). 
Assinale a alternativa que apresenta a recorrência que expressa corretamente a sequência 
de números S. 
Você acertou! 
A. 
 
 
 
 
 
Resposta incorreta. 
B. 
 
 
 
 
 
 
Resposta incorreta. 
C. 
 
 
 
 
 
 
Resposta incorreta. 
D. 
 
 
 
 
 
 
Resposta incorreta. 
E. 
 
 
 
 
 
 
 
Exercícios 
Respostas enviadas em: 06/03/2024 14:39 
2. 
Um dos métodos amplamente utilizados para a solução de recorrências é conhecido como o 
método da substituição. Considerando o uso desse método para verificar se O(n2) é solução 
para a recorrência T(n) = T(n – 1) + n , leia as afirmativas a seguir: 
I. Após a construção da desigualdade inicial, o próximo passo envolve a avaliação de n na 
solução proposta. 
II. Um dos passos da resolução envolve a avalição de uma diferença entre dois termos 
elevada à potência de 2. 
III. A aplicação do método se inicia com a construção da desigualdade a seguir ilustrada, 
onde c > 0. 
 
�(�)≤�(�2−�) 
IV. A conclusão da aplicação do método é que a solução proposta resolve a recorrência em 
questão. 
Assinale a alternativa correta. 
Resposta incorreta. 
A. 
Apenas as afirmativas I e II estão corretas. 
 
 
 
Você acertou! 
B. 
Apenas as afirmativas II e IV estão corretas. 
 
 
 
 
Resposta incorreta. 
C. 
Apenas as afirmativas I, II e III estão corretas. 
 
 
 
 
Resposta incorreta. 
D. 
Apenas as afirmativas II, III e IV estão corretas. 
 
 
 
 
Resposta incorreta. 
E. 
Apenas as afirmativas II e III estão corretas. 
 
 
 
 
 
Exercícios 
Respostas enviadas em: 06/03/2024 14:39 
3. 
A eficácia do método de substituição tem dependência intrínseca da proposição de uma 
boa solução (bom "chute") para a recorrência, e a verificação da solução é feita por indução 
matemática. Considere a seguinte recorrência: 
 
Marque V para verdadeira e F para falsa a respeito de sua resolução: 
( ) Se uma solução genérica O(♦) é proposta para a recorrência, então uma desigualdade do 
tipo ilustrado a seguir deve ser construída para qualquer valor de c. 
 
( ) Se O(log(n)) é uma solução proposta para a recorrência, então um dos passos do método 
envolve a avaliação da diferença log(n) – log2, e o método conclui com a validação da 
solução. 
( ) Se O(n2) é uma solução proposta para a recorrência, então o passo final do método vai 
gerar a expressão a seguir, que confirma a validade da solução. 
 
 
( ) Se O(n) é uma solução proposta para a recorrência, então a aplicação do método inicia 
com a substituição da recorrência pela expressão cn + 1 e conclui com a validação da 
solução. 
Assinale a alternativa que apresenta a sequência correta: 
Resposta incorreta. 
A. 
V – V – V – F. 
 
 
 
Resposta incorreta. 
B. 
F – F – F – V. 
 
 
 
 
Resposta correta. 
C. 
F – V – F – F. 
 
 
 
 
Você não acertou! 
D. 
V – F – F – V. 
 
 
 
 
Resposta incorreta. 
E. 
V – V – F – F. 
 
 
 
 
 
Exercícios 
Respostas enviadas em: 06/03/2024 14:39 
4. 
O teorema mestre constitui outra poderosa ferramenta para a solução de recorrências. 
Aplicando o método à recorrência 
 
�(�)=2�(�4)+1, o primeiro passo é avaliar a função nlogba, cujo valor é _________. 
Comparando o valor dessa função com f(n), conclui-se que f(n) é _____ nlogba. 
Nesse caso, o valor assintótico obtido a partir do teorema mestre é dado por _____. 
Marque a opção que preenche todas as lacunas: 
Resposta incorreta. 
A. 
nlog24/ limitada superiormente por / nlog24. 
Os termos considerados pelo teorema mestre são: a = 2, b = 4 e f(n) = 1. 
Logo, o primeiro passo do método é avaliar a função nlogba,cujo valor é dado por nlog42. Ao se 
comparar essa função com f(n), tem-se que f(n) = 1 = nlog42= n0,5 - £onde £ = 0,5 > 0. 
Nesse caso, conclui-se que f(n) é limitada superiormente por nlog42, o que permite a aplicação 
do caso 1 do teorema mestre. Portanto, o valor assintótico obtido a partir do teorema é nlog42. 
 
Resposta incorreta. 
B. 
nlog42/ delimitada assintoticamente por / nlog42log(n). 
Os termos considerados pelo teorema mestre são: a = 2, b = 4 e f(n) = 1. 
Logo, o primeiro passo do método é avaliar a função nlogba,cujo valor é dado por nlog42. Ao se 
comparar essa função com f(n), tem-se que f(n) = 1 = nlog42= n0,5 - £onde £ = 0,5 > 0. 
Nesse caso, conclui-se que f(n) é limitada superiormente por nlog42, o que permite a aplicação 
do caso 1 do teorema mestre. Portanto, o valor assintótico obtido a partir do teorema é nlog42. 
 
Resposta incorreta. 
C. 
nlog42/ limitadainferiormente por / 1. 
Os termos considerados pelo teorema mestre são: a = 2, b = 4 e f(n) = 1. 
Logo, o primeiro passo do método é avaliar a função nlogba,cujo valor é dado por nlog42. Ao se 
comparar essa função com f(n), tem-se que f(n) = 1 = nlog42= n0,5 - £onde £ = 0,5 > 0. 
Nesse caso, conclui-se que f(n) é limitada superiormente por nlog42, o que permite a aplicação 
do caso 1 do teorema mestre. Portanto, o valor assintótico obtido a partir do teorema é nlog42. 
 
Você acertou! 
D. 
nlog42/ limitada superiormente por / nlog42. 
Os termos considerados pelo teorema mestre são: a = 2, b = 4 e f(n) = 1. 
Logo, o primeiro passo do método é avaliar a função nlogba,cujo valor é dado por nlog42. Ao se 
comparar essa função com f(n), tem-se que f(n) = 1 = nlog42= n0,5 - £onde £ = 0,5 > 0. 
Nesse caso, conclui-se que f(n) é limitada superiormente por nlog42, o que permite a aplicação 
do caso 1 do teorema mestre. Portanto, o valor assintótico obtido a partir do teorema é nlog42. 
 
Resposta incorreta. 
E. 
nlog24/ limitada inferiormente por / 1. 
Os termos considerados pelo teorema mestre são: a = 2, b = 4 e f(n) = 1. 
Logo, o primeiro passo do método é avaliar a função nlogba,cujo valor é dado por nlog42. Ao se 
comparar essa função com f(n), tem-se que f(n) = 1 = nlog42= n0,5 - £onde £ = 0,5 > 0. 
Nesse caso, conclui-se que f(n) é limitada superiormente por nlog42, o que permite a aplicação 
do caso 1 do teorema mestre. Portanto, o valor assintótico obtido a partir do teorema é nlog42. 
 
 
 
Exercícios 
Respostas enviadas em: 06/03/2024 14:39 
5. 
Se a recorrência a ser resolvida satisfaz às condições para a aplicação do teorema mestre, a 
solução pode ser obtida de forma direta por meio do uso de um de seus três casos. Para a 
recorrência a seguir ilustrada, assinale a alternativa correta a respeito do uso do teorema 
mestre em sua resolução. 
 
 
�(�)=4�(�2)+�3 
Resposta incorreta. 
A. 
A comparação entre f(n) e nlogbaleva à conclusão de que f(n) < nlogba. Logo, o primeiro caso do 
teorema pode ser aplicado. 
 
 
 
Você não acertou! 
B. 
A verificação da condição 𝑎𝑓 ( 𝑛 𝑏 ) ≤ 𝑐𝑓(𝑛) demonstra que a desigualdade não pode ser 
satisfeita; logo, o terceiro caso do teorema não pode ser usado. 
 
 
 
 
Resposta incorreta. 
C. 
Uma constante £ = -1 pode ser utilizada para tornar a igualdade nlogba+£ verdadeira, o que 
possibilita o uso do segundo caso do teorema. 
Sem feedback 
 
Resposta incorreta. 
D. 
𝑇 ( 𝑛 ) = 𝑇 ( 𝑛2 ) + 𝑛 , 𝑠𝑒 𝑛 ≥ 1 
𝑇 ( 𝑛 ) = 1 , 𝑠𝑒 𝑛 = 0 
 
 
 
 
Resposta correta. 
E. 
O uso do teorema leva à aplicação do seu terceiro caso, o que implica T(n) apresentar um 
comportamento assintótico de n3. 
 
 
 
 
 
 
Recursão 
Exercícios 
Respostas enviadas em: 06/03/2024 11:47 
1. 
Uma progressão aritmética é uma sequência da forma 𝑎, 𝑎 + 𝑑, 𝑎 + 2𝑑, 𝑎 + 3𝑑, …, isto é, a 
sequência começa com o número 𝑎, e cada termo sucessivo é obtido do anterior 
adicionado 𝑑 (a diferença comum entre dois termos quaisquer). 
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 e 𝑎𝑘 + 1 = 𝑎𝑘 + 
𝑑para 𝑘≥ 1. 
Nesse contexto, encontre a solução geral para a progressão aritmética, assinalando a 
alternativa correta. 
Resposta incorreta. 
A. 
 
 
 
 
A sequência começa com o número 𝑎, e cada termo sucessivo é obtido do anterior 
adicionado 𝑑 (a diferença comum entre dois termos quaisquer). 
Por exemplo, (i) 𝑎 = 5, 𝑑 = 3: 5, 8, 9, 11, …; (ii) 𝑎 = 2, 𝑑 = 5: 2, 7, 12, 17, …; (iii) 𝑎 = 1, 𝑑 = 0: 1, 
1, 1, 1, 1, … 
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 𝑒 𝑎𝑘+1 = 𝑎𝑘 + 𝑑 para 
𝑘 ≥ 1. 
A solução é 𝑎𝑛 = 𝑎 + (𝑛 − 1)𝑑. 
 
Você acertou! 
B. 
 
 
 
 
 
A sequência começa com o número 𝑎, e cada termo sucessivo é obtido do anterior 
adicionado 𝑑 (a diferença comum entre dois termos quaisquer). 
Por exemplo, (i) 𝑎 = 5, 𝑑 = 3: 5, 8, 9, 11, …; (ii) 𝑎 = 2, 𝑑 = 5: 2, 7, 12, 17, …; (iii) 𝑎 = 1, 𝑑 = 0: 1, 
1, 1, 1, 1, … 
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 𝑒 𝑎𝑘+1 = 𝑎𝑘 + 𝑑 para 
𝑘 ≥ 1. 
A solução é 𝑎𝑛 = 𝑎 + (𝑛 − 1)𝑑. 
 
Resposta incorreta. 
C. 
 
 
 
 
 
A sequência começa com o número 𝑎, e cada termo sucessivo é obtido do anterior 
adicionado 𝑑 (a diferença comum entre dois termos quaisquer). 
Por exemplo, (i) 𝑎 = 5, 𝑑 = 3: 5, 8, 9, 11, …; (ii) 𝑎 = 2, 𝑑 = 5: 2, 7, 12, 17, …; (iii) 𝑎 = 1, 𝑑 = 0: 1, 
1, 1, 1, 1, … 
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 𝑒 𝑎𝑘+1 = 𝑎𝑘 + 𝑑 para 
𝑘 ≥ 1. 
A solução é 𝑎𝑛 = 𝑎 + (𝑛 − 1)𝑑. 
 
Resposta incorreta. 
D. 
 
 
 
 
A sequência começa com o número 𝑎, e cada termo sucessivo é obtido do anterior 
adicionado 𝑑 (a diferença comum entre dois termos quaisquer). 
Por exemplo, (i) 𝑎 = 5, 𝑑 = 3: 5, 8, 9, 11, …; (ii) 𝑎 = 2, 𝑑 = 5: 2, 7, 12, 17, …; (iii) 𝑎 = 1, 𝑑 = 0: 1, 
1, 1, 1, 1, … 
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 𝑒 𝑎𝑘+1 = 𝑎𝑘 + 𝑑 para 
𝑘 ≥ 1. 
A solução é 𝑎𝑛 = 𝑎 + (𝑛 − 1)𝑑. 
 
Resposta incorreta. 
E. 
 
 
 
 
 
A sequência começa com o número 𝑎, e cada termo sucessivo é obtido do anterior 
adicionado 𝑑 (a diferença comum entre dois termos quaisquer). 
Por exemplo, (i) 𝑎 = 5, 𝑑 = 3: 5, 8, 9, 11, …; (ii) 𝑎 = 2, 𝑑 = 5: 2, 7, 12, 17, …; (iii) 𝑎 = 1, 𝑑 = 0: 1, 
1, 1, 1, 1, … 
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 𝑒 𝑎𝑘+1 = 𝑎𝑘 + 𝑑 para 
𝑘 ≥ 1. 
A solução é 𝑎𝑛 = 𝑎 + (𝑛 − 1)𝑑. 
 
 
 
Exercícios 
Respostas enviadas em: 06/03/2024 11:47 
2. 
Na busca por compreender e representar conjuntos, três mecanismos fundamentais 
emergem como guias valiosos: a enumeração meticulosa de seus elementos, a clara 
definição das propriedades que os caracterizam e a intrigante construção indutiva que dá 
vida a novos membros. 
Cada um desses métodos oferece uma perspectiva única para desvendar a complexidade 
dos conjuntos, proporcionando ferramentas cruciais para os exploradores matemáticos. 
 
Observe cada um dos mecanismos para a descrição de elementos de um conjunto: 
 
 
Resposta incorreta. 
A. 
 
 
 
 
 
 
 
 
Resposta incorreta. 
B. 
 
 
 
 
 
 
Você não acertou! 
C. 
 
 
 
 
 
 
 
 
Resposta correta. 
D. 
 
 
 
 
 
 
 
 
Resposta incorreta. 
E. 
 
 
 
 
 
 
 Exercícios 
Respostas enviadas em: 06/03/2024 11:47 
3. 
A recursão pode ser usada para definir sequências, funções e conjuntos. As sequências 
podem ser definidas a partir do primeiro termo da sequência, 𝑎0, e de uma regra para 
encontrar um termo a partir do anterior, 𝑎𝑛 + 1. 
Quando se define uma sequência recursivamente, especifica-se como os seus termos são 
encontrados a partir de termos anteriores. 
Nesse contexto, considere a sequência definida por: 
𝑎1 = 2 
𝑎2 = 2 
𝑎3 = 6 
𝑎𝑛 = 3 × 𝑎𝑛 – 3, para 𝑛 > 3 
 
Calcule 𝑎4, 𝑎5, 𝑎6 e assinale a alternativa correta: 
Você acertou! 
A. 
6, 6, 18. 
𝑎4 = 3 × 𝑎4 – 3 = 3 × 𝑎1 = 3 × 2 = 6. 
𝑎5 = 3 × 𝑎5 − 3 = 3 × 𝑎2 = 3 × 2 = 6. 
𝑎6 = 3 × 𝑎6 − 3 = 3 × 𝑎3 = 3 × 6 = 18. 
 
Resposta incorreta. 
B. 
6, 18, 21. 
𝑎4 = 3 × 𝑎4 − 3 = 3 × 𝑎1 = 3 × 2 = 6. 
𝑎5 = 3 × 𝑎5 − 3 = 3 × 𝑎2 = 3 × 2 = 6. 
𝑎6 = 3 × 𝑎6 − 3 = 3 × 𝑎3 = 3 × 6 = 18. 
 
Resposta incorreta. 
C. 
6, 6, 6. 
𝑎4 = 3 × 𝑎4 − 3 = 3 × 𝑎1 = 3 × 2 = 6. 
𝑎5 = 3 × 𝑎5 − 3 = 3 × 𝑎2 = 3 × 2 = 6. 
𝑎6 = 3 × 𝑎6 − 3 = 3 × 𝑎3 = 3 × 6 = 18. 
 
Resposta incorreta. 
D. 
6, 18, 54. 
𝑎4 = 3 × 𝑎4 − 3 = 3 × 𝑎1 = 3 × 2 = 6. 
𝑎5 = 3 × 𝑎5 − 3 = 3 × 𝑎2 = 3 × 2 = 6. 
𝑎6 = 3 × 𝑎6 − 3 = 3 × 𝑎3 = 3 × 6 = 18. 
 
Resposta incorreta. 
E. 
6, 18, 18. 
𝑎4 = 3 × 𝑎4 − 3 = 3 × 𝑎1 = 3 × 2 = 6. 
𝑎5 = 3 × 𝑎5 − 3 = 3 × 𝑎2 = 3 × 2 = 6. 
𝑎6 = 3 × 𝑎6 − 3 = 3 × 𝑎3 = 3 × 6 = 18. 
 
 
Exercícios 
Respostas enviadas em: 06/03/2024 11:47 
4. 
Nos domínios da teoria das linguagens formais, há o conjunto de todas as cadeias, sejam 
palavras ou strings, de comprimento finito formadas por símbolos extraídos de um 
alfabetoA. Esse conjunto peculiar e abrangente é devidamente identificado como A*. 
Dessa forma, pode-se realizar uma definição recursiva de A* como: 
I – A cadeia vazia, denotada por ε, pertence a A*; 
II – Um único símbolo qualquer de A pertence a A*; 
III – Se x e y são cadeias em A*, então a concatenação xy também pertence a A*. 
Dado o alfabeto A = {0, 1, 2}, apresente as cinco menores cadeias de A*: 
Resposta incorreta. 
A. 
0, 1, 2, 00. 
Pela regra I, tem-se, inicialmente, que A* = {ε}. 
Pela regra II, tem-se que A* = {ε, 0, 1, 2}. 
Pela regra III, tem-se que A* = {ε, 0, 1, 2, 00}. 
 
Resposta incorreta. 
B. 
0, 1, 2, 00, 01. 
Pela regra I, tem-se, inicialmente, que A* = {ε}. 
Pela regra II, tem-se que A* = {ε, 0, 1, 2}. 
Pela regra III, tem-se que A* = {ε, 0, 1, 2, 00}. 
 
Resposta incorreta. 
C. 
0, 1, 2, 00, 11. 
Pela regra I, tem-se, inicialmente, que A* = {ε}. 
Pela regra II, tem-se que A* = {ε, 0, 1, 2}. 
Pela regra III, tem-se que A* = {ε, 0, 1, 2, 00}. 
 
Resposta incorreta. 
D. 
ε, 0, 1, 00, 01. 
Pela regra I, tem-se, inicialmente, que A* = {ε}. 
Pela regra II, tem-se que A* = {ε, 0, 1, 2}. 
Pela regra III, tem-se que A* = {ε, 0, 1, 2, 00}. 
 
Você acertou! 
E. 
ε, 0, 1, 2, 00. 
Pela regra I, tem-se, inicialmente, que A* = {ε}. 
Pela regra II, tem-se que A* = {ε, 0, 1, 2}. 
Pela regra III, tem-se que A* = {ε, 0, 1, 2, 00}. 
 
Exercícios 
Respostas enviadas em: 06/03/2024 11:47 
5. 
Sabe-se são usadas duas etapas para definir uma função com o conjunto dos números 
inteiros não negativos como seu domínio, a saber: passo base, em que se especifica o valor 
da função em zero; e passo recursivo, em que se fornece uma regra para encontrar seu 
valor em um número inteiro a partir dos valores dos números inteiros menores. 
Nesse contexto, suponha que 𝑓 seja definida recursivamente por: 𝑓0 = 3, 𝑓𝑛 + 1 = 2𝑓𝑛 + 3, 
encontre 𝑓1, 𝑓2, 𝑓3 e 𝑓(4), assinalando a alternativa correta. 
Resposta incorreta. 
A. 
 
 
 
 
 
 
A partir da definição recursiva, tem-se que: 
𝑓(1) = 2 𝑓(0) + 3 = 2 × 3 + 3 = 9 
𝑓(2) = 2 𝑓(1) + 3 = 2 × 9 + 3 = 21 
𝑓(3) = 2 𝑓(2) + 3 = 2 × 21 + 3 = 45 
𝑓(4) = 2 𝑓(3) + 3 = 2 × 45 + 3 = 93 
 
Resposta incorreta. 
B. 
 
 
 
 
 
A partir da definição recursiva, tem-se que: 
𝑓(1) = 2 𝑓(0) + 3 = 2 × 3 + 3 = 9 
𝑓(2) = 2 𝑓(1) + 3 = 2 × 9 + 3 = 21 
𝑓(3) = 2 𝑓(2) + 3 = 2 × 21 + 3 = 45 
𝑓(4) = 2 𝑓(3) + 3 = 2 × 45 + 3 = 93 
 
Você acertou! 
C. 
 
 
 
 
 
 
A partir da definição recursiva, tem-se que: 
𝑓(1) = 2 𝑓(0) + 3 = 2 × 3 + 3 = 9 
𝑓(2) = 2 𝑓(1) + 3 = 2 × 9 + 3 = 21 
𝑓(3) = 2 𝑓(2) + 3 = 2 × 21 + 3 = 45 
𝑓(4) = 2 𝑓(3) + 3 = 2 × 45 + 3 = 93 
 
Resposta incorreta. 
D. 
 
 
 
 
 
A partir da definição recursiva, tem-se que: 
𝑓(1) = 2 𝑓(0) + 3 = 2 × 3 + 3 = 9 
𝑓(2) = 2 𝑓(1) + 3 = 2 × 9 + 3 = 21 
𝑓(3) = 2 𝑓(2) + 3 = 2 × 21 + 3 = 45 
𝑓(4) = 2 𝑓(3) + 3 = 2 × 45 + 3 = 93 
 
Resposta incorreta. 
E. 
 
 
 
 
 
A partir da definição recursiva, tem-se que: 
𝑓(1) = 2 𝑓(0) + 3 = 2 × 3 + 3 = 9 
𝑓(2) = 2 𝑓(1) + 3 = 2 × 9 + 3 = 21 
𝑓(3) = 2 𝑓(2) + 3 = 2 × 21 + 3 = 45 
𝑓(4) = 2 𝑓(3) + 3 = 2 × 45 + 3 = 93 
 
 
 
Modelos de computação e eficiência de algoritmos 
xercícios 
Respostas enviadas em: 06/03/2024 10:09 
1. 
Entender o melhor e o pior caso de algoritmos é fundamental para escolher os algoritmos 
mais eficientes para determinado conjunto de entradas e, assim, eleger qual utilizar em 
soluções propostas, uma vez que um mesmo algoritmo pode ser muito veloz para 
determinado conjunto de casos, mas muito lento para outro grande conjunto de entradas. 
Entre as opções elencadas a seguir, marque aquela que apresenta a complexidade do pior 
caso e do melhor caso para um algoritmo que busca um valor em um vetor de forma 
sequencial, ou seja, percorre todo o vetor do início ao fim buscando pelo elemento 
desejado. 
Você acertou! 
A. 
Pior caso: N; melhor caso: 1. 
O pior caso é N, pois, em uma entrada em que o elemento não existe, é necessário percorrer 
todo o vetor. Já o melhor caso seria o elemento que está na primeira posição, por isso 
constante, ou seja, custo 1. Para o pior caso 1 e o melhor caso N, deveria ser o inverso disso. 
Para a complexidade ser log N, alguma recursão deveria ser utilizada, em que, em cada 
iteração, ela diminui pela metade o espaço de busca. Por fim, para ser N², seriam necessários 
dois laços alinhados. 
 
Resposta incorreta. 
B. 
Pior caso: 1; melhor caso: N. 
O pior caso é N, pois, em uma entrada em que o elemento não existe, é necessário percorrer 
todo o vetor. Já o melhor caso seria o elemento que está na primeira posição, por isso 
constante, ou seja, custo 1. Para o pior caso 1 e o melhor caso N, deveria ser o inverso disso. 
Para a complexidade ser log N, alguma recursão deveria ser utilizada, em que, em cada 
iteração, ela diminui pela metade o espaço de busca. Por fim, para ser N², seriam necessários 
dois laços alinhados. 
 
Resposta incorreta. 
C. 
Pior caso: N; melhor caso: log N. 
O pior caso é N, pois, em uma entrada em que o elemento não existe, é necessário percorrer 
todo o vetor. Já o melhor caso seria o elemento que está na primeira posição, por isso 
constante, ou seja, custo 1. Para o pior caso 1 e o melhor caso N, deveria ser o inverso disso. 
Para a complexidade ser log N, alguma recursão deveria ser utilizada, em que, em cada 
iteração, ela diminui pela metade o espaço de busca. Por fim, para ser N², seriam necessários 
dois laços alinhados. 
 
Resposta incorreta. 
D. 
Pior caso: log N; melhor caso: 1. 
O pior caso é N, pois, em uma entrada em que o elemento não existe, é necessário percorrer 
todo o vetor. Já o melhor caso seria o elemento que está na primeira posição, por isso 
constante, ou seja, custo 1. Para o pior caso 1 e o melhor caso N, deveria ser o inverso disso. 
Para a complexidade ser log N, alguma recursão deveria ser utilizada, em que, em cada 
iteração, ela diminui pela metade o espaço de busca. Por fim, para ser N², seriam necessários 
dois laços alinhados. 
 
Resposta incorreta. 
E. 
Pior caso: N²; melhor caso: N. 
O pior caso é N, pois, em uma entrada em que o elemento não existe, é necessário percorrer 
todo o vetor. Já o melhor caso seria o elemento que está na primeira posição, por isso 
constante, ou seja, custo 1. Para o pior caso 1 e o melhor caso N, deveria ser o inverso disso. 
Para a complexidade ser log N, alguma recursão deveria ser utilizada, em que, em cada 
iteração, ela diminui pela metade o espaço de busca. Por fim, para ser N², seriam necessários 
dois laços alinhados. 
 
Exercícios 
Respostas enviadas em: 06/03/2024 10:09 
2. 
Ao longo do tempo, diversas soluções para problemas conhecidos foram propostas, cada 
uma com suas particularidades que envolvem desde a eficiência até a qualidade do 
resultado. 
Sabendo que todas as soluções para um problema têm a mesma qualidade de resultado, 
qual das complexidades elencadas a seguir indica a solução com melhor eficiência de 
tempo? 
Você acertou! 
A. 
log N. 
A melhor eficiência é do algoritmo com complexidade log N. Após, haveria um tempo linear, 
ou seja, N. Depois do linear, viria o N log N, seguido das complexidades quadráticas e 
cúbicas, que são N² e N³, respectivamente. 
 
Resposta incorreta. 
B. 
N log N. 
A melhor eficiência é do algoritmo com complexidade log N. Após, haveria um tempo linear, 
ou seja, N. Depois do linear, viria o N log N, seguido das complexidades quadráticas e 
cúbicas, que são N² e N³, respectivamente. 
 
Resposta incorreta. 
C. 
N. 
A melhor eficiência é do algoritmo com complexidade log N. Após, haveria um tempo linear, 
ou seja, N. Depois do linear, viria o N log N, seguido das complexidades quadráticas e 
cúbicas, que são N² e N³, respectivamente. 
 
Resposta incorreta. 
D. 
N². 
A melhor eficiência é do algoritmo com complexidade log N. Após, haveria um tempo linear, 
ou seja, N. Depois do linear, viria o N log N, seguido das complexidades quadráticas e 
cúbicas, que são N² e N³, respectivamente. 
 
Resposta incorreta. 
E. 
N³. 
Amelhor eficiência é do algoritmo com complexidade log N. Após, haveria um tempo linear, 
ou seja, N. Depois do linear, viria o N log N, seguido das complexidades quadráticas e 
cúbicas, que são N² e N³, respectivamente. 
 
Exercícios 
Respostas enviadas em: 06/03/2024 10:09 
3. 
A ordenação de vetores é um dos problemas mais estudados em computação, sendo que 
diferentes soluções foram propostas ao longo do tempo. Diversas dessas soluções têm 
complexidade de tempo semelhante, e o que as diferencia é, principalmente, a 
complexidade de espaço. 
Sabendo que existe limitação de espaço para sua execução, qual das complexidades de 
espaço elencadas a seguir é a mais eficiente? 
Resposta incorreta. 
A. 
log N. 
No caso da complexidade de espaço, a mais eficiente é a 1, a qual utiliza apenas constantes 
extras e nenhum dado relacionado ao tamanho da entrada. Após, seria a complexidade de 
espaço log N, seguida da complexidade N e, por fim, N log N e N². 
 
Resposta incorreta. 
B. 
N. 
No caso da complexidade de espaço, a mais eficiente é a 1, a qual utiliza apenas constantes 
extras e nenhum dado relacionado ao tamanho da entrada. Após, seria a complexidade de 
espaço log N, seguida da complexidade N e, por fim, N log N e N². 
 
Resposta incorreta. 
C. 
N². 
No caso da complexidade de espaço, a mais eficiente é a 1, a qual utiliza apenas constantes 
extras e nenhum dado relacionado ao tamanho da entrada. Após, seria a complexidade de 
espaço log N, seguida da complexidade N e, por fim, N log N e N². 
 
Você acertou! 
D. 
1. 
No caso da complexidade de espaço, a mais eficiente é a 1, a qual utiliza apenas constantes 
extras e nenhum dado relacionado ao tamanho da entrada. Após, seria a complexidade de 
espaço log N, seguida da complexidade N e, por fim, N log N e N². 
 
Resposta incorreta. 
E. 
N log N. 
No caso da complexidade de espaço, a mais eficiente é a 1, a qual utiliza apenas constantes 
extras e nenhum dado relacionado ao tamanho da entrada. Após, seria a complexidade de 
espaço log N, seguida da complexidade N e, por fim, N log N e N². 
 
Exercícios 
Respostas enviadas em: 06/03/2024 10:09 
4. 
A operação de multiplicação de matrizes é base de muitos solucionadores de equações 
diferenciais e também simuladores de fenômenos físicos. 
Geralmente, essa operação é implementada por um algoritmo que tem três laços alinhados 
de execução. Sabendo que, dentro desses laços, existem apenas operações de tempo 
constante, qual é a complexidade de tempo da multiplicação de matrizes implementada 
dessa maneira? 
Resposta incorreta. 
A. 
1. 
A alternativa correta é N³, pois foi indicado que existe um algoritmo para multiplicação de 
matrizes com três laços alinhados. Para ser N², deveriam existir apenas dois laços. A 
complexidade 1 só seria encontrada caso não existissem laços. Por fim, as complexidades N 
e log N representam um laço e uma função recursiva que diminui a quantidade de operações 
pela metade a cada iteração. 
 
Resposta incorreta. 
B. 
N. 
A alternativa correta é N³, pois foi indicado que existe um algoritmo para multiplicação de 
matrizes com três laços alinhados. Para ser N², deveriam existir apenas dois laços. A 
complexidade 1 só seria encontrada caso não existissem laços. Por fim, as complexidades N 
e log N representam um laço e uma função recursiva que diminui a quantidade de operações 
pela metade a cada iteração. 
 
Resposta incorreta. 
C. 
N². 
A alternativa correta é N³, pois foi indicado que existe um algoritmo para multiplicação de 
matrizes com três laços alinhados. Para ser N², deveriam existir apenas dois laços. A 
complexidade 1 só seria encontrada caso não existissem laços. Por fim, as complexidades N 
e log N representam um laço e uma função recursiva que diminui a quantidade de operações 
pela metade a cada iteração. 
 
Você acertou! 
D. 
N³. 
A alternativa correta é N³, pois foi indicado que existe um algoritmo para multiplicação de 
matrizes com três laços alinhados. Para ser N², deveriam existir apenas dois laços. A 
complexidade 1 só seria encontrada caso não existissem laços. Por fim, as complexidades N 
e log N representam um laço e uma função recursiva que diminui a quantidade de operações 
pela metade a cada iteração. 
 
Resposta incorreta. 
E. 
log N. 
A alternativa correta é N³, pois foi indicado que existe um algoritmo para multiplicação de 
matrizes com três laços alinhados. Para ser N², deveriam existir apenas dois laços. A 
complexidade 1 só seria encontrada caso não existissem laços. Por fim, as complexidades N 
e log N representam um laço e uma função recursiva que diminui a quantidade de operações 
pela metade a cada iteração. 
 
Exercícios 
Respostas enviadas em: 06/03/2024 10:09 
5. 
Existe uma solução para a busca de elementos em um vetor que assume que existe um 
vetor já ordenado e realiza uma busca guiada nele, de maneira que, a cada iteração, metade 
do vetor restante é ignorada, buscando o elemento desejado apenas na outra metade. 
Qual é a complexidade de tempo de soluções desse tipo, ou seja, que em cada iteração 
diminuem o tamanho do problema pela metade, de maneira similar à busca mencionada? 
Resposta incorreta. 
A. 
N² log N. 
A resposta correta é a complexidade log N, pois, em cada iteração, o tamanho do problema é 
diminuído pela metade. Outras complexidades, como N log N e N² log N, são representadas, 
por exemplo, por um e dois laços respectivamente, que chamam uma busca binária dentro 
deles. Por fim, complexidades como N² e N seriam encontradas em dois e um laço alinhados. 
 
Resposta incorreta. 
B. 
N². 
A resposta correta é a complexidade log N, pois, em cada iteração, o tamanho do problema é 
diminuído pela metade. Outras complexidades, como N log N e N² log N, são representadas, 
por exemplo, por um e dois laços respectivamente, que chamam uma busca binária dentro 
deles. Por fim, complexidades como N² e N seriam encontradas em dois e um laço alinhados. 
 
Resposta incorreta. 
C. 
N. 
A resposta correta é a complexidade log N, pois, em cada iteração, o tamanho do problema é 
diminuído pela metade. Outras complexidades, como N log N e N² log N, são representadas, 
por exemplo, por um e dois laços respectivamente, que chamam uma busca binária dentro 
deles. Por fim, complexidades como N² e N seriam encontradas em dois e um laço alinhados. 
 
Resposta incorreta. 
D. 
N log N. 
A resposta correta é a complexidade log N, pois, em cada iteração, o tamanho do problema é 
diminuído pela metade. Outras complexidades, como N log N e N² log N, são representadas, 
por exemplo, por um e dois laços respectivamente, que chamam uma busca binária dentro 
deles. Por fim, complexidades como N² e N seriam encontradas em dois e um laço alinhados. 
 
Você acertou! 
E. 
log N. 
A resposta correta é a complexidade log N, pois, em cada iteração, o tamanho do problema é 
diminuído pela metade. Outras complexidades, como N log N e N² log N, são representadas, 
por exemplo, por um e dois laços respectivamente, que chamam uma busca binária dentro 
deles. Por fim, complexidades como N² e N seriam encontradas em dois e um laço alinhados.