Параллельные алгоритмы обработки больших данных иммитационного моделирования (стр. 4 )

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

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

       К основным этапам компьютерного моделирования относятся:

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

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

       2.1. Процессы порождения информации в системах имитационного моделирования

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

Имитационная модель должна отражать логику и закономерности поведения моделируемого объекта во времени (временная динамика) и пространстве (пространственная динамика).

       К имитационному моделированию прибегают, когда:

дорого или невозможно экспериментировать на реальном объекте; невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные; необходимо сымитировать поведение системы во времени.

       Цель имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов анализа наиболее существенных взаимосвязей между её элементами или другими словами — разработке симулятора исследуемой предметной области для проведения различных экспериментов. [5]

       Имитационное моделирование позволяет имитировать поведение системы во времени. При чём плюсом является то, что временем в модели можно управлять: замедлять в случае с быстропротекающими процессами и ускорять для моделирования систем с медленной изменчивостью. Можно имитировать поведение тех объектов, реальные эксперименты с которыми дороги, невозможны или опасны. С наступлением эпохи персональных компьютеров производство сложных и уникальных изделий, как правило, сопровождается компьютерным трёхмерным имитационным моделированием. Эта точная и относительно быстрая технология позволяет накопить все необходимые знания, оборудование и полуфабрикаты для будущего изделия до начала производства. Компьютерное 3D-моделирование теперь не редкость даже для небольших компаний.

Виды имитационного моделирования

Агентное моделирование — относительно новое (1990-е-2000-е гг.) направление в имитационном моделировании, которое используется для исследования децентрализованных систем, динамика функционирования которых определяется не глобальными правилами и законами (как в других парадигмах моделирования), а наоборот, когда эти глобальные правила и законы являются результатом индивидуальной активности членов группы. Цель агентных моделей — получить представление об этих глобальных правилах, общем поведении системы, исходя из предположений об индивидуальном, частном поведении её отдельных активных объектов и взаимодействии этих объектов в системе. Агент — некая сущность, обладающая активностью, автономным поведением, может принимать решения в соответствии с некоторым набором правил, взаимодействовать с окружением, а также самостоятельно изменяться. Дискретно-событийное моделирование — подход к моделированию, предлагающий абстрагироваться от непрерывной природы событий и рассматривать только основные события моделируемой системы, такие, как: «ожидание», «обработка заказа», «движение с грузом», «разгрузка» и другие. Дискретно-событийное моделирование наиболее развито и имеет огромную сферу приложений — от логистики и систем массового обслуживания до транспортных и производственных систем. Этот вид моделирования наиболее подходит для моделирования производственных процессов. Основан Джеффри Гордоном в 1960-х годах. Системная динамика — парадигма моделирования, где для исследуемой системы строятся графические диаграммы причинных связей и глобальных влияний одних параметров на другие во времени, а затем созданная на основе этих диаграмм модель имитируется на компьютере. По сути, такой вид моделирования более всех других парадигм помогает понять суть происходящего выявления причинно-следственных связей между объектами и явлениями. С помощью системной динамики строят модели бизнес-процессов, развития города, модели производства, динамики популяции, экологии и развития эпидемии. Метод основан Джеем Форрестером в 1950 годах.

       2.2. Вычислительные алгоритмы обработки последовательностей

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

Строковая последовательность — это набор элементов, которые удовлетворяют правилам:

Каждый элемент последовательности имеет уникальную метку. Каждый элемент с некоторой меткой х (за исключением не более одного элемента, который называется самый левый элемент) имеет единственный предшествующий элемент с меткой p(х). Каждый элемент с некоторой меткой х (за исключением не более одного элемента, который называется самый правый элемент) имеет единственный последующий элемент с меткой, s(х). Для любого элемента с меткой x, который не является самым левым, выполняется равенство

х = s(p(х)).

Для любого элемента с меткой х, который не является самым правым, выполняется равенство х = p(s(x)). Для двух различных элементов с метками х и у существует такое целое положительное число к, что х = sk(у) или х = pk(у).

       Эти правила охватывают сущность понятия сочленения и операции конкатенации, выполняющей это сочленение: каждый элемент последовательности, за исключением самого левого и самого крайнего элементов, имеет единственный предшествующий и единственный последующий элементы. Самый левый и самый крайний элементы имеют или единственного последующего, или единственного предшествующего элемента. Более того, начиная с любого элемента с меткой х мы, перебирая конечную последовательность предшествующих и последующих элементов, можем достичь любого другого элемента с меткой x. Критическим (но не очевидным) фактором этого определения являются условия в правилах 1 и 2, что может быть не более одного самого левого и не более одного самого правого элементов.

       

       2.3. Паттерны в последовательностях

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

       Будем различать три основных типа паттернов — частные, характеристические и внутренние. Частный паттерн (specific pattern) — это единственный вид паттернов, который можно задать в виде списка символов в нужном порядке. Например, в строке х — abaababaabaab мы можем найти (трижды) паттерн и = abaab, но не найдем паттерн и = ababab. (Иногда паттерн может содержать специальные "символы замещения", и в этом случае возможно только "приближенное" (в некотором точно определенном смысле) сравнение паттерна и строки.) Характеристические паттерны (generic patterns) основаны на специальных представлениях структурной информации о строковых последовательностях. Например, мы можем говорить о "повторениях" в строке х — в этом случае в строке х есть несколько смежных одинаковых подстрок. Внутренние паттерны отображают внутреннюю структуру строковых последовательностей. Паттерны формируют основу для эффективных процедур обработки строковых последовательностей.