Автор: Пользователь скрыл имя, 22 Декабря 2012 в 23:58, курсовая работа
Основні сучасні тенденції розвитку паралельної обчислювальної техніки, проблеми моделювання дискретних паралельних процесів, теорія паралельних дискретних динамічних систем, дискретна математика і синергетика, задачі штучного інтелекту і робототехніки, паралельна обробка інформації і алгоритми, фізичне і біологічне моделювання, а також цілий ряд передумов в різних областях сучасного природознавства спонукають в остання роки до підйому інтересу до різного типу формальних клітинних моделей, які мають паралельний принцип дії. Одним із основних типів таких моделей є клітинні автомати або однорідні структури.
РЕФЕРАТ ……………………………………………………………………………2
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ,
СКОРОЧЕНЬ І ТЕРМІНІВ …………………………………………………………3
ВСТУП ………………………………………………………………………………5
1. ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ КЛІТИННИХ АВТОМАТІВ
1.1 Історія виникнення та ідея клітинних автоматів ………………………….7
1.2 Основні поняття ……………………………………………………………..9
1.3 Основні види клітинних автоматів ………………………………………..12
1.4 Класи правил для найпростіших одновимірних клітинних автоматів …..14
1.5 Види правил для двовимірних клітинних автоматів ……………………..16
1.5.1 Необмежений ріст ……………………………………………………17
1.5.2 Обмежений ріст ………………………………………………………17
1.5.3 Конкурентний ріст …………………………………………………...18
1.5.4 Правила голосування ………………………………………………...19
1.5.5 Правило експоненціального затухання ……………………………..21
2. ДЕЯКІ ЗАСТОСУВАННЯ КЛІТИННИХ АВТОМАТІВ
2.1 Однорідні структури як формальна модель обчислювальної техніки ….22
2.2 Використання клітинних автоматів у фізиці ……………………………..25
2.3 Однорідні структури та диференційні рівняння ………………………….27
2.4 Використання клітинних автоматів у соціології ………………………...29
3. МОДЕЛЬ ПОШИРЕННЯ ІНФЕКЦІЇ НА БАЗІ КЛІТИНИХ АВТОМАТІВ
3.1 Концепція поширення властивості у просторі …………………………..32
3.2 Результати моделювання …………………………………………………..34
ВИСНОВКИ ………………………………………………………………………...41
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ І ЛІТЕРАТУРИ ………………………..42
ДОДАТОК А ……
3.2 Результати моделювання
Продемонструємо дану модель для випадку , , , і індексі сусідства Мура, при .
Рисунок 15 – початкова конфігурація
Рисунок 16 – 50 ітерацій
Рисунок 17 – 350 ітерацій
Це можна інтерпретувати як поширення інфекції із початкової області. Особа інфікується якщо серед її сусідів є хоча б один інфікований із імовірністю .
Цікаві результати демонструє модель, якщо ввести відображення також імовірнісним. Правда, тоді вже не буде зростаючою, а кількість кліток, що задовольняють буде варіюватися.
При і інших умовах як в попередній моделі, отримав результати на рис. 18 - рис. 20.
Також можна виділити підмножину , елементи якої не враховувати при підрахунку
Рисунок 18 – початкові умови
Рисунок 19 – 500 ітерацій
Епідеміологічна інтерпретація такої моделі:
Популяція
індивідів розподілена у
У позначеннях моделі описаної вище це можна записати так:
, , .
Результати моделювання на рис. 20 – рис. 22.
Рисунок 20 – (початкові умови – одна інфікована клітка у ценрі рисунка)
Остання модель після певного числа ітерацій входить у стан, коли зупиняється будь-яка активність і інфекція вже розповсюдилася на весь масив, тоді клітки залишаються або білого або сірого кольору. Сірі клітки можна інтерпретувати як осіб, які перехворіли, а білі – як осіб, які не були інфіковані. Графік залежності відношення білих кліток відносно всіх кліток для на рис. 23 (для немає значення, тому що активність зупинялася практично відразу).
Рисунок 23
ВИСНОВКИ
У першому розділі своєї курсової роботи я розглянув основні поняття та історію розвитку теорії клітинних автоматів. Також були розглянуті основні види клітинних автоматів: моногенні, полігенні, детерміновані, недетреміновані, стохастичні, особливий інтерес викликають клітинні автомати із рефрактерністю. Приведена класифікація найпростіших одновимірних клітинних автоматів та основні види правил для двовимірних клітинних автоматів, деякі із цих правил можуть мати великий практичний інтерес.
У другому розділі були розглянуті деякі сфери застосування теорії однорідних структур. Клітинні структури за визначенням забезпечують три фундаментальні властивості: однорідність, локальність і паралельність, якщо ж запрограмувати правило так, щоб воно було оборотнім, то така дискретна динамічна система може бути використана для моделювання фізичних явищ. Такі системи мають багато переваг над класичними методами і зараз активно застосовуються для моделювання гідродинамічних явищ, дифузії та ін. Також клітинні автомати активно застосовуються у соціології, наприклад, для моделювання електоральних процесів.
У третьому розділі була запропонована проста епідеміологічна модель на основі концепції поширення властивості у просторі клітинними автоматами. Було зроблено багато рисунків, які показують динаміку поширення інфекцій при різних параметрах. З точки зору медицини в цій моделі може бути знайдено багато недоліків, але, я думаю, сама концепція може бути використана в подальшому.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ТА ЛІТЕРАТУРИ
ДОДАТОК А
Текст програми на мові Delphi
unit CA;
interface
uses Graphics,SpreadableModel,
const r:real = 0.3;
type
TCellularAutomata = class
private
fS: array of array of byte;
f:Rule;
public
N,M: integer;
constructor Create(nN,nM:integer);
destructor Done;
function GetS(i,j:integer):byte;
procedure SetS(i,j:integer; v:byte);
property S[i,j:integer]:byte read GetS write SetS;
procedure Init(initpath:string; rand:Boolean);
procedure Run(Steps:integer);
end;
implementation
uses SysUtils;
constructor TCellularAutomata.Create(nN,
var i:integer;
begin
Randomize;
N:=nN; M:=nM;
if (N > 0) and (M > 0) then
SetLength(fS,N,M)
else fS:=nil;
f:=nil;
end;
destructor TCellularAutomata.Done;
begin
fS:=nil;
f:=nil;
end;
function TCellularAutomata.GetS(i,j:
begin
GetS:=fS[i,j];
end;
procedure TCellularAutomata.SetS(i,j:
begin
fS[i,j]:=v;
end;
procedure TCellularAutomata.Init(
var i,j:integer; temp:real;
b:TBitmap;
begin
f:=SpreadableModel.f;
if FileExists(initpath+'init.bmp'
b:=TBitmap.Create;
b.Height:=N;
b.Width:=M;
b.LoadFromFile(initpath+'init.
for i:=0 to N-1 do
for j:=0 to M-1 do
fS[i,j]:=ColorToByte(b.Canvas.
b.Free;
end
else begin
for i:=0 to N-1 do
for j:=0 to M-1 do
begin
temp:=Random;
if temp<r then
fS[i,j]:=1
else fS[i,j]:=0;
end;
end;
end;
procedure TCellularAutomata.Run(Steps:
var i,j,s,inx,ipr,jnx,jpr:integer;
S1:array of array of byte;
Nb:TNb;
begin
SetLength(S1,N,M);
for s:=1 to Steps do begin
for i:=0 to N-1 do
for j:=0 to M-1 do
begin
if (i>0) and (i<N-1) and (j>0) and (j<M-1) then
begin
ipr:=i-1;
inx:=i+1;
jpr:=j-1;
jnx:=j+1;
end;
if (i=0) then
begin
ipr:=N-1;
inx:=1;
end;
if (i=N-1) then
begin
ipr:=N-2;
inx:=0;
end;
if (j=0) then
begin
jpr:=M-1;
jnx:=1;
end;
if (j=M-1) then
begin
jpr:=M-2;
jnx:=0;
end;
Nb[0]:=fS[i,j];
Nb[1]:=fS[ipr,jpr];
Nb[2]:=fS[ipr,j];
Nb[3]:=fS[ipr,jnx];
Nb[4]:=fS[i,jpr];
Nb[5]:=fS[i,jnx];
Nb[6]:=fS[inx,jpr];
Nb[7]:=fS[inx,j];
Nb[8]:=fS[inx,jnx];
S1[i,j]:=f(Nb);
end;
for i:=0 to N-1 do
for j:=0 to M-1 do
fS[i,j]:=S1[i,j];
end;
S1:=nil;
end;
end.
unit SpreadableModel;
interface
uses Graphics,TypesUnt;
var p:real = 0.17;
th:real = 0.1;
function pi(x:byte):byte;
function pi_(x:byte):byte;
function sigma(x:byte):byte;
function delta1(x:byte):byte;
function delta2(x:byte):byte;
function f(const Nb:TNb):byte;far;
function ByteToColor(b:byte):TColor;
function ColorToByte(c:TColor):byte;
implementation
function pi(x:byte):byte;
begin
case x of
0: pi:=0;
else pi:=1;
end;
end;
function pi_(x:byte):byte;
begin
case x of
0: pi_:=0;
3: pi_:=0;
else pi_:=1;
end;
end;
function sigma(x:byte):byte;
begin
case x of
1: sigma:=2;
2: sigma:=3;
3: sigma:=3;
end;
end;
function delta1(x:byte):byte;
begin
case x of
0: delta1:=1;
end;
end;
function delta2(x:byte):byte;
begin
case x of
0: delta2:=0;
end;
end;
function f(const Nb:TNb):byte;far;
var i,sum,nu:integer;
r:real;
begin
sum:=0;
for i:=1 to 8 do
sum:=sum+pi_(Nb[i]);
if (sum/9)>=th then
begin
r:=Random;
if (r<p) then nu:=1
else nu:=0;
end
else nu:=0;
f:=pi(Nb[0])*sigma(Nb[0])+(1-
end;
function ByteToColor(b:byte):TColor;
begin
case b of
0: ByteToColor:=clWhite;
1: ByteToColor:=clRed;
2: ByteToColor:=clYellow;
3: ByteToColor:=clGray;
else ByteToColor:=clWhite;
end;
end;
function ColorToByte(c:TColor):byte;
begin
case c of
clRed: ColorToByte:=1;
clGray: ColorToByte:=3;
clYellow: ColorToByte:=2;
clWhite: ColorToByte:=0;
else ColorToByte:=0;
end;
end;
end.
unit TypesUnt;
interface
type
TNb = array[0..8] of byte;
Rule = function(const Nb:TNb):byte;
implementation
end.