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

Реферат по теме выпускной работы

Содержание

Введение

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

Прошлый век был свидетелем неуклонного развития теории графов, которая за последние десять - двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.[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(анимация - 81 кадров, 10 повторений) - Отображение изменения требований к графам каждого раздела

Основные требования к практическим заданиям

Исходя из задач в лабораторных, к генерируемого графу сформируем определенные требования, для каждой отдельной темы свои требования и занесем их в таблицу. Знак «+» обозначает, что для этой лабораторной работы это требование обязательно, знак «-» обозначает, это требование не должно присутствовать для графа темы, а знак «- \ +» обозначает, что требование необязательно.


Требования к графу Лабораторная работа № 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.