Complexidade e Problemas NP

ESTÁCIO EAD

Isakinhooo

em 24/11/2025

Questões resolvidas

Analise as seguintes afirmativas
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema.
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma.
Apenas a afirmativa I está correta.
As afirmativas I, II e III estão corretas.
Apenas as afirmativas I e II estão corretas.
Apenas as afirmativas I e III estão corretas.
Apenas a afirmativa II está correta.

Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica P = NP.
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.
A asserção I é uma proposição verdadeira e a II é uma proposição verdadeira.
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 e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras e a II é uma justificativa correta da I.
As asserções I e II são proposições falsas.

Considere uma Máquina de Turing (MT) T dada pelas quíntuplas: 1. (0, 1, 1, 0, D) 2. (0, b, 1, 1, H) Considere que 0 é um estado inicial e 1 é um estado final. A configuração inicial da fita é igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. Qual é a função que essa MT calcula?
2 +1n
2 - 1n+1
2 -1n
2n+1
2n

Existem dois tipos principais de complexidade computacional para um algoritmo: complexidade de tempo e complexidade de espaço. Nesse sentido, o que é falso para o problema da classe P?
O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
É computável por uma máquina de Turing determinística em tempo polinomial.
Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores.
P é definido como o conjunto de todos os problemas de decisão para os quais existe um algoritmo que pode ser realizado por uma máquina de Turing não-determinística em tempo polinomial.

Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a linguagem recursivamente enumerável. Acerca de suas características assinale a afirmação verdadeira.
Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.

Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral.
Acerca de suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing?
Pilha.
Fita de entrada.
Cabeça de leitura-escrita.
Direção de leitura.
Controle finito.

Uma analogia matemática simples do conceito de redutibilidade ocorre quando desejamos medir a área de um retângulo. Nesse sentido, podemos reduzir o problema a medição da largura e comprimento. Acerca dos conceitos de redução, o que é verdadeiro para redutibilidade?
Se A se reduz a B, podemos usar uma solução de A para resolver B.
Converter um problema resolvido em outro problema não resolvido.
Converter um problema não resolvido em outro problema não resolvido.
Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
Se A se reduz a B, podemos usar uma solução de B para resolver A.

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w. Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente. Para o problema da parada:
Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.

Conteúdos escolhidos para você

4 pág.

Atividade Objetiva 3 - Complexidade de Algoritmos - NOTA 1.0 de 1.0

87 pág.

TODAS AS ATIVIDADES

UNINASSAU PARANAÍBA

9 pág.

EXERCICIO 9

ESTÁCIO

6 pág.

ANALISE DE ALGORITMOS - ATIVIDADE 1 Unidades de Estudo 1 e 2

UAM

10 pág.

EXERCICIO 8

ESTÁCIO

Perguntas dessa disciplina

Leia o trecho a seguir. No que tange às questões relacionadas à efetiva ordenação dos algoritmos, podemos inicialmente relembrar que a definição de...

FMU

O conceito de algoritmo vai além da programação de computadores. Ele está presente em diversas atividades cotidianas, como seguir uma receita, montar

UCAM

Ao utilizarmos métodos iterativos para encontrar a solução de uma equação ou sistema de equações, geramos uma sequência de aproximações que, idealm...

FACAP

Funções recursivas são aquelas que se chamam a si mesmas durante sua execução. Essa técnica é utilizada para resolver problemas que podem ser dividido

ANHANGUERA

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Tur...

ESTÁCIO

Material

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

Analise as seguintes afirmativas
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema.
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma.
Apenas a afirmativa I está correta.
As afirmativas I, II e III estão corretas.
Apenas as afirmativas I e II estão corretas.
Apenas as afirmativas I e III estão corretas.
Apenas a afirmativa II está correta.

Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica P = NP.
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.
A asserção I é uma proposição verdadeira e a II é uma proposição verdadeira.
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 e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras e a II é uma justificativa correta da I.
As asserções I e II são proposições falsas.

Considere uma Máquina de Turing (MT) T dada pelas quíntuplas: 1. (0, 1, 1, 0, D) 2. (0, b, 1, 1, H) Considere que 0 é um estado inicial e 1 é um estado final. A configuração inicial da fita é igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. Qual é a função que essa MT calcula?
2 +1n
2 - 1n+1
2 -1n
2n+1
2n

Existem dois tipos principais de complexidade computacional para um algoritmo: complexidade de tempo e complexidade de espaço. Nesse sentido, o que é falso para o problema da classe P?
O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
É computável por uma máquina de Turing determinística em tempo polinomial.
Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores.
P é definido como o conjunto de todos os problemas de decisão para os quais existe um algoritmo que pode ser realizado por uma máquina de Turing não-determinística em tempo polinomial.

Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a linguagem recursivamente enumerável. Acerca de suas características assinale a afirmação verdadeira.
Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.

Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral.
Acerca de suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing?
Pilha.
Fita de entrada.
Cabeça de leitura-escrita.
Direção de leitura.
Controle finito.

Uma analogia matemática simples do conceito de redutibilidade ocorre quando desejamos medir a área de um retângulo. Nesse sentido, podemos reduzir o problema a medição da largura e comprimento. Acerca dos conceitos de redução, o que é verdadeiro para redutibilidade?
Se A se reduz a B, podemos usar uma solução de A para resolver B.
Converter um problema resolvido em outro problema não resolvido.
Converter um problema não resolvido em outro problema não resolvido.
Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
Se A se reduz a B, podemos usar uma solução de B para resolver A.

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w. Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente. Para o problema da parada:
Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.

Conteúdos escolhidos para você

4 pág.

Atividade Objetiva 3 - Complexidade de Algoritmos - NOTA 1.0 de 1.0

87 pág.

TODAS AS ATIVIDADES

UNINASSAU PARANAÍBA

9 pág.

EXERCICIO 9

ESTÁCIO

6 pág.

ANALISE DE ALGORITMOS - ATIVIDADE 1 Unidades de Estudo 1 e 2

UAM

10 pág.

EXERCICIO 8

ESTÁCIO

Perguntas dessa disciplina

Leia o trecho a seguir. No que tange às questões relacionadas à efetiva ordenação dos algoritmos, podemos inicialmente relembrar que a definição de...

FMU

O conceito de algoritmo vai além da programação de computadores. Ele está presente em diversas atividades cotidianas, como seguir uma receita, montar

UCAM

Ao utilizarmos métodos iterativos para encontrar a solução de uma equação ou sistema de equações, geramos uma sequência de aproximações que, idealm...

FACAP

Funções recursivas são aquelas que se chamam a si mesmas durante sua execução. Essa técnica é utilizada para resolver problemas que podem ser dividido

ANHANGUERA

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Tur...

ESTÁCIO

Prévia do material em texto

A
B
C
1 Marcar para revisão
Analise as seguintes afirmativas
I. Em um problema de decisão, o
objetivo é decidir a resposta sim ou
não a uma questão. Em um problema
de localização, procura-se localizar
uma certa estrutura que satisfaça
um conjunto de propriedades dadas.
Se as propriedades envolverem
critérios de otimização, então o
problema é dito de otimização.
II. A teoria da complexidade
restringe-se a problemas de
decisão, já que o estudo de
problemas NP-completos é aplicado
somente para esse tipo de problema.
III. Os problemas NP-Completos são
considerados como os problemas
mais difíceis em NP. Se qualquer
problema NP-Completo pode ser
resolvido em tempo polinomial,
então todos os problemas em NP
podem ser resolvidos da mesma
forma.
A análise permite concluir que:
Apenas a afirmativa I está
correta.
Apenas a afirmativa II está
correta.
Apenas as afirmativas I e II
estão corretas.
Questão 1 de 10
Em branco (10)
1 2 3 4 5
6 7 8 9 10
Finalizar exercícios
Lista de exercícios Computabilida… Sair e finalizar depois
24/11/2025, 10:41 estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/
https://estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/ 1/10
D
E
A
B
Apenas as afirmativas I e III
estão corretas.
As afirmativas I, II e III estão
corretas.
2 Marcar para revisão
Um cientista afirma ter encontrado
uma redução polinomial de um
problema NP-Completo para um
problema pertencente à classe P.
Considerando que esta afirmação tem
implicações importantes no que diz
respeito à complexidade
computacional, avalie as seguintes
asserções e a relação proposta entre
elas.
I. A descoberta do cientista implica P =
NP.
PORQUE
II. A descoberta do cientista implica na
existência de algoritmos polinomiais
para todos os problemas NP-
Completos.
A respeito dessas asserções, assinale
a opção correta.
As asserções I e II são
proposições verdadeiras e a II
é uma justificativa correta da
I.
As asserções I e II são
proposições verdadeiras, mas
a II não é uma justificativa
correta da I.
24/11/2025, 10:41 estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/
https://estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/ 2/10
C
D
E
A
B
C
D
E
A asserção I é uma
proposição verdadeira e a II é
uma proposição verdadeira.
A asserção I é uma
proposição falsa e a II é uma
proposição verdadeira.
As asserções I e II são
proposições falsas.
3 Marcar para revisão
Na máquina de Turing, a função de
transição δ está na forma: (onde Q é o
conjunto finito de estados, Σ é o
conjunto finito de alfabetos de entrada,
Γ é o símbolo de fita permitido, L
significa esquerda, R significa direita e
H significa parada).
Q × Γ → (Q × Γ × {L, R, H})
Q ×Σ→ (Q × {L, R, H})
Q ×Σ→ (Q × Σ × {L, R, H})
Q × Γ → (Q × Σ)
Q × Γ → (Q × Σ × {H})
4 Marcar para revisão
24/11/2025, 10:41 estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/
https://estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/ 3/10
A
B
C
D
E
Para resolver problemas, precisamos
construir algoritmos. Para esses
algoritmos, suas complexidades
precisam ser calculadas, as quais são
necessárias para analisar os
algoritmos e encontrar o mais
adequado. Considere as seguintes
quatro funções:
f1 (n) = 2n
f2 (n) = n
f3 (n) = 2n
f4 (n) = 2 + 3
Quais das seguintes sentenças
matemáticas são verdadeiras?
I. para n > 0, f2 (n) 2, f1 (n) 2, f3 (n)entrada w.
Mais informalmente, o mesmo
problema também pode ser assim
descrito: dados um algoritmo e uma
entrada finita, decidir se o algoritmo
termina ou se executará
indefinidamente. Para o problema da
parada:
Existe algoritmo exato de
tempo de execução
polinomial para solucioná-lo.
Existe algoritmo exato de
tempo de execução
exponencial para solucioná-
lo.
Não existe algoritmo exato,
mas existe algoritmo de
aproximação de tempo de
execução exponencial que o
soluciona, fornecendo
respostas aproximadas.
24/11/2025, 10:41 estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/
https://estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/ 9/10
D
E
Não existe algoritmo exato,
mas existe algoritmo de
aproximação de tempo de
execução polinomial que o
soluciona, fornecendo
respostas aproximadas.
Não existe algoritmo que o
solucione, não importa
quanto tempo seja
disponibilizado.
24/11/2025, 10:41 estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/
https://estacio.saladeavaliacoes.com.br/exercicio/69246071c93a20b4b3ac302e/ 10/10

Complexidade e Problemas NP

ESTÁCIO EAD

Ferramentas de estudo

Conteúdos escolhidos para você

Atividade Objetiva 3 - Complexidade de Algoritmos - NOTA 1.0 de 1.0

TODAS AS ATIVIDADES

EXERCICIO 9

ANALISE DE ALGORITMOS - ATIVIDADE 1 Unidades de Estudo 1 e 2

EXERCICIO 8

Perguntas dessa disciplina

Leia o trecho a seguir. No que tange às questões relacionadas à efetiva ordenação dos algoritmos, podemos inicialmente relembrar que a definição de...

O conceito de algoritmo vai além da programação de computadores. Ele está presente em diversas atividades cotidianas, como seguir uma receita, montar

Ao utilizarmos métodos iterativos para encontrar a solução de uma equação ou sistema de equações, geramos uma sequência de aproximações que, idealm...

Funções recursivas são aquelas que se chamam a si mesmas durante sua execução. Essa técnica é utilizada para resolver problemas que podem ser dividido

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Tur...

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Crie sua conta grátis para liberar esse material. 🤩

Conteúdos escolhidos para você

Atividade Objetiva 3 - Complexidade de Algoritmos - NOTA 1.0 de 1.0

TODAS AS ATIVIDADES

EXERCICIO 9

ANALISE DE ALGORITMOS - ATIVIDADE 1 Unidades de Estudo 1 e 2

EXERCICIO 8

Perguntas dessa disciplina

Leia o trecho a seguir. No que tange às questões relacionadas à efetiva ordenação dos algoritmos, podemos inicialmente relembrar que a definição de...

O conceito de algoritmo vai além da programação de computadores. Ele está presente em diversas atividades cotidianas, como seguir uma receita, montar

Ao utilizarmos métodos iterativos para encontrar a solução de uma equação ou sistema de equações, geramos uma sequência de aproximações que, idealm...

Funções recursivas são aquelas que se chamam a si mesmas durante sua execução. Essa técnica é utilizada para resolver problemas que podem ser dividido

O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Tur...

Mais conteúdos dessa disciplina