Baixe o app para aproveitar ainda mais
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 tratase 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 NPcompleto 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 é NPcompleto. Podese afirmar que: Resposta Selecionada: b. São verdadeiras apenas as afirmações II e III. Pergunta 2 “O estudo da complexidade computacional destinase 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.) “Considerese, por exemplo, o problema de verificar se um grafo tem um ciclo que contém todos os nós do grafo. Podese definir um processo de codificação para representar qualquer grafo como uma cadeia de símbolos. Cadeias que representam grafos tornamse 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é n1 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 empregandose 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, desejase 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, empregandose 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. Tratase 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 NPCompleto: Resposta Selecionada: e. Problema do ciclo hamiltoniano. Pergunta 9 Em uma determinada edificação, em que o esquema de segurança é crucial, desejase cobrir todas as áreas de circulação e ao mesmo tempo minimizar o número de pontos de monitoração. Sabese 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) = 26 g(b) = 43 g(c) = 2 – 3 g(d) = 14 g(e) = 12 g(f) = 56 g(g) = 5 8 g(h)=87 g(i)= 67 g(j) = 73 g(k) = 84 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çafeira, 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
Compartilhar