Перебор с возвратами

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

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

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

• Выполняется цикл, в котором

  • Перебираются допустимые значения текущей переменной

  • Для каждого значения переменной производится вызов процедуры решения задачи

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

Методы сокращения перебора: эвристики, метод ветвей и границ, динамическое программирование.

Эвристика(др.-греч.ευρίσκω «отыскиваю», «открываю») — наука, изучающаятворческуюдеятельность, методы, используемые при открытии новых концептов, идей и взаимосвязей между объектами и совокупностями объектов, а также методики процесса обучения.Эвристические методы(другое названиеэвристики) позволяют ускорить процесс решения задачи.

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

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

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

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

Метод используется для решения некоторых NP-трудныхзадач, такие как:

• Задача коммивояжера

• Задача о ранце

Динамическое программирование в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб» (brute force).

Словосочетание динамическое программирование впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

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

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

1. Разбиение задачи на подзадачи меньшего размера.

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

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачив динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычислениепоследовательности Фибоначчи,F₃=F₂+F₁иF₄=F₃+F₂— даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчиталиF₂дважды. Если продолжать дальше и посчитатьF₅, тоF₂посчитается ещё два раза, так как для вычисленияF₅будут нужны опятьF₃иF₄. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.

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

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

• перекрывающиеся подзадачи;

• оптимальная подструктура;

• возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов, чтобы убыстрить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme,Common Lisp,Perl), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального динамического программирования, когда графвзаимосвязей переменных — просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/илицелевую функциюкак рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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

Классические задачи динамического программирования

• Задача о наибольшей общей подпоследовательности

• Задача поиска наибольшей увеличивающейся подпоследовательности

• Задача о редакционном расстоянии (Расстояние Левенштейна)

• Задача о Вычислении чисел Фибоначчи

• Задача о порядке перемножения матриц

• Задача о выборе траектории

• Задача последовательного принятия решения

• Задача об использовании рабочей силы

• Задача управления запасами

• Задача о ранце

• Задача поиска кратчайшего пути в сети

• Алгоритм Флойда-Уоршелла

• Максимальное независимое множество вершин в дереве

20. Деревья. Свойства деревьев. Двоичные деревья. Планарные графы. Формула Эйлера.

Дерево — связный граф без циклов (=> и без множественных рёбер, и без петель).

Каждый связный граф содержит в себе дерево покрытия.

Для дерева верно:

1) для каждой пары разл. вершин существует единственный путь, их соединяющий;

2) удаление любого ребра из T приводит к появлению 2-х компонент связности.

3) |E| = |V| - 1.

--------

Корневое дерево — дерево (T,V*), у к-рого есть особая вершина (V*), отличающаяся от остальных.

Лист в корневом дереве — вершина, валентность к-рой = 1, не совпадающая с V*.

Вершина решения или внутренняя вершина — вершина, отличная от листа и V*.

Уровень вершины v для корневого дерева — длина пути, соединяющего v с V*.

--------

Двоичные деревья (L,S,R), где L и R — двоичные деревья, а S содержит только V*.

Деревья юзают для сортировки (дерево сортировки заполняют, а потом считывают в список).

Планарные

Граф — плоский, если его вершины лежат на плоскости, а рёбра — линии или дуги на плоскости — не пересекаются.

Граф — планарный, если он изоморфен плоскому.

Ф-ла Эйлера: |F| = |E|-|V|+2

|E| — кол-во рёбер

|V| — кол-во вершин

|F| — кол-во граней

Очевидно выполняется для деревьев.

-P: (индукция по числу рёбер n)

1) Пусть n=0 — одна вершина v. Рёбер — 0; грань — одна.

2) Предположим, что верно для |E| < n;

3) Если Г — дерево (тогда выполняется);

Если Г — не дерево, то у него есть цикл. Уберём в этом цикле ребро. По шагу 2 выполняется |F| = |E|-|V|+2. Добавим ребро. Равенство сохранится, т.к. грань++, ребро++: |F+1| = |E+1|-|V|+2

--------

K_(3,3) и K_5 непланарны (идёт отдельным вопросом)

--------

Если граф Г имеет подграфом K_(3,3) или K_5, то он непланарен.

Для того, чтобы конечный граф Г имел планарную реализацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен ни одному из графов K_(3,3) и K_5.

Графы Г1 и Г2 гомеоморфны, если существуют их подразделения, к-рые изоморфны.

Подразделение — построение нового графа, мн-во вершин к-рого = V U {v} и мн-во рёбер = {(vi,v),(vj,v)} U E \ {vi,vj}, v — новая вершина, vi,vj — старые.

Vi*-----*Vj ->

Vi*---*(v)----*Vj

--------

Для определения гомеоморфизма графов из них можно последовательно удалять 2-х валентные вершины.

--------

Св-ва:

1)Г — связный планарный граф, без петель и множественных рёбер =>

|E| <= 3|V| - 6.

-P:

3|F| <= 2|E|, но |F| = 2 - |V| + |E| => 3(2 - |V| + |E|) <= 2|E| => |E| <= 3|V| - 6.

2) В любом планарном графе существует вершина, валентность к-рой <= 5.

-P: (от противного)

Пусть для всех Vi € V. Сигма(валентность)(Vi) >= 6. => 6|V| <= SUM(Vi € V)(Сигма(Vi)) = 2|E|. => 3|V| <= |E|

Из св-ва (1) =>3|V| <= 3|V| - 6. Что неверно. => неверно предположение. => верно св-во.

K5, K3,3

Непланарность:

K33:

Предположим, что K33 — планарный. Разбивает пл-сть, на к-рой лежит, на |F| граней. Каждая грань отсечена замкнутой последовательностью рёбер, состоящей минимум из 4-х рёбер. С другой стороны, каждое ребро грани представляет собой часть границы раздела двух граней.

=> 2|E| >= 4|F|

По т. Эйлера, 2|E| >= 4(|E|-|V|+2)

2*9 >= 4(9-6+2)

18 >= 20 неверно => предположение неверно => K33 не является планарным

K5 (пентограмма в пентакле):

Предположим, что K5 — планарный. Разбивает пл-сть, на к-рой лежит, на |F| граней. Каждая грань отсечена замкнутой последовательностью рёбер, состоящей минимум из 3-х рёбер. С другой стороны, каждое ребро грани представляет собой часть границы раздела двух граней.

=> 2|E| >= 3|F|

2|E| >= 3(|E|-|V|+2)

2*10 >= 3(10-5+2)

20 >= 21 неверно => предположение неверно => K5 не является планарным.

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

В логике высказываний (ЛВ) рассматрив-ся предложения, отн-но к-ых м. однозначно сказать явл-ся ли они истинными или ложными. Такие предл наз-ся высказываниями.

X,y,z– переменные высказывания, они м. принимать значения истина или ложь.

Над высказываниями м .вып-ть разл. Логич. Операции и получать новые высказывания:

1. кконъюнкция (^) – операция, с пом кот м.построить новое высказывание х^y, из к-го истинность опр-ся след.образом:данное высказывание истинно только тогда, когда оба выск х и у б.истинны.

^ обычно наз-ся логическим умножением.

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

3. импликация (→) – оп, с пом к-ой для высказываний х и у м. построить новое высказ х→у, к-е принимает значение ложь тогда, когда х – истина, а у – ложь.

4. эквиваленция(↔) – оп, с пом к-ой м.построить новое выск-ние х↔у, истинность к-го опр-ся сл.образом: оно истинно только тогда, когда х и у принимают одинакове зна-я истинности.

5. отрицание(⌐,−) – оп, с пом к-ой строится новое выск х (с чертой)(отрицание х), истинность к-го опр-ся сл.образом: если х – истина. То новое выск – ложно. И наоборот

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

Т.о. приходим к понятию формулы высказываний(ФЛВ)

Исп-ся сл. Договоренности:

1 по силе лог оп будут вып-ся в след.порядке, если нет скобок: ^,v,→,↔

2 внешние скобки в формуле м.опускать

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

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

Такие формулы наз-ся законами АВ:

1 х≡х (х равносилен сам себе)

2 x(cдвойным отрицанием)≡х

3 xvл≡х, х^и≡х,xvи≡и, х^л≡л

4 переместительный закон: х^у≡ у^х, xvу≡ уvх

5 (х↔у)≡(х→у)^(у→х)

С пом законов AИ м.переходить от одной формулы к др, делая при этом равносильные преобразования.

Проблема разрешимости в АВ формулируется сл.образом: можно ли указать а-м для любой формулы АВ, с пом к-го м.опр-ть явл-ся ли ф-ла тождественно истинной, тождественно ложной или только выполнимой.

Опр. Ф-ла тожд-но истинна, если она принимает зн-е истинна на любом наборе переменных высказываниих х1,х2, …, хn

Опр. Ф-ла тожд-на л, если она принимает зн-е ложь на любом наборе пер-ys[

Опр. Ф-ла выполнима, если существует хотя бы один набор зн-ний пер-ys[? От к-ых щависит ф-ла. На к-ом ф-ла принимает зн-е и.

Проблема разрешимости решается в АВ положительно. М.указать неск-ко таких а-мов:

1) построение таблицы истинностей

2) связан с равносильными преобразованиями (СДНФ, CRYA)

Опр. Элементарная ^ - ф-ла АВ, к-ая предст собой ^ переменных или их отрицаний

Опр. ДНФ (диз.нормальная форма) – ф-ла АВ, к-ая предст.собой дизъюнкцию элем-х ^.

Опр. Элементарная дизъюнкция - ф-ла АВ, к-ая предст собой диз. переменных или их отрицаний.

Опр. КНФ - – ф-ла АВ, к-ая предст.собой ^ элем-х дизъюнкций.

Пр-р: (х vу) ^ (zvt)

Среди мн-ва ф-л выд-ют:

1. СДНФ – ф-ла, к-ая обладает след.св-ми:

   1. явл ДНФ

   2. элемент. ^ различны

   3. элем-ная ^ сод-ит ровно nэлементов

Смысл: любая ф-ла АВ, если она не явл-ся тожд-но л, м.б. однозначно приведена к СДНФ.

По аналогии CКНФ

СКНФ – ф-ла, к-ая обладает след.св-ми:

1. явл КНФ

2. элемент. диз различны

3. элем-ная диз сод-ит ровно nэлементов

Смысл: любая ф-ла АВ, если она не явл-ся тожд-но и, м.б. однозначно приведена к СКНФ.

Рассмотрим построение СДНФ и СКНФ по таблице истинностей(на пр-ре F(x,y,z))

А-м построения СДНФ:

1) Выбираем в таблице строки, в к-ых ф-ла принимает зн ИСТИНА (1,2,4,7)

2) Для каждой из выделеннх строк строим элем ^

1 – x^y^z2 –x^y^⌐z4 - ⌐x^y^z7 – ⌐x^⌐y^z

3) Построенные элем. ^ объединяют операцией дизъюнкция.

Получаем СДНФ:

(x^y^z)v(x^y^⌐z)v(⌐x^y^z)v(⌐x^⌐y^z) – СДНФ

А-м построения СКНФ:

1) Выбираем в таблице строки, в к-ых ф-ла принимает зн ЛОЖЬ (3,5,6,8)

2) Для каждой из выделеннх строк строим элем диз (если переменная истинна, то с отрицанием)

3 – ⌐xvyv⌐z5 – ⌐xvyvz6 –xv⌐yvz8 –xvyvz

3) Построенные элем. диз строим КНФ. Получаем СКНФ:

(⌐xvyv⌐z)^( ⌐xvyvz)^(xv⌐yvz)^(xvyvz) – СКНФ

С пом.СДНФ ф-лу м.исследовать на проблему разрешимости: если ф-ла от nпеременных явл СДНФ, то ф-ла не явл тожд-но Л. Если она сод-т 2ⁿэлем-х ^, то ф-ла тожд.И. Если сод-т < 2ⁿ- ф-ла выполнима

С пом CКНФ м. исследовать на проблему разрешимости : еслиCКНФ построена, то ф-ла не явл тожд-но И. Если она сод-т 2ⁿэлем-х диз, то ф-ла тожд.И. Если сод-т < 2ⁿ- ф-ла выполнима

22. Исчисление высказываний. Выводимость формулы в исчислении, выводимость формулы из гипотез. Теорема дедукции, ее следствие. Автоматическое доказательство теорем. Метод резолюций в исчислении высказываний: правило резолюций, понятие резолютивного вывода.

23. Предикаты. Основные операции над предикатами. Исчисление предикатов. Интерпретации. Общезначиммость. Метод резолюций для исчисления предикатов.

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

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

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

Слово "Модель" происходит от латинского modus (копия, образ, очертание). Моделирование - это замещение некоторого объекта А другим объектом Б. Замещаемый объект А называется оригиналом или объектом моделирования, а замещающий Б - моделью. Другими словами, модель - это объект-заменитель объекта-оригинала, обеспечивающий изучение некоторых свойств оригинала.

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

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

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

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

Все модели можно разделить на два класса:

1.вещественные,

2.идеальные.

В свою очередь вещественные модели можно разделить на:

1.натурные,

2.физические,

3.математические.

Идеальные модели можно разделить на:

1.наглядные,

2.знаковые,

3.математические.

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

Вещественные физические модели - это макеты, муляжи, воспроизводящие физические свойства оригиналов (кинематические, динамические, гидравлические, тепловые, электрические, световые модели).

Вещественные математические - это аналоговые, структурные, геометрические, графические, цифровые и кибернетические модели.

Идеальные наглядные модели - это схемы, карты, чертежи, графики, графы, аналоги, структурные и геометрические модели.

Идеальные знаковые модели - это символы, алфавит, языки программирования, упорядоченная запись, топологическая запись, сетевое представление.

Идеальные математические модели - это аналитические, функциональные, имитационные, комбинированные модели.

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

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

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

В общем случае математическая модель реального объекта, процесса или системы представляется в виде системы функционалов

Ф_i (X,Y,Z,t)=0,

где X - вектор входных переменных, X=[x₁,x₂,x₃, ... , x_N]^t,

Y - вектор выходных переменных, Y=[y₁,y₂,y₃, ... , y_N]^t,

Z - вектор внешних воздействий, Z=[z₁,z₂,z₃, ... , z_N]^t,

t - координата времени.

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

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

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

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

По принципам построения математические модели разделяют на:

1.аналитические;

2.имитационные.

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

Аналитическая модель разделяется на типы в зависимости от математической проблемы:

1.уравнения (алгебраические, трансцендентные, дифференциальные, интегральные),

2.аппроксимационные задачи (интерполяция, экстраполяция, численное интегрирование и дифференцирование),

3.задачи оптимизации,

4.стохастические проблемы.

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

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

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

1.детерминированные,

2.стохастические.

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

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

По виду входной информации модели разделяются на:

1.непрерывные,

2.дискретные.

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

По поведению моделей во времени они разделяются на:

1.статические,

2.динамические.

Статические модели описывают поведение объекта, процесса или системы в какой-либо момент времени. Динамические модели отражают поведение объекта, процесса или системы во времени.

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

1.изоморфные (одинаковые по форме),

2.гомоморфные (разные по форме).

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

Для построения математической модели необходимо:

1.тщательно проанализировать реальный объект или процесс;

2.выделить его наиболее существенные черты и свойства;

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

4.описать зависимость основных свойств объекта, процесса или системы от значения переменных с помощью логико-математических соотношений (уравнения, равенства, неравенства, логико-математические конструкций);

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

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

Математическое моделирование, кроме исследования объекта, процесса или системы и составления их математического описания, также включает:

1.построение алгоритма, моделирующего поведение объекта, процесса или системы;

2.проверка адекватности модели и объекта, процесса или системы на основе вычислительного и натурного эксперимента;

3.корректировка модели;

4.использование модели.

Математическое описание исследуемых процессов и систем зависит от:

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

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

Моделирование физических процессов

- задача об остывании

- падение без сопротивления

- падение с сопротивлением

- двумерные траектории

- задача Кеплера

- маятник

- линейный осциллятор

Пример:

Груз на пружине.

25. Имитационное моделирование. Клеточные автоматы. Моделирование случайных процессов. Компьютерное моделирование в экологии. Подходы к моделированию сложных систем.

Имитационное моделирование

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

Имитационные модели - это проводимые на ЭВМ вычислительные эксперименты с математическими моделями, имитирующими поведение реальных объектов, процессов или систем.

Реальные процессы и системы можно исследовать с помощью двух типов математических моделей: аналитических и имитационных.

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

Имитационное моделирование представляет собой численный метод проведения на ЭВМ вычислительных экспериментов с математическими моделями, имитирующими поведение реальных объектов, процессов и систем во времени в течении заданного периода. При этом функционирование РПС разбивается на элементарные явления, подсистемы и модули. Функционирование этих элементарных явлений, подсистем и модулей описывается набором алгоритмов, которые имитируют элементарные явления с сохранением их логической структуры и последовательности протекания во времени.

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

Клеточные автоматы

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

Игра «Жизнь»

Джон Конуэй (1970). Клеточный автомат является квадратной регулярной решеткой. Каждая ячейка может находиться в одном из двух состояний – живая и мертвая. Состояние клетки на след. шаге определяется только ее ближайшим окружением (8 соседей). Если у пустой клетки ровно 3 живых соседа, то на след. шаге в ней появляется жизнь. Если у живой клетки меньше 2-х либо больше 3-х живых соседей, то на след. шаге она умирает.

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

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

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

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

- Модель может служить образцом «идеального объекта» или идеализированного поведения, при сравнении с которым можно оценивать и измерять реальные объекты и процессы.

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

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

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

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

1. Традиционное математическое моделирование без привязки к инф-ке.

2. Инф-ионные модели и моделирование, имеющие приложения в ИС.

3. Вербальные (описательные).

4. Инф-ионные технологии.

Математическая модель– исследование математического объекта а′ реального объекта а, которое должно дать инф-ию о сов-ти свойств объекта а.

Компная модель– это математическая модель, перенесенная на комп и реализованная с его помощью.

А-м построения модели:

1)Исходный объект;

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

3)Построение содержательной модели;

4)Построение математической модели;

5)Выбор метода исследования;

6)Разработка программы для ПК;

7)Отладка программы;

8)Тестовые расчеты;

9)Анализ результатов (если нормально, то модель готова, если нет – пункт 3);

На практике все задачи обычно делятся на 2 большие группы:

1.Прямые задачи, направленные на достижение конкретной цели.

2.Обратные задачи. Пытаются по виду явления восстановить источник.

Классификация моделей. Все модели делятся на группы:

1.стр-рные (объекты, стр-ра которых известна) и функциональные (черный ящик).

2.Дискретные (время дискретно) и непрерывные (время непрерывно).

3.Линейные/нелинейные.

4.Детерминированные (объекты действуют по заранее определенным правилам).

5.Вероятностные (поведение может изменяться случайным образом).

Требования к моделям:

1. Адекватность модели (правильное качественное описание и правильное количественное описание);

2. Инф-ионная достаточность (существует минимальный набор сведений, необходимых для построения модели объекта);

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

4. Достаточная простота (модель должна быть настолько простой, насколько это возможно);

5. Осуществимость (достижение цели за поставленное время);

6. Обезразмерование (при построении модели следует использовать относительные/безразмерные величины);

7. Параметризация – некоторые подсистемы в модели м.б. заменены constбез описания функционирования этих систем.

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

9. Продуктивность – все необходимые исходные данные можно измерить;

10. Наглядность – все параметры модели имеют простой физический смысл.

Моделирование случайных процессов.

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

Конгруэнтный метод. Предложен Лемером. Очередное случайное числоx_nопределяется через предыдущее по линейному закону:x_n=(a*x_n+1+c)modm, гдеa,c,m– натуральные числа. Наибольший возможный период равенm. Количество неповторяющихся элементов, выдаваемых генератором, называется периодом.i≤T≤m.

Генератор Фибоначчи. Для задания 1-х семнадцати значений пользуются другим генератором. Значения сохраняются в массиве

A[1..17] of real;

i:=17; j:=5;

x:=a[i]-a[j];

if x<0 then x:=x+1;

a[j]:=x;

dec(i); dec(j);

if i=0 then i=17;

if j=0 then j=17;

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

Дано: пруд. Вычислить: площадь пруда.

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

N₀/N≈a*b/S_пруда→N*a*b/N₀. При небольшом числе попыток, площадь пруда ≈N*a*b/N₀.

Реализация на компе: если точка под кривой, то N=N+1.

Метод фон Неймана. Нужно сгенерировать случайные числа с некоторой нормированной функцией распределенияf(x) на интервале [a,b]. Метод фон Неймана – метод отбора отказов. Генерируются два случайных числа, определяющих равновероятные координаты в прямоугольнике с помощью датчика случайных чисел.

r:=random;

x:=a+(b-a)*r;

y:=f(max)*r.

Если точка не попадает под кривую f(x), мы ее отбрасываем, а если попадает – оставляем. Метод эффективен, когдаf(max) близко кf(x).

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