Details

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

This work is dedicated to the generation of educational problems on finding strongly connected components of a directed graph and constructing its metagraph. The work presents basic theoretical information about directed graphs and Kosarajus algorithm for finding their strongly connected components. Existing soft ware solutions and approaches to developing problem generators are also analyzed. Two templates of educational problems and a general scheme of the generator of problems corresponding to these templates are provided. The developed algorithms are described, namely the algorithm for generating a directed graph used in a problem and the algorithms for drawing a directed graph and its metagraph in LaTeX. The prob lem generator program is implemented that creates a LaTeX file with an educational problem. This program allows flexible configuration of the problem generation pro cess.  Automating the generation of educational problems saves an instructor’s time in preparing them.