ASPECTOS TEÓRICOS DA COMPUTAÇÃO_UNIP 2

Prévia do material em texto

08/03/2017 Revisar envio do teste: Questionário Unidade II (2017/1) &...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_49360351_1&course_id=_128741_1&content_id=_1564104_1&return_content=… 1/6
   Unidade II  Revisar envio do teste: Questionário Unidade II (2017/1)H
Revisar envio do teste: Questionário Unidade II (2017/1) 
Usuário VINICIUS LOPES DOMIN
Curso ASPEC TEORICOS DA COMPUTACAO
Teste Questionário Unidade II (2017/1)
Iniciado 07/03/17 21:06
Enviado 07/03/17 21:06
Status Completada
Resultado
da
tentativa
4 em 5 pontos  
Tempo
decorrido
24 minutos
Instruções ATENÇÃO: esta avaliação segue as seguintes configurações:
­ possui número de tentativas limitadas a 3 (três) 
­ valida a sua frequência e nota na disciplina em questão;
­ não apresenta as justificativas corretas, pois trata­se de um avaliativo;
­ não soma pontos de “tentativa em andamento” (tentativas iniciadas e não
concluídas/enviadas) – porém, uma vez acessada, é considerada como uma de suas 3
(três ) tentativas permitidas e precisa ser editada e enviada para ser devidamente
considerada;
­ possui sua pontuação submetida a um cálculo final conforme exposto abaixo – o
cálculo final será executado e apresentado em sua “Secretaria Virtual”:
1° envio – será considerada a nota referente aos acertos dos exercícios
enviados;
2° envio – será considerada a média aritmética das notas dos 1º e 2º
envios;
3° envio – será considerada a média aritmética das notas dos 1º, 2º e 3º
envios;
­ possui um período de envio (previsto em Calendário Acadêmico) e não será possível
acesso para validar sua nota e frequência após esse prazo.
­ a NÃO realização prevê nota 0 (zero).
Resultados
exibidos
Respostas enviadas, Perguntas respondidas incorretamente
Pergunta 1
Considere as seguintes afirmações e assinale a alternativa correta.
I  –  Se  qualquer  problema NP  –  completo  pode  ser  resolvido  em  tempo  polinomial,
então P = NP.
II – Se qualquer problema em NP não pode ser resolvido em tempo polinomial, então
nenhum problema NP­completo pode ser resolvido em tempo polinomial.
III – Um dos resultados mais significativos da Ciência da Computação diz respeito à
descoberta de um algoritmo de tempo polinomial, para o problema da Cobertura dos
UNIP EAD
0,5 em 0,5 pontos
VINICIUS DOMIN 2
08/03/2017 Revisar envio do teste: Questionário Unidade II (2017/1) &...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_49360351_1&course_id=_128741_1&content_id=_1564104_1&return_content=… 2/6
Vértices, que é NP­completo.
Pode­se afirmar que:
Resposta Selecionada:
b. 
São verdadeiras apenas as afirmações II e III.
Pergunta 2
“O  estudo  da  complexidade  computacional  destina­se  a  estabelecer  uma  classificação
quantitativa das linguagens decidíveis, de acordo com a quantidade de esforço que a máquina
de Turing deve dispender para processar suas cadeias de entrada” (NETO J, J.)
“Considere­se,  por  exemplo,  o  problema de verificar  se  um grafo  tem um ciclo que
contém  todos  os  nós  do  grafo.  Pode­se  definir  um  processo  de  codificação  para
representar  qualquer  grafo  como  uma  cadeia  de  símbolos. Cadeias  que  representam
grafos  tornam­se  cadeias  de  entrada  apropriadas  de  se  deseja  decidir,  dada  uma  tal
cadeia,  se  ela pertence  ao  conjunto de  cadeias  cujos grafos  associados  têm circuitos
hamiltonianos.” 
A classe P contém todas as Linguagens decidíveis por uma Máquina de Turing 
em um tempo limitado por um polinômio de grau d.
NP é a coleção de todos os conjuntos reconhecíveis por máquinas de Turing não
determinísticas em tempo polinomial.
 
Considere as seguintes afirmações:
I –P ⊆ NP, mas não se sabe se P ⊂ NP.
II – Apesar da similaridade entre os enunciados dos problemas, o ciclo euleriano
pertence à classe P, enquanto o problema do ciclo hamiltoniano pertence à classe NP.
III­ Existe uma máquina de Turing não determinística que decide se um determinado
grafo apresenta um ciclo hamiltoniano em tempo polinomial.
A alternativa correta é:
Resposta Selecionada:
c. 
Apenas I
Pergunta 3
Assinale  a  alternativa  que  diz  respeito  a  um  problema  que  apresenta  desempenho
polinomial:
Resposta Selecionada: e. Detecção de um caminho euleriano em um grafo.
Pergunta 4
0 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
08/03/2017 Revisar envio do teste: Questionário Unidade II (2017/1) &...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_49360351_1&course_id=_128741_1&content_id=_1564104_1&return_content=… 3/6
O  problema  da  acessibilidade  pode  ser  enunciado  como  se  segue:  “Dado  um  grafo
orientado G ⊆ V×V, em que V é o conjunto de nós e dois nós quaisquer vi e vj∈ V,
existe um caminho de vi para vj?” A solução desse problema é dada pelo algoritmo de
Warshall, conforme descrito no pseudocódigo abaixo:
 
Warshall (matriz booleana n ×n M)
//Incialmente, M = matriz de ajacência de um grafo orientado G sem arcos paralelos)
            para k = 0 até n­1 faça
                        para i= 1 até n faça
                                   para j= 1 até n faça
                                               M[i,j] = M[i,j] ∨ M[i, k+1] ∧ M[k+1, j]
                                   Fim do para
                        Fim do para
            Fim do para
Fim de Warshall
 
 
Esse problema apresenta complexidade computacional:
Resposta Selecionada:
b. 
Polinomial O(n3)
Pergunta 5
É possível classificar os problemas com base na computabilidade de suas soluções, utilizando­
se a Máquina de Turing como referencial. Considere as demais afirmações a respeito da
Máquina de Turing: 
I  –  A  complexidade  da  resolução  do  problema  da  Parada  não  pode  ser  analisado
empregando­se  a  Máquina  de  Turing,  por  esta  ser  determinística.  O  Problema  da
Parada poderá ser analisado logo se formalize o conceito Máquina de Turing com duas
ou mais fitas paralelas.
II – Uma ordenação lexicográfica fundamentada em um alfabeto de 16
símbolos apresenta uma palavra (símbolos do alfabeto concatenados) para a
qual não existe uma Máquina de Turing correspondente. Tal enunciado é de
complexidade NP.
III  ­  Uma  ordenação  lexicográfica  fundamentada  em  um  alfabeto  de  16  símbolos
apresenta uma palavra (símbolos do alfabeto concatenados) para a qual não existe uma
Máquina de Turing correspondente. Tal enunciado é de complexidade P.
IV – Uma Máquina de Turing que verifique se em um grafo existe um caminho que
passe por todos os vértices uma única vez, apresenta desempenho NP.
É correto afirmar:
0,5 em 0,5 pontos
08/03/2017 Revisar envio do teste: Questionário Unidade II (2017/1) &...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_49360351_1&course_id=_128741_1&content_id=_1564104_1&return_content=… 4/6
Resposta Selecionada:
d. 
Apenas II e IV
Pergunta 6
Considere o seguinte enunciado: Dado  um conjunto S de números inteiros, determine
se há algum subconjunto não vazio de S, cujos elementos são tais que quando somados
apresentam total igual a zero.
Para  esse  problema,  é  fácil  verificar  se  uma  resposta  é  correta
(um  particular  subconjunto  de  S).  No  entanto,  não  se  conhece  uma  solução
significativamente mais  rápida para  resolver  este problema, de  forma geral,    do que
aquela que  testa  todos os subconjuntos possíveis de S, até encontrar um que cumpra
com a condição. Assim, o enunciado acima diz respeito a um problema:
Resposta Selecionada:
a. 
De desempenho polinomial.
Pergunta 7
Considere os seguintes problemas:
 
I – O problema da mochila pode ser definido como: Dado um conjunto S = {a1, a2, ...,
an}  de  números  inteiros  não  negativos,  todos  representados  em  binário,  háum
subconjunto P de S, tal que a soma de todos os elementos de  P é igual a K?
II  – Dado um conjunto  de  caixas  de  dimensões  distintas,  deseja­se  armazená­las  no
menor número possível de contêineres, todos de mesmo tamanho.
III – O problema da partição pode ser definido como: Dado um conjunto de números
inteiros não negativos,  todos  representados  em binário,  existem duas partições deste
conjunto, tais que as somas dos elementos de cada partição sejam iguais?
IV – Há que se atribuir n  tarefas a duas máquinas. Ambas têm a mesma velocidade.
Não há restrições na ordem de execução das tarefas. Cada tarefa apresenta o seu tempo
de processamento e há um prazo para se finalizar a execução de todas estas operações.
É  possível  verificar  se  estas  tarefas  podem  ser  realizadas  no  prazo  previsto,
empregando­se  a  solução  para  o  problema da  partição. De  fato,  cada máquina  pode
corresponder  a  uma  partição,  desde  que  a  soma  dos  tempos  das  tarefas  atribuídas  a
cada uma das máquinas seja menor ou igual ao prazo de execução das tarefas.
V ­ A tarefa de balancear as  linhas de montagem em qualquer segmento industrial é
uma tarefa crucial. Trata­se de atribuir tarefas ao menor número possível de estações
de trabalho, de forma que nenhuma restrição de precedência entre estas operações seja
violada. Ainda, o tempo despendido para realizar tais operações não deve ultrapassar o
intervalo previamente planejado, visto que existe uma esteira que transporta o objeto
da produção de uma estação de trabalho à outra. 
 
São problemas NP:
0 em 0,5 pontos
0,5 em 0,5 pontos
08/03/2017 Revisar envio do teste: Questionário Unidade II (2017/1) &...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_49360351_1&course_id=_128741_1&content_id=_1564104_1&return_content=… 5/6
Resposta Selecionada:
d. 
I, II, III, IV e V
Pergunta 8
Assinale a alternativa que representa um problema NP­Completo:
Resposta Selecionada: e. Problema do ciclo hamiltoniano.
Pergunta 9
Em uma determinada edificação, em que o esquema de segurança é crucial, deseja­se
cobrir todas as áreas de circulação e ao mesmo tempo minimizar o número de pontos
de  monitoração.  Sabe­se  que  o  número  de  salas  deste  lugar  é  30  e  o  número  de
corredores  é  15.  A  fim  de  se  obter  exatamente  o  menor  número  de  pontos  de
monitoração de  forma a cobrir  todos os corredores, deveriam ser  realizados cálculos
de complexidade:
Resposta Selecionada:
a. 
Fatorial.
Pergunta 10
Considere o grafo G = (V, A, g), em que:
V = {1, 2, 3, 4, 5, 6, 7, 8} são os vértices
A = {a, b, c, d, e}
g(a) = 2­6
g(b) = 4­3
g(c) = 2 – 3
g(d) = 1­4
g(e) = 1­2
g(f) = 5­6
g(g) = 5­ 8
g(h)=8­7
g(i)= 6­7
g(j) = 7­3
g(k) = 8­4
 
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
08/03/2017 Revisar envio do teste: Questionário Unidade II (2017/1) &...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_49360351_1&course_id=_128741_1&content_id=_1564104_1&return_content=… 6/6
Terça­feira, 7 de Março de 2017 21h31min23s BRT
Sejam as seguintes afirmações:
I  ­   O grafo  apresenta  um caminho de Euler,  pois  apresenta  um número  par  de  nós
ímpares.
II – O grafo apresenta um ciclo hamiltoniano, pois apresenta um número par de nós
ímpares.
III  –  Este  grafo  apresenta  8  vértices  e  um  programa  que  verifique  se  existe  um
caminho hamiltoniano deverá efetuar em uma situação de pior caso 8! cálculos.
IV – Este grafo  apresenta 6 nós  ímpares  e,  portanto,  não  apresenta um Caminho de
Euler.
Resposta Selecionada:
c. 
Apenas I e II
← OK