Téma t4: Algoritmy od nuly (do $n$)

Zadáno v čísle 25.1.

Zadání

Obsah:

Stavíme počítač

Rekurze

 


Stavíme počítač

Slovo úvodem

Jak je již z názvu patrné, v našem témátku se budeme zabývat algoritmy. Co je to takový algoritmus? Žádná oficiální definice neexistuje. Dá se třeba říct, že je to přesný popis postupu, jak něco udělat. V tomto pojetí by algoritmem mohl být třeba dobře popsaný recept na smažení palačinek nebo návod na složení židle z IKEA. My se ale omezíme pouze na algoritmy, které jsou ve výsledku určeny pro zpracování počítačem. Po počítači nemůžeme chtít, aby nám usmažil palačinky (tedy, chtít to samozřejmě můžeme). Co po něm naopak chtít budeme, je například sečíst dvě čísla nebo určit, jestli se v posloupnosti čísel vyskytuje dané číslo. Náš algoritmus bude mít vždy vstup (data, se kterými má počítat) a výstup (výsledek). V případě prvního algoritmu by tedy vstupem byla dvě čísla a výstupem jejich součet, vstupem pro druhý algoritmus by byla posloupnost $n$ čísel a hledané číslo $k$ a výstupem informace, zda se číslo $k$ v posloupnosti vyskytuje, případně na které pozici.

Během řešení témátka se budeme snažit pro různé problémy vymyslet algoritmy, které vždy nejen vypíší správný výsledek, ale udělají to v co nejkratším čase. Algoritmus, který odpovídá vždy správně, ale výpočet by mu na dnešních počítačích již pro krátké vstupy trval několik miliard let, pro nás, jak jistě uznáte, není příliš užitečný (a brzy uvidíte, že omylem vymyslet takový algoritmus není vůbec složité).

Při vymýšlení algoritmů budeme, jak název napovídá, začínat úplně od nuly. Body tedy dáváme za to, že jste vymysleli řešení, a ne za sepsání algoritmu, který jste již dobře znali. Také věříme, že M&Mko řešíte hlavně proto, abyste se něco nového naučili (a ne jen kvůli bodům). Pokud tedy řešení některých zde zmíněných problémů znáte, pusťte se raději do jiného témátka nebo jiné úložky tohoto témátka, které pro vás budou větší výzvou, nebo si vhodnou úložku k řešení sami vymyslete.

Počítač

Algoritmy nebudeme spouštět na skutečném počítači – museli bychom brát ohled na spoustu technických detailů, které by nám zabraňovaly soustředit se na samotný algoritmus. Místo toho si tedy vymyslíme vlastní teoretický model počítače. Budeme od něj chtít, aby byl co nejjednodušší a aby zároveň jeho fungování co nejlépe odpovídalo skutečnému počítači (tedy aby algoritmy, které jsou na něm rychlé, byly rychlé i na skutečném počítači a naopak).

Protože zavést takový model od nuly dá trochu práci, ukážeme vám nejdříve jeho verzi, která bude obsahovat o trochu pokročilejší konstrukce, zato bude jednodušší na pochopení a používání. Nemusíte se ale bát, že bychom vás o skutečně minimalistický model ochudili – naleznete ho na konci tohoto textu.

Náš počítač má paměť, do které si můžeme ukládat proměnné. Proměnná má vždy nějaké jméno a je v ní uloženo jedno celé číslo. Počítač umí počítat (tedy provádět operace $+$, $-$, $\cdot $, $/$) s čísly uloženými v proměnných a přiřazovat je do jiných proměnných. Protože umíme do proměnných ukládat jen celá čísla, funguje dělení jako dělení se zbytkem, ale zbytek se nikam neukládá (tedy $8/3 = 2$). Na první pohled by se mohlo zdát, že je velmi omezující, že umíme pracovat pouze s celými čísly. Můžete si ale zkusit rozmyslet, že třeba text nebo racionální čísla se dají jednoduše zakódovat pomocí celých čísel.

Když chceme na našem modelu něco spočítat, rozepíšeme náš algoritmus jako jednotlivé instrukce, které má počítač provést, dáme mu je a on je postupně jednu po druhé provádí. Takovému seznamu instrukcí říkáme kód nebo program. Může vypadat například takto:

  1.     a $\gets $ 4 (do proměnné a přiřaď číslo 4)
  2.     b $\gets $ 5 (do proměnné b přiřaď 5)
  3.     soucet $\gets $ a $+$ b (do proměnné soucet přiřaď součet a $+$ b, tedy číslo 9)

Náš program sčítá čísla. Sčítá ale vždy jen čísla 4 a 5, což není moc užitečné. Potřebovali bychom, aby náš algoritmus (sečtení dvou čísel) šlo spustit pro libovolný vstup (tedy pro libovolná 2 čísla) a nemuseli jsme kvůli tomu psát pokaždé nový program. V praxi bychom museli vstup nějak načíst (třeba z klávesnice či souboru). My budeme předpokládat, že máme instrukci na načtení čísla ze vstupu a vypsání čísla nebo textu na výstup. Program tedy bude vypadat následovně:

  1.     a $\gets $ přečti číslo
  2.     b $\gets $ přečti číslo
  3.     soucet $\gets $ a $+$ b
  4.     Vypiš soucet

Vezměme si nyní další problém z úvodu tohoto textu. Chceme najít určené číslo v posloupnosti délky $n$. Abychom mohli problém vyřešit, museli bychom jako vstup dostat kromě čísla $n$ a čísla, které hledáme, ještě dalších $n$ proměnných – prvky posloupnosti. Stejně tak na výstup bychom někdy mohli potřebovat vypsat třeba $n$ proměnných. Pojmenovávání $n$ proměnných by bylo poněkud nepraktické, proto si zavedeme konstrukt, kterému budeme říkat pole. Pole je prostě pojmenovaná posloupnost celých čísel, která má předem určenou délku. V informatice je zvykem číslovat prvky pole od nuly a my budeme tento zvyk dodržovat. K prvkům pole budeme přistupovat tak, že za název pole napíšeme pozici příslušného prvku, tedy např. seznam[8] je devátý prvek v poli seznam (protože číslujeme od nuly). Jednotlivé prvky pole se pak chovají jako proměnné, a můžeme s nimi tedy dělat to, co s proměnnými – sčítat, odčítat, násobit, dělit (celočíselně), přiřazovat do nich, ale nejde třeba naráz přičíst jedničku ke všem číslům v poli. Pole navíc umí oproti proměnným to, že ho můžeme indexovat proměnnou. Tedy pokud je třeba v proměnné a hodnota 8, pak seznam[a] je to samé, co seznam[8]. Také nesmíme zapomenout, že u pole musí být určena maximální délka, nemůžeme tedy pole rovnou používat (jak to děláme u proměnných), ale musíme počítači napřed říct, aby vyrobil pole dané délky, tedy např. „vyrob pole seznam délky $n$“ a až poté „seznam[i] $\gets $ 13“.

Chybí nám ještě poslední dvě instrukce – podmínka a cyklus.

Podmínka obsahuje nějaký výraz, u kterého lze určit, zda je, či není pravdivý. Výraz má tvar „proměnná nebo číslo $<$, $>$, $\ge $, $\le $, $=$ jiná proměnná nebo číslo“ (např. a $>$ 0). Můžeme také použít negaci a spojit více výrazů pomocí OR, nebo AND1. Pod podmínku pak napíšeme část kódu, která se má provést, pokud podmínka platí, a volitelně i část kódu, která se má provést, pokud podmínka neplatí. Můžeme tedy napsat:

  1.     a $\gets $ vstup
  2.     Pokud (a$/$2)$\cdot $2 $=$ a:
  3.         Vypiš „Vstup je sudý“
  4.     Jinak:
  5.         Vypiš „Vstup je lichý“

Všimněme si, že u lichých čísel se podíl při dělení dvojkou zaokrouhlí dolů, a tedy opravdu nenastane v podmínce rovnost.

Nyní si zavedeme další konstrukt. Budeme mu říkat cyklus a vypadá následovně: Dokud platí „podmínka“, tak dělej „část kódu, která se má provádět“. Cyklus můžeme použít například k napsání programu, který násobí dvě přirozená čísla, aniž by použil operaci násobení.

  1.     a $\gets $ vstup
  2.     b $\gets $ vstup
  3.     pocetScitani $\gets $ 0
  4.     soucin $\gets $ 0
  5.     Dokud (pocetScitani $<$ b) tak:
  6.         soucin $\gets $ soucin $+$ a
  7.         pocetScitani $\gets $ pocetScitani $+$ 1
  8.     Vypiš soucin

To je zatím k našemu modelu vše. Pojďme si teď zkusit nějaký užitečný algoritmus napsat.

Algoritmus – hledání čísla v poli

Nyní si ukážeme jednoduchý algoritmus, který zjistí, zda se v posloupnosti čísel nachází číslo 42. (Zatím nás nebude zajímat, na které pozici je. Můžete si rozmyslet, jak algoritmus upravit, abychom pozici zjistili.) Budeme předpokládat, že víme, kolik čísel dostaneme. Pomocí cyklu si pak ze vstupu uložíme čísla do pole. (Tento technický detail nebudeme pokaždé zmiňovat – dále už budeme vždy předpokládat, že vstup máme na začátku uložen v paměti.)

Pomocí cyklu budeme postupně procházet celé pole. Vytvoříme si proměnné pozice a nalezeno. V proměnné pozice si budeme pamatovat pozici v poli, na které zrovna hledáme číslo 42 a kterou po každém průchodu cyklem zvýšíme o jedna. Takovou proměnnou potřebujeme, abychom věděli, jak v podmínce cyklu otestovat, zda máme pokračovat. V proměnné nalezeno bude na začátku 0 symbolizující, že jsme 42 ještě nenalezli, a když ji najdeme, nastavíme tuto proměnnou na hodnotu 1. V každém průchodu cyklem pak podmínkou zkontrolujeme, zda na pozici dané proměnnou pozice není číslo 42. Pokud je, tak proměnnou nalezeno nastavíme na 1, jinak jí necháme původní hodnotu. Po doběhnutí programu tedy můžeme díky proměnné nalezeno zjistit, zda jsme číslo 42 našli, nebo nenašli.

Celý algoritmus by tedy vypadal asi následovně:

     Vstup: posloupnost čísel v poli posloupnost a jejich počet v proměnné n

  1.     pozice $\gets $ 0
  2.     nalezeno $\gets $ 0
  3.     Dokud pozice $<$ n:
  4.         Pokud posloupnost[pozice] $=$ 42:
  5.             nalezeno $\gets $ 1
  6.     pozice $\gets $ pozice $+$ 1

     Výstup: Proměnná nalezeno, ve které je uložena 1, právě pokud je číslo 42
v posloupnosti obsaženo

Můžeme si navíc všimnout, že jsme k ničemu nepoužili to, že jsme hledané číslo znali předem, a že jsme na řádce 4 mohli kontrolovat rovnost s proměnnou, ve které by bylo uložené hledané číslo. Umíme takto tedy zjistit, zda je v poli libovolné číslo uložené v proměnné.

Časová složitost

V úvodu jsme tvrdili, že se budeme snažit vymýšlet algoritmy, které spočtou výsledek v co nejkratším čase. Co to ale na našem novém počítači vlastně znamená? Protože na teoretickém modelu jen těžko můžeme měřit čas běhu programu, budeme místo toho počítat provedené instrukce. Vztah ke skutečným počítačům je zde zřejmý – skutečné procesory opravdu mají sadu instrukcí (do kterých je každý program přeložen) a vykonat jednu instrukci trvá nějakou krátkou dobu. Počet vykonaných instrukcí tedy nějakým způsobem odpovídá době běhu programu.

Za instrukci považujeme některou z operací $\gets $ (přiřazení), $+$, $-$, $\cdot $, $/$ nebo určení pravdivostní hodnoty jednoduchého výrazu.

Můžete se pokusit spočítat, kolik instrukcí provede výše popsaný algoritmus (nezapomeňte, že některé instrukce uvnitř cyklu bude počítač provádět $n$-krát). Už jen to, že se autoři tohoto textu nejsou schopni shodnout, zda to vyjde $4n+4$, nebo $6n+3$, napovídá, že spočítat přesný počet instrukcí není vůbec jednoduché a u složitějších algoritmů téměř nemožné. Navíc když spustíme program na skutečném počítači, závisí počet instrukcí na tom, jak přesně funguje procesor daného stroje. Počítače jsou také ve skutečnosti různě rychlé, takže stejná instrukce bude trvat na různých počítačích různě dlouho. Co s tím? Místo toho, abychom počítali přesný počet instrukcí, budeme ho počítat jen zhruba. Konkrétně nebudeme řešit konstanty, kterými $n$ násobíme a které k němu přičítáme. Důvodem, proč to není zas tak špatné řešení, je, že když bude vstup dostatečně dlouhý (a tedy $n$ dostatečně velké), budou konstanty zanedbatelně velké vůči něčemu, co závisí na $n$. Například pokud porovnáme časové složitosti $20n$ a $3n^2$, tak vidíme, že již pro poměrně malá $n$ budou konstanty zanedbatelné vzhledem k rozdílu způsobenému kvadratickou funkcí.

V našem algoritmu závisí počet instrukcí na $n$ lineárně – počet provedených instrukcí je nejvýše přímo úměrný počtu čísel na vstupu. Není těžké si uvědomit, že rychlejší algoritmus nemůže existovat – na každé z $n$ zadaných čísel se totiž musíme alespoň jednou podívat a jen na to potřebujeme alespoň $n$ instrukcí.

Abychom si tedy ulehčili práci a nemuseli jsme počet instrukcí počítat přesně, zavádíme takzvanou „óčkovou notaci“2. Óčková notace je horní odhad na počet instrukcí, které algoritmus provede, pokud zanedbáme multiplikativní konstanty a spustíme ho pro dostatečně velký vstup. 3 Pokud má tedy algoritmus časovou složitost $\mathcal{O}(n^2)$, znamená to, že pro dostatečně velká $n$ existuje konstanta $k$ taková, že algoritmus provede maximálně $k \cdot n^2$ instrukcí (například pro každé $n$ větší než 100 provede algoritmus maximálně $42 \cdot n^2$ instrukcí). Také si můžeme všimnout, že například algoritmus, který vždy provede $5 + 2n + 3n^4$ instrukcí běží v čase $\mathcal{O}(n^4)$, jelikož $5 + 2n + 3n^4 < 5n^4$ pro každé $n > 1$ (ze stejného důvodu bychom mohli tvrdit, že tentýž algoritmus běží v čase $\mathcal{O}(2^ n)$, tato informace by ale pro nás nebyla příliš cenná – vždy se snažíme o co nejtěsnější odhad.) O našem algoritmu na hledání čísla v poli tedy můžeme říct, že má časovou složitost $\mathcal{O}(n)$.

V předchozím textu jsme vám trochu zalhali. Náš algoritmus umíme drobně upravit tak, že pro něj půjde najít lepší odhad než $\mathcal{O}(n)$. Stačilo by po každém průchodu cyklem zkontrolovat, jestli už jsme číslo našli, a pokud ano, ukončit provádění smyčky. Pokud by tedy první z čísel v posloupnosti bylo 42, algoritmus by provedl jen konstantně mnoho instrukcí (počet instrukcí by byl nezávislý na $n$), běžel by tedy v čase $\mathcal{O}(1)$. Takový případ ale pro nás není příliš zajímavý, protože nikdy nevíme, jaká čísla na vstupu dostaneme, a nemůžeme se při návrhu algoritmů spoléhat na to, že budeme mít pokaždé štěstí. Pokud tedy není řečeno jinak, budeme vždy určovat časovou složitost v nejhorším případě. Budeme tedy předpokládat, že nepřítel nám zadal vstup tak, aby náš algoritmus běžel co nejdéle. Taky si to můžeme představit tak, že spustíme algoritmus pro všechny vstupy dané délky a budeme počítat ten vstup, na který jsme potřebovali nejvíce instrukcí. S touto definicí složitosti už tedy opravdu platí naše dřívější poznámka, že najít číslo v poli $n$ čísel obecně neumíme rychleji než v čase $\mathcal{O}(n)$.


Úloha 1 [2b]: Vymyslete algoritmus, který zjistí, kde se v poli nachází největší číslo a jaké číslo to je. Můžete předpokládat, že největší číslo je v poli jen jedno.


Tato úložka by měla jít vyřešit podobně jako ukázkový problém výše. Kdykoliv po vás chceme vymyslet algoritmus, rádi bychom slyšeli i jeho časovou složitost. To k algoritmu patří, protože to je v určitém slova smyslu to, co nám říká, jak je daný algoritmus dobrý.

Když už umíme najít maximum v poli, tak není těžké pole setřídit.


Úloha 2 [3b]: Vymyslete algoritmus, který setřídí pole čísel. Jinými slovy, chtěli bychom čísla seřadit podle jejich velikosti.


Tento problém se vám pravděpodobně nepodaří vyřešit v čase $\mathcal{O}(n)$. Pokud ano, určitě nám takové řešení pošlete. Jedná se totiž o slavný otevřený problém, který se informatici snaží vyřešit již po desetiletí. A pokud máte pomalejší řešení, také ho určitě pošlete, i když si myslíte, že by to mohlo jít rychleji.

Lze dokázat, že třídit nejde rychleji než v $\mathcal{O}(n \log n)$, ale tento důkaz předpokládá, že si zakážeme s čísly dělat cokoliv kromě porovnávání. Kdybyste tento důkaz viděli, tak si vzpomeňte na tento předpoklad, díky kterému si důkaz neprotiřečí s tím, že bychom chtěli umět třídit v čase $\mathcal{O}(n)$.


Bonusová verze [+2b]: Vyřešte ten samý problém, ale jen s konstantní pamětí navíc. To znamená, že máte v paměti pole, chcete ho setřídit a smíte při tom využívat libovolné konstantní (tedy nezávislé na $n$) množství proměnných. Už si ale třeba nemůžete pořídit pole, do kterého budete ukládat setříděnou posloupnost. To konkrétně znamená, že setříděná čísla budou na konci muset být v poli, ve kterém jste je dostali (na výstup nic nevypisujte).


Na závěr formálněji popíšeme a odůvodníme chování našeho modelu. Pokud následující část nechcete číst, nijak vám to nebrání v řešení témátka, vážou se k ní ale některé další problémy.

Formální popis modelu

Náš počítač bude mít paměť, která se skládá z nekonečně mnoha paměťových buněk očíslovaných celými čísly (představujte si ji jako nekonečnou posloupnost čtverečků). V každé buňce může být uloženo libovolně velké celé číslo. Číslu buňky budeme říkat adresa. Buňka může být určena dvěma způsoby: Přímou adresací – napíšeme adresu buňky do hranatých závorek (buňku s adresou 3 tedy značíme [3]), nebo nepřímou adresací – do dvojitých hranatých závorek napíšeme adresu buňky, ve které je uložena výsledná adresa buňky (buňku, jejíž adresa je uložena v buňce s adresou 3, tedy značíme [[3]]).

Každý algoritmus, který chceme na našem počítači spustit, musíme zapsat pomocí instrukcí. Počítači tedy předáme seznam instrukcí (ekvivalent kódu napsaného v programovacím jazyce pro skutečné počítače) a do určených paměťových buněk napíšeme vstup. Na reálném počítači by vstup pocházel z nějakého souboru nebo by ho zadal uživatel, ale my budeme pro jednoduchost předpokládat, že ho už máme někde uložený. Počítač poté provede všechny instrukce v takovém pořadí, v jakém jsou zapsány. Až mu instrukce dojdou, skončí. Počítač navíc může pomocí instrukce print postupně vypisovat čísla na výstup. Výstupem je pak posloupnost čísel, které vypsal za dobu svého běhu.

Nyní již přímo k instrukcím našeho počítače. Typická instrukce bere dva argumenty – každý z nich je (přímo či nepřímo adresovaná) paměťová buňka, nebo celé číslo. Pokud je argumentem buňka, instrukce si vždy přečte číslo, které je v ní uložené, a dále počítá s ním. S takto určenými celými čísly instrukce něco provede a výsledek uloží do předem určené paměťové buňky.

Samotné instrukce budou následující:

  • Instrukce přiřazení $\gets $ bere jeden argument a jeho hodnotu uloží do určené buňky. Například [1] $\gets $ [2] přečte číslo z druhé paměťové buňky a uloží ho do první paměťové buňky.

  • Instrukce $+$, $-$, $\cdot $ a $/$ berou vždy dva argumenty, spočítají jejich součet, rozdíl, součin nebo podíl (zaokrouhlený dolů na celé číslo) a výsledek uloží do dané buňky. Například [[4]] $\gets $ [1] $+$ 2 vezme číslo uložené v první buňce, přičte k němu dvojku a výsledek uloží do buňky, jejíž adresa je uložena v buňce číslo 4.

  • Instrukce skoku nebere žádný argument, ale „skočí“ v našem programu na označené místo. Někam mezi instrukce tedy napíšeme klíčové slovo (třeba „bagr“). Pokud na jiném místě napíšeme instrukci „skok na bagr“, náš počítač začne provádět instrukce, které následují za slovem „bagr“. Můžeme tím tedy způsobit, že se některé instrukce přeskočí, nebo naopak provedou víckrát.

  • Instrukce podmíněného příkazu bere dva argumenty, podmínku, kterou mají splňovat, a libovolnou jinou instrukci s jejími argumenty. Podmínka je vždy některý z matematických operátorů ($<$, $>$, $\ge $, $\le $, $=$, $\neq $). Pokud je podmínka splněna, provede se daná instrukce. Např. „Pokud [1] $>$ 1, [2] $\gets $ 3“ uloží do druhé buňky číslo 3, pokud je v první buňce uloženo číslo větší než 1.

  • Instrukce print vypíše argument na výstup.

Tím je náš model kompletní.

Model jsme se snažili zavést tak, aby byl co nejjednodušší, ale zároveň uměl spočítat vše, co umí dnešní počítače, a to se stejnou časovou složitostí. Výhodou našeho nového modelu je, že má méně instrukcí a lépe se s ním pracuje matematicky (třeba se v něm lépe dokazuje, že problém nelze algoritmicky vyřešit), zatímco v tom předchozím se zase lépe uvažuje o programech. Můžete si zkusit rozmyslet, že ve skutečnosti není o nic slabší než náš dříve zavedený uživatelsky přívětivější model…


Problém: Zkuste dokázat, že jakýkoliv program, který funguje na modelu, který jsme si pro větší pohodlnost dříve zavedli, lze přepsat tak, aby fungoval i na tomto minimalistickém modelu se stejnou časovou složitostí. Můžete to samozřejmě dokázat jen pro nějakou část – například vysvětlit, jak v minimalistickém modelu vytvořit pole, podmínku či cyklus.


Možná vám přijde zvláštní, že jsme schopni na našem modelu počítat s libovolně velkými čísly v konstantním čase. Říkáte si, že to asi neodpovídá realitě, protože určitě bude existovat vážně velké číslo, které na opravdový počítač ani nepůjde uložit, natož aby s ním počítače uměly pracovat v konstantním čase (ať už to u reálných počítačů znamená cokoliv). Nám to také přijde zvláštní. Je na vás, abyste tento problém vyřešili. Zkuste náš model nebo způsob počítání složitosti nějak upravit, nebo si vymyslet vlastní výpočetní model a počítat časovou složitost na něm. Můžete samozřejmě popsat více různých možností.


Problém: Navrhněte výpočetní model nebo způsob počítání časové složitosti, který bude odpovídat realitě v tom, že operace s dlouhými čísly trvají déle než s krátkými.


Ptáte se, zda je to opravdu třeba? Zatím jsme si neukázali žádný způsob, jak by šlo konstantní operace s dlouhými čísly zneužít. Jedním z problémů, při jehož řešení to jde, je například již zmíněné třídění čísel, které lze v našem modelu provést v $\mathcal{O}(n)$, a tedy není tak úplně pravda, že by to byl slavný otevřený problém, jak jsme psali. Ale v libovolném rozumném modelu tomu tak je. Další takový problém je násobení matic, které lze zrychlit tím, že zakódujeme $n$ čísel do jednoho a poté umíme provést aritmetickou operaci na $n$ číslech v čase $\mathcal{O}(1)$. Tyto konstrukce však nejsou úplně jednoduché, a nebudeme je zde tedy ukazovat. Pilný řešitel si je může vymyslet sám a pak o tom napsat pro ostatní.


Těžký problém: Vymyslete nějaký algoritmus, který zneužívá operace s dlouhými čísly v konstantním čase. (Řešení tohoto problému nebudeme zveřejňovat, bude tedy možnost posílat k němu řešení po celý školní rok.)


Kuba a Tom; domestomas+mam@gmail.com
e-mailová konference: algoritmy@mam.mff.cuni.cz


1) AND a OR jsou logické spojky, které jste pravděpodobně brali ve škole v rámci výrokové logiky pod názvy konjunkce a disjunkce. Složený výrok se spojkou AND je pravdivý právě tehdy, když jsou pravdivé oba výroky, a se spojkou OR právě tehdy, když je pravdivý alespoň jeden z nich.

2) Přestože pojem „óčková notace“ nezní úplně odborně, anglicky se toto značení skutečně nazývá „Big O notation“.

3) Formální definici si můžete přečíst třeba na Wikipedii: https://en.wikipedia.org/wiki/Big_O_Notation


 

 

 

Rekurze

Slovo úvodem

Vítáme vás u dalšího dílu našeho témátka pro začínající informatiky (a také pro zvídavé fyziky a matematiky). Pokud jste zatím nečetli první díl, snažně vám doporučujeme s ním začít – budeme na něj navazovat. Znovu pro jistotu připomínáme, že cílem témátka je vymyslet si postupně základy teoretické informatiky. Body tedy dáváme za to, že jste vymysleli řešení, a ne za sepsání algoritmu, který jste již dobře znali. Také věříme, že M&Mko řešíte hlavně proto, abyste se něco nového naučili (a ne jen kvůli bodům). Pokud tedy řešení některých zde zmíněných problémů znáte, pusťte se raději do jiného témátka nebo jiného problému tohoto témátka, které pro vás budou větší výzvou, nebo si vhodný problém k řešení sami vymyslete. Také bychom chtěli doplnit, že u většiny problémů očekáváme především slovní popis algoritmu a ideálně i časovou složitost. Když přidáte i kód, může nám to pomoct lépe pochopit vaši myšlenku a rozhodně vám za něj body neubereme, neměl by ale nahrazovat slovní popis.

Dnes si ukážeme, jak funguje takzvaná rekurze, důležitá technika designu algoritmů. Ač, striktně vzato, není potřeba, protože libovolný algoritmus používající rekurzi můžeme přepsat v modelu, jenž jsme si ukázali minule, často výrazně zjednodušuje vymýšlení i následné programování algoritmu. Předtím si ale ještě řekneme, co jsou to funkce.

Funkce

Při programování často potřebujeme dělat nějakou věc opakovaně na různých místech v programu. Například, kdybychom programovali program na kreslení geometrických útvarů, budeme pravděpodobně často potřebovat počítat délku přepony trojúhelníku pomocí Pythagorovy věty. Proto jsou v programovacích jazycích takzvané funkce, které nám dovolují si „pojmenovat kus kódu“, a kdykoliv potřebujeme spočítat délku přepony, zavoláme funkci, která to za nás udělá. Taková funkce a její volání může vypadat třeba takto:

  1.    Funkce délka_přepony($x$, $y$):
  2.        Vrať $\sqrt {x^2 + y^2}$
  3.    
  4.    Z $\gets $ délka_přepony(2, 3)

Zamysleme se, jak přesně funkce fungují. Funkce se zavolá s nějakými argumenty (v našem příkladu proměnné $x$ a $y$), čímž nastavíme pro funkci hodnoty proměnných, které jsme definovali jako argumenty. Tyto a všechny ostatní proměnné definované ve funkci jsou lokální pro jedno zavolání (spuštění) dané funkce a když se funkce dokončí, zaniknou. Naopak k proměnným mimo funkci, které jsme nepředali jako argument, se nedostaneme. Může se tedy stát, že bude jinde v programu existovat proměnná $x$, která bude mít jinou hodnotu, než proměnná $x$ lokální pro konkrétní volání funkce délka_přepony.

Postupně se budou vykonávat instrukce funkce řádek po řádku, jako kdekoliv jinde v programu. Co se stane, když dojdeme na konec funkce, nebo k příkazu vrať? Chtěli bychom se vrátit přesně na místo, ze kterého jsme funkci zavolali. Přesně to se stane, protože programovací jazyk si za nás zapamatoval místo, ze kterého jsme funkci zavolali, a díky tomu na něj dokáže skočit, když funkce skončí. Pokud byla funkce ukončena příkazem vrať, vrátí se daná hodnota, jak můžete vidět v příkladu, kde nám funkce vrátí hodnotu $\sqrt {13}$.


Problém 1 (4b): Zkuste na našem formálním modelu, který jsme si vytvořili na konci minulého dílu, vytvořit funkce. Nezapomeňte, že po svém ukončení se funkce musí vrátit hned za místo, ze kterého byla zavolána.


Rekurze

Co se přesně bude dít při zavolání funkce délka_přepony by mělo být celkem intuitivní – funkce se spustí, spočte se výsledek, ten se vrátí a budeme pokračovat ve vykonávání instrukcí na místě, ze kterého jsme funkci volali. Co ale třeba následující funkce na výpočet Fibonacciho čísel?

1. Funkce fibonacciho_číslo($n$):
2.   Pokud $n$ = 0:
3.      Vrať 0
4.   Pokud $n$ = 1:
5.      Vrať 1
6. Vrať fibonacciho_číslo($n-1$) + fibonacciho_číslo($n-2$)

Už by nám mělo být jasné, co se stane, když $n$ bude 1, nebo 2. Když ale bude $n$ rovno 3 nebo víc, ani jedna z prvních dvou podmínek nebude splněna a tedy se při vyhodnocování funkce dostaneme až na řádek 6. Tady by se mohlo zdát, že funkce není dobře definovaná, protože její definice závisí na sobě samé. Není tomu ale tak. Abychom pochopili, co přesně se bude dít, uvědomme si, jak funkce fungují. Když funkci zavoláme, začne se vyhodnocovat řádek po řádku a když vyhodnocování skončí, pokračuje se ve vykonávání instrukcí na místě, odkud se funkce volala. Pokud tedy funkce zavolá sebe samou, začne se se vyhodnocovat ještě jednou od začátku a když přijde k příkazu vrať, skočí na místo odkud jsme ji zavolali, totiž do sebe samé. Hodnoty proměnných jsou lokální pro každé volání funkce, a tedy se jednotlivá volání nebudou navzájem ovlivňovat tím, že by si jednotlivá volání funkce „navzájem sahala na proměnné“.

Pokud tedy budeme chtít spočítat čtvrté Fibonacciho číslo, bude funkce
fibonacciho_číslo zavolána celkem pětkrát. Následující diagram ukazuje, jak by výpočet probíhal. Každý bod diagramu odpovídá jednomu zavolání funkce fibonacciho_číslo a z každého volání vedou šipky do bodů odpovídajících vykonání funkce z něj zavolané.

Fibbonacciho čísla
Obrázek 1: Výpočet Fibonacciho čísel

 


Problém 2 (1b): Spočítejte faktoriál pomocí rekurze bez použití cyklu. Otázka, kterou je dobré si položit při řešení tohoto problému, je: „Kdybych měl spočítané $(n-1)!$, jak z toho spočítám $n!$?“. Toto je ostatně otázka, kterou je dobré si položit, kdykoliv řešíte nějaký algoritmický problém a která vede na rekurzivní algoritmus (rozmyslete si proč).


Logaritmus

Ze školy možná znáte definici funkce zvané logaritmus. Logaritmus kladného reálného čísla $x$ o základu $a$ je takové reálné číslo $y$, pro které platí $a^ y = x$. Zapisujeme $y = \log _ a x$. Intuitivnější definice je, že logaritmus nám říká, kolikrát musíme základ vynásobit sebou samým, abychom dostali $x$. Platí tedy, že $\log _2 8 = 3$, protože $2^3 = 8$. Pokud se v informatice mluví o logaritmu, myslí se tím v drtivé většině případů logaritmus o základu 2. Stejně to bude i v našem témátku. Pokud tedy píšeme $\log n$, myslíme tím vždy $\log _2 n$.

\includegraphics[height=200pt]{obrazky/tema4-graf_30.pdf}
Obrázek 2: Porovnání lineání funkce s logaritmem

 

\includegraphics[height=200pt]{obrazky/tema4-graf_1000.pdf}
Obrázek 3: Porovnání lineání funkce s logaritmem – pohled z dálky

 

Na obrázku 4 můžete vidět úplný binární strom. Strom se skládá z vrcholů spojených hranami a neobsahuje cykly („větve“ se nikde nespojují). Jednotlivým „vrstvám“ vrcholů říkáme hladiny a číslujeme je od shora a od nuly. Na nulté hladině tedy leží jeden vrchol. Vrcholům, které jsou připojené pod některým vrcholem, říkáme jeho synové (podle rodokmenu, který má podobný tvar) a vrchol, který nemá ani jednoho syna, je list, zatímco vrchol bez otce se nazývá kořen (je vždy právě jeden). Strom na obrázku je navíc binární, protože každý vrchol má maximálně dva syny, a je úplný, protože každý vrchol kromě listů má dva syny a všechny listy leží na stejné hladině. Více se o stromech dozvíte v některém z dalších dílů témátka.

Můžeme si povšimnout, že na každé z hladin je dvakrát více vrcholů než na té předchozí. Na $k$-té hladině (počítáno shora) se tedy nachází $2^ k$ vrcholů (na nulté hladině jich je $1 = 2^0$). Podle zmíněné definice logaritmu tedy platí, že logaritmus počtu vrcholů na dané hladině je číslo hladiny (jinak řečeno hloubka).

\includegraphics[height=5.3cm]{obrazky/tema4-strom_final.pdf}
Obrázek 4: Úplný binární strom

K čemu je nám to dobré? Na stromu je hezky vidět, že logaritmus roste výrazně pomaleji než lineární funkce (když říkáme lineární funkce, budeme vždy předpokládat kladný koeficient u $x$). Graf těchto dvou funkcí můžete vidět na obrázcích 2 a 3. Hlavně se nám ale často stane, že něco – třeba strom všech možných průběhů algoritmu – má tvar úplného binárního stromu. Vizte následující úlohu.

Mějme panelák o $n$ patrech (pro jednoduchost nechť $n$ je mocnina dvojky – pokud není, tak přistavíme imaginární patra navíc aby bylo, a všimneme si, že jsme počet pater nanejvýš zdvojnásobili). Patra jsou standardně očíslována od 0 do $n-1$. Dále mějme dostatek ideálních vajec – tedy vajec, která jsou ve všech možných fyzikálních vlastnostech shodná. Naším cílem je zjistit, z jakého nejvyššího patra můžeme ideální vejce shodit, aby se nerozbilo. Vejce se ale po každém shození rozbije nebo zakutálí, chceme proto výsledek zjistit na co nejméně pokusů. Jak budeme postupovat a kolik pokusů budeme potřebovat v nejhorším případě? Než si přečtete řešení, zkuste se nejdříve zamyslet, jak byste úlohu řešili vy.

Nabízíme následující řešení: Pokud má panelák jen jedno patro, řešení je triviální. V opačném případě vyjdeme do patra číslo $n/2$ a shodíme z něj vajíčko. Pokud se rozbije, musí se nutně rozbít i při pádu ze všech vyšších pater, tudíž nás žádné z těchto pater nezajímá. Můžeme tedy úlohu rekurzivně vyřešit pro prvních $n/2$ pater. Pokud se naopak vajíčko nerozbije, nezajímají nás žádná nižší patra – řešením je buď naše patro, nebo některé z vyšších pater. Vyřešíme tedy úlohu rekurzivně pro horní polovinu paneláku (představte si, že první polovinu paneláku odseknete, zahodíte a druhou polovinu paneláku položíte na zem – z toho by mělo být vidět, že se opravdu jedná o stejný problém poloviční velikosti). Pokud řešení nenajdeme, je řešením naše patro. Na závěr jen vrátíme číslo patra, případně informaci, že takové patro neexistuje (reprezentovanou hodnotou $-1$). Rozmyslete si, jak bude tato vrácená informace „vybublávat“ všemi voláními. Následuje pseudokód:

   Vstup: počet pater $n$, funkce shod_vajicko která vrací 1 pro rozbité a 0 pro
nerozbité vajíčko
1. Funkce hledani_patra($n$, $prizemi$):
2.   Pokud $n = 1$:
3.      Pokud shod_vajicko($prizemi$) $= 0$:
4.         Vrať $prizemi$
5.      Jinak:
6.         Vrať $-1$
7.   Pokud $n > 1$:
8.      Pokud shod_vajicko($prizemi + n/2$) $= 1$:
9.         Vrať hledani_patra($n/2$, $prizemi$)
10.      Jinak:
11.         Vrať hledani_patra($n/2$, $prizemi + n/2$)
Výstup: hledani_patra($n$, 0)

Nyní nám zbývá určit časovou složitost algoritmu. Podobně jako u funkce fibonacciho_cislo si nakreslíme strom rekurzivních volání funkce. Je tady ale jeden zásadní rozdíl. Zatímco u Fibonacciho čísel volala funkce sama sebe vždy dvakrát, nyní se volá vždy pouze jednou. Pokud bychom tedy nakreslili, jak byla funkce skutečně volána, dostali bychom něco, čemu se v teorii grafů říká cesta – byla by to rovná řada vrcholů spojená čarami bez jakéhokoliv větvení.

My si ale pořídíme trochu jiný strom. Nebude znázorňovat průběh jednoho spuštění algoritmu, ale všechny možné způsoby, jak může tento průběh vypadat v závislosti na vstupu. Jinými slovy, bude znázorňovat všechna rozhodnutí, která algoritmus udělal, a proto mu budeme říkat rozhodovací strom. Při každém volání se funkce v závislosti na vstupních parametrech rozhodne, zda pokračovat v hledání správného patra v dolní, nebo horní polovině paneláku. Každý z vrcholů našeho stromu značí jedno zavolání funkce a jeho dva synové tyto dvě možnosti. Pokud je funkce zavolána na vstup velikosti 1, již se dál rekurzivně nevolá a její zavolání je tak reprezentováno některým listem stromu. Tvrdíme, že tento rozhodovací strom bude mít tvar úplného binárního stromu. Proč by to tak mělo být? Když si zkusíte strom nakreslit pro nějaké malé vstupy, které jsou mocniny dvojky, zjistíte, že strom pro vstup velikosti $n$ můžete vytvořit tak, že nakreslíte vedle sebe dvakrát rozhodovací strom pro vstup velikosti $n/2$ a přidáte nový společný kořen a z něj dvě hrany do dvou původních kořenů. Nový kořen totiž značí první volání funkce hledani_patra, ve kterém se rozhodneme, na kterou z polovin paneláku se rekurzivně zavolat. Další průběh algoritmu pro danou polovinu paneláku už je stejný jako pro vstup velikosti $n/2$, a proto má i stejný rozhodovací strom. Stejným způsobem si můžeme uvědomit, že počet listů stromu je vždy roven $n$ – při zdvojnásobení vstupu se totiž zdvojnásobí i počet listů. Pokud bychom chtěli tyto vlastnosti formálně dokázat, použili bychom matematickou indukci (to je taková rekurze pro matematiky). Doufáme ale, že spojitost mezi stromem a algoritmem je vidět, a přesný důkaz zde uvádět nebudeme (pilný řešitel nám ho samozřejmě může do časopisu poslat).

Skutečný průběh algoritmu je tedy cesta z kořene do jednoho z listů. Počet zavolání funkce je tedy roven počtu hladin ve stromu, což je logaritmus počtu listů. Počet listů je ale $n$, čímž dostáváme, že počet volání funkce hledani_patra je $\log n$. Jedno volání funkce trvá konstantně dlouho, celý algoritmus tedy běží v čase $\mathcal{O}(\log n)$ a shodí $\mathcal{O}(\log n)$ vajíček.

Časovou složitost můžeme nahlédnout i bez stromu rekurze. Jak už jsme zmínili minule, každým zavoláním funkce hledani_patra se délka vstupu zmenší na polovinu. Když nás tedy zajímá počet volání, stačí říct, kolikrát musíme $n$ vydělit dvěma, abychom dostali číslo 1. To je samozřejmě tolik, kolikrát musíme dvojku vynásobit samu sebou, abychom dostali $n$, a to je rovno $\log n$. Opět tedy dostáváme časovou složitost algoritmu $\mathcal{O}(\log n)$. Můžete si zkusit rozmyslet, že algoritmus po drobné úpravě (bude třeba $n/2$ zaokrouhlit) funguje se stejnou časovou složitostí i pro vstupy, které nejsou mocniny dvojky.


Problém 3: Náš algoritmus na házení vajíček lze pro některé velikosti vstupů ještě o trochu zlepšit (jen o konstantu). Zkuste si rozmyslet jak a napište nám to.


V minulém díle jsme měli algoritmus na hledání čísla v poli. To obecně nemůžeme umět rychleji než lineárně – na každé číslo se musíme alespoň jednou podívat. Co kdybychom ale měli zaručeno, že je pole setříděné (tedy čísla jsou seřazena vzestupně)? Zkuste se inspirovat naším vajíčkovým algoritmem a vymyslete algoritmus, který v čase $\mathcal{O}(\log n)$ najde dané číslo v setříděném poli (nebo zjistí, že se v poli nenachází).


Problém 4 (2b): Vymyslete algoritmus, který najde v setříděném poli délky $n$ dané číslo v čase $\mathcal{O}(\log n)$. Nezapomeňte na slovní popis algoritmu a zdůvodnění časové složitosti.


Třídění podruhé

Nyní se zamyslíme nad tím, zda by se pomocí rekurze nedal udělat rychlejší třídící algoritmus. V minulém díle jsme vymysleli algoritmus běžící v čase $\mathcal{O}(n^2)$. Teď bychom chtěli něco rychlejšího.

Začneme s otázkou podobnou té u výpočtu faktoriálu: chceme setřídit $n$ čísel. Předpokládejme, že už umíme setřídit $n-1$ nebo méně čísel, a zkusme pomocí toho setřídit všech $n$ čísel. Jedním řešením by bylo setřídit prvních $n-1$ čísel a poslední číslo poté vložit do setříděné posloupnosti (zkuste si rozmyslet detaily). Prozradíme, že tak získáme algoritmus běžící v čase $\mathcal{O}(n^2)$. Je tedy třeba vymyslet jiný přístup. V následujících dvou problémech si vymyslíte, jak dosáhnout časové složitosti lepší než $\mathcal{O}(n^2)$.


Problém 5 (3b): Předpokládejme, že máme dvě setříděné posloupnosti čísel (mohou být různě dlouhé). Vymyslete, jak s co nejlepší časovou složitostí z těchto dvou posloupností udělat jednu setříděnou posloupnost obsahující čísla z obou. Při vyjadřování časové složitosti použijte $n$ jakožto celkový počet čísel. Nezapomeňte určit časovou složitost vašeho algoritmu.


Při řešení tohoto problému si doporučujeme zkusit napsat dvě setříděné posloupnosti a napsat ručně výstupní posloupnost. Při vymýšlení algoritmů je často dobré si zkusit výsledek na malých vstupech spočítat ručně – třeba si při tom všimnete, jak to udělat efektivně.: Při řešení následujícího problému se vám bude pravděpodobně hodit využít řešení problému 4 výše. Pokud jste ho nevyřešili, můžete nyní předpokládat, že jde řešit v čase $\mathcal{O}(n)$.


Problém 6 (4b): Vymyslete třídící algoritmus běžící v čase lepším než kvadratickém (jinými slovy lepším než $\mathcal{O}(n^2)$). Nezapomeňte udat s odůvodněním jeho časovou složitost. Prozradíme vám, že se vám bude hodit nejen rekurze, ale i kapitola o logaritmech.:


Kuba a Tom; domestomas+mam@gmail.com
e-mailová konference: algoritmy@mam.mff.cuni.cz