Дата зміни інформації:

Трохименко О. С. ОСОБЛИВОСТІ ВПРОВАДЖЕННЯ НАВЧАЛЬНОГО ПРОГРАМНОГО ПРОДУКТУ ДЛЯ РЕАЛІЗАЦІЇ АЛГОРИТМУ ПОБУДОВИ МІНІМАЛЬНОГО КАРКАСУ

IVкурс, фізико-математичний факультет

Москаленко О.М., кандидат педагогічних. наук, асистент

Полтавський національний педагогічний університет імені В.Г. Короленка

Полтава

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

Комп’ютерні програми-тренажери широко використовуються у практиці предметного навчання і у професійній підготовці. У шкільному навчанні комп’ютерні тренажери призначені для набуття умінь і навичок для розв’язання типових завдань з певної предметної галузі.

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

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

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

Зв’язний граф може мати кілька каркасів. Якщо задати довжини ребер, то можна ставити задачу пошуку мінімального каркасу, яка має значну кількість практичних інтерпретацій.

Для пошуку мінімального кістякового дерева графа розроблено ряд алгоритмів, одним із яких є алгоритм Прима виокремлення мінімального каркасу для простих зважених графів, які зображають списками суміжних вершин. Побудова починається з дерева, що включає в себе одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить всі вершини вихідного графа. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з’єднують вершину з побудованого дерева і вершину, що не належить дереву [1, c. 21].

Зважаючи на поширеність веб-сервісу, можливість перегляду веб-сторінок незалежно від платформи як на стаціонарних комп’ютерах, так і на портативних пристроях учня/студента, для розробки демонстраційних програм доцільно використовувати веб-технології. Для розробки програмного засобу було обрано мову програмування JavaScript.

У порівнянні з іншими мовами програмування, JavaScript [2] має ряд переваг:

–                   висока продуктивність;

–                   функціональність: розробку JS-програми можна відокремити від власне розробки Web-сторінки, що спростить життя і програмісту, і дизайнеру;

–                   абсолютна безкоштовність;

–                   простота у використанні: маючи досвід програмування на поширених мовах знайдуть синтаксис JavaScript добре знайомим;

–                   портативність: один і той самий JS-код можна використовувати як у середовищах NT, так і на платформах UNIX.

Для побудови діаграми графа використовувалася безкоштовна JS-бібліотека «Dracula» [3]. Назва являє собою гру слів – Граф Дракула, Dracula Graph Library. На сьогоднішній день, останньою версією бібліотеки є 0.0.3alpha5.

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

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

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

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. М.Я. Бартіш Дослідження операцій. Частина 2. Алгоритми оптимізації на графах / М.Я. Бартіш І.М. Дудзяний. – Львів: Видавничий центр ЛНУ імені Івана Франка, 2007р. – 120с.

2. В. Вахтуров JavaScript. Освой на примерах / В. Вахтуров – Санкт-Петербург: БХВ-Петербург, 2007р. – 387с.

3. Dracula Graph Library [Електронний ресурс]. – Режим доступу до ресурсу: http://graphdracula.net.

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

Введіть цифри, що зображені у квадратах *