Computação & 11.645/08

Mochila 0/1 e Caixeiro‑Viajante em contexto indígena

Recontextualizamos problemas clássicos de Algoritmos (Mochila 0/1 e TSP) com elementos narrativos inspirados em contextos indígenas e conduzimos atividades no formato PRIMM (Predict, Run, Investigate, Modify, Make). O projeto dialoga com a Lei 11.645/08 e com diretrizes de Computação na BNCC, preservando a formulação clássica dos problemas e a ética no uso de referências culturais.

Ver materiais Ver resultados
Problema do Cesto

Mochila 0/1 (formulação clássica)

Seleção de itens com peso e valor sob capacidade W. Usamos itens didáticos (p.ex., arumã, jenipapo, yãkoana) apenas como narrativa, mantendo o modelo e algoritmos (DP, força‑bruta, guloso) inalterados.

Problema do Caminho dos Povos

Caixeiro‑Viajante (TSP métrico)

Visitar todas as aldeias e retornar com custo mínimo. Custos euclidianos sintéticos, instâncias pequenas e transparência para visualizar armadilhas gulosas e melhorias com 2‑opt. A narrativa inclui a motivação de trocas entre aldeias (p.ex., fibras de arumã, pigmentos), sem alterar a definição do TSP.

Turmas
4
Ganhos (TSP)
50% → 85.7%
Ganhos (Mochila)
33.2% → 85.6%

Atividades de Algoritmos

Mochila 0/1 — "Problema do Cesto"

  • Objetivo: modelar decisões sob restrição; comparar DP, força‑bruta e guloso.
  • Narrativa: escolhas de itens em deslocamentos (cesto como capacidade).
  • Ética: pesos/valores didáticos; distinção entre modelo e realidade.

TSP — "Caminho dos Povos"

  • Objetivo: compreender roteamento e melhoria local (2‑opt).
  • Motivação: deslocar‑se para trocas entre aldeias (fibras, pigmentos etc.).
  • Instâncias: N ≤ 6–8; custos euclidianos; visualização de armadilhas gulosas.

Metodologia PRIMM

  1. Predict: prever solução/rota sem executar.
  2. Run: executar código base (DP e guloso; vizinho mais próximo no TSP).
  3. Investigate: inspecionar tabela de DP, matriz de adjacência, laços e decisões.
  4. Modify: alterar w_i/v_i, inserir item/restrição, aplicar 2‑opt e observar efeitos.
  5. Make: criar instância autoral pequena e justificar critérios/rotas.

Resultados de Aprendizagem

Resumo Pré → Pós

AulaN (pré/pós)Média (%)Efeito
TSP28 / 2550.0 → 85.7g≈1.81, p<0.001
Mochila40 / 3933.2 → 85.6g≈2.91, p<0.001

Visual — ganho médio

Indicador simples (pré → pós)

TSP85.7%
pré: 50.0%
Mochila85.6%
pré: 33.2%

Dados agregados de pré/pós‑testes; instâncias e rubricas disponíveis nos materiais.

Materiais do Projeto

Autores & Contato

Coordenação: Weslen Schiavon e Gerson Cavalheiro

Dúvidas, contribuições e relatos de uso são bem‑vindos via Issues/Discussions no repositório.

Licença: CC BY 4.0 para materiais didáticos; código sob MIT.