(základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním)
(procházení grafu do hloubky a do šířky, složitost procházení grafu, komponenty souvislosti, hledání nejkratších cest, toky v sítích, kostra grafu)
Vnitřní třídění je takové třídění, kdy předem známe tříděné prvky a máme k dispozici dostatek volné paměti, abychom je uvnitř této paměti mohli setřídit. Opakem je pak třídění vnější, kdy jednotlivé prvky předem neznáme a musíme je ze vstupu postupně načítat v pořadí, v jakém přicházejí. Toto třídění se provádí typicky v situacích, kdy máme operační paměti málo a nejsme schopni v ní všechny prvky uložit. Ve vnějším třídění proto využijeme vnější paměti - pracujeme s jednotlivými soubory na disku. Teoreticky tak můžeme setřídit daleko větší množství dat, operace s vnější pamětí jsou však také podstatně pomalejší. Práce se soubory rychlé algoritmy podstatně degraduje.
Úlohu vnitřního třídění založeného na porovnávání dvou prvků lze vždy řešit algoritmem se složitostí ve třídě O(n log n) (takové výborné složitosti dosahuje Heap Sort). Některé jiné algoritmy (Quick Sort, nejrychlejší algoritmus v průměrném případě) mohou v ideálním případě dosahovat i lineární složitosti (O(n)), jiné zase často dosahují složitostí vyšších (O(n2)).
Uspořádávání přímým výběrem
Přímý výběr je přímočarý a jednoduchý algoritmus, který je vhodné použít u krátkých polí. Algoritmus projde celé pole a najde nejmenší prvek, který prohodí s prvním prvkem pole. Takto získané pole má nejmenší prvek na začátku. Algoritmus pokračuje hledáním nejmenšího čísla, které umístí na pozici o jednu větší, než při předchozím průchodu.
Složitost algoritmu Select Sort je O(n2).
Max Sort - algoritmus téměř totožný s Select Sortem, jen probíhá obráceně (od největšího k nejmenšímu).
Bublinkové třídění
Tento algoritmus je velmi pomalý v neuspořádaných polích, ale zato velmi efektivní v polích částečně uspořádaných. Postupně se systematicky porovnávají dvojice sousedních prvků a vyměňují se spolu vždy, když menší číslo následuje po větším. Po prvním průchodu FOR cyklem je zajištěno, že největší číslo je na konci pole. Druhý průchod už můžeme provádět jen ve zbytku pole. Po ukončení druhého průchodu jsou největší dvě čísla správně umístěna. Celý postup opakujeme až do uspořádání celého pole.
Průměrná i nejhorší asymptotická složitost je O(n2).
Shake Sort - Třídění přetřásáním - vychází z bublinkového třídění, které zlepšuje tak, že probublávají střídavě malá čísla na levý okraj a velká čísla na pravý okraj.
Třídění vkládáním
Třídění vkládáním je rychlejší než Select Sort, ale pomalé vzhledem ke Quick Sortu. Třídící metoda spočívá ve vkládání čísla před nejmenší větší číslo. Vkládání probíhá do neustále se zvětšující části pole (seřazené).
Pozn. Prvky se vybírají jen z nesetříděné části pole.
Třídění slučováním
Tento algoritmus rozdělí pole na dvě přibližně stejně velké části. Poté s každou z těchto částí učiní totéž – rozdělí na dvě, dokud nedostaneme jednoprvkové úseky. Jednopoložkové úseky jsou vždy utříděné, takže teď bereme utříděné úseky a slučujeme tak, aby byly zase utříděné(2 úseky se musí znovu setřídit, ne jen spojit). Končíme, až když uspořádáme celé pole. Složitost Merge Sortu je O(n log n).
Výhody a nevýhody: Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. Heapsort) je, že Mergesort pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace Mergesortu, která toto pole nepotřebuje, ale její implementace je velmi složitá a díky vysokému overheadu i pomalá. Kromě toho se Mergesort také ukazuje být pomalejší než Quicksort nebo Heapsort. Na druhou stranu je Mergesort stabilní řadící algoritmus, lépe se paralelizuje a má vyšší výkon na sekvenčních médiích s nižší přístupovou dobou. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadícím algoritmem (v Perlu 5.8, v Javě nebo v GNU C Library). 1)
Třídění pomocí „haldy“
V Heap Sortu se nejdříve vytvoří (binární) haldy. Binární halda je binární strom, pro který platí:
Jsou-li hodnoty uzlů na každé větvi seřazeny vzestupně (čím dále od kořene, tím větší hodnoty), je v kořenu haldy nejmenší prvek. Hovoříme pak o minimové haldě (min-heap).
Jsou-li hodnoty uzlů na každé větvi seřazeny sestupně (čím dále od kořene, tím menší hodnoty), je v kořenu haldy největší prvek. Hovoříme pak o maximové haldě (max-heap).2)
Věta: Neprázdná binární halda na n uzlech má hloubku .3)
Z výše uvedeného vyplývá, že každé patro haldy musí být kompletně zaplněno, pouze poslední patro nemusí mít plný počet prvků. Při přidání dalšího prvku se musí pole znovu „uhaldovat“ – prvek se přidá jako syn a pokud je menší (v případě min-heapu)/větší (v případě max-heapu) než otec, potom se s ním vymění. Pokud je i pak jeho otec menší/větší než přidaný prvek, opět se prohodí atd.
Věta: Algoritmus řazení haldou má složitost Θ(n log n). 4)
Práci s haldou je možné si interaktivně vyzkoušet.
Ve funkcionální implementaci algoritmu řazení haldou, kde se pracuje s explicitní haldou (datovou strukturou binární strom), použijeme minimovou haldu. Naopak v imperativní implementaci, kde se pracuje s implicitní haldou (reprezentovanou polem), je výhodnější použít maximovou haldu.5)
Řazení rozdělováním
Jedná se o rekurzivní třídění
Quick Sort je znatelně nejrychlejší ze zde zmíněných algoritmů. Princip Quick Sortu je velmi jednoduchý – pouze rozdělí čísla na menší a větší. Při opětovném zavolání se rozdělí menší zase na menší-menší a menší-větší a toto se provede i u větších (rozdělí se na větší-menší a větší-menší). Pří dalším zavolání se zase rozdělí každá část na menší a větší, až zbude v každé části pouze jedno číslo, nebo bude daná část uspořádaná.
Jiná definice
Základní myšlenkou Quick Sortu je rozdělení řazené posloupnosti čísel na dvě přibližně stejné části (Quick Sort patří mezi algoritmy typu „rozděl a panuj“). V jedné části jsou čísla větší a ve druhé menší, než nějaká zvolená hodnota (nazývaná pivot). Pokud je tato hodnota zvolena dobře, jsou obě části přibližně stejně velké. Pokud budou obě části samostatně seřazeny, je seřazené i celé pole. Obě části se pak rekurzivně řadí stejným postupem.
Příklad:
Máme posloupnost 5 1 3 4 7 6 8 2. Z posloupnosti vybereme nějaké číslo (a právě výběr tohoto čísla působí na složitost). Následně posloupnost rozdělíme na dvě části. V první části budou všechna čísla menší než zvolené číslo, v druhé části pak čísla větší nebo rovná vybranému číslu.
QuickSort ve funkcionálním zápisu
quickSort :: [Int] -> [Int] quickSort [] = [] quickSort (p:t) = quickSort lt ++ [p] ++ quickSort ge where lt = [ x | x <- t, x < p ] ge = [ x | x <- t, x ≥ p ]
Funkce algoritmu je dostatečně zřejmá z komentářů, takže stručně o co jde: Quick Sort vychází z rekurzivního přístupu – pokud máme třídit elementární pole o dvou prvcích, prvky jednoduše přehodíme na tu stranu, kam patří (porovnat je můžeme s pomyslnou hodnotou mezi nimi – pivotním prvkem). Pokud máme třídit pole větší, roztřídíme takto podle zvoleného pivota i dva velké úseky pole, které potom dále necháme třídit rekurzivně stejnou procedurou, až budou nakonec uspořádány všechny části pole. Tento algoritmus je typickým příkladem použití metody „rozděl a panuj“ (Divide & Impera), kdy programátor daný problém rozdělí na více jednoduchých elementárních problémů, které lze snadno vyřešit (třeba rekurzí). Pokud si vzpomenete na tento princip a vybavíte si postup, určitě pak budete schopni jednotlivé detaily algoritmu snadno doprogramovat.
Průměrná složitost Quick Sortu je O(n log n), přesněji O(n log2n). Stejně tak nejlepší případ, ve kterém je vždy vybrán pivot jako prvek s prostřední hodnotou, má časovou složitost O(n log n), nejhorší případ O(n2) nastává, pokud je pivot vždy nešikovně vybrán jako hodnota maximální nebo minimální. Výše uvedená procedura vybírá pivotní prvek jako střed pole, záleží ale na rozložení vstupních dat, každý z prvků pole je pro určitou kombinaci ideální, výběr se proto někdy provádí náhodně (pomocí generátoru náhodných čísel), což zaručuje, že při různém výběru pivotů nebude volba pro vstupní data vyloženě nevhodná a složitost se tak více přiblíží k očekávané složitosti O(n log n). V průměrném případě se v pravé a levé části pole zaměňuje vždy polovina prvků – pro jednotlivé zmenšující se úseky tedy , , , … – a vzhledem k tomu, že po záměně prvků se každé pole rozdvojuje na dvě poloviny (políčka si můžeme nakreslit do vyváženého binárního stromu), je složitost násobena dvojkovým logaritmem (zhruba zapisujeme jen logaritmus desítkový). Výsledná průměrná složitost je tedy intuitivně:
log n ( + + + + …) = n log n
Prohledávání do hloubky (v angličtině označované jako depth-first search nebo zkratkou DFS) je grafový algoritmus pro procházení grafů metodou backtrackingu. Pracuje tak, že vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil. Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byly všichni navštíveni), vrací se zpět backtrackingem.
Backtracking (česky zpětné vyhledávání) je způsob řešení algoritmických problémů založený na metodě pokus – omyl. Jedná se o vylepšení hledání řešení hrubou silou v tom, že velké množství potenciálních řešení může být vyloučeno bez přímého vyzkoušení. Algoritmus je založen na procházení do hloubky možných řešení.
Algoritmus je úplný (vždy najde řešení, tzn. určitý cílový vrchol, pokud existuje), ale není optimální (pokud graf není strom, nemusí najít nejkratší možnou cestu k cíli). Jeho asymptotická složitost je O(|V| + |E|), kde V je množina vrcholů a E množina hran daného grafu.
Podle pořadí, ve kterém se prochází uzly uspořádaného stromu, se rozlišují tři metody.
Výsledky způsobů procházení v binárním vyhledávacím stromu:
N = navštívený uzel, L = levý, R = pravý
Algoritmus prohledávání do hloubky s omezením na maximální délku větve.
animace prohledávání do hloubky
Algoritmus podle skript
marked(u) = False
). Successors(u)
seznam uzlů-následníků uzlu u.
Chceme-li projít do hloubky všechny uzly grafu G = (V,E), položíme W = V.
Věta: Algoritmus dfs navštíví všechny uzly grafu dosažitelné z uzlů z množiny W.
Důkaz je zřejmý a plyne z toho, že se opakovaně označují všechny uzly, které dosud označeny nebyly. Množina neoznačených uzlů se zmenšuje, takže algoritmus konverguje.
Poznámka: Algoritmus funguje stejně pro orientované i neorientované grafy.
Prohledávání do šířky (anglicky Breadth-first search, zkráceně BFS) je grafový algoritmus, který postupně prochází všechny vrcholy v dané komponentě souvislosti. Algoritmus nejprve projde všechny sousedy startovního vrcholu, poté sousedy sousedů atd. až projde celou komponentu souvislosti.
Prohledávání do šířky je algoritmus či metoda, která postupuje systematickým prohledáváním grafu přes všechny uzly. Nepoužívá při svém prohledávání žádnou heuristickou analýzu, pouze prochází všechny uzly a pro každý projde všechny jeho následovníky. Přitom si poznamenává předchůdce jednotlivých uzlů a tím je poté vytvořen strom nejkratších cest k jednotlivým uzlům z kořene (uzlu, ve kterém jsme začínali) v hranovo neohodnotenom grafe.
Z hlediska algoritmu, veškeré následovníky uzlu získané expanzí uzlu vkládáme do FIFO fronty. FIFO fronta znamená, že první uzel, který do fronty vstoupil, ji také první opustí. V typických implementacích jsou dosud neobjevené označeny jako FRESH. Uzly, které se dostávají do fronty a jsou v této chvíli právě vyšetřovány na jejich následníky, jsou označeny jako OPEN a naposled uzly, které už byly z fronty vybrány a dále se s nimi nebudeme pracovat, jsou označeny jako CLOSE. CLOSE uzly již nikdy v tomto běhu algoritmu nebudou prozkoumávány, mají vyplněné všechny informace. To znamená vzdálenost od kořenového (počátečního) uzlu, stav uzlu (CLOSE) a předchůdce.
Algoritmus prohledávání do šířky
Algoritmus podle skript
Algoritmus bfs (breadth-first search) prochází uzly v jiném pořadí než při prohledávání do hloubky: uzly, které leží blíže počátečním uzlům (uzlům, v nichž procházení začíná), jsou navštíveny dříve než uzly ležící dále od počátečních uzlů.
Pomocné datové struktury: fronta Q uzlů, les nejkratších cest (uložený v poli P)
Navštívené uzly se opět označují pomocí procedury mark
, uzel u bude označen, právě když marked(u) = True
.
Věta: Nechť , a nechť vzdálenost z s do u je menší než vzdálenost z s do v. Pak uzel u bude při výpočtu bfs(G,{s}) označen dříve než uzel v.
Důkaz: Stačí ukázat, že do fronty Q jsou vždy přidávány uzly s aspoň tak velkou vzdáleností od s, než jakou měl poslední přidaný uzel. To však lehce plyne indukcí podle vzdálenosti od uzlu s.
Věta: Nechť . Pak po provedení výpočtu bfs(G,{s}) jsou navštíveny právě všechny uzly, do nichž vede z uzlu s (orientovaná) cesta.
Důkaz: Indukcí podle vzdálenosti od uzlu s.
Složitost procházení grafu do šířky
Věta: Nechť G = (V,E) je graf a je množina počátečních uzlů (vstupního stupně 0). Pak délka výpočtu bfs(G,W) v nejhorším případě je v O(|W| + |E|).
Celková složitost algoritmu : O(|V| + |E|), kde V je počet vrcholů a E počet hran daného grafu.
Asymptotická časová složitost algoritmu je O(|V| + |E|), kde V je množina vrcholů a E je množina hran grafu.
Prostorová složitost je O(|V| + |E|). Řečeno jinak, prostorová složitost je O(BM), kde B je nejvyšší stupeň větvení stromu a M je nejvyšší délka cesty ve stromě. Tento velký nárok na prostor ve srovnání s nárokem prohledávání do hloubky je důvod, proč je prohledávání do šířky nepraktické pro rozsáhlejší problémy.
Asymptotická složitost: Řazení hran má asymptotickou složitost O(|H| · log |H|), množinový rozklad pak O(|H| · log* |U|), kde log* je velmi pomalu rostoucí inverzní Ackermannova funkce s jedním parametrem. Celková asymptotická složitost Borůvkova-Kruskalova algoritmu je tedy O(|H| · log |H|).
Asymptotická složitost: Počáteční nastavení má asymptotickou složitost O(|U|), získání minimálního prvku z fronty zabere čas O(|U| · log |U|). For cyklus přes všechny sousedy uzlu se provede O(|H|)-krát a zjištění, zda je prvek ve frontě (ke kterému dochází uvnitř tohoto cyklu) trvá O(log |U|). Celková asymptotická složitost Jarníkova-Primova algoritmu je tedy O(|U|) + O(|U| · log |U|) + O(|H| · log |U|) = O(|H| · log |U|).
složitost O(|U|2), při implementaci haldou O(|H|·log|U|)
složitost obecně O(|U|·|H|), pro acyklické grafy lze upravit na O(|U|+|H|) (topologické uspořádání uzlů)
operační složitost O(|U|3), paměťová O(|U|2)
Nech G=(V,E), komponenta súvislosti je maximálna podmnožina , pre ktorú platí, že medzi každými 2 vrcholmi vedie neorientovaná cesta. Ak v celom grafe medzi každými 2 vrcholmi vedie cesta, graf je súvislý (komponenta súvislosti je v tom prípade celý graf).
Všetky komponenty súvislosti môžeme nájsť pomocou prehľadávania do šírky.
Daný je orientovaný graf G=(V,E) spolu s ohodnotením hrán . Sled má dĺžku, ktorá je súčtom jeho hrán:
Cyklus nazývame záporný cyklus práve keď jeho dĺžka .
Definujeme dĺžku najkratšej cesty z u do v:
Hlavné problémy spojené s najkratšími cestami a algoritmy, ktoré sa používajú k ch riešeniu:
Graf musí mať nezáporné ohodnotenie hrán, aby na ňom Dijkstrov algoritmus korektne fungoval. Algoritmus udržuje množinu S vrcholov, pre ktoré sa už vypočítala dĺžka najkratšej cesty. Algoritmus opakovane vyberá vrchol s najkratšou cestou a relaxuje hrany vychádzajúce z u
DIJKSTRA(G,w,s) 1 INICIALIZACIA(G,s) 2 S ← Ø; Q ← V 3 while Q ≠ Ø do 4 u ← (u ∈ Q ∧ d[u] = min{d[x] | x ∈ Q} 5 S ← S ∪ {u} 6 Q ← Q \ {u} 7 for kazdy vrchol v taky, ze (u,v) ∈ H do 8 RELAXACIA(u,v,w) 9 od 10 od
RELAXACIA a INICIALIZACIA sú tie isté procedúry ako v prípade Bellman-Fordovho algoritmu. Zložitosť závisí od spôsobu reprezentácie množiny Q, efektivity výberu prvku u s minimálnou hodnotou d[u] a aktualizácie hodnôt d[v] pre vrcholy susediace s u. Pre pole: , pre Fibonacciho haldu:
Daný je orientovaný graf s ohodnotením hrán bez záporných cyklov. Predpokladajme, že graf je zadaný maticou susednosti rozmerov . Nech je cesta v grafe. Vnútorné vrcholy cesty p sú vrcholy .
Pre ľubovoľnú dvojicu vrcholov uvažujeme všetky cesty z i do j, ktorých vnútorné vrcholy sú množiny , nech p je z nich najkratšia. Floydov-Warshallow algoritmus využíva vzťah medzi touto množinou ciest z i do j a množinou ciest z i do j, ktorých vnútorné vrcholy sú z množiny (dynamické programovanie).
Označme dĺžku najkratšej cesty z i do j s vnútornými vrcholmi z množiny . Platí:
Algoritmus (D je matica najkratších ciest):
(riadok 5 je , nefunguje math v code :( )
FLOYD-WARSHALL(W) 1 D(0) ← W 2 for k=1 to n do 3 for i=1 to n do 4 for j=1 to n do 5 uvedene vyssie 6 od 7 od 8 od 9 return D(n)
Časová zložitosť algoritmu je .
Sieť G=(V,H) je orientovaný graf, ktorého každá hrana má nezápornú kapacitu (priepustnosť) . Ak , kladieme . Predpokladáme, že v sieti sú vyznačené dva vrcholy - zdroj s a cieľ t a že všetky vrcholy grafu ležia na nejakej ceste z s do t.
Tok v sieti G je funkcia spĺňajúca:
Hodnota sa nazýva tok z u do v. Hodnota toku f je (súčet hodnôt vytekajúcich z s). Problém maximálneho toku v sieti je nájsť tok maximálnej hodnoty - používa sa Ford-Fulkersonova metóda.
Ford Fulkersonova metoda 1 inicializuj tok f na 0 2 while existuje zlepsujuca cesta p do 3 zlepsi hodnotu toku na ceste p od 4 return f
Jedná sa o iteratívny algoritmus. Začína s tokom nulovej hodnoty a postupne zvyšuje hodnotu toku. V každej iterácii hľadá tzv. zlepšujúcu cestu z s do t, po ktorej môže zvýšiť hodnotu toku. Existujú rôzne varianty algoritmu podľa spôsobu hľadania zlepšujúcej cesty, jeden z nich je Ford-Fulkersonov algoritmus. Na jeho pochopenie potrebujeme zaviesť pomocné pojmy:
Ford Fulkersonov algoritmus 1 for kazdu hranu (u, v) ∈ H do 2 f[u, v] ← 0; f[v, u] ← 0 3 od 4 while existuje zlepsujuca cesta p do 5 c_f (p) ← min{c_f (u, v) | (u, v) lezı na p} 6 for kazdu hranu (u, v) na p do 7 f[u, v] ← f[u, v] + c_f (p) 8 f[v, u] ← −f[u, v] 9 od 10 od 11 return f
Obrázok, ktorý by to mal všetko objasniť (reziduálna sieť je graf s reziduálnymi kapacitami väčšími ako 0):
Ak v sieti G s celočíselnými kapacitami je |f*| hodnota maximálneho toku, cyklus 4-10 sa vykoná nanajvýš |f*| krát. Zložitosť jednej iterácie je rovná zložitosti nájdenia cesty z s do t a je O(|H|), celková zložitosť je O(|f*|.|H|).
Je daný súvislý neorientovaný graf spolu s ohodnotením hrán (váhovou funkciou) . Množinu nazveme kostrou grafu G, ak je graf súvislý a acyklický.
Definujeme váhu kostry K predpisom:
Minimálna kostra je potom kostra s minimálnou váhou.
Na nájdenie minimálnej kostry sa používajú 2 známe algoritmy: Kruskalov a Primov algoritmus.
Kruskalov algoritmus je príkladom hladového algoritmu. Množina K tvorí les. V každom kroku vyberáme hranu h s minimálnou váhou zo všetkých hrán spájajúcich rôzne komponenty z K.
Implementácia algoritmu využíva štruktúry UNION-FIND. V jednotlivých množinách sú práve vrcholy z rovnakej komponenty vzhľadom ku K.
Kruskal((V,H),w) 1 K ← ∅ 2 foreach v ∈ V do 3 MAKE-SET(v) od //kazdy prvok dame do samostatnej mnoziny 4 Zotried hrany podla w do neklesajucej postupnosti 5 foreach (u, v) ∈ H v tomto poradı do 6 if Find-Set(u) ≠ Find-Set(v) //su z roznych komponent 7 then K ← K ∪ {u, v} //pridaj ich do kostry 8 UNION(u, v) fi od //zjednot mnoziny 9 return K
Inicializácia (riadky 1-4) má zložitost Θ(|V|) + (|H| log |H|). Cyklus 5-8 prebehne |H| krát, celkovo sa teda prevedie Θ(|H|) operácıí Find-Set, Union, čo má zložitosť O(|H|α(|V|)). Celková zložitosť Kruskalovho algoritmu je .
Primov algoritmus je opäť príkladom hladového algoritmu. MnožinaK vždy tvorí jediný strom. Na začiatku zvolíme ľubovoľný vrchol r za koreň a postupne pridávame ďalšie vrcholy, resp. hrany. Tomuto koreňu priradíme ohodnotenie 0, zvyšným ∞. Efektívna implementácia Primovho algoritmu využíva štruktúru Q s operáciami EXTRACT-MIN a DECREASE-KEY.
Primov algoritmus postupne ohodnocuje vrcholy podľa hrán, ktoré do nich vedú,zo štruktúry Q odstráni vrchol, do ktorého vedie minimálna hrana. Uchovávame si pole predchodcov π - rodičov vo vytváranom strome, z ktorého na konci algoritmu vytvoríme kostru.
Celková zložitosť algoritmu je O(|V| log |V| + |H|) ak štruktúru Q implementujeme ako Fibonnaciho haldu.
http://ui.fpf.slu.cz
http://zorro.fme.vutbr.cz
skriptá z Návrhu algoritmov II
http://www.beranr.webzdarma.cz/algoritmy/trideni.html
http://www.sweb.cz/HonzaRug/Delphi/alg.htm
http://users.informatik.uni-halle.de
http://links.math.rpi.edu/applets/appindex/graphtheory.html -užitečný applet, který dokáže simulovat různé algoritmy jako je dijkstra, Bellman-Ford, Kruskal … Grafická ukázka řazení použitím algoritmů – http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html applety mj animuje operace nad haldou Heap, Merge a Quick Sort -- pekne zpracovane
Petr Kott
petr.kott@post.cz
Dusan Katona, ICQ: <426 081 873>
Zkrátil, sjednotil ze 2 otázek a upravil pro tisk(aby byla rozumně vytisknutelná, tj. do 12ti stránek): Marek Babák (50%, ještě budu upravovat)