Grátis: Assinale a alternativa que apresenta a análise correta das seguintes afirmativas: Os grafos (a) e (b) indicam o processo de geração da árvore gera...

Essa pergunta também está no material:

9 pág.

Teoria dos Grafos

UFSC

Mais perguntas desse material

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 conjunto S = ｛ a1, a2, …, an ｝ de tarefas, em que cada tarefa ai demanda pi unidades de tempo para ser concluída a partir do momento em que é iniciada. As tarefas podem ser executadas apenas uma por vez. Seja ci o tempo para finalização da tarefa ai, isto é, o tempo em que a tarefa ai completa seu processamento. Considerando que o objetivo é minimizar o tempo médio para finalização de todas as tarefas, ou seja, minimizar: Analise as afirmativas a seguir e marque V (verdadeira) ou F (falsa): 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.

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.
F, F, V, V.
V, V, F, V.
V, F, V, F.
F, V, F, V.

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 assim, alcançar todos os vértices. A partir do grafo, determine suas árvores geradoras.

AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c,d), (d,b), (d,e)}, AG3 = {(a,c), (a,d), (d,b), (d,e)}.
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c,d), (d,b), (d,e)}, AG3 = {(a,c), (a,a), (d,b), (d,e)}.
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c,d), (d,b), (d,e)}, AG3 = {(a,c), (a,d), (d,b), (a,e)}.
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c, e), (d,b), (d,e)}, AG3 = {(a,c), (a,d), (d,b), (d,e)}.

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 G são as seguintes: AG1 = ｛(a,d), (d,b), (b,c)｝, AG2 = {(d,a), (a,c), (c,b)}, AG3 = {(d,b), (b,c), (c,a)}, AG4 = {(b,d), (d,a), (a,c)}, AG5 = {(d,b), (b,a), (a,c)}, AG6 = {(d,a), (a,b), (b,c)}, AG7 = {(d,a), (a,b), (a,c)}, AG8 = {(d,b), (a,b), (c,b)}. De acordo com as oito árvores geradoras, determine o grafo G.

G = (V = ｛a,b,c,d｝ e E = {(a,d), (a,b), (a,c), (d,b), (c,b)}).
G = (V = ｛a,b,c,d｝ e E = {(a,d), (a,a), (a,c), (d,b), (c,b)}).
G = (V = ｛a,b,c,d,e｝ e E = {(a,d), (a,b), (a,c), (d,b), (c,b)}).

De acordo com a figura, determine as arestas que compõem a árvore geradora mínima deste grafo.

A principal finalidade das árvores geradoras é visitar todos os n vértices de determinado grafo – isso a partir de n - 1 arestas.
Há uma especialidade das árvores geradoras chamadas de árvores geradoras mínimas, sendo classicamente conhecidas por conta dos algoritmos de Prim e Kruskal.
AGM = ｛(a,e),(e,c), (c,b), (b,d)｝ (Alternativa correta)
AGM = ｛(a,e),(e,c), (c,b), (a,d)｝.
AGM = ｛(a,e),(e,c), (e,b), (b,d)｝.
AGM = ｛(a,b),(e,c), (c,b), (b,d)｝.

Dado o grafo, determine a sequência da fila se for executado um algoritmo do tipo BFS:

[A, B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[]
[A]
[B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[] (Alternativa correta)
[A]
[B, C]
[E, D]
[D]
[F]
[]

Qual alternativa representa uma semelhança entre esses algoritmos?

A pesquisa inicial por comparação da janela de caracteres é feita com caracteres do texto. Esse processo é denominado 'tentativa'.
Os algoritmos, assim que encontram o padrão no texto, marcam o primeiro padrão e param.
Esses algoritmos mudam a janela para a direita para que a pesquisa analise outra posição no vetor que armazena o padrão.
Os algoritmos escaneiam o texto pela janela. Cada janela tem o mesmo comprimento do padrão a ser pesquisado e é igual a m. (Alternativa correta)

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 [ s(i), f(i) ], o objetivo é atender ao maior número de solicitações possível. Porém, requisições com sobreposição de tempo são descartadas.

Nesse cenário, analise as afirmacoes 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 todos os índices r ≤ k, tem-se f(ir) ≤ f(jk). PORQUE II. Se for assumido que A não é um conjunto composto pela solução ótima, uma contradição é obtida para a condição de parada R = ∅ do algoritmo. Assinale a alternativa correta.

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 todos os índices r ≤ k, tem-se f(ir) ≤ f(jk).
PORQUE
II. Se for assumido que A não é um conjunto composto pela solução ótima, uma contradição é obtida para a condição de parada R = ∅ do algoritmo.
A afirmação I é uma proposição verdadeira e a II é uma proposição falsa.
As afirmações I e II são proposições verdadeiras e a II é uma justificativa correta da I.
As afirmações I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
A afirmação I é uma proposição falsa e a II é uma proposição verdadeira.

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 grafos: cada conjunto Sx vai ser representado por vértices e as distâncias de 30km que unem cada par de cidades por arestas. Considere esse cenário e o seguinte algoritmo guloso para ele: Algoritmo guloso Entrada: Um conjunto de elementos B e uma coleção S1, …, Sm. Saída: A seleção dos Si cuja união é B. 1. Repetir até que todos os elementos de B estejam cobertos. 2. Pegue o conjunto Si com maior número de elementos não cobertos. 3. Adicione Si à seleção que será retornada. Analise as afirmativas a seguir: 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?

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.
II e III.
I e II.
II e IV.
I, II e III.

Matemática Discreta

Teoria dos Grafos

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Teoria dos Grafos

Dado o grafo, determine a sequência da fila se for executado um algoritmo do tipo BFS:

[A, B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[]
[A]
[B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[] (Alternativa correta)
[A]
[B, C]
[E, D]
[D]
[F]
[]

Mais conteúdos dessa disciplina

Matemática Discreta

Teoria dos Grafos

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Teoria dos Grafos

Dado o grafo, determine a sequência da fila se for executado um algoritmo do tipo BFS:[A, B, C][C, E, D][E, D][D, F][F][B, C][C, E, D][E, D][D, F][F][][A][B, C][C, E, D][E, D][D, F][F][] (Alternativa correta)[A][B, C][E, D][D][F][]

Mais conteúdos dessa disciplina

Dado o grafo, determine a sequência da fila se for executado um algoritmo do tipo BFS:

[A, B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[]
[A]
[B, C]
[C, E, D]
[E, D]
[D, F]
[F]
[] (Alternativa correta)
[A]
[B, C]
[E, D]
[D]
[F]
[]