Teoria dos Grafos

Prévia do material em texto

Avaliação l – TEORIA DE GRAFOS 
1. Considere o texto "aaaaaaaaaaa". Quantas vezes o padrão "aaa" é encontrado pela busca com o 
algoritmo de Boyer-Moore? 
 
Quinze vezes. 
 
Dez vezes. 
 
Onze vezes. 
 
Nove vezes. (Alternativa correta) 
 
2. As árvores geradoras vêm sendo amplamente usadas por sua grande utilidade e contribuições em 
projetos que buscam alcançar todos os vértices de determinado grafo por meio de um número de 
arestas menor que o normalmente utilizado no grafo total, sendo uma estratégia gulosa quando 
usada para estipular o custo mínimo e o máximo. Dessa forma, assinale a alternativa que corresponde 
a um contexto de aplicação das árvores geradoras. 
 
Ciclo hamiltoniano de distribuição de arestas. 
 
Transmissão de uma rede óptica passiva (PON). (Alternativa correta) 
 
Ciclo euleriano de distribuição de arestas. 
 
Recursividade baseada nos números de Fibonacci. 
3. O algoritmo de busca tradicional de Boyer-Moore depende de um pequeno número de comparações 
de caracteres e grandes mudanças realizadas no texto durante a busca. O algoritmo de Boyer-Moore: I. 
funciona corretamente apenas com a tabela de símbolos ruins para orientar as mudanças de padrão. II. 
não funciona corretamente apenas com a tabela de símbolos ruins para orientar as mudanças de 
padrão. III. funciona corretamente apenas com a tabela de sufixos bons para orientar as mudanças de 
padrão. IV. não funciona corretamente apenas com a tabela de sufixos bons para orientar as mudanças 
de padrão. Está o que se afirma em: 
 
I e IV, apenas. (Alternativa correta) 
 
II e IV, apenas. 
 
I, II e III, apenas. 
 
II e III, apenas. 
 
4. Algumas características do algoritmo de Kruskal para o problema da árvore geradora mínima 
possibilitam que ele seja aplicado em uma grande variedade de cenários. Dentre as mais destacadas, a 
estratégia de explorar múltiplas árvores em paralelo faz com que o algoritmo apresente uma 
eficiência computacional superior em relação a outros algoritmos para o mesmo problema. 
Nesse contexto, considere a aplicação do algoritmo de Kruskal no grafo a seguir e avalie as afirmativas a 
respeito: 
 
I - A aresta de maior peso que compõe a árvore geradora mínima final tem valor 6. 
II - O número de árvores intermediárias geradas e compostas por mais de 1 vértice é, no máximo, 2. 
III - Para as primeiras i iterações, com i = 1, 2 e 3, as arestas de peso i são inseridas na solução nessa 
ordem. 
IV - O valor do custo total da árvore geradora mínima (soma dos pesos das arestas) é 15. Quais estão 
corretas? 
 
 
I, II e III. 
 
 
II e IV. 
 
 
I e II. 
 
II e III. (Alternativa correta) 
 
 
 
5. Junto da escolha do algoritmo, é importante adequar a forma como a entrada de dados será 
representada. Soluções comuns envolvem o uso de vetores, a lista de adjacência e a matriz de 
adjacência. Dado o grafo, selecione a alternativa que apresenta a matriz de adjacência equivalente: 
 
 
 
 
 
 
 
 
 
 (Alternativa correta) 
 
 
 
 
 
 
 
6. Várias são as estruturas de dados que podem ser empregadas na implementação do algoritmo de 
Kruskal para o problema da árvore geradora mínima de um grafo. Cada estrutura usada, no entanto, 
vai impactar de maneira diferente no desempenho computacional do algoritmo. Uma das estruturas 
de dados mais reconhecidas pela sua eficiência quando usada no algoritmo de Kruskal é a União-
Busca. Ela é composta de duas operações básicas: 
1. Busca: Dada uma lista de conjuntos e um elemento x a ser buscado, ela retorna o conjunto da qual x é 
um elemento. Esse retorno pode ser denotado por Conjunto(x). 
2. União: Dados dois conjuntos disjuntos, ela realiza a união desses dois conjuntos gerando um terceiro 
a partir da remoção dos dois conjuntos originais. Tendo como base o uso da estrutura de dados União-
Busca, assinale a alternativa que preenche corretamente as lacunas do algoritmo de Kruskal a seguir: 
 
 
 
Ordenar as arestas de G em ordem não decrescente de peso Conjunto(u) é diferente de Conjunto(v) 
Adicionar (u, v) a A. (Alternativa correta) 
 
Definir uma variável para armazenar a menor distância corrente Peso de u > Peso de v Adicionar (u, v) a 
A 
 
 
Organizar as arestas de G em ordem crescente de peso Conjunto(u) é igual ao Conjunto(v) Adicionar (u, 
v) a A 
 
 
Inicializar cada árvore construída com valor Ø Conjunto(u) é diferente de Conjunto(v) Remover (u, v) de 
G 
 
7. Embora seja um algoritmo tradicional para o problema da árvore geradora mínima de grafos, o 
algoritmo de Prim tem o seu funcionamento condicionado ao atendimento de certos pré-requisitos. 
Tanto as características do grafo como as estruturas de dados empregadas em sua implementação 
podem afetar o seu desempenho ou, até mesmo, inviabilizar a busca por uma solução ótima. Nesse 
contexto, considere que o grafo a seguir foi passado como parâmetro para o algoritmo de Prim. 
 
 Julgue V (verdadeiro) ou F (falso) as afirmativas a respeito do comportamento do algoritmo: 
( ) A alteração do peso w(e) de cada aresta e por w(e) * w(e) compromete a obtenção da árvore 
geradora mínima. 
( ) A solução obtida pelo algoritmo depende da escolha do vértice inicial usado para iniciar a construção 
da árvore. 
( ) A remoção de 3 arestas de qualquer vértice inviabiliza a obtenção da árvore pelo algoritmo. 
( ) O cuso total da árvore geradora mínima do grafo é inferior à soma dos pesos das arestas do vértice 
de maior grau. Assinale a alternativa que apresenta a sequência correta. 
 
F - V - F - F. 
 
 
V - F - F - V. 
 
 
V - V - V - F. 
 
F - F - F - V. (Alternativa correta) 
 
8. Assim como os tipos de problemas podem ser diferentes entre um caso e outro, também os 
algoritmos e técnicas mais adequados para solucionar o problema variam. Um dos algoritmos mais 
utilizados é o de busca em largura. Assinale a alternativa que descreve um problema que utilizaria 
esse algoritmo. 
 
Roteamento de dados, em que as arestas especificam o tempo de transmissão. 
 
Jogador de xadrez computarizado, em que um movimento pode produzir um custo positivo ou negativo. 
 
Algoritmo de planejamento de tráfego para controlar o trânsito no cruzamento entre rodovias de alto 
fluxo. 
 
Algoritmo para encontrar a sequência de movimentos que resolvam o cubo mágico. 
 (Alternativa correta) 
 
9. Para compreender o conceito de árvores geradoras, é preciso antes entender as definições de grafos 
e árvores, saber diferenciar o conjunto das arestas e vértices, assim como identificar o contexto de 
aplicação dessa estrutura de dados, não confundindo com as aplicações da estratégia usadas 
em caminhos mínimos. Com base nos principais conceitos correlatos às árvores geradoras, analise os 
itens a seguir: 
I. Uma árvore geradora é um subgrafo gerador cíclico, não direcionado e com o menor custo possível. 
II. Uma árvore tem complexidade na ordem de O(N3) e tem ciclo em 
sua estrutura, por exemplo: ciclo euleriano. 
III. Um corte C (S, V-S) é uma partição no grafo G = (V, E) que busca auxiliar na expansão das arestas da 
árvore geradora. 
IV. Toda árvore geradora mínima é uma árvore geradora, assim como toda árvore geradora é uma 
árvore geradora mínima. 
V. Toda árvore é um grafo, porém nem todo grafo pode ser uma árvore, pois este último goza de 
propriedades mais abrangentes. Quais estão corretos? 
 
I, III. 
 
III, V. (Alternativa correta) 
 
I, II. 
 
II, III. 
 
10. Os conceitos que fundamentam a construção de estratégias gulosas são importantes para que 
uma modelagem precisa possa ser empregada durante a proposição de soluções. Essa análise deve 
preceder, inclusive, a etapa de projeto de um algoritmo guloso. Nesse contexto, dado um conjunto ｛ 
x1, x2, …, xn ｝ de pontos na reta dos números reais, analise as afirmativas a seguir e a relação 
proposta entre elas: I. É possível projetar uma estratégia gulosa para encontrar o menor conjunto de 
intervalos fechados de comprimento 1 (um) contendo todos os pontos.PORQUE II. A cada etapa da 
estratégia gulosa, uma escolha local ótima pode ser feita de forma a garantir a obtenção de uma 
solução final ótima. Assinale a alternativa correta. 
 
As afirmações I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
 
As afirmações I e II são proposições verdadeiras e a II é uma justificativa correta da I. 
 (Alternativa correta) 
 
A afirmação I é uma proposição falsa e a II é uma proposição verdadeira. 
 
A afirmação I é uma proposição verdadeira e a II é uma proposição falsa. 
 
 
 
	1. Considere o texto "aaaaaaaaaaa". Quantas vezes o padrão "aaa" é encontrado pela busca com o algoritmo de Boyer-Moore?
	2. As árvores geradoras vêm sendo amplamente usadas por sua grande utilidade e contribuições em projetos que buscam alcançar todos os vértices de determinado grafo por meio de um número de arestas menor que o normalmente utilizado no grafo total, send...
	3. O algoritmo de busca tradicional de Boyer-Moore depende de um pequeno número de comparações de caracteres e grandes mudanças realizadas no texto durante a busca. O algoritmo de Boyer-Moore: I. funciona corretamente apenas com a tabela de símbolos r...
	4. Algumas características do algoritmo de Kruskal para o problema da árvore geradora mínima possibilitam que ele seja aplicado em uma grande variedade de cenários. Dentre as mais destacadas, a estratégia de explorar múltiplas árvores em paralelo faz ...
	Nesse contexto, considere a aplicação do algoritmo de Kruskal no grafo a seguir e avalie as afirmativas a respeito:
	I - A aresta de maior peso que compõe a árvore geradora mínima final tem valor 6.
	II - O número de árvores intermediárias geradas e compostas por mais de 1 vértice é, no máximo, 2.
	III - Para as primeiras i iterações, com i = 1, 2 e 3, as arestas de peso i são inseridas na solução nessa ordem.
	IV - O valor do custo total da árvore geradora mínima (soma dos pesos das arestas) é 15. Quais estão corretas?
	5. Junto da escolha do algoritmo, é importante adequar a forma como a entrada de dados será representada. Soluções comuns envolvem o uso de vetores, a lista de adjacência e a matriz de adjacência. Dado o grafo, selecione a alternativa que apresenta a ...
	6. Várias são as estruturas de dados que podem ser empregadas na implementação do algoritmo de Kruskal para o problema da árvore geradora mínima de um grafo. Cada estrutura usada, no entanto, vai impactar de maneira diferente no desempenho computacion...
	1. Busca: Dada uma lista de conjuntos e um elemento x a ser buscado, ela retorna o conjunto da qual x é um elemento. Esse retorno pode ser denotado por Conjunto(x).
	2. União: Dados dois conjuntos disjuntos, ela realiza a união desses dois conjuntos gerando um terceiro a partir da remoção dos dois conjuntos originais. Tendo como base o uso da estrutura de dados União-Busca, assinale a alternativa que preenche corr...
	7. Embora seja um algoritmo tradicional para o problema da árvore geradora mínima de grafos, o algoritmo de Prim tem o seu funcionamento condicionado ao atendimento de certos pré-requisitos. Tanto as características do grafo como as estruturas de dado...
	Julgue V (verdadeiro) ou F (falso) as afirmativas a respeito do comportamento do algoritmo:
	( ) A alteração do peso w(e) de cada aresta e por w(e) * w(e) compromete a obtenção da árvore geradora mínima.
	( ) A solução obtida pelo algoritmo depende da escolha do vértice inicial usado para iniciar a construção da árvore.
	( ) A remoção de 3 arestas de qualquer vértice inviabiliza a obtenção da árvore pelo algoritmo.
	( ) O cuso total da árvore geradora mínima do grafo é inferior à soma dos pesos das arestas do vértice de maior grau. Assinale a alternativa que apresenta a sequência correta.
	8. Assim como os tipos de problemas podem ser diferentes entre um caso e outro, também os algoritmos e técnicas mais adequados para solucionar o problema variam. Um dos algoritmos mais utilizados é o de busca em largura. Assinale a alternativa que des...
	9. Para compreender o conceito de árvores geradoras, é preciso antes entender as definições de grafos e árvores, saber diferenciar o conjunto das arestas e vértices, assim como identificar o contexto de aplicação dessa estrutura de dados, não confundi...
	I. Uma árvore geradora é um subgrafo gerador cíclico, não direcionado e com o menor custo possível.
	II. Uma árvore tem complexidade na ordem de O(N3) e tem ciclo em sua estrutura, por exemplo: ciclo euleriano.
	III. Um corte C (S, V-S) é uma partição no grafo G = (V, E) que busca auxiliar na expansão das arestas da árvore geradora.
	IV. Toda árvore geradora mínima é uma árvore geradora, assim como toda árvore geradora é uma árvore geradora mínima.
	V. Toda árvore é um grafo, porém nem todo grafo pode ser uma árvore, pois este último goza de propriedades mais abrangentes. Quais estão corretos?
	10. Os conceitos que fundamentam a construção de estratégias gulosas são importantes para que uma modelagem precisa possa ser empregada durante a proposição de soluções. Essa análise deve preceder, inclusive, a etapa de projeto de um algoritmo guloso....
	1. Um típico problema em que algoritmos gulosos são aplicados é conhecido como agendamento para minimizar o tempo médio de finalização. Várias estratégias têm sido propostas para oferecer uma solução em tempo computacionalmente viável. Suponha um conj...
	I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem finalizadas (pi), então a complexidade do algoritmo será O(n log n).
	II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de pi obtém a solução ótima para qualquer conjunto de tarefas.
	III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 = 5, o tempo médio de finalização de S é independente da ordem de execução das tarefas.
	IV. ( ) Uma solução gulosa baseada no tempo de processamento de cada tarefa apresenta uma estrutura local ótima em cada iteração. Agora, assinale a alternativa que apresenta a sequência correta.
	2. O algoritmo de Prim é um dos algoritmos mais tradicionais aplicados ao problema da árvore geradora mínima de um grafo. Diversas estruturas de dados podem ser utilizadas tanto na modelagem do grafo como na representação da fila de prioridades usada ...
	I. O maior tamanho alcançado pela fronteira é de 3 vértices.
	II. O último vértice a ser inserido na solução é o d.
	III. Após a terceira iteração, o vértice e se torna parte da solução.
	IV. A soma dos pesos da árvore final tem valor 18. Quais estão corretas?
	3. Dado um grafo não orientado e conexo G = (V, E), pode-se dizer que uma árvore geradora T é um subgrafo que consegue visitar todos os n vértices de G a partir de n - 1 arestas. Dessa forma, um grafo G pode ter muitas árvores geradoras e, mesmo assi...
	A partir do grafo, determine suas árvores geradoras.
	4. É comum encontrar as árvores geradoras T ao ser fornecido um grafo não direcionado e conexo G = (V, E). Entretanto, é possível fazer uma engenharia reversa para encontrar o grafo G = (V, E) a partir de suas árvores geradoras T. As árvores geradoras...
	De acordo com as oito árvores geradoras, determine o grafo G.
	5. A principal finalidade das árvores geradoras é visitar todos os n vértices de determinado grafo – isso a partir de n - 1 arestas. Entretanto, há uma especialidade das árvores geradoras chamadas de árvores geradoras mínimas, sendo classicamente conh...
	​De acordo com a figura, determine as arestas que compõem a árvore geradora mínima deste grafo.
	6. Os algoritmos de Prim e Kruskal constituem estratégias clássicas para a obtenção da árvore geradora mínima de grafos. Ambos podem alcançar bom desempenho computacional desde que suas particularidades sejam levadas em consideração durante a implemen...
	7. O BFS implementa uma fila na qual são inseridos os nós conectados ao nó visitado em cada camada. Esse processo se repete até que nenhum outro nó conste na fila. Dado o grafo, determine a sequência da fila se for executado umalgoritmo do tipo BFS:
	8. Os algoritmos de correspondência de strings incluem o algoritmo de força bruta (BF), o algoritmo Knuth-Morris-Pratt (KMP) e o algoritmo Boyer-Moore (BM), alguns dos algoritmos de pesquisa mais famosos. Todos eles executam os passos de busca de padr...
	9. Um problema tradicional em que algoritmos gulosos são aplicados é o de escalonar os intervalos de tempo para uso de determinado recurso. Considerando um conjunto R de n requisições, em que cada requisição i retém o recurso por um intervalo de tempo...
	Nesse cenário, analise as afirmações a seguir e a relação proposta entre elas: I. Um algoritmo guloso que itera sobre R aceitando a primeira requisição i com o menor f(i) possível, retorna um conjunto A com uma solução ótima, considerando que, para to...
	10. Vários são os problemas que podem ser modelados com grafos. Dentre os vários benefícios dessa modelagem, estão o uso de estruturas de dados otimizadas e a possibilidade de projetar algoritmos gulosos adaptados às particularidades do cenário. Um ex...
	Esse é um problema típico de cobertura de conjunto. Para cada cidade x, seja Sx o conjunto de cidades distantes 30km dele. Uma escola em x irá essencialmente “cobrir” essas outras cidades. Um modelo computacional comum para esse cenário é o uso de gra...
	I – O algoritmo guloso encontra a solução ótima para o problema.
	II – O primeiro Si selecionado pelo algoritmo corresponde ao vértice "a".
	III – Na segunda iteração, o algoritmo deve escolher entre quatro elementos possíveis.
	IV – O vértice de maior grau compõe a solução ótima para o problema. Quais estão corretas?