Descreva um algoritmo colaborativo que use um grafo para alocar professores a turmas considerando restrições…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Aplicar a estratégia de decomposição para resolver problemas complexos, dividindo esse problema em partes menores, resolvendo-as e combinando suas soluções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Descreva um algoritmo colaborativo que use um grafo para alocar professores a turmas considerando restrições de horário, disciplina e preferência: explique como representar professores, turmas e restrições como dados/variáveis, qual algoritmo de busca/otimização aplicar e como detectar e resolver conflitos.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Representar professores e turmas como nós de um grafo bipartido; atributos (variáveis) em nós: disciplinas, disponibilidade, preferências; arestas indicam compatibilidade com peso por preferência. Modelar restrições de horário como incompatibilidades temporais e remover arestas inválidas. Aplicar algoritmo de matching máximo ponderado (Hungarian/Hopcroft–Karp com custos) ou busca por satisfação de restrições com backtracking e heurísticas de ordenação das variáveis. Detectar conflitos por nós não casados ou sobreposições de horário; resolver reavaliando pesos, aplicando relaxação de restrições, busca local (hill-climbing) ou solicitar ajustes humanos. Para colaboração, manter repositório compartilhado de dados, registar variáveis de atribuição, usar mecanismos de lock ou atualização por consenso e fornecer visualização das trocas propostas.
Explicação
A representação de professores e turmas como um grafo bipartido permite uma visualização clara das relações e compatibilidades entre eles, facilitando a alocação. O uso de algoritmos de matching máximo ou busca por satisfação de restrições é adequado para otimizar a alocação, considerando as preferências e restrições. A detecção e resolução de conflitos garantem que a solução final atenda a todas as condições impostas, promovendo uma alocação eficiente e colaborativa.
Raio-X da questão
algoritmo colaborativo
avaliacao
representação de grafos · algoritmos de busca
Revisar conceitos de grafos e algoritmos de otimização.
O aluno pode confundir a representação de dados, não conseguindo alocar corretamente professores e turmas devido a uma má interpretação das restrições.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e conflitos de…
- Proponha um modelo em grafo para representar conflitos de horários entre turmas (nós) e descreva um algoritmo simples…
- Descreva um algoritmo colaborativo para distribuir notebooks entre turmas de várias escolas, detalhando como representar…
- Projete um algoritmo colaborativo para formar equipes em um projeto interdisciplinar: cada estudante é um registro…
- Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar entre várias…
- Proponha uma decomposição em subtarefas e um esboço de pseudocódigo para automatizar um algoritmo que agenda horários de…
🔎 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