ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

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

Минуле століття було свідком неухильного розвитку теорії графів, яка за останні десять - двадцять років вступила в новий період інтенсивних розробок. У цьому процесі явно помітно вплив запитів нових областей: теорії ігор і програмування, теорії передачі повідомлень, електричних мереж і контактних ланцюгів, а також проблем психології та біології.[ 1 ]

Опис предметної області

Теорія графів має велике значення в сучасному математичному та комп'ютерному світах, що робить важливим поліпшення якості підготовки фахівців в технічних областях. Також графи широко використовуються в інших сферах наукової діяльності, наприклад, психологи людей представляють вершинами, а ребра - це їх відносини один з одним. Такими відносинами є, наприклад, любов, ненависть, спілкування, підпорядкування. Фізики - теоретики для «внутрішніх» потреб своєї науки «відкривали» теорію графів не один раз. Займаючись статистичної механікою, Уленбек позначав крапками (вершинами) молекули, а сусідство вершин тлумачив як взаємодія найбільшої близькості (сусідства) деякого фізичного типу, наприклад магнітне тяжіння або відштовхування. У подібній інтерпретації вершинами служать малі куби, що лежать в евклідовому просторі, кожен куб може бути зайнятий чи ні молекулою. Дві вершини вважаються суміжними, якщо обидва відповідних куба зайняті молекулами. Інший аспект використання теорії графів у фізиці - як образотворчий засіб. Вчення про ланцюги Маркова в теорії ймовірностей пов'язано з орієнтованими графами в тому сенсі, що події представляються вершинами в іншу, вказує на те, що ймовірність прямого переходу від однієї події до іншої позитивна. Подібна інтерпретація орієнтованих графів виникає в розділах чисельного аналізу, присвячених зверненню матриць і обчисленню власних значень.

Теоретико-графовий підхід використовується також у швидко розвиваючихся розділах лінійного програмування і дослідження операцій при вивченні потоків у мережах. [ 2-3 ]

Актуальність завдання

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

Об'єкт дослідження : інтелектуальні методи автоматичної генерації графів.

Предмет дослідження : практичні завдання з навчального курсу «Теорія графів».

Теоретична частина реалізації

Для того, щоб реалізувати автоматичний генератор практичних завдань з курсу «Теорія графів», необхідно вивчити будову навчального матеріалу, зміст основних розділів і виділити навички та вміння, яким повинен навчитися студент після кожного розділу.

Основні поняття «Теорії графів»

Нехай є деяка безліч V ≠ ∅ і нехай V - невпорядкована безліч всіх його двоелементною підмножин (V (2) = {(u, v): u, v ∈ V, невпорядкована пара}). Тоді, неорієнтованим графом G називається пара множин (V, E), де E ∈ V. Позначається: G = (V, E).

Безліч V називається множиною вершин графа, а безліч Е - множиною ребер графа. [ 4 ]

Число | V | вершин графа G називається його порядком. Якщо | V | = p, а | E | = q, то граф G = (V, E) називають p-графом, або (p, q)-графом, або Gp, q. Цей граф зображений на рис. 3.1.

Приклад графа

Рисунок 1 - Граф Gp, q

Дві вершини графа називаються суміжними, якщо вони з'єднані ребром.

Два ребра графа називаються суміжними, якщо вони мають спільну вершину.

Позначимо ребро графа: e = (u, v), де u і v - кінцеві вершини ребра. Ребро e інцидентне вершині v, якщо вершина v є однією з кінцевих вершин ребра e.

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

Якщо безліч V кінцева, те граф називають кінцевим. [ 6 ]

Способи завдання графів

Існують наступні основні способи завдання графів:

Графи для практичних завдань

Рисунок 2(анiмація - 81 кадрiв, 10 повторень) - Відображенния змiни вимог до графів для кожного розділу

Основні вимоги до практичних завдань

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


Вимоги до графа Лабораторна робота № 1 Лабораторна робота № 2 Лабораторна робота № 3 Лабораторна робота № 4
Кількість вершин 12-15 12-15 12-15 12-15
Кількість ребер Не менше 20-ти Не менше 20-ти Не менше 20-ти Не менше 20-ти
Цикли - \ + - \ + - \ + +
Петлі - - + +
Замкнутий граф - + - - \ +

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

Заплановані практичні результати

На сьогоднішній день існує декілька алгоритмів генерації випадкових графів за допомогою технологій і методів штучного інтелекту, наприклад, за допомогою генетичних алгоритмів. Але детального опису в джерелах масового доступу на даний момент немає. [ 9-11 ]

Своє дослідження і розробки в напрямку автоматичної генерації графів я планую таким чином:

1. Для кожного розділу дисципліни «Теорія графів» дослідити матриці суміжності та інцедентності

2. Виявити і зафіксувати для кожної матриці закономірність

3. На основі цих закономірностей розробити алгоритм генерації графів для кожного розділу

4. Проаналізувавши властивості матриць суміжності і інцедентності, створити можливість генерації універсального графу - графу, який відповідатиме вимогам відразу до декількох розділів «Теорії графів»

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

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

- У хімії (для опису структур, шляхів складних реакцій, правило фаз також може бути інтерпретоване як задача теорії графів);

- В інформатиці і програмуванні (граф-схема алгоритму);

- У комунікаційних і транспортних системах. Зокрема, для маршрутизації даних в Інтернеті;

- В економіці;

- У логістиці.

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

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

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

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

Висновки

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

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

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

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

  1. Структуризація основних розділів теорії графів.
  2. На підставі аналізу особливостей кожного розділу сформовані основні вимоги для практичних завдань.
  3. Розроблено покроковий план реалізації алгоритму генерації графів.
  4. Розглянуто можливості комплексної автоматизації розробленого підходу до генерації графів, оцінені вимоги до програмного забезпечення, виконан пошук функціонально подібних програмних продуктів генерації графів.

Подальші дослідження спрямовані на наступні аспекти:

  1. Якісне вдосконалення запропонованого підходу до генерації практичних завдань з курсу «Теорія графів».
  2. Визначення меж ефективності різних алгоритмів генерації графів.
  3. Розробка кроссплатформенної і функціональної системи автоматизованої генерації практичних завдань.

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2013 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Список джерел

  1. Уилсон. Р. Введение в теорию графов / Г.П. Гаврилов. – Москва: Мир, 1957. – 450 с.
  2. Оре. А. Теория графов / А. Оре. – Москва: Наука, 1980. – 348 с.
  3. Берж. К. Теория графов и ее применение / К. Берж. – Москва: Иностранная литература, 1962. – 432 с.
  4. Андреев. В.В. Информационная система управления вузом / В.В. Андреев. – Рязань: Полиграфия, 2010. – 282 с.
  5. Харари. Ф. Теория графов / Ф. Харари. – Москва: Мир, 1973. – 380 с.
  6. Евстигнеев. В.А. Применение теории графов в программировании / В.А. Евстигнеев. – Москва: Наука, 1980. – 355 с.
  7. Информационные технологии в учебном процессе: сб. наук. пр. / сост.: М.И. Жолдак и др..; Юго-укр. гос. пед. ун-т им. К.Д. Ушинского. – Одесса: Астропринт, 2007. – 167 с.
  8. Щеголов. В.И. Этническое в психологическом поле студента: монография / В.И. Щеголов. – СПб.: Астерион, 2004. – 91 с.
  9. Исаенко А.А. Электронные научно-информационные ресурсы / А.А. Исаенко / / Документоведение: материалы IV Междунар. научно-практической. конф. – Киев, 2007. – С. 179-180.
  10. Гордукалова. Г.Ф. Информационный мониторинг / Г.Ф. Гордукалова, В.А. Минкина / / Стратегическое использование информационных систем: материалы Междунар. семинара. – СПб., 1992. – С. 52-54
  11. Дайнеко В. Интеллектуальные продукты / В.Г. Дайнеко / / Вестн. Воронеж. гос. техн. ун-та. Ср. Гуманитарные науки. – 2005. – Вып. 94. – С. 19-20.
  12. Simon. Н.А.Information-processingmodelsofcognition / / J. Amer. Soc. InformationScience. Sept. 1981. – 208 p.
  13. Линдсей П., Норман Д. Переработка информации у человека / Под ред. А.Р. Лурия. Москва: Мир, 1974. – 345 с.
  14. Грунский И.С. Об алгебре языков, представимых графами с отмеченными вершинами / И.С. Грунский, Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2009. – т.18. – С. 37-46.
  15. Пряничникова Е.А. Характеризация языков, представимых в графах с отмеченными вершинами / Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2010. – т.19. – С. 37-46.