автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование в табличных процессорах

На правах рукописи

Аникина Оксана Владимировна

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ТАБЛИЧНЫХ ПРОЦЕССОРАХ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

005007975

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 9 ЯНВ 2С12

УЛЬЯНОВСК - 2012

005007975

Работа выполнена на кафедре «Высшая математика и математическое моделирование» в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Тольятгинский государственный университет».

Научный руководитель: доктор технических наук, профессор

Зибров Петр Федорович

Официальные оппоненты: доктор технических наук, профессор

Семушин Иннокентий Васильевич

кандидат технических наук Крайнюков Николай Иванович

Ведущая организация: ФГОБУ ВПО «Поволжский государственный

университет телекоммуникаций и информатики»

Защита диссертации состоится «15» февраля 2012 г. в 1300 часов на заседании диссертационного совета Д 212.278.02 при ФГБОУ ВПО «Ульяновский государственный университет» по адресу: г. Ульяновск, ул. Набережная реки Свияги, 106, корп.1, ауд.703.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, с авторефератом - на сайте вуза http://www.vmi.ulsu.ru и на сайте Высшей аттестационной комиссии при Министерстве образования и науки Российской Федерации http://vak.ed.gov.ru.

Отзыв на автореферат присылать по адресу: 432017, г. Ульяновск, ул. Л.Толстого, д. 42, УлГУ, Отдел послевузовского и профессионального образования.

Автореферат разослан « /»г » января 2012 г.

Ученый секретарь диссертационного совета

Волков М.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В математическом моделировании за последние десятилетия произошел качественный скачок в создании и использовании модельно-обоснованных методов анализа действительности и формах представления результатов моделирования. Академическое понимание и узкопрофессиональное математическое моделирование уступает место имитационным моделям в научной и производственно-хозяйственной деятельности1.

В настоящее время электронные таблицы (ЭТ) являются одним из самых доступных и полезных компьютерных средств выполнения расчетов, анализа, моделирования и автоматизации в экономике, производственной деятельности и образовании. Последние достижения в области экономико-математического моделирования в ЭТ изложены в монографиях Л. Абдулазара, Ш. Беннинга2, К. Берка3, У.Л. Винстона4, Б. Джелена, А.Ф. Горшкова, А. Каплана, К. Карлберга5, Д. Левина, Б.Ю. Левита, A.B. Леоненкова, A.A. Минько, Дж. Мура, К. Олбрайта6, Л.В. Уэйна и других. Значительно скромнее, в основном работами А.Н. Васильева7, Р.Н. Вадзинского и Р.У. Ларсена, представлены их современные инженерно - технические приложения.

Из анализа литературных источников следует, что по своим потенциальным возможностям алгоритмическое и имитационное моделирование в ЭТ в ряде случаев уступает моделированию в специализированных программных средах, таких как GPSS или AnyLogic, однако оно имеет и свои очевидные преимущества:

1) огромное число задач, стоящих перед специалистами в предметных областях, например, многие управленческие ситуации не требуют для своего решения применения специализированных систем моделирования и могут быть смоделированы собственными силами, без привлечения труда программистов;

2) квалифицированная разработка моделей в специализированных средах базируется на профессиональном опыте моделирования, поэтому использование таких сред специалистами в конкретных предметных областях часто оказывается затруднительным или нерациональным;

1 Зибров П.Ф., Палфёрова С.Ш. Математические модели экономических и социальных систем: монография -Тольятти: ТТУ, 2010. - 143 с.

2 Беннинга Ш. Финансовое моделирование с использованием Excel / пер. с англ. М.: Издательский дом «Вильяме», 2007. - 592 с.

3 Берк К., Кейри П. Анализ данных с помощью Microsoft Excel /пер. с англ. М.: Издательский дом «Вильяме», 2005.-560 с.

4 Винстон У.Л. Microsoft Excel: анализ данных и построение бизнес - моделей / пер. с англ. М.: Издательско-торговый дом «Русская редакция», 2005. - 576 с.

5 Карлберг К. Бизнес-анализ с помощью Microsoft Excel / пер. с англ. М.: Издательский дом «Вильяме», 2006. -464 с.

6 Олбрайт К. Моделирование с помощью Excel и VBA. Разработка систем поддержки принятия решений / пер. с англ. - М.: Издательский дом «Вильяме»,2005. - 672 с.

7 Васильев А. Н. Финансовое моделирование и оптимизация средствами Excel 2007. СПб.:Питер, 2009 - 320 с.

3) любой интегрированный офисный пакет, например, Microsoft Office, имеющийся практически в любой организации, содержит табличный процессор, и сотрудники организации в той или иной степени владеют им, а специализированную систему моделирования необходимо приобрести, причем по достаточно высокой цене, и затратить значительные усилия и средства на ее освоение и сопровождение;

4) в ЭТ встроены мощные инструменты анализа, представления и визуализации данных, которые можно с успехом применять для интерпретации результатов моделирования и даже добавлять их непосредственно в создаваемую модель, в специализированных системах моделирования такая возможность ограничена или вообще отсутствует;

5) алгоритмическое и имитационное моделирование в электронных таблицах, благодаря их высокой информативности и наглядности, имеет особое значение в научных исследованиях, программно-инженерном творчестве и образовательном процессе.

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

Объектом исследования являются математические модели, комплексы программ, методы и средства алгоритмического и имитационного моделирования материальных, информационных и комбинированных систем и закономерностей природных явлений в табличных процессорах.

Предметом исследования являются теоретическое обоснование и разработка новых алгоритмических и имитационных методов моделирования статических и динамических систем и процессов в табличных процессорах.

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

1. Исследовать особенности алгоритмического и имитационного моделирования в электронных таблицах в режимах одной и множественных итераций.

2. Обосновать и разработать структуру, принципы и состав технологии проектирования имитационных табличных моделей на основе алгоритмов решаемых задач.

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

4. Разработать комплекс программ для автоматизированного построения табличных моделей недетерминированных алгоритмов.

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

Направление исследований. Создание новых и совершенствование существующих технологий алгоритмического и имитационного моделирования статических и динамических процессов на основе ЭТ.

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

Научная новизна диссертационной работы заключается в следующих новых результатах.

1. Разработаны оригинальные математические модели статистической обработки экспертных оценок показателей качества участников электронных торгов и нелинейной динамики развития основных производственных фондов предприятия.

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

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

4. Предложен и опробован на практике оригинальный численный метод приведения недетерминированных алгоритмов и программ, содержащих условные операторы, к детерминированному виду.

5. Разработаны методология и программное обеспечение автоматизированного создания имитационных табличных моделей недетерминированных алгоритмов.

6. Экспериментально изучены нестандартные особенности и принципы создания итерационных табличных моделей, определена их типовая структура.

7. Теоретически обоснована и спроектирована технология создания алгоритмических и итерационных табличных моделей алгоритмов.

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

9. Экспериментально доказано, что ЭТ являются эффективной средой имитационного моделирования и визуализации алгоритмов, включая нетривиальные алгоритмы искусственного интеллекта.

Практическая значимость работы. Использование технологии имитационного табличного моделирования (ИТМ) алгоритмов дает возможность специалистам в предметных областях самостоятельно создавать математические модели и проводить на их основе анализ систем, процессов и явлений в сфере своей профессиональной деятельности без привлечения труда квалифицированных программистов.

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

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

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

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

Реализация и внедрение результатов. По результатам диссертационного исследования изданы две монографии, три учебно - методических пособия для студентов специальности 080801 «Прикладная информатика (в экономике)» ПВГУС. Результаты диссертации внедрены в Тольяттинском муниципальном образовательном учреждении дополнительного образования детей ДЮЦ «Центр информационных технологий образования», Поволжском государственном университете сервиса, Тольяттинском технологическом центре ООО «НетКрэкер», что подтверждается прилагаемыми актами внедрения.

Основные положения, выносимые на защиту

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

2. Ориентированный граф связей между ячейками алгоритмической и имитационной табличной модели и определяющее влияние- этого графа на технологический процесс создания табличной модели и ее организационную структуру.

3. Оригинальный численный метод приведения недетерминированных алгоритмов и программ, содержащих условные операторы, к детерминированному виду, методология и программное обеспечение автоматизированного создания имитационных табличных моделей недетерминированных алгоритмов.

4. Структура, содержание, процедуры и операции информационной технологии проектирования имитационных табличных моделей алгоритмов без написания программного кода.

5. Алгоритмические и имитационные итерационные табличные модели алгоритмов оптимизации оценки участников электронных торгов, динамических систем и процессов, конечных и клеточных автоматов, генетических и эволюционных алгоритмов, искусственных нейронных сетей.

Апробация работы. Результаты диссертации использовались при выполнении поисковой научно-исследовательской работы «Развитие методов математического моделирования для решения актуальных задач механики деформирования, электродинамики, акустики и гидродинамики океана» в научно-образовательном центре «Экспериментальной и теоретической физики» Владивостокского государственного университета экономики и сервиса в рамках государственного контракта № 14.740.12.0835 от 20.04.2011 по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России на 2009-2013 гг».

Проект «Имитационное табличное моделирование алгоритмов искусственного интеллекта» награжден дипломом II степени за победу в региональном конкурсе по компьютерному моделированию (Тольятти, 2011г).

Основные результаты работы докладывались на Международном форуме «Формирование современного информационного общества - проблемы, перспективы, инновационные подходы» (Санкт-Петербург, 2011), Международной научно - практической конференции «Инновации на основе информационных и коммуникационных технологий ИНФО-2011» (Сочи, 2011), VI Международной научно-технической конференции «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ, и систем искусственного интеллекта» (Вологда, 2011), VII Международной научно -технической конференции «Физика и технические приложения волновых процессов» (Самара, 2008); IV, V и VI Международных научно - технических конференциях по синергетике (Тольятти, 2007, 2008, 2009), Всероссийской конференции с элементами научной школы для молодежи (Ульяновск, 2009), на V Международной научной конференции «Математика. Образование. Культура» (Тольятти, 2011), II и III Международных научно-практических конференциях (Тольятти, 2008, 2009), Межвузовской научно-методической конференции (Тольятти, 2009), Научно - методическом семинаре (Тольятти, 2008), Научно-методической конференции (Тольятти, 2007).

Публикации. Материалы диссертации опубликованы в 23 работах, в том числе б статей в рецензируемых журналах из списка ВАК, 2 монографиях. Список основных работ автора, отражающих существо диссертационной работы, приведен в конце автореферата.

Личный вклад автора. Постановка задач осуществлялась научным руководителем. Автором выполнен основной объем исследований, самостоятельно разработан оригинальный численный метод приведения недетерминированных ' алгоритмов и программ к детерминированному виду, программное обеспечение для автоматизированного построения имитационной табличной модели. На основании исследования недокументированных возможностей электронных таблиц разработана технология имитационного табличного моделирования алгоритмов. Представленные в диссертации имитационные табличные модели выполнены автором самостоятельно.

Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка цитируемой литературы из 133 источников и приложения. Работа изложена на 159 страницах машинописного текста, содержит 54 рисунка. В приложении приведены листинги разработанных макросов и процедур, описания наиболее громоздких имитационных табличных моделей, копии документов об использовании результатов работы.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Алгоритмические и имитационные методы математического моделирования в табличных процессорах» дается теоретическое обобщение и обоснование создания алгоритмических и имитационных моделей алгоритмов в ЭТ, разработаны оригинальный численный метод приведения недетерминированных алгоритмов и программ, содержащих условные операторы, к детерминированному виду, а также методология и программное обеспечение автоматизированного создания имитационных табличных моделей недетерминированных алгоритмов.

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

Главные достоинства предлагаемой технологии создания алгоритмических и имитационных табличных моделей состоят в следующем:

- процесс создания табличной модели становится организованным и логичным, что существенно ускоряет создание модели, позволяет избежать множества ошибок;

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

- разработчик большую часть времени затрачивает на работу с данными, тогда как при программировании его внимание постоянно отвлекается на процесс кодирования. Обладая перечисленными несомненными достоинствами, ИТМ алгоритмов имеет и

недостатки, ограничивающие область его практического применения:

- алгоритм обработки данных должен быть вычислительным, а не процедурным, так как функции табличного процессора пассивны;

- технология ИТМ алгоритмов хорошо подходит для создания одномерных, двумерных, в некоторых случаях трехмерных моделей, в противном случае серьезным ограничивающим фактором становится плоская структура ЭТ.

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

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

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

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

Граф алгоритма Граф связей между ячейками

О Исполнительное устройство (ИУ) © Устройство ввода Ц Устройство вывода [И Формула в ячейке Щ Входная ячейка Ц Выходная ячейка

Граф - машина не имеет собственной выделенной памяти, результат вычислений сохраняется в ИУ Табличная модель не имеет собственной выделенной памяти, результат вычислений сохраняется в ячейке

В процессе функционирования граф -машины каждое ИУ выполняет над элементами данных фиксированную вычислительную операцию В процессе пересчета ЭТ каждая ячейка выполняет над элементами данных фиксированную вычислительную операцию по заданной формуле

Граф алгоритма является ациклическим, каждое ИУ работает в режиме однократного срабатывания Граф связей между ячейками является ациклическим, каждая ячейка работает в режиме однократного срабатывания

Рис.1. Аналогия «граф-машина — табличная модель алгоритма».

Функциональные баллы - это количественная оценка функциональности системы и трудоемкости ее разработки. Сложность программного приложения характеризуется пятью элементами: число вводов, число выводов, число запросов, число файлов, число интерфейсов и их весами. Оценка трудоемкости работ программистов рассчитывается по формуле:

s

S = Л,

ы

где S - трудоемкость работ, Wj - весовой коэффициент элементов функциональных баллов, nj — число соответствующих элементов.

Эмпирические оценки относительной мощности разных средств разработки путем расчета числа строк кода, которое требуется для программирования одного функционального балла, следующие: Assembler - 320, С - 128, Pascal - 91, Ada - 83, С++ - 53, Java - 53, ЭТ - 6. Очевидно, что эффективность разработки алгоритмов и математических моделей в ЭТ существенно выше по сравнению с другими средами программирования. Особенно рационально использование ЭТ на начальных этапах разработки сложных алгоритмов или их фрагментов, когда спецификация создаваемой программы еще не совсем ясна.

Во второй главе «Теоретическое обоснование итерационных вычислений в электронных таблицах» дается теоретическое обоснование технологии создания итерационных моделей в табличных процессорах.

В литературных источниках проблема множественных итераций в ЭТ отражена чрезвычайно слабо - известна лишь монография Рональда Ларсена, в которой итерациям в Excel посвящена целая глава. Однако Рональд Ларсен рассматривает только простейший случай выполнения итераций в одной ячейке, начиная с нулевого начального приближения, и не анализирует проблему множественных итераций в ЭТ в целом. Расширенный поиск в Интернет показал, что обычно пользователи Excel решают итерационные задачи с помощью стандартных надстроек Подбор параметра и Поиск решения, каждая из которых имеет ограниченное применение.

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

• в итерациях может быть задействовано произвольное число ячеек табличной модели, связанных друг с другом неявной циклической ссылкой;

• пользователь может по своему усмотрению задавать начальное приближение для цикла итераций, а результаты итеративных вычислений фиксировать в произвольных выходных ячейках модели;

• табличная модель одновременно может содержать много замкнутых контуров связей между ячейками, реализующих как одинаковые, так и разные алгоритмы вычислений;

• пересчет формул в ячейках, связанных циклической ссылкой, а также в зависящих от них ячейках, выполняется, не следуя связям между ячейками, а в порядке слева направо по столбцам и сверху вниз по строкам табличной модели, что накладывает ограничения на размещение ячеек итерационной табличной модели на рабочем листе Excel;

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

Результаты проведенного исследования позволили обосновать принципы создания итерационных табличных моделей в ЭТ. Важным нововведением явилось использование в итерационных табличных моделях вспомогательной ячейки Start, которую логично назвать флагом ручного включения итераций (Start = 1 - итерации разрешены, Start = 0 - итерации запрещены). Управляя вручную (или программно) этим флагом, а также используя функцию ЕСЛИ вида ECIffl(Start = 1; замкнуть_контур_связей; разомкнутъ_контур_связей), можно динамически замыкать и размыкать контуры циклических связей в итерационной табличной модели.

Анализ закономерностей выполнения итераций в ЭТ позволил определить типовую структуру итерационной табличной модели, которая должна включать: таблицу входных данных (входы модели); таблицу выходных данных (выходы модели); диапазон ячеек, задающих начальное приближение итераций; диапазон ячеек инициализации цикла

итераций; диапазон ячеек с формулами, реализующими алгоритм тела цикла итераций; выходной диапазон ячеек.

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

Алгоритмическая табличная модель Итерационная табличная модель

На рабочем листе разворачиваются все проходы цикла вычислений подобно тому, как на заре вычислительной техники в явном виде разворачивались программные макросы На рабочем листе разворачивается часть циклов вычислений. Итерации выполняются с возвратом в начало цикла как в обычных программных циклах

Рабочий лист содержит все входные, выходные и промежуточные данные моделирования Рабочий лист содержит часть данных моделирования, для детального отображения выходных результатов приходится принимать специальные меры

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

Применение множественных итераций расширяет возможности технологии ИТМ, добавляя табличной модели дополнительное измерение (при моделировании динамических систем - временную координату)

В третьей главе «Типы математических моделей исследуемых объектов» дано описание различных типов математических моделей, реализованных в табличном виде в V главе диссертационной работы.

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

1?И

(

1У2р}-, / Л(5-0Л-(

а

Т-а

•а! т

(1)

где - текущее значение частости балльной оценки эксперта от 0 до 5,

а--

1

^гаах 5

Коэффициент нереализованных возможностей у определяет два нормированных показателя качества участника торгов:

г = 1-

а 1 ~а

•а!т

а 1-а

-а

В задаче динамики развития экономики предприятия с нелинейной производственной функцией в качестве функциональной модели динамического процесса выступает обыкновенное нелинейное дифференциальное уравнение первого порядка:

Л" (0 t

—j-= A(t]\-А0-{\+fiехр( )]}+/(0 (2)

al ç р

где А{1) - стоимость основных производственных фондов; / - время; Ао =Л(0);

.. /-(1 -w-щ)-^

-———— щ - норма налогообложения на объем выпуска (0 < щ < 1); пг -

1+п2 -к-[ 1-ç]

норма налогообложения на прибыль (0 < п2 < 1); £ - доля чистой прибыли, отчисляемой на обновление и расширение производства (0 < i < 1); w - удельная себестоимость выпуска продукции (0 <w < 1);/-показатель фондоотдачи; /? - коэффициент, определяющий уровень насыщения объема выпуска продукции; у, X, 0<а<1, параметры функции трудовых ресурсов; I(t) - интенсивность внешних инвестиций в стоимостном выражении; P{t)=/-A"(t)-Ll, L -трудовые ресурсы, P(t) - объем выпуска продукции в момент времени t в стоимостном выражении.

В табличной модели конкурирующего взаимодействия двух биологических видов функциональная модель описывается системой обыкновенных дифференциальных уравнений Вольтерр£:

~cxy,-cuyî + с12у,у2 % а (3)

-f-=c2y2 + c2{yty2-c22y2 at

при начальных условиях yw = yi(0), уго = yi(V), где члены типа c^yjj соответствуют

межвидовому взаимодействию (су < 0 - конкуренция, Су > 0 - симбиоз, су и Cjt разного знака -отношения «хищник-жертва»), знак минус при членах с^у2 отражает факт внутривидовой конкуренции, линейные члены qy, описывают свободное размножение видов.

Имитационное табличное моделирование недетерминированных конечных автоматов рассматривается на примере распознавателя слов формальных языков, задаваемого пятеркой

К> (Q, I и {е}, 5, S, F) где Q - множество состояний конечного автомата, Z - алфавит, 5 - функция переходов конечного автомата, S ç Q - множество стартовых состояний (входов) конечного автомата, F с Q - множество финальных состояний (выходов) конечного автомата, е - пустой символ.

Переход конечного автомата из состояний q в состояние г при подаче на его вход символа а определяется условием 8(q, а) э г, V q, г б Q, а е £ и {е}.

Функционирование конечного автомата состоит в перемещении по дугам его орграфа, чтении при этом букв алфавита £ и составлении из прочитанных букв некоторого слова, либо просто в переходах в случае, когда дуги помечены пустым символом е.

Алгоритм распознавания конечным автоматом слова длины п сводится к выполнению п последовательных итераций, в каждой из которых выполняются следующие шаги: 1) считывается очередная буква х распознаваемого слова; 2) определяется множество возможных текущих состояний конечного автомата в данной итерации; 3) анализируются возможные переходы из вершин {ц} орграфа по дугам, помеченным пустыми символами е, и к множеству текущих состояний {я} добавляются состояния, доступные из вершин по путям, определяемым рефлексивно-транзитивным замыканием ф *; с помощью матрицы смежностей находятся дуги орграфа, помеченные буквой х и допускающие переходы х) эг.

Наконец, имитационное табличное моделирование искусственных нейронных сетей представлено алгоритмом обратного распространения ошибки как итеративным градиентным методом оптимизации.

Минимизируемой функцией ошибки нейронной сети является величина:

адЦГМ'и-ч.,)1 (4)

Л*

где у^ - реальное выходное значение >го нейрона выходного слоя ИНС при подаче на ее

входы к-го учебного образца, с1к- известное выходное состояние этого нейрона для

каждого учебного образца, ге - матрица весовых коэффициентов нейронов. Суммирование ведется по всем нейронам выходного слоя и по всем учебным образцам.

Минимизация целевой функции методом градиентного спуска обеспечивается итеративным приращением весовых коэффициентов у/™ синаптической связи, равным:

дп(9) (0=- V (А • л*/" С-1) + 0 ■- М) ■ ¿Г ■ У{Г С -!)) ■ (5)

где # и слои нейронов, П (0 < П <1) - подбираемый экспериментально коэффициент скорости обучения, ц - коэффициент момента инерции, I - номер текущей итерации, б^ -ошибкаго нейрона в слое q.

В четвертой главе «Проектирование технологии алгоритмического и имитационного моделирования в электронных таблицах» изложена технология создания алгоритмических и итерационных табличных моделей алгоритмов (рис.2).

Практическое использование этой технологии обеспечивает реализацию логически и структурно безупречных имитационных табличных моделей многих алгоритмов. Заметим, что разработанную технологию ИТМ можно использовать не только для имитации алгоритмов, но и при создании любых ЭТ, безотносительно к их целевой направленности.

Технология проектирования алгоритмической и имитационной табличной модели включает следующие процедуры (рис.3):

- определение типа создаваемой табличной модели (алгоритмическая или итерационная);

- присвоение символических имен ячейкам и диапазонам;

- построение графа связей между ячейками табличной модели;

- проектирование организационной структуры таблиц модели;

8

О

а

■8

(Ц

с

Анализ и декомпозиция алгоритма

Трассировка алгоритма (\/ВА-программы)

Определение имен и типов переменных модели

Выбор типа модели

Построение графа связей между ячейками

Определение структуры табличной модели

Написание кода пользовательских функций

Ввод формул в зависимые ячейки

Разработка пользовательского интерфейса

Разработка управляющих макросов

Отладка и тестирование табличной модели

Разработка плана модельных экспериментов

Задание рядов значений входных переменных

Создание таблицы плана эксперимента

Задание таблиц подстановки и макросов

Выполнение и анализ результатов эксперимента

К

и «

о К!

■ч

Р5 >

О! '

ЕЯ

К

а

о К!

О

За о

а

тз о

1 г

о в! ч

§с

Рис.3. Схема технологического процесса проектирования имитационной табличной модели

алгоритма.

- табличная реализация алгоритма обработки данных;

- создание пользовательского интерфейса;

- тестирование и отладка табличной модели.

Построение графа связей между ячейками и создание организационной структуры табличной модели упрощаются за счет применения технологии drag-and-drop и предложенного в диссертации метода трассировки алгоритма. Для случаев, когда в распоряжении разработчика имеется VBA-программа, решающая задачу моделирования, разработаны процедуры трассировки, автоматизирующие процесс трассировки.

На основе технологии ИТМ созданы имитационные табличные модели большинства классических алгоритмов, составляющих основу численных методов: рекуррентных вычислений; интерполяции функций; решения линейных уравнений и их систем; одномерной и многомерной оптимизации; численного дифференцирования и интегрирования; решения обыкновенных дифференциальных уравнений и некоторых уравнений в частных производных; решения задач методом Монте - Карло и др.

Пятая глава «Перспективы практического применения имитационного моделирования в табличных процессорах» содержит нетривиальные примеры использования разработанной технологии создания алгоритмических и имитационных табличных моделей в современных перспективных направлениях: экспертной оценке интегрированных показателей фирм -участников торгов, временной динамики детерминированных и стохастических систем/процессов, конечных и клеточных автоматов, генетических и эволюционных алгоритмов, искусственных нейронных сетей (ИНС), визуализации тонкой информационной структуры алгоритмов.

Построены имитационные табличные модели, моделирующие временное поведение систем и процессов, описываемых обыкновенными дифференциальными уравнениями первого порядка и их системами (начальная задача Коши) и решаемых методами Эйлера, Рунге-Кутты, Адамса.

Рис. 4. Моделирование динамики основных производственных фондов предприятия: 1 - линейная модель; 2 - функция Кобба - Дугласа; 3 - насыщение объема выпуска;

4 - обобщенная модель.

Эффективность технологии продемонстрирована на примерах табличного решения методом Рунге-Кутты обыкновенных дифференциальных уравнений, описывающих динамику развития предприятия (рис.4) и конкурирующего взаимодействия двух популяций типа «хищник - жертва» (модель Вольтерра, рис.5).

Рис.5. Временная динамика численности популяций в модели Вольтерра.

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

Впервые созданы и изучены имитационные табличные модели почти всех семейств клеточных автоматов, представленных на сайте http://www.mirekw.com, и других: семейства КА «Ш-binary», «Generations». «Life», «Margolus», «Rules-Table», «Vote-for-Life», «Weighted-Life», «Одномерная диффузия», «Муравей Лэнггона», «Автоволны» (рис.б).

Рис.6. Состояние клеточного автомата семейства «Margolus» после 50 итераций.

Табличная имитация генетических и эволюционных алгоритмов продемонстрирована на примере глобальной оптимизации функции Растригина:

хг) = 20+Х12+Х22-10(со527К1+со82тп:2) (6) часто используемой в качестве тестовой для различных оптимизационных алгоритмов.

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

} "'Максимизация ^Минимизация П-;- Старт | Стоп j ¡

» - г Число итераций N 100 ^Вероятность скрещивания рс 1

I Флаг включения итераций 1 Вероятность мутации рт 1

Счетчик итераций 200 Ч( Число особей в популяции П 20

§ 1| ..„. .... __________ --- Длина хромосомы L 28

\ Левая граница а -2 (х1> хг) опт ?ОПТ

Правая граница Ь 2 Ii 508, -1 508 •44,5229

: Интервалов разбиения 16383 <X1, х2) „„=±1,508 44.5229

1 Шаг разбиения п 0,00024 Х2) min = 0 0,0000

I.............................................. ........

к ......................................................................................-.........-............... Макс, длина хромосомы 32

Рис. 7. Пользовательский интерфейс табличной модели ЭА оптимизации.

Возможность построения имитационной табличной модели искусственной нейронной сети (ИНС) продемонстрирована на примере решения классической задачи Фишера о

классификации цветков ирисов. В табличном виде реализована имитационная табличная модель трехслойной ИНС прямого распространения вида 4 - б - 3 с алгоритмом обучения методом обратного распространения ошибки (рис.8).

Подача образцов

Момент инерции 0,4

Скорость обучения 0,.04

Начальный вес синапсов 0,02

Флаг включения итераций 0

Число итераций 7150

Счетчик итераций 0

Число эпох 50

Счетчик эпох| 0 0

Счетчик образцов эпохи 0

последовательно С случайно «¡перемешивая1

Обучение!

Учебных образцов 137 Сброс

Контрольных образцов 6

Всего образцов 143

Номер образца 1 | гпсШит| 117 I

1 *

х

а Ю

| 0,9 о 0,8

а

¡0,7

? 0,6

5 0,5 + ш

0,4

0,3 0,2 0,1 0

У

4 ¥

20

*

—г—

40

£

—I—

60

; t I

80 100 Количество эпох ♦ Последовательно « Случайно * Перемешивая

Рис.8. Пользовательский интерфейс и среднеквадратичная ошибка обучения табличной

модели ИНС за 100 эпох.

Из графиков видно, что лучшими режимами подачи образцов в процессе обучения ИНС являются режимы «Перемешивая» и «Случайно», в которых уже после 10 эпох среднеквадратичная ошибка уменьшается до 0,04 и все учебные образцы правильно классифицируются сетью.

Для иллюстрации возможности моделирования в ЭТ параллельных алгоритмов на рис.9 приведена алгоритмическая табличная модель известного алгоритма параллельного вычисления частных сумм, на которой с помощью инструмента «Зависимости» визуализированы связи между ячейками.

Приведенная табличная модель (рис.9) показывает, что графические инструменты ЭТ позволяют в наглядном виде отображать тонкую информационную структуру как последовательных, так и параллельных алгоритмов.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В рамках проведенных исследований получены следующие основные результаты.

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

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

3. Разработан и реализован оригинальный численный метод приведения недетерминированных программ к детерминированному виду путем выравнивания ветвей условных операторов алгоритма.

4. Предложен метод трассировки алгоритма / реализующей его программы, позволяющий упростить процесс построения графа связей между ячейками, а также создавать структуру и строить табличную модель посредством технологии drag-and-drop.

5. Предложена методология, определены структуры данных и создано программное обеспечение автоматизированного имитационного табличного моделирования (создания граф-машин) недетерминированных вычислительных алгоритмов.

6. Сформулированы и теоретически обоснованы требования к типовой структуре итерационной табличной модели алгоритма. Даны методологические рекомендации по разработке итерационных табличных моделей численных алгоритмов, определены перспективы и особенности их практического применения.

7. Разработаны математические модели статистической обработки экспертных оценок показателей качества участников электронных торгов и нелинейной динамики развития производственных фондов предприятия.

8. Разработана информационная технология имитационного моделирования алгоритмов в табличных процессорах. Определены и описаны процедуры и операции этой технологии.

9. На основе разработанной технологии реализованы алгоритмические и имитационные табличные модели:

• классических численных алгоритмов интерполяции, нахождения корней нелинейных уравнений, оптимизации, численного дифференцирования и интегрирования, решения дифференциальных уравнений и др.;

• динамических систем, описываемых обыкновенными дифференциальными уравнениями и их системами (начальная задача Коши);

• конечных автоматов, одно- и двумерных клеточных автоматов: «Муравей Лэнгтона», «Автоволны», «Одномерная диффузия», «ID-binary», «Generations», «Life», «Margolus», «Rules-Table», «Vote-for-Life», «Weighted-Life» и др.;

• генетических и эволюционных алгоритмов;

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

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

11. Обосновано, что ЭТ являются эффективной средой математического моделирования и визуализации вычислительных алгоритмов, включая нетривиальные алгоритмы искусственного интеллекта.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК

1. Аникина О.В. Алгоритмическое табличное моделирование в Microsoft Excel / В.И.Аникин, О. В. Аникина. - «Информатика и образование», 2008. - №9. - с. 49-54

2. Аникина О.В. Эффективная техника создания табличных моделей в Microsoft Excel / В.И.Аникин, О. В. Аникина. - «Информационные технологии», 2008. - №10. - с. 74-77

3. Аникина О.В. Алгоритмическое табличное моделирование в Microsoft Excel: итерационные модели / В.И.Аникин, О.В. Аникина. - «Информатика и образование», 2009. - № 9, с. 88-95

4. Аникина О.В. Табличное моделирование клеточных автоматов в Microsoft Excel / В.И.Аникин, О.В. Аникина. - «Информационные технологии», 2009. - № б, с. 23-28

5. Аникина О.В. Табличная имитация алгоритмов искусственного интеллекта / О.В. Аникина, П.Ф. Зибров. - Вектор науки ТГУ, №4 (14), 2010. с. 27-29

6. Аникина О.В. Алгоритмическое табличное моделирование динамики развития малого предприятия / В.И. Аникин, О.В. Аникина. - «Вестник Поволжского государственного университета сервиса. Серия Экономика», 2011. - № 3 (17). - с. 99-104

Монографии

7. Аникина О.В. Техника алгоритмического табличного моделирования в Microsoft Excel / В.ИАникин, О.В. Аникина. - Проблемы моделирования систем управления и разработки информационных технологий в промышленности, науке и образовании: Монография // Под ред. О.М. Горелик. - СПб: Изд-во «Инфо-да», 2009. - с. 369-431

8. Аникина О.В. Технологии имитационного табличного моделирования численных алгоритмов: Монография / О.В. Аникина, В.И. Аникин, П.Ф. Зибров. - Тольятти: ТГУ, 2011.-150 с.

Публикации в других изданиях

9. Аникина О.В. Создание моделей коллективного поведения в среде Microsoft Excel / В.И. Аникин, О.В. Аникина. - Синергетика природных, технических и социально -экономических систем: Сб. статей Международной научно - технической конференции, ч.1. - Тольятти: Изд-ство ТГУ С, 2007. - с. 119-124

10. Аникина О.В. Табличная реализация клеточного автомата «Муравей Лэнгтона» / О.В. Аникина, О.М. Горелик. - Состояние и перспективы развития инновационной деятельности в области сервиса: Сб. статей II международной научно-практической конференции, ч.Ш. - Тольятти: Изд-во ПВГУС, 200В. - с. 120-123

И.Аникина О.В. О возможности табличной реализации генетических алгоритмов в Microsoft Excel / В.И.Аникин, О.В. Аникина, Е.М. Звездилина. - Синергетика природных, технических и социально-экономических систем: Сб. статей V Международной научно-технической конференции. - Тольятти: Изд-во ПВГУС, 2008. - с, 78-84

12. Аникина О.В. Табличная модель искусственной нейронной сети RBF для классификации образцов / В.И.Аникин, О.В. Аникина, Е.М. Звездилина. - Наука - промышленности и сервису: Сб. статей Ш Международной научно-практической конференции, ч.1. -Тольятти: Изд-во ПВГУС, 2009. - с. 25-31

13. Аникина О.В. Табличное моделирование биофизических продукционных процессов в Microsoft Excel / В.И.Аникин, О.В. Аникина. - Синергетика природных, технических и социально-экономических систем: Сб. статей VI Международной научно-технической конференции. - Тольятти: Изд-во ПВГУС, 2009. с. 59-63

14. Аникина О.В. Табличное моделирование генетических алгоритмов в Microsoft Excel / О.В. Аникина, Е.М. Звездилина. - Проведение научных исследований в области обработки, хранения, передачи и защиты информации: Сб. научных трудов Всероссийской конференции с элементами научной школы для молодежи. -УлГТУ, 2009. - с. 278-286

15. Аникина О.В. О возможности табличной реализации нейронных сетей в Microsoft Excel / В.И. Аникин, О. В. Аникина. - Потенциал развития непроизводственной сферы в крупных промышленных городах Поволжского региона: взгляд молодых профессионалов: сб. ст. II международной научно - практической конференции. Ч. II / Поволжский гос. ун-т сервиса. - Тольятти, Изд-во ПВГУС, 2009. - с. 266-270

16. Аникина O.B. Электронная табличная модель выбора наиболее выгодного участника торгов на основе алгебраического объекта математического моделирования / О.В. Аникина, В.И. Аникин, П.Ф. Зибров. - Сборник трудов V Международной научной конференции «Математика. Образование. Культура». Ч. I / под общ. ред. P.A. Утеевой. - Тольятти: ТГУ, 2011. - с. 94-99

17. Аникина О.В. Информационные технологии имитационного моделирования / О.В. Аникина, В.И. Аникин, П.Ф. Зибров. - Формирование современного информационного общества - проблемы, перспективы, инновационные подходы: Материалы международного форума, Санкт-Петербург, 30 мая - 3 июня 2011 г. / ГОУ ВПО СПбГУАП, СПб., 2011. - с. 181-189

18. Аникина О.В. Имитационное табличное моделирование недетерминированного конечного автомата для распознавания слов в формальных языках / О.В. Аникина, В.И. Аникин, Б.Ф. Мельников - 6-я международная научно-техническая конференция «Информатизация процессов формирования открытых систем на основе СУБД , САПР, АСНИ, и систем искусственного интеллекта» (ИНФОС-2011), г. Вологда - с. 6-13

19. Аникина О.В. Опыт использования Microsoft Excel в лабораторном практикуме вузов / О.В. Аникина, В.И. Аникин, П.Ф. Зибров. - Инновации на основе информационных и коммуникационных технологий: Материалы международной научно-практической конференцию. / Под ред., С.У.Увайсова; Отв. за вып. И.А.Иванов, Л.М.Агеева, Д.А.Дубоделова, В.Е.Еремина-М.: МИЭМ, 2011 - 125-127 с.

20. Аникина О.В. Роль имитационного моделирования в дистанционном обучении / В.И. Аникин, О.В. Аникина. - Научно - методическое обеспечение инновационного развития образовательного учреждения: Сб. тезисов докладов научно - методического семинара. - Тольятти, Изд-ство ТГУС, 2008. - с. 122-124

21. Аникина О.В. Техника алгоритмического табличного моделирования в EXCEL / В.И. Аникин, О.В. Аникина. - Сб. тезисов докладов научно - методической конференции «Научно - методическое обеспечение инновационного развития образовательного учреждения», - Тольятти, 2007. - с. 211-214

22. Аникина О.В. Табличное моделирование спиральных автоволн с помощью клеточных автоматов / В.И.Аникин, О.В. Аникина. - Тезисы докладов VII Международной научно -технической конференции «Физика и технические приложения волновых процессов». -Самара, 2008. - с. 12-13

23. Аникина О.В. MS EXCEL как эффективная среда моделирования по дисциплинам естественного и экономического профилей / О.В. Аникина, Е.М. Звездилина. -Компетентностный подход в высшем профессиональном образовании: теория, технологии, проблемы применения: Сб. тезисов докладов Межвузовской научно-методической конференции. - Тольятти: Изд-во ПВГУС, 2009. - с. 240-242

Подписано в печать 10.01.2012. Формат 60x84/16. Печать оперативная. Усл. п. л. 1,4. Тираж 100 экз. Заказ №3-01-12.

Издательство Тольяттинского государственного университета 445667, г. Тольятти, ул. Белорусская, 14

61 12-5/1949

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тольяттинский государственный университет»

Аникина Оксана Владимировна

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ТАБЛИЧНЫХ ПРОЦЕССОРАХ

Специальность: 05.13.18- Математическое моделирование, численные методы и комплексы программ

на соискание ученой степени кандидата технических наук

На правах рукописи

ДИССЕРТАЦИЯ

научный руководитель: доктор технических наук профессор Зибров П.Ф.

Тольятти - 2012

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..............................................................................................................5

ГЛАВА 1. АЛГОРИТМИЧЕСКИЕ И ИМИТАЦИОННЫЕ МЕТОДЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ В ТАБЛИЧНЫХ ПРОЦЕССОРАХ...................................................................................................14

1.1. Достоинства и недостатки алгоритмического и имитационного моделирования в электронных таблицах.......................................................15

1.2. Графовые модели алгоритмов. Граф-машина алгоритма.....................18

1.3. Граф связей между ячейками табличной модели алгоритма...............22

1.4. Практическая реализация граф - машины алгоритма в электронных таблицах............................................................................................................25

1.5. Анализ типовых графов связей между ячейками имитационной табличной модели алгоритма..........................................................................28

1.6. Типы данных и переменные в имитационных табличных моделях алгоритмов........................................................................................................33

1.7. Процедуры и функции в имитационных табличных моделях алгоритмов........................................................................................................39

1.8. Численный метод приведения алгоритмов и программ, реализуемых в табличном виде, к детерминированному виду..............................................41

1.9. Автоматизированное создание имитационных табличных моделей алгоритмов........................................................................................................46

1.10. Выводы по главе 1...................................................................................54

ГЛАВА 2. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ИТЕРАЦИОННЫХ ВЫЧИСЛЕНИЙ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ...........................................55

2.1. Особенности выполнения множественных итераций в электронных таблицах............................................................................................................55

2.2. Теоретическое обоснование технологии создания итерационных табличных моделей..........................................................................................63

2.3. Типовая структура итерационных табличных моделей........................70

2.4. Анализ алгоритмов и программ, допускающих реализацию в виде имитационных табличных моделей...............................................................72

2.5. Выводы по главе 2.....................................................................................75

ГЛАВА 3. ТИПЫ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ИССЛЕДУЕМЫХ ОБЪЕКТОВ............................................................................................................76

3.1. Алгебраическая стохастическая модель экспертной оценки конкурсных заявок...........................................................................................76

3.2. Функциональные модели динамических систем и процессов.............79

3.3. Алгоритмические и имитационные табличные модели систем и процессов..........................................................................................................86

3.4. Выводы по главе 3.....................................................................................92

ГЛАВА 4. ПРОЕКТИРОВАНИЕ ТЕХНОЛОГИИ АЛГОРИТМИЧЕСКОГО И ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ .................................................................................................................................93

4.1. Структура информационной технологии имитационного табличного моделирования алгоритмов.............................................................................93

4.2. Процедура создания имитационной табличной модели алгоритма.... 96

4.3. Процедура анализа имитационной табличной модели алгоритма.... 103

4.4. Выводы по главе 4...................................................................................106

ГЛАВА 5. ПЕРСПЕКТИВЫ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ В ТАБЛИЧНЫХ ПРОЦЕССОРАХ.................................................................................................107

5.1. Имитационная модель вероятностной оценки показателей качества участников аукциона.....................................................................................107

5.2. Имитационное моделирование функциональных объектов динамических процессов...............................................................................109

5.2.1. Имитационное табличное моделирование динамики развития предприятия..........................................................................................114

5.2.2. Имитационное табличное моделирование конкурентного взаимодействия двух популяций........................................................117

5.3. Имитационное моделирование конечных и клеточных автоматов... 119

5.3.1. Имитационная табличная модель конечного автомата для распознавания слов формальных языков..........................................119

5.3.2. Имитационная табличная модель клеточного автомата «Жизнь».................................................................................................123

5.3.3. Имитационная табличная модель клеточного автомата «Муравей Лэнгтона»...........................................................................126

5.3.4. Имитационное табличное моделирование автоволн с помощью клеточного автомата............................................................................127

5.4. Имитационное моделирование генетических и эволюционных алгоритмов......................................................................................................128

5.5. Имитационное моделирование искусственных нейронных сетей.....132

5.6. Визуализация тонкой информационной структуры алгоритмов в электронных таблицах...................................................................................138

5.7. Выводы по главе 5...................................................................................141

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ......................................................143

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ...........................................146

ПРИЛОЖЕНИЕ...................................................................................................160

ВВЕДЕНИЕ

Актуальность темы. Анализ тенденций математического моделирования свидетельствует об эволюции процесса смены парадигм моделирования, представляющих несколько этапов. Первому этапу присуща математическая запись отдельных феноменологических наблюдений за объектами, отличающимися простотой математического описания, линейностью уравнений в одно- или двумерном пространстве. На следующем этапе осуществляется построение моделей, наиболее полно представляющих объект как систему, при этом математическая модель отражает его структуру и законы функционирования. Дальнейшее развитие математического моделирования приводит к информационно-технологическим комплексам и виртуальному моделированию электронно-вычислительными средствами. Таким образом, в математическом моделировании за последние десятилетия произошел качественный скачок как в разработке моделей и их верификации, так и в создании и использовании модельно-обоснованных методов анализа действительности. Академическое понимание и узкопрофессиональное математическое моделирование уступает место имитационным математическим моделям в научной и производственно-хозяйственной деятельности [50].

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

Последние достижения в области экономико-математического моделирования в электронных таблицах изложены в монографиях Л. Абдулазара, Ш. Беннинга, К. Берка, У.Л. Винстона, Б. Джелейна, А.Ф. Горшкова, А. Каплана, К. Карлберга, Д. Левина, Б.Ю. Левита,

А.В. Леоненкова, А.А. Минько, Дж. Мура, К. Олбрайта, JI.B. Уэйна и других. Значительно скромнее, в основном работами А.Н. Васильева, Р.Н. Вадзинского и Р.У. Ларсена, представлены их современные инженерно -технические применения.

Из анализа литературных источников следует, что по своим возможностям алгоритмическое и имитационное моделирование в электронных таблицах в ряде случаев уступает моделированию в специализированных программных средах, таких как GPSS или AnyLogic [55], однако оно имеет и свои очевидные преимущества:

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

2. квалифицированная разработка моделей в специализированных средах базируется на профессиональном опыте моделирования и представляет собой своего рода искусство, непривычное даже для программистов. Использование таких сред специалистами в конкретных предметных областях с целью самостоятельного создания практически значимых математических или имитационных моделей часто оказывается нерациональным;

3. любой интегрированный офисный пакет, например, Microsoft Office, имеющийся практически в любой организации, содержит табличный процессор, и сотрудники организации в той или иной степени владеют им, а специализированную систему моделирования необходимо приобрести, причем по достаточно высокой цене, и затратить значительные усилия и средства на ее освоение и сопровождение;

4. в ЭТ встроены мощные инструменты анализа, представления и визуализации данных, которые можно с успехом применять для интерпретации результатов моделирования и даже добавлять их непосредственно в созда-

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

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

Объектом исследования являются математические модели, комплексы программ, методы и средства алгоритмического и имитационного моделирования материальных, информационных и комбинированных систем и закономерностей природных явленийв табличных процессорах.

Предметом исследования являются теоретическое обоснование и разработка новых алгоритмических и имитационных методов моделирования статических и динамических систем и процессов в табличных процессорах.

Целью диссертационной работы является теоретическое обоснование и разработка методов алгоритмического и имитационного моделирования в табличных процессорах, их практическая реализация в задачах вычислительного характера.

Для достижения данной цели необходимо решить следующие задачи.

1. Исследовать особенности алгоритмического и имитационного моделирования в электронных таблицах в режимах одной и множественных итераций.

2. Обосновать и разработать структуру, принципы и состав технологии проектирования имитационных табличных моделей на основе алгоритмов решаемых задач.

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

4. Разработать комплекс программ для автоматизированного построения табличных моделей недетерминированных алгоритмов.

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

Направление исследований. Создание новых и совершенствование существующих технологий алгоритмического и имитационного моделирования статических и динамических процессов на основе электронных таблиц.

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

Научная новизна диссертационной работы заключается в следующих новых результатах.

1. Разработаны оригинальные математические модели статистической обработки экспертных оценок показателей качества участников электронных торгов и нелинейной динамики развития основных производственных фондов предприятия.

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

электронные таблицы на ведущее место среди других известных сред математического моделирования.

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

4. Предложен и опробован на практике оригинальный численный метод приведения недетерминированных алгоритмов и программ, содержащих условные операторы, к детерминированному виду.

5. Разработаны методология и программное обеспечение автоматизированного создания имитационных табличных моделей недетерминированных алгоритмов.

6. Экспериментально изучены нестандартные особенности и принципы создания итерационных табличных моделей, определена их типовая структура.

7. Теоретически обоснована и спроектирована технология создания алгоритмических и итерационных табличных моделей алгоритмов без написания программного кода.

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

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

Практическая значимость работы. Использование технологии имитационного табличного моделирования (ИТМ) алгоритмов дает возможность

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

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

Разработанная технология создания алгоритмических и имитационных моделей в электронных таблицах позволяет виртуализовать лабораторный практикум по многим дисциплинам естественно - научного и экономического профилей [7, 16], повышает эффективность учебного процесса в вузах, так как создаваемые табличные модели отличаются исключительной наглядностью, удобством анализа, выполнения экспериментов, визуального представления полученных результатов.

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

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

Реализация и внедрение результатов. По результатам диссертационного исследования изданы две монографии, три учебно - методических посо-

бия для студентов специальности 080801 «Прикладная информатика (в экономике)» ПВГУ�