Proponha um modelo em grafo para representar conflitos de horários entre turmas (nós) e descreva um algoritmo…

Questão

Proponha um modelo em grafo para representar conflitos de horários entre turmas (nós) e descreva um algoritmo simples para atribuir horários evitando conflitos. Avalie vantagens e limitações do modelo.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Modelo: representar cada turma como nó; aresta entre nós indica conflito (professor ou sala comum). Algoritmo simples: algoritmo guloso de coloreção de vértices — atribuir o menor horário disponível (cor) a cada nó seguindo ordem por grau decrescente. Vantagens: implementação simples e rápido para conjuntos moderados; evita conflitos diretos. Limitações: solução pode não ser ótima (usa mais horários que o mínimo) e depende da ordem de processamento; não trata preferências, durações variadas ou restrições complexas (ex.: professores com pausas). Para melhorar, pode-se usar heurísticas avançadas ou algoritmos de backtracking/otimização considerando variáveis adicionais (salas, restrições de sequência), transformando o problema em coloração com restrições e aplicando algoritmos exatos ou metaheurísticas.

Explicação

O modelo proposto utiliza grafos para representar visualmente as relações de conflito entre turmas, facilitando a identificação de quais turmas não podem ter horários coincidentes. O algoritmo guloso de coloração de vértices é uma abordagem eficiente para atribuir horários, embora possa não garantir a solução mais otimizada. As vantagens e limitações destacadas mostram uma compreensão clara das implicações práticas do modelo e do algoritmo, além de sugerir melhorias para lidar com situações mais complexas.

Raio-X da questão

Questões parecidas com resolução

• Caminhões descarregam suprimentos em uma central que atende localidades isoladas após fortes chuvas. O depósito possui…
• Por que certos pedidos de melhoria no bairro demoravam a chegar ao responsável pela decisão? Para responder a essa…
• Ao final de uma oficina de montagem, uma turma precisou guardar 24 peças de encaixe usadas em atividades com tablets e…
• No fim da tarde, um grupo de jovens voluntários recebeu caixas de livros devolvidos por moradores do bairro. Para evitar…
• Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
• Em computação, defina sucintamente o que é um grafo simples não direcionado e explique o papel de vértices e arestas na…

Todas as questões de Organização e representação da informação