számítógépes grafika természetesen - az első feladat

Nyomtatóbarát verzió itt (zip doc - 229kb)

célmeghatározás

Végre sejtautomaták

Leírás A munka

Általános elmélet

Sejtautomaták diszkrét dinamikus rendszerek, akinek a viselkedése teljesen meghatározva szempontjából a helyi összefüggései az állammal. Egy sejtautomata egy n-dimenziós egyenletes rács (véges vagy végtelen), minden egyes cella (cella), amely képes fogadni az állam egy bizonyos sor körülmények között; telik az idő diszkrét lépésekben, és a törvények fejlesztés (sejt állapota megváltozik) vannak kifejezve, egységes szabályrendszert, például egy kis look-up table, amelyben minden cella minden lépést számol az új állam az állam közeli szomszédjához. Ha megad egy megfelelő szabályrendszer, mint egy egyszerű működési mechanizmusát elegendő ahhoz, hogy a teljes hierarchia szerkezetek és jelenségek. Sejtautomaták hasznos modellek számos tanulmány a természettudományokban. Ezek alkotják a közös paradigma párhuzamos számítási, csak úgy, ahogyan egy Turing-gép a későbbi számítások.

Egy jó példa, hogy tanulmányozza az elvek a sejtautomata játék John Horton Conway „Life”.

Változatos sejtautomaták

Sejtautomaták különböznek, különösen a számos sejt államok szabály Rácsméret és változások sejt államokban. Nézzük meg bizonyos típusú gépek egy két dimenziós rácsot.

A kétdimenziós gépek a szomszédos sejtek általában úgy tekintenek, 5 sejt - a sejt saját maga és a 4 átlós szomszédokat nem azonnali (Neumann környékén) és kilenc sejtek - a sejt saját maga és a nyolc szomszédja, beleértve a diagonális sejtek (Moore környékén).

Feltétel sejtautomata lehet leírni a mátrixban, például:

Itt az állam a sejtek tárolják a megfelelő sejteket a mátrix.
De sokkal érdekesebb elképzelni az állam formájában egy kép, ahol minden pixel megfelel egy sejt, és az aktuális szín a pixel határozza meg az állam a cellában.

Specifikus példa a sejtautomaták

Gép számos Államokban több, mint kettő.
Szabályzat kimondja a sejt változásokat rögzíti az alábbiak szerint:

ahol:
S - egy sor olyan számok 0-8, meghatározza, hogy hány „élő” szomszédok, amelyben egy sejt „életben”,
B - egy sor olyan számok 0-8, meghatározza, hogy hány „élő”, amelyben a szomszédok a „halott” sejt válik egy „élő”
C - a szám határozza meg a lépések számát „haldokló” cellában

Ez azt jelenti, hogy a sejt él, ha 2 vagy 3 szomszédok, hogy pontosan három szomszédok „született” az új sejtek, a sejt elpusztul tizennégy mozog.

Ha a szám a „live” szomszédok a cella nem egyenlő sem a számok halmaza az S, a sejt elkezd „meghalni”, és állapota növekszik minden körben, amíg el nem éri a C, majd a sejt elveszett. „Haldokló” sejt nem vesz részt a számláló a szám a „nappali” szomszédok kiszámításakor a következő lépésben. A születés, a sejt megkapja az első állam ( „sejt él”).

„Szikra”
02/02/25
Az ábra azt mutatja, a 0., 16., 32., 48., 64. és 80. konfiguráció:

"Bug"
23/2/8
Az ábra azt mutatja, a 0., 16., 32., 48., 64. és 80. konfiguráció

"Flame"
235678/3468/9
Az ábra azt mutatja, a 0., 16., 32., 48., 64. és 80. konfiguráció

Egy másik példa a sejtautomata nyissa David Griffith a University of Wisconsin Madison. Kezdve egy tetszőleges kezdeti állapotban, az automata mutatja négy különböző fázisok végződő bizarr kristályos képződmények, erősen hasonlít a primitív élet formák.

Magatartási szabályt gép felsorolni azokat a lehetséges állapotok 0 n - 1, és tegyük fel, hogy ha egy sejt, hogy ez az intézkedés az állami k, majd a következő ciklusban kell „enni” a szomszédos cellák az állami k - 1 . evett kimutatták, hogy megevett a szomszédos cellában megy k - 1 k állapothoz; cella a állapotban 0 ehet állapotban a szomszédos cellákban lévő n - 1.

Az ábra egy példát mutat végrehajtásának egy ilyen automatának (80x80 mező, n = 17). Minden egyes darab 12 eltér az előző iteráció.

Tyurmit - egyfajta szintézisét sejtautomata és Turing-gép. Sejtről tyurmit gép azzal jellemezve, hogy a kezdeti időben az üres, és néhány egysejtes kell tekinteni a kezdeti (tyurmit elfoglalja a kiindulási helyzet, még a kezdeti állapotban, a kezdeti irányt, például, hogy a kelet). Ezután minden egyes lépésében a típusa tipikusan használt:

Állam általában jelöljük latin betűkkel; szín - a számok 0 és 15 (16-színpaletta), a kezdeti színe fekete (ez nem egy erős korlátot, ha a kívánt színek lehet dúsított, és jön ki a szimbólumok); A mozgás iránya megváltozik képest a jelenlegi arány turmite jelöljük szám 1 (balra), 1 (jobbra), 0 (egyenes).
Például tipikusan 15 0 A 0 azt jelenti, hogy ha tyurmit állapotban van A és áll egy fekete ketrec, akkor meg kell festeni, hogy fehér, mozogni egy négyzet az irányt a jelenlegi és bemegy az állam B.

Így, ha egy - az eredeti állapot turmite, 0 - az eredeti szín, turmite meghatározott szabályok tartalmaznia kell egy szabályt A 0 _ _ _.

"Cactus"
(Az ábrán az egyik lehetséges konfigurációk)

A 0 2 1 A
Februári 10 -1 B
A 10 0 -1 B
B 0 2 1 A
Február 2 B -1 A
B február 10 -1 A

bejegyzés

Regisztráció nem különbözik a szokásos.

ZIP-fájlt a forráskód és a futtatható fájlokat, nevezett eljárás szerinti GZV_nnnnnnnn.zip (ahol G - az utolsó számjegy a csoport szám, Z - feladat száma, V - amelyben a verziószámot, nnnnnnnn - diákigazolvány szám), hogy küldjön [email protected]. msu.su

Például egy diák 206 csoportok tanulói azonosító száma 06529042, mely frissített (második) változata az első feladat a program küldjön egy fájl nevét 612_06529042.zip.

Ne felejtse el, hogy a readme.txt fájlt. A fájl leírja a program interfész (az algoritmus a program, a menüpontok, gombok), és adja meg a következő részfeladatok:

Megvalósítása gép: [insert megvalósult gép (ek)]
Képessége, hogy módosítsa a kezdeti állapotát automata: [+/-]
A program használata: [az algoritmus a program]

az eredmények

jegyzetek

1. A feladat fut szigorúan egyéni. Együttműködési vagy csere darab elhelyezett kódot nulla pontot minden résztvevőnek, ha az a tény csapatmunka nem volt megadva a readme.txt munkahelyeket.
2. Javasoljuk, hogy programozni az írás egy család a Windows. Írásban a másik alá operációs rendszer nem kívánatos, és késleltetné a hitelesítési ilyen műveleteket.

Gyakran ismételt kérdések az utasításokat

Hol találok részletes anyagok a programozás Windows alatt?

A beállítás a „generáció” azt mondják, hogy ha egy bizonyos számú szomszédok egy halott cella élővé válik. e haldokló sejtek életben (a megszámoljuk a nappali nem vesz részt)?

Nem, a pusztuló sejtek nem tekinthető meghalt, így lesz egy élő nem.

Mit jelent a „tyurmit fordul bal / jobb”?

Tegyük tyurmit mozog kelet felé.
A képen egy sötét szürke szín jelzi, ha tyurmit volt az előző ciklusban, a piros - a jelenlegi helyzet turmite és világosszürke - hol lesz a következő löket, amikor a mozgó balra (felső opció), a jobb oldali (alsó opció) vagy jobbra (közepes változat ).

A „Generációk” mi pont azt jelenti sejt „haldokló”: egyszer úgy éreztük, új állapotban az automata (az előző haldoklott), vagy közvetlenül, amint úgy éreztük, hogy a szomszédok száma benne, hogy ő már meghalni?

Azonnal, amint a sejtekbe a rossz szomszédok száma, akkor haldokolni kezd. Nem lehet automatikusan államban, ahol az élő sejtek száma szomszédok nem esik egybe bármelyike ​​egy sor S.