Žá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

Elon Musk předpovídá kyborgy a velké změny v zaměstnanosti

Podle Elona Muska je budoucnost samořízených aut blíž, než si většina z nás uvědomuje. To je dobrá zpráva. Každá mince má však dvě strany.

Akcie Shire na premarketu stoupají v reakci na slibné výsledky studie možného přípravku pro léčbu hereditárního angioedému

Výsledky klinického hodnocení fáze 1b přípravku společnosti Shire plc. (NASDAQ:SHPG) (lanadelumab) určeného pro léčbu hereditárního angioedému vykazují slibný léčebný účinek bez vážných nežádoucích příhod či abstinenčních příznaků.

Ilustrační obrázek

VIDEO: Létající motorka Scorpion-3 v akci

Ruský startup HOVERSURF zveřejnil videoukázku svého prototypu létající motorky Scorpion-3. Na vývoji podobných strojů se však podílí celá řada dalších společností z celého světa nebo také armáda USA.

Ilustrační obrázek

Podle poslední analýzy se v Česku užívá pirátsky 33 procent softwaru

Průměrná náhrada škody za odhalené softwarové pirátství ve firmách se za posledních pět let zvýšila o 100.000 na letošních 400.000 korun.

Ilustrační obrázek

Patentový úřad v USA překvapivě rozhodl o technologii genové editace CRISPR

Patentový úřad ve Spojených státech před několika málo dny překvapivě rozhodl ve věci široce diskutovaných patentů, týkajících se revoluční technologie genové manipulace CRISPR-Cas9.

Ilustrační obrázek

Elektronika je (bude) mrtvá, ať žije fotonika!

Experti i laici si v posledních desetiletích zvykli na platnost takzvaného Moorova zákona, který přibližně říká, že výkon elektronických zařízení se každé dva roky zdvojnásobí. Nové technologie slibují v tomto směru revoluční skok kupředu.



Čti více

Výhled pro měnový pár GBP/USD podle forex analytiků MUFG

Forex analytici Mitsubishi UFJ se ve své aktuální zprávě blíže věnovali měnovému páru GBP/USD.

Počet ropných vrtů v USA v tomto týdnu dále rostl

Z údajů společnosti Baker Hughes vyplývá, že celkový počet aktivních vrtů na ropu a zemní plyn vzrostl v posledním týdnu o 3 na 754, což představuje šestý týden růstu v řadě.

Japonský jen za současné bouřlivé politické situace znovu potvrdí svou roli bezpečného přístavu, tvrdí forex analytici Credit Agricole

Forex analytici Credit Agricole jsou přesvědčeni, že investoři nyní jako zajištění před politickými riziky v eurozóně budou preferovat krátké pozice na EUR/USD a především EUR/JPY.

Cena ropy dnes mírně oslabuje v reakci na růst zásob v USA

Ceny ropy na světových trzích v závěru týdne mírně klesají a zůstávají v úzkém rozpětí. Trh oslabil pokračující nárůst ropných zásob na americkém trhu, přestože řada světových producentů omezuje těžbu.

Forex analytici Nomura nebudou do prezidentských voleb ve Francii sázet na pokles eura

Forex analytici Nomura doporučují za současného růstu politické nejistoty prodávat USD/JPY, spíše než sázet na pokles společné evropské měny.

Podle Barclays zažije ropa ve druhém pololetí návrat silné nabídky

Britská banka Barclays snížila svou předpověď ceny ropy brent na rok 2018 o deset dolarů za barel na 67 dolarů.

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.