Baixe o app para aproveitar ainda mais
Prévia do material em texto
Questão 1 Incorreto Atingiu 0,00 de 1,00 Marcar questão Texto da questão Uma equipe de desenvolvimento utiliza aplicações computacionais para o desenvolvimento e a análise de grafos. O seu último desenvolvimento foi feito em uma aplicação com o algoritmo de Kruskal. Para a validação dos resultados obtidos, utilizou-se o grafo apresentado na seguinte figura: Fonte: Elaborada pelo autor. Nesse sentido, assinale a alternativa que apresenta o grafo com a árvore mínima geradora correta quando for aplicado o algoritmo de Kruskal. a. O grafo correto possui arestas entre os vértices de A para B, de B para F, de F para C, de C para D, de D para E e, finalmente, de E para A. Sua resposta está incorreta. A alternativa está incorreta. O simples fato da eliminação de arestas internas de um grafo não elimina o circuito formado. Embora o grafo não forme um ciclo, mas a aresta de menor custo entre B para F, com custo 1 foi eliminada, o grafo está incorreto, porque foi eliminado o menor custo. Dessa forma, o grafo não apresenta circuito, porém foram utilizados os vértices de maior custo. Assim, o grafo está incorreto, uma vez que fecha um ciclo com o trajeto A - B - C - D - A. b. O grafo correto possui arestas entre os vértice de E para D, de D para A, de A para B, de D para C e, finalmente, de C para F. c. O grafo correto possui arestas entre os vértice de A para D, de E para A, de A para B, de B para C e, finalmente, de B para F. d. O grafo correto possui arestas entre os vértice de E para A, de A para B, de A para D, de B para C, de C para D e, finalmente, de B para F. e. O grafo correto possui arestas entre os vértice de E para D, de D para A, de A para B, de B para C e, finalmente, de C para F. Feedback A resposta correta é: O grafo correto possui arestas entre os vértice de A para D, de E para A, de A para B, de B para C e, finalmente, de B para F. Questão 2 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão Os algoritmos são rotinas organizadas de algumas execuções que obedecem a alguns padrões da lógica para a resolução de alguns problemas. Esses algoritmos podem possuir implementações computacionais quando necessário ou apenas organizar os processos de determinadas atividades. A respeito do algoritmo de Kruskal, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. O primeiro passo do algoritmo de Kruskal visa selecionar a aresta externa de menor custo. II. O segundo passo do algoritmo de Kruskal visa determinar a aresta selecionada com o custo menor. III. O terceiro passo do algoritmo de Kruskal visa considerar a árvore mínima geradora como A. IV. O quarto passo do algoritmo de Kruskal visa acrescentar α em A se for formado um ciclo. Assinale a alternativa que apresenta a sequência correta. a. V, V, F, F. b. F, F, V, V. c. V, F, F, F. Resposta correta. A alternativa está correta, pois a afirmativa I é verdadeira, já que, na segunda etapa, ocorre a seleção das arestas de menor custo, considerando que já encontrou, anteriormente, o vértice inicial e atribuiu o valor zero. Assim, na etapa posterior, o algoritmo visa encontrar o vértice não processado que possui o valor infinito. d. F, F, F, F. e. F, V, F, V. Feedback A resposta correta é: V, F, F, F. Questão 3 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão Um grupo de arqueólogos encontrou um mapa no qual é possível indicar uma grande construção subterrânea. Porém, após diversas análises, foi cogitada a possibilidade de desvendar o trajeto, caso seja aplicado o algoritmo de Kruskal. Esse mapa é demonstrado na seguinte figura: Fonte: Elaborada pelo autor. A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. I. Não é possível aplicar o algoritmo de Kruskal no grafo. Pois: II. A quantidade de vértices no grafo é par, por isso, sempre será fechado um ciclo. A seguir, assinale a alternativa correta. a. A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. b. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. c. As asserções I e II são proposições falsas. Resposta correta. A alternativa está correta, poisa asserção I é uma proposição falsa, já que é possível aplicar o algoritmo de Kruskal no grafo. A asserção II também é uma proposição falsa, pois o fato de o grafo ter quantidade par ou ímpar não impede de se utilizar o algoritmo de Kruskal para se ter uma árvore geradora mínima. d. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. e. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. Feedback A resposta correta é: As asserções I e II são proposições falsas. Questão 4 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão Uma das etapas encontradas no algoritmo de Bellman-Ford está no processo de verificação de ciclos negativos, importante para se garantir que os resultados gerados sejam condizentes com as análises proporcionadas pelos algoritmos implementáveis na teoria dos grafos. A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. I. O primeiro processo do algoritmo de Bellman-Ford faz a padronização dos valores de vértices não relacionados. Pois: II. O processo que precede a verificação é o relaxamento, o qual é responsável por buscar o menor caminho de menor custo entre os vértices. A seguir, assinale a alternativa correta. a. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. Resposta correta. A alternativa está correta, poisa asserção I é uma proposição verdadeira, já que a primeira etapa dos processos do algoritmo visa à padronização dos vértices não relacionados. A asserção II também é uma proposição verdadeira e não justifica a I, pois se expõe que o processo de relaxamento busca o menor custo e isso está correto, porém, em cada asserção, é explicado o funcionamento, mas ambas não se justificam. b. A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. c. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. d. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. e. As asserções I e II são proposições falsas. Feedback A resposta correta é: As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. Questão 5 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão O mapeamento dos custos de deslocamento é uma variável de extrema importância, principalmente quando estamos falando a respeito do planejamento da otimização de rotas. O grafo representado na seguinte figura demonstra o custo de deslocamento entre algumas cidades: Fonte: Elaborada pelo autor. Com base no algoritmo de Floyd-Warshall, os valores foram expressos na matriz evidenciada no seguinte quadro: A B C D A 0 4 2 6 B ∞ 0 3 4 C ∞ ∞ 0 ∞ D ∞ ∞ 5 0 Fonte: Elaborado pelo autor. A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. I. A matriz utilizou seis símbolos de ∞. Pois: II. São utilizados para expressar que não existe uma aresta que liga um vértice ao outro naquela direção. A seguir, assinale a alternativa correta. a. As asserções I e II são proposições falsas. b. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. c. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. d. A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. e. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. Respostacorreta. A alternativa está correta, poisa asserção I é uma proposição verdadeira, uma vez que o grafo não possui ligação com o direcionamento entre os vértices: B para A, C para A, C para B, C para D, D para A e D para B, totalizando seis. A asserção II também é uma proposição verdadeira e justifica a I, pois expressa que não existe um relacionamento naquela direção. Feedback A resposta correta é: As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. Questão 6 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão O algoritmo de Dijkstra é semelhante ao algoritmo de Bellman-Ford, pois, entre outras coisas, pode calcular o trajeto mínimo entre dois vértices de determinado grafo valorado. Porém, em Dijkstra, possui diferenças em relação ao algoritmo de Bellman-Ford. Nesse sentido, assinale a alternativa que apresenta corretamente outra diferença nos algoritmos de Dijkstra e de Bellman-Ford. a. O algoritmo de Dijkstra não utiliza arestas direcionadas. b. O algoritmo de Dijkstra não utiliza vértices impares. c. O algoritmo de Dijkstra não utiliza uma sequência para a execução de sua rotina. d. O algoritmo de Dijkstra não efetua cálculos com valores negativos. Resposta correta. A alternativa está correta, pois o algoritmo de Dijkstra não consegue efetuar uma tratativa quando, no relacionamento entre os vértices por meio das arestas, são encontrados valores negativos. Para esse tipo de grafo com valores negativos, o indicado é utilizar o algoritmo de Bellman-Ford. e. O algoritmo de Dijkstra não utiliza vértices pares. Feedback A resposta correta é: O algoritmo de Dijkstra não efetua cálculos com valores negativos. Questão 7 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão O mapeamento dos custos de deslocamento entre algumas cidades foi representado na seguinte figura: Fonte: Elaborada pelo autor. Considerando um trajeto de A para E e com base no algoritmo de Dijkstra, os valores foram expressos na matriz evidenciada no seguinte quadro: Passo 1 Passo 2 Passo 3 Passo 4 Passo 5 A (0, A) (0, A) *** *** *** B (1, A) (1, A) *** *** *** C (4, A) (4, A) D ∞ (5, B) E ∞ (3, B) Fonte: Elaborado pelo autor. A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. I. Foram fixados os valores na linha A (0, A) e na linha B (1, A). Pois: II. Não haverá custo de A para A pela ausência de laço, não sendo encontrado um custo menor de B para C. A seguir, assinale a alternativa correta. a. A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. Resposta correta. A alternativa está correta, poisa asserção I é uma proposição verdadeira, porque foram fixados os valores encontrados nos trajetos de A para A como 0 (zero), uma vez que não existe laço no vértice A. Já o custo entre os vértices A para B foi fixado em 1, pois, se for feito qualquer outro trajeto entre os dois pontos, o custo será maior. b. As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. c. As asserções I e II são proposições falsas. d. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. e. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. Feedback A resposta correta é: A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. Questão 8 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão Uma viagem em família requer planejamento e estratégias, a fim de se ter um deslocamento com segurança, com o menor custo e, se possível, evitar longos congestionamentos que acabam por aumentar o tempo gasto entre dois pontos, os quais, muitas vezes, não são tão distantes. Todas essas análises estão diretamente ligadas à teoria dos grafos e, intuitivamente, busca-se o caminho com menor custo entre dois pontos. O algoritmo de Floyd é uma das técnicas responsáveis por encontrar tais informações. A respeito do algoritmo de Floyd-Warshall, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. Se o vértice inicial do grafo é dado por “i” e o vértice final é dado por “n”, então os vértices intermediários são compreendidos entre “i” e “n -1”. II. Os vértices intermediários são um conjunto de um grafo G. III. Na matriz utilizada pelo algoritmo de Floyd, apresenta-se i = j, então o valor será 0 (zero). IV. Se i for diferente de j e apresentar a aresta, então o menor custo deverá substituir o valor na matriz, no algoritmo de Floyd. Assinale a alternativa que apresenta a sequência correta. a. F, F, V, V. Resposta correta. A alternativa está correta. A afirmativa III é verdadeira, pois, se não fosse atribuído o valor 0 (zero), seria possível ter laços no grafo, não sendo o objetivo de análise do algoritmo de Floyd. A afirmativa IV também é verdadeira, pois, basicamente, o algoritmo de Floyd busca trajetos entre os vértices de menor custo e, quando encontrado, esse valor é substituído pelo atual valor da matriz. b. V, V, V, V. c. F, V, F, V. d. V, V, F, F. e. F, F, F, F. Feedback A resposta correta é: F, F, V, V. Questão 9 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão Os algoritmos são ferramentas da lógica computacional que permitem organizar rotinas, a fim de se planejar o sequenciamento de ações sobre determinado conjunto de valores. Quanto à sua aplicação na teoria dos grafos, é essencial saber identificar as características do grafo, para, após isso, ser utilizada a análise algorítmica. Um exemplo de grafo, passível de análise, pode ser observado na seguinte figura: Fonte: Elaborada pelo autor. A respeito do algoritmo de Dijkstra, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. São necessários 8 passos para se obter um trajeto otimizado de S para qualquer outro vértice. II. Não é possível utilizar o algoritmo de Dijkstra na análise do grafo, pois ele está desenvolvido em árvore. III. É preciso fazer todos os trajetos nas subárvores e seus respectivos custos. Somente após isso, deve-se passar para as subárvores adjacentes. IV. Não é possível utilizar o algoritmo de Dijkstra na análise do grafo, pois existem custos negativos entre os vértices. Assinale a alternativa que apresenta a sequência correta. a. V, V, V, V. b. F, F, V, V. c. V, V, F, F. d. F, V, F, V. Resposta correta. A alternativa está correta, pois a afirmativa II é verdadeira, já que o algoritmo de Dijkstra faz análise em grafos com circuito, mas não em grafos em árvore. O algoritmo de Dijkstra não efetua cálculos quando são utilizados pesos negativos nas arestas entre os vértices do grafo, o que torna a afirmativa IV verdadeira. e. F, F, F, F. Feedback A resposta correta é: F, V, F, V. Questão 10 Correto Atingiu 1,00 de 1,00 Marcar questão Texto da questão Leia o excerto a seguir. “[...] um exemplo clássico do uso de algoritmos é a tabela que se consulta atlas e guias rodoviários, que dão as distâncias de várias cidades. Atualmente, fazemos esse tipo de consulta, porém com a utilização de programas computacionais que efetuam os cálculos.” CORMEN, J. Desmistificando Algoritmos. Rio de Janeiro: Elsevier, 2017. p. 93. Considerando o exposto, sobre o algoritmo de Floyd-Warshall, analise as afirmativas a seguir. I. O algoritmo de Floyd utiliza a recursividade para determinar o menor custo, porém não poderia ser utilizado para a consulta de guias rodoviários. II. O algoritmo de Floyd resolve os problemas menores e, gradativamente, vai resolvendo problemas mais complexos. III. O algoritmo de Floyd utiliza valores negativos nas arestas entre os vértices. IV. O algoritmode Floyd busca fazer a eliminação de vértices para se obter uma estrutura mínima. Está correto o que se afirma em: a. II, apenas. Resposta correta. A alternativa está correta. A afirmativa I está incorreta, pois o algoritmo de Floyd não utiliza recursividade, ainda que poderia ser utilizado para a consulta de guias rodoviários. A afirmativa II está correta, visto que o algoritmo de Floyd é modular, ou seja, resolve os problemas menores inicialmente e vai aumentando aos poucos. A afirmativa III está incorreta, pois o algoritmo de Floyd não utiliza valores negativos para cálculo. A afirmativa IV está incorreta, porque não minimiza os grafos, tratando-se de outras técnicas. b. II e III, apenas. c. II, III e IV, apenas. d. I, II e IV, apenas. e. III, apenas. Feedback A resposta correta é: II, apenas.
Compartilhar