Žá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
Líbil se vám tento článek?
+0 / -0
Odeslat článek e-mailem
Diskuze
Vstoupit do diskuze
V diskuzi zatím není žádný komentář. Buďte první, kdo bude komentovat.


Související články

Slováci chtějí vyrábět nová létající auta

Nový model létajícího auta představila dnes na světové výstavě Top Marques v Monaku slovenská společnost AeroMobil.

Adidas začne s prodejem speciálních bot Futurecraft 4D ještě letos

Společnost Adidas AG uvedla, že v druhém pololetí letošního roku vyrobí na pět tisíc párů nových superbot Futurecraft 4D s mezipodešví, vytištěnou právě tak jedinečnou 3D tiskárnou.

FDA schválila software Mazoru pro léčbu deformace páteře, akcie vzrostly o 4 %

Akcie Mazor Robotics (NASDAQ:MZOR) před zahájením obchodování vzrostly o 4 % v reakci na oznámení, že americký Úřad pro kontrolu léčiv (FDA) schválil software Mazor X Align pro chirurgickou platformu Mazor X Surgical Assurance Platform.

Zajímají Vás investice do umělé inteligence? Nakupujte tyto akcie

Experti se vzácně shodují v názoru, že umělá inteligence v příštích letech pronikne do celé řady odvětví, kde zcela či částečně nahradí lidské zaměstnance. Společnosti, které tuto technologii vyvíjejí, čeká gigantický nový trh a růst tržeb v desítkách a stovkách procent. Které akcie budou na tomto poli přitahovat investice?

Švédský startup implantuje zaměstnancům mikročipy

Švédská startup společnost Epicenter implantuje do těl svých zaměstnanců mikročipy a ti tento postup vesměs vítají.

Ilustrační obrázek

Elon Musk chce permanentně napojit mozek člověka na počítač. Co znamená stvoření kyborga?

Elon Musk z Tesla Inc. přišel nedávno s dalším nápadem, nazvaným Neuralink, který by měl v budoucnu umožnit operativním způsobem vytvořit trvalé spojení mezi šedou lidskou kůrou mozkovou a počítačem. Jaké důsledky by sestrojení tohoto vynálezu mohlo mít pro běžné, průměrné obyvatelstvo?



Čti více

Cena ropy klesá kvůli nadměrným zásobám

Cena ropy dnes klesla v důsledku nadměrných zásob, ovšem ztráty byly omezeny očekáváním, zda se hlavní exportéři dohodnou na prodloužení snížení těžby ropy, aby na trh vrátili rovnováhu.

Ilustrační foto

ECB dnes ponechá nastavení měnové politiky nezměněné

ECB dnes zdůrazní rizika vyššího růstu pro H1 17. Udrží si ale holubičí tón a nastavení měnové politiky ponechá nezměněné.

Chystá se japonská centrální banka omezit svůj program nákupu dluhopisů? Ptají se forex analytici BofAML

Forex analytici Bank of America Merrill Lynch se ve své poslední zprávě zaměřili na dopady, které bude mít aktuální zasedání Bank of Japan na kurz jenu.

Freeport připravuje první vývozní zásilku mědi z dolu Grasburg po 15 týdnech

Freeport McMoRan (FCX +1,1 %) podle agentury Reuters připravuje k vývozu dodávku mědi z dolu Grasberg v Indonésii, odkud nesměla kvůli sporům s vládou vyvážet posledních 15 týdnů.

Cena ropy dnes posiluje v reakci na pokles zásob v USA

Cena ropy reaguje na dnešní zprávu amerického vládního Úřadu pro energetické informace (EIA), podle níž se zásoby ropy v USA minulý týden snížily. Pokles byl přitom výraznější, než se čekalo.

Americký dolar dnes posiluje. Investoři doufají v razantní snížení korporátních daní v USA

Euro vůči dolaru odpoledne ztrácelo půl procenta na 1,0877 USD, zatímco v úterý se jednotná evropská měna vyšplhala až na 1,0950 USD, nejvyšší úroveň za pět a půl měsíce.

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.