Лекция: Клеточные автоматы. Одномерный и двумерный случаи. Игра “Жизнь”.

Кл.Авт. — это абстракция сообщества некотор. элементарных объектов, м/у которыми возможен обмен информацией.– модель поведения клеточных сообществ(ФонНейман).–дискретн. динамич. с-ма (предст-ет собой совокупность клеток, одинаковым образом соед-х м/у собой-решетка клеточного автомата) Основными характеристиками являются: 1) дискретность в прост-ве, сущ-ют др. с др. но каждый занимает свой кант а прост-ве. 2) Развитие такого сообщ. со временем происходит скачками, дискретно. Предложил Дж.Ф. Нейман. Исследование клеточн. автоматов приводят к частичному раскрытию тайн самоорганизации в живой природе. Современ. наука синергетика. Одномерн. клеточ. авт-ты для каждой клетки рассматр. 2х соседних слева и справа(5кл.)Среди м.б. как мертвые(0) так и живые(1).Правила1) В следующий момент времени клетка б. жива если у неё жив ровно одна соседн. клетка. Двумерные клет-е авт-ты (поле неогран-но), к-я клетка м. находиться в конечном числе сост-й.Изменен. знач-я всех клеток происходит одновременно.

Рассм-им кл.авт. у которого положение клетки определяется одной коорд. Будем считать, что в момент времени клетки находились в каком-то состоянии, 1-жива, 0-мертва.

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

В одномерном случае берутся два соседа справа и два слева. Вычисляем сумму состояний соседей и смотрим по правилам

S=A[i-2]+ A[i-1]+ A[i]+ A[i+1]+ A[i+2]

В двумерном случае берутся соседи окружающие клетку со всех сторон (8 штук). Берём сумму и смотрим состояние по пр-лам. Вывод на экран живых в виде квадратов

15,Моделирование в физике. Физика – это наука, в кот-й моделирование явл. важным методом исследования. Раньше физика делилась на экспер-ю и теор-ю физику, а сейчас + вычислительная физика. В физику проникли различ мат методы, но многие задачи нельзя решить с пом мат модели, следует совмещать вычислит матем-у и проведение вычислительного экспер-та, кот-й схож с лабораторным. Этапы построения модели: 1)постановка задачи; 2) Мат модель 3) Вычисл модель 4)Комп модель 5) Работа с моделью

Модель Солнце-планета.1. Постановка задачи.В космическом пространстве находится массивное тело «Солнце». В некоторый момент времени t в поле его тяготения влетает с некоторой скоростью V тело меньшей массы m и меньших размеров — планета. Проследить судьбу этого тела( нарисовать траекторию планеты).

2.Построить мат модель движения планеты в поле тяготения Солнца.

— з-н всемирного тяготения.

— II з-н Ньютона.

, то:

х(0)=a1, у(0)=a2,,,

х(0)=a1,

у(0)=a2,

3.Переход к вычислительной модели .

Выберем значение шага h

Рассмотрим систему точек tj=j×h j=1,2,3,… .

xj+1-2xj+xj-1=G(tj)xjh2

yj+1-2yj+yj-1=G(tj)yjh2

j=1,2,...

4.Компьютерная модель.

DIM x,y(N)

1. Провести масштабирование.

2. Проверка 3х типов движений.

а) по орбите.

б) за пределы.

в) упадет.

5.Работа с программой.

Шаг h=0,1

1. Построение компьютерной модели позволяет глубоко войти в сущность представлений модели.

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

Баллистическая модель. 1. Постановка: Пушка под углом к горизонту. Из нее вылетает снаряд с нач. скоростью(v0). Сопр. Нет. Построить траекторию движения.

2. Мат модель

Модель падение тела в среде с сопротивлением.Тело находиться на высоте Н, тело отпускают, оно нач-ет падать. Ему придали нач. скорость. При относительно малых скоростях величина силы сопр-ия пропорциональна ск-ти, а при более высоких скоростях сила сопрот-я пропор-а квадрату скорости.

Fсопр=kV

Требуется выполнить моделирование тела.Нас интерисует не траектория, а тело, с какой оно скоростью падает.

1) X0=0 X’0=0

2) рисунок

3) F=mg

ma=mg+ Fсопр

4) max=mg-kvx2

mx’’(t)=mg-km(x’(t))2

5)Выбираем ∆t.Разбиваем ось времени на равностоящие промежутки. Запишем вторую и первую производные формы. Выражаем x(tk+1)

m(x(tk+1)- 2x(tk)+ x(tk+1))/ ∆t2)=mg- k((x(tk)- x(tk+1))/ ∆t2)2

x(tk+1)=(mg- k((x(tk)- x(tk-1))/ ∆t2)/m-m((x(tk-1)-2x(tk))/ ∆t2)

X(t1) =x(0)+ X’(0) ∆t

x(t1) =0

Замечание: до каких пор мы должны проводить расчеты x(t)>=H.

Задача линейного програмит-я. Методы её решения.

Имеем n-управляющих переменных: х1, х2,…, хn. Есть целевая функция: F=c1x1+c2x2+…+cnxn стремится к max (min). Треб-ся найти её max (min), если переменные с1…сn удовлетв-т линейным ограничениям:

а11х1+а12х2+…а1nxn>=b1

а21х1+а22х2+…а2nxn>=b2

…………

аk1х1+аk2х2+…аknxn<=bk

……..

аp1х1+аp2х2+…аpnxn=bp

Если все огр-я имеют вид нерав-в, то их геометрич. смысл закл-ся в пересечении полуплоскостей (n=2), полупространств(n=3), полугиперпр-в (n>3) и образовании ОДР – многогранник. Сущ-ет 2 теоремы для задач ЛП. Т1: ОДР – выпуклое множ-во (если оно вместе с 2я точками сод-т отрезок, их соединяющих). Точка наз-ся крайней, если в обл-ти нет точек, м-у кот-ми она лежит. Т2: Если ЗЛП имеет оптимальн реш-е, то линейн. ф-я принимает max (min) зн-е в 1й из крайних точек ОДР. Если max (min) достиг-ся > чем в 1й крайней точке, то он ддостиг-ся в любой точке, явл-ся их выпуклой линейной комбинацией. (n=3, реш-е > чем в 1й точке, то реш-м явл-ся точка, ребро или грань).

1)Графич.метод: исп-ся только в том случ-е, когда число переменных n=2. Алгоритм решеня: А) в осях ХОУ построить обл-ть допустимых решений (ОДР), т.е. построить все линии из ограничений и найти обл-ть их пересечения. Б) Построить линии уровня целевой ф-ии(F=0, F=1,F=4,..). В) Двигаем линию ур-я целев. Ф-ии в нухном напр-ии к max (min) пока есть хотя бы 1а общая точка с ОДР. Координаты точки = значению F. Возможные ситуации: А) ОДР – пустое множ-во, решений нет. Б) ОДР – точка, допустимое реш-е единственное и оптимальное. В) ОДР – неогр-е множ-во, в завис-ти от max (min) либо оптимальн. реш-я нет, либо оно есть. Г) решением м.быть те точка, а отрезок, когда линия F совпадает с гранью, оптмальн. Реш-й бесконечно много, х принадлежит интервалу.

2) Переборный метод: по Т2 необход. перебрать все вершины. Коорд-ы кажд. Вершины подставляем вцедевую ф-ю, вычисляем знач-я и выбираем ту, в кот F принимает max (min). А) n=2: будем перебирать по 2е прямые из ограничений различными способами и считать для них, получ. Коорд. Вершины подставляем в остальн. огр-я. Если удовлетворяет всем, то это вершина. Из всех вершин выбираем ту, в кот F max (min). Б) n=3: выбираем по 3 ур-я, … В) n неизвестных: решаем методом Гаусса.

3) Симплекс метод: вершины перебир-ся не произвольно, а так, что кажд. следующ. вершина улучшает знач-е целевой ф-ии. Стандартный вид: 1) все огр-я записны в виде рав=в; 2) правые части рав-в >=0; 3) переменные >=0; 4) F к min. Канонич.вид: 5) в кажд. ур-ии есть переменная, кот. присутсв. только в этом ур-ии с коэф. +1, в др. ур-х её нет. Одноэтапный СМ: для канонич вида. 1) Строим таблицу, 2) выбираем min эл-т и з F – ведущ столбец. 3) выбираем ведущ. строку с пом-ю сравнения отношений правых частей рав-в к эл-м ведущ столбца, из >0 выбираем min, получаем ведущ строку. 4) Эл-ты столбика кроме ведущего превращаем в 0. Далее с (1) пока все коэф-ты F не станут >=0. Двухэтапн. СМ для неканонич. вида: 1) приводим ЗЛП к канонич виду, т.е. решаем вспомогат задачу СМ. F’=(b1+b2+…+bm)+(a11+a21+…+am1)x1+(a12+a22+a32+…+am2)x2…+(a1n+a2n+…+amn)xn. 2) Решени получ задачи СМ.