Created by Pavel Klavík
Přednáška na STTI (https://www.mff.cuni.cz/cs/kam/poradane-akce/stti/stti-2021) o tom, jak v OrgPadu funguje automatické umisťování a přesouvání buněk.
spoluzakladatel a CTO
Bývalá učitelka, umělkyně, dnes školitelka OrgPadu a správce našich sociálních sítí.
Je to nástroj na zapisování a sdílení informací ve formě grafu.
Vidíte ho tady celou dobu.
Myšlenkové mapy jsou glorifikované bodíkové seznamy doplněné obrázky.
Jejich tvůrce Tony Buzan je markeťák a podvodník, který si zvyšoval svoji důvěryhodnost vydáváním se za profesora. Celé je ta založené na nesmyslech a pseudovědeckých poznatcích.
Baruš to nazvala svobodné strukturování:
Tomu říká řetěz nebo had.
Používala ho ve výuce dětí všech ročníků ZŠ, zejména ve 4. a 5., na ZŠ Hůrka v Kutné Hoře. Děti si nástroj sami osvojily a začaly ho používat na všechno.
Sepsala o tom pedagogické články na metodickém portálu RVP.
Baruš vypozorovala, že v pracech dětí přirozeně vznikají různé grafové struktury. Identifikovala je bez jakékoliv znalosti grafů. Tyto struktury lze vzájemně libovolně kombinovat.
Když jsou obdélníky buněk dostatečně blízko (nebo se překrývají), působí na sebe navzájem odpudivými silami od sebe. Když jsou dál než pevně zvolený limit, nepůsobí na sebe žádnými silami.
Používali jsme původně, ale mělo to tendenci moc přibližovat buňky k sobě. A nebylo možné mít dlouhé spoje napříč diagramem. Protože vytváříme asistenta a nekreslíme grafy z nuly, není tohle podstatné.
Paralelní spoje se nazvájem odpuzují. Funguje to velice dobře pro málo spojů, což je postačující.
Něco v rychlosti potřebuji uspořádat. Časem mohu propojit.
Nebo porovnávání dvou myšlenek.
Mají pozice a velikosti. Velikosti se mohou měnit podle toho, jak se buňky otevírají/zavírají nebo mění obsah.
Síly posouvají buňky.
Signalizuje, že tomu nerozumíme, musíme si to urovnat.
Pokud je spoj poblíž buňky, kterou nespojuje, působí na sebe odpudivými silami. Výpočet je mnohem pomalejší pro zahnuté spoje než pro rovné (zhruba 10x).
Síly ohýbají spoje jejich směrem.
Ohnuté spoje jsou kvadratické Beziérovy křivky. Dostatečně rovné spoje se narovnají na úsečky.
Snažíme se, aby rozbalený graf byl co nejbližší tomu zabalenému, jinak by se změny v rozbaleném příliš lišily od těch v zabaleném grafu. Proto buňky mají tendenci se vracet na svoje původní pozice.
Každé okno prohlížeče má svůj, podle toho, co je aktuálně otevřeno. V rozbaleném grafu se pracuje, ale není sdílený.
Čas měříme velice konzervativně, reálně je to mnohem více.
Matematik, učitel a filozof, působil na Matematicko-fyzikální fakultě UK. Přes 40 let se zabýval problémem, jak zapsat své myšlenky lépe pomocí počítače.
Síly aplikujeme Archimédovsky, tedy síla je změna pozice, ne změna rychlosti. Je to tak jednodušší a dává to pěkné výsledky.
Všechny působící síly složíme dohromady a aplikujeme jejich součet.
Mozek funguje ve formě sítě, kde jsou jednotlivé myšlenky propojené. OrgPad umožňuje si tuhle síť umístit před sebe a pracovat s ní.
Používání OrgPadu lidem předělá fungování hlavy. Lidé nám často říkají, že to trvá zhruba 10 hodin.
Zhruba 12x růst za poslední rok. Slabý růst v prosinci a přes léto.
Společný pro všechny, uložený na serveru. Všechny buňky jsou v něm zavřené.
Jak rozhodovat estetiku? Jak umožnit lidem mít dostatečnou svobodu?
Když ji třeba chceme převést do Wordu nebo vytisknout. Dnes kopírujeme buňky v náhodném pořadí.
Tím, že vidíme myšlenky před sebou, osvobodíme si hlavu a můžeme nad problematikou přemýšlet z jiného úhlu a objevovat nové souvislosti.
Dnes je člověk u počítače přehlcený blbostmi, které vůbec nechce řešit.
Každý může mít jinak otevřené jednotky, takže se nakreslení liší. Jak interpretovat změnu v jednom nakreslení do jiných nakreslení?
Dnes mám zhruba 1000 veřejných OrgPagí, které si může kdokoliv stáhnout. Nad nimi by šlo dělat různé analýzy nebo třeba trénovat neuronovou síť.
Pouze pokud je lomená čára blízko buňky, počítáme přesnou vzdálenost. Skoro vždycky to není pravda, takže výpočty pro zahnuté spoje jsou skoro vždycky rychlejší.
Třeba automatické umisťování/přesouvání buněk, o kterém je dnešní přednáška.
"Vytvořili jsme Macintosh pro lidi, kteří chtěli používat počítač, ne se učit používat počítač."
Vykreslujeme opakovaně mimo obrazovku. Pro zvolenou šířku získáme odpovídající výšku buňky. Prohledáváme prostor možných velikostí, abychom nalezli ideální rozměry esteticky.
Vidíte tady všude kolem. Například buňky na sobě mají pružiny, které je přitahují k jejich nové pozici. Díky tomu je možné animace plynule skládat a navazovat. Tenhle způsob animací vymysleli designéři v Applu.
OrgPad je asi jediný systém, který je neřeší simulací, ale řešením diferenciálních rovnic kmitání pružiny. Pružina má dva parametry: tuhost a tlumivost. Tyto parametry definují tři druhy pružin: podtlumené, přetlumené a kriticky tlumené. Pro ně jsou rozdílné vzorce, do kterých se dosadí počáteční pozice a rychlost.
Celý proces opakujeme ve zhruba 25 iteracích:
Výpočet běží v samostatném vláknu jako WebWorker. Výsledek poté pošleme hlavnímu vláknu a odanimujeme buňky a spoje na jejich novou pozici.
Ideální by byla rychlost tak 100 až 200 ms na přepočet. Tu umíme pro malé grafy, ale na větších pokulhává. Do nedávna byl největší bottleneck samotné vykreslování.
Během práce na OrgPadu vykrystalizovalo několik obtížných problémů, které jsme museli řešit.
V teorii se hlavně řeší asymptotická složitost, praktičnost algoritmů se moc neřeší. Z praktického hlediska je log(N) konstanta, zvlášť pokud je základ logaritmu dostatečný. Potřebujeme algoritmus, který
Number of vertices: 255, total pairs 485775 in all iterations.
Number of edges: 273, total vertex-edge pairs 522112.5 in all iterations.
Musí být zastoupeny všechny tři složky.
Vetšina algoritmů všechno nakreslí od začátku, neadaptují se podle měnícího grafu.
Vlastně mi není jasné, proč tohle trvá tak dlouho. Musím to prozkoumat :).
Většina klíčových problémů byla vyřešena někdy v 70.-80. letech. Tehdy byly položeny základy dnešních systémů.
V jádru každého systému se vynoří i složité algoritmické otázky.
To je problém, který teprve budeme řešit. V tuto chvíli předpokládáme, že jednotlivé změny různých lidí zároveň spolu komutují. To funguje překvapivě dobře, protože jednotlivé buňky mají různé náhodné 128 bitové identifikátory.
Řeší se to pomocí Operational transformations, které zpopularizoval nástroj Google Docs.
Jestliže algoritmy jsou základní stavební bloky programů, musíme je poskládat do celkové stavby. Ta musí dávat smysl, musí být dobře rozložená na části, atd. Její podoba je ovlivňována požadavky z reálného světa.
V OrgPadu je důležité, že si mohu věci rozmístit esteticky jak chci, podobně jako v malbě. Přílišné přesouvání by lidi nesmyslně omezovalo. OrgPad má jako nástroj asistovat, ne omezovat.
OrgPad je celý napsaný v programovacím jazyku Clojure(Script). To nám dává 10x větší efektivitu ve psaní kódu a vytváření aplikace.
 |  |
Informatika je věda, protože interaguje s reálným světem. Příchod počítačů obrátil na ruby všechny oblasti lidské činnosti.
Při vytváření něčeho nového je potřeba začít od reálných potřeb lidí. Ideálně řešíme svoje vlastní problémy, protože jim nejlépe rozumíme.
Ale neřeší celou řadu problémů klíčových pro OrgPad, nebo alespoň dostatečně.
Funguje pro 3-souvislí rovinný graf. Přišpendlíme vnější stěňu jako konvexní n-úhelník. Ostatní vrcholy umístíme do těžiště jejich sousedů. Takové pozice lze najít řešením soustavy s Laplaceovou maticí.
Chceme umístit každý vrchol skoro do těžiště svých sousedů. Takové nakreslení lze nalézt přes vlastní vektory odpovídající nejmenším vlastním číslům Laplaceovy matice.
Matice popisují lineární transformace. Jestliže x je ohodnocení vrcholů, získáme y = AGx a z = LGx:
Tedy zi popisuje, o kolik se hodnota vrcholu liší od průměru jeho sousedů.
Existují různá speciální druhy nakreslení, která nejsou moc užitečná.
