Superpočítání pro průmysl www.it4i.cz

Metody diskrétní matematiky

Rozvoj diskrétní matematiky jde od druhé poloviny minulého století ruku v ruce s rozvojem výpočetní techniky. Mezi klasické a dobře známé problémy patří hledání nejkratších cest, hledání maximálních toků v sítích, úloha obchodního cestujícího, sestavení rozvrhů nebo optimalizace křižovatek.

Klíčovým problémem není jen sestavení algoritmu, který úlohu vyřeší, ale především nalezení takového algoritmu, který úlohu vyřeší rychle. Hledání nejkratší cesty mezi dvěma uzly sítě a nalezení nejkratší trasy obchodního cestujícího přes všechny uzly sítě jsou úlohy na první pohled velmi podobné, je však zásadní rozdíl ve složitosti řešení těchto úloh. Zatímco pro nalezení nejkratší cesty mezi dvěma uzly existují algoritmy, jejich složitost roste lineárně s počtem hran (cest) sítě, tak úloha obchodního cestujícího spadá mezi NP úplné problémy. Žádný algoritmus s polynomiální (a už vůbec ne lineární) složitostí není pro řešení této úlohy znám!

Protože se s úlohami, které spadají do diskrétní matematiky, setkáváme v oblasti IT na každém kroku, je nutno pečlivě volit vhodné metody a často i formulaci dílčích problémů tak, aby složitost řešení nepřesáhla rozumnou hranici.

Optimální rozložení výpočtu

Jednou z optimalizačních úloh řešených elegantně metodami diskrétní matematiky je rozložení velkých výpočetních úloh na mnohajádrovém výpočetním clusteru tak, aby byla optimálně rozložena jak početní, tak paměťová náročnost jednotlivých procesů. S využitím technik teorie grafů (rozklady kompletních grafů na kompletní podgrafy) a teorie čísel se podařilo navrhnout takové rozložení výpočtu, kdy jsou nejen jednotlivé výpočetní uzly zatíženy rovnoměrně, ale současně části výpočtu pracují s pečlivě vybranými oddělenými částmi vstupních dat, přičemž každá část rozsáhlých vstupních dat je využívána jen jediným procesem. Tím se daří maximálně vyžít paměť jednotlivých uzlů a vyřešit větší úlohy, než je při jiném uspořádání dat možné.

Dosažené dělení je pro vybrané počty N uzlů v jistém smyslu dokonalé a již nemůže být překonáno. V současné době se věnujeme hledání optimálního rozložení i pro další hodnoty N.

Spravedlivé sportovní turnaje

Ve sportovních turnajích se často hrají různé systémy. Hráčům jsou pořadová čísla přidělována losem, který někdy závisí a někdy nezávisí na kvalitě hráče nebo týmu. Některé výsledky losování pak znamenají různou obtížnost a losování nemusí být pro každý tým stejně spravedlivé.

Můžeme však navrhnout takové hrací systémy, které zaručují přibližně stejnou obtížnost turnaje pro každý tým. Taková hrací schémata modelujeme pomocí grafů a obtížnost pomocí ohodnocení a vah v grafech. Věnujeme se intenzivně jednak návrhům spravedlivých hracích schémat a dále zobecněním, která stanovují obtížnější podmínky pro lepší týmy a lehčí podmínky pro slabší týmy. Takové turnaje jsou divácky atraktivnější, neboť se můžeme těšit na zajímavé zápasy během celého turnaje.

Faktorizace kompletních grafů

Od 80. let minulého století je zkoumán problém rozkladu kompletních grafů na isomorfní kostry. Zatímco pro kompletní bipartitní grafy je úloha zcela vyřešena, pro kompletní grafy je úplné řešení v nedohlednu. Přesto se podařilo klasifikovat vybrané třídy grafů a ukázat řadu překvapivých dílčích výsledků, které obtížnost úlohy ospravedlňují.

Zajímavé je, že snadněji se daří najít konstrukce rozkladů pro “velké grafy” zatímco pro “malé grafy” se spoléháme na počítačové řešení. Bohužel složitost úlohy roste exponenciálně s velikostí grafu a již pro grafy na 14 vrcholech se jedná o výpočet, který i přes řadu zjednodušení a triků klade obrovské nároky na výpočet. V současné době vyvíjíme a vylepšujeme paralelní software, který umí hrubou silou hledat rozklady kompletních grafů na isomorfní podgrafy.

Partneři