Teoria da Computação - TESTE 10

Prévia do material em texto

04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 1/4
Teste de
Conhecimento
 avalie sua aprendizagem
Qual das complexidades abaixo é a menor?
A área de complexidade de algoritmos abrange a medição da eficiência de um algoritmo frente
à quantidade de operações realizadas até que ele encontre seu resultado final.
A respeito desse contexto, suponha que um arquivo texto contenha o nome de N cidades de determinado estado, que cada
nome de cidade esteja separado do seguinte por um caractere especial de fim de linha e classificado em ordem alfabética
crescente. Considere um programa que realize a leitura linha a linha desse arquivo, à procura de nome de cidade.
Com base nessa descrição, verifica-se que a complexidade desse programa é:
TEORIA DA COMPUTAÇÃO 
Lupa Calc.
 
 
CCT0832_A10_202008191076_V1 
Aluno: YURI CID DA SILVA LIMA Matr.: 202008191076
Disc.: TEORIA DA COMPUTAÇÃO 2021.1 EAD (G) / EX
Prezado (a) Aluno(a),
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
O (n3)
O (n2)
O(log n)
O (2n)
O (n)
Explicação:
A menor complexidade é a linear
 
 
2.
O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(1), em caso de busca sequencial.
O(N), em caso de busca sequencial.
O(log2N), em caso de busca binária.
Explicação:
A análise de complexidade de algoritmos é realizada através da análise assintótica, que utiliza a notação O. Existe um
arquivo em formato texto e ficamos sabendo que: (a) o tamanho da entrada é definido pelo número de cidades N, (b) os
nomes estão em ordem alfabética e (c) cada nome de cidade está em uma linha. O programa que deve ser analisado procura
o nome de uma cidade no arquivo, realizando a leitura linha a linha.
A alternativa A assume que a busca sequencial pode ser realizada em tempo constante (0(1)), ou seja, encontrar o elemento
da primeira posição do arquivo tem o mesmo tempo de execução que encontrar o elemento da segunda posição ou mesmo a
última (posição N). Como o arquivo é lido linha a linha, claramente para encontrar o primeiro elemento será necessário ler
apenas a primeira linha;
para o segundo elemento, as duas primeiras linhas; e assim sucessivamente até necessitar realizar a leitura das N linhas do
arquivo para o último elemento. Desta forma temos um crescimento linear no número de elementos e não constante,
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 2/4
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 que 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.
 
 
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio de grau n, da forma: P(x) =
an xn+an-1 + xn-1+ ... +a1x + a0, onde os coeficientes são números de ponto flutuante armazenados no vetor a[0..n], e o
valor de n é maior que zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente an que é diferente de
zero.
Algoritmo 1:
soma = a[0]
Repita para i = 1 até n
Se a[i] ≠ 0.0 então
potencia = x
Repita para j = 2 até i
potencia = potência * x
Fim repita
soma = soma + a[i] * potencia
 Fim se
Fim repita
Imprima (soma)
Algoritmo 2:
soma = a[n]
Repita para i = n-1 até 0 passo -1
soma = soma * x + a[i]
Fim repita
Imprima (soma)
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.
I. Os algoritmos possuem a mesma complexidade assintótica.
PORQUE
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).
A respeito dessas asserções, assinale a opção correta.
correspondendo à alternativa B, que é a correta para a questão.
Para a análise da alternativa C, assumimos que não é possível fazer acesso aleatório ao arquivo, pois as linhas podem ter
tamanho variável e o deslocamento para a linha de posição (N/2) teria de ser realizado linha a linha (sequencial) até
encontrar N/2 marcadores de final de linha (e desta forma não será possível executar o algoritmo em tempo logarítmico).
Podemos projetar, ainda, um algoritmo que calcula o ponto médio do arquivo a partir do seu tamanho em número de bytes e
que ¿ajusta¿ para o marcador de final de linha mais próximo. Este algoritmo poderia executar em tempo logarítmico se o
sistema permitisse acesso aleatório por caracteres, o que não é possível, pois o enunciado define que a leitura é realizada
linha a linha; logo a alternativa é falsa.
As duas últimas alternativas supõem a transferência dos dados para uma árvore binária, sem especificar qual o seu tipo. Em
uma árvore binária de pesquisa balanceada, o tempo de busca é O(log2N) e, em uma implementação simples de árvore
binária, o tempo de busca é O(N), que fazem com que essas alternativas pareçam plausíveis. O tempo de construção da
árvore balanceada é O(N*log2N), com N operações de leitura ao arquivo e, para cada elemento, no mínimo log2N operações
para realizar a inserção. Caso a árvore não seja balanceada, o custo de inserção de cada elemento é O(N) e o tempo de
construção O(N^2). Logo as duas últimas alternativas são falsas, pois o tempo total do algoritmo será a soma do tempo de
construção mais o tempo de busca
 
 
3.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 
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.
 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
 
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
 
Explicação:
Uma redução polinomial de um problema NP-completo para um problema pertencente à classe P implica que P=NP, pois se
qualquer problema NPcompleto pode ser resolvido em tempo polinomial, então P=NP, um problema aberto e fundamental na
teoria da computação. Logo, a asserção I está correta.
Por outro lado, quando um problema pertence à classe NP-Completo, o mesmo pode ser reduzido, em tempo polinomial, a
um outro problema da classe NP-Completo. Por isso, ao solucionar um problema em tempo polinomial, todos podem ser
solucionados da mesma forma. 
 
 
4.
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 3/4
Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e químicos
para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na mesma caldeira. Além do custo
próprio de cada etapa do tratamento, existe o custo de se passar de uma etapa para a outra, uma vez que, dependendo da
sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para evitar a reação entre os produtos
químicos utilizados. Assuma que o processo de fabricação
inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de tratamentos que
possibilite fabricar o produto com o menor custo total. Nesta situação, conclui-se que
 
O problema P versus NP é um problemaainda não resolvido e um dos mais estudados em Computação. Em inhas gerais,
deseja-se saber se todo problema cuja solução pode ser eficientemente verificada por um computador, também pode ser
eficientemente obtida por um computador. Por ¿eficientemente¿ ou ¿eficiente¿ significa ¿em tempo polinomial¿.
A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de classe P. Os
algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no tamanho das suas
entradas.
Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo eficiente para
resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la eficientemente, então o problema
é dito estar em NP. Dessa forma, a classe de problemas para os quais suas soluções podem ser eficientemente verificadas é
chamada de classe NP.
Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na classe NP pode
ser eficientemente transformado nesse problema. Essa transformação eficiente envolve as entradas e saídas dos
problemas.
Considerando as noções de complexidade computacional apresentadas acima, analise as afirmações que se seguem.
I. Existem problemas na classe P que não estão na classe NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P,
então A está na classe P.
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
É correto apenas o que se afirma em
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
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.
 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Explicação:
Observa-se que o algoritmo 1 contêm dois laços, um externo e um interno, e o algoritmo 1 apresenta 1 laço. O laço externo
do algoritmo 1 e o laço do algoritmo 2 tem a mesma complexidade, mas a existência de 2 laços no algoritmo 1 invalida a
asserção I. 
O algoritmo 1 não necessariamente executa o laço interno, sendo que, no melhor caso, não executa o laço interno vez
alguma. Portanto, a asserção II está correta, e a alternativa D indica esta situação. Pode-se verificar que a questão não exige
que se verifique detalhadamente se os algoritmos realmente calculam o valor do polinômio, apenas que se analise a
complexidade dos algoritmos,o que se reduz a analisar o possível número de iterações dos mes
 
 
5.
A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de ordenação.
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo polinomial.
 
 Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de tempo não-
polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.
 
O problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo, requerendo tempo
de ordem polinomial para ser solucionado.
 
A utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o estado inicial e o final
soluciona o problema em tempo polinomial.
 
Explicação:
Para modelar este problema utilizando grafos se usa um grafo completo com n+1 vértices representando cada uma das
etapas e a etapa inicial caldeira limpa. 
As arestas contêm pesos que representam o custo de se passar de uma etapa para a outra. Deseja se sair do vértice que
representa a caldeira limpa passar por todos os vértices uma única vez e retornar ao vértice caldeira limpa de forma que o
custo seja mínimo. O problema não pode ser resolvido através de uma arvore geradora mínima, pois temos que encontrar um
ciclo (exclui C). Não podemos aplicar Dijkstra, pois
temos que garantir que todos os vértices sejam visitados (exclui D). O problema de coloração determina conjuntos de tarefas
e não uma ordem de tarefas (exclui B). Não é suficiente fazer uma ordenação dos valores pois isso não garante que os
vértices serão todos visitados uma única vez de forma mínima. Se colocarmos todas as etapas com o mesmo custo como
garantir que será encontrado um ciclo que visite todas os vértices.
O problema em questão corresponde ao problema do Caixeiro Viajante ou Ciclo Hamiltoniano, que é NP-Completo.
 
 
6.
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 4/4
 II e IV.
 
 
 II e III.
 IV.
 I.
 I e III.
.
Explicação:
I. Existem problemas na classe P que não estão na classe NP.
Esta asserção é falsa. Qualquer algoritmo de tempo polinomial A que decide uma linguagem L ∈ P pode ser facilmente
convertido em um algoritmo de verificação em tempo polinomial A' que apenas ignora o segundo argumento (certificado) e
simula A. Portanto, temos que P ⊆ NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na classe P.
Esta asserção é verdadeira. Apenas interprete problema como decisão de uma linguagem. Logo, a afirmação de que a
linguagem pode ser transformada eficientemente na linguagem B é equivalente a dizer que A é redutível em tempo
polinomial para B. 
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
Esta é uma asserção condicional. Não se sabe até hoje se o antecedente é verdadeiro ou falso.
(embora a probabilidade de que seja falsa é grande). Se ela for falsa, então a implicação é trivialmente verdadeira. Se ela for
verdadeira, então por definição, qualquer problema em P e, portanto em NP pode ser solucionado polinomialmente, isto é, de
forma eficiente. Desta forma, como qualquer problema NP-completo está em NP, segue que ele, por estar também em P, teria
também uma solução eficiente.
Logo, a asserção é verdadeira.
IV. Se P ≠ NP, então existem problemas na classe P que são NP-completos.
Esta é também uma asserção condicional. Provamos que ela é falsa, mostrando que ao assumirmos o antecedente e o
consequente, derivamos uma contradição. Da hipótese de que P ≠ NP e levando em conta que P ⊆ NP (ver alternativa I),
segue que P ⊂ NP. Desta forma, seja LP um problema em P que seja NP-completo. Pela definição 8 todo problema em NP
pode ser reduzido de forma eficiente a LP 
Daí segue, pela alternativa II, que todo problema em NP estaria em P, isto é, que P = NP. Mas isto é uma
contradição com a hipótese de que P ≠ NP. Portanto, esta afirmação é falsa.
Da discussão acima segue que apenas as afirmativas II e III são verdadeiras
 
 Não Respondida Não Gravada Gravada
 
 
Exercício inciado em 04/05/2021 12:52:35. 
 
 
 
 
javascript:abre_colabore('34697','224402592','4540055677');