Seminarky.cz > Diplomky, bakalářky > Diplomové práce > > Lindenmayerovy systémy

Lindenmayerovy systémy

Kategorie: Biologie

Typ práce: Diplomové práce

Škola: Slezská univerzita v Opavě Filozoficko-přírodovědecká fakulta, Opava

Charakteristika: Cílem diplomové práce je seznámit s Lindenmayerovými systémy, s historií vzniku těchto systémů, biologickou motivací, s aplikací Lindenmayerových systémů i se současnými trendy výzkumu. Zároveň bylo cílem vytvoření výukového programu na Lindenmayerovy systémy určeného především studentům IV. ročníku Slezské univerzity v Opavě, Filozoficko-přírodovědecké fakulty, obor Informatika a výpočetní technika, jako podpora výuky předmětu Kapitoly z teorie formálních jazyků a automatů I a předmětu Seminář z formálních jazyků I. Po úvodní kapitole jsou publikovány studijní materiály, které jsou prezentovány ve výukovém programu v teoretické části. Ta je zaměřena na tyto třídy L-systémů: 0L-, E0L-, T0L-, IL-systémy a obsahuje také další části související s obsahovou náplní přednášek předmětu. Desátá a dvanáctá část jsou prezentovány ve výukovém programu a souvisí s obsahovou náplní cvičení předmětu Seminář z formální jazyků I. Ve třinácté části je popsána inference Lindenmayerových systémů, s kterou souvisí současné trendy ve výzkumu v oblasti Lindenmayerových systémů. Ve čtrnácté kapitole se seznámíme s dokumentací k výukovému programu.

Obsah

0.
Úvod
1.
Lindenmayerovy systémy
1.1.
Biologická motivace
1.2.
Úvod do Lindenmayerových systémů
1.3.
Gramatika Lindenmayerových systémů
1.4.
Základní členění Lindenmayerových systémů
2.
0L systémy
3.
Růstové funkce
4.
Dospělé jazyky
5.
E0L systémy
6.
T0L systémy
7.
IL systémy
8.
Regenerace v IL systémech
9.
Vztah L systémů a gramatik Chomského typu
10.
Geometrická interpretace řetězců generovaných Lindenmayerovými systémy
11.
Aplikace Lindenmayerových systémů
12.
Programy pro grafickou reprezentaci Lindenmayerových systémů
13.
Inference Lindenmayerových systémů
14.
Dokumentace k výukovému programu
14.1.
Provozní konfigurace
14.2.
Implementace
14.3.
Uživatelská dokumentace
15.
Závěr

Úryvek

"1. LINDENMAYEROVY SYSTÉMY
1.1. BIOLOGICKÁ MOTIVACE
Jazyk je základním nástrojem lidské abstrakce - prostředkem pro redukci rozmanitosti jevu složitého vnímaného světa do uchopitelného množství kategorií. Cílem teorie formálních jazyků je popsat strukturu jazyka prostředky algebry, popřípadě vytvořit specializované nástroje pro tento účel. Základním východiskem teorie formálních jazyků byla struktura přirozeného jazyka, brzy byla ale vytvořena vlastní struktura formálních jazyků s exaktní syntaxí a sémantikou, vhodná pro komunikaci se stroji. Další aplikace teorie formálních jazyků se postupně uplatnily v oblastech:
- modelování biologické reality (procesu organického růstu) a umělého života (Artifical Life),
- počítačového zpracování obrazu (tvorba, analýza),
- modelování možností buněčných a molekulárních výpočtů (H-systémy - modely DNA počítačů, P-systémy - modely membránových výpočtů),
- popisu distribuovaných výpočetních i reálných systémů (gramatické systémy)
- a dalších.
Původní přepisování řetězců symbolů na jiné řetězce pomocí generativních pravidel přestalo pro tyto nové aplikace dostačovat. Postupně byla teorie formálních jazyků obohacována o prostředky jako:
- teorie grafů (grafové gramatiky),
- topologická pravidla (2D a 3D gramatiky pro popis obrazu),
- regulace generování pomocí kontextu (kontextuální gramatiky, regulované gramatiky),
- synchronizaci, paralelizmus (Lindenmayerovy systémy),
- distribuci komponent, hierarchie, protokoly (gramatické systémy).
Výzkum gramatických konstrukcí s výše uvedenými vlastnostmi je zaměřen jednak na aplikace, ovšem jeho výsledkem jsou též teoretické poznatky obohacující teorii formálních jazyků, bohatá hierarchie tříd jazyků se zajímavými vlastnostmi, vztahy k jiným disciplínám (lingvistika, teorie čísel, apod.).
Jednou z prvních koncepcí teorie formálních jazyků přesahující studium přirozených a počítačových jazyků byly Lindenmayerovy systémy, zkráceně L-systémy.
1.2. ÚVOD DO LINDENMAYEROVÝCH SYSTÉMŮ
V přírodě se vyskytuje mnoho přírodních objektů, které mají tu vlastnost, že celek a jeho části jsou si podobné. To platí například o stromu a jeho větvi nebo o skále a úlomku. A jelikož dochází v posledních letech k velkému rozvoji v oblasti generování syntetických scén, setkáváme se při tvorbě tvaru okolní krajiny nebo rostlin s velkou složitostí těchto přírodních struktur, jejichž popis by byl velmi náročný. Členitost těchto objektů způsobuje informatikům problém, jak je nejlépe uložit v paměti počítače. A protože jejich reprezentace, například vektorovou grafikou, by byla značně nehospodárná, využívá se jisté pravidelnosti těchto objektů a hledají se různé matematické objekty, kterými by bylo možné je nejlépe popsat.
Lindenmayerovy systémy zavedl Aristid Lindenmayer jako modifikaci formální gramatiky pro účely modelování vývoje jednoduchých vícebuněčných organizmů. Svoji teorii předvedl poprvé v roce 1968.
Tyto systémy je možné považovat za speciální případ celulárních automatů vzhledem k tomu, že stav prvku v následujícím kroku je odvozený od aktuálních stavů okolních prvků. Pravidla jsou v zásadě rekurzivní, což zaručuje soběpodobnost, charakteristickou vlastnost fraktálů. Ukázalo se, že i velmi jednoduchá soustava pravidel byla schopná simulovat proces růstu, resp. morfologii složitých struktur.
Vlastní L-systémy generují jen řetězce znaků. Bylo potřebné je nějakým způsobem interpretovat jako pravidla pro růst, větvení, tvorby pupenců, listů a květů.
Lindenmayerovi žáci, Ben Hesper a Pauline Hogeweg, začali v roce 1970 zkoumat, zda jsou L-systémy schopné generovat také obrazy rostlin. Řetězec, reprezentující morfologii rostliny, nazvali morfém. Své poznatky s generováním 3 584 umělých rostlin publikovali (Hogeweg a Hesper, 1974).
Lindenmayer ze začátku považoval tyto experimenty za nedůstojné a svoje studenty od nich odrazoval. Obrázky používal jen na svých novoročenkách.
Matematik Alvy Ray Smith byl naopak fascinovaný touto schopností L-systémů. Měl k celulárním automatům blízký vztah, ve své disertaci podal důkaz možnosti sestrojit univerzální počítač v 1-D CA. Stal se jedním z nejslavnějších představitelů počítačového umění. Ve svých dílech kombinoval rostliny generované L-systémy (používal pro ně termín graftály) s prvkami, které vytvářel pomocí klasických fraktálů.
V polovině 80-tých let Lindenmayer připustil, že generování virtuálních rostlin pomocí L-systémů pomáhá odhalit zákonitosti morfogenézy. Jeho nový spolupracovník Przemyslaw Prusinkiewicz začal detailně studovat pravidla, kterými se řídí procesy růstu, větvení, tvorby pupenců, listů a květů. Ukázalo se, že pomocí L-systémů je možné začít od jediné buňky, z které postupně vyrůstá vícebuněčná embryonální struktura a nakonec celá entita. Přesvědčivým příkladem je porovnání morfogenézy gametofytu (první vývojová fáze nižších rostlin), který vytvořil Martin de Boer pomocí L-systémů s mikroskopickými snímkami prvních vývojových kroků zárodku kapradí Microsorium lingueforme.
Pro účely modelování vývoje rostlin byly nalezeny takové metody interpretace řetězce, které umožňují vytvářet i realistické obrazy modelovaných rostlin. Při modelování rostlin pro účely počítačové grafiky se ve velké míře využívají biologické znalosti o jejich vývoji a mechanizmech, které ho řídí. L-systémy a jejich grafická interpretace dávají na druhé straně velké možnosti biologům. Umožňují jim sledovat vývoj rostliny za různých podmínek, testovat teorie o vnitřních mechanizmech řídících vývoj rostliny i o působení vnějšího prostředí. Nabízejí prostředky pro zjišťování parametrů těchto mechanizmů, například rychlosti šíření signálů v rostlině apod.
1.3. GRAMATIKA LINDENMAYEROVÝCH SYSTÉMŮ
Gramatiku používanou v L-systémech lze definovat jako:
,
kde jsou neterminály,
jsou terminály,
jsou přepisovací pravidla,
je startovací fráze, nazývaná axiom."

Poznámka

Práce obsahuje obrázky a schémata. Čistý text je cca 48 stran.

Vlastnosti

STÁHNOUT PRÁCI

  1. SMS platba (ČR) 30 Kč

    Platba prostřednictvím brány mobilního operátora. Pro započetí platebního procesu prosím vyplňte kontrolní kód a stiskněte tlačítko "Zaplatit"

    Po proběhnutí platby budete přesměrováni zpět na tuto stránku, kde najdete odkaz ke stažení práce.


    V případě potíží s realizací platby se neváhejte obrátit na infolinku poskytovatele služby, společnost Advanced Telecom Services s.r.o., na čísle +420 776 999 199

    Nápověda pro zákazníky Telefónica O2:

    1. Vyplňte Vaše číslo na mobil, zvolte jako operátora Telefónica O2 a klikněte na POTVRDIT.
    2. Zobrazí se Vám informace, že SMS byla odeslána.
    3. Na mobilní telefon Vám bude doručena SMS zpráva s odkazem.
    4. Klikněte na odkaz v SMS zprávě, budete propojeni na platební bránu společnosti Telefónica O2. Zde potvrďte platbu.
    5. Na internetu se zobrazí výsledek proběhlé platby.
    Pro úspěšnou realizaci platby je nutné mít aktivní službu „O2 platba“. Služba je většinou aktivní automaticky, takže není třeba nejdřív nic aktivovat.

    Nápověda pro zákazníky Vodafone:

    1. Vyplňte Vaše číslo na mobil, zvolte jako operátora Vodafone a klikněte na POTVRDIT.
    2. Dojde k přesměrování na Vodafone portál.
    3. Potvrďte Vaše mobilní číslo kliknutím na DALŠÍ. .
    4. Na Váš mobilní telefon přijde SMS zpráva s kódem.
    5. Zadejte tento kód do formuláře, klikněte na OK.
    6. Objeví se Vám údaje o platbě, kterou potvrďte kliknutím na POKRAČOVAT.
    7. V té chvíli proběhne platba, o jejímž výsledku Vás informuje došlá SMS zpráva.
    Pro úspěšnou realizaci platby je nutné mít aktivní službu „M-peněženka“. Služba je většinou aktivní automaticky, takže není třeba nejdřív nic aktivovat.

    Nápověda pro zákazníky T-mobile:

    1. Vyplňte Vaše číslo na mobil, zvolte jako operátora T-mobile a klikněte na POTVRDIT.
    2. Dojde k přesměrování na T-mobile portál, potvrďte zde svůj souhlas s podmínkami platby.
    3. Pokud máte na T-zones účet, přihlaste se a pokračujte bodem 7.
    4. Pokud účet na T-zones nemáte, vepište do formuláře svoje mobilní číslo a klikněte na ODESLAT ČÍSLO.
    5. Přijde Vám SMS zpráva s kódem.
    6. Vepište kód jako heslo do formuláře a klikněte na PŘIHLÁSIT.
    7. Objeví se Vám údaje o platbě, které potvrďte kliknutím na tlačítko ZAPLATIT.
    8. V té chvíli proběhne platba, o jejímž výsledku Vás informuje došlá SMS zpráva.
    Pro úspěšnou realizaci platby je nutné mít aktivní službu „M-platba“. Služba je většinou aktivní automaticky, takže není třeba nejdřív nic aktivovat.
  2. Platit kartou 30 Kč

    Platba kartou. Pro započetí platebního procesu prosím vyplňte kontrolní kód a stiskněte tlačítko "Zaplatit"

    Po proběhnutí platby budete přesměrováni zpět na tuto stránku, kde najdete odkaz ke stažení práce.


    Po odeslání kontrolního kódu budete přesměrováni do platební brány GP webpay, kde zadáte údaje potřebné pro platbu. Platbu dokončíte stisknutím tlačítka "ZAPLATIT".

    Akceptované karty: VISA, VISA Electron, V PAY, MasterCard, Maestro.

  3. Koupit za kredity - 25 Kč >>> ZVÝHODNĚNÁ CENA!
    Jedním stiskem tlačítka, obratem a za výhodnou cenu!
    JEN PRO REGISTROVANÉ UŽIVATELE
    Cena za stažení je pouze 450 kreditů (=25Kč).
  4. Platit převodem z ČSOB a Poštovní spořitelny, službou PaySec 25 Kč >>> ZVÝHODNĚNÁ CENA!
    Rychle, bezpečně a pohodlně.
    Zaplatit za tuto práci přes PaySec >>> Kliknutí na odkaz Vás přesměruje do platebního rozhraní
    Kliknutím na ikonku Vás přesměrujeme do platebního systému, kde si vyberete převod z ČSOB, Poštovní spořitelny nebo platbu PaySec
  5. SMS platba (Slovensko) - 1,20€
    Stahovací kód k této práci získáte do několika minut se službou mobilního operátora Premium Rate SMS.
    Zašlete SMS zprávu ve tvaru: SEMmezera23580
    - na telefonní číslo: 8877
    Cena jedné SMS je 1,20€ včetně DPH. Pro využití SMS platby je třeba mít aktivovanou službu Premium Rate SMS. Službu technicky zajišťuje Advanced Telecom Services, s. r. o.
    SMS musí být ve formátu TEXT, bez diakritiky a bez formátování (tj. základní velikost a typ písma). Stahovací kód je použitelný pouze pro tuto práci a je platný až do uzavření okna internetového prohlížeče.
    Stahovací kód přijde obratem na mobil, je platný 24 hodin a lze jej zadat celkem dvakrát.
    Pro stažení této práce zadejte stahovací kód (bez uvozovek):


Důležité informace: Provedením mobilní platby, odesláním SMS, platbou kredity, platbou kartou, PaySecem nebo převodem z účtu souhlasíte s Podmínkami stahování.
Veškeré informace o platbách si můžete přečíst zde.
Máte při placení nebo stahování práce problém? Odpovědi na časté problémy najdete zde nebo kontaktujte naší podporu.

Diskuse