Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado…

Questão

Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica usa a mesma sala que Fotografia; Fotografia divide um monitor com Teatro; Teatro necessita do mesmo equipamento de Podcast. Além disso, Robótica e Teatro dependem da única impressora 3D disponível. A coordenação pretende criar um programa que distribua as oficinas em horários, sem coincidência entre atividades que compartilham sala, pessoa ou equipamento. Para isso, registrou apenas os pares de oficinas incompatíveis, pois outras combinações podem acontecer ao mesmo tempo. Analise as relações descritas e identifique a modelagem que permite ao programa separar as oficinas incompatíveis em horários distintos.

1. A) Representar horários como uma pilha, retirando a última oficina adicionada quando houver conflito.
2. B) Representar oficinas em uma fila, atendendo primeiro as que possuem maior quantidade de conflitos.
3. C) Representar oficinas como vértices e conflitos como arestas, atribuindo cores diferentes às oficinas ligadas.
4. D) Representar oficinas como nós de uma árvore, colocando cada conflito como dependente de uma oficina.
5. E) Representar cada oficina em uma tabela isolada, repetindo nela as oficinas incompatíveis.

✅ Resposta correta: alternativa C

Resolução passo a passo

1. Identifique as oficinas mencionadas: Robótica, Fotografia, Teatro, Podcast. Os conflitos registrados são pares: Robótica-Fotografia (sala), Fotografia-Teatro (monitor), Teatro-Podcast (equipamento) e Robótica-Teatro (impressora 3D).
2. Perceba que o problema é separar em horários distintos apenas as oficinas que estão ligadas por um conflito, e que as demais combinações podem ocorrer ao mesmo tempo. Isso é exatamente a estrutura de um grafo: cada oficina é um vértice e cada incompatibilidade registrada é uma aresta ligando dois vértices.
3. Atribuir horários corresponde a colorir o grafo: vértices ligados por aresta recebem cores (horários) diferentes. Assim, oficinas com a mesma cor podem ocorrer no mesmo horário, pois não há aresta entre elas. Esse é o modelo que resolve o problema proposto e cujo número mínimo de cores corresponde ao número mínimo de horários.
4. Por que as outras estão erradas: A usa pilha, estrutura que não representa relações entre pares de oficinas e não garante separação de conflitos. B usa fila, que ordena o atendimento mas não modela quais oficinas não podem coincidir. D usa árvore, que não serve para representar conflitos gerais, pois o grafo de conflitos pode conter ciclos, como Robótica-Fotografia-Teatro-Robótica. E usa tabelas isoladas, que não expressam as relações entre as oficinas e não resolvem a distribuição de horários.

💡 Dica: Identifique as relações de incompatibilidade e pense em como modelar essas restrições para evitar conflitos de horários.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Proponha um modelo em grafo para representar conflitos de horários entre turmas (nós) e descreva um algoritmo simples…
• Proponha uma decomposição em subtarefas e um esboço de pseudocódigo para automatizar um algoritmo que agenda horários de…
• Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
• Durante a montagem de uma mostra de curtas no centro cultural do bairro, estudantes programam um painel para iniciar…
• — O aplicativo mostrou uma rua livre, mas hoje há uma feira ali — avisou Joana, que trabalha orientando entregadores de…
• Por que avisos sobre a subida de um rio chegam tarde a alguns moradores? Para responder a esse problema, a Defesa Civil…

Todas as questões de Programação - Programação usando grafos e árvores