Оптимізація алгоритму упорядкування графу дидактичної онтології

Оптимізація алгоритму упорядкування графу дидактичної онтології

Копилова В. Ю., Титенко С.В., к.т.н.
Національний технічний університет України «КПІ» ім. Ігоря Сікорського, м. Київ, vika.copilova@gmail.com 

В роботі визначено поняття дидактичної онтології, приведено можливі алгоритми пошуку шляху в графі дидактичної онтології, показано результати роботи алгоритмів, порівняння побудованих шляхів.

Вступ

В наш час людина повинна постійно розвити свої вміння та навички, щоб освоювати новітні технології, відповідати постійно зростаючим потребам ринку, а також доросла людина потребує індивідуального підходу до навчання відповідно до вже отриманих навичок, досвіду. Системи безперервного навчання орієнтуються на постійне вдосконалення і цілісний розвиток людини як особистості протягом усього її життя, підвищення можливостей в трудовій та соціальній сфері. Інформіційно-навчальні системи безперервного навчання повинні мати такі характеристики: індивідуалізація та адаптивність до попередніх знань учня, на основі цього було поставлено зачачу побудови індивідуального шляху проходження навчання на основі онтології предметної області.

Оптимізація алгоритму упорядкування графу дидактичної онтології

Дидактична онтологія

Онтологія — специфікація деякого предмета, а саме формальне та декларативне представлення, яке містить покажчик на терміни предметної області та логічні вирази, які описують значення термінів, їх співвідношення[1]. Сучасні онтології містять багато понять, тому вони часто мають формат, який зручно обробляти комп'ютерними програмами, а також мають строгу логічну базу.

Під дидактичною онтологією будемо розуміти зважений граф,  вершини якого є поняття, ребра — відношення дидактичного слідування, а вага — фактор впевненості деякого відношення. Поняття вказує на деякий об'єкт предметної області, що представляється для вивчення студентові. Відношення дидактичного слідування між поняттями вказує на порядок слідвання понять. Для побудови дидактичної онтології було використано модель застосування нечіткої логіки для розв'язання проблеми визначення дидактичної черговості едементів.

Задачею роботи є оптимізація впорядкування графу дидактичної онтології, а саме побудови шляху між поняттями, які потрібні студентові для вивчення обраної предметної області. Метод побудови шляху було вирішено вдосконалити за допомогою модифікації топологічного сортування.

Огляд існуючих методів

Топологічне впорядкування орієнтованого графа – це лінійне впорядкування його вершин таким чином, що для кожного натравленого ребра G = {u,v} з вершини u до вершини v, таким чином що вершина u передує вершині v[2]. Топологічне сортування можливо лише у випадку, коли граф немає орієнтованих циклів, тобто застосовується лише для орієнтованих ациклічних зважених графів.

Топологічне сортування можна реалізувати багатьма способами, а саме:

1. Алгоритм Кана[3]. Метод має ряд недоліків, через які не оптимально використовувати його при впорядкуванні графу дидактичної онтології. Алгоритм Кана потребує багато ресурсів та є асимптотично складним для реалізації. Оскільки при виборі вершини з множини немає конкретних правил, то отримана послідовність вершин для того самого графу, буде різною.
2. Алгоритм Прима — алгоритм побудови мінімального ациклічного зв’язаного підграфу. Асимптотична складність методу O(n²), Алгоритм Прима може бути вдосконалений за допомогою використання масиву суміжності О((n+m) log n) або кучі Фибаначі О(m + n log n)[4].
3. Алгоритм пошуку в вглиб перераховує все досяжні з кореня дерева s (якщо по ребрах йти) вершини в порядку зростання відстані від s. відстанню вважається довжина (число ребер) найкоротшого шляху. У процесі пошуку проглядаються всі сусідні вершини, потім сусіди сусідів тощо У процесі пошуку з графа виділяється частина, для кожної вершини якої шлях з кореня в дереві пошуку буде одним з найкоротших шляхів в графі[5].
4. Алгоритм Тарьяна потребує складності O(n) та використовує алгоритм пошуку вглиб[6]. Алгоритм на початковому кроці позначає усі вершини білим, під час заходу вершина та вершини, знайдені пошуком вглиб, позначають сірими, після виходу вершину позначають чорним кольором. Якщо при проходженні алгоритму наступної вершини знайдено сіру, то знайдено цикл і робота припиняється.

Алгоритми топологічного сортування не є оптимальними для обраної предметної області, тому що не враховують особливості графу дидактичної онтології.

Метод виділення семантичного ядра[7]. Семантичне ядро — набір ключьових понять, які найсильніше пов'язані з іншими поняттями курсу. Алгоритм враховує дидактичні особливості предметної області, але потребує багато ресурсів.

Оптимізація алгоритму семантичного ядра

Алгоритм пошуку семантичного ядра було вирішено оптимізувати за допомогою додавання топологічного сортування пошуком вглиб:

1. Знайдемо семантичне ядро графу дидактичної онтології, а саме вершину, в яку входить найбільша кількість ребер. Задамо результуючу множину як семантичне ядро.
2. Знайдемо множину понять-вершин графу, які передують семантичному ядру. Знайдену множину впорядкуємо відповідно до ваги ребер. Знайдений підграф відсортуємо методом топологічного впорядкування вглиб. Додамо до результуючої множини відсортований підграф.
3. Знайдемо множину понять-вершин графу, що розсташовані після семантичного ядра. На отриманому підграфі виділимо ядро підграфу та рекурсивно виконуючи пункт 2.
4. Перевірити чи відповідає розмір послідовності кількості цільових зв’язаних понять. Якщо ні, по черзі запустити пункти 1-3 для зв’язаних понять, що досі не в послідовності.
5. Додати до послідовності незв’язані поняття.

Порівняння отриманих результатів

Топологічне сортування є одним з найкращіх методів впорядкування графів, але під час впорядкування графу дидактичної онтології він не враховує особливості графу, не враховує кількість вхідних ребер від кожної вершини, тому шлях, побудований цим алгоритмом не є оптимальним. На відміну від топологічного сортування, оптимізований алгоритм виділення семантичного ядра орієнтований на предметну область — систему безперервного навчання. На рисунку 1 представлено граф дидактичної онтології та наведено шляхи, побудовані топологічним сортуванням та алгоритмом виділення топологічного сортування(таблиця 1).

Рисунок 1. Зважений направлений граф дидактичної онтології
 

Алгоритм виділення семантичного ядра було оптимізовано за допомогою сортування підграфів алгоритмом топологічного сортування, тим самим кількість ресурсів та час роботи алгоритму стала меншою(таблиця 2) за рахунок використання меншої кількості ресурсів. За часом виконання топологічне сортування є найбільш оптимальним, але не виконує вимоги до предметної області.

Шлях побудований завдяки виділенню семантичного ядра враховує особливості дидактичної онтології, тому розміщує поняття-вершини, які не вимагають додаткового опрацювання вершин попередників, відповідно до ваги ребер.
 

Таблиця 1. Шляхи проходження графу топологічного сортування та алгоритмом виділення топологічного сортування
 

 Таблиця 2. Час виконання алгоритмів сортування графу “Матриця”
 

Висновки

Проаналізовано існуючі методи впорядкування графів, можливість застосування їх до предметної області – автоматизованих систем навчання. Було обрано метод, який орієнтуається на особливості предметної області. Метод семантичного ядра було оптимізовано за допомогою додавання топологічного сортування підграфів в середені графу, тим самим кількість вирористаних ресурсів була зменьшеною.

Література

1. David M. Mount, The Lecture notes: Design and Analysis of Computer Algorithms. [Електроний ресурс] / Dept. of Computer Science, University of Maryland, 2004. — Режим доступу:  http://www.cs.umd.edu/ mount/451/Lects/451lects.pdf . - сс.30-38
2. Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт — М.: Мир, 1983, — 406с.
3. Кнут Д. Искусство программирования Т. 1. Основные алгоритмы / Д. Кнут — М.: Вильямс, 2000, - 736с.
4. Кофман А., Фор Р. Займемся исследованием операций / А. Кофман, Р. Фор — М.: Мир, 1966, - 262с.
5. Кнут Д. Искусство программирования Т. 1. Основные алгоритмы / Д. Кнут. — М.: Вильямс, 2000, — 736с.
6. Кнут Д. Искусство программирования Т. 3. Сортировка и поиск / Д. Кнут — М.: Вильямс, 2000.
7. Титенко С. В. Побудова семантичного конспекту і понятійного довідника курсу [Електроний ресурс] / С.В. Титенко. — Режим доступу: http://www.setlab.net/?view=dissertation-2-3-4.

Презентація