Exercício 10

Prévia do material em texto

Disc.: TEORIA DA COMPUTAÇÃO 2022.3 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. 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 falsas.
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.
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.
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
https://simulado.estacio.br/bdq_simulados_exercicio.asp
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
2. 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
IV.
I.
II e III.
I e III.
.
II e IV.
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
https://simulado.estacio.br/bdq_simulados_exercicio.asp
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
3. 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 verdadeiras, e a II é 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 falsas.
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.
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. 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
https://simulado.estacio.br/bdq_simulados_exercicio.asp
https://simulado.estacio.br/bdq_simulados_exercicio.asp
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
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 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.
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.
5. 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(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 transferência dos nomes para uma árvore binária e, então, realizar a busca.
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
https://simulado.estacio.br/bdq_simulados_exercicio.asp
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
6. Qual das complexidades abaixo é a menor?
O (2n)
O (n2)
O (n)
O(log n)
O (n3)
Explicação:
A menor complexidade é a linear
https://simulado.estacio.br/bdq_simulados_exercicio.asp