Logo Passei Direto

A maior rede de estudos do Brasil

Grátis
6 pág.
ASPECTOS TEÓRICOS DA COMPUTAÇÃO_UNIP 2

Pré-visualização | Página 1 de 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=… 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á
Página12