Žádný efektivní algoritmus na řešení relačních rovnic neexistuje

15.03.2016 17:07 | Redakce Web4Trader | Diskuze

Menší pozdvižení vzbudili ve svých odborných kruzích informatici z přírodovědecké fakulty, kteří se zabývali algoritmy pro výpočet minimálních řešení relačních rovnic. Zjistili totiž, že pro tento problém žádný efektivní algoritmus vlastně neexistuje. Zaskočili tím mnoho autorů, kteří si v minulosti mysleli, že takový algoritmus objevili. Práci Radima Bělohlávka a Eduarda Bartla z katedry informatiky otiskl prestižní oborový časopis IEEE Transactions on Fuzzy Systems.

Foto: Gerd Altmann

 

Algoritmy, tedy teoretické principy řešení problémů, jsou denním chlebem informatiků. Celá řada problémů je však natolik vnitřně složitých, že pro ně žádný algoritmus není. Ne proto, že by na něj dosud nikdo nepřišel, ale protože je matematicky dokázáno, že takový algoritmus prostě nemůže existovat. Počítače je proto nikdy nebudou moci řešit. Další skupinou jsou pak problémy, pro jejichž řešení informatici sice algoritmy našli, ale nejsou efektivní.

Do poslední skupiny podle olomouckých informatiků patří i algoritmy pro nalezení všech minimálních řešení relačních rovnic, tedy rovnic, u nich není neznámou číslo, ale strukturovanější entita – relace neboli vztah. Tuto problematiku odborná obec řeší posledních zhruba 40 let. Odborníci pro ni hledali rychlé algoritmy a byli přesvědčení, že jsou správné. „Přišli jsme na to, že tito autoři se mýlili. Pokud jejich algoritmy fungovaly, byla to shoda náhod. My tvrdíme, že obecný algoritmus, který by fungoval za všech okolností rychle, neexistuje,“ uvedl vedoucí katedry informatiky Radim Bělohlávek. Potvrdil, že někteří informatici přijali jejich zjištění s rozladěním. Pádnost argumentu ale podtrhlo uveřejnění v prestižním časopise, jehož impaktový faktor 8,75 ho řadí na první místo v obou klastrech Web of Science, do kterých je zařazen.

Řešení relačních rovnic je jeden ze základních problémů v oblasti práce s daty, zejména analýzy dat. Využívá se například při návrhu tzv. fuzzy regulátorů. „To jsou algoritmy, které mají za úkol regulovat různé složité procesy. Ve fázi, kdy se regulátor navrhuje, známe podobu vstupů a výstupů. Pak se musí vymyslet, jak to provést, abychom ze zadaných vstupů získali potřebné výstupy. Právě otázka, jak to navrhnout, se dá reformulovat do řeči relačních rovnic. Jediné, co tedy potřebujeme, je vyřešit relační rovnici,“ uvedl Bělohlávek.

Oblasti relačního modelování se olomoučtí informatici věnují dlouhodobě. „Říkali jsme si, že se musíme podívat na zoubek právě těm algoritmům, o kterých se tvrdilo, že jsou rychlé. Dlouho jsme to odkládali, protože jsme si říkali, že je v nich něco divného. Plánovali jsme to možná dva tři roky. Pak nás napadlo podívat se na to z té negativní strany, tedy že rychlý algoritmus možná ani neexistuje. A poměrně jednoduše jsme přišli na to, že to tak opravdu je. Náš technický argument není nijak složitý, šlo jen o správný pohled a uvidět to,“ uzavřel profesor Bělohlávek.

A jak se k tomuto zjištění postaví tradiční technologické firmy působící na tomto poli? Těžko říct, ale asi je to nepotěší.

Zdroj:Žurnál UPOL

Podobná témata
technologie, česká republika, obchodní algoritmus, univerzita palackého, věda a výzkum, databáze

Líbil se vám tento článek?
+0 / -0

Sdílejte článek na sociálních sítích
Odeslat článek e-mailem

Diskuze

V diskuzi zatím není žádný komentář. Buďte první, kdo bude komentovat.

Vstoupit do diskuze


Související články

Airbus plánuje první testy svého létajícího taxi již na letošní rok

Výkonný ředitel Airbus, Tom Enders dnes na technologické konferenci DLD prohlásil, že výrobce letadel se chystá provést první testy svého „samořiditelného létajícího auta“ již na konci tohoto roku.

Chytré hodinky poznají, že onemocníte dřív než vy

Čtení z ruky a okultní diagnóza nemoci na dálku se začínají třást o práci, protože nyní nastupují chytré hodinky.

Chemik Pavel Hobza je opět mezi nejcitovanějšími vědci světa, RCPTM má v seznamu tři zástupce

Regionální centrum pokročilých technologií a materiálů (RCPTM) Univerzity Palackého v Olomouci vstupuje do nového roku hned se třemi svými zástupci v prestižním seznamu nejcitovanějších vědců světa Highly Cited Researchers za rok 2016.

Společnost Alphabet ukončila program vývoje solárních dronů Titan

Divize X společnosti Alphabet (GOOG, GOOGL) ukončila podporu vývojovému programu dronů na solární pohon, které by létaly ve vysokých výškách a umožňovaly by připojení k Internetu.

Ilustrační foto

Valeant Pharmaceuticals zveřejnila pozitivní výsledky fáze 3 studie zaměřené na léčbu lupénky – akcie na premarketu posilují

Akcie farmaceutické firmy Valeant Pharmaceuticals reagovaly na premarketu vzestupem (o 12 %) nejen na zprávu o prodeji vedlejších aktiv společnosti, ale i na zveřejnění výsledků fáze 3 klinické studie zaměřené na léčbu ložiskové psoriázy.

Ilustrační foto

Soukromý sektor nemá zájem na investicích do výzkumu

Spolupráce mezi podnikateli a veřejným výzkumem, tedy vysokými školami a akademickými ústavy, je stále nedostatečná, a to i přesto, že ji podporuje stát.



Čti více

Britskou libru čeká na páru s japonským jenem další výrazné oslabení, tvrdí forex analytici Credit Agricole

Podle forex analytiků Credit Agricole se můžeme na páru GBP/JPY dočkat výraznějšího oslabování, pokles GBP/USD bude spíše omezený.

Gazprom hlásí rekordní vývoz zemního plynu do Německa

Ruská plynárenská společnost Gazprom zvýšila loni vývoz zemního plynu do Německa o deset procent na nový rekord 49,8 miliardy krychlových metrů a překonala dosavadní maximum více než 45 miliard kubíků z roku 2015.

USD/CAD nyní nabízí atraktivní úrovně pro vstup do dlouhé pozice, tvrdí forex analytici TD Bank

Podle valuačního modelu forex analytiků TD Bank je nyní měnový pár USD/CAD mimořádně levný a kanadský dolar bude dále profitovat z možného krátkodobého oslabení amerického dolaru.

Týdenní výhled: 16.-20. ledna; Ekonomický kalendář signalizuje vysokou volatilitu

Americký dolar minulý týden skončil níže oproti všem hlavním měnám, protože prezident USA Donald Trump ve svém projevu neposkytl dostatek informací o svých budoucích činech, jak se od něj očekávalo. Jedinou výjimkou byla britská libra, která dnes ráno překvapila gapem směrem dolů díky spekulacím, že britská premiérka Theresa Mayová bude v úterý naznačovat takzvaný "Hard Brexit".

Britská libra dnes prudce oslabuje. Investoři očekávají tvrdý brexit

Britská libra v dnešním obchodování v Asii zažila bleskový výprodej, takzvaný flash crash, a propadla se na nejnižší hodnoty od října. Forex obchodníci reagovali na spekulace médií, podle nichž britská premiérka Theresa Mayová v úterním projevu signalizuje takzvaný tvrdý brexit.

Cena ropy dnes klesá. Přetrvávají pochybnosti o redukci těžby v zemích OPEC i obavy ze zvýšení produkce v USA

Světové ceny ropy zůstávají na počátku týdne pod tlakem a odpoledne mírně ztrácely. Na ropném trhu přetrvávají pochybnosti, zda velké těžařské země dodrží sliby snižování těžby. Ceny oslabují i kvůli očekávání, že těžba ropy ve Spojených státech letos obnoví růst.

Portál Web4Trader používá cookies s cílem zajistit co možná nejlepší zážitek při návštěvě těchto webových stránek. Dalším užíváním těchto webových stránek vyjadřujete souhlas s umístěním souborů cookies na vašem počítači / zařízení. Více informací naleznete zde.