Computação3º anoBNCC EF15CO02Difícil⏱ longo

Descreva como representar um labirinto como um grafo e escreva um algoritmo em linguagem descritiva que…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF15CO02

Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Descreva como representar um labirinto como um grafo e escreva um algoritmo em linguagem descritiva que encontre o caminho mais curto entre entrada e saída. Explique por que escolheu esse algoritmo e analise sua complexidade em termos de vértices (V) e arestas (E).

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

Resposta esperada

Representação: modele cada célula livre do labirinto como um vértice; conecte vértices por arestas quando células adjacentes (cima/baixo/esquerda/direita) forem acessíveis. Algoritmo (descrição): 1) Construir o grafo a partir do mapa do labirinto. 2) Executar BFS (busca em largura) a partir do vértice da entrada, mantendo fila e vetor de predecessores. 3) Ao alcançar a saída, reconstruir o caminho seguindo predecessores até a entrada. Justificativa da escolha: BFS garante encontrar o caminho com menor número de arestas em grafos não ponderados, ou seja, o menor número de passos no labirinto. Complexidade: construir o grafo visita cada célula e suas adjacências: O(V+E). A execução do BFS também é O(V+E). Observação: se as arestas tiverem pesos diferentes (custos distintos), usar Dijkstra; para caminhos simples em grade sem peso, BFS é mais eficiente e suficiente.

Explicação

A representação do labirinto como um grafo permite a modelagem eficiente das células e suas conexões, facilitando a busca por caminhos. O algoritmo BFS é ideal para encontrar o caminho mais curto em grafos não ponderados, já que explora todos os vértices em camadas, garantindo a menor distância em termos de arestas. A análise de complexidade O(V+E) reflete a eficiência do algoritmo, considerando a quantidade de vértices e arestas no grafo.

Raio-X da questão

Dificuldade Difícil

Bloom Analisar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

representação de grafos

📌 Objetivo

avaliacao

🧱 Pré-requisitos

representação de grafos · algoritmos de busca

📚 Reveja

Revisar algoritmos de busca em grafos e suas complexidades.

⚠️ Erro mais comum

O aluno pode descrever um algoritmo que não considera todos os caminhos possíveis, levando a uma solução incorreta ou incompleta.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

cientifico

Questões parecidas com resolução

Todas as questões de Algoritmos

🔎 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