1 Algoritmus
Cílem této kapitoly je seznámi studenty se základními pojmy informatiky jako jsou algoritmus, program, složitost. Student získá také přehled o složitostních třídách problémů (algoritmů). O algoritmech toho lze říci mnoho. Nejsou vidět, ale jsou důležitou součástí našeho života a běžně je při svých činnostech používáme. Je těžké si představit, jak složitý by byl náš každodenní život složitý, pokud by algoritmy neexistovaly.
1.1
Úvod
V 9. století znamenal význam slova algoritmus „provádění aritmetiky za pomoci arabských číslic“. Dnes se s pojmem algoritmus setkáváme nejčastěji v matematice a v programování, kde označuje sestavení teoretických principů řešení. Využívá se k tomu i mnoho již známých algoritmů. Aniž bychom si to uvědomovali, s algoritmy v podobě návodů či instrukcí se setkáváme také v mnoha běžných každodenních činnostech. Ovšem ne každý návod je algoritmus. Takto lze označit jen postupy, které splňují určité vlastnosti.
1.2
Programování (tvorba algoritmů)
V praxi se pod pojem programování schovávají následující činnosti: 1. Analýza (problému) – zjistit, co uživatel přesně potřebuje, přesná specifikace úlohy 2. Algoritmizace – vymyslet postup, jak danou úlohu řešit 3. Programování/Kódování – „donutit“ počítač, aby tento postup realizoval 4. Testování Analýza Často největší problém, je zde nutná spolupráce se zadavatelem. Zadavatel většinou neví, co chce (i když si myslí, že ví) a zjistí, že to chtěl jinak, až když je práce (program) hotová. Proto je vhodné před započetím práce sepsat dokument (specifikace zadání), kde bude přesně uvedeno, co zadavatel požaduje. Algoritmizace Algoritmus si můžeme představit jako „kuchařku“ pro řešení dané úlohy. Algoritmus definujeme jako konečnou posloupnost elementárních příkazů, jejichž provádění umožňuje pro každá přípustná vstupní data mechanickým způsobem získat po konečném počtu kroků příslušná výstupní data. Programování/Kódování Programem budeme nazývat algoritmus, který je zapsaný ve tvaru vhodném pro jeden konkrétní typ procesoru (počítač). Procesory pracují ve strojovém kódu který pro lidi velmi nepřehledný. Proto vznikly programovací jazyky, které můžeme chápat jako kompromis. Pro lidi je relativně dobře čitelný a je snadno přeložitelný do strojového kódu pomocí překladače (kompilátoru). Výhoda je také ta, že jednou napsaný program (v programovacím jazyce) lze přeložit do strojového kódu různých počítaču.
1
Prekladač vs. Interpret Prekladač je nástroj, který vezme zdrojový tvar programu (napsaný v programovacím jazyce) a preloží (zkompiluje) ho do strojového kódu daného procesoru (binární tvar programu). Interperet (interpreter) je nástroj, který vezme zdrojový tvar programu a jeho jednotlivé instrukce postupně vykonává. Běh programu je tak pomalejší. Příklad: Uveďte programovací jazyky které znáte a rozhodněte, do které z těchto dvou kategorií patří. Testování Ověření funkčnosti vytvořeného programu. Alfa-testování provádí tvůrce programu, betatestování provádí vybraná skupinka uživatelů (beta-testeri). Na testování nezapomínat! V některých případech je to prakticky jediná možnost, jak zjistit jestli náš program funguje tak jak má.
1.3
Historie algoritmů
S ohledem na obecnost algoritmu, jako popisu libovolné běžné každodenní činnosti, sahá počátek vzniku algoritmu až ke vzniku lidstva samotného. Vždyť i činnosti pravěkých lidí měly přesně daný postup, řád, konečnost a výsledek. Postupy, které dnes splňují podmínky algoritmu, se ve vědních oborech objevily již v období starého Řecka, ačkoli v této době pojem algoritmus ještě nebyl vůbec znám. Podstatu a použití algoritmu v období cca 300 let p.n.l. dokládá např. známý Euklidův algoritmus pro výpočet NSD, tj. největšího společného dělitele, nebo v 1 století n.l. Herón z Alexandrie který algoritmicky podal důkaz vzorce pro obsah trojůhelníku, či algoritmus pro hledání odmocniny z čísla. Samotný pojem algoritmus vzniknul zhruba o tisíc let později v 9. století našeho letopočtu, a je spojován se jménem perského matematika Abú Abd Alláh Muhammad ibn Músá al-Chwárizmí, který vytvořil systém arabských číslic. Prvním významem slova algoritmus tak bylo „provádění aritmetiky pomocí arabských čislic“ a používal se k vyjádření zejména matematických postupů. Pojem algoritmus ve smyslu dnešního významu se používá zhruba od 20. století. Využití známých algoritmů Algoritmy se dnes využívají ve všech vědních oborech. Nejčastěji se s nimi ale setkáme v matematice a v programování, kde jsou nástrojem k sestavení teoretickému principu řešení daného problému. Vytváření algoritmů je v dnešní době předmětem intenzivního zkoumání a stává se i samostatným vědním oborem, při kterém se v nemalé míře využívají a dále rozvíjejí již vytvořené algoritmy, kterých existuje velmi mnoho, např.: • Eratosthenovo síto je algoritmus pro nalezení všech prvočísel menších než zadaná horní mez. • Dijkstrův algoritmus slouží k nalezení nejkratší cesty v grafu. • Ballman-Fordovův algoritmus nám umožní spočítat nejkratší cestu od uzlu k uzlu v ohodnoceném grafu. • Algoritmus de Casteljau pro výpočet bodu na Beziérově křivce.
Turingův stroj Díky objevu Alana Turinga (1912-1954), který navrhl abstraktní matematický model počítače - Turingův stroj (1936/37), můžeme algoritmus definovat jako proceduru implementovatelnou pomocí Turingova stroje. TS se skládá z procesorové jednotky, tvořené konečným automatem, programu ve tvaru pravidel přechodové funkce a potenciálně nekonečné pásky pro zápis mezivýsledků. Existuje více obecných definicí Turingových strojů (jednopáskové / vícepáskové deterministické TS, nedeterministické TS, univerzální). V jednom kroku výpočtu stroj v závislosti od aktuálního stavu a od symbolu (resp. k symbolů u k-páskových TS) snímaných hlavami: 1. změní svůj stav,
2
2. 3.
zapíše symbol na každé políčko snímané hlavou (čímž přepíše symbol, který tam byl zapsaný předtím ), posune každou hlavu o jedno políčko doprava nebo doleva.
Způsob, kterým se má změnit stav, přepsat políčka a posunout hlavy, předepisuje přechodová funkce δ. Výpočet končí když stroj přejde do jednoho ze speciálních stop stav, na některých vstupech může výpočet stroje být nekonečný. Další zdroje: http://alan.sourceforge.net - projekt emulátoru TS http://www.warthman.com/ex-turing.htm - projekt animace činnosti TS
1.4 Algoritmy Algoritmem budeme nazývat jakýkoliv postup (návod, soupis kroků), který bude splňovat následující kritéria: 1. 2.
3. 4.
5.
6.
7.
Elementárnost algoritmus se skládá z jednoduchých, tzv. elementárních, kroků. Hromadnost, obecnost, univerzálnost algoritmus slouží k řešení celé třídy (skupiny) navzájem si podobných úloh. Úlohy jsou si podobné, ale liší se vstupními daty. Tzn. neřeší „jak spočítat 3x7“, ale řeší, „jak spočítat součin dvou celých čísel“. Konečnost pro každá přípustná data algoritmus po konečném počtu kroků (může být libovolně velký) skončí. Determinovanost algoritmu každý krok uvedený v algoritmu musí být jednoznačně a přesně definován. V každé situaci musí být napřosto zřejmé, co a jak se má provést a jak má provádění algoritmu pokračovat. Částečná (parciální) správnost jestliže algoritmus skončí, pak výsledek je správný (tj. nestane se, že pro nějaká přípustná vstupní data algoritmus skončí se špatným výsledkem). Výstup, resultativnost algoritmus musí mít alespoň jeden výstup. Říkáme, že algoritmus vede od zpracování hodnot k výstupu. Můžeme algoritmus chápat také jako funkci, která nám ke vstupu přiřadí příslušný výstup. Mechanické provádění algoritmus může provádět každý bez hlubší znalosti řešené úlohy, např. procesor (umí jen základní sadu příkazů) nebo ten kdo bude vykonávat algoritmus (nemusí to být nutně počítač).
3
Druhy algoritmů Algoritmů dnes existuje celá řada a proto existuje klasifikace (roztřídění) do skupin. Rozdělení ale neplatí direktivně, a je běžné, že jeden algoritmus může patři současně i do více skupin. Mezi důležité skupiny algoritmů patří: 1. 2. 3. 4.
5.
Rekurzivní algoritmy, které v rámci cyklu volají samy sebe. Pravděpodobnostní algoritmy provádějí některá rozhodnutí náhodně. Paralelní algoritmy lze využít v případě, kdy můžeme algoritmus rozdělit na více samostatných úloh a zpracovávat je odděleně na více strojích. Výhodou je časová úspora. Genetické algoritmy, které pracují na základě napodobování biologických evolučních procesů. Pro vědu jsou přirozené procesy probíhající v přírodě velkým vzorem, protože mohou být chápány a aplikovány i jako možná řešení daného problému. Heuristické algoritmy, jejichž cílem není nalézt přesné řešení daného problému. Tyto algoritmy se používají v situacích, kdy dostupné zdroje nepostačují na využití exaktních algoritmů.
Ověřování správnosti algoritmu K ověření správnosti algoritmu nestačí vyzkoušet reakci algoritmu na konečný počet vstupních dat, i když se to tak v praxi často dělá a takové ověření o správnosti algoritmu leccos vypoví. Není ovšem dokázáno, že se algoritmus při neočekávané kombinaci vstupních dat nezhroutí. Pro ověřování správnosti algoritmu neexistuje univerzální metoda, algoritmus by měl být matematicky dokázán sledem předem známých kroků (operací), které nevyvratitelně vedou pro všechna přípustná data k správnému výsledku úlohy. Je zřejmé, že takový algoritmus je pak korektním řešením úlohy. Algoritmus můžeme považovat za korektní, pokud není opomenuta žádná z možností zpracování dat při průchodu algoritmem. Algoritmus je částečně (parciálně) správný, právě když platí, že pokud skončí, vydá správný výsledek. K dokázání částečné správnosti výpočtu můžeme použít tzv. invariant tvrzení, které platí po celou dobu výpočtu. Nutné je také ověřit konečnost algoritmu (pro všechna přípustná data algoritmus po konečném počtu kroků skončí). Dokazování konečnosti algoritmu Konečnost algoritmu je často intuitivně zřejmá tím, že se pro vstupní data nemůže algoritmus zacyklit. Matematicky lze dokázat konečnost algoritmu takto: Pokud najdeme způsob, který každý stav výpočtu ohodnotí přirozeným číslem, a ukážeme, že provedením jednoho kroku algoritmu se tato hodnota zmenší, je jasné, že algoritmus po konečném počtu kroků skončí, neboť interval počtu průchodů algoritmem je konečný.
Kvantitativní ukazatele kvality algoritmů Mezi dva nejdůležitější kvantitativní ukazatele kvality algoritmů patří: • operační složitost • paměťová složitost Příklady: Zadání: Pole S obsahuje n vzestupně seřazených prvků. Je třeba nalézt funkci typu Boolean, která vrátí hodnotu true, pokud zadaný prvek v poli S existuje, a hodnotu false v opačném případě. Řešení: Řešení hrubou silou - sekvenční hledání function sekvencni_hledani(hodnota, pole) { var existuje = false; var i = 0; while(i<pole.lenght && !existuje) { if(pole[i] === hodnota) { existuje = true; } i++; }
4
return existuje; } Nejhorší případ: prvek v poli není, pak tělo cyklu proběhne (n-1) krát a bude provedeno n porovnání. Cvičení: Je-li pole uspořádáno, lze využít efektivnější binární půlení, napište tento algoritmus. function binarni_hledani(hodnota, pole) { var existuje = false; var i = l = 0; var r = pole.length; while(!ret && r >= 1) { i = Math.round((l+r)/2); if(hodnota === pole[i]) { existuje = true; } else { if(hodnota > pole[i]) { l = i+1; } else { r = i-1; } } } return existuje; } Opět časově nejnáročnější při neexistenci prvku v poli. Cyklus while však proběhne jen (log2 n) krát. Algoritmus je však mírně paměťově náročnější. Důležitost analýzy složitosti algoritmů Ukážeme na dvou příkladech tisku Fibonacciho posloupnosti: Fibonacci (Leonardo z Pisa) řešil reprodukční problém - kolik párů králíků může vzniknout za rok z jednoho páru, jestliže budeme předpokládat, že každý pár každý měsíc plodí nový pár, který se začne množit od druhého měsíce? Měsíc: Počet párů:
1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 3 5 8 13 21 34 55 89 144
f0 = 0; f1 = 1 a fn = fn-1 + fn-2 pro n > 1. Varianta 1: Rekurzivní výpočet n-tého Fibonacciho čísla: function fib(n) { return (n == 0) ? 0:((n == 1) ? 1 : fib(n-1) + fib(n-2)); } function printFib(n) { for(var i = 1; i <= n; i++) { console.log(i + " " + fib(i)); } } Varianta 2: Fibonaccioho posloupnost bez rekurze: function prinFib2(n) { var p0 = p1 = p = 1; for (var i = 1; i <= n; i++) { console.log(i + " " + p0);
5
p = p1; p1 = p0 + p1; p0 = p; } } Pod složitostí algoritmu rozumíme tedy dobu prováděného algoritmu - časovou složitost a rozsah použité operační paměti - paměťovou náročnost (složitost). 1.5
Složitost algoritmu
Složitost závisí na velikosti vstupních dat, tj. můžeme popsat jako funkci T(n), kde číslo n udává velikost vstupních dat. Např. T(n) = an + b, kde a, b jsou nějaké konstanty, je zápis lineární časové složitosti (složitost roste lineárně s rostoucí velikostí vstupů). Obvykle je pro odhad složitosti důležitý pouze typ funkční závislosti a nikoliv přesné hodnoty konstant, ty se zanedbávají. Efektivními algoritmy nazveme takové postupy, jejichž složitost je maximálně polynomiální (např. n127, nikoliv exponenciální např. 2n). Provádění exponenciálních algoritmů T(n) = 2n či dokonce algoritmů o složitosti T(n) = n! může už jen při malém navýšení velikosti vstupních dat trvat i mnoho tisíců a miliónů let. Ani polynomiální algoritmy s velkým stupněm polynomu nebo s velkými vstupními daty nejsou příliš rychlé, viz následující tabulka:
V zápisu T(n) = an + b je a multiplikativní konstanta, která v sobě zahrnuje počet operací, který je třeba provést na jednotku vstupních dat. Aditivní konstanta b udává pouze konstantní nárůst složitosti nezávislý na velikosti vstupních dat. Při značné velikosti vstupních dat můžeme konstanty a a b zanedbat, protože vzhledem k velikosti n jsou nepatrné, a výsledná složitost T(n) tak závisí především na velikosti n, tj. velikosti vstupních dat algoritmu.
6
Vybereme-li ze všech konstant a největší konstantu, kterou označíme c, platí T(n) ≤ cn pro všechna dostatečně velká n. Tuto skutečnost značíme T = O(n), čímž vyjadřujeme asymptotické chování funkce T. Horní odhad složitosti algoritmu Tworst(n) udává složitost algoritmu v nejhorším případě. Složitost algoritmu f(n) je asymptoticky menší nebo rovna g(n), tj. f(n) = O(g(n)), právě když existuje taková kladná konstanta c tak, že pro každou velikost dat n od určité hodnoty n0 platí: 0 ≤ f(n) ≤ cg(n). Např.: 2n2 + 3n + 4 = O(n2), neboť pro n0 = 1 a c = 10 platí 2n2 + 3n + 4 <= cn2. Dolní odhad složitosti Tbest(n) určuje minimální složitost daného algoritmu (nejkratší čas provedení), která nastává jen pro určité případy vstupních dat. Pokud o algoritmu víme, že má dolní odhad složitosti n2, je jasné, že výsledek nedostaneme rychleji než v kvadratickém čase: Složitost algoritmu f(n) je asymptoticky větší nebo rovna g(n), tj. f(n) = Ω(g(n)), právě když existuje taková kladná konstanta c tak, že pro každou velikost dat n od určité hodnoty n0 platí: 0 ≤ cg(n) ≤ f(n). Např. zápis Tbest(n) = Ω(n3) udává kubickou dolní složitost algoritmu. Složitost v průměrném případě (očekávaná složitost) Tavrg(n) se počítá jako střední hodnota náhodné složitosti T(n) při nějakém rozložení vstupních dat. Někdy může být i řádově lepší než složitost v nejhorším případě. Řekneme, že složitost algoritmu f(n) je asymptoticky stejná jako g(n), tj. f(n) = Θ(g(n)), právě když existují takové kladné konstanty c1,c2 tak, že pro každou velikost dat n od určité hodnoty n0 platí: 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n). Algoritmus je pro danou úlohu optimální, jestliže neexistuje algoritmus, který by tuto úlohu řešil v nejhorším případě s menším počtem základních operací. Často se místo Tworst(n) odhaduje pouze podle toho, kolikrát se provedou některé základní, časově nejnáročnější operace. Většinou existuje tzv. triviální dolní odhad, což je velikost instance, protože algoritmus musí vždy projít celý vstup alespoň jednou.
1.6
Složitost úloh – P a NP úlohy
Třída P je třída všech rozhodovacích úloh U, pro něž existuje polynomiální algoritmus, řešící úlohy U. Rozhodovací úloha je úloha, jejímž řešením je odpověď „ano“ nebo „ne“. Každou optimalizační úlohu zle převést na rozhodovací úlohu. Příklad - problém obchodního cestujícího. Je zadána množina nějakých bodů a pro každé dva z nich je zadána jejich vzdálenost. Uvažujeme cesty, které vychází z některého z daných bodů, projdou všemi body a vrátí se do výchozího. Optimalizační verze: Najděte trasu nekratší délky. Převedeno na rozhodovací úlohu: Je dáno navíc číslo K. Rozhodněte, zda existuje trasa délky ≤ K. Obchodní cestující není zatím ve třídě P, ale je ve třídě NP úloh. NP úloha je taková úloha, kdy platí : pro každou „ano“ instanci lze v polynomiálním čase ověřit správnost odpovědi „ano“. Pro „ne“ instanci takový algoritmus neexistuje. Třída NP je třída všech rozhodovacích úloh U, pro něž existuje nedeterministický algoritmus, pracující v polynomiálním čase. Nedeterministický algoritmus má dvě fáze. Nedeterministická, kdy se náhodně vygeneruje řetězec symbolů s a deterministická, kdy na vstupu úlohy je jak instance úlohy, tak řetězec s. Po konečném počtu kroků je výstupem „ano“ nebo „ne“. Řetězec s je vlastně navržené řešení úlohy, které se v deterministické části otestuje, zda platí. Pro obchodního cestujícího je to číslo K. Redukce a polynomiální redukce Obtížnost rozhodovacích úloh se dá srovnávat. Pojem „U se redukuje na V“ vlastně znamená, že rozhodovací úloha U není těžší než rozhodovací úloha V. U se redukuje na V, jestliže existuje algoritmus A, který pro každou instanci I úlohy U zkonstruuje instanci A(I) úlohy V tak, že I je „ano“ instance U právě když A(I) je „ano“ instance V. Je-li algoritmus A polynomiální, pak jde o polynomiální redukci. NP úplné úlohy Rozhodovací úloha U je NP úplná, jestliže je NP úloha a každá NP úloha se na U polynomiálně redukuje. Třídu NP úplných úloh označujeme jako NPC. (NP úplné úlohy jsou nejtěžší mezi NP úlohami). Není známo, zda třídy P a NP jsou opravdu různé. Jinak řečeno, o žádné úloze v NP se nepodařilo dokázat, že není v P.
7
Podařilo se však nalézt úlohy, které jsou úplné ve třídě NP. Příklady Otázka (obtížné problémy): Existuje pro každý problém efektivní (polynomiální) algoritmus, který ho řeší? Odpověď: Ne, existují problémy, pro které se dá dokázat, že neexistuje žádný efektivní algoritmus, který by daný problém řešil. Dokonce existují problémy, pro které se dá dokázat, že neexistuje žádný (ani neefektivní) algoritmus, který by daný problém řešil. Námitka (neexistence algoritmů): Jak dokázat, že něco neexistuje? Odpověď: Sporem. Předpokládáme, že to existuje a ukážeme, že z toho vyplývá nějaký závěr, který je ve zjevném rozporu se skutečností (typicky ukážeme, že něco musí být současně pravda i nepravda). Příklad obtížného problému Vstup: Uzavřená aritmetická formule vytvořená ze symbolů +, =, ∧, ∨, ¬, ∀, ∃, (, ), proměnných a celočíselných konstant. Otázka: Je tato formule pravdivá v oboru přirozených čísel? Příklad vstupu: ∀x∃y∀z((x + y = z) ∧ (y + 5 = x)) Pro tento problém je znám algoritmus se složitostí 22^2^O(n). Současně bylo dokázáno, že jakýkoliv algoritmus rešící tento problém má složitost minimálně 22^cn. Příklad algoritmicky neřešitelného problému Vstup: Uzavřená aritmetická formule vytvořená ze symbolů +, ×, =, ∧, ∨, ¬, ∀, ∃, (, ), proměnných a celočíselných konstant. Otázka: Je tato formule pravdivá v oboru přirozených čísel? Příklad vstupu: ∀x∃y∀z((x × y = z) ∧ (y + 5 = x)) Tento problém je algoritmicky neřešitelný (u rozhodovacích problémů se používá též pojem algoritmicky nerozhodnutelný). Úzce souvisí s Gödelovou větou o neúplnosti. Další příklad nerozhodnutelného problému Vstup: Počítačový program a nějaká jeho vstupní data. Otázka: Zastaví se někdy tento program, když dostane na vstup tato data? Idea důkazu nerozhodnutelnosti: Předpokládejme existenci programu H, který řeší tento problém. Můžeme ho snadno upravit na podprogram H′(p,v), který vrací „Ano" nebo „Ne" jako návratovou hodnotu. Vytvoříme nový program D: Vezme svůj vstup x a zavolá H′ jako H′(x,x). Pokud H′ vrátí „Ano", D skočí do nekonečné smyčky. Pokud H′ vrátí „Ne", D se zastaví. Zastaví se program D nebo ne, když mu předložíme jako vstup jeho vlastní kód? 1.7
Třídy problémů
Některé problémy jsou těžší než jiné. Při posuzování obtížnosti problémů se ukázalo jako užitečné rozdělit problémy do tříd složitosti, které značíme: PTIME - problémy řešitelné v polynomiálním čase PSPACE - problémy řešitelné s polynomiálním množstvím paměti EXPTIME - problémy řešitelné v exponenciálním čase EXPSPACE - problémy řešitelné s exponenciálním množstvím paměti
8
Třída NPTIME Jednou z nejdůležitějších tříd je třída NPTIME. Do třídy NPTIME patří rozhodovací problémy, pro které existuje polynomiální algoritmus, který ověří správnost nalezeného řešení. Přesněji řečeno, pokud je odpověď „Ano", existuje svědek, který dosvědčuje, že odpověď je „Ano", kterého je možné v polynomiálním čase otestovat, že tomu tak skutečně je. Pokud je odpověď „Ne", žádný takový svědek neexistuje. Příklad problému z NPTIME Vstup: Popis mapy (seznam států a informace který stát sousedí s kterým) a číslo k. Otázka: Je možné státy obarvit k barvami tak, aby žádné dva sousední státy neměly stejnou barvu?
P vs. NP Jeden z největších otevřených problémů teoretické informatiky: Otevřený problém: Je P = NP? Pozn.: Třídy PTIME a NPTIME bývají také označovány stručněji P a NP. NP-úplné problémy Důležitou podtřídou třídy NPTIME jsou tzv. NP-úplné problémy. Definice Problém P je NP-těžký, jestliže platí, že libovolný problém ze třídy NPTIME je možné v polynomiálním čase redukovat na problém P. Definice Problém P je NP-úplný, jestliže je NP-těžký a současně sám patří do třídy NPTIME. NP-úplné problémy jsou důležité, protože: • Kdyby alespoň jeden z nich byl řešitelný v polynomiálním čase, všechny problémy z NPTIME by byly řešitelné v polynomiálním čase. • Pokud v NPTIME existuje alespoň jeden problém, který není řešitelný v polynomiálním čase, pak žádný z NP-úplných problémů není řešitelný v polynomiálním čase. • Velké množství problémů, které se objevují v praxi v různých oblastech informatiky, je NP-úplných nebo NP-těžkých. • To, že NP-úplné problémy nelze řešit v polynomiálním čase je podmínkou nutnou (nikoli však postačující) pro to, aby existovaly šifrovací algoritmy, které by nebyly snadno prolomitelné. Někdy dva problémy mohou vypadat podobně, a přitom jeden z nich je řešitelný v polynomiálním čase, zatímco druhý je NP-úplný. Problém 1 Vstup: Popis měst a silnic. Výstup: Existuje okružní cesta, na které projedeme každou silnici právě jednou? Problém 2 Vstup: Popis měst a silnic. Výstup: Existuje okružní cesta, na které projedeme každé město právě jednou?
9
Problém 1 je v PTIME. Problém 2 je NP-úplný. Jak řešit těžké problémy? Pokud pro daný problém neexistuje efektivní algoritmus, máme následující možnosti: 1. Exponenciální algoritmy – použitelné jen na malé instance. 2. Aproximační řešení – použitelné jen pro optimalizační problémy. Najde řešení, které je o něco horší než optimum. 3. Pravděpodobnostní (randomizované) algoritmy – najde rychle řešení, ale řešení je s určitou pravděpodobností špatně. 4. Speciální případy – soutředit se jen na některé speciální případy instancí, neřešit problém v plné obecnosti. 5. Heuristiky – postup, který najde řešení rychle ve většině „rozumných" případů, není však zaručeno že vždy. Příklad: Randomizovaný algoritmus Zadání: Vstup: Přirozené číslo p. Otázka: Je p prvočíslo? Teprve od roku 2003 je znám polynomiální algoritmus (O(n12+ε), později o něco zlepšen). V praxi je používán randomizovaný algoritmus se složitostí O(n3): Pokud p je prvočíslo, vrátí vždy odpověď „Ano". Pokud p není prvočíslo, je pravděpodobnost odpovědi „Ne" minimálně 50%, ale existuje až 50% šance, že program vrátí chybnou odpověď „Ano". Program můžeme volat opakovaně (k krát). Pokud program vrátí alespoň jednou odpověď „Ne", víme na 100%, že p není prvočíslo. Pokud program vrátí pokaždé „Ano", je pravděpodobnost toho, že p není prvočíslo, menší než 2−k. Když k = 100, je pravděpodobnost chyby zanedbatelně malá. Poznámka: Lze například odvodit, že pravděpodobnost toho, že počítač bude zasažen během dané mikrosekundy meteoritem, je nejméně 2−100 za předpokladu, že každých 1000 let je meteoritem zničeno alespoň 100 m2 zemského povrchu.
10
