Details

Работа посвящена генерации учебных заданий одного вида на применение алгоритмов поиска в глубину и поиска в ширину в графах. В работе приводятся базовые теоретические сведения о графах, алгоритмах поиска в глубину и ширину. Также приводится анализ существующих программных решений и подходов к разработке генераторов учебных заданий. Приводится шаблон задания и высокоуровневая спецификация генератора заданий, на основе которых была разработана программа-генератор. Разработанная программа генерирует LaTeX-файл с учебным заданием. Также программа позволяет гибко настраивать генерацию тестового задания. Описываются разработанные алгоритмы для рисования графа в LaTeX, генерации графа, указываемого в условии учебного задания, построения всех деревьев поиска в глубину из заданной вершины графа, построения всех деревьев поиска в ширину из заданной вершины графа. Автоматизация генерации снижает общее время преподавателя на подготовку тестов.

The work is devoted to generation of educational problems of one kind on the example of depth-first and breadth-first search algorithms in graphs. The work contains basic theoretical information about graphs, depth-first search and breadth-first search algorithms. It also analyzes existing software solutions and approaches to the development of generators of educational problems. A problem template and a high-level specification of the problem generator are given, based on which the generator program was developed. The developed program generates a LaTeX-file with an educational problem. The program also allows flexible customization of educational problem generation. The work describes the algorithms developed for drawing graphs in LaTeX, generating the graph specified in the educational problem, finding all DFS trees from a given vertex of the graph, and finding all BFS trees from a given vertex of the graph. Automation of generation reduces the total time of the teacher for test preparation.