Když algoritmus selže

Některé úlohy nelze řešit pouze zvyšováním technických parametrů současných počítačů. Překotný rozvoj výpo...


Některé úlohy nelze řešit pouze zvyšováním technických parametrů současných
počítačů.
Překotný rozvoj výpočetní techniky v posledních desetiletích a její uplatnění
ve stále více oblastech lidského života snadno svádí k pocitu, že možnosti
počítačů jsou prakticky neomezené a rychlostní limity, na které při práci s
výpočetní technikou občas narážíme, jsou pouhým projevem dočasných technických
omezení, která s dalším vývojem budou rychle mizet. Ačkoli se takové
přesvědčení zdá být empiricky dobře podložené, v řadě případů se bohužel
ukazuje jako zcela mylné.
Cílem následujícího článku je zaměřit se právě na takové výpočetní problémy, ve
kterých se nedokonalost současných počítačů ukazuje jako principiální.

Algoritmus
Výchozí bod následujících úvah se opírá o pojem algoritmu. Algoritmus obvykle
chápeme jako popis postupu určitého výpočtu, lze na něj ovšem také pohlížet
jako na překlad takového postupu z jednoho "jazyka" (dohodnutého souboru
přípustných akcí) do jiného. Například kuchařské recepty lze chápat jako
algoritmy, které popisují postup výroby určitého pokrmu v termínech
nejjednodušších kuchařských úkonů. V informatickém kontextu jde obvykle o
vyjádření postupu matematického výpočtu pomocí základních matematických operací
(porovnávání čísel, aritmetické výpočty apod.), případně přímo jako posloupnost
elementárních instrukcí počítače.

Trocha historie
Nejstarší nám známé algoritmy v dnešním slova smyslu pocházejí ze starověkého
Řecka. Jedná se například o Eukleidův algoritmus postupného dělení, umožňující
stanovit největší společný dělitel zadané dvojice přirozených čísel, nebo o
Eratosthenovo síto sloužící k nalezení prvočísel ve zvoleném intervalu číselné
osy. Samotný pojem algoritmu se odvozuje ze jména středověkého arabského
matematika Muhammada al-Chórezmího (latinsky Algorizmi), který ve své učebnici
aritmetiky podrobně popsal pravidla pro sčítání, odčítání, násobení a dělení
čísel v desítkové soustavě.
Jakkoli řada výsledků středověké a novověké matematiky více či méně k pojmu
algoritmu odkazuje, nauka zkoumající algoritmy jako takové však zaznamenala
výrazný rozvoj až ve 20. století mimo jiné díky nástupu elektronických
počítačů. Mezi klíčovými matematiky 20. století, kteří svými výsledky výrazně
obohatili teorii algoritmů, je třeba zmínit např. Rakušana Kurta GÖdela
(1906-1978) a Brita Alana Mathisona Turinga (1912-1954).
Mezi zásadní GÖdelovy výsledky patří věta o neúplnosti v matematických
výpočetních systémech (zjednodušeně řečeno v každé dost silné teorii lze
sestrojit tvrzení, které je pravdivé a přesto jeho pravdivost v rámci této
teorie nelze dokázat viz dále); Turing je pak autorem Turingova stroje,
matematické abstrakce umožňující modelovat pomocí malého souboru primitivních
operací princip výpočtu ve všech dnes známých počítačových systémech bez ohledu
na jejich výrobní technologii nebo konkrétní hardware.
Turingovy ideje nám také umožňují uvažovat o algoritmech obecně, bez odkazu na
instrukční soubor určitého mikroprocesoru nebo na zvolený programovací jazyk;
Turing totiž dokázal, že všechny takové instrukční soubory a programovací
jazyky jsou v konečném důsledku z hlediska řešení algoritmických úloh
ekvivalentní a rozdíly mezi nimi lze shrnout do pouhých časových konstant
odvozených z rychlosti jednotlivých systémů.

Rychlost algoritmů
Běžné aritmetické, řadicí, vyhledávací a grafické úlohy technického a
kancelářského softwaru realizují obvykle algoritmy s tzv. polynomiální časovou
náročností. Pokud se n-krát zvětší objem vstupních dat takového algoritmu, jeho
doba běhu se zvětší zhruba nk-krát, přičemž konstanta odpovídá nějakému
přirozenému číslu. Speciálně algoritmy s k = 1 nazýváme lineární a algoritmy s
k = 2 kvadratické. Takové algoritmy jsou obvykle dobře realizovatelné stávající
výpočetní technikou a pokračující technický vývoj má výrazný vliv na rozsah
zpracovatelných dat (na dvakrát rychlejším hardwaru lze lineárním algoritmem
zpracovávat stejnou rychlostí dvakrát větší objem vstupních dat, kvadratickým
algoritmem pak zhruba 1,4krát větší). Některé algoritmy jsou dokonce ještě
rychlejší, logaritmické např. dvojnásobné zvětšení objemu vstupních dat zvýší
dobu běhu algoritmu pouze o konstantní počet kroků.

Růst složitosti
Časová náročnost jiných algoritmů ovšem roste s velikostí vstupních dat mnohem
rychleji. Příkladem může být známá hříčka Hanojské věže (viz obrázek). Ve
variantě se 64 disky dospěli tibetští mniši (hra je i přes svůj název původem
tibetská) k závěru, že přesun disků nelze provést do skonání světa. Skutečně
lze dokázat, že počet tahů nezbytných k přesunutí n-diskové pyramidy je roven
2n 1, takže přidáním jediného dalšího disku stoupne přibližně dvakrát. Pro n =
64 je potřebný počet tahů roven zhruba 1,84 x 1019 (takže např. v případě, že
hráč přesune 1 disk za 3 sekundy, bude přesun pyramidy trvat 1,84 x 1012 let).
Algoritmy s takovým chováním nazýváme exponenciální to vlastně znamená, že
jejich výpočetní složitost roste vzhledem k zadání exponenciálně. Počítače jsou
úlohy tohoto typu obvykle schopny řešit jen pro velmi malé vstupní hodnoty.
Problém je v tom, že technický pokrok má navíc na rozsah zpracovatelných dat
pouze minimální vliv.
Lze pochopitelně namítnout, že úloha Hanojských věží představuje umělou hříčku
bez praktického dopadu. Bohužel se však ukazuje, že podobné nebo ještě horší
chování vykazuje řada praktických algoritmů nutných pro technické a matematické
aplikace.

NP úplné problémy
Oblíbeným příkladem exponenciálních algoritmů je tzv. problém obchodního
cestujícího. Cílem úlohy je obejít zadanou skupinu měst (matematicky uzlů
grafu, jehož hrany představují cesty mezi městy) co nejkratší cestou,
eventuálně projít městy i za předpokladu, že ne všechna jsou spolu propojena.
Ekvivalentní problému obchodního cestujícího je řešení pravdivostní formule
(tedy určení hodnot logických proměnných, pro které zvolený logický výraz
složený z těchto proměnných nabývá hodnoty pravda).
Obě tyto úlohy patří do bohaté kategorie NP úplných problémů. Bez ohledu na
určité přetrvávající teoretické nejasnosti týkající se charakteru těchto úloh
pro ně každopádně platí, že pro jejich řešení není znám žádný polynomiální
algoritmus a odborníci se spíše kloní k závěru, že takový algoritmus ani
vytvořit nelze.
NP problémy se vyznačují významnou asymetrií mezi časem potřebným na řešení
úlohy a na ověření výsledku. Pokud už je řešení takového problému jednou
nalezeno, lze velmi rychle zkontrolovat jeho korektnost například v případě
pravdivostní formule lze pro nalezené kombinace logických proměnných snadno
ověřit výpočtem logického výrazu, že jeho hodnota je skutečně pravdivá.
Asymetrie mezi faktorizací velkého čísla na prvočísla a ověřením řešení se také
využívá v moderních kryptografických metodách (byť u faktorizace není striktně
vzato prokázáno, že patří mezi NP úplné problémy).
Další zajímavou vlastností NP problémů je, že pokud by bylo možno v každém
místě větvení algoritmu jakoby pokračovat ve výpočtu oběma směry zároveň, jedna
z větví by výpočet dokončila v polynomiálním čase (tento fakt motivuje zkratku
NP, jejíž význam je nedeterministicky polynomiální). Předpokládá se, že
takového výpočetního postupu by mohlo být možno dosáhnout pomocí kvantových
počítačů, vývoj v této oblasti je ovšem zatím v plenkách.

Nerozhodnutelné problémy
Existují ovšem problémy, jejichž chování je ještě horší než u třídy NP a
algoritmicky je obecně nelze řešit vůbec. Příkladem mohou být některé problémy
typu domina nebo dláždění. Je dokázáno, že nemůže existovat algoritmus, který
by v konečném čase pro libovolnou kombinaci dlaždic správně odpověděl, zda
touto kombinací dlaždic lze rovinu vydláždit, či nikoli (viz obrázek na
vedlejší straně).

Certifikáty
Zajímavou vlastností nerozhodnutelných úloh je existence jednostranného
certifikátu, uvádějící je do souvislosti s NP úplnými problémy: zatímco NP
úplné problémy jsou obtížné na řešení a přesto jednou nalezené řešení lze
snadno ověřit (doložit tzv. certifikátem), v případě nerozhodnutelných úloh lze
konečným certifikátem doložit jen jednu z možných pravdivostních hodnot.
Například v úloze s dlaždicemi lze pro danou kombinaci dlaždic doložit, že jimi
rovinu dláždit nelze udáním rozměru minimálního čtverce, který již dlaždicemi
nelze pokrýt. Pokud tento rozměr známe, můžeme (i když v exponenciálním čase)
teoreticky prověřit všechna možná pokrytí této konečné plochy různými
kombinacemi dlaždic a prokázat tak, že žádné z nich není korektní vzhledem k
zadání úlohy. Opačný výsledek, tedy že dlaždicemi rovinu vydláždit lze, obecně
konečným certifikátem doložit není možné (neboť vydláždění roviny nemusí být
periodické).
Obdobně v případě problému zastavení (viz vložený text) lze doložit zastavení
algoritmu jeho konečnou simulací. Naproti tomu nekonečnost algoritmu takto
doložit nelze, neboť sice můžeme demonstrovat libovolně dlouhý běh zkoumaného
algoritmu, obecně ovšem nelze předpovědět, zda by výpočet náhodou po další
hodině běhu přece jenom neskončil.

Bohatství logického světa
Uvedené výsledky mohou působit překvapivě. Lze namítnout, že se také jedná o
speciálně zkonstruované úlohy pouze teoretického významu. Tato námitka však
není příliš relevantní. Chování některých matematických objektů, např.
fraktálů, vykazuje totiž takové abnormality a doslova nekonečnou citlivost na
hodnoty vstupních parametrů, že by bylo spíše s podivem, kdyby existovala
nějaká obecná kuchařka umožňující analyzovat jejich chování.
V konečném důsledku popsané problémy a negativní výsledky při jejich řešení
především potvrzují rozmanitost abstraktního logického světa (spíše než aby jej
popíraly nebo odhalovaly jeho vnitřní konflikty). Z čistě programátorského
hlediska zde pak zůstává otevřený prostor pro tvorbu mnoha dílčích algoritmů,
které popsané problémy řeší alespoň částečně pro některé případy, s omezenou
přesností nebo poloautomaticky s průběžnými lidskými zásahy.

Problém zastavení algoritmu
Do značných problémů se dostáváme u algoritmů analyzujících chování jiných
algoritmů. Mějme libovolný algoritmus A zapsaný v domluveném programovacím
jazyce a ptáme se pro existenci algoritmu H, který by jako vstup přijal tento
algoritmus A a rozhodl, zda se algoritmus A po konečném počtu kroků zastaví
nebo uvízne v nekonečné smyčce. V počítačové teorii se tato úloha označuje jako
problém zastavení.
Pro řadu algoritmů samozřejmě dokážeme odpovědět poměrně snadno (zacyklit se
např. nemůže algoritmus vůbec neobsahující cykly a skoky). Nás však zajímá, zda
existuje algoritmus, který by uměl správně rozhodnout u libovolného dalšího
algoritmu.
Jednoduchý důkaz ukazuje, že žádný obecný algoritmus H těchto vlastností nemůže
existovat. Principem důkazu je logický paradox (spor). Předpokládejme, že
algoritmus H požadovaných vlastností existuje. Logickou hodnotu vrácenou
algoritmem označme H(A). Sestrojme nyní nový algoritmus HN takto:
Vezmi kód tohoto algoritmu (HN) v dohodnutém programovacím jazyce akceptovaném
algoritmem H.
Spusť hypotetický algoritmus H s parametrem HN a spočítej jeho pomocí
pravdivostní hodnotu H(HN).
Pokud je H(HN) = nepravda, ukonči okamžitě výpočet.
Pokud je H(HN) = pravda, spusť nekonečný cyklus (opakuj stále dokola tento bod).
Algoritmus HN je sestrojen tak, že popírá sám sebe. Pokud by bylo H(HN) =
= pravda (tedy dle předpokladu algoritmus H detekoval, že HN je konečný),
algoritmus HN zahájí nekonečný cyklus (bod 4) a nikdy neskončí, pokud naopak
H(HN) = nepravda (H považuje HN za nikdy nekončící), algoritmus HN okamžitě
skončí (a opět tak popře výsledek výpočtu algoritmem H). Z tohoto výsledku
vyplývá, že konečný algoritmus H řešící popsaný analytický problém nemůže
existovat pro každý takový algoritmus lze sestrojit protipříklad HN, pro který
bude výsledek H(HN) chybný.
Všimněte si, že nejspíš existuje algoritmus, který by dokázal správně
analyzovat zastavení programu HN. Důležité však je, žádný jednotlivý algoritmus
nezvládne vyřešit problém zastavení pro všechny představitelné algoritmy
současně. Za pozornost také stojí, že problém nastane, pokud nechápe algoritmus
analyzovat některou variantu sebe sama. Na tomto principu stojí celá řada
paradoxů (některé jsou známy už od antiky, např. problém pravdivostní hodnoty
výroku "jeden Kréťan řekl, že všichni Kréťané jsou lháři") a problému
"sebevztahu" využívá i známá GÖdelova věta o nemožnosti určit (dokázat) v rámci
systému pravdivost určitých výroků.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.