Dissertação
{pt_PT=Automatic Generation of Exercises for Massive Open Online Courses (MOOCs)} {} EVALUATED
{pt=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., en=There has been a lot of research made on random graph generation, however most existing generators only offer a probabilistic expectation that a certain property will exist in the final graph. Therefore, this graphs are not adequate to be used as exercises in introductory algorithms courses since their properties may not relate to the algorithms being studied. We propose new algorithms that generate graphs parameterized by specific properties, specially selected for the generation of graphs for exercises. The first algorithm generates unweighted, undirected, connected graphs. Users may parameterize the number of vertices, the number of edges, the maximum length of all shortest paths from the root vertex and the existence of at least one shortest path with a predetermined minimum value. The second algorithm generates weighted, directed graphs. Users may parameterize the number of vertices, the number of edges, determine the range of possible weights, the existence of negative cycles and the existence of vertices unreachable from the root. We evaluated our algorithms by implementing a set of tools which were used in an introductory algorithms' course lectured at our University. Our tools were used to evaluate the current automatic grading process, to generate the graphs used to grade students' solutions for curricular exercises and to find problems in those solutions with small inputs. The results were highly positive.}
novembro 12, 2015, 14:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Vasco Miguel Gomes Nunes Manquinho
Departamento de Engenharia Informática (DEI)
Professor Associado