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

Intel: Mooreův zákon stále platí

Během svého „výrobního dne“ společnost Intel uvedla, že „se snažila o dodržování Mooreova zákona po celou dobu své existence.“

Elon Musk spouští nový startup

Elon Musk opět stál u spuštění nového startupu, tentokrát pod názvem Neuralink.

Rychle rostoucí trh finančně-technologických společností (FinTech) dosahuje v ČR velikosti asi 5,13 miliardy Kč

Rychle rostoucí trh finančně-technologických společností (FinTech), které využívají technologie jako sociální sítě, chytré mobilní telefony či internet při poskytování finančních služeb, v Česku nyní dosahuje asi 5,13 miliardy Kč (190 milionů eur).

Elon Musk kritizuje výši nového rozpočtu NASA

Elonu Muskovi z Tesla Inc. se nelíbí výše vládních dotací pro NASA, kterou včera odsouhlasil prezident Trump.

SuperCom získala v České republice zakázku v hodnotě 3,7 milionu dolarů

Společnost SuperCom (NASDAQ:SPCB) oznámila, že její divize M2M získala šestiletou zakázku v hodnotě 3,7 milionu dolarů. Firma poskytne českému ministerstvu spravedlnosti své řešení elektronického monitorovacího systému PureSecurity Electronic Monitoring Suite.

Apple postaví v Číně další dvě výzkumná centra

Apple postaví v Číně další dvě výzkumná centra.



Čti více

Akcie Tenaris posilují o 5 % po zvýšeném výhledu globální poptávky po potrubí používaném při těžbě ropy

Akcie Tenaris posilují o 5,6 % poté, co společnost zvýšila svůj výhled poptávky po potrubních produktech používaných při produkci ropy a zemního plynu.

Kurz USD se dnes po včerejším propadu stabilizuje

Kurz amerického dolaru se po pondělním propadu na nejnižší hodnotu za více než čtyři měsíce dnes téměř nemění. Ke stabilizaci kurzu přispěly naděje na další růst úrokových sazeb v USA.

Cena ropy dnes roste v reakci na výpadek těžby v Libyi

Ceny ropy se dnes výrazně zvyšují, severomořský Brent se tak vrátil nad hranici 51 dolarů za barel.

Forex výhled pro měnové páry USD/JPY, EUR/USD, AUD/JPY a EUR/JPY podle forex analytiků Societe Generale

Forex analytici Societe Generale se ve své aktuální zprávě blíže zaměřili na měnové páry USD/JPY, EUR/USD, AUD/JPY a EUR/JPY.

Podle íránského ministra bude omezení globální těžby ropy pravděpodobně prodlouženo

Íránský ministr pro ropu Bijan Zanganeh dnes pro novináře v Moskvě uvedl, že dohoda o snížení produkce ropy bude pravděpodobně prodloužena, ovšem že celá záležitost musí být nejprve důkladně projednána jednotlivými stranami.

Ilustrační foto

Dolar proti euru včera na novém čtyřměsíčním minimu

Čeká nás pravděpodobně klidné úterý, protože kalendář dnešních událostí – navíc druhořadých – je velmi krátký. Do zasedání ČNB zbývají dva dny, mezi investory na českém trhu tak bude pravděpodobně růst nervozita.

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.