Ivánkův blog

Nejlepší programovací jazyk pro začátečníky

2011-09-23T07:22:00.000-07:00

Tento problém trápí spoustu začátečníků. Ti mohou na internetu najít různé, více čí méně správné odpovědi. V tomto článku bych rád shrnul celou tuto problematiku.

V tomto článku bych velmi nerad vnucoval ostatním svůj pohled na programování. Naopak budu rád, když se k němu v komentářích vyjádříte, já to zvážím a článek patřičně upravím :) Chtěl bych, aby tento článek reprezentoval názor odborné většiny a aby ti zkušenější programátoři sem mohli s důvěrou odkázat své mladší kolegy, které trápí stejná otázka.

Který programovací jazyk je nejlepší?

To je stejné jako se ptát, které auto je nejlepší?. Obě tyto věci, auta i programovací jazyky, jsou nástroje, které používáme za nějakým účelem. Každé auto se hodí na něco jiného. Pokud chceme převážet náklady, dáme přednost dodávce či kamionu před osobním autem. Ferrari je skvělé, když máme rádi rychlou jízdu, ovšem když pracujeme v zemědělství, spíš použijeme traktor. Rovněž záleží na osobních prioritách. Někdo upřednostňuje rychlost, jiný zase komfort nebo bezpečnost.

Který jazyk toho umí nejvíc?

Model počítače

Ve 30. letech 20. století britský matematik Alan Turing zkoumal, co všechno lze a co naopak nelze čistě mechanickou prací "vypočítat". Přišel s myšlenkou tzv. Turingova stroje. Je to matematický model počítače a lze na něm zkoumat, co všechno může nějaký stroj umět. Tímto Turing už před 70 lety přesně stanovil možnosti a hranice nejen současných, ale i budoucích počítačů.

Programovací jazyk

Programovací jazyk je prostředek, jak sdělit počítači, co po něm chceme. V našem jazyku by mělo jít vyjádřit všechno, co na daném počítači lze provést. To jest všechno, co dokáže udělat Turingův stroj. U jazyků se tak zkoumá "turingovská úplnost" nebo "turingovská ekvivalence". Všechny dnes používané programovacích jazyků jsou "turingovsky ekvivalentní", tedy "umí stejné věci", jako Turingův stroj.

Příklad z praxe	Příklad z praxe	Matematické zobecnění
sčítání jablek	sčítání hrušek	sčítání přirozených čísel
programování v Javě	programování v Pascalu	programování pro Turingův stroj

Z výše uvedeného jasně vyplývá, že všechny jazyky toho umí stejně. Každou věc, kterou napíšete v jednom jazyku, lze napsat i v jiném. Tj. v Haskellu můžete napsat 3D střílečku, v C můžete napsat interpret Javy, v Javě lze napsat překladač C, v JavaScriptu můžete napsat operační systém :) . Všechno tyto věci (hra, překladač, operační systém) jsou jen programy, které lze napsat v libovolném jazyce, jelikož si všechny jazyky odpovídají svými schopnostmi.

Rozdělení programovacích jazyků

Podle mě je správné rozdělovat jazyky podle tzv. "programovacího paradigmatu". To, co se doopravdy učíte, není jazyk, ale paradigma. Toto paradigma určuje, jakým způsobem musí programátor přemýšlet. V každém paradigmatu se musí přemýšlet trochu jinak. Pokud ovládáte jedno paradigma, ovládáte více-méně všechny jazyky z dané skupiny. Přechod z jednoho paradigmatu na jiné může být velmi náročný. Když jste zvyklí jen na jedno paradigma, kód z jiného paradigmatu se vám může zdát jako holý nesmysl.

Procedurální ( = imperativní = přikazovací)
- masivně používané v praxi
- píše se posloupnost instrukcí, které počítač provádí jednu za druhou
- jazyky: Jazyk symbolických adres, C, C++, Pascal, Basic, Fortran, Java, C#, PHP, ActionScript, JavaScript, ...
Neprocedurální ( = deklarativní = popisovací)
- používané ve velmi specifických případech. Buď proto, že se tam opravdu víc hodí, nebo proto, že je má dotyčný rád.
- píše se logika programu a vztahy mezi prvky programu
- Funkcionální
  - jazyky: Lisp, Scheme, Haskell
- Logické
  - jazyky: Prolog, Gödel, Fril
Ostatní
- turingovsky úplné jazyky, mající nějaké zvláštní paradigma
- často vytvořeny jen pro zábavu
- jazyky: výše zmíněný SED, Brainfuck, ...

Existují však i jazyky, umožňující zápis programu podle více paradigmat. Je to například Perl, Python nebo F#. Tyto jazyky mívají spoustu "vychytávek", které ušetří programátorovi čas a zkrátí kód. Podle mě jsou dost nepřehledné a nemám je moc rád, ale opět - je to individuální. Někdo má rád složité věci, někdo ne.

Nativní vs. interpretovaný program

Většina dnešních počítačů jsou elektronické, vybavené tzv. mikroprocesorem. Každý mikroprocesor má svoji sadu instrukcí, které umí provádět.

Nativní je program, který je převeden přímo do instrukcí pro daný mikroprocesor (strojový kód). Procesor čte instrukce jednu za druhou a provádí je. Je to velmi rychlé. Bohužel různé mikroprocesory mohou mít různé instrukční sady, a podle toho musíme udělat různé verze našeho programu.

Interpretovaný je program, který je převeden do instrukcí pro nějaký virtuální stroj. Tento stroj je zase program, který čte tyto "virtuální" instrukce a převádí je na instrukce pro daný mikroprocesor, na kterém běží (říká se tomu, že je "interpretuje"). Samotný převod je často důvodem pomalého běhu oproti nativním programům. Stačí nám však jen jedna verze programu pro konkrétní virtuální stroj, ale musíme mít víc verzí virtuálních strojů pro každý procesor nebo operační systém, na kterém to chceme spouštět. Virtuální stroje jsou třeba:

Java Virtual Machine (JVM) pro Javu
Adobe Virtual Machine (AVM/AVM2) pro ActionScript (součást Flash Playeru)
Common Language Runtime (CLR) pro jazyky z .NET (součást .NET frameworku)
virtuální stroj pro JavaScript je většinou součástí webového prohlížeče.

Rozdělení imperativních jazyků

Programem rozumějme posloupnost instrukcí pro fyzický či virtuální stroj. Hlavní vlastností jazyků je rychlost, která často klesá s rostoucí přenositelností programů. Nativní program je bleskově rychlý, ale jen na daném procesoru / architektuře. Interpretovaný program nám poběží na různých procesorech a systémech (Windows, Linux, tablety, mobily, ...), ale kvůli převodu instrukcí bývá často pomalejší. Graf níže ukazuje "polohu" jazyka vzhledem k jeho rychlosti / přenositelnosti.

Existují také různé nezvyklé případy, kdy se třeba JavaScript přeloží do strojového kódu, či naopak kód C++ se interpretuje na virtuálním stroji.

Jak tedy začít

Je důležité si uvědomit, že začínající programátor se neučí jazyk. Učí se programovat a jazyk je jen prostředek pro zápis programu. Umění programovat není vázáno na žádný programovací jazyk. Pokud umíte programovat třeba imperativním způsobem, tak se naučíte nový jazyk z dané skupiny během 2 dnů, maximálně týdne. Počet jazyků neříká vůbec nic o schopnostech programátora.

Doporučuje se začít programovat s imperativním jazykem. Nejdříve nízkoúrovňový, potom vysokoúrovňový jazyk.

Nízkoúrovňový jazyk

S nízkoúrovňovým jazykem lépe pochopíte, jak počítač pracuje s daty v paměti, jak je ukládá, načítá a zpracovává. Doporučuji začít s jazykem Pascal. Masochisté začínají s jazykem C, ten bych ale doporučil až ve chvili, kdy trochu ovládnete programování.

Vysokoúrovňový jazyk

Vysokoúrovňové jazyky nám nabídnou spoustu hotových "zkratek" a "vzorů", které jsme si museli v nízkoúrovňových jazycích sami programovat. Tím je například pohodlnější práce s dynamicky alokovanou pamětí a Objektově orientované programování. Doporučuji začít s jazyky Java nebo C#.

C++

C++ je zvláštní jazyk. Je nízkoúrovňový, ale tváří se velmi vysokoúrovňově. Z obou kategorií přebírá to nejlepší. Kompiluje se do strojového kódu (je nativní), a proto je velmi rychlý. Navíc obsahuje spoustu konstrukcí, "zkratek" a "vzorů", které jsou obvyklé ve vysokoúrovňových jazycích a usnadní programátorovi práci. Kvůli rozsáhlosti těchto konstrukcí a tím i složitosti celkové syntaxe, tento jazyk začátečníkům rozhodně nedoporučuji.

Algoritmy a datové struktury

Při praktickém programování programátoři hojně využívají algoritmů a datových struktur. Algoritmy a datové struktury však s programováním přímo nijak nesouvisí! Jejich vztah bych naznačil takto:

psání programu v prog. jazyce	psaní pravopisně správných vět
zápis algoritmu pomocí prog. jazyka	psaní příběhu s dějem pomocí pravopisně správných vět

Algoritmy a datové struktury nemusí být v prog. jazyce pro počítač. Algoritmy může provádět třeba člověk, datové struktury existují i mimo svět počítačů. Stejně jako příběh s dějem nemusí být zapsán pomocí pravopisně správných vět. Může být třeba převyprávěn či zfilmován. Je však jasné, že když chcete být dobrý spisovatel, znalost pravopisu nestačí!

Přeji vám hodně štěstí, nápadů a trpělivosti při vašich prvních krocích, ať se daří! :)

Kreslení grafů v JavaScriptu

2011-08-07T03:19:00.001-07:00

V tomto článku bych vám rád ukázal předělávku své flash aplikace do HTML5. Jedná se o kreslení hezkých grafů z Minulého článku.

HTML5 aplikace

ActionScript 3 jsem přepsal do JavaScriptu, pro vykreslování jsem použil HTML5 komponentu <canvas> a její metody. Navíc jsem přidal regulaci odpudivosti vrcholů a přitažlivosti pružin - hran. Grafy lze předávat jako parametry v URL. Aplikace je k dispozici na

g.ivank.net

Voroného diagram v JavaScriptu

2011-07-14T13:41:00.000-07:00

Už dlouhou dobu mě láká vyzkoušet si práci s JavaScriptem. Přece jen je to hlavní otevřený jazyk pro web, navíc v posledních letech vznikla řada opravdu rychlých interpretů pro JS.

Čím je JS zajímavý

Doposud jsem o JS věděl pouze to, že je hodně podobný ActionScriptu a že nemá třídy.

Zní to zvláštně, ale je to tak. JavaScript je objektově orientovaný, stejně jako ActionScript nebo C++, ale datové typy ani třídy v něm neexistují. Namísto tříd se používá Prototypové programování. Je trochu těžké zvyknout si na absenci tříd, avšak po chvíli už vám to nebude vadit, nebo vám se to nedej bože začne líbit :)

Přepis kódu z ActionScriptu do JS

Se způsobem programování v JS jsem se seznámil ve článku na wikipedii. Vypadalo to celkem jasně a jako cvičení jsem si řekl, že přepíši svoji knihovnu pro Voroného diagramy, kterou už mám napsanou v ActionScriptu a C++. Ze začátku jsem se trochu bál, že bude těžké přepsat AS do JS, ale nakonec to bylo až podezřele jednoduché, a co je ještě divnější, ono to i fungovalo! Během necelé hodiny bylo vše hotové.

Výsledek

Výsledek můžete vidět výše. Diagramy vykresluji do HTML elementu "canvas". Bohužel jsem neměl implementaci haldy pro prioritní frontu a místo ní jsem použil pole. Časová složitost je tak $O(n^2)$ místo $O(n * log(n))$, kterou má flešová a C++ verze. Pomalost se může projevit při vysokém počtu bodů.

Přepis běžných imperativních objektových jazyků do JS by se dal shrnout do těchto bodů:

Odstranit specifikace typů při definici proměnných
- int a = 5; var a:int = 5; => var a = 5;
Přepsat definice tříd na definice funkcí. Když se tyto funkce zavolají s "new", chovají se jako konstruktory
Všechny metody tříd napojit na prototyp konstruktorů

Řešení hlavonamů v Prologu

2011-06-02T12:26:00.000-07:00

Tato práce vznikla jako součást zápočtového programu na předmětu Neprocedurální programování, MFF UK. Jedná se o řešení konkrétního druhu hlavolamu v programovacím jazyce Prolog.

Posouvací puzzle na obecném grafu

Popis problému

Mějme neorientovaný graf na n vrcholech, každý jeho vrchol je označen číslem z $[0, n-1]$ a zároveň obsahuje číslo z $[0, n-1]$. Vrcholu obsahujícímu $0$ říkejme "prázdný" vrchol. Čísla se posouvají mezi vrcholy s použitím prázdného vrcholu, tj. obsahy vrcholů $U$ a $V$ můžeme prohodit, pokud je mezi nimi hrana a jeden z nich obsahuje $0$.

Puzzle je vyřešeno, když obsah každého vrcholu odpovídá jeho označení.
Ukázka: čirou náhodou jsem na internetu našel flash hru (výše), která přesně odpovídá popisovanému problému (autorem je Douglas Ensley, FlashAndMath.com). Do stejné kategorie hlavolamů patří např. Patnáctka.

Poznatky Wilsona (1974)

řešení může existovat pouze pro vrcholově 2-souvislé grafy (nemá smysl zkoumat např. stromy)
obecně neřešitelné pro graf theta₀ a kružnice
bipartitní graf (např. mřížka) - řešitelné pouze pro sudé permutace, kterých je polovina
v ostatních případech řešitelné vždy

Algoritmus řešení

Řešíme postupným zkoušením všech možností, ovšem pouze do stanovené hloubky. V každém kroku vybíráme další krok prioritně dle heuristiky.

Heuristika

Definujme domácí vzdálenost vrcholu $v$ jako délku nejkratší cesty od označení $v$ do obsahu $v$, tj, nejmenší počet tahů pro posun "domů". Definujme rozladěnost grafu jako součet domácích vzdáleností přes všechny vrcholy. Puzzle je vyřešené, jakmile rozladěnost klesne na 0. Pokud z vrcholu obsahujícího $0$ máme více možností tahu, vybíráme z nich prioritně podle vlivu na rozladěnost grafu. Nejdříve ty, které ji zmenší, pak ty, co ji nezmění, nakonec ty, co ji zvětší.

Poznámky k mé implementaci

Pro hledání nejkratších cest používám Floyd-Warshallův algoritmus.
Pro seřazení vrcholů dle priority používám Insertion sort.
Nedovoluji v řešení cykly délky 2 (Např. když hledáme řešení dlouhé do 10 kroků a řešením je [1,2,3,4], potom [1,2,1,2,3,4] nevrátím, ačkoli to je řešení a má do 10 kroků.

Zdrojový kód v Prologu

Stručná dokumentace k programu

Vstup

Vstupní graf může být definován kdekoli v souboru s programem použitím predikátu

graph(Název, g(V, E)).

Název je název grafu, pomoci kterého k němu budeme přistupovat V značí seznam vrcholů ve tvaru

[označení-obsah, označení-obsah, ...]

E značí seznam hran ve tvaru

[e(označení, označení), e(označení, označení), ...]

Ukázka

graph(ctverec,  g( [0-1, 1-2, 2-3, 3-0],  
                [e(0,1), e(1,2), e(2,3), e(3, 0)] ) ).

Což znamena takovýto graf

Spuštění výpočtu

Výpočet se spustí predikátem

solve(Název, Max-tahů).

Název je název grafu v predikátu "graph"
Max-tahů je horní hranice pro počet tahů ve výstupních řešeních.

Výstup

Výstupem programu jsou všechny posloupnosti tahů do stanovené délky řešící hlavolam. Jsou ve tvaru

[vrchol, vrchol, vrchol, ...]

vrchol je označení vrcholu, který si v daném kroku prohazuje obsah s nulovým vrcholem. Tahy jsou uspořádány zleva. Pokud vám dané řešení nevyhovuje, vygenerujte si další zmáčknutím ";". Pro náš výše uvedený graf je řešením toto

[2, 1, 0]

Stejně jako toto

[0, 1, 2, 3, 0, 1, 2, 3, 0]

Již vložené vsupy

Pro účely testování jsem do souboru přepsal některé grafy z výše uvedené URL a je možné se na ně dotazovat. Jsou to: graph1, graph3, graph5, graph7, graph9, graph11, graph17, graph30. Vyzkoušejte např. solve(graph1, 8).

Nejkratší řešení hlavolamů výše

Zadal jsem některé hlavolamy ze výše uvedené hry do programu a toto je výstup. Pokud chcete, můžete zadat zbytek a vypočítat si další hlavolamy, Patnáctky apod.

Číslo	Řešení
1	[2,4,3,2,1,0], [2,3,4,2,1,0], [1,2,4,3,2,0], [1,2,3,4,2,0]
3	[4,3,0,2,1,0], [4,3,0,1,2,0], [3,4,0,2,1,0], [3,4,0,1,2,0], [2,1,0,4,3,0], [2,1,0,3,4,0], [1,2,0,4,3,0], [1,2,0,3,4,0]
5	[3,2,1,0,3,4,1,0], [1,4,3,0,1,2,3,0]
7	[5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0],
9	[1,5,2,3,4,5,6,0]
11	[5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0]
17	[1,2,5,4,3,2,1,0,5,4,3,2,1,0]
30	[7,6,3,2,7,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,3,2,7,0]

Hra ve stylu Untangle

2011-05-30T12:41:00.000-07:00

Dnes se pokusíme využít znalosti z předchozích článků a vytvořit hru. Jedná se o typ hry, kde posouváme vrcholy rovinného grafu ve snaze nalézt jeho rovinné nakreslení. Zní to složitě, ale čtěte dál a hned bude vše jasné.

Postup práce

Stanovme si, co vše potřebujeme a jak to budeme dělat.

Kde vzít grafy

Ve hře se pracuje s rovinnými grafy, tedy grafy, které lze nakreslit tak, aniž by se nějaké hrany protínaly. Pokud uděláme náhodný graf, nemusí být rovinný (třeba $K_{3,3}$ není rovinný).

Vstupní grafy je možné zadat ručně, ale musíme nejdříve nějaké hezké vymyslet. Další možností je nechat si je náhodně vygenerovat počítačem.

Rovinným grafem by mohla být např. triangulace (mezi body v rovině dáme hrany tak, že každá stěna je trojúhelník). V minulém článku o Voroného diagramu jsme při výpočtu diagramu dostali vedlejší produkt, Delaunayho triangulaci. Tu můžeme použít, případně z ní odstranit nějaké hrany, aby graf nebyl tak komplikovaný.

V grafu také potřebujeme kontrolovat protínání hran a podle toho je správně vykreslovat. Kontrolu protínání lze použít z předchozího článku.

Postup tedy je:

vytvořit v rovině vrcholy
vypočítat na nich triangulaci - správný seznam hran
vyhodit některé hrany pro zjednodušení grafu
zamíchat vrcholy (my je dáme do kružnice)
nechat uživatele hýbat vrcholy, podle toho překreslovat graf

Kód

/*
   Vrcholy jsou třídy Point, graficky je reprezentuje
   třída Dot. Dot má pointer na svůj vrchol (Dot.p) 
*/

import net.ivank.voronoi.*;
import net.ivank.Geometry;

var i:int;
const n:int = 10;   // počet vrcholů
// rozměry scény
const w:int = stage.stageWidth;
const h:int = stage.stageHeight;
var dDot:Dot;       // vrchol, kterým se táhne
var edges:Vector.< VEdge >; 
var v:Voronoi = new Voronoi();
var vertices:Vector.< Point> = new Vector.< Point >();

Vytvoření grafu

// náhodné vrcholy
for(i = 0; i< n; i++)
   vertices.push(new Point(150 + Math.random()*300, 120 + Math.random()*240 ));

// generujeme pro ně hrany (voronoi a delaunay)
edges = v.GetEdges(vertices, stage.stageWidth, stage.stageHeight);

// umístíme vrcholy do kružnice
for(i=0; i< n; i++)
{
   vertices[i].x = w/2 + 170 * Math.cos(Math.PI*2*i/n);
   vertices[i].y = h/2 + 170 * Math.sin(Math.PI*2*i/n);
}

// přidáme na scénu DOTy
for(i = 0; i< n; i++)
{   
   var d:Dot = new Dot();
   d.addEventListener(MouseEvent.MOUSE_DOWN, onDown );
   d.addEventListener(MouseEvent.MOUSE_UP,   onUp   );
   d.p = vertices[i];
   d.x = vertices[i].x; d.y = vertices[i].y;
   d.buttonMode = true;
   addChild(d);
}

Už jen zbývá napsat vykreslování čar a také kontrolu, zda se nějaké dvě protínají (-> kontrola, zda se žádné neprotínají). To jde napsat různými způsoby a konkrétní kód nechám na vás.

Vylepšení hry

Pokud do hry přidáme pěknou grafiku, případně nějaké další extra funkce, bude hra mnohem pestřejší a pro určité procento populace i zábavná :) V tomto duchu jsem vytvořil hru FlyTangle. Pokud by vás bavila a máte Google Chrome, můžete si ji nainstalovat jako Chrome aplikaci.

Jednoduché geometrické výpočty

2011-04-20T12:08:00.000-07:00

V tomto článku si ukážeme nějaké základní geometrické výpočty v rovině. Kdybyste je někdy potřebovali, tak si je jen okopírujete, anebo vás to může motivovat k psaní vlastních, pokročilejších funkcí :)

Začneme napsáním základních funkcí, které budeme využívat při psaní složitějších. Můžeme je dávat jako statické metody do třídy Geometry.

Vzdálenost dvou bodů

Vzdálenost dvou bodů (v prostoru s eukleidovskou metrikou) spočítáme Pythagorovou větou ($c = \sqrt{a\times a + b \times b}$).

Kód

 
public static function Distance(a:*, b:*):Number
{
   return(Math.sqrt( (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y) ));
}

Zda bod leží v obdélníku

Obdélník mějme definovaný dvěma body: levým horním a pravým dolním rohem ("b" a "c"). Ptáme se, jestli bod "a" leží uvnitř obdélníku. a.x musí být mezi b.x a c.x, a.y musí být mezi b.y a c.y.

Kód

public static function isInRect(a:*, b:*, c:*):Boolean
{
   if(a.x >= Math.min(b.x, c.x) && a.x <= Math.max(b.x, c.x)
   && a.y >= Math.min(b.y, c.y) && a.y <= Math.max(b.y, c.y)) 
   return true;
   return false;
}

Průsečík dvou úseček / přímek

Mějme úsečky "a", "b" definované dvěma body (začátky "a1", "b1" a konce "a2", "b2"). Chceme zjistit bod, kde se protínají. Nejdřív najdeme průsečík přímek a, b. Aby to byl průsečík úseček, musí ležet mezi začátky a konci obou úseček.

Při výpočtu průsečíku si přímku převedeme do směrnicového tvaru $y = f\times x + g$, kde "f" je směrnice a "g" je svislý posun.

Kód

public static function GetLineIntersection(a1:*, a2:*, b1:*, b2:*):Point
{
   var f1:Number = -(a2.y - a1.y) / (a1.x - a2.x);
   var f2:Number = -(b2.y - b1.y) / (b1.x - b2.x);
   var g1:Number = a1.y - f1 * a1.x;
   var g2:Number = b1.y - f2 * b1.x;

   // rovnoběžky -> žádný průsečík
   if(f1 == f2) return null;
   
   var inter:Point;
   if       (a1.x == a2.x) inter = new Point(a1.x, f2*a1.x + g2);
   else if  (b1.x == b2.x) inter = new Point(b1.x, f1*b1.x + g1);
   else     
   {
      inter = new Point((g2-g1)/(f1 -f2),0);
      inter.y =  f1 * inter.x + g1;
   }

   if(isInRect(inter, a1, a2) && isInRect(inter, b1, b2)) return inter;
   return null;
}

Střed kružnice opsané

Mějme tři body v rovině (a, b, c). Hledáme kružnici (její střed a poloměr), která prochází těmito třemi body. Tj. hledáme bod (střed kružnice), který má stejnou vzdálenost od a, b, c. Uděláme si osu úsečky a,b (to jsou body se stejnou vzdáleností k "a" a "b"), osu úsečky b,c (body stejně vzdáleny od b, c) a průsečík těchto os je stejně vzdálen od a, b, c.

Kód

public static function GetCircumcenter(a:*, b:*, c:*):Point
{
   // m1 - bod uprostřed (a,b), osa ním prochází
   var f1 = (b.x - a.x) / (a.y - b.y);
   var m1 = new Point((a.x + b.x)/2, (a.y + b.y)/2);
   var g1 = m1.y - f1*m1.x;

   var f2 = (c.x - b.x) / (b.y - c.y);
   var m2 = new Point((b.x + c.x)/2, (b.y + c.y)/2);
   var g2 = m2.y - f2*m2.x;

   // ošetření degenerovaných případů
   // - tři body na přímce
   if     (f1 == f2)   return null;
   // - a, b ve stejné výšce -> směrnice osy |ab| = nekonečno
   else if(a.y == b.y) return new Point(m1.x, f2*m1.x + g2);
   else if(b.y == c.y) return new Point(m2.x, f1*m2.x + g1);

   var x:Number = (g2-g1) / (f1 - f2);
   return new Point(x, f1*x + g1);
}

Voroného diagram v AS3

2011-03-13T15:50:00.000-07:00

Jak jste možná vytušili z předchozího článku, nyní si implementujeme Fortunův algoritmus pro hledání Voroného diagramu ve flashi.

Knihovna Voronoi

Celý kód jsem zabalil do jedné knihovny, aby byla snadno přístupná. Knihovnu si stáhnete kliknutím ZDE.

Příklad použití

 
import net.ivank.voronoi.*;       // import knihoven
import flash.geom.Point;

var i:int;
var edges:Vector.< VEdge >;       // vektor, kam se uloží hrany
var v:Voronoi = new Voronoi();    // tato instance vše spočítá
// vektor bodů, pro které počítáme diagram
var vertices:Vector.< Point> = new Vector.< Point >();

// přidáme náhodné body (pouze kladné pozice)
for(i = 0; i< vnum; i++)
{
   var p = new Point(Math.random() * 1000 , Math.random() * 800)
   vertices.push(p);
}
// necháme si spočítat hrany, uvedeme rozměr diagramu
edges = v.GetEdges(vertices, 1000, 800);

// takto si nakreslíme Delaunayho triangulaci
graphics.lineStyle(3, 0x888888);
for(i = 0; i< edges.length; i++)
{
   graphics.moveTo(edges[i].left .x, edges[i].left .y);
   graphics.lineTo(edges[i].right.x, edges[i].right.y);
}

// takto si nakreslíme Voroného diagram
graphics.lineStyle(5, 0x000000);
for(i = 0; i< edges.length; i++)
{
   graphics.moveTo(edges[i].start.x, edges[i].start.y);
   graphics.lineTo(edges[i].end  .x, edges[i].end  .y);
}

Test výkonu

Pro reprezentaci fronty událostí lze použít pole nebo haldu. Podívjeme se na rychlost jednotlivých možnosti (diagram pro 200 bodů, přepočítává se při pohybu myši).

Pole - přidání události: na konec pole; mazání události: vymazání + posun zbytku o políčko dozadu; výběr maxima: sort + odebrání posledního.

Halda - přidání událost, výběr maxima: dle definice haldy.

Fortunův algoritmus a jeho implementace

2011-03-08T12:51:00.000-08:00

Tato práce vznikla jako zápočtový projekt na předmětu Algoritmy a datové struktury 2, MFF UK. Pojí se k ní implementace v C++ (níže) a v ActionScript 3.0 (v příštím článku).

Stručně o Voroného diagramu

Mějme N bodů v rovině, kterým budeme říkat místa. Přiřaďme místu $a$ množinu bodů $V(a)$ z dané roviny takovou, že vzdálenost její bodů od $a$ je menší nebo rovná vzdálenosti jakéhokoli jiného místa. Je zřejmé, že množina bodů $V(a)$ bude vytvářet souvislou plochu kolem místa $a$. Tj. ke každému místu $a$ patří oblast, ze které je to k $a$ nejblíž.

Průnikem dvou množin $V(a)$ a $V(b)$ jsou body, mající stejnou vzdálenost od $a$ jako od $b$, přitom žádné místo neleží v kratší vzdálenosti od nich. Mohou ležet na přímce, polopřímce nebo úsečce. Voroného diagramem nazveme právě množinu těchto bodů.

Podobně lze Voroného diagram definovat pro vícerozměrné prostory a různé metriky.

VD jako graf

Na voroného diagram se lze dívat jako na neorientovaný graf. Jeho hrany jsou výše zmíněné úsečky (průniky V(a) a V(b)) a vrcholy jsou průniky těchto úseček, tedy body, mající stejnou vzdálenost ke třem nebo více nejbližším místům. Poznamenejme, že některé hrany mohou vést do nekonečna.

Delaunayho triangulace

Na množině bodů $P$ ležících v rovině lze vytvořit velké množství triangulací. Dleaunayho triangulací $DT(P)$ nazveme tu triangulaci, kde kružnice opsaná libovolnému trojúhelníku neobsahuje uvnitř žádné body z $P$. Tato triangulace má "nejrovnostrannější" trojúhelníky - maximalizuje se jejich minimální úhel. Delaunayho triangulace je duálním grafem k Voroného diagramu pro danou množinu bodů v rovině.

Algoritmy pro výpočet Voroného diagramu

Rozděl a panuj - algoritmus rozdělí body na pravou a levou část, rekurzivně spočítá Voroného diagramy těchto dvou částí a nakonec dvě části spojí, vytvořením chybějící části diagramu mezi nimi.
Inkrementální algoritmus - spočítá Voroného diagram pro dvě místa. Při přidávání dalšího místa vypočítá nový diagram pro danou část.

Nevýhody těchto algoritmů - náročná implementace, netriviální spojování diagramů, velké numerické chyby.

Fortunův algoritmus

Tento algoritmus je založen na "zamétání" roviny. Po rovině se pohybuje přímka $L$ (např. zezdola nahoru), která zpracuje každý bod, přes který projde. Pokusme se určit, které body $x$ ležící pod ní patří do Voroného diagramu.

Pokud je bod $x$ stejně daleko od dvou míst $a$ a $b$ (všechny 3 leží pod přímkou), ještě nemusí být v diagramu, jelikož těsně nad přímkou může ležet místo $c$, které je k němu blíž než $a$ či $b$. Voroného diagram můžeme určit pouze pro body, které mají blíž k nějakému místu $a$ než k přímce $L$. Tyto body leží pod parabolou ($a$ je její ohnisko a $L$ řídící přímkou, z definice paraboly).

Hranice, pod kterou už můžeme diagram rozhodnout, je tvořená oblouky parabol (angl. "beachline"). Průsečíky parabol mají stejně daleko ke dvěma sousedním místům (ohniskům sousedních parabol) jako k přímce, a tedy při pohybu přímky $L$ "kreslí" diagram. Hranice je tedy posloupnost oblouků $p$ a jejich průsečíků $x$, kterým říkejme hrany, jelikož při pohledu na VD jako na graf $x$ kreslí jeho hranu.

Hraniční posloupnost $p_0, x_0, p_1, x_1, .... x_{n-1}, p_n$.

Posloupnost se však během kreslení může změnit, a to dvěma způsoby:

Místní událost - vstoupí do ní nové místo - nová parabola. Rozpůlí parabolu pod ní na dva oblouky a ze středu začnou vycházet do stran dvě nové hrany. Tedy parabolu $p_i$ nahradí posloupnost $p_i, x_i, p_{i+1}, x_{i+1}, p_{i+2}$, kde $p_i$ a $p_{i+2}$ mají ohnisko původní paraboly a $p_{i+1}$ má ohnisko v nově přidaném místě.
Kružnicová událost - zanikne parabola - sousední paraboly ji zatlačí a vznikne zde nová hrana.. Tedy posloupnost $x_{i-1}, p_i, x_i$ se nahradí novou hranou $x_i$. Místo, kde parabola $p_i$ zanikne, má stejně daleko k ohnisku pi jako k ohniskům obou sousedních oblouků, je tedy středem nimi definované kružnice (proto "kružnicová" událost).

Události budeme uchovávat ve frontě, kde budou seřazeny podle y. Jelikož vidíme, že se hraniční posloupnost mění pouze v několika místech, můžeme s přímkou L hýbat diskrétně, z jedné události na druhou.

Kód algoritmu

Rozbalit kód - Skrýt kód

   pro každé místo 
   {
      vytvoříme místní událost e, 
      e.bod = dané místo, vložíme e do fronty
   }
   dokud fronta není prázdná
   {
      e = první událost z fronty, vyjmeme ji z fronty
      když e je Místní : PřidejParabolu( e.bod )
      jinak : OdstraňParabolu( e.parabola );
      dokresli hrany x_i
   }
   funkce PřidejParabolu ( bod u )
   {
      par = oblouk pod bodem u;
      když par má event, kde zaniká, tak ho odstraň z fronty
      nové oblouky a, b, c;
      b.site = u;
      a.site = c.site = par.site;
      xl, xr  = hrany z bodu na “par” ležícím pod u (levá, pravá)
      xl kolmá na (a.site, b.site);
      xr kolmá na (b.site, c.site);
      nahraď par posloupností a, xl, b, xr, c
      ZkontrolujKružnici(a);
      ZkontrolujKružnici(c);
   }
   funkce OdstraňParabolu ( Parabola p )
   {
      l = oblouk vlevo od p;
      r = oblouk vpravo od p;
      když l nebo r mají eventy, kde zanikají, tak je odstraň z fronty
      s = střed kružnice definované l.site, p.site, r.site
      x = nová hrana se středem v s, kolmá na (l.site, r.site)
      ukonči postranní hrany xl, xr bodem s
      nahraď posloupnost xl, p, xr hranou x
      ZkontrolujKružnici(l);
      ZkontrolujKružnici(r);
   }
   funkce ZkontrolujKružnici(Parabola p)
   {
      l = oblouk vlevo od p;
      r = oblouk vpravo od p;
      xl, xr = hrany kolem p
      když l chybí  OR  r chybí  OR  l.site=r.site  VRAŤ SE
      s = střed, kam konvergují xl a xr
      když s chybí (nekonvergují) VRAŤ SE
      r = vzdálenost s a p.site (průměr kružnice procházející ohnisky)
      když s.y + r leží pod zametací přímkou  VRAŤ SE
      e = nová kružnicová událost
      e.parabola = p;
      e.y = s.y + r;
      přidej novou událost e do fronty 
   }

Spousta autorů mylně uvádí, že při kontrole kružnicové události stačí najít kružnici a zjistit, zda její vrchol leží nad zametací přímkou. To však nestačí, jelikož dvě okolní hrany mohou jít směrem od středu kružnice a nikdy se nesetkají.¨

Implementace

Fronta události

Jako frontu událostí je zvykem použít prioritní frontu, ve které jsou události uspořádány podle souřadnice "y". Měla by umožňovat mazání prvků.

Hraniční posloupnost

Hraniční posloupnost lze reprezentovat jako obousměrně spojový seznam. Vkládání a mazání je jednoduché, ovšem vyhledání potřebné položky trvá lineární čas.

Steven Fortune přišel s výbornou myšlenkou reprezentace hraniční posloupnosti jako binárního stromu.

Každý list představuje jeden oblouk. Vnitřní uzly představují hrany.
pokud je oblouk jeden, stromem je pouze jeden list
Při přidání paraboly do listu se daný list stane vnitřním uzlem, jedna půlka bude levým synem, vpravo bude vnitřní uzel, kde vlevo bude nový oblouk a vpravo druhá půlka.
Mazání listu je rovněž jednoduché. Otec představuje levou nebo pravou hranu, určitý "vyšší předek" představuje další hranu. Pokud jsme levým synem, nahradíme otce pravým synem a obráceně. "Vyššímu předkovi" přiřadíme novou hranu.

Složitost

Věta: Pro $n \geq 3$ míst v rovině obsahuje Voroného diagram max. $2n - 5$ vrcholů a $3n - 6$ hran.

Důkaz:

Pro body ležící na přímce to zřejmě platí.
Předpokládejme, že body neleží na přímce.

Označme si:

$V$: počet vrcholů voroného diagramu
$E$: počet hran diagramu
$N$: počet stěn voroného diagramu = počet míst

Z Eulerova vzorce víme, že pro každý souvislý rovinný graf platí, že:
$V - E + N = 2$

Jelikož Voroného diagram obsahuje nekončící hrany, vytvořme vrchol "nekonečno" a spojme s ním tyto hrany. Nyní máme rovinný graf.
$(V + 1) - E + N = 2$

U Voroného grafu navíc víme, že každý jeho vrchol (včetně "nekonečna") má stupeň aspoň 3. Hrana je mezi dvěma vrcholy, a tedy
$3 * (V + 1) \leq 2 * E$
Jednoduchou algebraickou úpravou dostaneme původní tvrzení.

Primitivní operace, jako vyhledání prvku ve stromu nebo ve frontě, vymazání z fronty, trvají logaritmický čas $O(log(n))$. Při každé události uděláme konstatntí počet těchto primitivních operací.

Počet místních událostí je $N$, kružnicových je až $2N - 5$. Při každé z nich provedeme $k$ primitivních operací. Celková složitost je tedy $O(n*log(n))$.

Implementace v C++

ZDE je moje implementace napsaná v C++ a komentovaná v angličtině. Součástí je i EXE soubor, který spustí animaci bodů a kreslení diagramů (v OpenGL). Rychlost je ohromující - program dokáže spočítat diagram pro 500 bodů 50 krát za vteřinu, výpočet je asi 10 krát rychlejší než stejná implementace v ActionScript 3.

Kreslení hezkých grafů 3D

2010-11-26T08:33:00.000-08:00

Dnes jsem se rozhodl navázat na svůj Předchozí článek o kreslení hezkých grafů, a to tak, že jsem do kódu pouze přidal třetí souřadnici "z" (pro polohu, vektory síly a vše, kde předtím byl jen "x" a "y"). Pro vykreslování jsem použil knihovny Away3DLite.

Nakreslení grafu podle parametrů

U této aplikace jsem navrhl možnost zadání grafu, který se má vykreslit. Tvar vstupu je

početVrcholů:hrana,hrana,hrana,hrana

kde "hrana" je ve tvaru

odVrhcolu-doVrcholu

Příklady

Název	Kód (vložte nahoru)
Tyčka	2:1-2
Trojúhelník	3:1-2,2-3,3-1
Kružnice $C_7$	7:1-2,2-3,3-4,4-5,5-6,6-7,7-1
Hvězda	4:1-2,1-3,1-4
Čtyřstěn	4:1-2,2-3,3-1,1-4,2-4,3-4
Krychle	8:1-2,2-3,3-4,4-1,5-6,6-7,7-8,8-5,1-5,2-6,3-7,4-8
Osmistěn	6:1-2,2-3,3-4,4-1,1-5,2-5,3-5,4-5,1-6,2-6,3-6,4-6
Dvacetistěn	12:1-2,2-3,3-4,4-5,5-1,6-7,7-8,8-9,9-10,10-6,1-11,2-11,3-11,4-11,5-11,6-12,7-12,8-12,9-12,10-12,1-6,6-2,2-7,7-3,3-8,8-4,4-9,9-5,5-10,10-1
Dvanáctistěn	20:1-2,2-3,3-4,4-5,5-1,6-7,7-8,8-9,9-10,10-6,1-11,2-12,3-13,4-14,5-15,6-16,7-17,8-18,9-19,10-20,11-16,16-12,12-17,17-13,13-18,18-14,14-19,19-15,15-20,20-11
Diabolo	11:1-2,2-3,3-4,4-5,5-1,6-7,7-8,8-9,9-10,10-6,11-1,11-2,11-3,11-4,11-5,11-6,11-7,11-8,11-9,11-10
Fanova rovina	7:1-2,2-3,3-4,4-5,5-6,6-1,1-7,2-7,3-7,4-7,5-7,6-7,2-4,4-6,6-2
4D krychle	16:1-2,2-3,3-4,4-1,5-6,6-7,7-8,8-5,1-5,2-6,3-7,4-8,9-10,10-11,11-12,12-9,13-14,14-15,15-16,16-13,9-13,10-14,11-15,12-16,1-9,2-10,3-11,4-12,5-13,6-14,7-15,8-16
Trubka (???)	18:1-2,2-3,3-4,4-5,5-6,6-1,1-7,7-2,2-8,8-3,3-9,9-4,4-10,10-5,5-11,11-6,6-12,12-1,7-8,8-9,9-10,10-11,11-12,12-7,13-14,14-15,15-16,16-17,17-18,18-13,1-13,13-2,2-14,14-3,3-15,15-4,4-16,16-5,5-17,17-6,6-18,18-1
$K_{10}$ neboli Gulička (díky Míšo :))	10:1-2,1-3,1-4,1-5,1-6,1-7,1-8,1-9,1-10,2-3,2-4,2-5,2-6,2-7,2-8,2-9,2-10,3-4,3-5,3-6,3-7,3-8,3-9,3-10,4-5,4-6,4-7,4-8,4-9,4-10,5-6,5-7,5-8,5-9,5-10,6-7,6-8,6-9,6-10,7-8,7-9,7-10,8-9,8-10,9-10

Pokud vytvoříte nějaké další zajímavé grafy, napište je dolů do komentářů (pojmenování grafu a kód) a já je sem dopíšu.

Aho-Corasick, kód v AS3

2010-11-24T09:33:00.000-08:00

Ve dnešním díle si ukážeme způsob implementace algoritmu Aho-Corasickové. Používá se pro vyhledávání slov v textu a je velmi rychlý oproti ostatním běžným metodám. Podobně se dá implementovat jazycích C, C++, C#, Java a dalších.

Algoritmus Aho-Corasick

Tento algoritmus lze rozdělit do 2 kroků:

stavba konečného automatu
- výstavba trie z hledaných slov
- konstrukce zpětné hrany pro každý uzel
průchod automatem - čtení textu po znacích, ukládání výsledků

V příkladu výše máme ve trii slova "depo", "sedět", "posed", "seno", "se". Prohledávaný text je v políčku dole. Pokud v nějakém kroku najdu hledaná slova (v jednom místě může končit více slov), rozsvítí se jejich koncová písmena.

Implementace

Trie

Stavbu trie jsme si již ukázali v předchozím článku o Trii. Pro náš účel si do ní přidáme 5 dalších položek:

   // ukazatel na předka a zpětná hrana
   public var parent:TNode;
   public var fall:TNode;
   // nějaké údaje pro snazší kreslení
   public var x:Number;
   public var y:Number;
   public var width:Number;

Konstrukce zpětných hran

Pro konstrukci zpětných hran (pointer "fall") musíme prohledávat trii do šířky a potřebujeme frontu. Já jsem použil frontu z balíčku AS3DS od PolygonLabs (proměnná "q").

function MakeFallFunctions():void
{
   trie.fall = trie; // zpětná hrana z kořene je kořen
   q.enqueue(trie);  // přidám do fronty kořen
   while (q.size != 0) // prohledávám do šířky
   {
      var n:TNode = q.dequeue();
      var no:TNode;
      var i:int;
      for (i = 0; i < 4; i++) // naházím potomky do fronty
      {
         no = n.cn[i];
         if (no == null) continue;
         while (no.next != null) { q.enqueue(no); no = no.next; }
         q.enqueue(no);
      }
      if (n == trie) continue; // kořen už má zpětnou hranu
      // od předka jdu po zpětných hranách než najdu pokračování
      // nebo dojdu do kořene
      var fall:TNode = n.parent.fall;
      while (fall.GetChild(n.c) == null && fall != trie) fall = fall.fall;
      // když najdu pokračování, do nastavím do fall
      n.fall = fall.GetChild(n.c);
      if (n.fall == null) n.fall = trie; // není pokračování
      if (n.fall == n) n.fall = trie;
   }
}

Prohledávání - průchod automatem

function Prohledávej(e:MouseEvent):void
{
   var text:String = "V tomhle textu budu prohledávat.";
   var cState = trie; // aktuální stav
   var n:TNode;       // pomocné uzly
   var no:TNode;
   var b:String;      // písmeno, které čteme
   for(var i:int=0; i < text.length; i++)
   {
      n = cState;
      b = text.charAt(i);
      
      // jedu po zp. hranách, než najdu pokračování
        while (n.GetChild(b) == null && n != trie) n = n.fall;
      
      // když jsem se dostal do kořene
        if (n == trie)
        {
            n = n.GetChild(b);
            if (n == null) n = trie;
        }
        else n = n.GetChild(b); // našel jsem pokračování
      
      no = n; // jedu po fallech do kořene, tím projdu všechny přípony
      while(no!= trie)
      {
         if(no.isEnd){/* právě jsem našel slovo, co končí v "no"*/}
         no=no.fall;
      }
      cState = n;
   }
}

Lineární složitost algoritmu

Při vysvětlování nebudu uvažovat složitost hlášení nalezených slov. Jen dodám, že jde vyřešit v konstantním čase.

Nechť prohledávaný text má $n$ znaků. Při hledání děláme buď pohyby "dolů" - na další písmeno, nebo "nahoru" - po zpětné hraně. S každým písmenem se pohneme max. jednou dolů. Počet pohybů "dolů" je max. $n$.

Abychom mohli udělat několik pohybů nahoru (po zpětných hranách), musíme nejdříve udělat aspoň stejně tolik pohybů dolů (abychom byli v patřičné "hloubce"). Počet pohybů nahoru tedy nikdy nepřekročí počet pohybů dolů. Celkový počet pohybů (nahoru i dolů) během celého výpočtu nikdy nepřekročí $2n$, algoritmus tedy má lineární složitost $O(n)$.

Závěr

Aho-Corasickovou jsem původně programoval v C#, teď jsem ten kód jen přepsal do AS3. Tento algoritmus se v AS3 nikdy neprogramuje, jelikož když hledáme málo prvků v krátkém textu, vystačíme si se String.indexOf("..."). Pokud hledáme hodně prvků ve velkém textu, nepoužijeme Flash, ale efektivnější nástroj, např. unixový program grep. Tento článek má spíše sloužit jako ilustrace a nástřel k implementaci Aho-Corasickové v jiných jazycích.

Kreslení hezkých grafů v AS3

2010-11-21T23:20:00.000-08:00

V tomto článku se podíváme na způsoby kreslení hezkých grafů do roviny. Použijeme fyzikální, tzv. "pružinový" algoritmus, v průběhu kterého si budeme graf vykreslovat.

Grafy a jejich nakreslení

Grafy

Klasický graf je definován množinou vrcholů (např. ${a, b, c, d}$) a množinou hran, což jsou dvojice vrcholů ($\{ \{ a,b\}, \{b,c\}, \{c,d\}, \{d,a\}\}$). Většina lidí by tento graf nakreslila jako "čtvereček", ovšem způsobů, jak ho nakreslit, je mnoho, některé se nám esteticky líbí více, některé méně.

Co je to hezké nakreslení

Zkusme hezké nakreslení nějak definovat. Určitě budeme chtít, aby vrcholy nebyly příliš blízko u sebe, už vůbec ne jeden na druhém. Budeme asi také chtít, aby hrany byly rozumně dlouhé a nekřížily se příliš často. Můžeme si vymyslet i spoustu dalších kritérií.

Pružinový model

V tomto modelu přiřadíme každému vrcholu "antigravitaci", odpudivou sílu. Díky tomu vrcholy nebudou příliš blízko u sebe. Mezi dvojice vrcholů, kde vede hrana, přidáme přitažlivou sílu (pružinu). Postupem času se působení sil ustálí a graf bude "hezký".

Třída Vertex

package
{
   import flash.display.Sprite;
   import flash.geom.Point;
 
   public class Vertex extends Sprite
   {
      // rychlost vrcholu
      public var velocity:Point = new Point(); 
      // síla vůči aktuálnímu modelu
      public var net_force:Point = new Point();
      public var isDragged:Boolean = false;  // zda ho táhnu myší

      public function Vertex():void
      {
         // doprostřed nakreslím kroužek
         with(graphics)
         {
            beginFill(0xFF005E);
            drawEllipse(-12, -12, 24, 24);
            endFill();
         }
      }
   }
}

Vytvoření grafu

   // množina vrcholů
   vertices = new Vector.< Vertex >(n, true);
   // hrany v grafu incidence
   edges = new Vector. < Vector.< Boolean >>(n, true);
   for(i=0; i < n; i++) edges[i] = new Vector.< Boolean >(n, true);
   while(e > 0) // přidám hrany
   {
      var a:int = Math.floor(Math.random()*n);
      var b:int = Math.floor(Math.random()*n);
      if(a==b || edges[a][b])continue;
      edges[a][b] = true;
      edges[b][a] = true;
      e--;
   }
   // přidám vrcholy
   for(i=0; i < n; i++)
   {
      var v:Vertex = new Vertex();
      v.x = 200+Math.random()*300;
      v.y = 100+Math.random()*200;
      vertices[i] = v;
      addChild(v);
      v.addEventListener(MouseEvent.MOUSE_DOWN, drag);
      v.addEventListener(MouseEvent.MOUSE_UP, sdrag);
   }

Vykreslování modelu

Už máme vrcholy na náhodných pozicích. Teď provádíme iterace, v každé z nich přepočítáme polohu každého vrcholů podle ostatních vrcholů a podle jeho hran. Iterace provádíme, než "rozklepanost" (kinetická energie) systému neklesne pod nějaké minimum. V příkladu níže provádím iterace při každém snímku, model se nikdy úplně nezastaví.

function onEF(e:Event):void
{
   for(i=0; i < n; i++) // projdu vrcholy
   {
      var v:Vertex = vertices[i];
      var u:Vertex;
      v.net_force.x = v.net_force.y = 0;
      for(j=0; j < n; j++) // spočítám odpudivou sílu vůči ostatním
      {
         if(i==j)continue;
         u = vertices[j];
         var rsq:Number = ((v.x-u.x)*(v.x-u.x)+(v.y-u.y)*(v.y-u.y))/200;
         v.net_force.x += (v.x-u.x) /rsq;
         v.net_force.y += (v.y-u.y) /rsq;
      }
      for(j=0; j < n; j++) // spočítám přitažlivou sílu pro hrany
      {
         if(!edges[i][j])continue;
         u = vertices[j];
         v.net_force.x += 0.06*(u.x - v.x);
         v.net_force.y += 0.06*(u.y - v.y);
      }
      v.velocity.x = (v.velocity.x + v.net_force.x)*0.85; 
      v.velocity.y = (v.velocity.y + v.net_force.y)*0.85; 
   }
   for(i=0; i < n; i++) // nastavím vrcholům nové pozice
   {
      v = vertices[i];
      if(v.isDragged){ v.x = mouseX; v.y = mouseY; }
      else { v.x += v.velocity.x; v.y += v.velocity.y; }
   }
   // nakreslím hrany
   graphics.clear();
   graphics.lineStyle(3, 0x333333);
   for(i=0; i < n; i++)
   {
      for(j=0; j < n; j++)
      {
         if(!edges[i][j]) continue;
         graphics.moveTo(vertices[i].x, vertices[i].y);
         graphics.lineTo(vertices[j].x, vertices[j].y);
      }
   }
}

Trie v AS3

2010-11-17T06:15:00.000-08:00

Dnes se ve flashi pokusíme implementovat datovou strukturu Trie. Kromě samotné trie ji navíc nějak hezky vykreslíme, abychom dostali přehledné znázornění této struktury.

Něco o Trii

Řekněme, že náš program dostane tisíc slov, která musíme uložit do nějaké struktury. Poté nám budou chodit dotazy, zda naše struktura obsahuje konkrétní slovo. Uložení prvku do lineárního pole by bylo paměťově náročné, zároveň při hledání slova bychom museli projít všechny prvky. Trie je na tom o mnoho lépe. Sice přidání slova není tak rychlé jako u pole, ale hledání je výrazně rychlejší. Pokud v každém uzlu uchováváme pole o velikosti celé abecedy, jdeme od kořene přímo k listu, složitost je rovná délce slova. Více ve článku na Wikipedii.

Třída TNode

Co od trie chci

Chci si trii snadno vytvářet (var trie = new ...), snadno přidávat slova (trie.AddWord("ahoj");). Chci snadno zjišťovat, zda obsahuje nějaké slovo (if(trie.Contains("ahoj")) ...).

Jak ukládat potomky uzlu

Každý uzel ve trii může mít potomků od 0 až do velikosti abecedy. Abecedy jsou často velké (26 - písmena ang. abecedy, 256 - ASCII znaky, $2^{16}, 2^{24}, 2^{32}$ - znaky Unicode atd.). Avšak uzel většinou neobsahuje všechny tyto potomky. Paměťově efektivnější použít nějaké menší pole pevné velikosti, do kterého budeme prvky hešovat. Níže ukládám prvek na pozici (kód znaku) modulo 4. Kolize řeším vytvářením spojového seznamu.

Základní třída

package
{
   public class TNode
   {
      // pole 4 potomků tohoto uzlu
      public var cn:Vector. = new Vector.(4, true);
      public var c:String;   // znak uložený v uzlu
      public var next:TNode; // ukazatel na další prvek na stejné úrovni
      public var isEnd:Boolean = false; // zda je uzel koncem slova
  
      public function TNode(c:String):void
      {
         this.c = c; // přiřadím znak do "c"
      }
   }
}

Vyhledání potomka pro daný znak

Jelikož potomky máme v poli pevné velikosti a navíc ve spojových seznamech, není jejich vyhledání úplně triviální, proto si raději napíšeme metodu.

public function GetChild(s:String):TNode
{
   // nejdříve se podíváme do pole
   var n:TNode = cn[ s.charCodeAt(0)% 4 ];
   if ( n == null) return null; // nebyl v poli
   else    // byl v poli, hledáme ve spojáku
      while (n.next != null)  
      {
         if (n.c == s) return n;
         n = n.next;
      }
   if (n.c == s) return n; // byl na konci spojáku
   return null; // nebyl nikde
}

Přidání slova do trie

Nejdříve si přečteme první znak slova. Buď pro tento znak už máme potomka, nebo ne (potom ho vytvoříme). Tomuto potomku sdělíme mu, aby si přidal zbytek slova.

public function AddWord(s:String):void
{
   // podíváme se, zda nemáme potřebného potomka
   var n:TNode = GetChild(s.charAt(0));
   if(n==null) // nemáme
   {
      n = new TNode(s.charAt(0)); // vytvoříme ho
      var pos:int = s.charCodeAt(0)% 4; // kam ho dáme
      if(cn[pos] == null) cn[pos] = n;  // místo je volné
      else // není volné - dáme do spojáku
      {
         var no:TNode = cn[ pos ];
         while(no.next != null) no = no.next;
         no.next = n;
      }
   }
   // když není konec slova, přidáme zbytek do "n"
   if(s.length>1) n.AddWord(s.substring(1,s.length));
   else n.isEnd = true; // konec slova
}

Zda trie obsahuje slovo

public function Contains(s:String):Boolean
{
   // když jsme na dně rekurze, vrátíme "isEnd"
   if(s.length == 0) return isEnd;
   // podíváme se na potomka s daným znakem
   var n:TNode = GetChild(s.charAt(0));
   if(n==null) return false; // potomek není
   else return n.Contains(s.substring(1,s.length)); // potomek je
}

Vykreslení trie

Trii vykreslujeme podobným způsobem, jako Binární vyhledávací strom.

function vykresli(n:TNode, x:int, y:int, w:int, place:Sprite)
{
   var i:int;
   // potomky uzlu si dám do nového pole
   var nodes:Array = new Array();
   for(i = 0; i<4; i++)
   {
      var no:TNode = n.cn[i]; if(no == null) continue;
      while(no != null){ nodes.push(no); no = no.next;}
   }
   var sW:int = w/nodes.length; // místo pro každý uzel
   for (i = 0; i < nodes.length; i++)
   {
      with(place.graphics)  // čára k potomkovi
      {
         lineStyle(3,0x00E1FF);
         moveTo(x, y);
         lineTo(x-w/2 + i*sW + sW/2, y+60);
      }
      // a vykreslení potomka
      vykresli(nodes[i], x-w/2 + i*sW + sW/2, y+60, sW, place); 
   }

   // nakreslíme kroužek pro daný uzel
   with(place.graphics)
   {
      if(n.isEnd) lineStyle(4, 0x000000); // když je koncový
      else lineStyle(2, 0x333333);  // když není - tenčí okraj
      beginFill(0x6D00D9);
      drawEllipse(x-14, y-14, 28, 28);
      endFill();
   }
 
   // přidáme textové pole s písmenkem
   var tf:TextField = new TextField();
   tf.text = n.c; tf.x = x-tf.textWidth; tf.y = y-14;
   place.addChild(tf);
}

Sierpinského trojúhelník v AS3

2010-11-10T15:08:00.000-08:00

V tomto článku si ukážeme, jak v ActionScript 3 snadno rekurzivně nakreslit fraktál, a to konkrétně Sierpinského trojúhelník.

Sierpinského trojúhelník

Sierpinského trojúhelník je fraktálový obrázek, který lze vytvořit např. tímto způsobem:

Nakreslíme černý trojúhelník
Z černého trojúhelníku odstraníme "vnitřní trojúhelník" a tuto funkci zavoláme na tři menší trojúhelníky, které vznikly v okolí

Další informace naleznete ve článku na Wikipedii.

Kód v AS3

var limit:int = 6;

function drawTriangle(x:Number, y:Number, level:int, size:Number):void
{
   if(level==0)  // pokud jsme na 0. úrovni, nakreslíme čer. troj.
      with(graphics)
      {
         clear();
         beginFill(0x00);
         moveTo(x, y-size);
         lineTo( x + size * 1.73/2, y + size/2);
         lineTo( x - size * 1.73/2, y + size/2);
         moveTo(x, y-size);
         endFill();
      }
   if(level == limit) return; // pokud jsme se zanořili do limitu, nepokračujeme
   with(graphics)    // nakreslíme bílý trojúhelník
   {
      beginFill(0xffffff);
      moveTo(x, y+size/2);
      lineTo( x - size * 1.73/4, y - size/4);
      lineTo( x + size * 1.73/4, y - size/4);
      moveTo(x, y+size/2);
      endFill();
   }
   // nakreslíme trojúhelníky kolem
   drawTriangle(x, y - size/2, level+1, size/2); // horní
   drawTriangle(x - size * 1.73/4, y + size/4, level+1, size/2); // pravý dolní
   drawTriangle(x + size * 1.73/4, y + size/4, level+1, size/2); // levý dolní
}

Binární vyhledávací strom v AS3

2010-11-03T14:34:00.000-07:00

V tomto článku si ukážeme konkrétní příklad použití OOP ve flashi. Implementujeme si binární vyhledávací strom v AS3 a jeho základní metody. Nakonec ho zkusíme ještě vykreslit.

Co je to Binární vyhledávací strom?

BVS (binární vyhledávací strom), anglicky BST (binary search tree) je dynamická datová struktura, která obsahuje množinu porovnatelných prvků (čísla, slova) a pokud je dobře vyvážený, umožňuje rychlé operace s nimi (v logaritmickém čase - $O(log(n))$. Podrobný popis v článku na Wikipedii.

Třída Uzel

Co od stromu chci

Chci, abych si strom mohl snadno vytvořit (var strom = new ...), mohl do něj snadno přidávat další čísla (strom.Přidej(24);). Chci mít možnost zjišťovat, zda nějaké číslo je ve stromě (if(strom.Obsahuje(24)) ...). Také chci snadno vypisovat jeho obsah (trace(strom.toString());)

Data v uzlu

Každé číslo bude ležet v uzlu, vlevo budou čísla menší, vpravo větší. Každý uzel zároveň definuje strom, který je pod ním.

Základní třída

package
{
   public class Uzel
   {
      public var levý:Uzel; // uzel vlevo
      public var pravý:Uzel; // uzel vpravo
      public var hodnota:int = int.MAX_VALUE; // hodnota v uzlu
   }
}

Konstruktor

Jeho parametr je číslo, které sem ukládáme. Pokud nebude uveden, hodnota v uzlu je int.MAX_VALUE.

public function Uzel(c:int = int.MAX_VALUE):void
{
   if(c == int.MAX_VALUE) return; // bez parametru -> vrátíme se
   hodnota = c; // jinak přiřadíme parametr do hodnoty
}

Přidání čísla do struktury

je velmi snadné. Pokud daná hodnota už je v uzlu, neděláme nic. Pokud přidáváme menší číslo než hodnota v uzlu, přidáme ho do levého podstromu, jinak do pravého.

public function Přidej(c:int)
{
   if(hodnota == int.MAX_VALUE) 
   { hodnota = c; return;} // konstruktor byl bez parametru
   if(c == hodnota){return; } // c už tu je
   if(c > hodnota)
   {
      if (pravý != null) pravý.Přidej(c);
      else pravý = new Uzel(c);
   }
   else
   {
      if (levý != null) levý.Přidej(c);
      else levý = new Uzel(c);
   }
}

Zjištění, zda číslo už je ve struktuře

je také snadné. Podíváme se, zda je v daném uzlu, pokud je menší než hodnota v uzlu, hledáme ho v levém podstromu, jinak v pravém.

public function Obsahuje(i:int):Boolean
{
   if(i == hodnota) return true;
   if(i < hodnota) 
   {
      if(levý != null) return levý.Obsahuje(i);
      else return false;
   }
   else 
   {
      if(pravý != null) return pravý.Obsahuje(i);
      else return false;
   }
}

Vypsání čísel ve struktuře - seřazeně

Obsah stromu vypíšeme velmi snadno. Nejdříve vypíšeme levý podstrom, pak vypíšeme hodnotu v tomto uzlu tolikrát, kolikrát tu je, potom pravý podstrom.

public function toString():String
{
   var out:String = "";
   
   if(levý != null) out += levý.toString();
   out += hodnota + ", ";
   if(pravý != null) out += pravý.toString();
   
   return out;
}

Další funkce

Další funkce, které by měl BVS umět, je odebrání prvku (můžete doprogramovat). Velmi užitečné jsou funkce pro vyvažování (aby strom byl symetrický a neměl dlouhé větve, kdy musíme chodit příliš hluboko). To často obnáší úpravu funkcí pro přidávání a odebírání prvku. Pravidla pro toto vyvažování jsou např. AVL strom nebo Červeno-černý strom.

Použití třídy

Zkusme si do stromu naházet nějaké hodnoty a pak ho vypsat.

btn.addEventListener(MouseEvent.MOUSE_DOWN, vav);

function vav(e:MouseEvent):void
{
   var strom:Uzel = new Uzel();
   txt.text = "Přídáváme:\n";
   for(var i:int = 0; i < 15; i++) 
   {
      var číslo:int = Math.round(Math.random()*100)-50;
      strom.Přidej(číslo);
      txt.appendText(číslo + ", ");
   }
   txt.appendText("\nSeřazené:\n"   + strom.toString());
   txt.appendText("\nObsahuje -5: " + strom.Obsahuje(-5));
   txt.appendText("\nObsahuje 10: " + strom.Obsahuje(10));
}

Vykreslení stromu

Napišme si funkci pro rekurzivní vykreslení stromu.

function vykresli(u:Uzel, x:int, y:int, šířka:int, místo:Sprite)
{
   //--- když uzel má levého syna
   if(u.levý != null)
   {
      //--- nakreslíme k němu čáru
      with(místo.graphics)
      {
         lineStyle(6,0x00E1FF);
         moveTo(x, y);
         lineTo(x - šířka/4, y + 70);
      }
      //--- a vykreslíme syna
      vykresli(u.levý, x - šířka/4, y + 70, šířka/2, místo); 
   }
   //--- když má pravého, to samé
   if(u.pravý != null)
   {
      with(místo.graphics)
      {
         lineStyle(6,0x91FF00);
         moveTo(x, y);
         lineTo(x + šířka/4, y + 70);
      }
      vykresli(u.pravý, x + šířka/4, y + 70, šířka/2, místo); 
   }
   //--- nakreslíme kroužek pro tento uzel
   with(místo.graphics)
   {
      lineStyle(4, 0x6D00D9);
      beginFill(0xff005E);
      drawEllipse(x - 23 - i*4, y - 23 - i*4, 46, 46);
      endFill();
   }
   //--- přidáme textové pole s číslem
   var tf:TextField = new TextField();
   tf.text = u.hodnota.toString();
   tf.x = x-tf.textWidth-2;
   tf.y = y-16;
   tf.setTextFormat(tfo);
   místo.addChild(tf);
}

2. Rychlý úvod - Flash a OOP - teorie

2010-11-03T12:45:00.000-07:00

V tomto článku se seznámíme se základy objektově orientovaného programování v AS3. Předpokládám, že již znáte základní koncepty OOP (OOP na Wikipedii).

Teorie

AS3 je objektově orientovaný jazyk a každá proměnná je nějakého typu / třídy a má s ní spojené vlastnosti a metody.
Ve flashi je zvykem definici každé třídy psát do zvláštního souboru. Každá třída je uvnitř nějakého package (balíček), které také definuje jmenný prostor, ve kterém je třída umístěna.
Základním typem je Object, ze kterého dědí všechny třídy. Pokud předka nespecifikujeme, předpokládá se, že je to právě Object.
Každá metoda je virtuální, můžeme ji tedy v potomcích přepsat.

Parametry třídy a její položek

public - veřejná položka, dostupná všem
private - soukromá, dostupná pouze z dané třídy
protected - private + přístupná pro podtřídy
internal - dostupná v rámci daného jmenného prostoru
static - statická položka, patří třídě, nezávislá na instancích
override - nahrazuje danou metodu předka

Ukázka OOP v AS3

První třída

package fauna // jmenný prostor "fauna"
{
   //import flash.display.MovieClip;  // -import dalších tříd
 
   public class Zvíře // definice třídy
   {
      public var hmotnost:int = 10; // proměnná a poč. hodnota
      public var jmeno:String;
 
      public function Zvíře(/*parametry*/) :void // konstruktor třídy
      {
      }
 
      public function OzviSe() :String // veřejná metoda
      {
         return("Ahoj, jsem " + jmeno + " a vážím " + hmotnost + "kg!");
      }
   }
}

Rozšíříme třídu

package fauna
{
   import fauna.Zvíře;
 
   public class Pes extends Zvíře
   {
      public var kouše:Boolean;
      public var plemeno:String;

      public function Pes() :void 
      {
      }
 
      public override function OzviSe() :String
      {
         var hláška:String = "Ahoj, jsem pes " + jméno + " a ";
         hláška += kouše?"koušu!":"nekoušu!";
         return(hláška);
      }
   }
}

Použití tříd

var prase:Zvíře = new Zvíře();
prase.jméno = "Čuník";
prase.hmotnost = 100;

var alík:Pes = new Pes();
alík.jméno = "Alík";
alík.hmotnost = 15;
alík.kouše = true;
trace(alík.OzviSe());
// vypíše "Ahoj, jsem pes Alík a koušu!"

Zdrojové soubory

1. Rychlý úvod do Adobe Flash / AS3

2010-10-14T14:23:00.000-07:00

V tomto článku se vás pokusím rychle uvést do Adobe Flash a jazyku AS3 a ukážu základy potřebné pro praktickou práci. Předpokládám, že jste programátoři. Zbylé věci z prostředí Adobe Flash se lze doučit praxí.

AS3

Komentáře

// toto je jednořádkový komentář
/*
toto je komentář na
více řádků
*/

Funkce pro vypsání textu (při debuggingu)

trace("ahoj" + nejakyString + ".");

Proměnné

Základní:

// var název:Typ = hodnota;
var n:int = 5;
var a:Number = 4.3419;
var s:String = "Ahoj Ahoj";
var b:Boolean = true; // nebo false

Pole:

var a:Array = [];
a = [4, 3, "ahoj", b, true];
a[2] = "čau";
var n:Number = a[0];

Instance tříd:

// var název:Typ = new KonstruktorTřídy(parametry ...);
var mc:MovieClip = new MovieClip();
var tf:TextField = new TextField();

Podmínky

// if(podmínka) proveď jednu věc
// if(podmínka) {proveď víc věcí}
// else {proveď něco jiného}
if(x == 5) trace("x je pět");
else trace("x není pět");

Další operátory pro porovnávání naleznete ZDE

Cykly

// for (počáteční hodnota; podmínka; operace při cyklu) dělej něco
for(var i:int = 0; i < 10; i++)
{
   trace(i);
}
// while (podmínka) dělej něco
var j:int = 0;
while(j < 10)
{
   trace(j);
   j++;
}

Funkce

// function názevFunkce(parametry ...)
// :Typ návratové hodnoty nebo "void" {něco ...; return něco;}
function dvaKrat(a:int):int
{
   //nějaký kód ..
   return a*2;
}

Události

Veškeré asynchronní akce v Adobe Flash jsou prováděny přes systém událostí (Event) a tím, že jim nasloucháme a případně provedeme obslužnou rutinu. Většina tříd pochází z EventDispatcher a mají metody dispatchEvent(event) a addEventListener(typEventu, obslužnáFunkce). Některé DisplayObjecty (např. MovieClip) standardně vyvolávají události myši, klávesnice atd., stačí jim jen naslouchat.

 
// function názevFunkce(parametry):Typ návratové hodnoty 
//nebo "void" {dělej něco ...; return něco;}
var mc:MovieClip = new MovieClip();
mc.addEventListener("mojeUdalost", mojeFunkce);
var e:Event = new Event("mojeUdalost");
mc.dispatchEvent(e);

function mojeFunkce(ev:Event):void
{
   trace("zavolána událost");
}

Standardní události jsou typů Event, MouseEvent nebo KeyboardEvent.

MovieClip

Nejznámější třídou ve flashi je MovieClip. Je to zobrazovatelný objekt (DisplayObject), může obsahovat další objekty (je to i DisplayObjectContainer). Má časovou osu a vyvolává událost "enterFrame" podle FPS. Má metodu addChild(p) pro přidání objektu. Více o MC. Má vlastnosti jako "x", "y", "alpha", "width", "height" ...

Matematické funkce

Ty jsou ve statické, uloženy ve třídě Math. Jsou to např. sin, cos, abs, log, tan, min, max. Math.random() vrací náhodné číslo mezi 0 a 1. Obsahuje konstanty Math.PI nebo Math.E. Více o třídě Math.

Přklady AS3

Načítání obrázků

var obr:Array = ["obr1.jpg", "obr2.jpg", "novyobrazek.jpg"];

for(var i:int = 0; i<obr.length; i = i+1)  nactiObrazek( obr[i] );

function nactiObrazek (c:String) : void
{
   // dopíšeme načítání obrázku
   trace("Načítáme obrázek: " + c);
}

Teď si vytvoříme čtverec asi 30px x 30px, převedeme ho na MovieClip a nastavíme export pod třídou "Ctverec"

Umístění čtverců po diagonále

var ctverce : MovieClip = new MovieClip ()
addChild (ctverce);

for (var i:int = 0; i < 10; i++)
{
   var c:Ctverec = new Ctverec();
   c.x = i*50;
   c.y = i*50;
   ctverce.addChild(c);
}

Jednoduchá hra - počítá se počet najíždění na čtverce

var tf:TextField = new TextField();
addChild(tf);
tf.x = 200;

var n:int = 0;

for (var i:int = 0; i < 4; i++)
{
   for (var j:int = 0; j < 5; j++)
   {
      var c:Ctverec = new Ctverec();
      c.x = j*100;
      c.y = i*100;
      addChild(c);
      c.addEventListener(MouseEvent.MOUSE_OVER, mojeFunkce);
   }
}

function mojeFunkce(e:MouseEvent):void
{
   e.target.x = Math.random()*500;
   e.target.y = Math.random()*400;
   n++;
   tf.text = "Chytil jsi " + n + " čtverců";
}

LU rozklad

2010-09-25T15:49:00.000-07:00

Tato práce vznikla jako zápočtový projekt na předmětu Algoritmy a datové struktury 1, MFF UK. Pojí se k ní ještě tato implementace v C#.

Efektivní maticové operace s využitím LU rozkladu

LU rozklad nám říká, že čtvercovou regulární matici lze rozložit na součin matic $A = L * U$, kde L je dolní a U je horní trojúhelníkova matice. Zatím nezkoumejme tuto větu do hloubky a pojďme na to postupně.

Využití:

Řešení soustavy rovnic

Mějme soustavu lineárních rovnic $A * x = b$, která se dá řešit gaussovou eliminací. Pokud se nám však podaří převést matici A na součin $L * U$, tedy $L * U * x = b$ (mějme na paměti, že matice L a U jsou trojúhelníkové), vektor $U*x$ snadno spočteme dopřednou a vektor x zpětnou substitucí.

Výpočet determinantu

Mějme za úkol určit determinant matice A, $det(A)$. Pokud se nám podaří převést A na součin $L*U$, pak $det(A) = det(L*U) = det(L) * det(U)$, což je součin prvků na diagonále L a U, jelikož to jsou matice trojúhelníkové.

Inverze matice

Mějme za úkol určit inverzní matici k A, $A^{-1}$. Hledáme tedy řešení rovnice $A * A^{-1} = I$. K tomuto můžeme přistupovat jako k řešení n soustav rovnic, tj. $A * x_i = e_i$, kde $e_i$ je jednotkový vektor s 1 na i-tém místě a $x_i$ je sloupec námi hledané matice.

Jak je vidět, pro takovýto rozklad matice bychom našli spoustu využití.

Algoritmus:

Idea

Uvažujme normální gaussovu eliminaci. V první fázi je zde snaha převést matici na horní trojúhelníkovou, v našem případě by to mohla být matice U. Zde vyplývají na povrch dvě zajímavé otázky - zda by se nedaly elementární úpravy reprezentovat násobením maticí zleva a zda by součin těchto matic elementárních úprav nebyl dolní trojúhelníkovou maticí. Odpověď je ano. Převod na horní trojúhelníkovou matici je možné realizovat přičítáním alfa-násobku prvního vhodného řádku k řádkům pod ním, abychom vynulovali daný sloupec pod pivotem. Tato elementární úprava se dá reprezentovat násobením zleva maticí, kterou vyrobíme z jednotkové tak, že pod pivot umístíme potřebné koeficienty.

Příklad

Úskalí

Při tomto postupu se může stát, že se na diagonále objeví nula. Při běžné gaussově eliminaci tyto dva řádky (i. a j.) prohodíme. Tuto úpravu můžeme emulovat prohozením i. a j. řádku v matici L, ovšem potom L už nebude trojúhelníková. Vyřešíme to tzv. “permutační maticí” P, která bude na začátku jednotková a které budeme prohazovat řádky. Rozklad tedy bude $A = P L U$.

Vliv permutační matice na operace:

řešení soustavy rovnic - $PLUx = b$ - ve vstupním vektoru b pouze prohodíme hodnoty podle matice $P$.
determinant - $det(PLU)$ - někde si evidujeme počet prohození řádků v P, podle kterého výsledný determinant vynásobíme +1 / -1.
inverze - ve výsledné inverzní matici prohodíme řádky podle matice P

Složitost:

V cyklu musíme probrat řádky matice a od každého z nich odečteme násobek prvního řádku, to vše pro každý ze sloupců. Jsou to tedy 3 vnořené cykly a složitost LU rozkladu je tedy $O(n^3)$.

Při řešení soustavy rovnic je třeba dopočítat vektor Ux dopřednou a x zpětnou substitucí (obojí má složitost $O(n^2)$). Nezískali jsme tedy žádné zrychlení oproti Gaussově eliminaci (složitost $O(n^3)$). Zrychlení ale získáme ve chvíli, kdy máme vyřešit stejnou soustavu A pro více pravých stran. Když už jednou spočítáme LU rozklad, vyřešení soustavy pro libovolnou pravou stranu má složitost $O(n^2)$.

Efektivnost výpočtu determinantu dle definice musíme sečíst n! členů, v každém z nich vynásobit n čísel, složitost je tedy $O(n*n!)$. Determinant lze vypočítat pomocí gaussovy eliminace v čase $O(n^3)$. Náš algoritmus funguje také v čase $O(n^3)$, jelikož LU rozklad je jiný způsob přístupu ke gaussově eliminaci.

Výpočet inverzní matice gaussovou eliminací má složitost $O(n^3)$. Nezískali jsme tedy žádné zrychlení.

Taylorův polynom srozumitelně

2010-09-24T08:11:00.001-07:00

Článek jsem napsal proto, že všechny články na internetu se mi zdály příliš složité a nevysvětlovaly základní princip fungování taylorova polynomu.

Vyhýbám se přesným formalismům, mohou zde být i drobné nepřesnosti, avšak doufám, že po přečtení článků vám formalismy přijdou jasné a srozumitelné.

Předpoklady

Před tím, než začnete číst, byste měli vědět, co je to polynom, derivace a faktoriál, a umět derivovat a integrovat polynom.

Polynom je funkce, do které dosadíme hodnotu x a pomocí sčítání, odčítání, násobení a dělení spočítáme hodnotu polynomu v bodě x.

Derivace funkce v bodě a je číslo. Pokud y roste stejně rychle jako x, derivace je $=1$. Pokud y roste rychleji než x, derivace je $>1$, pokud pomaleji, derivace je $<1$. Pokud x roste, ale y stojí, derivace je $=0$.

Motivace

V každodenním životě často potřebujeme spočítat sinus, cosinus, tangens či logaritmus. Tak daleko však chodit nemusíme. Stačí, když potřebujeme spočítat odmocninu z nějakého čísla. Problém je ten, že my, lidé, umíme jenom sčítat, odčítat, násobit a dělit. Málo kdo z nás dokáže sínusit, logaritmovat či odmocňovat. Bohužel ani počítače nám s tím nepomohou. Jejich procesory většinou umí taky pouze sčítat (či přičítat opačnou hodnotu) nebo násobit (či násobit převrácenou hodnotou).

Už před stovkami let však existovaly matematické tabulky s hodnotami těchto funkcí. Stejně tak i kalkulačka při zmáčknutí SIN nám vrátí dost přesnou hodnotu. Jak to tedy ti lidé nebo stroje dělají?

Řešení je v přiblížení (aproximace) naší funkce (kterou neumíme spočítat) nějaké jiné podobné funkci (kterou umíme spočítat).

Konkrétní příklad

Řekněme, že chceme spočítat $sin(1)$, tedy sinus jednoho radiánu, který má hodnotu asi 0.841470984. O funkci sinus víme tyto 3 věci:

sinus nuly je nula ... $sin(0) = 0$
derivace sinu v nule je jedna ... $sin'(0) = 1$
sinus má periodu dvě pí ... $sin(x) = sin(x + 2\pi)$

Hezká vlastnost polynomů

Polynomy mají jednu hezkou vlastnost, a to:

"Pro každých N bodů v rovině existuje polynom stupně N-1 nebo menšího, který jimi prochází."

To znamená, že:

pro každý bod existuje vodorovná přímka, která jim prochází
pro každé dva body existuje přímka, která jimi prochází
pro každé tři body existuje parabola, která jimi prochází
...

Vypadá to tedy, že polynomy mohou vypadat jakkoli a podobat se nejrůznějším funkcím.

Základní princip taylorova polynomu

Taylorův polynom je založen na jednoduchém principu, a to:

"Dvě funkce si jsou v okolí bodu X tím více podobné, čím více se podobají jejich derivace vyšších řádů v tomto bodě."

Idea byla asi takováto: funkce by se měly v okolí bodu podobat jedna druhé. Asi by tam měly mít stejnou funkční hodnotu (celkem logické). Asi by ten bod měly protínat pod stejným úhlem (neměla by tam jedna funkce růst a druhá naopak klesat). Pak by tam měly být obě stejně "křivé" (aby jedna nebyla v tomto bodě konvexní zatímco druhá konkávní). A pak si náhodou všimneme, že jsme právě mluvili o nulté, prví a druhé derivaci :)

Vypadá to, že by mohlo platit něco takového:

funkce by měly mít stejnou 0. derivaci, tj. funkční hodnotu v daném bodě.
když mají stejnou 1. derivaci (stejnou směrnici tečny v daném bodě), jsou si víc podobné
když mají stejnou 2. derivaci, jsou si podobné ještě víc
...

Přiblížení polynomem obecně

Přibližujeme polynomem právě proto, že ho umíme spočítat (stačí nám sčítání, odčítání ...).

Příklad: $sin(x)$ v bodě 0 má nultou derivaci 0, první derivaci 1, druhou derivaci 0, třetí -1 a dál se to opakuje. Pokud bychom tedy našli polynom, který bude mít v nule stejné derivace do nějakého řádu, můžeme místo sinu počítat hodnotu polynomu a věřit, že se to skoro rovná hodnotě sinu.

Příklad: hledání polynomu pro sinus

Zkusme najít polynom, který bude podobný funkci sinus v okolí nuly. Nejdříve chtějme, aby měl stejnou 0. derivaci, potom 1., 2. ... a postupně zvyšujme nároky. Přitom si všímejme, jak se graf polynomu více a více podobá grafu sinu a zároveň $f(1)$ se víc a víc blíží $sin(1)$.

Polynom nultého stupně, co má v 0 stejnou hodnotu, jako sinus, je $f(x) = 0$ (stejná 0. derivace), f(1)= 0

Sinus má první derivaci rovnou 1, odpovídá tomu polynom $f(x) = x$ (stejná 0. a 1. derivace), f(1)= 1
Funkce $f(x) = x$ má v bodě 0 druhou derivaci 0, nepotřebujeme ji nijak měnit.
Třetí derivace našeho polynomu v nule má být -1, zkusme tedy trochu integrovat a podle potřeby přičítat konstantu.
- $f'''(x) = -1$ - v nule má být -1 (třetí derivace)
- $f''(x) = -x$ - v nule má být 0 (druhá derivace), což odpovídá
- $f'(x) = 1 - \frac{x^2}{2}$ , v nule má být 1 (první derivace), proto + 1
- $f(x) = x - \frac{x^3}{6}$ v nule má být 0 (nultá derivace), což odpovídá
a skutečně, polynom $f(x) = x - \frac{x^3}{6}$ se už víc podobá sinu (stejná 0. až 3. derivace), f(1)= 0.833333
Čtvrtá derivace našeho polynomu v nule má být 0, tomu už ale vyhovuje předchozí polynom.
Pátá derivace našeho polynomu má být 1, a tedy:
- $f''''(x) = x$ - v nule má být 0 (čtvrtá derivace), což odpovídá
- $f'''(x) = -1 + \frac{x^2}{2}$ , v nule má být -1 (třetí derivace), proto - 1
- $f''(x) = -x + \frac{x^3}{6}$ v nule má být 0 (druhá derivace), což odpovídá
- $f'(x) = 1 - \frac{x^2}{2} + \frac{x^4}{24} $ v nule má být 1 (první derivace), proto + 1
- $f(x) = x - \frac{x^3}{6} + \frac{x^5}{120}$ v nule má být 0 (nultá derivace), což odpovídá
a skutečně, polynom $f(x) = x - \frac{x^3}{6} + \frac{x^5}{120}$ se už víc podobá sinu (stejná 0. až 5. derivace), f(1)= 0.841666
Šestá derivace našeho polynomu v nule má být 0, tomu už ale vyhovuje předchozí polynom.
Podobným způsobem odvodíme nebo odhadneme další, přesnější polynom, a to $f(x) = x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}$. (stejná 0. až 7. derivace), f(1)= 0.841468

Došli jsme tedy k funkci $f(x) = x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}$, která je v okolí 0 velmi podobná funkci $sin(x)$.

Jak jsme si všimli, $sin(x)$ má v bodě nula derivace sudého řádu vždy nulové, taylorův polynom se mění pouze u přesnosti do liché derivace, stejně tak x má v polynomu pouze liché exponenty. Teď možná mnozí tuší, kde se vzal výraz "lichá funkce" (funkce souměrná dle počátku).

Taylorův polynom pro obecnou funkci

Pro obecnou funkci f hledáme taylorův polynom p, který bude funkci f podobný v okolí bodu a. O funkci f známe několik úrovní derivací v bodě a. Polynom p musí v bodě a nabývat stejných derivací, jako f. Tedy $p^{(i)}(a) = f^{(i)}(a)$. To je vše, co od funkce p vyžadujeme.

Pokud do i-krát zderivovaného polynomu p dosadíme a, všechny členy by se měly vynulovat a zůstane tam pouze číslo $f^{(i)}(a)$. Polynom p tedy musí obsahovat hodnoty těchto derivací, navíc členy musí obsahovat (x-a), aby se vynulovaly po dosazení a. Členy polynomu musí také mít jmenovatele, který se při derivování bude krátit s exponenty, které se derivováním snižují o 1. Ve jmenovateli by měl být součin těchto exponentů, tedy faktoriál.

Vyhovuje tomu tento zápis:

$p(x) = f(a) + \frac{f'(a) * (x-a) }{ 1! } + \frac{f''(a) * (x-a)^2 }{ 2! }+ \frac{f'''(a) * (x-a)^3 }{ 3! } + ...$

Po dosazení a se polynom rovná $f(a)$ (ostatní členy se vynulovaly). Zkusme polynom zderivovat.

$p'(x) = 0 + f'(a) + \frac{f''(a) * (x-a)^1 }{ 1! }+ \frac{f'''(a) * (x-a)^2 }{ 2! } + ...$

Po dosazení a se polynom rovná $f'(a)$ (ostatní členy se vynulovaly). To platí i pro další úrovně derivování.

Polynom pro naši funkci sinus (a=0, nultá derivace 0, první 1, druhá 0, třetí -1, čtvrtá 0, ...) by vypadal takto:

$p(x) = 0 + \frac{1 * (x-0) }{ 1! } + \frac{0 * (x-0)^2 }{ 2! }+ \frac{-1 * (x-0)^3 }{ 3! } + \frac{0* (x-0)^4 }{ 4! } + \frac{1 * (x-0)^5 }{ 5! } +... $

Taylorova řada

Pokud pro nějakou funkci známe všechny její derivace do nekonečna (např. pro sinus, kde se tyto derivace opakují), můžeme ji vyjádřit nekonečným taylorovým polynomem. Hodnotu této funkce v nějakém bodě můžeme vyjádřit jako součet řady (nekonečně mnoha čísel).

Příklad:

O funkci $y=e^x$ víme, že v nule má hodnotu 1, první a všechny další derivace také 1. Vyjádříme si pro tuto funkci taylorův polynom

$p(x) = 1 + \frac{1 * (x-0) }{ 1! } + \frac{1* (x-0)^2 }{ 2! }+ \frac{1* (x-0)^3 }{ 3! } + ...$

Teď si můžeme spočítat hodnotu čísla $e$ (tj. $e^1$) libovolně přesně. Je to totiž:

$e = 1 + 1 + \frac{1}{2}+ \frac{1}{6} + \frac{1}{24} + \frac{1}{120} + ...$

Jak vytvořit herní web

2010-09-19T15:18:00.000-07:00

V tomto článku jsem se rozhodl popsat postup při tvorbě webu, kde budeme nabízet online hry. Bude možné do něj snadno přidávat nové hry, odebírat, možnosti komentářů a podobně.

Budeme potřebovat:

internetový hosting s 5 MB volné paměti, podporou PHP a databáze MySQL
redakční systém Wordpress
Plugin a téma do Wordpressu
Čas a chuť přidávat nové hry

Jak získat hosting

Pro náš web potřebujeme, aby byl dostupný neustále, musí tedy být na počítači, který je pořád připojený k internetu. Hosting znamená, že si pronajímáme místo na takovémto počítači a můžeme tam umísťovat svoje stránky a další data.

Spousta hostingů na internetu je zdarma, např. WebZdarma. Většinou podporují PHP a MySQL. Máme jen málo paměti (50 - 500 MB) a musíte na stránkách zobrazovat jejich reklamu.

Hostingů za peníze je ještě víc, např. za poplatek 50 Kč měsíčně můžeme dostat 5 GB paměti a kromě PHP a MySQL dostaneme spoustudalších funkcí.

Instalace Wordpressu

Wordpress je systém, který nám umožňuje psát si blog (dále pouze WP). Je to hromada souborů s příponou ".php" a dá se rozdělit na 3 části:

jádro - to je sada funkcí, které pracují s databází, ukládají a načítají články a informace o nich
téma - to jsou soubory, které si návštěvníci otevírají v prohlížeči. Je tam HTML a CSS kód naší stránky a taky komunikace s jádrem pro načtení článků atd.
pluginy - to jsou další soubory, které si do WP nahrajeme a přidáme tak nové funkce, např. hodnocení článků, ankety, plugin pro vtipy a podobně.

Kroky instalace:

stažení WP, třeba ODSUD, archiv rozbalíte
založení databáze na svém hostingu, které dáte jméno a heslo
v archivu najdeme soubor "wp-config.php" a do něj napíšeme název a heslo k databázi, se kterou WP bude pracovat
všechny soubory nahrajeme na hosting
otevřeme naši stránku, nastavíme přihlašovací údaje a porozhlédneme se v administraci WP

Podrobný návod na instalaci naleznete ZDE

Instalace pluginu

Hry budeme dostávat ze stránek MochiMedia.com, kde nabízí hry zdarma, avšak do každé dávají reklamu. Ital Emanuele Feronato vytovřil plugin do WP, který si sám nahraje hry z MochiMedia a každou z nich uloží do databáze jako příspěvek blogu.

Plugin stáhneme odsud, rozzipujeme a nahrajeme do složky wp-content/plugins. Otevřeme administraci WP, zapneme plugin, vlevo se objeví menu kde zmáčkneme "Feed Games". Po chvilce se objeví seznam her, po kliknutí na "Publish" vedle hry se hra zveřejní do blogu.
Podrobný návod v angličtině je zde.

Instalace tématu

Emanuele Feronato také vytvořil téma pro WP, které zobrazuje články jako tabulku obrázků (to budou náhledy našich her). Téma si stáhneme odsud. Opět rozbalíme a nahrajeme do složky wp-content/themes. V administraci WP téma aktivujeme.

V balíčku s tématem najdeme spoustu souborů, např. CSS nebo obrázky (pozadí, titulní obrázek ...). Ty si můžeme upravit nebo nahrát vlastní, tím změníme vzhled webu podle sebe.
Opět podrobný návod v angličtině je zde.

Výsledek

Jak to vypadá můžete vidět na mém webu s online hrami www.HrejOnlineHry.cz.

Třída pro matice v C# (Strassenův algoritmus, LU rozklad)

2010-09-11T04:58:00.000-07:00

Toto je jednoduchá třída, která obsahuje opravdu rychlé násobení matic (Strassenův algoritmus, který je cache oblivious), LU rozklad a další funkce.

Obsahuje mocnění celým číslem (-1 : inverze, ...), LU rozklad, který se dál používá pro výpočet determinantu inverze a řešení systému lineárních rovnic. Samozřejmostí jsou standardní funkce jako sčítání matic, násobení, transpozice ... Třída má vlastní systém vyjímek a přetížené operátory, takže lze psát

C = A * B;
D = -C;
...

Test

Při pokusu násobení matice 500x500 čísel je výpočet 3 krát rychlejší, než klasickým algoritmem ($O(n^3)$).

Stažení kódu

CS file
EXE example (.NET - Windows)

Maticová kalkulačka v Pascalu

2010-09-10T04:34:00.000-07:00

Vytvořil jsem jednoduchou kalkulačku na matice v Pascalu. Ovládá se z konzole jednoduchými příkazy.

Každá matice je záznam (record) na haldě. Máte 26 pointerů na matice (názvy A až Z).

Kód je psán přehledně a robustně, je snadno rozšířitelný, takže si můžete dopsat vlastní Matlab :)

Maticové funkce v Pascalu

Kód obsahuje sčítání matic, násobení, transpozici, inverzi, gaussovu a gauss-jordanovu eliminaci a další funkce.

Pro začátek napište "help" a zmáčkněte Enter.

EXE soubor
PAS soubor
Dokumentace