ÚVOD k BT

Bergrovy tabulky (BT) jsou celkem běžným prostředkem zejména v rámci rozdělení různých duelů nebo turnajů sportovního charakteru na základní dvojice každý s každým, nebo také navíc s odvetami každý s každým.

Z pohledu kombinatoriky jsou základem [u]kombinace druhé třídy z ceku obecného „n“. Zápis podle notace vzorců tabulkových procesorů =COMBIN(n;2)

Model rozšířený s odvetami [u]obsahuje kombinace 2x s tím, že druhá polovina má opačné pořadí členů dvojice[/u]. Z pohledu kombinatoriky se pak jedná o variace bez opakování druhé třídy celku „n“. Zápis variací bez opakování podle notace vzorců tabulkových procesorů =COMBIN(n;2)*FACT(2). Ve skutečnosti také (n)*(n-1).

Existuje i obdoba pro variace s opakováním. Ta se dá vyjádřit nejlépe takto (n)^2. Tato verze je velice zajímavá ale až pro analytickou část která je popsaná v jiné kapitole.

Pro základní pochopení budeme používat jen verzi s kombinacemi. To si ukážeme na příkladech rozboru čísla 11 a 12. Na konci ukážeme i aplikace pro variace bez opakování. Jde například o známý problém „Obchodního cestujícího“.

Tabulka rozkladu na dvojice celku „n“=11 (Berger’s Table)

Sloupce dvojic s přirozenými SIGNATURAMI sloupců (první řádek se znaménkem mínus). Signatura nad sloupcem je číslo které není obsaženo mezi dvojicemi (SYMPTOMY). Schází proto je celkem přirozeným příznakem sloupce. Tuto vlastnost mají pouze LICHÁ ČÍSLA.

Trojice vytvořené z dvojic SIGNATUR vzniknou tak, že se SIGNATURA přiřadí ke každé dvojici (SYMPTOMU) „svého“ sloupce bez znaménka mínus. Stává se tak součástí SYMPTOMU.

Takto jsme získali [u]KONSTRUOVANÝ VÝBĚR[/u] unikátních trojic z celku „n“=11. V této podobě trojic je každá různá dvojice obsažena 3x. V dalších pasážích ukážeme, že je to 1/3 všech trojic z celku 11.

Tyto trojice mají několik nepříjemných vlastností. Především čísla zkombinovaná do trojic nejsou uspořádaná vzestupně zleva doprava tak jak je příznačné pro kombinace. Další spíše praktickou nepříjemností je textový tvar vytvořený za účelem jednotného tvaru trojice. Tedy čísla menší nežli 10 jsou jednociferná a proto jim přidáváme nulu na začátek. Mezi jednotlivými čísly je pomlčka (-) která odděluje jednotlivá čísla.

[u]Tabulka rozkladu na dvojice celku „n“=12 (Berger’s Table)[/u]

Sloupce jsou bez přirozených SIGNATUR protože každý sloupec obsahuje všechna čísla „n“. Na signaturu přirozeného typu se znaménkem mínus se tedy nedostaneme. Přes to SIGNATURY (-) přidělíme jako pořadí sloupců. Důvodem je srovnání podob mezi [u]lichým číslem které označíme jako (n)[/u] a [u]sudým číslem (n+1)[/u]. V tomto případě tedy porovnáváme vlastnosti rozložených množin dvojic čísel 11 a 12. Rozšířený rozklad na trojice bez „odvety“.

Takto jsme získali KONSTRUOVANÝ VÝBĚR unikátních trojic z celku „n“=12. V této podobě trojic je „téměř“ každá různá dvojice obsažena 3x.

V případě sudých čísel je ještě mimo stejných nepříjemných vlastností navíc skutečnost, že přidělená číselná signatura vytvoří v každém sloupci jednu z trojic která není trojicí kombinace, ale variace s opakováním. Nyní je to záměrně trojice v prvním řádku. Pozorně si prohlédněte oba systémy trojic jak lichého, tak sudého počtu. Zjistíte že trojice jsou ve sloupcích úplně shodné až na to že sudé sloupce mají 1. řádek navíc a není to trojice typická pro kombinace. Z toho plyne první závěr : [u]Ze systému lichého (n) vytvoříme systém sudého (n+1) přidáním prvního řádku typu variace s opakováním v symbolickém tvaru AAX, BBX, CCX,,……(tyto tvary obsahují dvojice AX, BX, CX pouze 2x)[/u].

---

KOMENTÁŘ VÝSLEDKU POROVNÁNÍ

• Rozklady na dvojice BT pro liché (n) a sudé (n+1) jsou si podobné ve smyslu konstrukce a obsahu :
  • • [u]A1 : Pro konstrukce a analýzy[/u] vyplyne, že sudé číslo (n+1) nad lichým (n) se řídí podle lichého (n).
    • [u]A2 : Pro konstrukce a analýzy[/u] vyplyne, že sudé číslo (n-1) pod lichým (n) se řídí podle lichého (n-2).
    • [u]B1 : Pro obecné matematické analýzy[/u] je typickým elementárním problémem rozložení na poloviny. Přestože z ukázky to zatím není patrné má toto porovnání hodnotu matematického důkazu zásadního charakteru. To bude vysvětleno v rámci mnoha různých aplikací. Například faktorizace součinů 2 čísel (obecně) i speciálně prvočísel. Jinou problematikou je hledání posloupností (X…Y) = X*Y [X<Y] = Y^2 – Combin(X,2) a podobně.
    • [u]B2 : Z pohledu matematické analýzy[/u] je nejdůležitější skutečností že kombinace 2. třídy z celku „n“ – tedy C(n,2) jsou také rovny výrazu 1/2(n^2-n). BEZ ROZDÍLU ZDA JDE O LICHÁ, NEBO SUDÁ ČÍSLA. [Combin(n,2) = 1/2(n^2-n)]. 

   

• Přímý význam pro nejdůležitější aplikace :
  • [u]A : Určení podle jména autora původní metody[/u] – rozdělování duelů pro sportovní a podobné příležitosti z pohledu obecného „n“. Nejčastěji pořádání turnajů v šachu, tenisu, rozdělení pohárových kol v různých sportech a podobně.
  • [u]B : Oblast kryptologie a kryptoanalýzy[/u]. Zejména přímá šifrovací metoda kdy se provede substituce alfabetických znaků za číselné výrazy. Takovou šifru jsem popsal v rozšíření jako určitý typ šifer PNBT+specifikace. PN(Partition Numerorum) a BT(Berger‘s Table). Princip je v tom, že ta nejprimitivnější metoda tohoto systému spočívá v SIGNATURÁCH které jsou reprezentovány dvojicemi ostatních znaků (SYMPTOMY) – unikátně. Je možné na princip PNBT nahlížet také jako na zdroj pro šifry AES (Advanced Encryption Standard). Více ve specializované kapitole.
    
  • [u]C : Hledání optimální trasy v rámci logistiky[/u] – dopravní, pracovních procesů, nebo také v rámci hledání nejvhodnější relaci poměru směsí, slitin a další. Zde hraje BT sekundární úlohu v rámci vyšších systémů. Princip je v tom, že místo signatur použijeme přímo množství a dvojice už je přímo součtem, rozdílem, součinem, podílem nebo i mocninou, odmocninou, derivací, a podobně – obecně SYMPTOMY jsou vztahem SIGNATURNÍCH hodnot.
  • [u]D : Rozšíření systémů dvojic na unikátní trojice už nepatří přímo do pojmové kategorie „Berger‘s Table“[/u] ale je to celkem snadno pochopitelná záležitost rozboru do trojic a dá se z ní přímo vycházet. Podobně vyšší k- tice. BT je typem základního nástroje KONSTRUKČNÍ KOMBINATORIKY.
  • [u]E : Různé aplikační rozbory, nebo konstrukce.[/u] V mnoha případech je potřeba provést analýzu nejvhodnějšího strukturálního uspořádání. Tomu budeme říkat FRAGMENTACE. Efektivní nástroj tohoto typu nabízí až další kapitola ZÁKLADEM VŠEHO JSOU DVOJICE, ale základem je pochopení právě významu BT.

• Přímý význam pro vlastní metodiku a koncepci :
  • [u]A : Uvedené téma rozkladu na dvojice ve formě BT považuji za základní dogma[/u], přestože já osobně jsem začínal úplně jinak. Toto téma má charakter praktického a celkem dobře známého problému. Existují různá řešení kromě těch které používám já jako autor. Což znamená, že existují různá řešení která lze používat ke stejnému účelu. Spíš jde o to k čemu je rozklad potřebný a jaký má mít aplikační efekt. Řídím se tedy určitým druhem analýz které vychází z původních intuitivních metod.
  • B : Mám velmi tvrdě ověřeno, že numerické analýzy ve formě operací s kombinacemi, variacemi a nakonec i variacemi s opakováním často selžou na maličkosti. Na jednu maličkost už jsme narazili. Tedy na problematiku sudých a lichých čísel v zadání rozkladu. Uvedu ale celkem známý problém Latinských čtverců. Jedná se o „n“=36, tedy o čtverec 6×6. Čtverec 6×6 vykazuje perfektní poměry dělitelnosti a teoreticky by s ním neměl být problém – opak je pravdou. Ukážeme si to dále.
  • C : Z obecného pohledu je práce s dvojicemi nejdůležitější právě pro část praktické konstrukce. Ale když selhává analýza je to jediná možnost jak analýzu ověřit. Teprve z toho lze dovodit analytická pravidla tedy predikci vzorcem, konstruktory a algoritmy. Takže pokud budeme uvádět podstatné věci (vyjádřeny většinou větou) mělo by být pochopeno, že se jedná o lemma ve více smyslech významu.
  • D : Musím ač nerad také konstatovat, nebo se velmi často přiznat ke skutečnosti, že dokázaný efekt nebo predikát a podobně – není obecným výrokem z jednoduchého důvodu. K důkazu globální validity nemám prostředky. Půjde tedy velmi často o popisy které problematiku spíše nastavují a dokazují jen to, že by řešení mohlo být validně dokázáno. Velmi mnoho záležitostí totiž znemožňuje technicky podat nezvratný důkaz. Není to v silách jednoho člověka. Téměř každé téma vede na teorii čísel a další matematické disciplíny. Myslím že tak je to s každým novým oborem. Otevře se pandořina skříňka a jeden důkaz vyvolá celou sadu nových otázek a často nečekaných problémů.
  • E : Prakticky je tato práce motivována axiomatizací kombinatoriky. Uvedená práce by měla být propojením mezi klasickou kombinatorikou z konce 19. století a mimo jiného také mezi teorií množin bez které se axiomatizace neobejde. Ale nejedná se pouze o toto určení. Kombinatorika nemá v rámci matematiky správné docenění významu.
    
  • F : Dál pokračujeme aplikacemi na uvedené téma Berger‘s Table“ – výše přislíbené nebo naznačené.

VÝZNAM SUBSTITUCE PRO RŮZNÉ ÚČELY

Nejprve si ukážeme názorně co je myšlenou tou SUBSTITUCÍ. Substituce je ve smyslu této práce také základním pracovním nástrojem. Běžně je však tento pojem užíván například v oblasti kryptologie. Této oblasti se nevyhýbáme ani v této práci, ale vždy půjde o rozšířený význam.

Ukážeme si to na dříve uvedených tabulkách sytémů BT(11,3) a BT(12,3). Tedy na trojicích vytvořených z původních tabulek dvojic rozšířením na trojice. Nyní tedy použijeme substituci pouze v rámci signatur. Část symptomů – konkrétně původní číselný význam zachováme.

Můžeme si představit například rozdělení pracovních úkolů mezi kolektiv 11 osob (pracovníků, studentů, překladatelů, počítačů apod.) kteří mohou zpracovávat duplicitně 11, nebo 12 témat. Zde je vidět, že signatura substitucí čísla za alfabetický znak (jméno a podobně) vytvoří ze systému sudého čísla plnohodnotný ekvivalent k lichému rozdělení.

Nyní už je tady tématem BT distribuce a redistribuce obecného typu.

Tento systém můžeme použít i opačně. Dvojice (nyní unikátní číselné symptomy) jsou jako dvojice pravidelně rozděleny do 11-ti sloupců. Dvojic je ale mnohem více nežli Signatur. V našem případě buď 55 pro „n=11“, nebo 66 pro „n=12“. To znamená že každá dvojice může být nahrazena jiným tématem buď z celku 55 nebo 66 a tyto jsou pravidelně rozděleny mezi 11 Signatur (lidí, strojů apod.). Tedy typický příklad paralelního rozdělení práce.

Toto „paralelní rozdělení“ není v uceleném výčtu možností. Můžeme si představit že řádky v každém sloupci reprezentují pracovní skupinu která má signaturu alfabetickým výrazem. Každý skupina (5, nebo 6 lidí – strojů ap.) pak řeší symptomatické dvojice jako úlohy s modulo „n“ (buď 11. nebo 12).

Řekněme pro BT(11) = 11 skupin po 5-ti řádcích (lidé stroje apod.) Sloupce A[1..5], B[6..10], …..K[51..55], nebo A[1..10], B[11..20], …..K[101..110]. Podobně pro BT(12) A[1..6], B[7..12], …..K[61..66], nebo A[1..12], B[13..24], …..K[120..132]. A v tomto duchu ještě můžeme použít například GCD (největšího společného dělitele), nebo LCM (nejmenší společný násobek). 

Ještě nejsme u konce. Například pro BT(11) v rámci trojic se dají stejné jednice rozlišovat řádkem. Takže Původní signatura se stane také symptomem. Potom nastává možnost vázat počet variant každého jednoho symptomu na index (sloupec + řádek). Potom každý různý symptom dostává 5 + 10 významů – řekněme úloh. To je celkem 11 x 15 různých úloh tedy 165 úloh rozdělených do 11-ti, nebo 55 celků (skupin, nebo jednotlivých strojů. Tentýž postup pro BT(12) = 198 (3×66).

Samozřejmě že se nejedná o konečný výčet možností. Jenom si shrneme čísla, která jsme v souvislosti s popsanými postupy doposud uvedli. Je to zlomek z toho co se dá vše analyticky použít.

Takže jen orientačně čísla pro BT(11,3) : (5, 10, 11, 55, 110, 165) a podobně BT(12,3) : (6, 12, 66, 132, 198).

Celkem musíme vyjádřit vzhledem k „podobnosti mezi BT(11) a BT(12) čísla v posloupnosti (5, 6, 10, 11, 12, 55, 66, 110, 132, 165, 198). Není to interval uzavřený ani zleva ani zprava.

Uzavření zprava konverguje k nekonečnu dík GCD a LCM (tím se dostáváme k intervalům prvočíselných modulo 5 a 11).

Uzavření zleva musíme rozšířit ještě o logickou jedničku (1 systém, správně množina), 2 (jak jinak jde o dvojice) a trojku. Tu jsme sice už používali pro rozšíření dvojic na trojice, ale hraje úlohu v distribuci úloh. Celkem je jasné že snadno spočítáme dělitelnost dvojic ve trojicích. Ta je pro BT(11,3) dána jako (55*3)/3 = 55 a pro BT(12,3) jako (66*3)/3 = 66. Tuto představu si musíme ukázat názorně nejlépe pro BT(11,3) :

Jedná se o celkem banální ale důležitou skutečnost možnosti rozkladu. Trojice jsme vytvořili přidáním signatury k symptomům (udělali jsme symptomatické trojice). Okamžitě jsme získali trojnásobek všech dvojic.

Výsledkem v substituci která se vyskytuje zcela systematicky rozložená do různých sloupců (o řádcích to neplatí). Můžeme tedy například na 55 elementů (lidí, strojů apod.) rozdělit například 165 úloh. Konkrétně na každý jeden element 6 úloh, nebo opačně 165 úloh na 6 elementů po 55-ti úlohách.

Nyní si představíme snadno Berger‘s Table nad systémem dvojic. Například z původního BT(11) vznikne 55 dvojic které postavíme do BT(55) se signaturou sloupce – nejlépe jako modulo 11 = 165.

Z toho vznikne systém čtveřic a sloupce budou označeny signaturou – rozdělení do další podmnožiny.

Respektive snadno navíc přiřadíme číslo sloupce a získáme pěti-čísla strukturovaná ve sloupcích po 1/2(n-1) tedy 27 řádků. Vždy 5 sloupců (135 řádků) bude pod jiným násobkem čísla 5 (princip podíl – modulo). To jsme už ale daleko.

Uvedeme si pouze, že takový postup je zajímavější jako rekurzivní rozklad – to jsme ale daleko ve specializované matematické oblasti.jedná se posloupnosti kterými se zabývá zejména The On-Line Encyclopedia of Integer Sequences®

PROBLEMATIKA ŘAZENÍ RESPEKTIVE TŘÍDĚNÍ v rámci BT.

Zásadní skutečností je, že BT obsahuje ve své podstatě kombinace 2. třídy. Ale může obsahovat také variace bez opakování 2. třídy z celku „n“. Variace bez opakování mají opačné pořadí členů dvojic. Ale tuto skutečnost popisovanou původně autorem jako odvetu pro tento výklad vyloučíme. Jde nám o ty kombinace, které mají typické pořadí vzestupně řazených dvojic.

To je dáno algoritmem a ten který osobně používám k tomuto účelu. Generuje striktně kombinace ze striktně seřazených signatur. Pro šifrování toto neplatí – naopak síla šifry PNBT je v možnosti řadit signatury do Faktoriál(n) podob.

Můžeme si této skutečnosti povšimnout. Uvedená tabulka byla vygenerována generátorem v němž je motorem iterativní algoritmus. Aby to bylo zřejmé ukážeme si tuto tabulku s porovnávacím operátorem (<).

Ale to co platí pro řazení v rámci dvojice neplatí v rámci sloupce. Toto jak uvádí tabulka je neupravený výstup z generátoru a má specifický význam. Ten si zvýrazníme barvou jako přechod. Přechod a tím pádem řazení dvojic ve sloupci je důležitý pro pochopení, že toto je řízeno potřebou.

Například pro šifrování použijeme plný rozsah faktoriálu(5) = 120 možností pro každý sloupec. Toto se profiluje jako zvýšení obtížnosti šifer. Někdy potřebujeme vysloveně řazení podle generátoru a jindy zase podle typického vzestupného systému. Jde tedy o účel.

ÚČELY ŘAZENÍ

Nyní se budeme okrajově zabývat problematikou řazení. Toto bývá také často uváděno ač nesprávně také jako třídění.

Podle barev pozadí buněk se nám vykresluje postup algoritmu. Je to symetrická struktura která je typická právě pro určitý typ algoritmu a řazení symptomů – samozřejmě ve formě čísel která mohou vyjádřit relaci x<y. Toto je velice výhodné pro ŘADÍCÍ ALGORITMY. Připomeneme že lichý počet sloupců mají jak sudá, tak samozřejmě lichá čísla. Přes to si značně usnadníme práci když v případě sudých čísel jednou projedeme pole hodnot Bubble Sortem.

Ale u velkých polí jde o fragmentaci celku „n“ do dílů. Ideálním rozdělením je druhá odmocnina celku „n“ – zápis SQRT(n). Proto je možnost volby rozčlenit na nejbližší lichý díl a zbytek uděláme bezpečně Bubble Sortem. Tento už před-připraví také celé pole před rozdělením a navíc otestuje zda není pole již setříděné.

Úvodní test Bubble Sortem by se měl z tohoto důvodu udělat vždy pro jistotu jako první krok. Ale důvodem může být také zjištění počtu řazených elementů, nebo seřazené úseky které lze okamžitě považovat za přetříděné a obrazně řečeno „swapovat do přesného místa“. Tomuto tématu tady ŘAZENÍ se bude věnovat víc do hloubky protože je technicky velice zajímavý.

Barva pozadí růžová vytváří typický „trychtýř“ a typické je sestupné třídění až k rozhraní světle modré barvy prostřední sloupec je pouze růžový. Řazení ve sloupci je podle prefixu sestupné.

Barva pozadí Světle modrá tvoří typický opak tvaru trychtýře („mísu“) ale je také „trychtýřem“ protože má „díru uprostřed“. Také ve sloupci opačně řadí podle prefixu (vzestupně).

Postup je následující : setřídíme dvojice podle PROSTŘEDNÍ POLOHY SIGNATURY do dvojic (PODLE „PIVOTa“). Tím získáme výhodu kombinací. Na první pozici je menší číslo a hned můžeme usoudit kam opravdu signatura (PIVOT) patří ve smyslu sloupce. Podle prvního čísla ve dvojici (symptomu) zjistíme ke kterému sloupci se dá skutečná poloha SIGNATURY přiřadit NEJSNADNĚJI. (Tady pozor na skutečnost – nevytváříme plnou tabulku BT nad množinou tříděných dat. Vytvoříme jen pivota z prostředního elementu pole a dvojice tvoříme systémem číslo(-1) a (+1) = dvojice + elementární krok (<). Následně (-2) & (+2) & (<) a tak dál. Nemusím asi uvádět, že tyto operace provádíme jen nad lichým počtem sloupců které mají přirozenou signaturu a jiné nežli liché počty sloupců neexistují 🙂

Když se pozorně podíváme tak zjistíme že PIVOT (Signatura) v růžovém trychtýři je vždy větší nežli první číslo dvojice (symptomu). Například ve druhém sloupci je signatura přesně mezi čísly dvojice 01(2)03, podobně třetí sloupec 02(3)04 + 01(3)05 a tak dál.

Vzestupné řazení v rámci celého sloupce mají oba krajní sloupce. Zde je ukazatelem první i druhé číslo ze symptomu. Pokud je signatura menší nežli první číslo prvního symptomu jde o signaturu jedničky, pokud je větší nežli druhé číslo dvojice je to největší číslo.

Ovšem úplný popis to není – jen náznak. Můžeme testovat také od prostředního „pivota“ mezi dvojicemi – nejprve o jednu dvojici nahoru a o jednu dolu. V našem případě už stačí otestovat v následném kroku jedinou hodnotu buď první nebo poslední.

Poznámka : Připomeneme si jenom, že [u]lichý počet symptomů[/u] „n“ může mít jak lichý počet dvojic, tak sudý počet dvojic. Například číslo 17 má sudý počet (symptomů) – (17-1)/2 = 8 dvojic. Naopak sudé číslo 10 má lichý počet dvojic (symptomů) ve sloupci. Zde se jedná o jakési vyrovnávání skutečnosti, že počet sloupců BT je vždy lichý.

V takovém případě kdy má sloupec sudý počet symptomů začneme místo jedné operace (<) nad dvojicí (pivotem) hned 6 operací nad dvěma středními „pivoty“X a Y (dvě dvojice). Metoda je jednoduchá místo jediné operace (<) provedeme 6*(<) nad X,Y [a<b<c<d] potom platí pro dvojice X[a<b]<Y[c<d].

Následně pokračovat buď po jedné dvojici nebo stejně po dvou dvojicích. Pro obecně sudé počty dvojic bychom následně porovnali obě podmnožiny X < Y podle prvních členů dvojic. Velkou výhodou je při tom celočíselný násobek. Tato metoda patří mezi kombinatorické metody podobné s proslaveným krokem Bubble Sortu. Musíme se na „plný Bubble Sort“ dívat jako na počet operací = Combin(n,2) – nejde tedy o kvadratickou skutečnost počtu kroků. Kvadratickou skutečnost (asymptotická náročnost) z tohoto dělá nepřesně dvojí možnost výsledku.

Konkrétně buď x<=y, nebo x>y Doslova jde tedy o ekvivalent V(n,2) = n^2 – n. Platí tedy že počet kroků pro 2p = 2(počet operací n), ale už při systému 3p platí jiný počet. To objasníme ve specializované kapitole.

ÚČELY VYHLEDÁVÁNÍ

Toto je jiná problematika nežli ŘAZENÍ. Jedná se o algoritmy k prohledávání struktur – často uváděné pod pojmem „stromy“. Struktury ve kterých se prohledávají hodnoty mívají charakter řazených seznamů se známou strukturou. Praxe bývá jiná. Prohledávají se sice objektově známé struktury ale prakticky bez výjimky nesymterické – dané implicitní skutečností. BT tohle může změnit velmi snadno na symetrické sytémy s minimální asymptotickou náročností.

Problematika je jen naznačena, protože prakticky se prohledávají binární struktury. Ale i to umí BT i když si musíme pomocí nestandardně – jiným čtením binárních zápisů. Toto bude popsáno také v jiné kapitole (nemohu stále odbočovat na detaily).

Tabulka je podobná s tabulkami výše uvedenými, ale má své specifické rysy. Sloupce tabulky jsou nyní setříděny vzestupně podle prefixů ve sloupci.

Nyní se díváme na logické řazení lexikálního typu. Tedy jak ve smyslu dvojic (kombinace), tak ve smyslu řádků ve sloupcích. Je to určitý typ úpravy nebo fragmentace která usnadňuje vyhledávání podle pozice prvního čísla ve dvojici. Toto uspořádání stabilizuje asymptotickou složitost prohledávání.

Velmi snadno se prohledává výraz tím, že se okamžitě vyloučí sloupec se shodnou signaturou (tedy n-1) sloupců.

Podle pořadí signatury se prohledává přednostně ve sloupcích které jsou od prostředního „pivota“ menší nebo větší. Znamená to distanc vlevo, nebo vpravo. Jak ve smyslu sloupců podle signatur, tak ve smyslu pořadí ve dvojici.

V každém sloupci v rámci dvojic se vyskytuje hledané číslo výlučně 1x. Jakmile tedy hledaný prefix nemá správný sufix, okamžitě se přechází na hledání vedlejšího sloupce. [prefix = první číslo symptomu] a [sufix = druhé číslo symptomu].

Algoritmus vyhledávání má potom velmi nízkou asymptotickou složitost. Toto si ukážeme docela názorně. Jsou to záležitosti více či méně informatického typu, ale myslím že důležité.

Ukázky pro pochopení asymptotické složitosti vyhledávání pomocí BT :

Ačkoliv je to pro oči „zmatečné“ je to problém velmi dobře enumerovatelný. Tento problém si vysvětlíme na dvou pojmech. Jedná se o náhled na to jak se prefixy a sufixy rozdělují podle sloupců.

Druhý problém je právě dán realizací vyhledávání přímo ve sloupci který můžeme identifikovat ve smyslu pozice. Jedná se pojem řazené seznamy u kterých známe pojem zda hledat „zleva“ nebo „zprava“ a tím pádem víme jakou má hledaná signatura šanci že bude prefixem, nebo sufixem.

Ta může být v obecném případě od prefix/sufix [0/(n), 1/(n-1), … x/(n-x),… (n)/0]. Ve skutečnosti se hledá dvojice, takže když narazíme na správný prefix, nebo sufix a nesprávný pár – okamžitě přejdeme do dalšího sloupce. Je evidentní, že v každém sloupci je každá signatura pouze 1x. Dá se předpokládat, že nalezení hledaného páru bude cca ½^2 = ¼ z celku (n-1)

Podobné „problémy“ a „výhody“ jsou také pro případy systémů které řadí pole neznámých hodnot. To už ale přímo do tématu BT nepatří. Uvedeme si pouze, že se najde poziční střed (pivot), nebo dvojice a složí se 1 sloupec. Hned při skládání se dá setřídit na prefix < sufix. Následně se sloupec seřadí podle prefixů. Zde musím upozornit že podobné metody už existují. Pouze neznají pravidla pro rozpad podle generátoru (viz barevné schema které staví na poměru počtu vzestupného a sestupného třídění).

Mimo toho existují v rámci kombinatoriky mnohem lepší metody pro extrémně velké objemy řazených prvků. Princip je v ideálních dílech sqrt(n).

Z tabulek je zřetelné, že nejde o žádný náhodný ani složitý jev. Je možné snadno předvídat kolik má které číslo jako signatur prefixů a sufixů.

Druhý problém je právě dán realizací vyhledávání přímo ve sloupci který můžeme identifikovat ve smyslu pozice. Jedná se pojem řazené seznamy u kterých známe pojem zda hledat „zleva“ nebo „zprava“ a tím pádem víme jakou má hledaná signatura šanci že bude prefixem, nebo sufixem.

Ta může být v obecném případě od prefix/sufix [0/(n), 1/(n-1), … x/(n-x),… (n)/0]. Ve skutečnosti se hledá dvojice, takže když narazíme na správný prefix, nebo sufix a nesprávný pár – okamžitě přejdeme do dalšího sloupce. Je evidentní, že v každém sloupci je každá signatura pouze 1x. Dá se předpokládat, že nalezení hledaného páru bude cca (½)^2 = ¼ z celku (n-1) operací x 2. nejméně však pod logaritmickou náročností ostatních metod, respektive až pod hodnotou (n)^1.

Přes to by Berger‘s Table nebyla bez odvet úplná. Takže si jako poslední téma ukážeme Dvojnásobnou BT(11) která už obsahuje odvety. Na této pak vysvětlíme například možnost použití pro řešení logistických úloh, nebo známého problému „obchodního cestujícího“.

NA ZÁVĚR JEN PRO ÚPLNOST

Ukážeme si úplnou tabulku BT(11) včetně odvet, tedy v relaci variace bez opakování. V(11,2) :

Vidíme zrcadlové řazení „odvet“ vzhledem ke kombinacím. Obě tabulky dohromady reprezentují množství podle vzorce variací bez opakování V(11.2) = přesně 11*10 symptomů. Tedy dvojnásobek kombinací. Pokud bychom signatury chápali místo (-No) jak 2(No) šlo by o variace s opakováním 2. třídy celku „n“.

Naznačené aplikace pro logistiku – respektive problém obchodního cestujícího.

LEGENDA :

J→G To je jediný směr binární 01 (příklad sloupec C a I), nebo binární 10 (příklad E, H, K)

D→K Neexistující směr binární 00 = příklad ve sloupci B

A→C oba směry C→A Značíme binárně 11

V praxi bychom místo A→B uváděli jako dvojice dvojic : [ Latitude(a), Longitude(a) ] → [ Latitude(b), Longitude(b) ]. Dokonce by bylo vhodnější přídat ještě nadmořskou výšku (altitude).

Obchodní cestující sečte délky trasy a stejně dispečer – tím určí nejlepší cestu. Když ji nenajde použije se BruteForce Factorial(11) což je celkem 39,916.800 možností. Teprve potom by bylo možné určit kolik různých řešení existuje, a které je nelepší, nebo potvrdit skutečnost že řešení neexistuje.

K těmto problematikám konkrétních úloh můžeme použít přímo množinu faktoriál s tím že dosazujeme přímo jen existující dvojice ve formě souřadnic samozřejmě jako stochastickou pomůcku. Pokud je vyžadován například návrat po jiné trase a ukončení v místě startu, lze použít BT jako stochastickou metodu přibližně takto : Signatura = vstup i výstup. Testujeme v cyklu součty vzdáleností prefixů + poslední dvojice.

Pokračujeme sufixy až na signaturu. Zde se nabízí nejen výše popsané BruteForce, ale vyhodnocení vektorů. Je zřejmé že vektory prefixů by měly být určeny jako tenzor proti kterému stojí tenzor sufixů. Je typickým znakem, že cesta tam a návrat po stejné trase je stejným jen opačným tenzorem. Jejich rozdíl je nula. Proto cesty po nestejných trasách mají rozdíl tenzorů nenulový. Čím menší rozdíl je, tím lepší řešení. Je ale nutné přistupovat k množině prefixů a sufixů jako k „n“ – tici rovnou 1/2(n), nebo 1/2(n-1).

Proto bychom předchozí tabulku definovali přibližně jako „transponovanou“. Ale místo metody faktoriál použijeme metodu rozkladu na poloviny. Ta je nejlepší pro stejné poloviny, ale také pro nestejné poloviny [1/2(n) proti 1/2(2+1)] – tedy v rámci sudého počtu symptomů kde není přirozená signatura. Mimo toho Lze předpokládat potřebu testovat celou 2. třídu PN (Partition Numerorum ve dvou skupinách). PN(11,2) = [(1+10), (2+9), (3+8), (4+7), (5+6)]. K této metodě musíme podat vysvětlení názorně :

Tento postup nebudeme blíž komentovat. Pokud by existovala potřeba variací místo kombinací, byl by ve vzorci místo operátoru „=“ použit operátor pro součin variací bez opakování (fakticky jde o součiny faktoriálů obou členů). Pokud by bylo potřeba i operací s opakováním (tam i zpět po stejné trase) potom by šlo místo o třídy o exponenty. Tím že používáme pouze kombinace – dostáváme se do úrovně aproximací a také stochastických postupů.

Nesmíme zapomínat že můžeme používat klasické číselné řešení, nebo lépe řešení tenzory které by se více realisticky přiblížily k volbě optimálních cest – to je dáno samozřejmě nadmořskou výškou pro každou signaturu (longitude, latitude, altitude).

Příjemnou zábavu Petr Neudek