Proponha um modelo em grafo para representar conflitos de horários entre turmas (nós) e descreva um algoritmo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).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
modelagem de grafos
avaliacao
modelagem de grafos · algoritmos de atribuição
Revisar algoritmos de alocação de recursos e grafos.
O aluno pode falhar ao não considerar todos os possíveis conflitos de horários entre as turmas, resultando em um modelo incompleto.
ciencia_tecnologia
criatividade
abstrato
Questões parecidas com resolução
- Descreva um algoritmo colaborativo que use um grafo para alocar professores a turmas considerando restrições de horário…
- Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e conflitos de…
- Proponha uma decomposição em subtarefas e um esboço de pseudocódigo para automatizar um algoritmo que agenda horários de…
- Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar entre várias…
- Projete um algoritmo colaborativo para formar equipes em um projeto interdisciplinar: cada estudante é um registro…
- Descreva em pseudocódigo um algoritmo que detecte conflitos de sala em uma matriz 'horarios' onde cada registro é [dia…
Todas as questões de Organização e representação da informação
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog