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

• Os aplicativos de mapa, como o GPS, ajudam o carro de entregas a chegar à casa do cliente. O aplicativo compara dois…
• Lia organiza carrinhos, bonecas e blocos separando cada tipo, colocando-os em caixas e guardando as caixas na…
• Em um jogo, uma personagem controlada por IA precisa chegar a um tesouro sem bater nas paredes. Qual instrução ajuda a…
• Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
• Em um programa, Substring(codigo, início, quantidade) pega letras do texto a partir da posição indicada, e…
• Projete um algoritmo em pseudocódigo que, dadas as variáveis temperatura (inteiro ºC), ocupacao (inteiro, número de…

Todas as questões de Algoritmos