Thesis (MSc (Mathematical Sciences)) University of Stellenbosch, 2011. / ENGLISH ABSTRACT: Cellular Automata (CA) have become a popular vehicle to study complex dynamical
behaviour of systems. CA can be used to model a wide variety of physical,
biological, chemical and other systems. Such systems typically consist of subparts
that change their state independently, based on the state of their immediate surroundings
and some generally shared laws of change.
When the CA approach was used to solve the LEGO construction problem, the best
solution was found when using a variant of CA allowing for the clustering of cells.
The LEGO construction problem concerns the optimal layout of a set of LEGO
bricks. The advantages found for using the CA method with clustering in this case
are the ease of implementation, the significantly smaller memory usage to previously
implemented methods, and its trivial extension to construct multicoloured LEGO
sculptures which were previously too complex to construct.
In our research we propose to explore the definitions of clustering in CA and investigate
the implementation and application of this method. We look at the ant
sorting method described by Lumer and Faieta, and compare the implementation
of this algorithm using regular CA as well as the clustering variation. The ant
sorting model is a simple model, in which ants move randomly in space and pick
up and deposit objects on the basis of local information. / AFRIKAANSE OPSOMMING: Sellulêre Outomate (SO) het ’n populêre metode geword om die komplekse dinamiese
gedrag van sisteme bestudeer. SO kan gebruik word om ’n groot verskeidenheid
fisiese, biologiese, chemiese en ander tipe sisteme te modelleer. Sulke sisteme bestaan
tipies uit subafdelings wat, gebaseer op die status van hulle omgewing en ’n
paar algemene gedeelde reëls van verandering, hulle status onafhanklik verander.
Met die gebruik van die SO benadering om the LEGO konstruksieprobleem op te
los, is die beste oplossing bereik deur gebruik te maak van ’n variant van SO, waar
selle saamgroepeer kan word. Die LEGO konstruksieprobleem behels die optimale
uitleg van ’n stel LEGO blokkies. In hierdie geval is die voordele van die SO
met sel groepering die maklike implementasie, ’n beduidende kleiner geheuegebruik
teenoor voorheen geïmplementeerde metodes, en die triviale uitbreiding daarvan om
gekleurde LEGO beelde wat voorheen te kompleks was, te kan bou.
In ons ondersoek verken ons die definisies van selgroepering in SO en ondersoek die
implementasie en toepassing van die metode. Ons kyk na die miersorteringsmetode
beskryf deur Lumer en Faieta, en vergelyk die implementasie van hierdie algoritme
deur gewone SO asook die groeperingsvariasie te gebruik. Die miersorteringsmodel
is ’n eenvoudige model waarin miere lukraak in ’n omgewing beweeg en voorwerpe
optel of neersit volgens plaaslike inligting.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/6674 |
| Date | 03 1900 |
| Creators | Adams, Roxane |
| Contributors | Van Zijl, L., University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Dept. of Computer Science. |
| Publisher | Stellenbosch : University of Stellenbosch |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | 73 p. : ill. |
| Rights | University of Stellenbosch |
Page generated in 0.003 seconds