Категории:

Дом Здоровье Зоология Информатика Искусство Искусство Компьютеры Кулинария Маркетинг Математика Медицина Менеджмент Образование Педагогика Питомцы Программирование Производство Промышленность Психология Разное Религия Социология Спорт Статистика Транспорт Физика Философия Финансы Химия Хобби Экология Экономика Электроника

Графы, деревья, фреймы и сети, нейронные сети, генетические алгоритмы

Моделирование

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

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

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

Существует два основных способа моделирования:

1. Физическое моделирование. Создается физическая копия объекта, на которой изучаются свойства/поведение объекта (проводятся испытания). Эта копия может копировать как объект целиком, так и только некоторые структуры объекта, требующие изучения. Также при физическом моделировании часто используются уменьшенные копии объекта (например макеты зданий/объектов, испытание моделей самолетов в аэродинамической трубе и т.п. ).

2. Информационное моделирование.

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

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

Пример. Рассматривая физическое тело, брошенное с высоты h и падающее свободно в течение t времени, можно записать соотношение: h = gt²/2 . Это физико-математическая модель системы (математическая модель физической системы) пути при свободном падении тела. При построении этой модели приняты следующие гипотезы: 1) падение происходит в вакууме (то есть коэффициент сопротивления воздуха равен нулю); 2) ветра нет; 3) масса тела неизменна; 4) тело движется с одинаковым постоянным ускорением g в любой точке.

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

Схема построения модели М системы S с входными сигналами X и выходными сигналами Y изображена на рисунке.

Рисунок – Схема построения модели

Если на вход М поступают сигналы X и на входе появляются сигналы Y, то задан закон, правило f функционирования модели, системы.

Классификацию моделей проводят по различным критериям.

Модель – статическая, если среди параметров описания модели нет (явно) временного параметра.

Модель – динамическая, если среди параметров модели явно выделен временной параметр.

Модель – дискретная, если описывает поведение оригинала лишь дискретно, например в дискретные моменты времени (для динамической модели).

Модель – непрерывная, если описывает поведение оригинала на всем промежутке времени.

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

Модель – функциональная, если представима системой функциональных соотношений (например, уравнений).

Модель – теоретико-множественная, если представима некоторыми множествами и отношениями их и их элементов.

Модель – логическая, если представима предикатами, логическими функциями и отношениями.

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

Модель – игровая, если она описывает, реализует некоторую игровую ситуацию между элементами (объектами и субъектами игры).

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

Модель – графовая (сетевая), если она представима графом (отношениями вершин и соединяющих их ребер) или графами и отношениями между ними.

Модель – иерархическая (древовидная), если она представима иерахической структурой (деревом).

Модель – языковая, лингвистическая, если она представлена некоторым лингвистическим объектом, формализованной языковой системой или структурой. Иногда такие модели называют вербальными, синтаксическими и т.п.

Модель – визуальная, если она позволяет визуализировать отношения и связи моделируемой системы, особенно в динамике.

Модель – натурная, если она есть материальная копия оригинала.

Модель – геометрическая, если она представима геометрическими образами и отношениями между ними.

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

Модель – алгоритмическая (математическая) – моделирование реализуется с помощью различных алгоритмов. Такое моделирование используется для объектов поведение/свойства, которых можно описать математически (изменение свойств, которых происходит по известным математическим/физическим закономерностям). Примеры: алгоритмы решения степенных уравнений, алгоритмы построения кривых в векторной графике, алгоритмы построения многогранных (объемных) объектов и моделирования отражения света в 3D графике, алгоритмы расчета тока/напряжения/сопротивления в сети и т.п.

Модель – статистическая – данные обрабатываются статистическими методами, такой вид моделирования используются для трудно формализуемых задач (сюда относятся «чисто статистические» методы и методы на основе распознавания образов).

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

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

Модель – черный ящик – если известны величины входов и выходов, а внутреннее содержание модели неизвестно.

Есть и другие типы моделей.

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

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

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

Основные свойства любой модели:

· целенаправленность;

· конечность;

· упрощенность;

· приблизительность;

· адекватность;

· информативность;

· полнота;

· замкнутость и др.

Жизненный цикл моделируемой системы:

· сбор информации;

· проектирование;

· построение;

· исследование;

· оценка;

· модификация.

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

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

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

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

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

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

производство: управление техническими и технологическими процессами и системами, ресурсами (запасами), планирование, прогнозирование оптимальных процессов производства и т.д.;

экология: моделирование загрязнения экологических систем, прогноз причинно-следственных связей в экологической системе, откликов системы на те или иные воздействия экологических факторов и т.д.;

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

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

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

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

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

туризм: моделирование и прогнозирование потока туристов, развития инфраструктуры туризма и др.;

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

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

Компьютерное моделирование – основа представления (актуализации) знаний как в компьютере, так и с помощью компьютера и с использованием любой информации, которую можно актуализировать с помощью ЭВМ.

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

Компьютерное моделирование от начала и до завершения проходит следующие этапы:

· постановка задачи;

· предмодельный анализ;

· анализ задачи;

· исследование модели;

· программирование, проектирование программы;

· тестирование и отладка;

· оценка моделирования;

· документирование;

· сопровождение;

· использование (применение) модели.

Экспертные системы

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

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

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

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

· диагностика неисправностей (как в технических системах, так и в человеческом организме);

· структурный анализ сложных объектов (например, химических соединений);

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

· планирование последовательности выполнения операций, приводящих к заданной цели (например, выполняемых промышленными роботами).

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

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

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

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

Метод частных целей

Этот метод имеет следующую общую формулировку: «Необходимо свести трудную задачу к последовательности более простых задач».

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

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

Пример. Имеется комплекс N=6 взаимосвязанных работ. Для каждой из N работ задана ее трудоемкость в человеко-часах. Необходимо расставить К=10 имеющихся в распоряжении рабочих так, чтобы длительность выполнения всего комплекса работ была минимальной. При этом не разрешается динамически (в ходе выполнения комплекса) перемещать рабочих с одной работы на другую.

Рисунок 1 – Сетевой график работ

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

Вершины графа представляют собой события, а дуги - работы.

Числа над дугами (работами) графа представляют собой трудоемкости работ. Множество полных путей для нашего графика: где

Общее количество вариантов расстановки рабочих в нашем случае равно .

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

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

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

Продолжительность выполнения всего комплекса работ, таким образом, получается равной 7 часам и определяется продолжительностью самого длинного из полных путей критическому пути I₁.

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

Путь I₁ состоит из работ (0,1), (1,3) и (3,5). Рассматривая постановку одного рабочего на одну из этих работ и сравнивая получающиеся варианты, выбираем из них вариант с наименьшей продолжительностью выполнения всего комплекса работ в нашем случае это будет постановка рабочего на работу (3,5). Таким образом, задача на добавление одного работника решена, и можно переходить к следующей задаче последовательности.

В общем случае, при поиске решения по данному методу придется проанализировать не более вариантов.

Метод подъема

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

Пример. Имеется предыдущая задача о расстановке рабочих.

Первым шагом является построение начального решения. В нашей задаче о расстановке рабочих начальным решением идет какая-либо расстановка рабочих по работам комплекса. Можно предположить много разных вариантов процедуры начальной расстановки. Рассмотрим одну из простейших. На первом шаге начальной расстановки примем , для любых i,j ([ ] - означает целую часть числа).

На втором шаге оставшееся количество рабочих К mod N распределяется так. Ставится один рабочий на работу с наибольшей трудоемкостью и, если резерв рабочих еще не исчерпан, ищется следующая по трудоемкости работа и проводится постановка очередного рабочего и т.д. Процесс заканчивается, когда резерв рабочих исчерпан. В рассматривавшемся примере расстановка может быть такой:

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

Тесты

1. К высшим уровням абстрактного описания систем относят:

1:символический

2:топологический

3:динамический

4:логико-математический

2. Метод исследования сложных вычислительных систем это:

1:Системный анализ

2:Математический анализ

3:Теория технических систем

4:Нечеткие логики

3. Новый объект, отражающий существенные особенности изучаемого объекта, процесса или явления, называют …

1:моделью

2:предметной областью

3:сущностью

4:языком представления знаний

4. К моделированию НЕЦЕЛЕСООБРАЗНО прибегать, когда …

1:не определены существенные свойства исследуемого объекта

2:процесс очень медленный

3:создание объекта чрезвычайно дорого

4:исследование самого объекта приводит к его разрушению

5. К основным формам представления информационных моделей НЕ ОТНОСЯТ

1:экономические

2:описательные

3:формально-логические

4:графические

6. Процесс описания объекта на искусственном языке называют ___________ объекта.

1:формализацией

2:семантическим анализом

3:синтаксическим анализом

4:компиляцией

7. В модели «черный ящик» система представляется как

1:совокупность функций входов и выходов

2:наиболее абстрактное представление структуры системы

3:совокупность связей между входами и выходами

4:совокупность состояний системы

8. На каком этапе осуществляется определение целей моделирования

1:постановка задачи

2:разработка концептуальной модели

3:разработка имитационной модели

4:разработка математической модели

9. Укажите число различных деревьев, которые можно построить на n нумерованных вершинах.

10. Выберите наиболее точное определение. Информационный процесс с известным начальным состоянием объектов, конечным состоянием, исполнителем и набором операций из системы команд исполнителя называется …

1:алгоритмическим процессом

2:моделированием

3:компиляцией

4:аналитическим процессом

11. Среди общепринятых классификаций видов моделей нет классификации …

1:«логические – сенсорные»

2:«статические – динамические»

3:«детерминированные – стохастические»

4:«дискретные-непрерывные»

12. Укажите наиболее точное определение. Модели типа «черный ящик» – это …

1:модели, описывающие зависимость выходных параметров объекта от входных без учета внутренней структуры объекта;

2:модели, описывающие зависимость параметров состояния объекта от входных с учетом структуры и закономерностей работы объекта

3:модели «аварийного» ящика на самолетах

4:модели мышления

5:модели, описывающие изменение выходных параметров объекта без связи со значением входных переменных

13. Укажите наиболее точное определение. Модель конечного автомата – это …

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

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

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

4:дискретная модель

5:модель станков-автоматов

14. Укажите содержательную модель:

1:милицейский протокол

2:имитационная модель

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

4:модель «черный ящик»

15. Какая модель системы изображена на рис.:

1:модель отношений

2:модель «черный ящик»

3:модель состава

4:модель переходов

16. Формализация задачи с использованием пространства состояний не включает:

1:алгоритм решения

2:формы описания состояний

3:множество операторов перехода из состояния в состояние

4:свойства целевых состояний

17. Метод решения задач, при котором объекты разного рода объединяются общим понятием (концепцией), а затем сгруппированные сущности рассматриваются как элементы единой категории:

1:абстрагирование

2:декомпозиция

3:индукция

4:структуризация

18. Деревья , списки, хэш-адресация – это…

1:структуры данных

2:модели предметной области

3:условия вывода

4:типы информации

19. Изменение концентрации соли в растворе пропорционально самой концентрации. Самая подходящая для описания процесса модель, описывающая изменение концентрации во времени, …

1:относится к классу непрерывных динамических моделей и имеет вид дифференциального уравнения (с независимой переменной времени)

2:относится к классу непрерывных статических моделей и имеет вид дифференциального уравнения (с независимой пространственной переменной)

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

4:относится к классу дискретных динамических моделей и имеет вид модели конечного автомата

20. Самая подходящая математическая модель, с помощью которой может быть описана (задана) работа обычного уличного светофора – это модель …

1:детерминированного конечного автомата

2:описываемая системой дифференциальных уравнений

3:описываемая системой алгебраических уравнений

4:вероятностного автомата

21. Задача коммивояжера (объехать все пункты из списка по разу и вернуться так, чтобы преодоленное расстояние было бы минимальным) формализуется проще всего с использованием языка …

1:описания графов

2:представления знаний

3:алгоритмического

4:программирования

5:баз данных

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

1:гамильтоновым

2:эйлеровым

3:ориентированным

4:полным

23. Задача «Обслуживание станков мостовыми кранами» является задачей

1:массового обслуживания

2:управления запасами

3:сетевого планирования

4:календарного планирования

24. Задача моделирования эволюции реализуется

1:на основе генетических алгоритмов

2:с использованием нейронных сетей

3:алгоритмами нечеткой логики

4:интеллектуальными программными агентами

25. Одна из моделей для описания простейшей лотереи типа «Спринт» (тянешь билет и сразу проверяешь) – это модель …

1:вероятностного автомата

2:детерминированного автомата

3:системы массового обслуживания

4:динамической системы

5:случайного блуждания

26. К естественному представлению алгоритма относят:

1:блок-схема

2:ER-диаграмму

3:язык PASCAL

4:рекурсивные функции

27. Можно ли считать формальным исполнителем алгоритма следующие устройства:

1:графический редактор

2:кодовый замок

3:телефон с памятью для записи номеров

4:принтер

28. Формализация задачи с использованием пространства состояний не включает:

1:алгоритм решения

2:формы описания состояний

3:множество операторов перехода из состояния в состояние

4:свойства целевых состояний

29. Метод познания, состоящий в исследовании объекта на его модели, называют ..

1:моделированием

2:логическим выводом

3:исчислением предикатов

4:имитацией

30. К основным классам моделей (по способу отражения свойств объекта) относят …

1:предметные

2:социальные

3:медико-биологические

4:территориальные

31. В представлении алгоритма не существенна

1:трудоемкость

2:понятность

3:наглядность

4:однозначность