Детальная информация

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

This paper is devoted to the generation of educational tasks for the construction and verification of linearizations of digraphs (directed graphs). The paper presents basic information about digraphs and their linearization (topological sort), and also gives an overview of existing software solutions and approaches to the development of generators of educational tasks. Two templates of educational tasks are presented and the architecture of the generator of tasks based on these templates is described, including the algorithm for generating the digraph specified in a task condition, the  algorithm for constructing all linearizations of a digraph and two algorithms for visualizing digraph. The generator program  is developed that has user-configurable parameters and generates a LaTeX file with an educational task. This program reduces the time required to compose tasks for educational courses on algorithms.

• Введение
• Базовые сведения о линеаризации орграфов и методах генерации заданий
  • Основная терминология
    • Ориентированный граф
    • Ориентированный ациклический граф
    • Линеаризация орграфов
  • Обзор методов генерации учебных заданий
    • Генерация на основе шаблонов
    • Генерация математических выражений
    • Генерация на основе баз знаний
    • Алгоритм генерации заданий
• Близкие программные решения
  • Визуализация работы алгоритмов линеаризации
  • Алгоритмы RD-Gen для генерации случайных ациклических орграфов
  • Использование нейросетей
  • Генерация тестовых заданий на решение рекуррентных соотношений
  • Генерация учебных заданий на поиск в глубину и ширину в графах
  • Выводы
• Общая схема генерации учебных заданий на линеаризацию
  • Первый шаблон задания
  • Второй шаблон задания
  • Примеры заданий по первому шаблону
  • Примеры заданий по второму шаблону
  • Параметры генератора
  • Общая схема генерации учебного задания
  • Общая схема генерации вариантов ответов на учебное задание по второму шаблону
  • Общая схема генерации обоснования учебного задания по первому шаблону
  • Общая схема генерации обоснования учебного задания по второму шаблону
• Структура и описание разработанныхалгоритмов
  • Алгоритм генерации ориентированного графa
    • Общая идея алгоритма генерации орграфов
    • Псевдокод алгоритма
  • Алгоритм изображения орграфа
    • Устранение циклов
    • Присваивание уровня вершинам
    • Добавление фиктивных вершин
    • Присваивание ординаты
  • Алгоритм визуализации линеаризации орграфа
  • Алгоритм нахождения линеаризаций
• Программная реализация генератора заданий
  • Таблицы с описанием всех классов
  • Описание ключевых классов
    • Класс Main
    • Класс AllLinTaskGenerator
    • Класс CheckLinTaskGenerator
    • Класс Digraph
    • Класс DigraphGenerator
    • Класс LayoutDigraph
    • Класс DigraphDrawer
    • Класс LinearizationDrawer
    • Класс TableDrawer
  • Описание программы
    • Параметры
    • Интерфейс командной строки
    • Графический интерфейс
• Заключение
• Список использованных источников