Sumário

1 Introdução 1

2 O Problema de Montagem de Avaliações Acadêmicas

2.1 Comentários Iniciais

2.2 Algoritmos para o Problema Bin Packing

2.3 Pontos Críticos

2.3.1 Exigência dos Pesos das Questões Totalizarem o Exato Valor da Prova

2.3.2 Aleatoriedade

2.3.3 Armazenamento e Gerenciamento da Base de Dados

3 Implementação Proposta

3.1 Comentários Iniciais

3.2 Pseudo-Código

3.3 Refinamentos

3.3.1 Obtenção do Vetor de Questões

3.3.2 Ordenação do Vetor de Questões

3.3.3 Obtenção do Vetor de Partições

3.3.4 Aleatorização do Vetor de Partições

3.3.5 Encontrar Partição Possível no Vetor de Questões

4 Conclusão 17

A Interfaces das Classes 19

A.1 Classe “questao”

A.2 Classe “particao”

A.3 Classe “quicksort”

A.4 Classe “avaliacao”

B Sites Consultados

Resumo

Nosso projeto propõe um algoritmo que implementa uma solução para montagem automática de avaliações acadêmicas. Com base nesse algoritmo é implementado um aplicativo que dispôe de uma base de dados com questões de diversos pesos que serão sorteadas e incluídas no arquivo final que conterá a avaliação.

Esforços têm sido despendidos por pesquisadores, acadêmicos e professores engajados no estudo da teoria de complexidade computacional, visando obterem implementações razoáveis que solucionem problemas NP-Completos. Dentre os problemas NP-Completos clássicos abordados na literatura especializada encontra-se o problema Bin Packing, no qual buscamos a primeira inspiração para a implementação que realizaremos. O termo bin packing tem por significado "empacotamento de caixas". O problema Bin Packing consiste em encontrar uma solução para empacotar objetos de diferentes tamanhos em caixas de tamanho fixos (bins), utilizando o menor número de caixas.

Trabalho Completo: Estudo de um algoritmo para montagem automática de avaliações Acadêmicas