PRŮVODCE LABYRINTEM ALGORITMŮ

Martin Mareš, Tomáš Valla

Vydavatel:
CZ.NIC, z. s. p. o.
Milešovská 5, 130 00 Praha 3
Edice CZ.NIC
www.nic.cz

2. vydání, Praha 2022
Kniha vyšla jako 28. publikace v Edici CZ.NIC.
ISBN 978-80-88168-64-5

© 2017, 2022 Martin Mareš, Tomáš Valla

Toto autorské dílo podléhá licenci Creative Commons BY-ND 4.0 (http://creativecommons.org/licenses/by-nd/4.0/). Dílo však může být překládáno a následně šířeno v písemné či elektronické formě, na území kteréhokoliv státu, za předpokladu, že nedojde ke změně díla a i nadále zůstane zachováno označení autora a prvního vydavatele díla, sdružení CZ.NIC, z. s. p. o. Překlad může být šířen pod licencí CC BY-ND 4.0.

ISBN 978-80-88168-64-5

Sázet elektronickou knihu plnou matematické notace je velké dobrodružství. Standard EPUB k tomu dává jen skrovné možnosti a mnohé čtečky si ho navíc vykládají velmi svérázně. Může se proto stát, že zrovna vaše čtečka některé symboly zobrazí chybně, nebo třeba neodsadí kroky algoritmů. Pokud se to přihodí, zkuste prosím nastavit preferenci písem od vydavatele. V každém případě rádi uslyšíme o vašich zkušenostech na adrese pruvodce@ucw.cz.

Martin Mareš, Tomáš Valla

Průvodce
labyrintem
algoritmů

Edice CZ.NIC

Předmluva vydavatele

Vážení čtenáři,

dostává se vám do rukou druhé, rozšířené vydání knihy Průvodce labyrintem algoritmů. Již samotný fakt, že vzniklo druhé vydání, ukazuje, že kniha je „živá“, nachází si své nové čtenáře, kteří poskytují hodnotnou zpětnou vazbu autorům. To je dáno i faktem, že se kniha stala svým způsobem učebnicí pro související předmět, kteří oba autoři přednášejí.

Jako vydavatele nás těší, že za pět let od svého vzniku se tato kniha stala třetí nejprodávanější knihou z naší edice CZ.NIC, čítající již přes dvacet titulů. Počet stažení elektronické verze této knihy přesahující 20 000 ukazuje, že i v on-line prostoru je o knihu zájem.

Jak již zmínil kolega Ondřej Filip v předmluvě k prvnímu vydání, znalost efektivních algoritmů a datových struktur je bezpochyby jedním z klíčových znaků skutečného programátora. V této oblasti osobně neznám povolanější autoritu, než je náš společný spolužák Martin Mareš. Společně s Tomášem Vallou vytvořili ideální autorskou dvojici, umožňující zkombinovat zkušenosti z jejich přednášek hned na dvou vysokých školách.

Přeji druhému vydání minimálně stejně úspěšnou cestu k vám, jeho čtenářům, jako mělo vydání první.

Jaromír Talíř, CZ.NIC
Praha, 15. srpna 2022

Předmluva autorů

Předmluva autorů

Každý, kdo se pokusí napsat složitější počítačový program, brzy zjistí, že více než na detailech konkrétního programovacího jazyka záleží na tom, jak řešení komplikované úlohy vyjádřit pomocí řady elementárních kroků srozumitelných počítači.

Tomuto vyjádření se obvykle říká algoritmus a právě tím, jak algoritmy navrhovat a analyzovat, se bude zabývat celá tato kniha. Napsali jsme ji pro každého, kdo už umí trochu programovat v jakémkoliv jazyce a chtěl by se naučit algoritmicky myslet. Hodit se může jak studentovi informatiky, tak zkušenému programátorovi z praxe.

Kniha vychází z mnoha let našich přednášek: Martinových na Matematicko-fyzikální fakultě Univerzity Karlovy a Tomášových na Fakultě informačních technologií Českého vysokého učení technického. Kniha pokrývá obsah obou přednášek, ale často se snaží vám čtenářům ukázat i něco navíc – naznačit, jak rozvyprávěný příběh pokračuje.

Jelikož se k analýze algoritmů obvykle používají matematické prostředky, předpokládáme, že čtenáři jsou zběhlí ve středoškolské matematice (logaritmy, exponenciály, jednoduchá kombinatorika) a základech vysokoškolské (jednoduchá lineární algebra a matematická analýza, teorie grafů). Většinou se snažíme vystačit si s co nejjednodušším aparátem, případně čtenáře odkázat na vhodný zdroj, ze kterého se lze aparát doučit. Upozorňujeme, že oproti středoškolským zvyklostem považujeme nulu za přirozené číslo a místo desetinné čárky píšeme tečku.

Algoritmy nezapisujeme v žádném konkrétním programovacím jazyce, nýbrž v takzvaném pseudokódu – abstraktním zápisu, který je příjemně srozumitelný člověku, ale také se dá s minimem úsilí převést do libovolného programovacího jazyka. Na začátku knihy píšeme pseudokódy velmi detailně, později se stávají abstraktnějšími, protože čtenář už dávno pochopil základní obraty a nemá smysl je znovu podrobně rozepisovat.

Nedílnou součástí výkladu jsou cvičení v závěru většiny oddílů. Ponoukají čtenáře k tomu, aby nad myšlenkami z daného oddílu uvažoval a pokusil se je použít k řešení dalších úloh. Pokud si nebudete vědět rady, u některých cvičení najdete odkaz [Nčíslo] na nápovědu v zadní části knihy. Občas je na konci kapitoly ještě jeden oddíl s dalšími úlohami na procvičení látky z celé kapitoly.

Některá cvičení a oddíly knihy jsou označeny jednou nebo dvěma hvězdičkami. To znamená, že se v nich nachází pokročilejší a často také o něco obtížnější materiál. Při prvním čtení je doporučujeme přeskakovat, později si je užijete mnohem více. Mimo jiné proto, že se v nich mohou hodit znalosti z následujících kapitol.

Na konci knihy naleznete rejstřík, který také obsahuje přehled používaného matematického značení. Jednopísmenné značky jsou zařazeny pod příslušnými písmeny, ostatní symboly na začátku rejstříku.

Dodejme ještě, že do každé odborné knihy se přes všechnu snahu autorů vloudí pár chyb. Pokud na nějakou narazíte, dejte nám prosím vědět na adrese pruvodce@ucw.cz, ať ji můžeme v příštím vydání opravit. Seznam všech nalezených chyb budeme udržovat na webové stránce http://pruvodce.ucw.cz/. Tamtéž najdete elektronickou verzi celé knihy.

O druhém vydání

Rádi jsme po pěti letech od prvního vydání využili příležitost knihu „oprášit“ a aktualizovat. Přibyly především datové struktury pro práci s řetězci (suffixová pole a stromy), heuristiky pro hledání cest (algoritmus A* a potenciálové redukce) a randomizované vyhledávací stromy. Na konec knihy jsme doplnili úvod do teorie grafů pro čtenáře, kteří se s grafy dosud nepotkali.

Kromě toho jsme na mnoha místech výklad zjednodušili na základě připomínek od našich studentů i kolegů využívajících knihu při výuce. Děkujeme za ně! Také přibylo mnoho dalších cvičení a nápověd.

Druhé vydání zachovává číslování kapitol a oddílů, všechny nové oddíly jsou přidány na konec příslušné kapitoly. Naopak čísla cvičení zachována nebyla – preferovali jsme udržet související cvičení u sebe.

Doporučená literatura

Rádi bychom zmínili několik knih, jež nás při přednášení a psaní inspirovaly, a doporučili je všem čtenářům, kteří by se rádi o algoritmech dozvěděli více. Mnohá témata zmíněná v naší knize pokrývá monumentální dílo Introduction to Algorithms [2] od Cormena a spol. Učebnice Algorithms [3] od Dasgupty a spol. je méně encyklopedická, ale daleko bližší našemu způsobu uvažování – je psaná neformálně, a přitom přesně. Podobně kniha Algorithm Design [6] od Jona Kleinberga a Évy Tardos, která se výrazně více věnuje randomizovaným algoritmům a partiím na pomezí teorie složitosti. Zajímavé implementační triky se lze naučit z knihy Competitive Programmer's Handbook [7] od Antti Laaksonena.

Českých knih o algoritmech existuje pomálu. Pomineme-li překlady, jsou první a donedávna i poslední učebnicí algoritmizace Algoritmy a programovací techniky [11] od Töpfera. Oproti naší knize se daleko více věnují programátorskému řemeslu a výklad algoritmů ilustrují detailní implementací v Pascalu.

Kdo se chce věnovat řešení algoritmických úloh, najde rozsáhlý archiv na webových stránkách http://ksp.mff.cuni.cz/ Korespondenčního semináře z programování MFF UK a http://mo.mff.cuni.cz/ Matematické olympiády kategorie P. Dalším zajímavým zdrojem úloh je Skienův The Algorithm Design Manual [10].

Partie kombinatoriky a teorie grafů používané při analýze algoritmů pokrývají vynikající Kapitoly z diskrétní matematiky [9] od Matouška a Nešetřila. Aplikacemi grafů v informatice se zabývá také kniha Jiřího Demela [4]. Pokročilejší kombinatorice a asymptotické analýze se věnuje Concrete Mathematics [5] od Grahama, Knutha a Patashnika.

Poděkování

Rádi bychom poděkovali kolegům, kteří si obětavě přečetli mnoho pracovních verzí knihy a přispěli svými radami, připomínkami, opravami a cvičeními. Díky patří Tomáši Gavenčiakovi, Janu Hricovi, Radku Huškovi, Martinu Kouteckému, Vladanu Majerechovi, Jiřímu Matouškovi, Janu Musílkovi, Ondřeji Suchému a Pavlu Töpferovi.

Uvažovat, přednášet a psát o algoritmech nás naučila především léta organizování Korespondenčního semináře z programování a semináře Introduction to problem solving. Z úloh KSP také pochází část našich cvičení. Za inspiraci děkujeme všem minulým i současným organizátorům KSP a IPS, zejména pak Meggy Machové, Zdeňku Dvořákovi, Ondrovi Hlavatému, Karry Hořeňovské, Danovi Kráľovi, Jirkovi Kalvodovi, Vaškovi Končickému, Martinu Krulišovi, Marii Matějka, Michalu Pokornému, Jirkovi Setničkovi, Milanu Strakovi, Jirkovi Škrobánkovi, Vaškovi Šraierovi, Filipu Štědronskému, Michalu Vanerovi a Pavlu Veselému.

Díky patří též studentům, kteří pořizovali zápisy z našich prvních přednášek, sloužící jako inspirace k této knize. Byli to: Kateřina Böhmová, Lucia Banáková, Rudolf Barczi, Peter Bašista, Jakub Břečka, Roman Cinkais, Ján Černý, Michal Demín, Jiří Fajfr, Martin Franců, František Haško, Lukáš Hermann, Ondřej Hoferek, Tomáš Hubík, Josef Chludil, Martin Chytil, Jindřich Ivánek, Karel Jakubec, Petr Jankovský, František Kačmarik, Kamil Kaščák, Matej Klaučo, Pavel Klavík, Tereza Klimošová, Vojtěch Kolomičenko, Michal Kozák, Karel Král, Radoslav Krivák, Vincent Kríž, Vladimír Kudelas, Jiří Kunčar, Martin Kupec, Jiří Machálek, Ľuboš Magic, Bohdan Maslowski, Štěpán Masojídek, Jakub Melka, Jozef Menda, Petr Musil, Jan Návrat, Gábor Ocsovszky, Martin Petr, Oto Petřík, Martin Polák, Markéta Popelová, Daniel Remiš, Dušan Renát, Pavol Rohár, Miroslav Řezáč, Luděk Slinták, Michal Staša, Pavel Taufer, Ondrej Tichý, Radek Tupec, Vojtěch Tůma, Barbora Urbancová, Michal Vachna, Karel Vandas, Radim Vansa, Jan Volec a Jan Záloha.

Za mapu části Vinoře na obrázku 5.2 a automapu z oddílu 6.5 vděčíme projektu Openstreetmap. Pro vykreslení jsme použili experimentální mapový renderer Leo.

V neposlední řadě děkujeme našim rodinám, které se smířily s tím, že tátové tráví večery a noci nad knihou. A také Katedře aplikované matematiky MFF UK a Katedře teoretické informatiky FIT ČVUT za příjemné a velmi inspirující pracovní prostředí.

Přejeme vám příjemné čtení

Martin Mareš

Tomáš Valla

Obsah

1 Příklady na úvod

1  Příklady na úvod

Tématem této knihy má být návrh a analýza algoritmů. Měli bychom tedy nejdříve říci, co to algoritmus je. Formální definice je překvapivě obtížná. Nejspíš se shodneme na tom, že je to nějaký formální postup, jak něco provést, a že by měl být tak podrobný, aby byl srozumitelný i počítači. Jenže detaily už vůbec nejsou tak zřejmé. Proto s pořádným zavedením pojmů ještě kapitolu počkáme a zatím se podíváme na několik konkrétních příkladů algoritmů.

1.1  Úsek s největším součtem

Náš první příklad se bude týkat posloupností. Máme zadanou nějakou posloupnost celých čísel x₁, …, xn a chceme v ní nalézt úsek (tím myslíme souvislou podposloupnost), jehož součet je největší možný. Takovému úseku budeme říkat nejbohatší. Jako výstup nám postačí hodnota součtu, nebude nutné ohlásit přesnou polohu úseku.

Nejprve si rozmyslíme triviální případy: Kdyby všechna zadaná čísla byla kladná, měla by evidentně maximální součet celá vstupní posloupnost. Pokud by naopak byla všechna xi záporná, nejbohatší by byl prázdný úsek, který má nulový součet; všechny ostatní úseky totiž mají součet záporný.

Obecný případ bude komplikovanější: například v posloupnosti

najdeme dva úseky kladných čísel se součtem 9 (totiž 4, 5 a 2, 7), ale dokonce se hodí spojit je přes záporná čísla −1, −5 do jediného úseku se součtem 12. Naopak hodnotu −2 se použít nevyplácí, jelikož přes ní je dosažitelná pouze počáteční jednička, takže bychom si o 1 pohoršili.

Nejpřímočařejší možný algoritmus by téměř doslovně kopíroval zadání: Vyzkoušel by všechny možnosti, kde může úsek začínat a končit, pro každou z nich by spočítal součet prvků v úseku a pak našel z těchto součtů maximum.

Algoritmus MaxSoučet1

Vstup: Posloupnost X = x₁, …, xn uložená v poli

m ← 0 ◃ zatím jsme potkali jen prázdný úsek

Pro i = 1, …, n opakujeme: ◃ i je začátek úseku

Pro j = i, …, n opakujeme: ◃ j je konec úseku

s ← 0 ◃ součet úseku

Pro k = i, …, j opakujeme:

s ← s + xk

m ← max(m, s)

Výstup: Součet m nejbohatšího úseku v X

Pojďme alespoň zhruba odhadnout, jak rychlý tento postup je. Prozkoumáme řádově n² dvojic (začátek, konec) a pro každou z nich strávíme řádově n kroků počítáním součtu. To dohromady dává řádově n³ kroků, což už pro n = 1 000 budou miliardy. Zkusme přijít na rychlejší způsob.

Podívejme se, čím náš první algoritmus tráví nejvíce času. Jistě počítáním součtů. Například sčítá jak úsek xi, …, xj, tak xi, …, xj+1, aniž by využil toho, že druhý součet je prostě o xj+1 vyšší než ten první. Nabízí se zvolit pevný začátek úseku i a pak zkoušet všechny možné konce j od nejlevějšího k nejpravějšímu. Každý další součet pak dovedeme triviálně spočítat z předchozího. Pro jedno i tedy provedeme řádově n kroků, celkově pak řádově n².

Algoritmus MaxSoučet2

Vstup: Posloupnost X = x₁, …, xn uložená v poli

m ← 0 ◃ zatím jsme potkali jen prázdný úsek

Pro i = 1, …, n opakujeme: ◃ i je začátek úseku

s ← 0 ◃ součet úseku

Pro j = i, …, n opakujeme: ◃ j je konec úseku

s ← s + xj

m ← max(m, s)

Výstup: Součet m nejbohatšího úseku v X

Myšlenka průběžného přepočítávání se ale dá využít i lépe, totiž na celou úlohu. Uvažujme, jak se změní výsledek, když ke vstupu x₁, …, xn přidáme ještě xn+1. Všechny úseky původního vstupu zůstanou zachovány a navíc vzniknou nové úseky tvaru xi, …, xn+1. Chceme tedy ověřit, zda součet některého z nových koncových úseků nepřekročil dosavadní maximum.

Stačí s maximem porovnat součet nejbohatšího z koncových úseků. Ten také neumíme najít v konstantním čase, ale pojďme tutéž myšlenku použít ještě jednou. Jak se změní koncové úseky po přidání xn? Všem stávajícím koncovým úsekům stoupne součet o xn a navíc vznikne nový koncový úsek obsahující samotné xn. Maximální součet je proto roven buď předchozímu maximálnímu součtu plus xn, nebo samotnému xn – podle toho, co je větší.

Označíme-li si tedy k maximální součet koncového úseku, přidáním nového prvku se tato hodnota změní na max(k + xn, xn) = xn + max(k, 0). Jinými slovy: počítáme průběžné součty, ale pokud součet klesne pod nulu, tak ho vynulujeme. Hledaný maximální součet m je pak maximem ze všech průběžných součtů. Tímto principem se řídí náš třetí algoritmus:

Algoritmus MaxSoučet3

Vstup: Posloupnost X = x₁, …, xn uložená v poli

m ← 0 ◃ prázdný úsek je tu vždy

k ← 0 ◃ maximální součet koncového úseku

Pro i od 1 do n opakujeme:

k ← max(k, 0) + xi

m ← max(m, k)

Výstup: Součet m nejbohatšího úseku v X

V každém průchodu cyklem potřebujeme na přepočítání proměnných k a m pouze konstantně mnoho operací. Celkem jich tedy algoritmus provede řádově n, tedy lineárně s velikostí vstupu. Hodnoty ze vstupu navíc potřebuje jen jednou, takže je může číst postupně a vystačí si tudíž s konstantním množstvím paměti.

Dodejme ještě, že úvaha typu „jak se změní výstup, když na konec vstupu přidáme další prvek?“ je poměrně častá. Vysloužila si proto zvláštní jméno, algoritmům tohoto druhu se říká inkrementální. Ještě se s nimi několikrát potkáme.

Cvičení

1. Upravte algoritmus MaxSoučet3, aby oznámil nejen maximální součet, ale také polohu příslušného úseku.

2. Na vstupu je text složený z písmen české abecedy a mezer. Vymyslete algoritmus, který najde nejdelší úsek textu, v němž se žádné písmeno neopakuje.

3. Najděte v českém textu nejkratší úsek, který obsahuje všechna písmena abecedy. Malá a velká písmena nerozlišujte.

4.* Úsek posloupnosti je k-hladký (pro k ≥ 0), pokud se každé dva jeho prvky liší nejvýše o k. Popište co nejefektivnější algoritmus pro hledání nejdelšího k-hladkého úseku.

5. Jak spočítat kombinační číslo (n k)? Výpočtu přímo podle definice brání potenciálně obrovské mezivýsledky (až n!), které se nevejdou do celočíselné proměnné. Navrhněte algoritmus, který si vystačí s čísly omezenými n-násobkem výsledku. [N95]

1.2  Binární vyhledávání

Jak se hledá slovo ve slovníku? Jistě můžeme slovníkem listovat stránku po stránce a pečlivě zkoumat slovo po slovu. Jsme-li dostatečně trpěliví, hledané slovo nakonec najdeme, nebo slovník skončí a můžeme si být jistí, že slovo neobsahoval.

Listování slovníkem může být dobrá zábava na dlouhé zimní večery (nebo spíš na celou polární noc), ale obvykle hledáme jinak: otevřeme slovník někde uprostřed, podíváme se, jak blízko jsme k hledanému slovu, a na základě toho nadále aplikujeme stejný postup buďto v levé, anebo pravé části rozevřeného slovníku.

Nyní se tento postup pokusíme popsat precizně. Získáme tak algoritmus, kterému se říká binární vyhledávání nebo také hledání půlením intervalu. Na vstupu dostaneme nějakou uspořádanou posloupnost x₁ ≤ x₂ ≤ … ≤ xn a hledaný prvek y.

Postupujeme takto: pamatujeme si interval xℓ, …, xr, ve kterém se prvek může nacházet. Na počátku je ℓ = 1 a r = n. V každém kroku vybereme prvek ležící uprostřed (nebo přibližně uprostřed, pokud je prvků sudý počet). Ten bude sloužit jako mezník oddělující levou polovinu od pravé. Pokud se mezník rovná hledanému y, můžeme hned úspěšně skončit. Pokud je menší než y, znamená to, že y se může nacházet jen napravo od něj – všechny prvky nalevo jsou menší než mezník, tím pádem i menší než y. A pokud je naopak mezník větší než y, víme, že y se může nacházet pouze v levé polovině.

Postupně tedy interval [ℓ, r] zmenšujeme na polovinu, čtvrtinu, atd., až se dostaneme do stavu, kdy prohledávaný úsek pole má velikost jednoho prvku, nebo je dokonce prázdný. Pak už se snadno přesvědčíme, zda jsme hledaný prvek našli.

V pseudokódu náš algoritmus vypadá následovně.

Algoritmus BinSearch (hledání půlením intervalu)

Vstup: Uspořádaná posloupnost x₁ ≤ … ≤ xn, hledaný prvek y

ℓ ← 1, r ← n ◃ xℓ, …, xr tvoří prohledávaný úsek pole

Dokud je ℓ ≤ r:

s ← ⌊(ℓ + r)/2⌋ ◃ střed prohledávaného úseku

Pokud je y = xs: vrátíme s a skončíme.

Pokud je y > xs:

ℓ ← s + 1 ◃ přesouváme se napravo

Jinak:

r ← s − 1 ◃ přesouváme se nalevo

Vrátíme 0. ◃ nenašli jsme

Výstup: Index hledaného prvku, případně 0, pokud prvek v poli není

Pokusme se poctivě dokázat, že algoritmus funguje. Především nahlédneme, že výpočet se vždy zastaví: v každém průchodu cyklem zmenšíme prohledávaný úsek alespoň o 1. Korektnost pak plyne z toho, že kdykoliv oblast zmenšíme, odstraníme z ní jen prvky, které jsou zaručeně různé od y. Jakmile tedy algoritmus skončí, buďto jsme y našli, nebo jsme naopak vyloučili všechny možnosti, kde by mohlo být.

Nyní ukážeme, že binární vyhledávání je mnohem rychlejší než probrání všech prvků.

Věta: Při hledání v posloupnosti délky n provede algoritmus BinSearch nejvýše log₂ n průchodů cyklem.

Důkaz: Stačí nahlédnout, že v každém průchodu cyklem se velikost prohledávaného úseku zmenší alespoň dvakrát. Proto po k průchodech úsek obsahuje nejvýše n/2k prvků, takže pro k > log₂ n je úsek nutně prázdný.  □

Na závěr dodejme, že prvky naší posloupnosti vůbec nemusí být čísla: stačí, aby to byly libovolné objekty, které jsme schopni mezi sebou porovnávat. Třeba slova ve slovníku. V oddílu 3.3 navíc dokážeme, že logaritmický počet porovnání je nejlepší možný.

Dvojice se zadaným součtem

Podívejme se ještě na jeden příbuzný problém. Opět dostaneme na vstupu nějakou uspořádanou posloupnost x₁ ≤ x₂ ≤ … ≤ xn a číslo s. Tentokrát ovšem nehledáme jeden prvek, nýbrž dva (ne nutně různé), jejichž součet je s.

Řešení „hrubou silou“ by zkoušelo sečíst všechny dvojice xi + xj, ale těch je řádově n². Pokud ovšem zvolíme nějaké xi, víme, že xj musí být rovno s − xi. Můžeme tedy vyzkoušet všechna xi a pokaždé půlením intervalu hledat s − xi. Každé vyhledávání spotřebuje řádově log₂ n kroků, celkově jich tedy bude řádově n ⋅ log₂ n.

To je mnohem lepší, ale ještě ne optimální. Představme si, že k x₁ hledáme s − x₁. Tentokrát ale nebudeme hledat binárně, nýbrž pěkně prvek po prvku od konce pole. Dokud jsou prvky větší, přeskakujeme je. Jakmile narazíme na prvek menší, víme, že už se můžeme zastavit, protože dál už budou jen samé menší.

Pozici, kde jsme skončili, si zapamatujeme. Máme tedy nějaké j takové, že xj < s − x₁ < xj+1. (Pokud protestujete, že xj+1 může ležet mimo posloupnost, představte si za koncem posloupnosti ještě +∞.)

Nyní přejdeme na x₂ a hledáme s − x₂. Jelikož x₂ ≥ x₁, musí být s − x₂ ≤ s − x₁. Všechna čísla, která byla větší než s − x₁ jsou tedy také větší než s − x₂, takže v nich nemá smysl hledat znovu. Proto můžeme pokračovat od zapamatované pozice j dále doleva. Pak si zase zapamatujeme, kde jsme skončili, což se bude hodit pro x₃, a tak dále.

Existuje hezčí způsob, jak formulovat totéž. Říká se mu metoda dvou jezdců. Máme dva indexy: levý a pravý. Levý index i popisuje, které xi zrovna zkoušíme jako první člen dvojice: začíná na pozici 1 a pohybuje se doprava. Pravý index j ukazuje na místo, kde jsme se zastavili při hledaní s − xi: začíná na pozici n a postupuje doleva.

Kdykoliv je xj > s − xi, posuneme j doleva (pokračujeme v hledání s − xi). Je-li naopak xj < s − xi, posuneme i doprava (s − xi se v posloupnosti určitě nenachází, zkoušíme další xi). Takto pokračujeme, dokud buďto neobjevíme hledanou dvojici, nebo se jezdci nesetkají – tehdy dvojice zaručeně neexistuje.

Algoritmus DvojiceSeSoučtem

Vstup: Uspořádaná posloupnost x₁ ≤ … ≤ xn, hledaný součet s

i ← 1, j ← n

Dokud i ≤ j:

Je-li xi + xj = s:

Vrátíme jako výsledek dvojici (i, j).

Jinak je-li xi + xj < s: ◃ totéž jako xi < s − xj

i ← i + 1

Jinak:

j ← j − 1

Ohlásíme neúspěch.

Výstup: Indexy i a j, pro něž je xi + xj = s, nebo neúspěch

Snadno nahlédneme, že cyklus proběhne nejvýše n-krát. Vzdálenost jezdců j − i se totiž při každém průchodu cyklem sníží o 1. Po maximálně n krocích se proto jezdci potkají.

Překonali jsme tedy rychlost opakovaného binárního vyhledávání. Povedlo se nám to díky tomu, že mezi hledanými prvky existoval nějaký vztah: konkrétně každý prvek byl menší nebo roven předchozímu.

Cvičení

1. Rozmyslete si, jak se bude chovat algoritmus binárního vyhledávání, pokud se bude hledaný prvek v posloupnosti nacházet vícekrát. Algoritmus upravte, aby vždy vracel první výskyt hledaného prvku (ne jen libovolný).

2. Upravte binární vyhledávání, aby v případě, kdy hledaný prvek v posloupnosti není, nahlásilo nejbližší větší prvek.

3.* Nekonečné vyhledávání: Popište algoritmus, který v nekonečné posloupnosti x₁ < x₂ < … najde pozici i takovou, že xi ≤ y < xi+1. Počet kroků hledání by neměl přesáhnout řádově log₂ i.

4. Lokální minimum: Je dána posloupnost +∞ = x₀, x₁, …, xn, xn+1 = +∞. O prvku xi řekneme, že je lokálním minimem, pokud xi−1 ≥ xi ≤ xi+1. Navrhněte co nejrychlejší algoritmus, který nějaké lokální minimum najde.

5. Součet úseku: Je dána posloupnost x₁, …, xn kladných čísel a číslo s. Hledáme i a j taková, že xi + … + xj = s. Navrhněte co nejefektivnější algoritmus. [N65]

6.* Jak se změní úloha z předchozího cvičení, pokud povolíme i záporná čísla?

7. Implicitní vstup: Posloupnost, v níž binárně hledáme, nemusí být nutně celá uložená v paměti. Stačí, když se tak dokážeme dostatečně přesvědčivě tvářit: kdykoliv se algoritmus zeptá na hodnotu nějakého prvku, rychle ho vyrobíme. Zkuste tímto způsobem spočítat celočíselnou odmocninu z čísla x. To je největší y takové, že y² ≤ x.

8. První díra: Na vstupu jsme dostali rostoucí posloupnost přirozených čísel. Chceme najít nejmenší přirozené číslo, které v ní chybí. Vymyslete, jak k tomu přesvědčit binární vyhledávání.

9.* Opět hledáme nejmenší chybějící číslo, ale tentokrát na vstupu dostaneme neuspořádanou posloupnost navzájem různých přirozených čísel. Posloupnost nesmíme měnit a kromě ní máme k dispozici jenom konstantně mnoho paměti. [N12]

10. Monotónní predikáty: Na předchozích několik cvičení se můžeme dívat trochu obecněji. Mějme nějakou vlastnost φ, kterou všechna přirozená čísla od 0 do nějaké hranice k mají a žádná větší nemají. Popište, jak binárním vyhledáváním zjistit, kde se nachází tato hranice.

11. Rovnoměrná data: Mějme pole délky n. Na každé pozici se může vyskytovat libovolné celé číslo z rozsahu 1 až k. Čísla vybíráme rovnoměrně náhodně (všechny hodnoty mají stejnou pravděpodobnost). Následně pole setřídíme a budeme v něm chtít vyhledávat. Zkuste upravit binární vyhledávání, aby pro tyto vstupy fungovalo v průměru rychleji. [N91]

12.* Kolik porovnání provede algoritmus z předchozího cvičení v průměru?

13.* Může se stát, že výše uvedený algoritmus nedostane pěkná data. Můžeme mu nějak pomoci, aby nebyl ani v takovém případě o mnoho horší než binární vyhledávání? [N38]

1.3  Euklidův algoritmus

Pro další příklad se vypravíme do starověké Alexandrie. Tam žil ve 3. století před naším letopočtem filosof Euklides (Ευκλειδης) a stvořil jeden z nejstarších algoritmů.⟨1⟩ Ten slouží k výpočtu největšího společného dělitele a používá se dodnes.

Značení: Největšího společného dělitele celých kladných čísel x a y budeme značit gcd(x, y) podle anglického Greatest Common Divisor.

Nejprve si všimneme několika zajímavých vlastností funkce gcd.

Lemma G: Pro všechna celá kladná čísla x a y platí:

gcd(x, x) = x,

gcd(x, y) = gcd(y, x),

gcd(x, y) = gcd(x − y, y) pro x > y.

Důkaz: První dvě vlastnosti jsou zřejmé z definice. Třetí dokážeme v silnější podobě: ukážeme, že dvojice (x, y) a (x − y, y) sdílejí množinu všech společných dělitelů, tedy i největšího z nich.

Pokud nějaké d je společným dělitelem čísel x a y, musí platit x = dx' a y = dy' pro vhodné x' a y'. Nyní stačí rozepsat x − y = dx' − dy' = d(x' − y') a hned je jasné, že d dělí i x − y. Naopak pokud d dělí jak x − y, tak y, musí existovat čísla t' a y' taková, že x − y = dt' a y = dy'. Zapíšeme tedy x jako (x − y) + y, což je rovno dt' + dy' = d(t' + y'), a to je dělitelné d.  □

Díky lemmatu můžeme gcd počítat tak, že opakovaně odečítáme menší číslo od většího. Jakmile se obě čísla vyrovnají, jsou rovna největšímu společnému děliteli. Algoritmus nyní zapíšeme v pseudokódu.

Algoritmus OdčítacíEuklides

Vstup: Celá kladná čísla x a y

a ← x, b ← y

Dokud a ≠ b, opakujeme:

Pokud a > b:

a ← a − b

Jinak:

b ← b − a

Výstup: Největší společný dělitel a = gcd(x, y)

Nyní bychom měli dokázat, že algoritmus funguje. Důkaz rozdělíme na dvě části:

Lemma Z: Algoritmus se vždy zastaví.

Důkaz: Sledujme, jak se vyvíjí součet a + b. Na počátku výpočtu je roven x + y, každým průchodem cyklem se sníží alespoň o 1. Přitom zůstává stále nezáporný, takže průchodů nastane nejvýše x + y.  □

Lemma S: Pokud se algoritmus zastaví, vydá správný výsledek.

Důkaz: Dokážeme následující invariant, neboli tvrzení, které platí po celou dobu výpočtu:

Invariant: gcd(a, b) = gcd(x, y).

Důkaz: Obvyklý způsob důkazu invariantů je indukce podle počtu kroků výpočtu. Na počátku je a = x a b = y, takže invariant jistě platí. V každém průchodu cyklem se pak díky vlastnostem 2 a 3 z lemmatu G platnost invariantu zachovává.  □

Z invariantu plyne, že na konci výpočtu je gcd(a, a) = gcd(x, y). Zároveň díky vlastnosti 1 z lemmatu G platí gcd(a, a) = a.  □

Víme tedy, že algoritmus je funkční. To bohužel neznamená, že je použitelný: například pro x = 1 000 000 a y = 2 vytrvale odčítá y od x, až po 499 999 krocích vítězoslavně ohlásí, že největší společný dělitel je roven 2.

Stačí si ale všimnout, že opakovaným odčítáním b od a dostaneme zbytek po dělení čísla a číslem b. Jen si musíme dát pozor, že pro a dělitelné b se zastavíme až na nule. To odpovídá tomu, že algoritmus provede ještě jedno odečtení navíc, takže skončí, až když se jedno z čísel vynuluje. Nahrazením odčítání za dělení se zbytkem získáme následující algoritmus. Když se v současnosti hovoří o Euklidově algoritmu, obvykle se myslí tento.

Algoritmus Euklides

Vstup: Celá kladná čísla x a y

a ← x, b ← y

Opakujeme:

Pokud a < b, prohodíme a s b.

Pokud b = 0, vyskočíme z cyklu.

a ← a mod b ◃ zbytek po dělení

Výstup: Největší společný dělitel a = gcd(x, y)

Správnost je zřejmá: výpočet nového algoritmu odpovídá výpočtu algoritmu předchozího, jen občas provedeme několik původních kroků najednou. Zajímavé ovšem je, že na první pohled nenápadnou úpravou jsme algoritmus podstatně zrychlili:

Lemma R: Euklidův algoritmus provede nejvýše log₂ x + log₂ y + 1 průchodů cyklem.

Důkaz: Vývoj výpočtu budeme sledovat prostřednictvím součinu ab:

Tvrzení: Součin ab po každém průchodu cyklem klesne alespoň dvakrát.

Důkaz: Kroky 3 a 4 součin ab nemění. Ve zbývajícím kroku 5 platí a ≥ b a b se evidentně nezmění. Ukážeme, že a klesne alespoň dvakrát, takže ab také. Rozebereme dva případy:

b ≤ a/2. Tehdy platí a mod b < b ≤ a/2.

b > a/2. Pak je a mod b = a − b < a − (a/2) = a/2.  □

Na počátku výpočtu je ab = xy a díky právě dokázanému tvrzení po k průchodech cyklem musí platit ab ≤ xy/2k. Kromě posledního neúplného průchodu cyklem ovšem ab nikdy neklesne pod 1, takže k může být nejvýše log₂ xy = log₂ x + log₂ y.  □

Shrnutím všeho, co jsme o algoritmu zjistili, získáme následující větu:

Věta: Euklidův algoritmus vypočte největšího společného dělitele čísel x a y. Provede přitom nejvýše c ⋅ (log₂ x + log₂ y + 1) aritmetických operací, kde c je konstanta.

Cvičení

1. Největšího společného dělitele bychom také mohli počítat pomocí prvočíselného rozkladu čísel x a y. Rozmyslete si, jak by se to dělalo a proč je to pro velká čísla velmi nepraktické.

2. V kroku 3 algoritmu Euklides není potřeba porovnávat. Nahlédněte, že pokud bychom a s b prohodili pokaždé, vyjde také správný výsledek, jen nás to bude v nejhorším případě stát o jeden průchod cyklem navíc.

3. Dokažte, že počet průchodů cyklem je nejvýše 2 log₂ min(x, y) + 2.

4. Pro každé x a y existují celá čísla α a β taková, že gcd(x, y) = αx + βy. Těmto číslům se říká Bézoutovy koeficienty. Upravte Euklidův algoritmus, aby je vypočetl.

5. Pomocí předchozího cvičení můžeme řešit lineární kongruence. Pro daná a a n chceme najít x, aby platilo ax mod n = 1. To znamená, že ax a 1 se liší o násobek n, tedy ax + ny = 1 pro nějaké y. Pokud je gcd(a, n) = 1, pak x a y jsou Bézoutovy koeficienty, které to dosvědčí. Je-li gcd(a, n) ≠ 1, nemůže mít rovnice řešení, protože levá strana je vždy dělitelná tímto gcd, zatímco pravá nikoliv. Jak najít řešení obecnější rovnice ax mod n = b?

6. Nabízí se otázka, není-li logaritmický odhad počtu operací z naší věty příliš velkorysý. Abyste na ni odpověděli, najděte funkci f, která roste nejvýše exponenciálně a při výpočtu gcd(f(n), f(n + 1)) nastane právě n průchodů cyklem. [N70]

7. Binární algoritmus na výpočet gcd funguje takto: Pokud x i y jsou sudá, pak gcd(x, y) = 2 gcd(x/2, y/2). Je-li x sudé a y liché, pak gcd(x, y) = gcd(x/2, y). Jsou-li obě lichá, odečteme menší od většího. Zastavíme se, až bude x = y. Dokažte, že tento algoritmus funguje a že provede nejvýše c ⋅ (log₂ x + log₂ y) kroků pro vhodnou konstantu c.

8.* Mějme permutaci π na množině {1, …, n}. Definujme její mocninu následovně: π⁰(x) = x, πi+1(x) = π(πi(x)). Najděte nejmenší k > 0 takové, že πk = π⁰. [N42]

1.4  Fibonacciho čísla a rychlé umocňování

Dovolíme si ještě jednu historickou exkurzi, tentokrát do Pisy, kde na začátku 13. století žil jistý Leonardo řečený Fibonacci.⟨2⟩ Příštím generacím zanechal zejména svou posloupnost.

Definice: Fibonacciho posloupnost F₀, F₁, F₂, … je definována následovně:

Příklad: Prvních 11 Fibonacciho čísel zní 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Pokud chceme spočítat Fn, můžeme samozřejmě vyjít z definice a postupně sestrojit prvních n členů posloupnosti. To nicméně vyžaduje řádově n operací, takže se nabízí otázka, zda to lze rychleji. V moudrých knihách nalezneme následující větu:

Věta (kouzelná formule): Pro každé n ≥ 0 platí:

Důkaz: Laskavý, nicméně trpělivý čtenář jej provede indukcí podle n. Jak na kouzelnou formuli přijít, naznačíme v cvičení 3.  □

Dobrá, ale jak nám formule pomůže, když pro výpočet n-té mocniny potřebujeme n − 1 násobení? Inu nepotřebujeme, následující algoritmus to zvládne rychleji:

Algoritmus Mocnina

Vstup: Reálné číslo x, celé kladné n

Pokud n = 0, vrátíme výsledek 1.

t ← Mocnina(x, ⌊n/2⌋)

Pokud n je sudé, vrátíme t ⋅ t.

Jinak vrátíme t ⋅ t ⋅ x.

Výstup: xn

Lemma: Algoritmus Mocnina vypočte xn pomocí nejvýše 2 log₂ n + 2 násobení.

Důkaz: Správnost je evidentní z toho, že x2k = (xk)² a x2k+1 = x2k ⋅ x. Co se počtu operací týče: Každé rekurzivní volání redukuje n alespoň dvakrát, takže po nejvýše log₂ n voláních musíme dostat jedničku a po jednom dalším nulu. Hloubka rekurze je tedy log₂ n + 1 a na každé úrovni rekurze spotřebujeme nejvýše 2 násobení.  □

To dává elegantní algoritmus pro výpočet Fn pomocí řádově log₂ n operací. Jen je bohužel pro praktické počítání nepoužitelný: Zlatý řez (1 + √5)/2 ≐ 1.618 034 je iracionální a pro vysoké hodnoty n bychom ho potřebovali znát velice přesně. To neumíme dostatečně rychle. Zkusíme to tedy menší oklikou.

Po Fibonacciho posloupnosti budeme posouvat okénkem, skrz které budou vidět právě dvě čísla. Pokud zrovna vidíme čísla Fn, Fn+1, v dalším kroku uvidíme Fn+1, Fn+2 = Fn+1 + Fn. To znamená, že posunutí provede s okénkem nějakou lineární transformaci a každá taková jde zapsat jako násobení maticí. Dostaneme:

Levou matici označíme F a nahlédneme, že násobení okénka n-tou mocninou této matice musí okénko posouvat o n pozic. Tudíž platí:

Nyní stačí využít toho, že násobení matic je asociativní. Proto můžeme n-tou mocninu matice vypočítat obdobou algoritmu Mocnina a vystačíme si s řádově log n maticovými násobeními. Jelikož pracujeme s maticemi konstantní velikosti, obnáší každé násobení matic jen konstantní počet operací s čísly. Všechny matice jsou příjemně celočíselné.

Proto platí:

Věta: n-té Fibonacciho číslo lze spočítat pomocí řádově log n celočíselných aritmetických operací.

Cvičení

1. Naprogramujte funkci Mocnina nerekurzivně. Může pomoci převést exponent do dvojkové soustavy.

2. Uvažujme obecnou lineární rekurenci řádu k: A₀, …, Ak−1 jsou dána pevně, An+k = α₁An+k−1 + α₂An+k−2 + … + αkAn pro konstanty α₁, …, αk. Vymyslete efektivní algoritmus na výpočet An, nejlépe pomocí řádově log₂ n operací.

3.* Jak odvodit kouzelnou formuli: Uvažujme množinu všech posloupností, které splňují rekurentní vztah An+2 = An+1 + An, ale mohou se lišit hodnotami A₀ a A₁. Tato množina tvoří vektorový prostor, přičemž posloupnosti sčítáme a násobíme skalárem po složkách a roli nulového vektoru hraje posloupnost samých nul. Ukažte, že tento prostor má dimenzi 2 a sestrojte jeho bázi v podobě exponenciálních posloupností tvaru An = αn. Fibonacciho posloupnost pak zapište jako lineární kombinaci prvků této báze.

4. Dokažte, že Fn+2 ≥ φn, kde φ = (1 + √5)/2 ≐ 1.618 034.

5.* Algoritmy založené na explicitní formuli pro Fn jsme odmítli, protože potřebovaly počítat s iracionálními čísly. To bylo poněkud ukvapené. Dokažte, že čísla tvaru a + b√5, kde a, b ∈ ℚ jsou uzavřená na sčítání, odčítání, násobení i dělení. K výpočtu formule si tedy vystačíme s racionálními čísly, dokonce pouze typu p/2q, kde p a q jsou celá. Odvoďte z toho jiný logaritmický algoritmus.

6.* Pro ctitele lineární algebry: Jelikož matice F má dvě různá vlastní čísla, můžeme ji diagonalizovat. Platí tedy F = SΛS⁻¹ pro nějakou regulární matici S přechodu mezi bázemi a diagonální matici vlastních čísel Λ. Pak je Fn = SΛnS⁻¹. Odvoďte z tohoto vztahu kouzlenou formuli (zlomky s odmocninami jsou vlastní čísla).