Salve - Aula 10 - Teoria da Computação - Teste de Conhecimento

Prévia do material em texto

TEORIA DA COMPUTAÇÃO
10a aula
 Lupa 
PPT MP3
 
 
 1a 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.
 
 
 IV.
 I e III.
.
 II e III.
 I.
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
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','10','','','');
javascript:abre_frame('3','10','','','');
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
 
 2a Questão
Qual das complexidades abaixo é a menor?
 O (n)
O(log n)
O (n2)
O (2n)
O (n3)
Explicação:
A menor complexidade é a linear
 
 3a 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.
 
 
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 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 verdadeiras, mas a II não é 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. 
 
 4a 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
 
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.
 
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.
 
 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.
 
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 vezde 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.
 
 5a 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(N), em caso de busca sequencial.
O(log2N), em caso de busca binária.
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 transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(1), em caso de busca sequencial.
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
 
 6a Questão
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.
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 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.
 
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
javascript:abre_colabore('38403','194090269','3875701032');