Důkazové výpočty

Evidence-based computing  je účelové počítání na počítači spojené s analytickým výzkumem, které vede k důslednému stanovení nových faktů a důkazu teorémů [1] .

Spolehlivé výpočty

Jednou z často používaných metod výpočtů založených na důkazech jsou spolehlivé výpočty. Spolehlivými výpočty se rozumí numerické metody s automatickým ověřováním správnosti získaných výsledků [2] . Docela často jsou výpočty založené na důkazech založeny na intervalové analýze , kde se místo reálných čísel uvažují intervaly , které určují přesnost hodnot. Intervalová analýza je široce používána pro výpočty se zaručenou přesností z hlediska strojní aritmetiky .

Příklady

V teorii čísel

Vzhledem k tomu, že teorie čísel do značné míry operuje s celými čísly, ukazuje se použití demonstrativních výpočtů v teorii čísel jako velmi plodné.

• Říká se, že Mersennovo číslo je prvočíslo . Tuto skutečnost si teoreticky může člověk ověřit , ale prakticky pouze s využitím výpočetní techniky.
• L. Euler předpokládal , že rovnice nemá řešení v kladných celých číslech. Později se však ukázalo, že existuje alespoň jedno řešení:

Toto řešení bylo navíc nalezeno pomocí výčtu na počítači [1] .

V teorii grafů

Jedním z nejznámějších úspěchů v aplikaci výpočtů založených na důkazech v teorii grafů je řešení problému čtyř barev . Tento slavný problém byl položen v roce 1852 a je formulován takto: „zjistěte, zda lze jakoukoli mapu umístěnou na kouli obarvit čtyřmi barvami tak, aby jakékoli dvě oblasti, které mají společnou část hranice, byly obarveny různými barvami. V roce 1976 K. Appel a W. Haken pomocí výpočtů založených na důkazech ukázali, že takto lze vybarvit jakoukoli mapu.

V hydrodynamice

Na Ústavu aplikované matematiky se systematicky zabývalo využití výpočtů založených na důkazech v matematických úlohách hydrodynamiky . M. V. Keldyshe z Ruské akademie věd pod vedením K. I. Babenka . Příkladem je následující věta získaná pomocí důkazních výpočtů [3] .

Věta . For a Orr-Sommerfeldův spektrální problém má vlastní hodnotu ležící v polorovině . Proto je v linearizované formulaci pro tyto parametry Poiseuilleho tok nestabilní.

Další příklady

• Booleův problém na pythagorejských trojicích .
• Klasifikace Johnsonových mnohostěnů .

Viz také

• Matematický důkaz
• experimentální matematika

Poznámky

1. ↑ 1 2 Babenko K. I. . Základy numerické analýzy. — M .: Nauka, 1986.
2. ↑ Kulish W., Ratz D., Hammer R., Hawks M. Reliable Computing. Základní numerické metody. - RHD, 2005.
3. ↑ Babenko K. I., Vasiliev M. M. K proof-of-work výpočty v problému stability Poiseuilleova proudění // Dokl. - 1983. - T. 273 , č. 6 . - S. 1289-1294 .

Odkazy

• Intervalová analýza a její aplikace

Literatura

• Pankov P.S. Výpočty založené na důkazech na elektronických počítačích. - Frunze: Ilim, 1978. - 179 s.
• K. I. Babenko. O důkazních výpočtech a matematickém experimentu na počítači  // Uspekhi Mat . - 1985. - T. 40 , č. 4 (244) . - S. 137-138 .
• Babenko K.I., Petrovič V.Yu., Rakhmanov A.I. O demonstrativním experimentu v teorii povrchových vln konečné amplitudy // Dokl. AN. . - 1988. - T. 303 , č. 5 . - S. 1033-1037 .