Dissertação

Automatic Generation of Exercises for Massive Open Online Courses (MOOCs) EVALUATED

A geração automática de grafos aleatórios tem sido objeto de significativa investigação académica. No entanto, os algoritmos existentes apenas permitem determinar a probabilidade de certas características serem encontradas no grafo gerado. Assim, estes grafos não se adequam a exercícios para cursos de introdução a algoritmos, dado poderem não ter propriedades relevantes para os algoritmos em estudo. São aqui apresentados novos algoritmos capazes de gerar grafos cujas propriedades finais são estabelecidas por parâmetros selecionados pelo utilizador. O primeiro algoritmo gera grafos ligados, não pesados e não dirigidos. O utilizador pode selecionar o número de vértices, sugerir o número de arcos, determinar a dimensão máxima de todos os caminhos mais curtos a partir de uma determinada raiz e determinar a existência de pelo menos um caminho mais curto cuja dimensão mínima é igualmente selecionada. O segundo algoritmo gera grafos pesados e dirigidos. O utilizador pode selecionar o número de vértices, sugerir o número de arcos, determinar o âmbito dos valores dos pesos dos arcos, determinar a existência de ciclos de valor negativo e a existência de vértices não atingíveis a partir da raiz. Estes algoritmos foram avaliados no contexto de um curso de introdução aos algoritmos desta Universidade. As ferramentas implementadas com base nestes algoritmos foram usadas para validar o atual processo de avaliação dos alunos, para gerar os grafos utilizados na avaliação automática do código dos alunos e para procurar pequenos grafos que revelem erros nesse mesmo código. Os resultados foram francamente positivos.
grafos, educação, geração de grafos, algoritmos

Novembro 12, 2015, 14:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Mikolas Janota

Microsoft Research

Investigador

ORIENTADOR

Vasco Miguel Gomes Nunes Manquinho

Departamento de Engenharia Informática (DEI)

Professor Associado