Diskrétne symetrie 1 (diskuse)

[deda.jabko]

ja to vzdavam... sice je ten clanek asi nejlepsi z toho co jsi zatim o symetriich napsal... ale je to ubijejici nuda... prijde mi to jako vytah ze skript algebra 1... a co je nejhorsi... porad nevim, co jsou to ty symetrie a k cemu je to dobre. :-]]

[Marek Bernát]

ja to vzdavam...

Každopádne dík, že si na to pozrel

sice je ten clanek asi nejlepsi z toho co jsi zatim o symetriich napsal...

To beriem ako kompliment

ale je to ubijejici nuda...

Mne to tak nepripadá. Ale ja čítam aj skriptá ako beletriu Čo s tým teda?

prijde mi to jako vytah ze skript algebra 1...

To môžem tiež považovať za kompliment, lebo žiadne skriptá z podobných oblastí som nikdy v ruke nemal a vymýšľal som si ten obsah z hlavy. A v prvej ankete väčšina hlasovala, že matematická úroveň môže zostať rovnaká, tak som predpokladal, že táto forma by nemusela vadiť.

a co je nejhorsi... porad nevim, co jsou to ty symetrie a k cemu je to dobre. :-]]

To vieš, začal som budovať teóriu a chcel som postupne ilustrovať jej aplikácie na zložitejších a zložitejších príkladoch. Rozumnejší postup som holt nevymyslel. Čo navrhuješ ty?

[deda.jabko]

Mne to tak nepripadá. Ale ja čítam aj skriptá ako beletriu Čo s tým teda?

ono jde psat citelne, presne a nemusi to byt definice-veta-dukaz-dusledek. ale je to otazka zvyku a stylu. sice moc neznam teoretickou fyziku... ale schvalne se zkus mrknout do nejakeho dobreho casopisu z vasi oblasti na to jakym stylem jsou psane...

To vieš, začal som budovať teóriu a chcel som postupne ilustrovať jej aplikácie na zložitejších a zložitejších príkladoch. Rozumnejší postup som holt nevymyslel. Čo navrhuješ ty?

ujasnit si, kdo jsou ctenari a co je smyslem toho serialu. zkus si predstavit, ze chces nekoho tim i zaujmout a ne jen jim predat fakta. formatem (pro sirsi verejnost), ktery se mi docela libil, byl serial o fraktalech, co vychazel na rootu.

a takova drobnost na zaver... i v tomto clanku pouzivas pojmy a notace, ktere sis predem nezavedl. napr. generator a jeho znaceni...

[Marek Bernát]

ono jde psat citelne, presne a nemusi to byt definice-veta-dukaz-dusledek. ale je to otazka zvyku a stylu. sice moc neznam teoretickou fyziku... ale schvalne se zkus mrknout do nejakeho dobreho casopisu z vasi oblasti na to jakym stylem jsou psane...

Myslíš odborného časopisu s odbornými článkami? O tých ti môžem povedať, že sú nečitateľné, ak neovládaš dosť pokročilú fyziku a matiku. Takže ako vzor by som to nebral

ujasnit si, kdo jsou ctenari a co je smyslem toho serialu. zkus si predstavit, ze chces nekoho tim i zaujmout a ne jen jim predat fakta. formatem (pro sirsi verejnost), ktery se mi docela libil, byl serial o fraktalech, co vychazel na rootu.

No, to som si už vcelku ujasnil vďaka anketám a tak. A aj vďaka tomu, že ten seriál dostáva stále pomerne vysoké hodnotenie, tak predpokladám, že (aspoň niektorí) ľudia sú spokojní. Samozrejme, budem hľadať cestičky, ako ho zlepšovať, takže ak to náhodou nevzdáš úplne a pozrieš sa aj na budúci diel, tak tvoja kritika bude opäť vítaná Na ten seriál o fraktáloch teda pozriem. Ale to je oveľa vďačnejšia téma, lebo človek môže kresliť pekné obrázky...

a takova drobnost na zaver... i v tomto clanku pouzivas pojmy a notace, ktere sis predem nezavedl. napr. generator a jeho znaceni...

Máš pravdu, že explicitne tam pojem generátor zavedený nie je. Ale jeho značenie tam je (1.2.2). Nechcel som z toho zasa spraviť úplne čisté skriptá a definovať každú blbosť. Myslím, že z pojmu cyklickej grupy a textu okolo je dosť jasné, čo to znamená "generovať grupu jedným prvkom", a teda aj čo je to generátor. Ale asi by bolo lepšie tam tieto veci napísať explicitne – takže dík za poznámku, premyslím si to.

[deda.jabko]

Myslíš odborného časopisu s odbornými článkami? O tých ti môžem povedať, že sú nečitateľné, ak neovládaš dosť pokročilú fyziku a matiku. Takže ako vzor by som to nebral

tak jsem to nemyslel.... schvalne se podivej treba na pomer definic/lemat/teoremu k poctu stran.

[Marek Bernát]

Nechápem. Fyzika sa zaoberá inými vecami než matematika, preto tam nič podobné nenájdeš (ak sa teda nejedná konkrétne o matematickú fyziku -- tam sú tie články písané práve štýlom definícia/veta/dôkaz). Úplne rovnako v matematickom článku zasa nenájdeš fyzikálne aplikácie, ale len tie vety a dôkazy. Takže čo sa vlastne snažíš povedať okrem triviálneho tvrdenia, že fyzika nie je matematika?

[JS]

Souhlasim s dedou.jabkem. Ja vim, ze se snazite, ale problem vidim v tomtez - skupina lidi, ktera je schopna precist vas text (= matematici), patrne tyto veci mela ve skole a tedy nemaji vlastne duvod to cist.

Ale chtel jsem podotknout k tomu uceni, prestoze na to nejsem zadny expert. Predevcirem jsem na Slashdotu narazil na odkaz na Khan Academy. Ten clovek natocil spoustu vyukovych videi (zejmena ze zakladu matematiky) pod CC a spoustu lidi si ho pochvalovalo, ze dokaze veci dobre vysvetlit.

Tak jsem koukal na par jeho videi a prisly mi strasne nezazivna - ze vyklada hrozne pomalu a opakuje se. Tak jsem premyslel, za predpokladu, ze on je dobry, proc mi pripada nezazivny. Odpoved je - protoze to znam! Pokud neco znate, je strasne snadne podlehnout dojmu, ze je to snadne. Ale neni. Takze je mozna lepsi chybovat na te druhe strane a predpokladat, ze lide jsou hloupejsi (coz ja sam delam nerad), a vysvetlovat to klidne pomalu a na jednoduchych prikladech; a nesnazit se o rigoroznost za kazdou cenu.

Druha vec je, co rikal Richard Feynman - na jmenech nezalezi. Je jedno, zda cyklickou grupu nazvete od zacatku cyklickou nebo ne. Podstatne je vysvetlit ten koncept a k cemu je dobry. Vas text zase ukazuje psani pro matematiky - kdyz pisete pro matematiky, tak definice prichazi prvni, a je to tak v poradku, protoze to je styl, na ktery jsou zvykli. Pokud ale neco chcete vysvetlit, muzete si formalni definici nechat klidne az na konec odstavce (nebo do poznamky pod carou), az za motivujici priklady, a mozna dokonce i az za nejaky ten dukaz.

[Marek Bernát]

Souhlasim s dedou.jabkem. Ja vim, ze se snazite, ale problem vidim v tomtez - skupina lidi, ktera je schopna precist vas text (= matematici), patrne tyto veci mela ve skole a tedy nemaji vlastne duvod to cist.

Myslím, že pozitívne ohlasy a hodnotenia seriálu toto Vaše tvrdenie bezpečne vyvracajú Je kopa ľudí, ktorí nejakú matematiku ovládajú, ale grupy a symetrie buď nevideli nikdy, alebo len z rýchliku.

Ale chtel jsem podotknout k tomu uceni, prestoze na to nejsem zadny expert. Predevcirem jsem na Slashdotu narazil na odkaz na Khan Academy. Ten clovek natocil spoustu vyukovych videi (zejmena ze zakladu matematiky) pod CC a spoustu lidi si ho pochvalovalo, ze dokaze veci dobre vysvetlit.

Mrknem na to, dík za odkaz.

Tak jsem koukal na par jeho videi a prisly mi strasne nezazivna - ze vyklada hrozne pomalu a opakuje se. Tak jsem premyslel, za predpokladu, ze on je dobry, proc mi pripada nezazivny. Odpoved je - protoze to znam! Pokud neco znate, je strasne snadne podlehnout dojmu, ze je to snadne. Ale neni. Takze je mozna lepsi chybovat na te druhe strane a predpokladat, ze lide jsou hloupejsi (coz ja sam delam nerad), a vysvetlovat to klidne pomalu a na jednoduchych prikladech; a nesnazit se o rigoroznost za kazdou cenu.

No, ale veď o to som sa v tomto diele trochu snažil. Takmer nikdy som nenadefinoval pojem, ktorý by spadol z neba. Ten text okolo sa naňho vždy snažil trochu pripraviť. Ale uznávam, že by mohlo pomôcť viac motivácie + príkladov na úkor rigoróznosti. Popremýšľam nad tým do ďalšieho dielu.

Druha vec je, co rikal Richard Feynman - na jmenech nezalezi. Je jedno, zda cyklickou grupu nazvete od zacatku cyklickou nebo ne. Podstatne je vysvetlit ten koncept a k cemu je dobry. Vas text zase ukazuje psani pro matematiky - kdyz pisete pro matematiky, tak definice prichazi prvni, a je to tak v poradku, protoze to je styl, na ktery jsou zvykli. Pokud ale neco chcete vysvetlit, muzete si formalni definici nechat klidne az na konec odstavce (nebo do poznamky pod carou), az za motivujici priklady, a mozna dokonce i az za nejaky ten dukaz.

Jasné, že nejde o pojmy, ale keď sa na ne budeme nabudúce odvolávať, tak bude dobré ich poznať. Čo sa cyklickej grupy týka, tak ten pojem tak úplne nespadol z neba, ale týka sa toho rozprávania o Z_n a symetriách n-uholníka. Ale asi to šlo formulovať lepšie a definície odložiť až na koniec. Popravde, o také niečo som sa snažil, ale návyk na skriptá ma asi zasa podvedome stiahol do oblasti definícia/veta/dôkaz

[hajoucha]

myslím, že to co požaduješ není možné splnit na zakázku. Jestli Tě baví symetrie, hledej dál a najdi vlastní řešení. Domnívám se, že jedině tento postup Ti přinese efektivní užitek. Když něco najdeš, pošli prosím tip i ostatním. Zde je něco, co jsem náhodou našel já: Symetry and the Monster popř. From error correcting codes...

[Marek Bernát]

Monster group je veľmi pekná vec, ale je to tak hlboká matematika, že by som sa o nej neodvažoval niečo písať

Ale tie samoopravné kódy vyzerajú lepšie. Niečo podobné by sa asi dalo časom použiť.

[hajoucha]

jen pro upřesnění - můj příspěvek byl reakcí na příspěvek dedy.jablko (nic proti němu). Tj. nemá cenu pořád kritizovat cizí výplody, protože "mě to přijde nuda a už jsem viděl lepší". Mnohem lepší strategie je prostě najít co vyhovuje mě, popř. to sám stvořit.

Jinak řečeno, velmi významnou hodnotou je to, že si Marek ošahá, jaké to je, když se píší skripta. To, že některým studentům nebudou vyhovovat (což je dobře) není jeho problém. Naopak se můžeme v budoucnu těšit z toho, že napíše ještě lepší a lepší texty a že _on_ té látce lépe a lépe porozumí. Možná dokonce tak, že to jednou bude moci někoho naučit.

[Marek Bernát]

Ja viem, ale chcem tam časom dostať aj zaujímavé príklady, takže keď budeš o niečom vedieť, tak neváhaj a daj vedieť

To je pravda. Ale o to skôr vítam každú kritiku (aj keď občas nie je úplne konštruktívna).

[hajoucha]

A ještě další poznámka - často tu zaznívá, že text je určen "matematikům, kteří už to ale beztak měli ve škole". To je ekvivalentní filozofie k "všechno důležité a potřebné nás naučí ve škole".

Dále - matematika _je_ složitá a těžká. Jestli vás to nebaví, jednoduše se na to vykašlete a dělejte dobře svou práci. Idea je: "pěstovat rýži taky neumíte, tak proč vás trápí, že neumíte grupy?".

[JS]

Nesouhlasim. Ta moje poznamka se tykala konkretniho textu, ktery napsal Marek, a me pripadal prilis matematicky pro nekoho, kdo ve skole uz teorii grup v nejake podobe nemel. Rozhodne si nemyslim to druhe a ani to z toho neplyne.

K te druhe poznamce - je to otazka. Ja dnes rano koukal na prednasku toho Sal Khana, co jsem ho zminoval vyse. Rika tam, ze byl prekvapeny, jak moc matematika podana jeho zpusobem nektere lidi bavila. Jeho filozofii je, rozdelit vyuku na male kousky, a v kazdem kousku vysvetlit nejaky koncept. Domniva se, ze timto zpusobem se da ucit cela matematika. Takze si rikam, jestli ta bariera ("matematika je tezka") neni jen umela.

[Dadam]

Když už mluvíš o té grupě čísel %n, mám pro tebe jeden poznatek: jako projekt do školy jsme měli rotaci pole x čísel o y prvků. Nepamatuju si přesné zadání, nicméně dělal jsem to přímo v tom poli, nikoliv kopírováním do pole jiného. S algoritmem jsem si hrál, dokud se mi nezačal líbit, a všiml jsem si, že teorie, kterou jsem si kolem toho dělal, se nápadně podobala teorii, kterou jsme dělali rok zpátky v matice. Už jsem si to nepamatoval, takže jsem to nedopracoval, ale jako příklad z "praxe" by to snad šlo.
A k seriálu: Myslím že se tu objeví spoustu negativních komentářů o tom, že je to moc teoretické. Ano, je. Ke kvalitě by tedy mohlo docela přispět, kdyby se (třeba pod seriálem v komentářích) objevily příklady z praxe, které by ukazovaly využitelnost v programování a programování obohatily o teoretický základ. Který je IMHO velmi důležitý např. při optimalizacích. Takže oslovuju kohokoliv, kdo má něco podobného jako já, aby to sem dopsal, samozřejmě pokud má autor zájem. Pokud má, udělám i tu teorii okolo rotace.
A poslední: ocenil bych, kdyby názvy .pdf souborů byly číslované (ano, udělat sám si to můžu)

[Dadam]

A mimochodem - nebyl by nějaký způsob, jak soubory ukládat tady na serveru?

[Marek Bernát]

To by aj mňa zaujímalo. V správe blogu je len upload obrázku/videa (a to video mi ani nefunguje). Neviem, ako je to s ostatnými súbormi.

[Jirka Keresteš]

Je na to zaznam v bugzille (#1226), ted jdou vkladat jine soubory jenom jako priloha ke komentari.

Jinak serial je super, tesim se na dalsi dil.

[Dadam]

Jakože mně se to taky líbí, doufám že si autor nemyslí opak

[Marek Bernát]

Dík vám obom za podporu. Jabkove komentáre ma vždy demotivujú (aj keď viem, že to myslí dobre), takže potrebujem aj pozitívny ohlas z času na čas

[deda.jabko]

z toho si nic nedelej, me zase demotivuji jini...

[Marek Bernát]

Když už mluvíš o té grupě čísel %n, mám pro tebe jeden poznatek: jako projekt do školy jsme měli rotaci pole x čísel o y prvků. Nepamatuju si přesné zadání, nicméně dělal jsem to přímo v tom poli, nikoliv kopírováním do pole jiného. S algoritmem jsem si hrál, dokud se mi nezačal líbit, a všiml jsem si, že teorie, kterou jsem si kolem toho dělal, se nápadně podobala teorii, kterou jsme dělali rok zpátky v matice. Už jsem si to nepamatoval, takže jsem to nedopracoval, ale jako příklad z "praxe" by to snad šlo.

Mno, ale úplne presne netuším, jak by to malo súvisieť so symetriami/grupami. O čo v tej úlohe presne išlo?

A k seriálu: Myslím že se tu objeví spoustu negativních komentářů o tom, že je to moc teoretické. Ano, je. Ke kvalitě by tedy mohlo docela přispět, kdyby se (třeba pod seriálem v komentářích) objevily příklady z praxe, které by ukazovaly využitelnost v programování a programování obohatily o teoretický základ. Který je IMHO velmi důležitý např. při optimalizacích. Takže oslovuju kohokoliv, kdo má něco podobného jako já, aby to sem dopsal, samozřejmě pokud má autor zájem. Pokud má, udělám i tu teorii okolo rotace.

Zaraďovať viac a viac praxe je v pláne v súlade s tým, ako sa bude zväčšovať množstvo prebratej teórie. Premýšľal som nad viacerými prístupmi a tento mi prišiel najlepší. Čo očakávaš od tej praxe? Ok, môžem ilustrovať nejakú pomerne pokročilú aplikáciu, ale nikomu nebude jasné, o čo tam ide, lebo nebude rozumieť grupám. Takže v tom bude zasa zmätok. Každopádne, ak bude ľud chcieť ubrať teórie, tak sa prispôsobím

A poslední: ocenil bych, kdyby názvy .pdf souborů byly číslované (ano, udělat sám si to můžu)

Ok, opravím to.

[Dadam]

Přečetl jsem si zhruba první stránku a půl a tady je výsledek, doufám že tam nenapíšu nějakou blbost:
Zadání: Napište funkci void rotuj(int *cisla, int d, int n), která provede rotaci pole cisla délky d o n prvků doprava.
Teorie: Vytvořit nové pole, čísla přesunout do něj a pak rotovat zpátky by bylo pro velké rozměry neefektivní, proto se hodí pracovat nad daným polem. Vezmete první prvek, přesunete ho o k míst doprava. Co s prvkem, který tam byl před ním? To samé, nicméně se opět dostanete před stejný problém. Můžete pokračovat, ale časem se dostanete na konec pole a přeskočíte na začátek. Pokud budete pokračovat dál, můžou nastat dva scénáře, buď zrotujete celé pole a vrátíte se na prvek s indexem 0, nebo se vrátíte na index 0 a část prvků zůstane nerotovaná. Tady jsem začal odvozovat a počítat jak blbý, protože mě nenapadlo že se pohybuji v cyklické grupě.
Funkce pak vypadala tak, že byly dva vnořené cykly, vnitřní prováděl to, co jsem popsal nahoře, a vnější to opakoval pro nerotované prvky.
Dál to rozvádět nebudu, všechno najdete v článku, jen přikládám seznam problémů, které jsem řešil:

• Jak určím počet iterací pro vnitřní cyklus?
• Jak určím počet iterací pro vnější cyklus?
• Jak určím krok vnější iterace?
• Může se stát, že první vnější iterace pokryje první dva prvky, třetí ne a čtvrtý a pátý ano?

Na všechny tyhle otázky (které vyvstávaly postupně) se odpověď dá najít v grupách, já to dělal... no už ani nevím jak

[Marek Bernát]

Uh, to mi pripadá strašne zložité. Môj algoritmus by bol:

tmp = a[0]
g = gcd(d,n)
for i in range(d/g - 1):
  a[i * g] = a[(i+1) * g]
a[d-g] = tmp

Ale je pravda, že zopár vecí z článku by sa na to dalo aplikovať. Skúsim si nabudúce vymyslieť nejaký podobný príklad, na ktorom by som niečo ilustroval. Uvidíme, či ma niečo napadne.

[Marek Bernát]

Ups, sorry, nejak som to nedomyslel. Máš pravdu, treba tam ešte jeden cyklus, ktorým sa presunie všetko z intervalu [0,g). V tom prípade by sa na tom dali ilustrovať ešte ďalšie grupové pojmy, ktoré by som chcel prebrať nabudúce

[:::]

tak nevim, tohle jsem vytvoril za 15min a bez teorie

inline void swap(int *a, int *b, int count)
{
        int *end = a + count;
        while (a != end)
        {
                int t = *a;
                *a = *b;
                *b = t;
                ++a; ++b;
        }
}

void rotate(int *a, int len, int count)
{
        while (1)
        {
                int left = count % len;
                if (left == 0) { break; }
                int right = len - left;
                if (right == left) 
                {
                        swap(a, a+left, left);
                        break;
                }
                else            
                if (left < right)
                {
                        swap(a, a+(len-left), left);
                        a += left;
                        len -= left;
                }
                else
                {
                        swap(a, a+(len-right), right);
                        len -= right;
                        count = len - right;
                }
        }

}

myslim ze na to jdes zbytecne slozite ;)

[Dadam]

Jak se dělá formátovaný kód? Dám ti sem moji verzi, pro srovnání

[:::]

napises:

<pre class="brush: c++">
... kod ...
</pre>

[Dadam]

void rotate (int *a, int len, int count)
{
    usigned int outer = MF(len, count);
    for (int i = 0; i < outer; i++) {
        int tmp = arr[i];
        for (int j = (i + k) % count; j != i; j = (j + k) % count) {
            swap(&arr[j], &tmp);
        }
        arr[i] = tmp;
    }
}

To je celé. Co chybí je funkce swap, která jen prohodí hodnoty dvou proměnných, a funkce MF (magic function), která na základě teorie grup spočítá kolikrát se má vnitřní smyčka opakovat. Výpočet není nijak náročný, bylo to něco jako délka/největší společný dělitel délky a posunu.

[:::]

Vypada to zajimave, ale mel bych par pripominek:

1. kdyz si nakreslis jak pracuje muj algoritmus tak z toho snadno pochopis jak funguje a proc funguje (a pochopi to 90% lidi). Zatimco u tve verze je jakasi MF o ktery average programmer nedokaze rict jestli funguje jak ma a proc

2. tvuj algoritmus dela vzdy N swapu, muj maximalne N-1 a idealne N/2 :)

3. pri posouvani o relativne vetsi cislo bude tvul alg. v podstate 'nahodne' skakat po pameti, coz si myslim povede k neefektivnimu vyuziti cache. Ale tohle je jenom ciste moje teorie... Mohl bys sem hodit jeste MF? Ze bych udelal benchmark

PS: predpokladam ze misto '(i + k) % count' ma byt '(i + count) % len' :)

[Marek Bernát]

1. To je práve pointa toho riešenia, ilustrovať trochu inteligentnejší (a podľa mňa aj elegantnejší) prístup s využitím teórie navyše.

2. irelevantné

3. diskutabilné.

MF je len nájdenie najväčšieho spoločného deliteľa gcd. Toho nájdeš jednoducho pomocou euklidovho algoritmu, ktorý aj pre veľké vstupy obvykle vyžaduje len pár krokov. Najhoršie sa chová na Fibonacciho číslach, kde pre zhruba n-té F-čísla trvá n-krokov. Vzhľadom k asymptotickému tvaru F-čísel pomocou exponenciály sa dá teda zložitosť gcd odhadnúť ako nanajvýš logaritmická. Ergo zanedbateľná voči zbytku algoritmu...

[:::]

1. to chapu, ale precejenom u algoritmu nemuzes zapomenout i na praktickou pouzitelnost. Pokud pracujes sam tak neni problem, ale pokud delas v teamu tak moje zkusenost rika 'the simpler the better'

2. rychlost je vzdycky relevantni :)

3. jasne, proto jsem psal ze je to jen moje teorie a ze udelam benchmark

[Dadam]

1. Máš pravdu. Nicméně chápu to tak, že každý z programátorů projektu má chápat každý řádek z celého projektu? Včetně třeba zdrojových kódů knihoven? Navíc jsem to psal narychlo (jak jsi asi poznal z chyb ), normálně bych to okomentoval, navíc MF by nebyla MF ale třeba pocet_podgrup. Což jsem mohl udělat rovnou, no nevadí. Mimochodem - pokud si můj algoritmus uděláš na papír, vyjde ti že vnitřní cyklus udělá jednu podgrupu a vnější to opakuje pro všechny.
2. Opět máš pravdu. Nicméně může se vyskytnout situace, kdy můj bude lepší. Nevím jaká, ale může.
3. Opravdu je to GCD? Chm chm chm Chtělo by to podívat se pořádně na ty grupy Jinak Euklidův algoritmus se IMHO dá optimalizovat takhle:
while (a != b) {
    if (a > b) a = a % b;
    else b = b % a;
}
4. Facepalm. Zrovna jsem si všiml Nápovědy k formátování. Hledal jsem nápovědu k portálu, FAQ a ono je to tady...

[Dadam]

Šel by, prosím, tento příspěvek a příspěvek nad ním smazat? Nějakým omylem jsem ho odeslal dvakrát

[Dadam]

Tak neodeslal... Porucha byla, zdá se, na mém přijímači. Žádost o smazání tímto stahuji

[Marek Bernát]

Vyjadrím sa len k 3.: čo tak sa pozrieť znova na môj seriál, konkrétne posledné riadky? Píšem tam, že podgrupu, ktorú generuje k v Z_n, je práve gcd(k,n). Počet jej prvkov je potom pochopiteľne n / gcd(n,k) (to už tam napísané nie je, ale je to zrejmé ).

Dosť podivná verzia. Ja mám radšej

int gcd(int a, int b) {
  if (!b)
    return a;
  return gcd(b, a%b);
}

[Ladicek]

TCO z Céčkových překladačů snad dělá jenom gcc, ne?

[Marek Bernát]

Napadlo ma, že sa niekto chytí pamäťovej zložitosti, ale nechal som to tak. Písať ten príklad v Scheme by veci asi veľmi nepomohlo Ono, aj tak bude v priemere hĺbka toho volania O(1), takže je to vcelku nepodstatné

[Dadam]

Nevím jestli to tu bude ještě někdo číst, nicméně uvědomil jsem si jednu výhodu mého algoritmu, která mě předtím nenapadla. Ne vždycky je prioritou rychlost, někde potřebuješ stabilitu, předvídatelnost atd. Můj algoritmus se dá zcela popsat nějakým matematickým aparátem, takže 1) by mělo jít dokázat, že se nikdy nezacyklí ani nespustí segfault 2) jde jednoduše zjistit, jak dlouho bude trvat.

[asap]

nic osobního, ale nečetl jsem to kvůli jazyku. škoda :(

[Dadam]

tím bych se být tebou nechlubil

[Dag]

Bola to zábava, ale pre budúcnosť sa budem musieť naučiť MetaPost. Ak sa tu naň nájde nejaký odborník, tak by som si rád vypočul, ako dlho by podobný obrázok trvalo vyrobiť v ňom.

Odborník (skutečný) nejsem, ale tohle udělat v MetaPostu by nebyl problém. Samozřejmě po naučení základů.

[Marek Bernát]

No, také niečo som aj čakal. Ale skôr by som rád videl nejaký pekný príklad, kým sa do toho MetaPostu pustím. Dá sa napr. vygenerovať ten šesťuholník a kruhy s číslami na pár riadkoch? Veľmi by som ocenil, keby ste sem napísali k tomu napísali kód. Samozrejme, len ak na to máte čas; nechcem Vás zbytočne otravovať

[Marek Bernát]

Přílohy:

• test.ps (8632 bytů)
• test.mp (567 bytů)

Tak niečo malé som po troche googlenia dal dokopy. Ale ako je vidieť, dokonalé to nie je. Asi by nebolo od veci opýtať sa v poradni

[Dag]

To je pěkný!

[Dag]

Jednu čast a otočit o šedesát stupňů. Na pár řádek to může být. To ale záleží na definici "pár řádek". Sorráč, jsem v časovým presu víc teď nesepíšu.

Na MetaPost jsou asi dvě knížky na internetu. Myslim Krátká a ... Google. Tam jsou základy a zdrojáky. Zatom ahoj, běžim pracovat, kdy skončim nevim (pár dní možná).

[Marek Bernát]

Už som to dostal do relatívne použiteľnej formy; aj so šípkami a tak. Ale tak pekné jak tie obrázky z Inkscapeu to nie je. Problém je samozrejme na mojej strane, neviem ešte úplne všetko poriadne nastaviť. Resp., viem, ale len strašne pracne, lebo neovládam pokročilejšie vlastnosti toho jazyka.

Google mi už bol vcelku na nič, takže som stiahol User Manual a MetafontBook. Tam už som si dohľadal, čo som potreboval. No, a na ďalšie pokroky už budem potrebovať asi hlavne prax. Tak či onak, hlavné je, že som začal a zatiaľ som z MetaPostu nadšený

[Dag]

Miroslava Krátka sepsala tohlea myslím, že se s tim dá. Ale to už asi znáš a jdeš do hloubky.

Já nepíšu od sebe, takže jen jak si vzpomínám. V angličtině toho bude mraky.

JInak se mi zdá MataPost prostě elegantní. Myslim výsledek, ty obrázky.

[Dag]

Ta ale používí mfpic. Ale to jde také kombinovat.

[Marek Bernát]

Dík za odkaz, mrknem na to. Na nete je všeličo, ale maximálne mi to môže slúžiť ako inšpirácia a vzor pre kvalitnejšie písanie kódu. Obvykle totiž už potrebujem zistiť, jaké presne sú funkcie ku ktorému dátovému typu atp. a na to sa dokonale hodí manuál/dokumentácia Btw, najviac mi asi dal seriál na Roote. Je tam prakticky všetko, čo človek potrebuje pre začiatok vedieť.

Jj, MetaPost je skvelý. Ale vygooglil som, že kopa ľudí ho už v dnešnej dobe považuje za zastaralý a používa nové nástroje, ktoré sa ním inšpirovali. Asymptote napr. (má c++-like syntax, ale inak je to veľmi podobné) a veľa ďalších.

[zimous]

Následující myslím v dobrém, třeba něco zaujme.
1) Pěkně napsanej kousek skript, pokud to je to, co chceš, jen tak dál. Ale je to hrozně suchý. Systém definice-věta-důkaz může hodně lidí odradit. Pojmy izomorfismu a podgrupy se daj vysvětlit intuitivně, homomorfismum bych se určitě aspoň ze začátku vyhnul. Kdo to chce formálně, najde si to ve skriptech (viz bod 7). A pokud to i tak chceš psát, doporučil bych systém a) nejdřív neformální hodně kecací úvod s příkladama a ilustracema tvrzení bez důkazů, b) formální apendix, kde všechno korektně zadefinuješ a dokážeš.
2) Málo příkladů. V podstatě si probral a nakreslil jenom Z6. Ukázat jich víc: třeba nejmenší Z2 (hned můžeš poznamenat, že otočení o 180 je totéž co středová symetrie, když už to má bejt o symetriích), pak třeba Z3, Z5 (ukázat výjimečnost prvočísel, když už se chceš zabejvat podgrupama), dál uvedenou Z6, ale i Z4 nebo Z18 (abys naznačil jak se ta Eulerova funkce komplikuje).
3) Nevhodný příklady. Symetrie mnohoúhelníků jsou prostě dihedrální grupy, ne cyklický (automatická první odpověď). Zákaz reflexí je trochu matoucí a z obrázku není vidět. Takový ozubený kolo se zahnutejma zubama by posloužilo mnohem líp a vnucovalo tu rotaci. To, že si vrcholy šestiúhelníku očísloval, optickýmu vnímání symetrie taky nepomáhá.
4) Příklady a aplikace z jinejch oborů. O tom se tu už psalo, ten příklad na rotaci pole je prostě geniální. Z toho ty podgrupy přímo kapou (dokonce maximální:). Dál by se dalo zabrousit i do grafiky a aspoň ukázat, jak vypadá matice takový rotace (abych si trochu pohonil reprezentace;).
5) Je tam někde zdůrazněná komutativita? Možná by se hodil i odstaveček o aditivní notaci.
7) Odkazy na literaturu nebo net.
8) A jak tohle všechno udržet rozumně dlouhý? Každá rada drahá, to je umění.
9) Na kreslení obrázků v LaTeXu se výborně hodí PGF/TikZ.

[zimous]

Ještě drobnost. V nadpisu máš sice diskrétní symetrie, ale zrovna u rotací by se přeci jenom ta SO(2) alias kružnice zmínit dala. Přece jenom jsou to všechno právě její diskrétní podgrupy. Jak jsem už psal u předchozího blogu, kompaktní spojitý grupy jsou v mnoha ohledech (jako je třeba ehm, kompaktnost:) podobnější konečným, než nekonečný diskrétní. Grupu Z si těžko představíš jako rotace.

[Marek Bernát]

Máš samozrejme pravdu. A spojitým grupám sa tak či tak nedá vyhnúť, či už pri reprezentáciách, alebo pri pontryaginovských duáloch. Resp. dá sa, ale bola by to trochu škoda.

[Marek Bernát]

Sorry za oneskorenú odpoveď, týždeň som bol mimo civilizáciu

Všetky tvoje komentáre sú moc dobré. Nechám si to zasa prejsť hlavou a uvidíme, čo z toho vypadne. Tak či onak, táto forma skrípt zopár ľuďom vyhovuje, takže sa jej asi budem držať. Keď som minule používal len príklady (aj keď možno boli trochu zložitejšie z fyziky), tak sa to s takým úspechom nestretlo. Takže asi zostanem pri skriptách, ale určite skúsim ísť cestou väčšieho množstva príkladov a okecávania. Dík za reakciu a dúfam, že niečo napíšeš aj k ďalším dielom.

[hajoucha]

já bych měl prosím taky jednu prosbu....když jsem to četl, tak jsem měl trochu potíže s "mentálními skoky" tj. bylo pro mne těžké číst od začátku do konce. Tj. nové věci se objevují jaksi "ad hoc" a není jasné, jak souvisí s těmi předchozími. Vysvětluji si to tak, že Marek ví spoustu věcí a chce je rychle čtenáři sdělit. Kdybych byl starší, tak bych asi napsal, že to přisuzuji mladické netrpělivosti, hehe :)

Jinak řečeno - klidně bych si přečetl o dvě tři stránky více, ale měl logickou strukturu, kdy "druhé plyne z prvního".

Je taky docela možné, že tohle jsou jakési dětské nemoce, které se přirozeně ztratí při psaní dalších dílů...které s velkou zvědavostí očekávám.

[Marek Bernát]

Ak sú tam tie tzv. "mentálne skoky", tak, prosím, daj vedieť konkrétne kde. Určite niektoré veci, ktoré považujem za zrejmé a/alebo prirodzené, proste preskočím, ale niekomu inému už to tak zrejmé pripadať nemusí.

Čo sa týka počtu strán, tak nerád by som to naťahoval. Seriál síce bude mať skriptoidnú formu, ale predsa len by to malo byť ešte ako tak stráviteľné. Ak to bude moc dlhé, tak to už fakt môžeš rovno čítať nejaké skriptá (navyše v oveľa vyššej kvalite).

Btw, zdá sa, že tých pripomienok je už celkom dosť, takže možno skúsim neskôr vydať opravenú/vylepšenú verziu tohoto dielu. Aj keď to už nikto nebude čítať, tak len tak, aby som sa pocvičil

[hajoucha]

mrknu se na to, aktualne nemam prislusne listy u sebe.

Co se tyce delky a kvality - podle meho skromneho nazoru se delky nemusis bat. Opravdu odstrasujicich rozmeru to nenabyde a 2-3 stranky misto 1-2 stranek - to nehraje roli. Jinak receno - upravy, ktere jsem si tak predstavoval, by znamenaly par vet, nejvyse par odstavcu navic.

Co se tyce moznosti cist nejaka skripta s popr. mnohem vyssi kvalitou - tohle uvazovani nikam nevede. Tohle je _Tvoje_ dilo. Nikdy nemuzes vedet, pro koho dalsiho jeste bude dobre. Ale uz ted vis, ze muze byt hodne dobre pro Tebe.

Navrhuji udelat ho nejlepe jak to jde _ted_ a prestat se ohlizet na to, jestli se dostanes do nejakeho pomyslneho zebricku top10 nejlepsich skript na svete. Copak to je Tvoje posledni a jedine dilo? V tom pripade to beru a pak na tom opravdu jeste tak 20 let popracuj, nez to vydas. Pak to bude zcela jiste hodne hodne dobre skriptum (a to prave proto, ze do neho bude vlozeno 20 let neci prace, nikoli proto, ze bude obsahovat matematiku, kterou neni mozno nikde jinde nalezt nebo kterou by nikdo jiny na svete nevymyslel).

[Dag]

Přesné!

[Marek Bernát]

Máš pravdu, ako obvykle. Dík, že si to napísal