Содержание к диссертации
Введение
1. Проблематика процессов приобретения и управления знаниями 14
1.1. Управление знаниями 14
1.1.1. Жизненный цикл знаний 14
1.1.2. Управление знаниями организации 17
1.1.3. Модели представления знаний в информационных системах 20
1.1.4. Инструментальные средства управления знаниями 23
1.2. Семантическая теория информации в процессах приобретения знаний 24
1.2.1. Обзор концепций теории информации 24
1.2.2. Процессы приобретения знаний с позиций семантической теории информации 29
1.2.3. Эффективность освоения материала 32
1.3. Информационное обеспечение процессов приобретения знаний 35
1.3.1. Представление знаний в информационно-обучающих системах 35
1.3.2. Системы поддержки процессов приобретения знаний 37
1.4. Постановка задачи 43
2. Модели иерархического сетевого представления предметной области 45
2.1. Формирование семейства семантических моделей предметной области. 45
2.1.1. Отношение «часть - целое» и иерархические модели предметной области 45
2.1.2. Онтологическая модель предметной области процесса приобретения знаний 48
2.2. Сетевые модели представления предметной области 51
2.2.1. Применение сети знаний для представления предметной области 51
2.2.2. Представление траектории обучения с помощью сетевых графиков 53
2.2.3. Отношение упорядоченности и сетевые модели 55
2.3. Иерархическая сетевая модель информационного обеспечения 60
2.4. Оценка достижения целей информационного обеспечения 61
2.4.1. Нечеткая сетевая модель формирования целей информационного обеспечения 61
2.4.2. Формирование целевой функции информационного обеспечения 64
2.5. Формирование исходных данных для построения моделей предметной области 70
2.5.1. Сбор и обработка мнений экспертов 70
2.5.2. Автоматизация формирования дидактических связей 77
3. Процедуры иерархического сетевого представления предметной области 81
3.1. Способ формирования информационного обеспечения 81
3.1.1. Построение иерархической сетевой модели информационного обеспечения 81
3.1.2. Процедура определения структуры информационного обеспечения 85
3.1.3. Процедура определения последовательности объектов предметной области 86
3.2. Определение состава информационных элементов 87
3.2.1. Задача определения состава информационных элементов 87
3.2.2. Задача о рюкзаке 88
3.2.3. Применение задачи о рюкзаке для определения состава информационных элементов 89
3.3. Структурирование информационного обеспечения на основе кластеризации фрагментов контента 91
3.3.1. Оценка близости информационных элементов на основе дидактических связей 91
3.3.2. Процедура кластеризации объектов предметной области 95
3.3.3. Определение дидактических связей между информационными фрагментами 105
3.4. Определение последовательности применения информационных объектов предметной области 108
3.4.1. Алгоритмы топологической сортировки 108
3.4.2. Применение линейной сортировки информационных объектов предметной области 110
3.4.3. Применение параллельно-последовательной сортировки информационных объектов предметной области 110
4. Разработка информационного обеспечения процессов приобретения знаний 119
4.1. Процедура подбора курсов повышения квалификации для сотрудников организации 119
4.2. Структурирование дидактических материалов предметной области «Методология» 124
4.2.1. Формирование исходных данных 124
4.2.2. Определение расстояний между информационными элементами. 126
4.2.3. Выделение тем с помощью кластеризации информационных элементов 127
4.2.4. Формирование структуры предметной области «Методология» 133
4.3. Автоматизация разработки учебных планов 134
4.3.1. Формирование плана образовательного модуля целевой подготовки бакалавров 134
4.3.2. Автоматизация разработки учебного плана магистров 138
4.4. Формирование разделов дисциплины «Электроника» 141
Заключение 148
Список сокращений и условных обозначений 150
Список литературы 152
Приложения 164
- Обзор концепций теории информации
- Построение иерархической сетевой модели информационного обеспечения
- Применение параллельно-последовательной сортировки информационных объектов предметной области
- Формирование разделов дисциплины «Электроника»
Введение к работе
Актуальность темы исследования. В настоящее время как для деятельности отдельных специалистов так и организаций в целом всё больше возрастает значимость процессов управления знаниями и совершенствования информационного обеспечения. В работе термин «информационное обеспечение» трактуется в соответствии с ГОСТ 7.0-99: «Совокупность информационных ресурсов и услуг, предоставляемых для решения управленческих и научно-технических задач в соответствии с этапами их выполнения». Поэтому вопросы формирования и совершенствования информационного обеспечения играют важную роль в научно-технической и проектной деятельности. В условиях продолжающегося роста темпа обновления знаний и накопления информации быстрое развитие получила концепция обучающихся организаций, предложенная P.Senge. Такие организации создают, приобретают, передают и сохраняют знания. Для каждого из этих процессов и, особенно, для процесса приобретения знаний ключевую роль играют модели описания предметной области.
Вопросам непрерывного управления информацией в процессе жизненного цикла промышленных изделий посвящен ряд исследований в областях CALS-технологий (Continuous Acquisition and Lifecycle Support), PLM (Product Lifecycle Management), PDM (Product Data management) ряда известных авторов: Норенков И.П., Кузьмик П.К., Колчин А.Ф., Овсянников М.В., Стрекалов А.Ф., Сумароков С.В., Судов Е.В., Левин А.И., Петров А.В., Чубарова Е.В., Братухин А.Г., Советов Б.Я., Яковлев С.А.
Повышение эффективности процессов приобретения знаний, в том числе за счет создания информационно-образовательной среды, тесно связано с совершенствованием технологии подготовки информационного обеспечения, в том числе, предметного контента. Эта технология основывается на моделях представления предметной области, алгоритмах и инструментальных средствах для создания таких моделей. Изучению моделей представления знаний посвящены работы Сарвилиной И.Ю., Корпачевой Л.Н., Тарховой Л.М., Курзыбовой Я.В. и множества других исследователей.
Ввиду большого объема доступных информационных ресурсов, актуальным становится вопрос разработки способа, позволяющего повысить результативность приобретения знаний, в частности, за счет создания условий для наиболее успешного освоения контента предметной области посредством повышения качества подготовки информационного обеспечения.
Последние годы данному вопросу, а также вопросам, касающимся пространства знаний, систем управления обучением и контентом предметной области LMS и LCMS посвящен ряд исследований (Пудовкин Ю.В., Баротов К.А., Елагина В.С., Джамалова Т.Ю., Тагаева Г.М., Короткова И.И., Биркун Н.И., Зверев Д.И., Загрекова Л.В., Schrepp M., Albert D., Lukas J., Днепров Э.Д., Лиферов А.П., Борисова Т.Ф. и др.).
Наряду с составом и структурой информационного обеспечения развиваемые в работе модели содержат необходимые сведения для определения последовательности применения информационных объектов. Несмотря на наличие многочисленных исследований, можно констатировать отсутствие единого общепринятого подхода к вопросам определения состава и структуры информационного обеспечения, а также последовательности применения информационных объектов, обеспечивающих повышение эффективности процессов приобретения знаний.
я с
Таким образом, представляются актуальными задачи разработки теоретических основ и процедур для повышения эффективности приобретения знаний, в частности, посредством анализа и синтеза структуры и последовательности применения материалов, а также задача разработки способа и процедуры формирования траектории освоения материала, которая позволила бы достичь поставленной цели информационного обеспечения учетом уже приобретенных знаний.
Объект исследования – информационное обеспечение процесса приобретения и применения знаний, включая информационно-справочные системы и входящие в их состав системы электронного обучения, такие как интерактивные электронные технические руководства (ИЭТР).
Предмет исследования – модели и процедуры иерархического сетевого представления предметной области.
Цель и задачи
Целью работы является повышение эффективности информационного обеспечения процесса приобретения и применения знаний на основе разработки моделей и процедур иерархического сетевого представления предметной области.
Задачи:
-
Разработать нечеткую сетевую модель формирования целей информационного обеспечения.
-
Разработать способ формирования информационного обеспечения.
-
Разработать процедуру определения структуры информационного обеспечения на основе кластеризации информационных объектов.
-
Разработать процедуру определения последовательности изучения или применения информационных объектов.
-
Разработать методику автоматизированного структурирования учебно-методического обеспечения.
предметных областей (п. 4), разработки средств анализа информации и
предметных областе приобретения знаний
й (п. 9).
Область исследования Область исследования соответствует п. 2, 4, 9 паспорта специальности 05.13.17 «Теоретические основы информатики» в части исследования информационных структур, разработки и анализа моделей
х с
-
Разработана нечеткая сетевая модель формирования целей информационного обеспечения, предназначенная для управления процессами приобретения и/или использования знаний, позволяющая учитывать полезности информационных элементов и дидактические связи между ними, отличающаяся от известных способом оценивания степени освоения информационных элементов в зависимости от их порядка, а так же подходом к оценке реализованности целей информационного обеспечения.
-
Предложен способ формирования информационного обеспечения, предназначенный для иерархического сетевого представления предметной области, позволяющий структурировать контент информационно-справочных и иных систем, отличающийся от известных использованием взаимосвязанных этапов отбора, кластеризации и упорядочивания контента.
-
Разработана процедура определения структуры информационного обеспечения для построения моделей предметных областей с применением кластеризации информационных объектов, основанная на применении нового коэффициента близости информационных элементов, определяемого по графу дидактических связей использованием теории нечетких множеств, а также возможным учетом ограничений на объем кластеров.
-
Разработана процедура определения последовательности (траектории применения) информационных объектов, предназначенная для информационной поддержки процессов приобретения знаний, основанная на модификации алгоритма топологической сортировки, учитывающая дидактические связи между информационными элементами и отличающаяся от известной предложенным критерием максимизации степени достижения целей информационного обеспечения на основе нечеткой сетевой модели.
Теоретическая и практическая значимость работы
Полученные в диссертационной работе результаты могут быть использованы для поддержки принятия решений при приобретении и применении знаний, а именно: при создании информационного обеспечения производственных процессов, в части разработки элементов методического обеспечения информационных систем (справочные руководства, ИЭТР и др.), в корпоративных системах обучения персонала; при разработке программ отдельных курсов повышения квалификации, а так же комплексов программ с последующей их корректировкой; информационного обеспечения систем электронного обучения; при формировании программ дистанционного образования; при разработке и последующей корректировке учебных планов; формировании обучающих, справочных материалов, курсов лекций для отдельных дисциплин.
Реализация разрабатываемых подходов, методов и процедур в системах поддержки процессов приобретения и применения знаний, освоения предметной области будет способствовать повышению эффективности процесса восприятия информации пользователями за счет структурирования предметного контента, отбора необходимого и достаточного (для поставленной задачи) перечня информационных элементов, а также определению на нем порядка освоения, способствующего достижению целей информационного обеспечения (из условия максимизации целевых функций информационного обеспечения) с использованием дидактических связей между информационными элементами.
Полученные в диссертационном исследовании результаты используются в ФНПЦ АО «НПП «Полет», ООО «МФИ СОФТ», а также внедрены в учебный процесс на кафедре «Электроника и сети ЭВМ» Нижегородского государственного технического университета им. Р.Е. Алексеева.
Методология и методы исследования
Для решения поставленных задач применялись методы системного анализа, теории графов, теории нечетких множеств, теории информации, обработки экспертных оценок, кластерного анализа.
Положения, выносимые на защиту
-
Нечеткая сетевая модель формирования целей информационного обеспечения.
-
Способ формирования информационного обеспечения.
-
Процедура определения структуры информационного обеспечения.
-
Процедура определения последовательности информационных объектов.
Степень достоверности и апробация работы
Основные положения и результаты диссертационной работы доложены и обсуждены на следующих научно-технических конференциях, сессиях и симпозиумах.
1. Всероссийская научно-методическая конференция «Инновационные
технологии в образовательной деятельности», г. Нижний Новгород
(2011 г., 2013 г., 2014 г., 2015 г.);
-
14-16, 18-19 Нижегородская сессия молодых ученых (технические науки, математические науки), г. Нижний Новгород (2009 г. - 2011 г., 2013 г.-2014 г.);
-
Международная молодежная научно-техническая конференция «Будущее технической науки», г. Нижний Новгород (2009 г.- 2015 г.);
-
Международная научно-техническая конференция «Информационные системы и технологии», г. Нижний Новгород (2009 г. - 2016 г.);
-
Всероссийская научно-практическая конференция «Актуальные проблемы социальной коммуникации», г. Нижний Новгород (2011 г.);
-
Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», г. Москва (2012 г.);
-
Всероссийская научно-методическая конференция «Инновационные технологии современного учебного процесса», г. Нижний Новгород (2012 г.);
-
X, XI международный симпозиум «Интеллектуальные системы». INTELS'2012, г. Вологда; INTELS'2014, г.Москва (2012 г., 2014г.);
-
Всероссийская научно-практическая конференция «Инновационные технологии командообразования и лидерства в современных бизнес-организациях», г. Нижний Новгород (2012 г.);
-
XI, XII Всероссийская научная конференция «Нейрокомпьютеры и их применение», г. Москва (2013 г., 2014 г.);
-
III Международная конференция «Информационные технологии в науке, управлении, социальной сфере и медицине», г. Томск (2016 г.).
Публикации
Результаты исследований опубликованы в 49 печатных работах, из них 6 статей в рецензируемых научных журналах из списка ВАК, 2 свидетельства Федеральной службы по интеллектуальной собственности о государственной регистрации программы для ЭВМ
Личный вклад автора. Автором самостоятельно определены цели исследования и сформулирована постановка задачи разработки нечеткой сетевой модели формирования целей информационного обеспечения, разработан способ формирования и процедуры определения структуры информационного обеспечения, процедуры определения последовательности изучения или применения информационных объектов, а также разработана методика автоматизированного структурирования учебно-методического обеспечения.
Обзор концепций теории информации
Прежде чем перейти к понятию «теория информации», дадим определение понятия «информация». Информация – понятие, используемое в философии с давних времен и получившее новое, более широкое значение благодаря развитию кибернетики, где оно выступает как одна из центральных категорий наряду с понятиями связи и управления [126]. Первоначальное понимание информации как сведений сохранялось вплоть до середины 20-го века. В связи с развитием коммуникационных средств были предприняты первые попытки измерения количества информации с использованием вероятностных методов. Позднее появились другие варианты математической теории информации – топологический, комбинаторный и прочие – получившие общее название синтаксических теорий. Содержательный (смысловой) и аксиологический (ценностный) аспекты информации исследуются в рамках семантической и прагматической теорий соответственно [126].
Из множества определений понятия «теория информации» приведем определение, которое дается в [125]: Теория информации - теория, изучающая законы и способы измерения, преобразования, передачи, использования и хранения информации. В теории информации и ее технических приложениях центральными являются понятия количества информации и его меры.
В 1928 американский специалист по связи Р. Хартли предложил меру информации, которая не зависела от способов передачи и формы сигналов в передающих каналах, а также от содержания и психологических аспектов передаваемых сообщений. Каждое сообщение выбирается отправителем из заранее известного получателю множества возможных различных сообщений (общим числом m). Количество информации может быть оценено мерой неопределенности выбора, которая уничтожается после получения сообщения.
К. Шеннон [131] обобщил результат Хартли и его предшественников. В теории Шеннона все разнообразные случаи передачи информации сводятся к абстрактной схеме: "источник сообщений – передатчик – канал – приемник – получатель". Его теория учитывает зависимость неопределенности выбора не только от m, но и от вероятностей выбора символов и вероятностных взаимосвязей между ними. Поэтому вычисление меры информации базируется на вероятностных оценках. Теория информации Шеннона позволяла ставить и решать задачи об оптимальном кодировании передаваемых сигналов с целью повышения пропускной способности каналов связи, подсказывала пути борьбы с помехами на линиях и т.д.
Приведенные подходы к оценке информации не являются единственными в своем роде. На возможность иных, не специально статистических, подходов к определению информации указал Колмогоров [56].
В работах Хартли и Шеннона информация представлена синтаксическими отношениями. Количественная мера Хартли–Шеннона не претендует на оценку содержательной (семантической) или ценностной, полезной (прагматической) сторон передаваемого сообщения.
Новый этап расширения понятия информации связан с кибернетикой. Кибернетический подход развивается в работах Н. Винера [34]. Информация по Винеру — это "обозначение содержания, полученного из внешнего мира в процессе нашего приспособления к нему и приспособления к нему наших чувств" [34]. Таким образом, кибернетическая концепция подводит к необходимости оценить информацию как некоторое знание, имеющее одну ценностную меру по отношению к внешнему миру (семантический аспект) и другую по отношению к получателю, накопленному им знанию, познавательным целям и задачам (прагматический аспект) [41].
Развитие кибернетики дало толчок дальнейшему развитию теорий информации — семантической и прагматической.
Попытки построить модели понятия информации, охватывающие семантический аспект знания, содержащегося в некотором высказывании относительно обозначаемого объекта, привели к созданию ряда логико-семантических теорий (Р. Карнап, И. Бар–Хиллел, Дж.Г. Кемени, Е.К. Войшвилло и др.). В них информация рассматривается как уменьшение или устранение неопределенности. Если учитывать, что информация собирается для достижения некоторой цели, то ее ценность зависит от того, насколько она способствует достижению этой цели. Отсюда мера ценности может быть выражена через приращение вероятности достижения цели. Продолжая развивать этот прагматический аспект теории информации, Е. С. Вентцель указывает следующий путь оценки полезности информации. Когда эффективность каких-либо мероприятий можно оценить численно, приращение эффективности характеризует важность и ценность полученного сообщения. М. М. Бонгард связывает меру полезности сообщения с задачей, которую решает получатель, с запасом его знаний до прихода сообщения и способом истолкования сообщения.
В статистической и семантической теориях информации речь идет о потенциальной возможности извлечь из передаваемого сообщения какие-либо сведения. Вместе с тем в процессах информационного обмена часто складываются ситуации, в которых ценность или качество информации, воспринимаемое приемником, зависит от того, насколько он подготовлен к ее восприятию.
Новый подход к оценке семантической информации разрабатывался советским математиком Ю. А. Шрейдером [133]. Абстрактная модель системы связи в математической теории информации строится в предположении, что получателю известен алфавит источника сообщений. В более общей формулировке это требование означает, что для понимания и последующего использования сообщений получатель должен обладать определенным запасом знаний.
Одним из представителей прагматических теорий информации является поведенческая модель коммуникации — бихевиористская модель Акоффа–Майлса [41]. Следующим этапом в развитии прагматических теорий информации явились работы американского логика Д. Харраха, построившего логико-прагматическую модель коммуникации. Одной из слабостей бихевиористской модели является ее неподготовленность к оценке ложных сообщений. Модель Харраха предполагает учет общественного характера человеческой коммуникации. В соответствии с ней получаемые сообщения должны быть сначала подвергнуты обработке, после которой выделяются сообщения "годные к употреблению". Именно к совокупности годных к употреблению сообщений должны быть применены критерии прагматической ценности.
В работе [139] говорится, что количество семантической информации в сообщениях должно зависеть не только от заключенного в них смыслового содержания, но и от значения истинности этих сообщений. В [139] введено понятие условно ложного предложения, представляющего собой конъюнкцию двух его составных частей, одна из которых истинная, а вторая — ложная. Такое предложение одновременно несет информацию и дезинформацию. Количество семантической информации в сообщении, в данном случае, определяется степенью соответствия этого сообщения ситуации. Несоответствие возникает либо в результате бессодержательности сообщения, либо в результате его неточности. В данной теории непосредственно не используется понятие дезинформации, вместо этого вводится понятие степени неточности условно ложных предложений.
В работе [103] предлагается модифицировать классическую теорию семантической информации, включив в неё понятие дезинформации, которую несет ложное сообщение. В этой теории, как и в [139], рассматривается множество различных ситуаций – одно и то же предложение языка может быть истинным в одной ситуации и ложным в другой. Поскольку получатель сообщений не может быть застрахован от ошибок при оценке их истинности, количество семантической информации оценивается отдельно с точки зрения получателя и с точки зрения всезнающего эксперта.
Приведенный обзор самостоятельных, но тесно связанных подходов, показывает, что теория информации сформировалась, быстро эволюционировала во второй половине XX века и продолжает развиваться в XXI веке. При рассмотрении процессов приобретения знаний, основными подходами являются семантический и прагматический, позволяющие работать с содержательным аспектом информации.
Построение иерархической сетевой модели информационного обеспечения
Поскольку на сегодняшний день скорость обновления знаний непрерывно увеличивается, современный человек вовлечен в постоянный процесс работы с информационным обеспечением. Ввиду большого объема доступных информационных ресурсов, актуальным становится вопрос разработки инструментария [10, 44, 83], позволяющего повысить результативность работы с информационным обеспечением, в частности, за счет создания условий для наиболее успешного использования материала. Один из ключевых вопросов в разработке информационного обеспечения – выбор модели представления контента таким образом, чтобы обеспечить наиболее эффективную работу с ней как пользователя, так и разработчика. Качество информационного обеспечения можно рассматривать в двух аспектах – содержание и структура. Последняя, в свою очередь, включает в себя модель информационно-справочного контента и последовательность его применения [5, 75].
В главе 2 рассмотрены иерархическая и сетевая модели предметной области. Учитывая что, описание предметной области с помощью только сетевых или только иерархических моделей не является достаточным для представления информационного обеспечения, введена обобщенная иерархическая сетевая модель (п. 2.3).
В зависимости от вида входных данных рассмотрим возможные способы формирования иерархических сетевых моделей информационного обеспечения.
Случай 1. Входные данные представлены множеством информационных элементов, количество которых сравнительно невелико и обозримо для применения экспертных методов. Примерами задач с такими входными данными могут служить формирование тематического плана дисциплины, справочного пособия, структуры курсов повышения квалификации и т.д. Совокупность этапов построения иерархической сетевой модели для случая 1 (Алгоритм 1) приведена ниже. На рис. 3.1 приведена блок-схема Алгоритма 1 для случая двухуровневой модели.
Алгоритм 1.
1. Экспертным путем устанавливаются дидактические связи между ИЭ, отражающие отношение парной упорядоченности при рассмотрении (применении) ИЭ. Выполняются проверки на непротиворечивость и согласованность(если экспертов было несколько). В результате формируется сетевая модель информационного обеспечения. Если экспертами применялись не бинарные оценки парной дидактической упорядоченности, то формируется взвешенная сетевая модель информационного обеспечения.
2. На основе полученных оценок парной дидактической упорядоченности рассчитываются расстояния между ИЭ с применением мер близости (как показано в п. 3.3.1).
3. Выполняется кластеризация ИЭ на основе матрицы расстояний, полученной на шаге 2. В результате формируются информационные фрагменты (ИФ), представляющие собой информационные объекты предметной области (ОПО) следующего (более высокого) уровня иерархической модели информационного обеспечения.
4. Определяется порядок изучения ИЭ внутри кластеров.
5. Рассчитываются меры близости между полученными кластерами (информационными фрагментами) на основе связей между ОПО, вошедшими в разные кластеры и определяется матрица дидактических связей между ИФ (на очередном уровне).
6. Определяется порядок изучения ИФ (на очередном уровне).
7. Перейти на следующий уровень.
8. Перейти к п. 2, если не достигнуто заданное количество уровней и, в противном случае, завершить синтез иерархической сетевой модели информационного обеспечения.
Случай 2. Входные данные представлены «Деревом знаний», т.е. иерархической моделью информационного обеспечения. Примерами таких моделей являются дерево понятий «Computing Classification System» [83], представленное на рис. 2.3, различные справочные ресурсы (в том числе построенные на wiki движке), классификаторы (УДК, ГРНТИ) ит.д. Требуется построить модель некоторого фрагмента исходного «дерева знаний». Совокупность этапов построения иерархической сетевой модели для случая 2 (Алгоритм 2) приведена ниже. На рис. 3.2 приведена блок-схема Алгоритма 2.
Алгоритм 2.
1. Выбирается фрагмент входной иерархической модели, соответствующий некоторому кусту исходного дерева.
2. Экспертным путем устанавливаются дидактические связи внутри отдельных уровней выбранного фрагмента, при этом выбор уровня детализации и количества таких уровней определяется лицом, принимающим решения (ЛПР). Дидактические связи могут быть бинарными или взвешенными.
3. Определяется порядок изучения ИЭ и ИФ на всех выбранных иерархических уровнях.
4. В результате формируется иерархическая сетевая модель информационного обеспечения.
Применение параллельно-последовательной сортировки информационных объектов предметной области
Кроме задач формирования линейного порядка рассмотрения объектов предметной области, существует ряд задач, когда требуется построить параллельно-последовательную сортировку, например, при формировании учебного плана, когда в одном и том же семестре изучаются параллельно несколько дисциплин.
Параллельно-последовательная сортировка объектов может быть представлена ярусно-параллельной формой (ЯПФ) графа [32]. Ярусно-параллельная форма (ЯПФ) ориентированного ациклического графа определяется распределением вершин этого графа на такие перенумерованные подмножества Si , что, если дуга l идет от вершины d1 є Sj к вершине d2eSk, то обязательно j k. Каждое из множеств Si представляет i-й ярус ЯПФ, а число вершин Si в ярусе - его ширину.
Число ярусов в ЯПФ графа является его высотой, а максимальная ширина ярусов - шириной ЯПФ. Минимальной высотой всех возможных ЯПФ графа является его критический путь. Построение ЯПФ с высотой, меньшей критического пути, невозможно. Для построения ЯПФ графа используется один из алгоритмов топологической сортировки.
Для реализации проверки ацикличности, а также построения ярусно-параллельной формы графа и квази-ЯПФ графа разработано соответствующее программное обеспечение.
Построенная таким образом ЯПФ графа имеет высоту не меньше длины критического пути в исходном графе и неограниченное количество вершин в каждом ярусе. Однако, в реальных задачах (например, при формировании учебного плана), количество ярусов может быть задано заранее, причем их число может быть меньше, чем длина критического пути исходной графовой структуры. Также возможно наличие ограничений на объем каждого из ярусов. В этом случае, возможно размещение части связей внутри ярусов, поэтому полученную структуру будем называть квази ярусно-параллельной формой графа [21].
В таком случае задача может быть решена переборным алгоритмом, т.к. применить алгоритм топологической сортировки, без его модификации, не удастся.
Запишем многокритериальную задачу дискретной оптимизации
Для решения задачи будем считать, что графовая структура, отражающая дидактические связи между ОПО, направленная и не содержит циклов. Процедуры обнаружения и разрешения направленных циклов в графе описана в п.2.5.
Пусть задано множество объектов предметной области X = {x1, x2 ,..., xN }, их объемыvn ,n = 1, N .
Для квази-ЯПФ графа, ширина яруса определяется суммарным объемом ОПО в ярусе Vi , высота графа соответствует заданному числу ярусов Nяр .
Число всех структур квази-ЯПФ (включая как допустимые, так и не допустимые структуры) определяется выражением Nстр =NярN где N – мощность множества объектов; Nяр – заданная высота ярусно-параллельной формы графа.
Каждое из решений закодируется вектором-строкой r с N элементами, номера которых соответствуют объектам, а значения элементов – номерам ярусов, на которых расположены эти объекты. Совокупность всех возможных решений представлена матрицей R , размера Nстр N . Строки матрицы R определяют различные решения (структуры квази-ЯПФ).
Для решения задачи (3.6) выбора структуры квази-ЯПФ введена совокупность показателей, на основании которых определены частные целевые функции и ограничения [21].
Суммарное количество «обратных» связей между объектами квази-ЯПФ – количество дидактических связей, идущих от вершин яруса с большим номером, к вершинам яруса с меньшим номером
Поскольку наличие «обратных связей» не позволяет обеспечить последовательный характер работы с объектами предметной области, то на основе показателя (3.7) сформировано ограничение к=0. Таким образом, задача построения квази-ЯПФ графа может быть представлена как задача минимизации целевых функций (3.8) и (3.9) на множестве квази-ЯПФ графа без обратных связей Jосk = 0 с заданной высотой сем и ограничениями на ширину ярусов V\q - допу, где Ц - суммарный объем ОПО, отнесенных к 7-муярусу,у = 1,тяр.
Очевидно, что задача построения квази-ЯПФ графа имеет решение только в том случае, если суммарный объем ОПО не превышает суммарный объема ярусов
Решение задачи дискретной оптимизации (3.6) кроме переборного алгоритма может быть найдено на основе модификации алгоритма топологической сортировки графа с учетом ограничений на объемы ярусов, высоту ЯПФ и учета весов связей (в матрице смежности W).
Пример применения параллельно-последовательной сортировки объектов при разработке учебного плана. Предполагая наличие обширных учебно-методических ресурсов и преподавательского опыта в вузе, будем считать доступным множество дисциплин, достаточное для отбора и определения состава дисциплин D УП, отбор которых осуществляется на основе перечня компетенций, содержащихся в ФГОС ВО. Также к исходным данным относятся сведения о наличии дидактических связей между дисциплинами, которые могут быть представлены в виде квадратной (N х N) -матрицы Q, определение элементов которой осуществляется на основе обработки экспертных мнений членов координационного совета по направлению подготовки.
Разработку учебного плана p на основе решения задачи оптимизации будем проводить по критерию дидактически упорядоченного изучения дисциплин. Определяемый при этом порядок изучения дисциплин обеспечивает достаточность знаний для успешного освоения последующего материала на каждом этапе учебного процесса. Многокритериальная задача дискретной оптимизации, в результате решения которой находится распределение дисциплин по семестрам, определяющее УП: J(p;Q) - min,p є P, где J(p;Q) - вектор целевых функций; P – множество допустимых решений, состоящее из всех возможных УП, удовлетворяющих ограничениям ФГОС ВО.
Для решения приведенной задачи представим УП в виде направленного ациклического графа, вершинами которого являются дисциплины, наличие дидактической связи между ними отражают дуги. Предусмотрены процедуры обнаружения направленных циклов в полученном графе, в том числе на основе анализа связей между ИЭ, когда разрешение цикла возможно за счет перераспределения ИЭ между дисциплинами (п. 3.3.3).
В качестве примера рассмотрим задачу формирования УП на множестве D, состоящем из di ,i = 1,N дисциплин, N =8. Трудоемкости отдельных дисциплин в зачетных единицах трудоемкости (ЗЕТ) определяются вектором-строкой v = [2,6, 4,5,5,2,3,3]. Количество семестров Nсем =3, что соотвествует количеству учебных семестров при подготовке магистров. Ограничения на объем семестров заданы вектором Vдоп =[12,12,9]. Тогда количество возможных решений (вариантов распределения N =8 дисциплин по Nсем =3 семестрам) составляет Nстр = 38 = 6561. Матрица смежности Q, отражающая экспертные оценки дидактической упорядоченности дисциплин приведена в таблице (таблица 3.2). Тогда размерность матрицы R решений составляет 65618, а например строке r990 = [1, 2,2,1,1,2,3,3], соответствует граф, представленный на рис. 3.12. Каждый номер элемента строки r990 сопоставлен с определенной дисциплиной, а значение – с номером смемстра.
Формирование разделов дисциплины «Электроника»
Аналогично разработанный подход применен при формировании учебных материалов по дисциплине «Электроника».
Выявлено 28 информационных элементов ( x1,...xN , N = 28), соответствующих основным темам, изучаемым в данном курсе, установлены дидактические связи между ними, представленные матрицей W. Выбрана шкала оценки дидактических связей (таблица 4.6).
Информационные элементы и связи между ними приведены в Приложении 5.
Учебным планом за данной дисциплиной закреплена компетенция ОПК-2 (Приложение 2), основной образовательной программой по направлению подготовки 09.03.02 «Информационные системы и технологии» для Электроники определена следующая дисциплинарная часть компетенции (элементарная компетенция) «Знать основы работы основных полупроводниковых приборов, их характеристики и параметры». Данная дисциплинарная часть компетенции является целью информационного обеспечения дисциплины «Электроника».
Также установлено, какие из представленных ИЭ непосредственно участвуют в формировании цели и какой вклад вносят (в шкале от 0 до 1). Полезности отдельных ИЭ при формировании цели информационного обеспечения представлены вектором U (таблица 4.7).
Полученная матрица дидактических связей была проверена на наличие замкнутых циклов. Циклы не выявлены.
На основе матрицы дидактических связей W с использованием коэффициента близости по входящим связям, описанного в п. 3.3.1, построена матрица близости между ИЭ. На основе её значений определены расстояния между ИЭ, необходимые для дальнейшей кластеризации. Матрица расстояний D приведена в Приложении 6.
Для кластеризации ИЭ применен алгоритм иерархической агломеративной кластеризации, описанный в п. 3.3.2 (использован программный пакет MEGA 5.1).
Результат кластеризации представлен на рис. 4.20. Так как выбранный программный пакет допускает использование только латинских шрифтов, названия ИЭ приведены в транслитерации.
Как видно из рис. 4.20 в результате кластеризации выделено 4 кластера, соответствующих разделам дисциплины. Между полученными кластерами-разделами определены связи, как описано в п. 3.3.3. Полученная матрица смежности кластеров представлена в таблице (таблица 4.8). Для элементов каждого кластера была определена последовательность их изучения с применением алгоритма топологической сортировки графа, описанного в п. 3.4.
Результаты упорядочения ИЭ (сверху-вниз) для каждого из разделов приведены на рис. 4.21.
На следующем шаге выполнено упорядочение кластеров, аналогично упорядочению ИЭ в кластерах. Результат представлен на рис. 4.22.
Каждому кластеру присвоено название и порядковый номер раздела (по полученному порядку изучения). Соответствие номеров кластеров разделам приведено в таблице (таблица 4.9).
Из графика (рис. 4.24) видно, что при низких значениях изученности ИЭ, сформированность компетенции также низкая. Чем больше значение изученности, тем быстрее нарастает сформированность компетенции.