[ «НАУКА И МОЛОДЕЖЬ – 2014 XI Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых СЕКЦИЯ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ подсекция ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ...»
Министерство образования и наук
и Российской Федерации
Федеральное государственное бюджетное
образовательное учреждение
Высшего профессионального образования
Алтайский государственный технический университет
им. И.И.Ползунова
НАУКА И МОЛОДЕЖЬ – 2014
XI Всероссийская научно-техническая конференция
студентов, аспирантов и молодых ученых
СЕКЦИЯ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
подсекцияПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И
АВТОМАТИЗИРОВАННЫХ СИСТЕМ
Барнаул – 2014 УДК 004 XI Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Наука и молодежь 2014". Секция «Информационные технологии». Подсекция «Программное обеспечение вычислительной техники и автоматизированных систем». / Алт. гос. техн. ун-т им. И.И.Ползунова. – Барнаул: изд-во АлтГТУ, 2014. – 89 с.В сборнике представлены работы научно-технической конференции студентов, аспирантов и молодых ученых, проходившей 24 апреля 2014 г.
Редакционная коллегия сборника:
Кантор С.А., заведующий кафедрой «Прикладная математика» АлтГТУ – руководитель секции, Крючкова Е.Н., профессор, зам. зав. кафедрой ПМ, Сорокин А.В., доцент каф. ПМ, ответственный за НИРС на кафедре ПМ
Научный руководитель подсекции: к.ф.-м.н., профессор, Кантор С.А.
Секретарь подсекции: к.т.н., доцент, Сорокин А.В.
Компьютерная верстка: Сорокин А.В.
© Алтайский государственный технический университет им. И.И.Ползунова
СОДЕРЖАНИЕ
Вольф В.Я., Астахова А.В. Разработка программного обеспечения для скрининга заболеваний органа зренияВорона О.И., Леонов С.Л., Коновалов В.К. Обработка данных компьютерных томограмм
Гузеев Д.С., Боровцов Е.Г. Инструментарий управления доменной средой Samba4 для операционной системы GNU/Linux
Есипенко С.П., Крючкова Е.Н. Проблема скелетной реконструкции произвольных биологических и механических объектов в системах компьютерного зрения
Зимонина А.В., Астахова А.В. Разработка программного обеспечения формирования и исполнения договоров поставки (на материалах фирмы ООО «Алейрон»)
Казаков М.Г., Крючкова Е.Н. Адаптивность классификации изображений на основе автоматической генерации обучающей выборки
Колосовский М.А., Крючкова Е.Н. Алгоритм обнаружения автомобилей на основе вычитания фона для видеонаблюдения за пешеходными переходами
Коновалова К.В., Бубнова Н.Д., Ловцкая О.В. Разработка системы управления базой метаданных геоинформационного Интернет-портала ИВЭП СО РАН
Корякин Н.А., Третьяков И.В.
Защита информации на мобильных устройствах под управление ОС Android в корпоративной среде
Костин К.В., Кантор С.А., Созутов А.Е. Разработка программного обеспечения для автоматизированного построения графика работы мастеров по обслуживанию заявок....... Кронберг И.А., Старолетов C.М. Создание универсальной среды для проведения вебинаров
Лаптев М.А., Некрасов Д.В., Сорокин А.В. Использование генетического алгоритма для решения задачи теории расписаний
Овчинникова А.А., Бразовская Н.В. Разработка программного комплекса для обучения студентов экономических специальностей финансово-коммерческим операциям с помощью интерактивных методов
Еремин Я.Б., Путинцев Р.В., Боровцов Е.Г. Разработка сетевого универсального органайзера студента
Зыков Р.В., Поддубный В.И. Разработка программного обеспечения для системы определения точных координат движущегося объекта с применением спутниковых радионавигационных систем
Савченко В.В., Крючкова Е.Н. Алгоритм семантического поиска в больших текстовых коллекциях
Смирнова А.Ю., Крючкова Е.Н., Тамплон А.В. Разработка программного обеспечения автоматизированной системы судейства и проведения соревнований в авиамодельном спорте
Бобб А.Я., Хатников А.С., Троицкий В.С. Средство профилирования для анализа проблем производительности в АБС RS-Bank
Уваров Д.А., Силин Д. И., Крючкова Е.Н. Инструментальная система эффективной разработки интерактивного обучающего курса
Шамин А.С., Кошелев К.Б. Численное моделирование движения подземных вод с использованием параллельных вычислений
Гуленко К.А., Старолетов С.М. Проектирование и реализация каркаса для создания электронных образовательных материалов
Чураков М., Старолетов C.М. Лицензии свободного программного обеспечения............. Краюшкин М.С., Старолетов C.М. Разработка утилиты для учета и анализа http траффика под ОС Linux
Стручев Р.К., Старолетов C.М. Комплекс программ для создания, просмотра и оценки анимированных изображений в формате gif
Ненайденко А.С., Боровцов Е.Г. Методы Data Mining как современные подходы для решения статистических задач прогнозирования
Смолянинов А.Ю., Крайванова В.А. Консольный клиент к музыкальному сайту............. Бобков К.А., Крючкова Е.Н. Распределенный комплекс управления устройствами в умном доме
Шитов Д.А., Старолетов С.М. Концепция построения искусственного интеллекта на основе абстрактного мышления и ассоциативной структуры мозга человека
Кааль C.В. Программная реализация модели баланса графа ссылок
Турубарова Е.А., Крайванова В.А. Плагин визуализации данных для фреймворка symfony 2
Гриднева А.Е., Корягина С.И., Моисеева А.А., Шевелев И.В., Яковенко Р.А., Рогозин К.И., Сорокин А.В. Дистанционная поддержка курса
Никитин А.А., Андреева А.Ю. Проблема определения параметров частиц по монохромному изображению процесса сварки
Головин М.А., Крючкова Е.Н. Контент-зависимое изменение размеров изображения.....
РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
ДЛЯ СКРИНИНГА ЗАБОЛЕВАНИЙ ОРГАНА ЗРЕНИЯ
Вольф В.Я. – студент, Астахова А.В. – к.э.н., профессор Алтайский государственный технический университет (г. Барнаул) Зрительная система является весьма чувствительным и одним из важнейших анализаторов человека, который передает ему около 80% информации об окружающей действительности. Глаз обеспечивает получение представления о движении предмета, о его освещенности, цвете, форме, величине, а также расстоянии, на котором предмет находится от человека. Глаза функционируют весь период нашего бодрствования, не переходя в состояние зрительного покоя. В итоге в многообразной трудовой деятельности людей, в выполнении ими многочисленных, часто – весьма тонких работ, глазам принадлежит первостепенная роль.К сожалению, зрительная система человека, как и любая другая, дает сбои. И эти сбои зачастую связаны с постоянными зрительными нагрузками, будь то чтение книги, просмотр телевизора, работа на компьютере или другая работа, требующая напряжения зрения.
Современная статистика показывает, что патология зрительной системы – далеко не редкое явление. И эта статистика свидетельствует о том, что патология органа зрения неуклонно растет с каждым годом. Однако любое заболевание не наступает внезапно, оно проходит так называемый функциональный этап развития, который является одним из важнейших, поскольку считается переходным от нормы к патологии. Именно, на данном этапе своевременное выявление имеющихся функциональных изменений, их профилактика и устранение могут позволить снизить уровень заболеваемости. Однако существует ряд проблем, препятствующих этому. В Алтайском крае основными из них в настоящее время являются:
низкая доступность специализированной офтальмологической помощи для населения;
сложности организационного характера при записи на прием к врачу-офтальмологу;
недостаточная оснащенность современным, высокоэффективным диагностическим и лечебным оборудованием;
отсутствие информационной базы данных, позволяющей оперативно получить необходимую информацию о проведении обследований, о заболеваемости болезнями органа зрения, о профилактических лечебных мероприятиях, проводимых среди Система удаленной скрининг диагностики зрения способна решить названные проблемы. Такая диагностика позволяет на безвозмездной основе упростить предварительное выявление у пациентов отклонений в состоянии органа зрения от нормы, а также провести централизованный сбор, статистическую обработку и анализ результатов данных, полученных при проведении скрининговых обследований населения. Основная цель удаленного скрининга раннее выявление заболеваний на основе оптометрических и офтальмологических обследований в интерактивном режиме.
Над компьютерными программами дистанционной диагностики состояния органа зрения работали многие организации, в том числе, Новосибирский филиал ФГУ МНТК «Микрохирургия глаза им. академика С.Н. Федорова» [1]. Следует отметить, что все эти проекты разработаны таким образом, что при проведении исследования используется лишь одна известная, редко две методики проверки зрительных функций, которых оказывается недостаточно для точной диагностики наличия или отсутствия патологических изменений органа зрения. Кроме того, упомянутые работы, помимо проекта Новосибирского филиала ФГУ МНТК Микрохирургия глаза им. академика С.Н. Федорова, не предусматривают возможность формирования и последующего анализа результатов исследования с использованием базы данных (БД) пациентов.
Проблема проведения массовых офтальмологических профилактических осмотров, связанная с низкой доступностью специализированной помощи населению, вынуждает специалистов искать пути е решения посредством решения задач по разработке различных компьютерных программ автоматизации офтальмологического скрининга взрослого населения. Разработка и создание программы автоматизированного офтальмологического скрининга, является задачей составляющей содержание данного проекта, который выполняется по заявке ГБОУ ВПО АГМУ Минздрава России и ФГБУ «НИИ КПГПЗ» СО РАМН, чем и обусловлена актуальность работы.
Цель проекта: разработать и создать систему автоматизированного скрининга заболеваний органа зрения, для своевременного выявления и профилактики глазных болезней у взрослого населения Алтайского края. Данная цель может быть разбита на следующие подцели:
упрощение методики проведения исследования основных зрительных функций у взрослых с целью выявления отклонений от нормы;
создание автоматизированной системы, позволяющей проводить массовые диагностические исследования взрослого населения, без участия врача-офтальмолога;
создание автоматизированной системы, способной накопить и систематизировать данные, полученные в результате проведенных исследований, с целью последующего статистического анализа для разработки профилактических мероприятий по предупреждению глазных заболеваний.
Задачи работы:
разработка проекта программного обеспечения для достижения поставленной цели и ее подцелей в двух режимах тестирования пациентов:
o на локальном компьютере;
o в сетевом варианте с использованием интернет-технологий;
отладка проекта на подмножестве реальных данных заказчика;
разработка технологической документации по эксплуатации системы.
Результатом работы является система автоматизированного скрининга заболеваний органа зрения, которая имеет клиент-серверную сетевую архитектуру и позволяет провести ряд оптометрических и офтальмологических обследований в интерактивном режиме посредством сети Интернет (см. рисунок 1).
В системе реализуются следующие возможности.
Тест на исследование остроты зрения. В тесте в качестве оптотипов применяются кольца Ландольта. Угловой размер и количество оптотипов, показываемых пациенту, а также количество допустимых ошибок строго соответствует мировому стандарту при исследовании остроты зрения.
Дуохромный тест для определения состояния рефракции на момент проведения обследования, ее сдвиг в сторону гиперметропии (дальнозоркости) или миопии (близорукости) [2].
Тест Амслера, который позволяет косвенно исключить или выявить патологию макулярной зоны — участка сетчатки, ответственного за состояние центрального зрения [2].
Тест на исследование полей зрения может выявить значительные изменения в поле зрения, связанные с заболеваниями глаз, такими как хориоретинит, отслойка сетчатки;
аномалиями зрительного нерва, например при далеко зашедшей глаукоме, или внутричерепными заболеваниями, связанными с повышением внутричерепного давления:
опухоль мозга, ишемическое повреждение или кровоизлияние в него.[2].
Тест на глаукому можно рассматривать как продолжение теста на исследование полей зрения. Он позволяет получить результаты, предназначенные для построения надежного и быстрого диагностического алгоритма, позволяющего выявить глаукому на ранней стадии.
Стоит отметить, что результаты удаленного скрининга являются лишь предварительными: при выявлении патологии органа зрения пациенту следует незамедлительно обратиться к врачу офтальмологу для установления более точного диагноза.
Помимо проведения оптометрических и офтальмологических обследований в интерактивном режиме, система предполагает автоматическое занесение в БД и хранение в ней персональных данных пациента (ФИО, дата рождения, адрес регистрации, номер СНИЛС), а также сведений обо всех проведенных обследованиях (дата обследования, полученные результаты). Таким образом, в базу данных попадают результаты не только текущего обследования, но и предыдущих обследований, если таковые имелись. Кроме этого, пациенту предоставляется возможность получения на руки результатов обследования и записи на прием к врачу-офтальмологу. Кроме того, врачу офтальмологу – на основании данных, хранимых в БД, предоставляется возможность формирования отчетов и диаграмм, отражающих зависимость уровня заболеваемости различными глазными болезнями от возраста, района проживания и т.д.
В результате создания системы должны быть улучшены значения следующих основных показателей, характеризующих состояние офтальмологической помощи в Алтайском крае:
улучшена доступность специализированной офтальмологической помощи населению Алтайского края;
увеличен процент охвата населения профилактическими осмотрами на предмет раннего выявления зрительных патологий;
уменьшено время, затрачиваемое на обследование значительной части населения для предварительного выявления отклонений зрительной системы от нормы;
время сбора и обработки статистических данных, характеризующих патологическую пораженность населения Алтайского края болезнями органа зрения;
профилактические мероприятия, разработанные на основании анализа полученных данных обследования, позволят снизить заболеваемость взрослого населения болезнями органа зрения.
Список литературы 1. Новосибирский филиал ФГУ МНТК «Микрохирургия глаза им. академика С.Н.
Федорова» [Электронный ресурс]. – Режим доступа: http://www.mntk.nsk.ru 2. Копаева В.Г. (ред.) Глазные болезни. – М.: Издательство «Медицина», 2002. – 560 с.: ил.
ОБРАБОТКА ДАННЫХ КОМПЬЮТЕРНЫХ ТОМОГРАММ
Ворона О.И. – студент, Леонов С.Л. – д.т.н., профессор, Алтайский государственный технический университет (г. Барнаул) Алтайский государственный медицинский университет*(г. Барнаул) Большинство заболеваний легких, особенно рак, туберкулез и пневмония, относятся к группе социально значимых. За четыре года количество ежегодно регистрируемых новых случаев раковых заболеваний в мире выросло почти на полтора миллиона, с 12,7 миллиона в 2008 году до 14,1 миллиона в 2012 году. Первое место как среди вновь диагностируемых злокачественных новообразований, так и среди причин смерти от онкологии занимает рак легких [1]. Чаще всего в мире в 2012 году диагностировали рак легких (1,8 миллиона случаев, 13 процентов от общего числа).Существует несколько способов исследования заболеваний легких и один из них это компьютерная томография. Компьютерная томография в настоящее время является методом выбора в диагностике объемных процессов средостения. Она позволяет выявить на ранних стадиях патологическое образование, правильно оценить его размеры и контуры, изучить его структуру, установить степень инвазии на окружающие органы и ткани, позволяет уточнить распространенность опухолевого процесса, тем самым определить его стадию.
Денситометрическая характеристика плотности объемных образований при компьютерной томографии позволяет отличить новообразования от кист, с высокой точностью установить гистологическое строение жировых опухолей [2].
Сейчас последовательность действий, выглядит следующим образом [3]:
Врач-рентгенолог работает с серией срезов, полученных с помощью компьютерного томографа. На каждом срезе подходящем для анализа выбирается область интереса, которая представляет собой прямоугольную область, она должна быть не менее 6 пикселей в любом разрешении и не содержать в себе что-либо кроме тканей самого шаровидного образования.
После выделения области интереса, значения яркости пикселей в шкале Хаунсфилда [4] сохраняются в файл для дальнейшей обработки. Шкала единиц Хаунсфилда— шкала линейного ослабления излучения по отношению к дистиллированной воде, рентгеновская плотность которой была принята за 0 HU (при стандартных давлении и температуре). Для материала X с линейным коэффициентом ослабления, величина HU определяется по формуле где и — линейные коэффициенты ослабления для воды и воздуха при стандартных условиях. Таким образом, одна единица Хаунсфилда соответствует 0,1 % разницы в ослаблении излучения между водой и воздухом, или приблизительно 0,1 % коэффициента ослабления воды, так как коэффициент ослабления воздуха практически равен нулю.
Из полученных значений получают набор параметров, по которому возможно проводиться дифференциальная диагностика в программе «Конструктор нейронных сетей», которая на основании существующей базы пациентов и сконструированной по ней сети, выдает вероятность того или иного заболевания.
На основании полученных данных врач-рентгенолог принимает решение о диагнозе.
Когда диагноз становится верифицированным, данные пациента добавляется в рабочую базу пациентов.
Файлы компьютерных томограмм имеют специальный формат dicom [5]. Dicom отраслевой стандарт создания, хранения, передачи и визуализации медицинских изображений и документов обследованных пациентов. Файлы типа dicom имеют четкую структуру, они состоят из заголовка и тела файла. Файлы, с которыми оперирует томограф,имеют тип CT- image, изображение черно-белого спектра. Значение яркости пикселя, такого изображения, соответствует шкале Хаунсфилда и изменяется от 1024 до +3071, но обычный компьютерный монитор способен отображать до 256 оттенков серого цвета. В связи со значительной шириной шкалы Хаунсфилда и неспособностью существующих мониторов отразить весь е диапазон в черно-белом спектре, используется программный перерасчет серого градиента в зависимости от интересуемого интервала шкалы.
Программное обеспечение написано на языке Java. Для того, чтобы программа работала с dicom CT- image файлом как с файлом обычного изображения используется плагин dcm4che2. Dcm4che2 - это открытое программное обеспечение на языке Java, для работы в сфере здравоохранения, оно является программной реализацией стандарта dicom, а потому содержит все необходимые инструменты для работы c ним.
Программа позволяет:
1. Загружать и просматривать последовательность dicom- изображений.
2. Масштабировать изображения с использованием метода ближайшего соседа или билинейного сглаживания.
3. Выделять область интереса и трансформировать ее на различных слоях.
4. Просматривать значение плотности указанного пикселя и информацию о выделенной области.
5. Сохранять интересующую последовательность в выбранную папку в виде набора txt 6. Получать значение параметров на основании плотностей 7. Отправлять параметры на сервер с программой «Конструктор нейронных сетей»
8. Получать ответ от сервера и выдавать результат врачу На разработанное программное обеспечение получено свидетельство о государственной регистрации. В дальнейшем планируется доработка программного обеспечения с целью расчета фрактальных параметров томограмм.
Список литературы 3. Рак: основные цифры и факты [Электронный ресурс]: «Всемирная организация здравохранения». – Электрон. текст. дан. – 2013. – Режим доступа:
http://www.who.int/cancer/about/facts/ru/ 4. Власов, П.В. Комплексная лучевая диагностика объемных образований средостения.Часть первая / П.В.Власов // Медицинская визуализация. – 2005. – №3. – С.
29-41.
5. Шкала Хаунсфилда [Электронный ресурс]: Википедия. – Электрон. текст. дан. – 2013. – Режим доступа: http://ru.wikipedia.org/wiki/Шкала_Хаунсфилда 6. Ворона, О. И. Получение и анализ данных компьютерных томограмм. / О.И.Ворона, С.Л.Леонов, В.К.Коновалов//X Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Наука и молодежь 2013". Секция «Информационные технологии». Подсекция «Программное обеспечение вычислительной техники и автоматизированных систем». / Алт. гос. техн. ун-т им. И.И.
Ползунова. – Барнаул: изд-во АлтГТУ, 2013. – С.16-18.
7. Dicom Standard [Электронный ресурс]: Официальный сайт организации, разрабатывающей стандарт DICOM. – Электрон. текст. дан. – 2013. – Режим доступа:
http://medical.nema.org/
ИНСТРУМЕНТАРИЙ УПРАВЛЕНИЯ ДОМЕННОЙ СРЕДОЙ SAMBA4 ДЛЯ
ОПЕРАЦИОННОЙ СИСТЕМЫ GNU/LINUX
Гузеев Д.С. – студент, Боровцов Е.Г. – к.т.н., профессор Алтайский государственный технический университет (г. Барнаул) Развитие информационных технологий повлекло за собой создание множества сервисов, обладающих необходимым для бизнеса функционалом. При этом на уровне предприятия все сервисы должны составлять единую информационную среду, тесно интегрируясь друг с другом. В роли основы такой инфраструктуры выступает доменная среда, связывающая разрозненные сервисы воедино.В последние годы наметилась тенденция к использованию, в том числе и на государственном уровне, свободного программного обеспечения. Одним из вариантов построения доменной среды является создание ее на базе открытого программного обеспечения Samba версии 4. Открытые средства для управления доменной средой Samba4 в настоящее время слабо развиты, основным вариантом является использование Microsoft Windows RSAT. Данный инструментарий управления работает на ОС Microsoft Windows, что не позволяет полностью отказаться от использования проприетарного программного обеспечения.
Целью данной дипломной работы является разработка инструментария управления доменной средой Samba4 для операционной системы GNU/Linux с возможностью управления доменными пользователями и компьютерами, а так же управления групповыми политиками. Разработка ведется на языке С++ с использованием фреймворка Qt4.
Основными особенностями Samba4 являются:
Свободное программное обеспечение с открытым исходным кодом;
Встроенный DNS-сервер, интеграция с существующим DNS-сервером;
Работа с протоколом Kerberos;
Управление групповыми политиками;
Возможности репликации с Microsoft Active Directory Возможности интеграции с приложениями, имеющими поддержку интеграции с Microsoft Active Directory Доменная среда строится вокруг службы каталогов, являющейся центральным хранилищем информации о пользователях, компьютерах и политиках предприятия.
Основным протоколом доступа к службе каталогов в настоящее время является LDAP (Lightweight Directory Access Protocol), получивший наибольшее распространение благодаря своей легкости при сохранении необходимого функционала. LDAP работает через стек протоколов TCP/IP.
Основные преимущества внедрения доменной среды:
Единая точка аутентификации;
Единая точка управления политиками;
Повышенный уровень информационной безопасности;
Интеграция с корпоративными приложениями и оборудованием;
Единое хранилище конфигурации приложений.
Разрабатываемое программное обеспечение должно обладать следующими особенностями:
Кроссплатформенность — ПО должно работать как на операционной системе GNU/Linux, так и на других операционных системах;
Обеспечение необходимого функционала управления доменной средой;
Интуитивно-понятный оконный графический интерфейс (GUI).
Функционал управления доменной средой включает в себя:
Глобальное управление сервисом — запуск, остановка, перезапуск;
Управление пользователями и компьютерами — добавление, редактирование, удаление, блокирование учетных записей пользователей;
Предоставление информации о состоянии системы;
Управление групповыми политиками.
В дальнейшем данный проект может быть расширен добавлением дополнительного функционала, к примеру, многопользовательского режима работы приложения с возможностью разграничения прав пользователей, отправкой e-mail при обнаружении неполадок в доменной среде.
Список литературы 1. Бланшет Ж. QT4 программирование GUI на С++. Второе издание / Ж. Бланшет, М.
Саммерфилд — Кудиц-Пресс, 2008. — 738 с.
2. Введение в протокол облегченного доступа к каталогам [Электронный ресурс] – Режим доступа: http://support.microsoft.com/kb/196455/ru 3. Samba[Электронный ресурс] – Режим доступа: https://wiki.samba.org/index.php/Samba 4. Головач В.В. Дизайн пользовательского интерфейса / В.В. Головач – 2001. - 141с.
ПРОБЛЕМА СКЕЛЕТНОЙ РЕКОНСТРУКЦИИ ПРОИЗВОЛЬНЫХ БИОЛОГИЧЕСКИХ И
МЕХАНИЧЕСКИХ ОБЪЕКТОВ В СИСТЕМАХ КОМПЬЮТЕРНОГО ЗРЕНИЯ
Есипенко С.П. – аспирант, Крючкова Е.Н. – к.ф.-м.н., профессор Алтайский государственный технический университет (г. Барнаул) Одной из важнейших проблем современного компьютерного зрения является моделирование движения живых существ и, в частности, человека. С ней приходится сталкиваться при проектировании самых различных систем и устройств. На данный момент, в большинстве случаев обходятся грубыми методами и узкоспециализированными решениями. Но с развитием техники растет потребность в более точных и универсальных подходах к решению данной проблемы.Очень часто, для эффективного изучения некоторого объекта или процесса достаточно выделить его ключевые характеристики и сфокусироваться на них. Такой характеристикой для большинства движущихся живых существ является скелет. Под скелетом здесь подразумевается упрощенная модель реального скелета, в которой кости представляются отрезками. Зная только расположение скелета объекта в различные моменты времени, можно достаточно точно определять, что делает объект, а также предсказывать его положение в пространстве.
Проблема скелетной реконструкции Скелетная реконструкция изучается достаточно давно. Есть и коммерческие разработки[1,2]. Однако зачастую они слишком дороги и могут применяться лишь в специально оборудованных помещениях и с использованием специализированной техники.
С другой стороны, с ростом вычислительных мощностей, появляется возможность, применяя сложные математические методы, использовать обычные камеры или относительно дешевые датчики глубины для анализа движения и реконструкции скелета. А это, в свою очередь, открывает широкие перспективы для развития таких направлений, как дополнительная реальность, автоматическое управление автомобилем, видеонаблюдение и безопасность, компьютерная графика и анимация, игровые и развлекательные устройства и другие.
Несмотря на то, что уже разработаны достаточно перспективные подходы для решения проблемы скелетной реконструкции и анализа движения [3,4], их применение на практике остается под вопросом. Готовых реализаций и решений очень мало, причем многие из них анализируют только движение человека (например, [5]).
Прежде чем рассматривать возможные подходы скелетной реконструкции, необходимо сформулировать задачу. В общем виде, дана видеопоследовательность, на ней необходимо выделить объект, определить его структуру скелета, и для каждого кадра последовательности определить пространственную конфигурацию костей. Скелет представляет собой набор отрезков в пространстве. Отрезки могут соединяться только в концевых точках. Если рассматривать скелет в виде графа, в котором ребрами являются кости, а вершинами – точки их соединения, то он всегда связный. Кроме того, если запретить в данном графе циклы (это позволительно для живых существ), то в результате, скелет можно представить в виде дерева (обычно корню соответствует некоторый базовый сустав).
Полученный скелет и будет решением задачи.
Конкретная постановка задачи зависит от типа входных данных (последовательность с одной камеры, с нескольких произвольных камер, с нескольких синхронизированных камер, с камеры и датчика глубины), а также способа оценки степени соответствия полученного скелета реальному скелету объекта.
Стоит отметить, что различные механические системы (роботы, строительные краны и другие) тоже могут моделироваться набором отрезков, и для них также можно решать задачу скелетной реконструкции.
Алгоритмы и методы решения Если проанализировать современные подходы для скелетной реконструкции, то можно выделить несколько групп.
В первую входят решения, основанные на маркерах. Это наиболее простой подход, заключающийся в том, что к объекту прикрепляются специальные высококонтрастные пометки-маркеры, которые легко выделяются и идентифицируются на изображении. Обычно такие маркеры помещают на суставы или другие ключевые точки объекта. При использовании многокамерных конфигураций или датчиков глубины, очень просто отследить положение в пространстве отдельных суставов, и соответственно, восстановить конфигурацию костей объекта. Такие подходы применяются в современных коммерческих системах захвата движения (motion capture). Они обеспечивают хорошую точность, достаточно устойчивы и не требуют слишком сложных программных комплексов, однако для применения в обычных условиях не подходят. В некотором роде, к данным методам можно отнести решения, основанные на поиске лица [6] или других ключевых частей тела (кисти, ладони). Выделив область лица, можно предположить, где буде расположено туловище, затем руки и ноги. К сожалению, данные методы хоть и просты в реализации, слишком ограничены (человек должен смотреть в камеру) и для серьезного применения не подходят.
Вторая группа, развивает идеи первой, но использует более универсальные подсказки, такие как текстура, цвет, углы и ребра, шаблоны и другие. Эти подходы более универсальны, но все же, каждый из этих методов работает только при определенных условиях. Так, например, методы, основанные на выделении участков с кожей, перестают работать при сильном изменении освещения.
Третью группу составляют методы, основанные на вероятностных моделях. В них, конфигурация костей описывается вектором случайных величин (положения в пространстве корневого сустава, угловые смещения костей). Для них определяется распределение вероятности, которое пересчитывается каждый кадр с учетом данных выделенных из текущего изображения. К сожалению, движение человека или других живых существ, является достаточно сложным процессом, поэтому пересчет распределения вероятности параметров модели выполняется с помощью специальных техник. В основном используется Particle Filtering [3] и ее модификации, Particle Swarm Optimization [4] и другие. На данный момент, вероятностные методы являются наиболее перспективными для скелетной реконструкции. Они могут применяться как для многокамерных конфигураций [4], так и для изображения с одной камеры [3].
Список литературы 1. Organic Motion [Электронный ресурс]: – Режим доступа: http://www.organicmotion.com.
2. iPi Soft [Электронный ресурс]: – Режим доступа: http://ipisoft.com.
3. Sidenbladh, H. Stochastic tracking of 3D human figures using 2D image motion [Текст] / H.
Sidenbladh, M. Black, D. Fleet // ECCV 2000. – 2000. – С. 702-718.
4. John, V. Markerless human articulated tracking using hierarchical particle swarm optimization [Электронный ресурс] / V. John, E. Trucco, S. Ivecovic // Image and Vision Computing. – 2010. – Режим доступа: http://dx.doi.org/10.1016/j.imavis.2010.03.008.
5. Human Motion Imitation [Электронный ресурс]: – Режим доступа: http://humim.org/tracker.
6. Siddiqui, M. Robust real-time upper body limb detection and tracking [Электронный ресурс] / M. Siddiqui, G. Medioni // VSSN '06. – 2006. – Режим доступа:
http://iris.usc.edu/outlines/papers/2006/siddi-medioni-vssn06.pdf.
РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
ФОРМИРОВАНИЯ И ИСПОЛНЕНИЯ ДОГОВОРОВ ПОСТАВКИ
(НА МАТЕРИАЛАХ ФИРМЫ ООО «АЛЕЙРОН»)
Зимонина А.В. – студент, Астахова А.В. – к.э.н., профессор Алтайский государственный технический университет (г. Барнаул) Фирма ООО«Алейрон» занимается переработкой сырья и поставкой готового зерна заказчикам. Одним из базовых документов е деятельности является договор поставки. Основные работы по формированию договора и учтных документов принадлежат менеджеру по продажам. Менеджер по продажам принимает заказ, формирует договор согласовывает его с директором фирмы и представителями фирмы заказчика. После того как договор вступил в стадию исполнения, менеджер по продажам занимается формированием учтных документов. Формирование документов проводится на основе их шаблонов, ввод информации в которые осуществляется вручную, что приводит к временным затратам и замедляет процесс предоставления документов заказчику. Поиск информации по составленным договорам осуществляется либо просмотром отдельных документов, либо через обращение к бухгалтерии фирмы. Автоматизация данных задач позволит ускорить процессы формирования и исполнения договоров поставки.Существующие решения сторонних разработчиков такие как DocsVision 3.6 [3] и система «Парус» [4] являются интегрированными в огромные программные комплексы, имеют большие базы данных и очень много избыточной информации, все это лишь путает пользователей. А так же в данных разработках отсутствует система гибкого поиска информации, что осложняет процесс анализа информации и дальнейшего планирования поставок.
Цель дипломного проектирования - разработка и создание программного обеспечения для формирования и исполнения договоров поставки предприятия ООО «Алейрон».
Программа должна обладать данными функциями:
Создание, хранение и доступ к справочникам предприятия.
Формирования договора и спецификаций к нему.
Формирование исполнительных документов (ТТН, счт на оплату, счт-фактура, акт исполнения работ).
Одной из основных целей разработки является предоставление пользователю удобной работы с данными хранящимися в программе. Для этого необходимо разработать систему гибкого и жсткого поиска. Жсткий поиск предоставляет информацию из базы данных на основе заранее заданных (составленных) запросов, например: Спецификации договора с указанным пользователем номером. Гибкий поиск позволит пользователю самостоятельно выбирать параметры поиска, и задавать их значения для фильтрации данных.
Для достижения данной цели необходимо было решить следующие задачи:
Изучение выбранную предметную область.
Проектирование и реализация базы данных.
Разработка интуитивно понятного интерфейса и его реализация.
Разработка и реализация системы жсткого и гибкого поиска.
Отладка проекта на подмножестве реальных данных заказчика.
Разработка технологической документации по эксплуатации системы.
В результате работы была разработана база данных для формирования, хранения и исполнения договоров поставки, включающая в себя информацию справочников:
Сырь - необработанная крупа, определнной культуры которая определяет процесс Зерно - крупа полученная в результате обработки и очистки крупы от примесей;
- ГОСТ-ов:
Стандартов обработки сырья, а так же определяют итоговый объм крупы после переработки;
- Контрагентов;
- Банков;
- Городов;
- Единиц измерения.
Информацию для ведения журнала договоров и формирования учтных документов:
- Счт-фактура;
А так же был реализован удобный интерфейс для внесения, просмотра и поиска необходимых данных.
Для удобства анализа информации и формирования отчтов был создан поиск по жстким запросам, таким как:
1. Список договоров поставки указанного сырья за определнную дату 2. Список спецификаций относящихся к определнному договору 3. Итоговая стоимость переработки сырья по определнному договору 4. Итоговая стоимость (или объмы сырья) переработки сырья поставленного определнным заказчиком – может использоваться для установления является ли заказчик постоянным клиентом, и возможно ли ему предоставление определнной скидки на стоимость переработки 5. Список договоров, контрагенты которых пользуются определнным банком 6. Список договоров заключнных в определнном городе – в дальнейшем развитии фирмы может использоваться как определение наиболее развитого и актуального для заказчиков филиала 7. Список ТТН, счт-фактур, счетов на оплату относящихся к определнному договору 8. Итоговая стоимость переработанного сырья за определнный период 9. Список договоров по определнному зерну за период 10. История расценок на переработку установленных для определнного заказчика за Из результатов поиска пользователю по двойному клику предоставляется возможность перехода к соответствующей таблицы данных отсортированной в соответствии с выбранным запросом.
Кроме жстких запросов была разработана логика формирования и выполнения гибких запросов, которая состоит из данных задач:
Описание логики поиска Описание структуры выходных данных Выбор варианта хранения сформированного запроса Выполнение запроса и выгрузка результата для последующего анализа (в MS Excel).
Логика поиска определяется одним или несколькими параметрами(критериями).
Каждый параметр представляет собой отношение, определяющее допустимые значения одного из отобранных полей, которыми ограничивается результат поиска. Если критериев несколько, то они соединятся между собой логическим условием «И». Это означает, что в результаты поиска будут включена информация, одновременно удовлетворяющая всем введнным параметрам(критериям).
В результате создания данного ПО должен ускорится процесс формирования и исполнения договоров поставки, предоставления необходимых документов заказчику, поиска необходимой информации.
Список литературы 1. Гражданский кодекс РФ часть вторая 2. Ананьев П.И., Кайгородова М.А. Основы баз данных. Учебное пособие/ АлтГТУ им.
И.И. Ползунова. - Барнаул: 2010. -189 с. - ил.
3. Описание комерческого ПО DocVision: http://www.docsvision.com/kupit/dv-catalog/dv5.html 4. Описание комерческого ПО «Парус»: http://www.parus.com/solutions/corporate/system/
АДАПТИВНОСТЬ КЛАССИФИКАЦИИ ИЗОБРАЖЕНИЙ НА ОСНОВЕ
АВТОМАТИЧЕСКОЙ ГЕНЕРАЦИИ ОБУЧАЮЩЕЙ ВЫБОРКИ
Казаков М.Г. – аспирант, Крючкова Е.Н. – к.ф.-м.н., профессор Алтайский государственный технический университет (г. Барнаул) Введение Задачи компьютерного восприятия изображений представленных в растровом виде являются вероятно наиболее сложными среди задач компьютерного зрения. При этом часть задач из этой области можно считать в той или иной степени разрешенными, например задачи локализации конкретного объекта или же задачи поиска экземпляров объекта. Другая область задач – задачи классификации изображений остаются крайне тяжелыми для машинного решения [1]. Это связано, со многими факторами, в первую очередь с непониманием принципов работы восприятия человека. Так же задача усложняется возможными нечеткими трактовками принадлежности изображений классам и пересечением классов между собой, вплоть до включения.В данной статье рассматривается подход к классификации изображений, опирающийся на представление изображений в виде набора многомерных векторов – дескрипторов локальных визуальных особенностей, обычно инвариантных к определенному классу трансформаций изображений [2]. При этом подразумевается наличие обучающей выборки изображений, соответствующим определенным классам. Наиболее эффективным на сегодняшний день считается применение этапа квантования, которое представляет весь спектр дескрипторов из обучающей выборки в виде набора так называемых визуальных слов (Bag Of Words), для чего используется кластеризация [3]. На этом этапе многомерные вектора фактически трансформируются в одномерные индексы. Общая схема классификации при этом может быть представлена в виде следующих шагов:
Извлечение дескрипторов локальных визуальных особенностей из набора обучающих изображений.
Кластеризация дескрипторов по заданному количеству визуальных слов.
Для каждого дескриптора производится поиск ближайшего центра кластера, после чего многомерный вектор заменяется на индекс этого центра (визуального слова).
Изображения обучающей выборки представляются в виде нормализованных гистограмм частоты появления визуальных слов в них.
Основываясь на представлении обучающей выборки классов как множества многомерных векторов – гистограмм, производится обучение классификаторов, например используя метод опорных векторов.
Анализируемое изображение аналогичным образом представляется в виде многомерного вектора – гистограммы.
Исходя из результата работы классификаторов, принимается решение об отнесении анализируемого изображении к тому или иному классу.
Особую важность в этом методе представляет обучающая выборка. С одной стороны, количество изображений в каждом классе должно быть достаточным для составления количественных характеристик класса, с другой стороны на связность изображений между собой накладываются определенные ограничения. Если изображения представляющие класс визуально разрозненны, то для классификатора проблематично подобрать достаточно четко описывающую их модель. Если же изображения чрезмерно похожи, по уменьшается охват классификатора, и увеличивается процент ложноотрицательных результатов работы классификатора. При этих сложностях, обычно обучающая выборка составляется в ручном режиме, что осложняет перенастройку системы под новые требования – в первую очередь при появлении новых классов.
Предлагаемый подход С учетом объема изображений, доступных в Интернете, возможны попытки автоматизации процесса формирования обучающей выборки путей использования поисковых систем. Рассматриваемой поисковой системой, по причине наибольшей распространенности, была выбрана Google Custom Search. Традиционное количество обучающих изображений варьируется в диапазоне до 50, таким образом текущий лимит Google Custom Search на 100 первых элементов поисковой выдачи вполне укладывается в требуемые характеристики. Задача сбора обучающей выборки несколько упрощается тем, что имеется возможность предварительно фильтровать поисковую выдачу, используя поверхностный анализ изображений проводимый поисковой системой. Так, например, доступна фильтрация по типу формата изображения, диапазону размеров и содержимому – в данном случае интерес представляют только фотографии (синтетические изображения, например так называемый clipart, довольно плохо поддаются анализу с использованием дескрипторов локальных особенностей).
Для оценки качества автоматически полученной обучающей выборки можно использовать метод confusion test, заключающийся в перекрестном анализе изображений представляющих классы с различными классификаторами. При этом для каждого изображения вычисляется наиболее близкий класс исходя из результата работы классификаторов, и составляется confusion matrix, в которой по горизонталям идут фактические изображения классов, а по вертикалям изображения, по которым была предсказана принадлежность к классу. В случае идеально работающих классификаторов confusion matrix должна представлять собой диагональную матрицу. В таблице 1 представлен результат такого перекрестного анализа, при этом классификаторы обучались на изображениях из каждого класса, а для анализа были использованы по 40 изображений классов таким образом, чтобы они не пересекались с уже использованными для обучения. Из полученных данных видно, что подобная обучающая выборка вполне может использоваться для задач классификации изображений. Влияние количества изображений используемых для обучения классификаторов на число верных срабатываний показано в таблице 2.
Стоит отметить, что переход от абстрактного набора изображений, относящихся к определенному классу название которого не имеет прямой связи с содержимым, к генерации набора опираясь на название класса в качестве поискового запроса, позволяет использовать дополнительные механизмы при классификации. Например, появляется возможность построить семантические связи между классами, исходя из его названия и расположения соответствующего понятия в семантическом графе. На примере графа, представленного в [4], была построена модель верификации результатов классификации.
Заключение Использование автоматически полученной обучающей выборки способно решить часть проблем связанных со сложностью перенастройки системы классификации под изменившиеся требования.
Список литературы 1. Szeliski R. Computer Vision: Algorithms and Applications. - Springer-Verlang New York, 2. Lowe D. G. Object Recognition from Local Scale-Invariant Features. - The Proceedings of the Seventh IEEE International Conference on Computer Vision, 1999.
3. Csurka G., Dance, C., Fan, L., Willamowski, J., Bray, C. Visual categorization with bags of keypoints // Workshop on statistical learning in computer vision, 2004.
4. Крайванова В.А., Кротова А.О., Крючкова Е.Н. Построение взвешенного лексикона на основе лингвистических словарей. - Материалы Всероссийской конференции «Знания – Онтологии - Теории», 2011.
АЛГОРИТМ ОБНАРУЖЕНИЯ АВТОМОБИЛЕЙ НА ОСНОВЕ ВЫЧИТАНИЯ ФОНА ДЛЯ
ВИДЕОНАБЛЮДЕНИЯ ЗА ПЕШЕХОДНЫМИ ПЕРЕХОДАМИ
Колосовский М.А. – аспирант, Крючкова Е.Н. – к.ф.-м.н., профессор Алтайский государственный технический университет (г. Барнаул) В последнее время благодаря широкому классу решаемых задач активно развиваются технологии видеонаблюдения. Особенно заметны системы интеллектуального видеонаблюдения, способные в автоматическом режиме отслеживать ситуацию и минимизировать человеческие ресурсы для обработки информации. Примером систем интеллектуального видеонаблюдения являются системы автоматической фиксации нарушений правил дорожного движения, способные фиксировать такие нарушения, как превышение скорости, пересечения сплошной или стоп-линии, проезд на красный свет. В данной статье рассматривается задача обнаружения нарушений на нерегулируемом пешеходном переходе, которая является принципиально более сложной, чем обнаружение упомянутых видов нарушений. Это связано со сложностью одновременного сопровождения на видео автомобилей и пешеходов, а также со сложностью обнаружения нарушения по траекториям участников движения.Ключевыми частями интеллектуальной системы видеонаблюдения являются алгоритмы компьютерного зрения, способные находить и сопровождать на видео участников движения.
Их работа осложняется рядом факторов, среди которых:
Неравномерность освещения;
Необходимость работы в режиме реального времени;
Перекрытие объектов друг другом;
Шумы камеры и погодные условия (дождь, туман, снег и другие).
В этой статье описывается алгоритм для обнаружения автомобилей. Обнаружение автомобилей в данной задаче видеонаблюдения имеет ряд особенностей, которые следует учесть для построения наиболее подходящего алгоритма:
Автомобили всегда видны фронтально или под небольшим углом;
Траектории движения автомобилей подчинены ряду простых шаблонов;
В наблюдаемой ситуации присутствуют два вида участников движения (автомобили и пешеходы), принципиально отличающиеся по внешнему виду.
Проведя анализ используемых подходов для обнаружения автомобилей, было выявлено, что использование метода вычитания фона (background subtraction) является наиболее часто используемым подходом благодаря своей простоте реализации и быстродействию [1Алгоритмы на основе вычитания фона строят модель фона (изображение статических объектов сцены), сравнивают ее с текущим кадром, получая области, принадлежащие движущимся объектам. Стоит заметить, что такие алгоритмы чувствительны к шумам камеры, перепадам освещения, их работу нарушает появление тени от объектов, а также похожесть объекта и фона. Поэтому для верификации найденных областей используют дополнительные алгоритмы [5-7].
На данный момент мы остановились на алгоритме только на основе вычитания фона, так как области, получаемые методом вычитания фона и соответствующие автомобилям, существенно больше областей, соответствующих пешеходам, поэтому размер области является хорошим признаком для классификации этой области. Предлагаемый алгоритм Работа выполнена при поддержке Фонда содействия развитию малых форм предприятий в научнотехнической сфере (госконтракт №0068 ГУ1/2013) поддерживает модель фона (рисунок 1а) как усреднение 200 последних кадров. Кадр видео (рисунок 1б) сравнивается с текущей моделью фона, пиксели с разницей выше заданного порога формируют маску активных пикселей (рисунок 1в). Далее сканирующее окно заданного размера находит такие позиции, где внутри окна оказывается не менее 90% активных пикселей. Среди таких позиций выделяются локальные максимумы по числу активных пикселей. Эти максимумы считаются найденными объектами (рисунок 4г). Кроме того, порядок сканирования строится, учитывая специфику наблюдаемой сцены. Данные для тестирования алгоритма взяты из [8].
Рисунок 1 – а) Построенная модель фона; б) текущий кадр; в) маска активных В статье был предложен алгоритм обнаружения автомобилей, основанный на методе вычитания фона, для видеонаблюдения за пешеходными переходами с целью контроля соблюдения правил дорожного движения. Алгоритм справляется с задачей обнаружения автомобилей, однако имеет ряд существенных недостатков, связанных с невозможностью обрабатывать перекрытия автомобилей друг другом и связанных с чувствительностью к теням и неравномерности освещения. Поэтому дальнейшим направлением работы будет усиление предложенного детектора алгоритмом, использующим в качестве признаков объекта не только размер активной области, но и другие признаки.
Список литературы 1. Jyothi kiran M., Roy K. A Video Surveillance System for Speed Detection in Vehicles.
International Journal of Engineering Trends and Technology. 2013. Volume 4, Issue 5, paper №25. Pp. 1437-1441.
2. Celil O., Fatih C. Automatic traffic density estimation and vehicle classification for traffic surveillance systems using neural networks. Journal of Mathematical & Computational Applications. 2009, Vol. 14, Issue 3, pp. 187-196.
3. Norbert Erich B. Classification of vehicles for urban traffic scenes. PhD thesis, Kingston University. 2010.
4. Coifman B, Beymer D., McLauchlan P., Malik J. A real-time computer vision system for vehicle tracking and traffic surveillance. Journal of Transportation Research Part C: Emerging Technologies. Volume 6, Issue 4, August 1998, Pages 271–288.
5. Negri P., Clady X., Prevost L. Benchmarking haar and histograms of oriented gradients features applied to vehicle detection. Fourth International Conference on Informatics in Control, Automation and Robotics, Robotics and Automation. France, May 9-12, 2007. Pp.
359-364.
6. Sasidharan S., Kumar K. Vehicle Detection in Images using SVM. International Journal of Advanced Electrical and Electronics Engineering. 2013. Volume 2, Issue 6, pp. 62-68.
7. Chiu C.-C., Ku M.-Y., Wang C.-Y. Automatic Traffic Surveillance System for Vision-Based Vehicle Recognition and Tracking. Journal of Information Science and Engineering. 2010.
Volume 26, pp. 611-629.
8. Leibe B., Schindler K., Van Gool L. Coupled Detection and Trajectory Estimation for MultiObject Tracking // 2007 IEEE 11th International Conference on Computer Vision. Rio de Janeiro, Brazil. October 2007. P. 1–8.
РАЗРАБОТКА СИСТЕМЫ УПРАВЛЕНИЯ БАЗОЙ МЕТАДАННЫХ
ГЕОИНФОРМАЦИОННОГО ИНТЕРНЕТ-ПОРТАЛА ИВЭП СО РАН
Коновалова К.В. – студент, Бубнова Н.Д. – ст. преп., Ловцкая О.В. – с.н.с.* Алтайский государственный технический университет (г. Барнаул) Институт водных и экологических проблем СО РАН* (г. Барнаул) Метаданные – структурированные данные, которые описывают характеристики объектов-носителей данных, способствующие идентификации, обнаружению, оценке и управлению этими данными [1]. Метаданные используются в различных предметных областях и информационных технологиях: базы данных, технологии текстового поиска, вебсервисы, библиотечное дело, медицина, геоинформатика и др. Широкое распространение метаданных говорит об их важности и ценности для общества. Метаданные помогают документировать данные, структурировать, а также создавать механизмы по поиску и идентификации данных.Институт водных и экологических проблем (ИВЭП) Сибирского отделения Российской академии наук был основан 1 сентября 1987 года на базе лабораторий ряда институтов Сибирского отделения РАН, проводивших исследования природно-ресурсной и экологической направленности. Организация Института была вызвана необходимостью проведения фундаментальных исследований по изучению процессов и явлений в окружающей среде, а также оценки состояния водных ресурсов и решения проблем сбалансированного природопользования [2].
За время существования института в научных подразделениях было накоплено большое количество разнообразной информации о проводимых исследованиях. В связи с немалым объемом информации и трудностью проведения поиска среди разрозненных данных возникла потребность в структуризации и стандартизации с использованием международных стандартов метоописания, а также в создании единой базы данных института.
На начальном этапе был проведен отбор информации, включаемой в базу метаданных.
На основе международных и отечественных стандартов (ISO 19115:2003 «Geographic information Metadata», ГОСТ Р 52573-2006 «Географическая информация. Метаданные») был разработан единый образец файла метазаписи, который включает в себя следующие поля:
1. Заголовок 2. Аннотация 3. Код классификатора.
4. Ключевые слова 5. Производители данных 6. Персоны, связанные с данными 7. Первая публикация 8. Носитель информации 9. Дата создания данных 10. Формы разрешений на данные 11. Авторы метаданных 12. Вложенная ссылка (характеристика типа набора данных текст, снимок, HTML и т.п., собственно ссылка имя прилагаемого файла, ссылка на источник в Интернет и т. п.) 13. Координаты 14. Географическая привязка Файлы метаданных могут содержать не все поля, но в целом структура метазаписи едина, и не нарушена.
Следующий этап в разработке единой базы института – реализация интерфейса доступа к метаданным.
На данном этапе первым делом был выбран способ классификации метазаписей.
Географические данные, накопленные за время существования ИВЭП, можно классифицировать используя линейную классификацию, когда отсутствует как таковая классификация и все данные располагаются независимо друг от друга. Чтобы структурировать данные можно применить классификации по подразделениям института, по водным бассейнам, по водным объектам, по административным районам, по субъектам федерации, по среде исследования, по теме исследования и т.д. Так же можно организовать иерархическую классификацию, когда заданное множество делится на подмножества, образуя древовидную структуру.
Каждая из классификаций имеет свои недостатки:
1. Линейная слишком проста и представляет собой длинный список без возможности 2. Классификации, основанные на каком-либо одном общем критерии для группы, слишком не однозначны и имеют множество пересечений;
3. Иерархическая классификация хороша в своей простоте и структурированности, но она не отражает полный перечень возможных подклассификаций геоданных.
Наиболее подходящей классификацией для структурирования географических данных является фасетная классификация. Фасетная классификация – классификация, дающая возможность классифицировать объекты одновременно по нескольким различным признакам [3]. Преимущества этого вида классификаций в том, что они облегчают многоаспектное классифицирование объектов, позволяя воедино собрать все аспекты рассмотрения. Фасетное классифицирование легче поддается изменениям при введении новых понятий, допускает большую глубину деления. Недостаток фасетной системы классификации заключается в сложности построения (т.к. необходимо учитывать все многообразие классификационных признаков).
Структурно фасетную классификацию можно представить в следующем виде [4]:
Здесь под фасетом подразумевается признак, по которому в многоаспектной классификации осуществляется деление.
В качестве базы данных для хранения классификаций выбрана графовая база данных Neo4j [5], представляющая собой разновидность баз данных с реализацией сетевой модели в виде графа и его обобщений. Основные элементы – узлы и отношения. Фасетная классификация географических объектов, а так же связанных с ними проектов, слоев и т. п., наполнена семантикой и графовая база данных Neo4j позволяет осуществить все необходимые функции. Каждый из узлов в базе – узел классификации, каждое отношение – связь одного узла классификации с другим, совокупность отношений – отдельная классификация. Каждое отношение может быть нагружено своим смыслом, каждый узел – своими свойствами. В системе могут существовать два узла с одинаковым названием, но несущие совершенно различный смысл, т.к. у них свои связи и свои свойства. Neo4j также позволяет осуществлять поиск по необходимым параметрам.
Интерфейс доступа к базе данных реализуется на языке Java с использованием вебфреймворка Spring MVC [6]. Выбор данных инструментов позволяет получать доступ к системе, имея только браузер, нет необходимости в каких-либо дополнительно устанавливаемых компонентах. Отсутствует привязка к конкретной операционной системе.
Архитектура системы на основе паттерна MVC (модель-представление-контроллер) [7] является очень гибкой: интерфейс всегда может быть заменен альтернативной реализацией;
не затрагивая вид, можно изменить поведение системы, для этого достаточно заменить контроллер; модель данных не зависит от представления.
Система состоит из двух частей:
1. Интерфейс для администрирования базы метаданных. Он содержит инструменты для добавления и изменения классификаций.
2. Интерфейс пользовательской части. Содержит инструменты для различного поиска метаданных и их отображения.
Создание единой базы метаданных позволит собрать воедино, структурировать и сделать более доступной информацию, собранную в результате многолетних исследований подразделениями Института водных и экологических проблем.
Список литературы 1. Вязилов, Е.Д. Современные подходы по созданию метаданных [Текст] / Е.Д. Вязилов, А.Е. Кобелев // Современные проблемы дистанционного зондирования Земли из космоса: Физические основы, методы и технологии мониторинга окружающей среды, потенциально опасных явлений и объектов: сб. статей. – Москва, 2010. – С. 194-204.
2. Институт водных и экологических проблем СО РАН [Электронный ресурс] – Режим доступа: http://www.iwep.ru/ru/ 3. Гендина Н.И. Неиерархические классификации [Презентация].
4. Автоматизированные информационные технологии. [Электронный ресурс]. – Режим доступа: http://fakit.narod.ru/uch2003/p4_2_1_2.html 5. Neo4j. [Электронный ресурс]. – Режим доступа: http://www.neo4j.org/ 6. Spring Framework. – [Электронный ресурс]. – Режим доступа:
http://ru.wikipedia.org/wiki/Spring_Framework 7. Model – View – Controller. – [Электронный ресурс]. – Режим доступа:
http://ru.wikipedia.org/wiki/Model-View-Controller
ЗАЩИТА ИНФОРМАЦИИ НА МОБИЛЬНЫХ УСТРОЙСТВАХ ПОД УПРАВЛЕНИЕ ОС
ANDROID В КОРПОРАТИВНОЙ СРЕДЕ
Корякин Н.А. – студент, Третьяков И.В. – ведущий разработчик мобильных приложений* Алтайский государственный технический университет (г. Барнаул) Использование персональных устройств на рабочих местах обязывает корпорации разрабатывать и использовать технологии, которые обеспечивают информационную и экономическую безопасность, что является актуальной задачей. Необходимо контролировать персональные устройства и обеспечивать их безопасное использование, при этом нужно учитывать интересы владельцев.Для эффективного решения данной задачи необходимо уделять должное внимание современному технологическому развитию, возможностям мобильных устройств, а также безопасной работе с конфиденциальной информацией.При решении задач подобного класса наиболее используемым является подход «Bring-Your-OwnDevice» (BYOD). Корпорации используют BYOD как способ привлечения и удержания талантов. Ограничения в использовании персональных устройств отрицательно отражаются на показателях качества работы сотрудников, т.к. для них это более удобно.Личное оборудование зачастую более высокопроизводительно и эффективно, чем то которое предоставляет организация, что подтверждает необходимость внедрения технических решений рассматриваемой задачи.Рисунок 1 – График использования мобильных устройств на рабочих местах С ростом числа приложений, контента и данных, доступ к которым может осуществляться с самых разнообразных устройств, становится жизненно необходимым внедрение системы управления мобильными устройствами MobileDeviceManagement.
MDMвключает в себя центрально-ориентированную систему функций по защите и управлению данными и приложениями, а также центрально-ориентированную систему информационных функций. Необходим менеджмент всего жизненного цикла устройств, и IT-персонал несет полную ответственность за мобильные устройства, находящиеся в собственности компании, в том числе за настройку их аппаратной и программной части, поддержку приложений и соблюдение обязательств предприятия в их отношении. Если же сотрудникам разрешено использование личных устройств на местах (BYOD), тонеобходимо разделять обязанности, а также определить совместную ответственность предприятия и пользователя, что должно быть надлежащим образом организовано, доведено до сведения и проконтролировано.
Symantec Mobile Management и McAfee Enterprise Mobile Management – одниизсамыхраспространенных MDM. Они обеспечивают защиту данных, а также управление мобильными устройствами. Несмотря на многочисленные позитивные характеристики современных MDM, многие компании предпочитают их не использовать.
Основной из причин такого решения является высокая цена гарантированной безопасности.
Внедрение такой системыпредполагает установку на устройство специального набора программного обеспечения, с помощью которого можно подключаться к корпоративным сервисам. В этом случае на мобильном устройстве фактически создается защищенная среда, через которую пользователь получает доступ к корпоративным данным. При этом ему приходится осваивать новый набор приложений, который входит в состав самого решения.
На устройстве создаются две рабочие среды: персональная, доступ к которой имеет пользователь, и корпоративная, контролируемая ИТ-администраторами компании, при этом администратор не имеет доступа к персональной части устройства. Программное обеспечение мобильного клиента, а также постоянная поддержка связи с корпоративной сетью сильно нагружают устройства, поэтому их производительность снижается, и они теряют свою ценность для сотрудников организации.
В настоящее время ведется разработкапрограммного обеспечения описанного класса.
Данное техническое решение обладает низкой стоимостью и обеспечивает надежность работы, возможность обработки критических ситуаций и при этом не требует больших ресурсов вычислительной мощности. Возможности мобильного устройства зависят от его текущего местоположения, времени суток и должности сотрудника.Система управления мобильными устройствами централизованаи гарантирует информационную безопасность для организации, которая ее использует. Конечный пользователь должен быть заинтересован в возможностях MDM, поэтому влияние корпоративной среды устройства на его персональную среду минимально. Для настройки, контроля и сопровождения устройств реализована консоль администратора, с помощью которой можно сконфигурировать оборудование сотрудников, а также создать правила использования персональных устройств и контролировать нарушения этих правил. Система обладает удобным для пользователя функционалом - потерянное или украденное устройство всегда можно заблокировать или же обнаружить с помощью запроса последних известных координат. Основным недостатком программного продукта является отсутствие кроссплатформенности клиентского приложения, которое работает только под операционной системой Androidминимальной версии 2.2.
Список литературы 1. Соколов А.В., Шаньгин В.Ф. Защита информации в распределенных корпоративных сетях и системах. ДКМ Пресс – Администрирование и защита. ISBN 5-94074-172-Х;
2. Шифрование и защита данных в GoogleAndroid. «ТехноМир».– Портал [Электронный ресурс]. [2005-2013]. – Режим доступа: http://www.mobimag.ru/Articles/5046.
3. Малюк А.А. Информационная безопасность: концептуальные и методологические основы защиты информации. Москва. – Горячая линия – Телеком. 2004.
4. ForeScout Technologies Inc. NetworkAccessControl [Электронныйресурс] - 2014. – Режимдоступа: https://www.forescout.com/solutions/network-access-control/ 5. RemotiumVirtualMobilePlatform (VMP) [Электронныйресурс] - 2014. – Режимдоступа:
https://www.remotium.com/#about
РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ АВТОМАТИЗИРОВАННОГО
ПОСТОЕНИЯ ГРАФИКА РАБОТЫ МАСТЕРОВ ПО ОБСЛУЖИВАНИЮ ЗАЯВОК
Костин К.В. – студент, Кантор С.А. – к.ф.-м.н., профессор, Созутов А.Е. – технический директор компании «Ритейл Сервис»* Алтайский государственный технический университет (г. Барнаул) Транспортная задача в своем классическом варианте формулируется следующим образом – необходимо найти оптимальный план перевозок продукта из пунктов наличия в пункты потребления используя заранее предопределенное количество транспортных средств.На практике в данной формулировке эта задача редко применяется, так как в каждой конкретной предметной области существуют свои собственные ограничения. Это могут быть ограничения на время транспорта в пути или ограничения на посещения некоторых пунктов некоторыми транспортными средствами.
В связи с оптимизацией деятельности компании возникла следующая задача, которую можно отнести к классу транспортных задач.
Компания занимается установкой, ремонтом и обслуживанием оборудования на объектах по всему краю и имеет представительства в некоторых населенных пунктах.
Работы, выполняемые компанией, осуществляются в соответствии с поступающими заявками, из которых следует определенный набор требований.
1. Период, то есть начальная и конечная даты выполнения заявки. Если она будет обслужена после конечной даты, то считается просроченной.
2. Перечень работ, которые необходимо выполнить, откуда можно определить примерное время, затрачиваемое на выполнение заявки.
3. Местоположение объекта, на котором необходимо осуществить работы.
4. Приоритет. Каждое установленное компанией оборудование должно проходить планово-предупредительные ремонты, поэтому существуют плановые заявки, имеющие наименьший приоритет. Наивысший приоритет имеют самые критические заявки, например поломка оборудования, влияющего на ход производства у заказчика. Могут быть не критические заявки, например перенастройка оборудования.
Обслуживанием заявок занимаются мастера. Существует базовое расписание работы мастеров, в котором определено какой мастер выезжает из на выполнение заявки из какого представительства, его продолжительность работы в каждый конкретный день.
Необходимо, имея список заявок и базовое расписание, составить график работы мастеров по обслуживанию заявок. При этом графики работы должны сравниваться в соответствии со следующими критериями:
1. количество просроченных заявок;
2. общее количество маршрутов в расписании 3. количество дней, потраченных на выполнение заявок;
4. максимальное количество мастеров, работающих в один день.
5. суммарное время работы всех мастеров.
Критерии перечислены в порядке уменьшения важности. Это означает, что из двух расписаний предпочтение отдается тому, которое лучше по i-му критерию, а по критериям 1,..,i-1 они равны.
Данная задача является NP-полной [1], поэтому за приемлемое время найти оптимальное решение невозможно. Однако, в данной постановке, оптимальное решение задачи не требуется. Это связано с тем, что в реальности точно по плану работы не могут быть выполнены: какая-то заявка будет выполняться быстрее, какая-то дольше, мастер по какойлибо причине может не выйти на работу и т.д. Поэтому поставим задачу о нахождении рационального решения за приемлемое время. Существует целый класс алгоритмов, позволяющих находить приближенное решение этой задачи, называемых эвристическими [2]. Эвристический алгоритм – это алгоритм, правильность которого в общем случае не доказана, но про который известно, что на практике он дает достаточно хорошее решение.
Для решения был выбран генетический алгоритм [3], одно из преимуществ которого – простота при его распараллеливании. Для реализации метода необходимо определить структуру организма. Это сделано следующим образом. Назовем базовыми пункты, где расположены представительства компании и из которых мастера выезжают для выполнения заявок. Пусть имеется n базовых городов, пронумеруем их от 1 до n. На практике все населенные пункты разбиваются на районы, и каждый район обслуживается только из одного базового города. Поэтому можно сделать хорошее начальное приближение к искомому решению – каждую заявку поместить в список ближайшего к ней базового города.
Поэтому разобьем множество заявок на n частей, и будем считать, что имеется массив R размерности n, где n – количество базовых городов, R[i] – список заявок, выполняемых мастерами из i-го базового города.
Пусть m – продолжительность периода, на который составляется график работ.
Определим матрицу A размерности n*m, где A[i][j] – список мастеров, которые выезжают из i-го базового города в j-ый день.
Кроме того, имеется матрица S, описывающая время перемещения мастера из одного пункта в другой, S[i][j] — время в минутах, на проезд от пункта i до пункта, j.
Теперь на основе массивов R, A и S необходимо составить расписание. Состояние мастера в какой-либо момент времени можно описать его местоположением, текущим временем работы и базовым городом. Выполняя заявку, мастер переходит из одного состояния в другое, то есть меняется его местоположение и время работы. Мастер может выполнить заявку из какого-то состояния, если в сумме текущее время работы, время проезда до места выполнения заявки, время выполнения заявки и возврат в базовый город будут меньше времени работы мастера в текущий день. Считаем, что мастера из списка А[i][j] выезжают по очереди и по очереди выполняют заявки из R[i], то есть первый мастер выполняет максимальное количество заявок, которое может выполнить, потом второй мастер максимальное количество заявок, начиная с той, которую не смог выполнить первый и т.д.
Если мастера в j-ом списке закончились, то переходим к следующему дню и аналогично составляем расписание. Таким образом, по A, R и S однозначно вычисляется расписание.
Матрица S не изменяется в время работы алгоритма. Каждый организм описывается индивидуальными массивом R и матрицей A. Поколение - набор организмов. Популяция — набор сменяющих друг друга поколений. В одной популяции на каждой итерации алгоритма строится новое поколение на основе предыдущего с использованием методов скрещивания и мутации. Скрещивание - получение организма потомка на основе двух родительских организмов, мутация — случайное изменение структуры организма.
Реализованы следующие виды скрещивания (с указанием вероятности их наступления):
Скрещивание по списку заявок, вероятность 0,7. Организм потомка принимаем равным второму организму. Выбираем случайное число i, выбираем случайный подсписок из списка R[i] первого организма и помещаем его в случайное место списка R[i] потомка. При этом некоторые заявки будут встречаться в потомке два раза, поэтому удаляем второе вхождение каждой из них.
Скрещивание по спискам мастеров, вероятность 0,3. Массив R организма потомка с равной вероятностью копируем у одного из родителей. Аналогично списки A[i][j], для любых возможных i и j, с равной вероятностью копируем у одного из родителей Были реализованы следующие виды мутации:
1. Мутация перемещения заявок между базовыми городами, вероятность 0,02. Из случайного списка заявок берем случайную заявку и перемещаем ее в случайное место случайного списка.
2. Мутация перемещения заявок внутри списка базового города, вероятность 0,4. Берем случайный список заявок, в нем случайно выбираем 2 заявки и меняем их местами.
3. Мутация реверсирования, вероятность 0,2. Берем случайный список заявок, в нем выбираем случайный подсписок и реверсируем его.
4. Мутация уменьшения количества мастеров, вероятность 0,1. Из случайного списка A[i][j] удаляем последнего мастера 5. Мутация увеличения количества мастеров, вероятность 0,1. В случайный A[i][j] добавляем мастера, который может выехать из i-го базового города в день j.
6. Мутация изменения порядка мастеров, вероятность 0,2. В случайном списке A[i][j] выбираем два случайных мастера и меняем их местами.
7. Оптимизация путем изменения порядка соседних заявок, вероятность 0,01.
Перебираем все рядом стоящие в списках заявки и меняем их местами, если расписание улучшилось, то оставляем их, иначе меняем обратно. Вероятность данной мутации очень мала потому, что она выполняется очень долго и существенно увеличивает время работы алгоритма. Данная мутация применяется к лучшим организмам популяции после каждой итерации алгоритма.
Были реализованы следующие методы параллельной работы алгоритма:
Реализован многопопуляционный параллельный генетический алгоритм - это значит, что при работе используется несколько популяций, каждая из которых обрабатывается в собственном потоке. Через некоторое количество итераций происходит обмен лучшими организмами между популяциями. Реализована работа с двумя популяциями.
На каждой итерации получения нового поколения происходит большое количество операций скрещивания. Можно заметить, что эти операции независимы, поэтому реализовано их параллельное выполнение. Так же реализовано параллельное выполнение мутаций. Эта работа осуществляется в двух потоках.
Из алгоритма составления расписания на основе организма видно, что для каждого базового города разбиение списка заявок на маршруты независимо. Реализовано параллельное вычисление расписания с использованием двух потоков.
Все представленные выше значения были подобраны в результате численных экспериментов.
При дальнейшем развитии работы планируется добавление новых условий, таких как:
учет необходимого оборудования для ремонта;
учет квалификации сотрудника для выполнения заявки.
Результаты работы алгоритма при 250 заявках, 17 мастерах и периоде планирования дней представлены в таблице:
Время работы всех мастеров, в минутах 12815 13162 12773 12210 Список литературы 1. Michael R. Garey. Computers and Intractability: A Guide to the Theory of NP-Completeness. / Michael R. Garey, David S. Johnson.- NewYork: W.H. Freeman and Company 1979. - 339 p.
2. Michalewicz Z. How to solve it. Modern heuristics. / Michalewicz Z., Fogel D.B Berlin. Springer, 2004. – 155 p.
3. Francisco B. Pereira. Bio-inspired algorithms for the vehicle routing problem / Francisco B.
Pereira, Jorge Tavares. - Coimbra: Springer, 2008 – 221 p.
СОЗДАНИЕ УНИВЕРСАЛЬНОЙ СРЕДЫ ДЛЯ ПРОВЕДЕНИЯ ВЕБИНАРОВ
Кронберг И.А. – студент, Старолетов C.М. – к.ф.-м.н., ст. преп.Алтайский государственный технический университет (г. Барнаул) Постановка и анализ проблемы Современные системы дистанционного (электронного) обучения можно разделить на две категории:
1. Системы, обеспечивающие асинхронный характер взаимодействия обучающихся и преподавателей. Для таких систем характерны такие функции как:
1.1. Создание и управление электронными образовательными курсами.
1.2. Проведение лабораторных работ, контрольных опросов и их оценка.
2. Системы, обеспечивающие синхронный характер взаимодействия обучающихся и преподавателей.Для таких систем характерны такие функции как:
2.1. Организация online вещания и обмена мультимедийной информацией между преподавателем и обучающимися.
2.2. Возможность коллективного выполнения заданийв режиме реального времени(collaborativenetwork).
На рынке существует сравнительно мало решений поддерживающих как асинхронные, так и синхронные способы организации занятий. Те же из них, что обеспечивают в равной степени и позволяют проводить оба типа занятий, часто имеют высокую цену приобретения и использования лицензионной копии программного комплекса.
Постановка задачи На базе результатов анализа известных систем дистанционного (электронного) обучения:
1. Определить функциональность будущей системы.
2. Подобрать инструментарий необходимый для реализации системы, на основе современных тенденций в области разработки программного обеспечения.
3. Спроектировать базу данных и составить диаграмму классов 4. Реализовать базовые функции системы:
4.1. Возможность создания и управления электронными учебными курсами 4.2. Организация online занятий и семинаров с использованием большинства доступных средств взаимодействия (текстовый чат, видео-конференция, 5. Осуществить установку и тестирование системы на удаленном хосте.
Решение Для решения поставленных задач были использованы следующие инструменты и технологии:
Symfony 2 - свободно распространяемый веб фреймворк (CMF), написанный на PHP5, базирующийся на архитектуре Model-View-Controller. Имеет поддержку множества баз данных (MySQL, PostgreSQL, SQLite или любая другая PDO-совместимая СУБД).
Информация о реляционной базе данных в проекте должна быть связана с объектной моделью.
WebRTC — интернет-протокол, проект с открытым исходным кодом, предназначенный для организации передачи потоковых данных между браузерами или другими поддерживающими его приложениями по технологии точка-точка (Peer – to - Peer) Рисунок 1 – Схема организации передачи данных Peer – to–Peer WebRTC позволяет получать медиаданные (аудио и видео) через браузер и устанавливатьсоединение между двумя и более клиентами, через которое могут передаваться обычные данные и медиапотоки.
Непосредственно при создании данного приложения была использована javascript библиотека Peer.js, которое является надстройкой надвстроенной в браузеры функциональностью WebRTCAPI (последние версии Mozilla, GoogleChrome, Opera)и обеспечивает стабильное соединение и передачу медиа-данных Созданная система состоит из двух модулей:
1. Модуль создания и управления электронными курсами;
2. Модуль для организации on-lineзанятий.
Для обеспечения создания и хранения электронных курсов была разработан и реализован при помощи Symfony2 проект базы данных.
Модуль проведения занятий включает в себя такие возможности как:
1. Создание отдельных виртуальных комнат для проведения занятий 2. Групповой текстовый чат 3. Живое видео – вещание с камеры преподавателя (при необходимости и с камеры обучаемого) 4. Интерактивная доска с возможностью рисования.
5. Область для показа слайдов.
Результаты Разработаннаясистема объединяет в себе такие функции как:
1) Создание и управление электронными образовательными курсами.
2) Организация он-лайн вещания и обмена мультимедийной информацией между преподавателем и обучающимися.
Функционала системы достаточно, чтобы качественно организовать проведение индивидуальных занятий и занятий для малых групп (от 5 до 25 человек).
В перспективе, планируется создания специализированных приложений для мобильных устройств на базе операционных систем Windows 8/Phone, Android, AppleIOS.
Список литературы 1. Symfony 2 Frameworkofficialsite [Электронныйресурс]. – М., 2010. – Режимдоступа:
http://symfony.com/ 2. Lynda Education Javascript tutorials library – 2013 – Режимдоступа:
http://www.lynda.com/aboutus/website-use-policy 3. Webrtcoficiall website – 2013 – Режимдоступа: http://www.webrtc.org/
ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ
Лаптев М.А., Некрасов Д.В. – студенты, Сорокин А.В. – к.т.н., доцент Алтайский государственный технический университет (г. Барнаул) Проблема решения задачи упорядочения из области теории расписаний достаточно долгое время занимает умы многих исследователей, начиная с 60-х годов, когда была опубликована работа Джонсона [1,2]. Как было показано в работе, в общем случае нет конкретного общего решения задачи упорядочения, хотя в частных случаях получаются достаточно простые алгоритмы ее решения.Как правило, задачу упорядочения связывают с производственной задачей, хотя на самом деле ее можно применять в различных областях. Остановимся на ее формулировке, привязанной к производству, имеющей смысл в серийном производстве.
Данная задача, представляет собой задачу выбора порядка обслуживания, оптимизирующего какой-либо существенный показатель качества функционирования системы. Одними из первых ученых, исследовавших задачу упорядочения, были американские ученые Беллман и Джонсон. Приведем постановку этой задачи в их формулировке.
Имеется m станков, выполняющих различные технологические операции, на которых необходимо обработать набор n различных деталей с номерами i=1,2…,n. Предполагается, что дано tij - время обработки i-ой детали на j-ом станке, не являющееся нулевым. Каждая деталь имеет одинаковый технологический маршрут обработки, в котором прописан порядок «движения» детали от первого станка к последнему. Такой маршрут называется «жстким».
Ограничения, фигурирующие в задаче, формулируются следующим образом:
1. Для каждой детали обработка начинается с первого станка;
2. Для каждой детали обработка на j-ом станке может начинаться не раньше, чем окончится е обработка на станке j-1;
3. На каждом станке одновременно может обрабатываться не более одной детали;
4. Начавшаяся операция не прерывается до полного е завершения.
Необходимо найти такую последовательность обработки набора n-деталей, которая минимизирует время окончания обработки последней детали этой последовательности.
Данная задача в общем случае при m 3 является NP-полной и, следовательно, для е решения не существует алгоритма, завершающегося за полиномиальное число операций. В связи с этим для е решения применяют подходы, находящие решения, приближнные к оптимальному. Хотя степень приближенности здесь оценить достаточно сложно. Среди таких подходов можно выделить методы, основанные на случайном поиске: метод отжига [3,4], генетические алгоритмы [7-9] и др., и детерминированные методы (подходы), основанные на «правилах предпочтения» или на «правилах Петрова» [5].
В данной работе для решения задачи упорядочения будет рассмотрен метод, основанный на "Генетическом алгоритме". Будет представлено его сравнение с простой эвристикой и подходом, основанным на "правилах Петрова".
Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путм случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Он является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
В работе реализован генетический алгоритм, состоящий из следующих основных шагов:
1. Генерируется первое поколение, каждая особь, которой содержит случайную последовательность деталей.
2. Для каждой особи считается выживаемость (Fitness). Она показывает близость последовательности к «идеальной». На основании выживаемости рассчитывается вероятность оставить потомство.
3. Создатся потомство, которое заменяет текущее поколение. Каждая особь потомства имеет двух родителей, признаки которых данная особь содержит в себе (плюс мутации - признаки, не содержащиеся ни в одном из родителей).
4. Процесс «скрещивания» двух особей называется кроссинговером. Кроссинговер предусматривает наследование случайных признаков родителей, а также появление новых признаков (мутаций).
5. Повторяем пункты 2-4 некоторое число раз. Изменяя данный параметр или размер популяции, можно регулировать точность ответа и время выполнения программы.
6. Среди всех существовавших особей запоминается наиболее удачная, она и будет Может быть показано, что каждое следующее поколение будет сходиться к идеальному решению, алгоритм дат всего лишь приближнное решение. Чтобы ответить на вопрос, насколько это решение точное было проведено исследование, которое показало, что алгоритм проявляет себя состоятельным при малых и средних размерностях. При таких начальных условиях он обгоняет по точности подход, основанный на «правилах Петрова» и простую эвристику. При больших объмах задачи также возможно использование генетического алгоритма, но оно будет оправдано только при наличии больших вычислительных мощностей, так как время работы программы имеет асимптотику:
Результаты временных затрат программ, реализующих подход Петрова, простую эвристику и генетический алгоритм, в зависимости от размерности задачи упорядочения приведены в таблицах.
Список литературы 1. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М., Наука, 1975. – 360 с.
2. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М., Наука, 1975. – 256 с.
3. http://ru.wikipedia.org/wikiАлгоритм_имитации_отжига 4. Лопатин А.С. Метод отжига. – СпбГУ. - http://www.math.spbu.ru/user/gran/sb1/lopatin.pdf 5. Шукис А.А. Исследование операций: Задачи упорядочения. – Изд-во: АПИ, 1980. – 98 с.
6. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — 320 с.
7. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы — 2-е изд. — М: Горячая линия-Телеком, 2008. — С. 452 с.
http://habrahabr.ru/post/128704/
РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА ДЛЯ ОБУЧЕНИЯ СТУДЕНТОВ
ЭКОНОМИЧЕСКИХ СПЕЦИАЛЬНОСТЕЙ ФИНАНСОВО-КОММЕРЧЕСКИМ
ОПЕРАЦИЯМ С ПОМОЩЬЮ ИНТЕРАКТИВНЫХ МЕТОДОВ
Овчинникова А.А. – студент, Бразовская Н.В. – к.ф.-м.н., профессор Алтайский государственный технический университет (г. Барнаул) В современном обществе образование играет очень важную роль. Постоянное расширение числа компьютерных классов, создание на их основе информационновычислительных сетей вузов и школ с последующим объединением в региональные сети, расширение информационной наполненности таких сетей приводят к качественным изменениям в методике преподавания дисциплин, создают предпосылки к созданию компьютерной образовательной среды. Создание и развитие такой среды предполагает решение следующих задач.Первая задача связана с переосмыслением методики преподавания дисциплин в вузах.
Традиционная методика обучения и методика обучения с использованием компьютера сильно разнятся между собой. Назрела существенная необходимость разработки структурированных учебных материалов для использования их в КОП, разработки методики их подачи и осуществления контроля знаний в КОП.
Вторая важная задача состоит в разработке общих подходов и принципов для объединения КОП в единую учебно-информационную среду. Прежде всего, большое внимание должно быть уделено вопросам навигации как от фрагмента к фрагменту в рамках отдельного компьютеризированного курса, так и от курса к курсу.
Унификация принципов навигации, разработка общих подходов и, возможно, инструментальных средств для создания различных типов КОП вне зависимости от разделов знаний должны строиться на основе того, что компьютерная технология обучения - это образовательный процесс, основанный на едином средстве обучения - компьютере, и взаимодействие пользователя с новой обучающей программой должно строиться на основе привычных ему навыков.
При разработке компьютерных обучающих программ следует учитывать эргономический аспект разработки. Пользователь КОП может проводить за компьютером достаточно длительное время (особенно если пользователь работает в режиме самообразования). При этом ему часто требуется повторять большое число однотипных манипуляций (выбор режима работы, ввод исходных данных и т.п.). Отсюда следует, что при разработке пользовательского и графического интерфейса КОП необходимо ориентироваться на требования инженерной психологии и эргономики.
Информационное наполнение КОП состоит из различных компонент, реализующие ее определенные функциональные свойства.
Выделим три основные компоненты информационного наполнения обучающих программ:
текстовая;
вычислительная;
имитационная.
Текстовая компонента. Любая обучающая программа немыслима без использования в большей или меньшей мере текстового материала (от изложения теоретической части курса и до надписей на нестандартных кнопках). При разработке программ следует стремиться к тому, чтобы весь текстовый материал курса размещался вне вычислительной и имитационной компоненты. Выполнение этого требования позволяет осуществлять модификацию КОП, а также, при необходимости, создавать иноязычные варианты обучающей программы.
Вычислительная компонента. Во многих КОП используется сложный и уникальный математический аппарат для поддержки процедуры обучения, визуализации полученных результатов, построения оценочной части контролирующего или тестирующего раздела обучающей программы и решения других задач. Создание подобных программ трудоемкий процесс.
Имитационная или моделирующая компонента. Необходимость использования моделей в процессе обучения обусловлена следующими причинами: моделирование позволяет за время одного занятия рассмотреть и проанализировать процессы, которые в реальной жизни занимают дни, недели, месяцы и годы, а использование моделей позволяет сформировать адекватное представление об исследуемом процессе.
Технологический аспект разработки компьютерных обучающих программ связан с кодированием, сопровождением и развитием во времени КОП как программного продукта.
При разработке обучающего комплекса была выбрана тема «Финансово-коммерческие операции». В современном мире практически любая деятельность связана с денежными операциями. Мы можем говорить как о большой фирме, так и об отдельном человеке, который каждый день сталкивается с денежными отношениями. Цель нашей работы смоделировать реальные ситуации финансово – коммерческой деятельности, которые позволят понять и принять правильное решение в конкретном случае, потому что без определенных знаний и навыков о финансово – коммерческих операциях довольно трудно понять, как посчитать ту или иную процентную ставку, срок ссуды или сумму, которую необходимо будет выплатить через какой-то промежуток времени.
В рамках научно – исследовательской работы разработан обучающий программный комплекс для студентов экономических специальностей, в котором были реализованы следующие финансово – коммерческие операции:
- операции по схеме простых процентов;
- операции по схеме сложных процентов;
- операции дисконтирования;
- финансово-товарные потоки;
- инфляция;
- операции с облигациями;
- операции с акциями;
- модели сравнения операций.
«