Názory k článku
Paralelní přepisování řetězců v L-systémech

Pokud krivku (tedy spojite zobrazeni z [0,1] do R^2) ztotoznime s jejim obrazem (tedy s mnozinou f([0,1]), pak at vezmeme jakoukoliv definici topologicke dimenze z ucebnic obecne topologie, dostaneme cislo 2. Proste proto, ze f([0,1]) je ctverec.

Pokud toto ztotozneni neprovedeme, mame krivku jako bod v prostoru vsech spojitych zobrazeni z [0,1] do R^2 a bod by mel mit dimenzy 0, neni-liz pravda?

Problem bude v tom ztotozneni krivky s jejim obrazem, takto se to IMHO delat neda. Ale je zajimave, ze Hilbertova krivka v limite opravdu pokryje cely ctverec, takze libovolny bod v nem je mozne popsat pouze jednim parametrem [0,1].

A mohl byste mi tedy vysvetlit vetu: "Z toho vyplývá, že topologická dimenze je rovna jedné, ale dimenze Hausdorffova je o celou jedničku vyšší ..."?

Vyplyva to z toho, ze se jedna o krivku (a je jedno v jakem prostoru). Krivka=jednodimenzionalni spojity objekt. Druha cast vety (o H. dimenzi rovne dvema) se da dokazat bud klasickym zpusobem, tj. vycislenim zlogaritmizovaneho pomeru zmeny delky krivky s jeji rostouci slozitosti (ln 4/ln 2), nebo take tim, ze se jedna o krivku cele vyplnujici danou rovinu, ktera ma T. dimenzi rovnu dvema.

Mimochodem, existuje i Hilbertova krivka vyplnujici krychli, potom je H. dimenze rovna trem (ln 8/ln 2).

Chapu. Zrejme je problem v definici a terminech. Tak trochu jsem zapomnel, ze jsem na rootu a ze tudiz "topologicka dimenze" bude asi trochu neco jineho, nez co znam ze skoly ;-)

Taky mam dojem, ze jsme si trosku nerozumeli. Mozna doslo k zamene T. dimenze a H. dimenze (ze by uz ve skolnich textech :-). Pokud se shodneme na popisu T. dimenze tak, jak je popsana napriklad v http://en.wikipedia.org/wiki/Topological_dimension, tak je IMHO zrejme, ze kazda krivka ma T. dimenzi rovnu jedne (o H. dimenzi se tam nemluvi, ta je v pripade Hilbertovy krivky rovna 2).

Kdyztak sem zkuste napsat skolni definici T. dimenze, mam dojem, ze dojdeme ke stejnym zaverum.

Skolnich definic je vic - Ind, ind, dim (cili induktivni dimenze a Lebesgeuova, ktere jsme ale ve skole rikali jinak, snad Brouwerova). Jejich presne zneni viz wikipedie.

Tyhle definice se musi vypustit na nejaky topologicky prostor? V nasem pripade je timto prostorem co?

Obraz intervalu [0,1] se silnou topologii (viz http://en.wikipedia.org/wiki/Final_topology) nejspise da vysledek 1.

Uz je to sice davno, ale na termin Lebesgeuova mira si taky vzpominam. Jestli si dobre pamatuju, tak urceni topologickeho prostoru bylo potreba zavest napriklad (minimalne, duvodu bude vice) kvuli definici spojitosti - ta ma pri praci s krivkami dosti velky vyznam.

Pardon. V predchozim prispevku mam misto tecky otaznik. Tedy definice dimenze se musi vypustit na nejaky topologicky prostor. Coz je mnozina spolu se systemem jejich otevrenych podmnozin.

Otazkou tedy je, s jakym topologickym prostorem tu pracujeme. Pokud jim bude obraz krivky (tedy mnozina f([0,1]) se silnou topologii (viz odkaz v predchozim prispevku), tak nam (skoro urcite) vyjde topologicka dimenze rovna jedne. Jenze tahle silna topologie na ctverci rozhodne ani trochu nepripomina tu standardni. A to je to, co iniciovalo muj prvni prispevek.

To zda ta nase mnozina ma topologickou dimenzi jedna nebo dva zalezi na tom, jakou topologii si na ni vybereme, zatimco v definici Hausdorffovi dimenze se pouzivaji metricke pojmy, coz v tomto kontextu znamena, ze pri jejim vypoctu pokladame mnozinu f([0,1]) za podmnozinu R^2 se standardni metrikou.

Tedy tvrzeni, ze f([0,1]) ma topologickou dimenzi rovnou jedne a Hausdorffovu dimenzi rovnou dvema je nepravdive, protoze oba pojmy se vztahuji k mnozine s jistou topologii (respektive metrikou), a tudiz vezmeme-li pri vypoctech stejnou metriku dostaneme obe dimenze rovne dvema.

Pokud nase krivka neni f([0,1]), ale treba to samo spojite zobrazeni f: [0,1] -> R^2 jak se to standardne bere v analyze, pak mi prosim vysvetlete jak jsou definovane topologicka a Hausdorffova dimenze pro jedno konkretni spojite zobrazeni :)

Punchline: Topologicka dimenze se nezachovava spojitymi obrazy.

No me by zajimalo, pro jakou definici topologicke dimenze vychazi dimenze libovolne _krivky_ vetsi nez 1. Berme ted obecnou krivku, to ze zrovinka H. krivka limitne pokryva ctverec (takovych krivek je vice) ty obecne uvahy nemusi nijak narusovat. Tj., velmi laicky receno, je mozne obecnou krivku "rozmotat" tak, abych dostal _neco jineho_ nez pouhou usecku/primku?

Dival jsem se na Wikipedii na definici silne topologie a nepripadne mi na tom nic extrovniho - jestli to dobre chapu, tak pouze zavadi homomorfismus na zobrazeni, ale to nas problem s krivkou (IMHO, nejsem matematik) nijak neresi.

Nas problem s krivkou nejspise bude ten, ze porad nejak nevime co je to ta krivka. :-]

Kdyz chceme mluvit o jeji topologicke dimenzi, musi to byt topologicky prostor. Kdyz chceme mluvit o jeji Hausdorffove dimenzi, musi to byt metricky prostor (coz je specialni pripad topologickeho prostoru). Chceme-li davat tyto dve dimenze do souvislosti, meli bychom pro vypocet topologicke dimenze pouzit topologii, kterou dostaneme z metriky, jiz jsme pouzili pro vypocet Hausdorffovi dimenze.

uz se nam ten prostor pro prispevky nejak zuzuje, budeme muset zalozit nove vlakno :-)

V tom svem predposlednim prispevku mam chybu, protoze krome otevrenych krivek (topologicky shodnych s useckou/primkou) samozrejme existuji i uzavrene krivky (kruznice), ale s temi mohou byt problemy, minimalne pri chapani krivky jako zobrazeni R->E^2 (nebo do jineho prostoru).

S temi prostory mate pravdu, pro vypocet H. dimenze (a dalsi operace) potrebujeme pojem vzdalenosti. To pro topologickou dimenzi neni zapotrebi. Ja krivku porad chapu "analyticky", at uz je popsana nekolika par. funkcemi ci jinak. Proste zobrazeni z R do nejakeho prostoru (vetsinou E^2 nebo E^3, to vsak neni podminkou).

Na wikipedii uvadeji tuto definici:
Je-li M uvažovaný prostor (resp. varieta) a I interval, pak křivkou rozumíme diferencovatelné zobrazení φ(x) z I do M takové, že φ'(x) není nulové pro žádné x z I.

Ja mam vubec pocit, ze tahle diskuse neni zrovna na spravnem miste :)

Krivka je standardne definovana jako zobrazeni s nejakymi vlastnostmi z intervalu realnych cisel kamsi (E^2, E^3, varieta, obecny topologicky prostor). Nazveme toto zobrazeni f a ten interval I.

V diferencialni geometrii se po f chce presne to, co jste napsal. Aby bylo diferencovatelne a melo nenulovou derivaci (cili gradient). Takovehle krivky skutecne zachovavaji dimenzi v tom smyslu, ze f(I) ma topologickou dimenzi rovnou 1.

Jenze nase Hilbertova krivka takova neni. Ona totiz neni vubec diferencovatelna.

Pro topologickou dimenzi potrebujeme topologicky prostor. To je mnozina s topologii, kde topologie je sada otevrenych mnozin. Tedy mame nejakou mnozinu M a pak sadu jejich podmnozin, ktera splnuje jiste axiomy. Kuprikladu rovina spolu s otevrenymi kruhy je topologicky prostor. Stejne tak rovina s otevrenymi ctverci. Tohle jsou pripady, kdy topologii mame v podstate zadanou nejakou metrikou (ta nam da ty otevrene koule). Pak ale existuje jeste nepreberne mnozstvi topologii, ktere zadnou metrikou byt zadane nemohou.

My jsme tu s nasi Hilbertovo krivkou. To je spojite zobrazeni z [0,1] do [0,1]x[0,1], ktere je surjektivni (tedy je na). Chceme-li nejakym zpusobem zmerit jeji topologickou dimenzi je nutne ji chapat jako topologicky prostor. Stejne tak chceme-li zmerit jeji dimenzi Hausdorffovu, musime ji chapat jako metricky prostor. To druhe prirozene udelame tak, ze se podivame na f([0,1]), tedy na ctverec, a za metriku vezmeme standartni funkci vzdalenosti v rovine. Tohle chapani Hilbertovo krivky jakozto metrickeho prostoru nam ale umoznuje spocitat i jeji topologickou dimenzi (protoze na metricky prostor muzeme nahlizet jako na specialni pripad topologickeho).

Ja vidim jen jeden rozumny zpusob jak Hilbertove krivce priradit Hausdorffovu dimenzi a ten je popsany v predchozim odstavci. Naproti tomu je mnoho zpusobu jak Hilbertovu krivku chapat jako topologicky prostor (i kdyz ja nevidim jine, nez vzit f([0,1]) jako nosnou mnozinu a na ni uvazovat ruzne topologie) a kazdy z nich muze davat jinou topologickou dimenzi. Nicmene pokud budeme chapat Hilbertovu krivku jako topologicky podprostor E^2, pak jeji topologicka dimenze vyjde 2.

Vyborne, ten predposledni odstavec myslim celou nasi diskusi osvetlil (omlouvam se za pocatecni nechapavost). Ano, Hilbertova krivka a mnohe dalsi - abych neodbihal od tematu, tak i Kochova krivka - opravdu nejsou diferencovatelne, a to dokonce ani v zadnem svem bode.

Hilbertova krivka je jiste zobrazeni z [0,1] do [0,1]x[0,1]. Na vypoctu Hausdorffovy dimenze se, jak vidim, shodneme, proste se vezme metrika v E^2 jako vzdalenost dvou bodu. Nicmene neni mozne pouzit jiny topologicky prostor vychazejici z [0,1]?

Ta podminka diferencovatelnosti snad nemusi vzdy platit, vzdyt i jine krivky nejsou v celem svem oboru diferencovatelne (asi nejjednodussi je 1/x), u nekterych se neda zjistit hodnota v nejakem bode ani limitou zprava ci zleva (opet namatkou sin 1/x) a porad zde muzeme mluvit o topologii a dimenzi. Uznavam, ze Hilbertova krivka je odlisna v tom, ze neni diferencovatelna v zadnem svem bode, ale zavadet kvuli tomu topologii zalozenou na mnozine obsahujici v limite body s nulovou mirou...

Na diferencovatelnost se klidne v definici krivky muzem vykaslat a vzit jen spojite zobrazeni z intervalu kamsi. Jen to nebude mit takove pekne vlastnosti.

Pokud je mi znamo, tak 1/x je diferencovatelna v celem svem definicnim oboru. sin 1/x neni definovana v nule, takze jeji hodnotu tam nemuzeme zjistovat.

O topologii a (top.) dimenzi muzeme mluvit i u naprosto "uchylnych" prostoru. Cantoruv stan, jezek, dlouhe primky, ...

Vasi posledni vetu nechapu, ale podstatne je odpovedet na vasi otazku, zda neni mozne pouzit jiny topologicky prostor vychazejici z [0,1]. Ja myslim, ze ne. Navic byste to pak nemohl davat do souvislosti s tou Hausdorffovou dimenzi. Protoze kazda dimenze by merila jiny prostor.

Nice,

jinak nic proti Wikipedii, ale k topologii, mire a fraktalum je IMHO hodne dobra knizka
Edgar, Gerald A., "Measure, topology, and fractal geometry", Springer-Verlag, New York, 1990. 230 pp. ISBN 0-387-97272-2
jsou toho 2 dily a clovek tam najde spousty zajimavejch veci, a hlavne definice vsech moznejch dimenzi na ktery si matematici vzpomeli ]:)

Můžu se zeptat jekou sovislost ma pernoseho pokryti na titulnim obrazku se zbytkem clanku?

Reklama na dalsi cast, vzdyt se nejedna o nic jineho nez zavorkovy L-system :-)

Doopravdy: pri zmensovani obrazku Sierpinskeho krivky a Hilbertovy krivky byly ty obrazky v danem rozliseni 80x80 pixelu docela skarede (slevani sousednich hran), takze jsem vybral hezci obrazek. Ale opravdu se jedna o L-system, gramatiku pro nej neni tezke najit.

Mel bych par pripominek k funkci applyRules, ktera ma provadet paralelni aplikaci pravidel na axiom. V prvni rade se axiom vubec nepouziva, tato vada je pro Sierpinskeho trojuhelnik kompenzovana prevzetim rozvinute prave strany 2. pravidla (Y=...) a doplnenim F, coz da axiom YF, pro Hilbertovu krivku se tak axiomem vlastne stava Y misto X. Navic pouzity zpusob prepisovani pravych stran pravidel misto klasickeho nahrazovani znaku v axiomu zpusobuje, ze zadana maximalni iterace vede na obrazec s iteraci 2^maxiter (priklad pro Kochovu krivku: F=F+F--F+F, 1. F=F+F--F+F+F+F--F+F--F+F--F+F+F--F+F 2. F=F+F--F+F+F+F--F+F--F+F--F+F+F--F+F+
F+F--F+F+F+F--F+F--F+F--F+F+F--F+F--
F+F--F+F+F+F--F+F--F+F--F+F+F--F+F+
F+F--F+F+F+F--F+F--F+F--F+F+F--F+F).

Mate pravdu, tu funkci jsem "bastlil" na posledni chvili (puvodne byla napsana uplne jinak, ale potom jsem objevil jednu chybu, ktera by se sice na dnesnich gramatikach neprojevila, ale pro jina pravidla uz ano).

Mel jsem dojem, ze takto udelane prepisovani je rychlejsi, protoze dochazi k mene kopiim novych retezcu do retezcu starych (samotne nahrazovani urychlit moc nejde, ale porad je implementovano lip, nez napr. nahrazovanim znaku ala Java). Zkusite navrhnout korektni reseni? (myslim, ze postacuje zmenit "prostredni" smycku tak, aby brala v uvahu i axiom).

Zdravim, pokusil jsem se narychlo funkci applyRules() upravit do korektni podoby a vysledek vypada nasledovne (kontrolni vypisy jsou zakomentovane):

//-----------------------------------------------------------------------------
// Aplikace prepisovacich pravidel na retezec
//-----------------------------------------------------------------------------
void applyRules(
        char *rules[],                          // pole prepisovacich pravidel
        char *axiom,                            // axiom - prvotni naplneni retezce
        char *ret,                              // retezec, do ktereho se ma ulozit vysledek
        int maxiters)                           // maximalni pocet iteraci (aplikaci pravidel)
{
    int rulesCount;                             // pocet pravidel
    char *leftSide;                             // pole levych casti prepisovacich pravidel
    char **rightSideSrc;                        // pole pravych casti prepisovacich pravidel
    int i, j, k, iter;                          // pocitadla smycek a indexy znaku
    char src[MAX_LENGTH];

    // zjistit celkovy pocet prepisovacich pravidel
    for (rulesCount=0; rules[rulesCount]; rulesCount++)
        ;
    // nyni mame v promenne rulesCount ulozen pocet prepisovacich pravidel
    printf("celkovy pocet pravidel=%d\n", rulesCount);

    // alokace pameti pro levou stranu prepisovacich pravidel
    // a inicializace pole znaku
    leftSide=(char *)malloc(rulesCount*sizeof(char));
    for (i=0; i<rulesCount; i++)
        leftSide[i]=rules[i][0];

    // alokace pameti pro pravou stranu prepisovacich pravidel
    // a inicializace pravych stran
    rightSideSrc=(char **)malloc(rulesCount*sizeof(char *));
    for (i=0; i<rulesCount; i++) {
        rightSideSrc[i]=(char *)malloc(MAX_LENGTH);
        strcpy(rightSideSrc[i], rules[i]+2); // podretezec za znakem '='
    }

    // nastaveni axiomu
    strcpy(ret, axiom);

    // hlavni iteracni smycka
    for (iter=0; iter<=maxiters; iter++) {
        j=0;
        printf("iteration=%d\n", iter);
        strcpy(src, ret);
        puts(src);
        char *ch;
        // projit celym retezcem
        for (ch=src; *ch; ch++) {
            int left;
            int found=0;
            // pro kazdy znak zjistit, zda pro nej neexistuje prepisovaci pravidlo
            // a pokud ano, provest prepis
            for (left=0; left<rulesCount; left++) {
                if (leftSide[left]==*ch) {
                    //printf("%c -- %s\n", *ch, rightSideSrc[left]);
                    for (k=0; rightSideSrc[left][k]; k++, j++)          // provest prepis
                        ret[j]=rightSideSrc[left][k];
                    found=1;
                }
            }
            // zadne pravidlo pro dany znak jsme nenasli, proto se znak
            // pouze zkopiruje
            if (!found) {
                //printf("%c -- %c\n", *ch, *ch);
                ret[j]=*ch;
                j++;
            }
        }
        ret[j]=0;
    }
}

pod ouchylnej clanek, jenom ouchylny prispevky ;-)

Jestli myslite ty 3D obrazky, tak ano. Asi uz nebudu psat vlastni program na jejich generovani a vykreslovani, pouzijeme skvely program L-Parser (ten vygeneruje z gramatiky polygony) a potom POV-Ray (raytracer, ktery ty polygony zobrazi).