A010E02

Prévia do material em texto

04/06/2020 EPS
simulado.estacio.br/alunos/ 1/4
 
 
 
 TEORIA DA COMPUTAÇÃO
10a aula
 Lupa 
PPT MP3
 
Exercício: CCT0832_EX_A10_201908040459_V2 19/05/2020
Aluno(a): JOSEILDON DA SILVA DANTAS 2020.1 EAD
Disciplina: CCT0832 - TEORIA DA COMPUTAÇÃO 201908040459
 
 1a Questão
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 é:
 O(log2N), em caso de busca binária.
O(1), em caso de busca sequencial.
O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
 O(N), em caso de busca sequencial.
O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
Respondido em 19/05/2020 08:54:00
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,
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
 
 2a Questão
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','10','','','');
javascript:abre_frame('3','10','','','');
04/06/2020 EPS
simulado.estacio.br/alunos/ 2/4
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.
 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 verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições falsas.
 
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, e a II é uma proposição verdadeira.
Respondido em 19/05/2020 08:54:04
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
 
 3a Questão
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
 
 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.
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo polinomial.
 
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 solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de ordenação.
 
 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.
 
Respondido em 19/05/2020 08:54:07
Explicação:
04/06/2020 EPS
simulado.estacio.br/alunos/ 3/4
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.
 
 4a Questã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 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.
 
 
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 
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 falsas.
 
 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, e a II é uma proposição verdadeira.
 
Respondido em 19/05/2020 08:54:10
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. 
 
 5a Questão
O problema P versus NP é um problema ainda 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
 II e IV.
 
04/06/2020 EPS
simulado.estacio.br/alunos/ 4/4
 
 I e III.
.
 I.
 IV.
 II e III.
Respondido em 19/05/2020 08:54:15
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
 
 6a Questão
Qual das complexidades abaixo é a menor?
 O (2n)
O (n2)
 O (n)
O(log n)
O (n3)
Respondido em 19/05/2020 08:54:18
Explicação:
A menor complexidade é a linear
javascript:abre_colabore('38403','194141314','3876738308');