Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e…

Questão

Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e conflitos de horários entre disciplinas. Indique quais estruturas de dados (registros, listas, matrizes, grafos) usará, explique por que cada escolha é adequada e descreva como combinar buscas e ordenações para gerar alocações compatíveis.

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

Resposta esperada

Resposta modelo (exemplo de solução): - Representações: usar registros para descrever entidades: Sala{id, capacidade, recursos} e Turma{id, tamanho, disciplinas, preferências}. Utilizar uma matriz horários[dias][turnos] para representar ocupação de salas por slot temporal. Representar conflitos entre disciplinas (compartilham alunos ou professor) como um grafo onde vértices são disciplinas/turmas e arestas indicam conflito. - Estratégia: 1) Construir o grafo de conflitos e aplicar uma coloração heurística (algoritmo guloso ou DFS com ordenação por grau decrescente) para atribuir turnos sem conflito; cada cor representa um conjunto de turmas que podem ocorrer simultaneamente. 2) Para cada turno (cor), obter a lista de turmas e ordenar turmas por tamanho decrescente; ordenar salas por capacidade crescente ou adequada. 3) Atribuir salas por emparelhamento guloso: para cada turma na lista, selecionar a menor sala disponível cuja capacidade >= tamanho da turma. Manter listas (fila ou vetor) de salas livres por turno e atualizar a matriz horários com o registro da alocação. - Ajustes e buscas: caso uma turma não caiba em nenhuma sala disponível, aplicar reordenação (backtracking limitado) ou tentar trocar alocações entre turmas semelhantes (swap) — usar busca local para melhorar solução. Para otimização por preferência de recurso, filtrar salas por recursos antes da atribuição. - Justificativa das escolhas: registros armazenam atributos heterogêneos; matriz modela claramente ocupação por dia/turno; grafo captura conflitos complexos; listas mantêm candidatos e permitem ordenação para heurísticas eficazes. A combinação de coloração de grafo e emparelhamento/guloso reduz conflitos temporais e respeita capacidades.

Explicação

A solução apresentada utiliza estruturas de dados adequadas para representar as entidades e relações do problema, permitindo uma visualização clara dos conflitos e ocupações. A combinação de coloração de grafo e emparelhamento guloso é eficaz para garantir alocações sem conflitos, respeitando as capacidades das salas. Além disso, a abordagem de reordenação e busca local para otimização demonstra flexibilidade na busca por soluções melhores, adaptando-se a diferentes cenários de alocação.

Raio-X da questão

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 uma decomposição em subtarefas e um esboço de pseudocódigo para automatizar um algoritmo que agenda horários de…
• Descreva como você construiria um programa que organiza o horário de aulas de uma escola. Inclua as estruturas de dados…
• Proponha um modelo em grafo para representar conflitos de horários entre turmas (nós) e descreva um algoritmo simples…
• Compare três instâncias do problema de alocação de salas: instância A (30 turmas, horários fixos), B (45 turmas…
• Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar entre várias…

Todas as questões de Algoritmos