Fakulta Informatiky
Masarykova Univerzita
Matematické Základy Informatiky
(FI: IBOOO)
Doc. RNDr. Petr Hliněný, Ph.D.
hlineny@f i.muni.cz
3. prosince 2012
Obsažný a dobře přístupný úvod do nezbytných formálních matematických základu moderní informatiky, doplněný řadou interaktivních cvičení v IS MU.
Výukový text pro předmět IBOOO na FI MU od roku 2012, navazující zčásti na původní výukové texty Úvodu do Informatiky z minulých let.
Verze 1.98 (2012)
© 2006-2012 Petr Hliněný, FI MU.
0.1    O tomto textu a jeho studiu
Vážení čtenáři,
dostává se vám do rukou výukový text Matematické Základy Informatiky, který je primárně určený pro studenty stejnojmenného předmětu na FI MU Brno. Seznamuje čtenáře s několika formálními matematickými oblastmi důležitými pro úspěšné studium moderní informatiky.
Náš text svým obsahem volně navazuje na původní slidy předmětu IB000 sepsané A. Kučerou do roku 2005 a rozšířené autorem v letech 2006-11 o volný text a komentáře. Od roku 2012 však byl obsah některých pasáží podstatně změněn či přímo vyměněn za nový (nejzřetelnější je zahrnutí úvodu do grafů). Mimo textu samotného (jak jej zde vidíte) jsou z téhož zdoje vytvářeny i přednáškové slidy předmětu, které najdete například v IS MU. Slidy však pochopitelně obsahují jen část textu a jsou jinak formátovány.
Učební text je psán strukturovaným matematickým přístupem, s velkým důrazem na přesnost a formalitu vyjadřování v nutných partiích. Na druhou stranu jsou strohá matematická vyjádření pokud možno doplněna obsáhlými neformálními komentáři, které mají studentům ulehčit pochopení látky. V žádném případě však čtenáři nemají zaměňovat neformální komentáře za matematické definice - v případě nejasností vždy platí to, co přesně říká formální definice.
Interaktivní osnova
http://is.muni.cz/el/1433/podzim2012/IB000/index.qwarp
Nedílnou součástí celého výukového textu jsou interaktivní osnova předmětu IB000 v IS MU a z ní odkazované online odpovědníky sloužící k procvičování probrané látky na jednoduchých i složitějších příkladech. To je také důvod, proč texto text obsahuje jen velmi málo příkladů k probírané látce; od každého studenta očekáváme, že si látku bude procvičovat online na zmíněných odpovědnících, obsahujících až tisíce příkladů desítek typů. K praktickému pochopení přednesených znalostí i k jejich budoucím aplikacím je takové procvičení nezbytné(l). V návaznosti na tyto odpovědníky doporučujeme studentům diskutovat o probírané látce a svých (ne) úspěších s cvičícími předmětu i na předmětovém diskuzním fóru v IS.
ii
Obsah
0.1   O tomto textu a jeho studiu......................... ii
1 Základní formalismy matematiky 1
1.1 Úvod do matematického dokazování..................... 1
1.2 Význam matematických vět......................... 2
1.3 Struktura matematických vět a důkazů................... 3
1.4 Výroky a základ výrokové logiky ...................... 5
1.5 Střípky matematické logiky ......................... 6
2 Důkazové techniky, Indukce 11
2.1 Přehled základních důkazových technik................... 11
2.2 Věty typu „tehdy a jen tehdy"........................ 13
2.3 Matematická indukce............................. 14
2.4 Komentáře k matematické indukci...................... 16
3 Množiny a jejich prvky 19
3.1 Pojem množiny................................ 19
3.2 Množinové operace.............................. 20
3.3 Porovnávání a určení množin ........................ 23
3.4 Posloupnosti a rekurentní vztahy...................... 25
4 Relace a funkce, Ekvivalence 27
4.1 Relace a funkce nad množinami....................... 27
4.2 Reprezentace konečných relací........................ 29
4.3 Vlastnosti binárních relací.......................... 30
4.4 Relace ekvivalence .............................. 32
4.5 Rozklady a jejich vztah k ekvivalencím................... 33
5 Uspořádané množiny, Uzávěry 35
5.1 Uspořádání a uspořádané množiny ..................... 35
5.2 Další pojmy uspořádaných množin ..................... 37
5.3 Hasseovské diagramy............................. 39
5.4 Uzávěry relací................................. 40
6 Skládání relací a funkcí 42
6.1 Vlastnosti funkcí............................... 42
6.2 Inverzní relace a skládání relací....................... 43
6.3 Skládání relací „v praxi"........................... 44
6.4 Skládání funkcí, permutace.......................... 46
6.5 Induktivní definice množin a funkcí..................... 48
7 Pojem grafu, ve zkratce 52
7.1 Definice grafu................................. 52
7.2 Podgrafy a Isomorfismus........................... 55
7.3 Souvislost grafů, komponenty........................ 58
7.4 Stromy - grafy bez kružnic.......................... 58
7.5 Použití a implementace grafů ........................ 60
iii
8 Procházení grafu a odvozené úlohy 63
8.1 Jak obecně projít souvislý graf........................ 63
8.2 Vzdálenost v grafu.............................. 66
8.3 Hledání nejkratší cesty............................ 67
8.4 Problém minimální kostry.......................... 70
9 Orientované grafy, Toky v sítích 73
9.1 Základní pojmy orientovaných grafů..................... 73
9.2 Definice sítě a toku.............................. 76
9.3 Nalezení maximálního toku ......................... 77
9.4 Zobecněné použití sítí ............................ 81
10 Formalizace a důkazy pro algoritmy 84
10.1 Formální popis algoritmu........................... 84
10.2 O „správnosti" a dokazování programů................... 86
10.3 Jednoduché indukční dokazování ...................... 87
10.4 Rekurzivní algoritmy............................. 88
11 Pokročilé dokazování nad algoritmy 91
11.1 Dokazování konečnosti algoritmu ...................... 91
11.2 Přehled technik důkazu indukcí....................... 94
11.3 Zajímavé algoritmy aritmetiky........................ 97
11.4 Dynamický algoritmus............................ 99
12 Nekonečné množiny, Zastavení algoritmu 101
12.1 O nekonečných množinách a kardinalitě................... 101
12.2 „Naivní" množinové paradoxy........................ 102
12.3 Algoritmická neřešitelnost problému zastavení............... 104
i v
1   Základní formalismy matematiky
Úvod
Začneme nejprve několika obecnými poznámkami ke smyslu a směřování celého našeho předmětu: Jak sami poznáte, studium informatiky neznamená jen „naučit se nějaký programovací jazyk", nýbrž zahrnuje celý soubor dalších relevantních předmětů, mezi nimiž najdeme i matematicko-teoretické (formální) základy moderní informatiky Právě odborný nadhled nad celou informatikou včetně nezbytné formální teorie nejspíše odliší „řadového programátora", kterých jsou dnes spousty i bez VS vzdělání, od skutečného a mnohem lépe placeného počítačového experta.
A na tomto místě nyní přichází náš předmět Matematické Základy Informatiky, který vás právě na studium těchto formálních základů moderní informatiky připraví. Začínáme zostra, přesným matematickým vyjadřováním, výrokovou logikou a principy logických úsudků a matematických důkazů. Tak se do tohoto studia s chutí dejte...
Cíle
Prvním cílem této lekce je rozebrat struktury matematických tvrzení (vět) a jejich formálních důkazů. V druhém sledu se naučíte chápat smysl matematických vět formálním pohledem výrokové logiky a pracovat s touto formalizací, včetně kvantiňkace.
1.1   Uvod do matematického dokazování
Matematika (a tudíž i teoretická informatika jako její součást) se vyznačuje velmi přísnými formálními požadavky na korektnost argumentace. Takto korektně postavená argumentace vede od přijatých předpokladů v elementárních krocích směrem k požadovanému závěru (a nikdy ne naopak!).
Definice 1.1. Matematický důkaz .
Uvažme matematickou větu (neboli tvrzení) tvaru
„Jestliže platí předpoklady, pak platí závěr". Důkaz této věty je konečná posloupnost tvrzení, kde
• každé tvrzení je buď
* předpoklad, nebo
* obecně přijatá „pravda" - axiom, nebo
* plyne z předchozích a dříve dokázaných tvrzení podle nějakého „akceptovaného" logického principu - odvozovacího pravidla:
• poslední tvrzení je závěr.
Komentář: O potřebné úrovni formality matematických důkazů a o běžných důkazových technikách se dozvíme dále v této a příští lekci. Nyní si jen celou problematiku uvedeme názornými příklady.
Příklad 1.2. Uvažujme následující matematické tvrzení (které jistě už znáte). Věta. Jestliže x je součtem dvou lichých čísel, pak x je sudé.
1
Poznámka pro připomenutí:
- Sudé číslo je celé číslo dělitelné 2, tj. tvaru 2k.
- Liché číslo je celé číslo nedělitelné 2, tj. tvaru 2k + 1.
Důkaz postupuje v následujících formálních krocích: tvrzení zdůvodnění
1) a = 2k + 1, k celé předpoklad
2) b = 21 + 1, / celé předpoklad
3) x = a + b = 2k + 21 + 1 + 1 1,2) a komutativita sčítání (axiom)
4) x = 2(k + /) + 2 • 1 3) a distributivnost násobení
5) x = 2(k + / + 1) 4) a opět distributivnost násobení
6) x = 2m, m celé 5) a m = k + / + 1 je celé číslo (axiom)
Příklad 1.3. Dokažte následující tvrzení:
Věta. Jestliže x a y jsou racionální čísla pro která platí x < y, pak existuje racionální číslo z pro které platí x < z < y.
Důkaz po krocích (s již trochu méně formálním zápisem) zní:
1) Nechť z =       =x + ^ =y-
2) Číslo z je racionální, neboť x a, y jsou racionální.
3) Platí z > x, neboť ^ > 0.
4) Dále platí z < y, neboť opět       > 0.
5) Celkem x < z < y.
Jak čtenář vidí, tento strohý formální zápis (i když matematicky kompletní) si zaslouží aspoň krátký vysvětlující komentář. Takový komentář, ať už se objeví před nebo hned po formálních argumentech, sice není součástí důkazu samotného, velmi však napomáhá správnému pochopení a má své nezastupitelné místo. Konkrétně je zde velmi vhodné poznamenat, že klíčový krok (1) popisuje námi vymyšlenou algebraickou konstrukci, která vede k požadovanému číslu z. Zbylé kroky (2-5) pak jen snadno zdůvodňují, že nalezené z má všechny požadované vlastnosti. □
Poznámka. Alternativní formulace Věty z Příkladu 1.3 mohou znít:
- Pro každé x, y G Q, kde x < y, existuje z G Q takové, že x < z < y.
- Množina racionálních čísel je hustá.
1.2   Význam matematických vět
První krok formálního důkazu je uvědomit si, co říká věta, která se má dokázat; tedy co je předpoklad a co závěr dokazovaného tvrzení. Pravdivost takového tvrzení pak je třeba
2
chápat v následujícím významu:
Pro každou situaci, ve které jsou splněny všechny předpoklady, je platný i závěr tvrzení.
Komentář: Příklady běžné formulace matematických vět:
* Konečná množina má konečně mnoho podmnožin.
* sin2(a) + cos2(a) = 1.
* Graf je rovinný, jestliže neobsahuje podrozdělení K5 nebo 1^3,3.
Co přesně nám uvedené matematické věty říkají? Často nám k lepšímu pochopení toho, co je tvrzeno a je třeba dokázat, pomůže pouhé rozepsání definic pojmů, které se v dané větě vyskytují.
O pravdivosti implikace
Všimněte si také, jaký je správný logický význam matematického tvrzení vysloveného touto formou implikace („jestliže ..., pak ... "). Především, pokud předpoklady nejsou splněny nebo jsou sporné, tak celé tvrzení je platné bez ohledu na pravdivost závěru!
Příklad 1.4. Je pravdivé následující matematické tvrzení?
Věta. Mějme dvě kuličky, červenou a modrou. Jestliže červená kulička je těžší než modrá a zároveň je modrá kulička těžší než ta červená, tak jsou obě kuličky ve skutečnosti zelené.
„ To přece nemůže být pravda, jak může být jedna kulička těžší než druhá a naopak zároveň? Jak mohou být nakonec obě zelené? To je celé nějaká blbost... "
Ano, výše uvedené jsou typické laické reakce na uvedenou větu. Přesto však tato věta pravdivá je! Stačí se vrátit o kousek výše ke kritériu - Pro každou situaci, ve které jsou splněny všechny předpoklady je platný i závěr tvrzení - které je zjevně naplněno. Nenaleznete totiž situaci, ve které by byly splněny oba předpoklady zároveň, a tudíž ve všech takových neexistujících situacích si můžete říkat cokoliv, třeba že kuličky jsou zelené. □
Příklad 1.5. Anna a Klára přišly na přednášku a usadily se do lavic. Proč je pravdivé toto matematické tvrzení?
Věta. Jestliže Anna sedí v první řadě lavic a zároveň Anna sedí v poslední řadě lavic, tak Klára nesedí v druhé řadě lavic.
Opět je třeba se hluboce zamyslet nad významem předpokladů a závěru, ale ten-tkrát není situace předpokladů tak triviálně sporná, jako v Příkladu 1.4. Kdy tedy nastávají oba předpoklady zároveň? Když první řada lavic je zároveň řadou poslední! Neboli posluchárna má jen (nejvýše) jednu řadu lavic a Klára tudíž v druhé řadě nemůže sedět. Důkaz je hotov. □
1.3   Struktura matematických vět a důkazů
Jak „moc formálníCÍ mají správné matematické důkazy vlastně být?
3
• Záleží na tom, komu je důkaz určen — konzument musí být schopen „snadno" ověřit korektnost každého tvrzení v důkazu a plně pochopit, z čeho vyplývá.
• Je tedy hlavně na vás zvolit tu správnou úroveň formálnosti zápisu vět i důkazů podle situace.
A jak na ten správný matematický důkaz máme přijít?
• No..., nalézání matematických důkazů je tvůrčí činnost, která není vůbec snadná a vyžaduje od vás přímo „umělecké" vlohy. Přesto se jí alespoň trochu musíte přiučit.
Dokazovat či vyvracet tvrzení?
Představme si, že našim úkolem je rozhodnout platnost matematického tvrzení. Jak matematicky správně zdůvodníme svou odpověď?
• Záleží na odpovědi samotné... Pokud je to ANO, prostě podáme důkaz tvrzení podle výše uvedených zvyklostí. Pokud je odpověď NE, tak naopak podáme důkaz negace daného tvrzení.
Poměrně častým případem pak je matematická věta T, která tvrdí nějaký závěr pro širokou oblast vstupních možností. Potom platí následující:
• Pokud T je pravdivá, nezbývá než podat vyčerpávající důkaz platnosti pro všechny vstupy.
• Avšak pokud T je nepravdivá, stačí „uhodnout" vhodný vstupní protipříklad a jen pro něj dokázat, že závěr tvrzení není platný.
Komentář: A nyní se znovu vraťte na začátek Oddílu 1.2 a srovnejte si výše uvedené se základními poznatky o významu matematických vět...
Příklad 1.6. Rozhodněte platnost následujícího tvrzení: Pro všechna reálná x platí
x2 + 3x + 2 > 0 .
Důkaz: Standardními algebraickými postupy si můžeme upravit vztah na x2 + 3x + 2 = (x + 1) • {x + 2) > 0. Co nám z něj vyplývá? Například to, že k porušení daného tvrzení stačí volit x tak, aby jedna ze závorek byla kladná a druhá záporná. To nastane třeba pro x = — |.
Pro vyvrácení tvrzení nám tedy stačí začít volbou protipříkladu x = — | (není nutno zdůvodňovat, jak jsme jej „uhodli"!) a následně dokázat úpravou
x2+ 3x + 2 = (x + l).(x + 2) = (-| + l).(-|+2) = (-!)•(+!) = ~<0. Dané tvrzení není platné. □
Konstruktivní a existenční důkazy
Z hlediska praktické využitelnosti je potřeba rozlišit tyto dvě kategorie důkazů (třebaže z formálně-matematického pohledu mezi nimi kvalitativní rozdíl není).
• Důkaz Věty 1.3 je konstruktivní. Dokázali jsme nejen, že číslo z existuje, ale podali jsme také návod, jak ho pro dané x a y sestrojit.
4
• Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán použitelný návod na jeho konstrukci.
Příklad 1.7.  čistě existenčního důkazu.
Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu sportky v roce 2012.
Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2012. Pro každý možný výsledek existuje program, který tento daný výsledek vypíše na obrazovku. Mezi těmito programy je tedy jistě ten, který vypíše právě ten výsledek, který bude ve 45. tahu sportky v roce 2012 skutečně vylosován.
□
Komentář: To je ale „podvod", že? A přece není... Formálně správně to je prostě tak a tečka (2011: tedy dokud nám to pan Husák všechno nepokazí, že?).
Fakt. Pro informatické i další aplikované disciplíny je důležitá konstruktivnost důkazů vět, které se zde objevují. V matematice ale jsou mnohé příklady užitečných a nenahraditelných existenčních důkazů, třeba tzv. pravděpodobnostní důkazy.
Příklad 1.8. „pravděpodobnostního" existenčního důkazu.
Věta. Na dané množině bodů je zvoleno libovolně n2 podmnožin, každá o n prvcích. Dokažte pro dostatečně velká n, že všechny body lze obarvit dvěma barvami tak, aby žádná množina nebyla jednobarevná.
Důkaz: U každého bodu si „hodíme mincí" a podle výsledku zvolíme barvu červeně nebo modře. (Nezávislé volby s pravděpodobností |.) Pravděpodobnost, že zvolených n bodů vyjde jednobarevných, je jen ^ = 21_n.
Pro n2 podmnožin tak je pravděpodobnost, že některá z nich vyjde jednobarevná, shora ohraničená součtem
-> 0.
Jelikož je toto číslo (pravděpodobnost) pro n > 7 menší než 1, bude existovat obarvení bez jednobarevných zvolených podmnožin. □
1.4   Výroky a základ výrokové logiky
Pojem výroku se dá považovat za důležitý „pevný most" mezi běžnou mluvou a přesným matematickým formalismem. Jeho správné uchopení napomůže chápání významu matematických výroků a práci s nimi (jako třeba v případě mechanické negace složeného výroku).
Definice 1.9. Výrok v přirozené mluvě:
V běžné mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl platně prohlásit, že je buď pravdivé nebo nepravdivé.
Komentář: Ukážeme si několik příkladů - které z nich jsou výroky?
* Dnes už v Brně pršelo.
* Předmět FI: IB000 se vyučuje v prvním ročníku.
* Platí 2 + 3 = 6.
5
* To je bez problémů. (Co?)
* Platí x > 3.
* Pro každé celé číslo x platí, že x > 3.
Všimněte si, že pravdivost výroku by mělo být možné rozhodnout bez skrytých souvislostí (kontextu), a proto čtvrtý a pátý příklad za výroky nepovažujeme. Poslední příklad již zase výrokem je, neboť obor hodnot x je jednoznačně vymezen tzv. kvantifikací.
Z více jednoduchých výroků vytváříme výroky složitější pomocí tzv. logických spojek.
Komentář: Následuje několik dalších příkladů.
* Množina {a, b} má více než jeden prvek a není nekonečná.
* Jestliže má Karel přes 90 kg váhy, nejedu s ním výtahem.
* Jestliže má tato kráva 10 nohou, pak mají všechny domy modrou střechu. Zastavme se na chvíli nad posledním výrokem. Co nám říká? Je pravdivý? Skutečně mají všechny domy modrou střechu a před námi stojí kráva s 10 nohama? (Ano, výrok je pravdivý, viz definice či pravdivostní tabulka implikace.)
Schopnost porozumět podobným větám je součást lidského způsobu uvažování a z tohoto hlediska nemá přímou souvislost s matematikou (je to „přirozená logika"). Formální (matematická) logika pak v podobném duchu definuje jazyk matematiky a přitom odstraňuje nejednoznačnosti přirozeného jazyka.
1.5   Střípky matematické logiky
Všimněte si, že podle Definice 1.9 každému výroku běžné mluvy prostě můžeme přiřadit logickou hodnotu 0 (falše) nebo 1 (true) a dále se nestarat o jazykový význam... Proto (jazykové) výroky v matematice vyjádříme výrokovými proměnnými, které značíme velkými písmeny A, B,C,... a přiřadíme jim hodnotu 0 nebo 1.
Definice: Výroková formule (značíme <p>, o, ip,...) vzniká z výrokových proměnných pomocí závorek a logických spojek -i negace a =>- implikace. Zároveň používáme v zápise následujících zkratek
* ip\/ ip    (disjunkce/„nebo") je jiný zápis formule    ~np =>- ip,
* <p> a ip    (konjunkce/„a") je jiný zápis formule —<(—np\J—<ip),
* <p> <=ř ip    (ekvivalence) je jiný zápis formule    (ip =>- ip) a (ip =>• ip).
Poznámka: Uvedená definice je instancí tzv. induktivní deňnice, jíž se budeme blíže věnovat v Oddíle 6.5, a proto ji zde uvádíme jen v hodně zjednodušené podobě.
Komentář: Při zápise výrokových formulí je potřeba dávat pozor na správné závorkování, aby formule měla jednoznačný význam. Na intuitivní úrovni to ilustrujeme takto:
Správně A,    (A) =>- (B),    A^B,   -^A^B, AVBV^C
a nesprávně    A =ř B =ř C    — znamená to (A => B) => C nebo A => (B => C)l
Matematický význam logickým formulím pak dodává následující definice. Definice 1.10. Sémantika (význam) výrokové logiky.
Nechť valuace (ohodnocení) je funkce v : Prom —> {0,1} na všech (dotčených) výrokových proměnných. Pro každou valuaci v definujeme funkci Sv(o), vyhodnocení formule a, induktivně (tj. po krocích) takto:
6
SV(Á) = v {Ä) pro každé A G Prom.
1  jestliže Sv{ip) = 0:
* ~   ' 0 jinak.
, s,   ^é)=í°  jeStHŽe SM = 1 a = °:
v 7        1 jinak.
Poznámka: Tento předpis podává nejen dennici funkce Sv, ale také návod na to, jak ji pro daný argument vypočítat.
Pro odvozené logické spojky disjunkce, konjunkce a ekvivalence pak dostaneme následující zcela přirozený výsledek (který tak potvrzuje, že jsme definici sémantiky zvolili správně).
Tvrzení 1.11. Důsledkem Definice 1.10 je následovné:
* Sv{ip V ip) = 1    právě když    Sv{ip) = 1 nebo Sv(ip) = 1.
* Sv(ip a ip) = 1     právě když    Sv(íp) = 1 a současně Sv{ip) = 1.
* Sv(ip     ip) = 1   právě když    platí jedna z následujících podmínek
- Sv(íp) = 1 a současně Sv(ip) = 1.
- Sv(íp) = 0 a současně Sv(ip) = 0.
Pravdivostní tabulky
V praxi často vyhodnocení Sv logické výrokové formule zapisujeme do tzv. pravdivostní tabulky. Tato tabulka typicky má sloupce pro jednotlivé proměnné, případné „mezifor-mule" (pomůcka pro snazší vyplnění) a výslednou formuli. Řádků je 2P (počet valuací), kde p je počet použitých proměnných.
Pro naše účely postačí uvést pravdivostní tabulku instruktážním příkladem. Čtenáři nechť si vyplní podle Definice 1.10 vlastní pravdivostní tabulky dalších výrokových formulí, viz také příslušné cvičící odpovědníky v IS MU.
Příklad 1.12. Jaká je pravdivostní tabulka pro formuli {A =^ B)\/ B V C?
A	B	c	A ^B	(A ^ B) V 5 V C
0	0	0	1	1
0	1	0	1	1
1	0	0	0	0
1	1	0	1	1
0	0	1	1	1
0	1	1	1	1
1	0	1	0	1
1	1	1	1	1
Splnitelnost formulí a tautologie
Definice: Formule ip G $ je splnitelná, pokud pro některou valuaci z/ platí, že Sv(íp) = 1. Formule ip G $ je vždy pravdivá, neboli výroková tautologie, psáno |= >p>, pokud pro každou valuaci v platí, že Sv(íp) = 1.
7
Řekneme, že dvě formule <p,ip G $ jsou ekvivalentní, právě když \= <p ip.
Tvrzení 1.13. Následující formule jsou tautologiemi:
• |= A v -iA
^^A<=> A {A A (A     B)) B {^B     -iA) ^(A^B) (-iA 4 (BA -i-B)) A Komentář: Jak poznáme tautologii v pravdivostní tabulce?
Kvantifikace a predikátová logika
Výše popsaná výroková logika je velmi omezená faktem, že každý výrok musí být („absolutně") vyhodnocen jako pravda nebo nepravda. Co když však chceme zpracovat tvrzení typu „den D v Brně pršelo"? Jeho pravdivostní hodnota přece závisí na tom, co dosadíme za den D, a tudíž jej nelze považovat za výrok výrokové logiky.
• Predikátová logika pracuje s predikáty. Predikáty jsou „parametrizované výroky", které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
• Predikátová logika je tak obecnější než logika výroková; každá formule výrokové logiky je i formulí predikátové logiky, ale ne obráceně.
Komentář: Pro neformální přiblížení si uvedeme několik ukázek predikátů:
* x > 3 (parameterem je zde x £ R).
* čísla x a y jsou nesoudělná (parametry x, y £ N).
* obecně jsou predikáty psány P(x,y), kde x,y jsou libovolné parametry.
Definice: Z predikátů lze vytvářet predikátové formule pomocí už známých (viz Definice 1.10) výrokových spojek a následujících tzv. kvantifikátorů:
• \/x. ip    „pro každou volbu parametru x platí formule 99",
• 3x . ip    „existuje alespoň jedna volba parametru x, pro kterou platí 99".
Čtenář by měl v tomto místě vzít na vědomí, že naše definice vztahující se k predikátové logice jsou velmi zjednodušené a nenahrazují kurz matematické logiky! Přesto poskytnou alespoň základní povědomí o této problematice (a hlavně o použití kvantifikace v tvrzeních) pro potřeby matematické formalizace v našem kurzu.
Fakt: Je-li každá proměnná - parametr predikátu - v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je celá formule buď pravdivá nebo nepravdivá.
Příklad 1.14. Ukažme si vyjádření následujících slovních výroků v predikátové logice:
• Každé prvočíslo větší než 2 je liché:
VííéN. [(Pr(n)An>2) Li(n)], přičemž lze rozepsat Li(n) = 3fcGN. n = 2k + 1.
8
• Každé číslo n > 1, které není prvočíslem, je dělitelné nějakým číslem y kde n/i/a
y > i;
VnGN. (n > 1 a -iPr(n)) =>- 3í/(í/| n a n^y a y>l). Mechanický postup negace výroků
Závěrem lekce se dostáváme k jednomu specifickému úskalí lidského chápání, totiž že přesný význam formulí se zanořenými negacemi je někdy skutečně obtížné zjistit (podobně jako v běžné řeči).
„ Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad."
Výrokové formule se proto obvykle prezentují v tzv. normálním tvaru, kde se negace vyskytují pouze u výrokových proměnných, formálně:
Definice: Formule ip G $ je v normálním tvaru, pokud se v ní operátor negace aplikuje pouze na výrokové proměnné.
Komentář: Například, pokud přijmeme pravidlo „dvojí negace" (|= -i —*A 4^ A), tak výše napsanou větu si převedeme na lépe srozumitelný tvar:
„Nemusím říct, že tě mám nerad."
Tvrzení 1.15. Každou výrokou formulí lze převést do normálního tvaru, pokud k =>• povolíme i užívání odvozených spojek a a v.
Komentář: Pro ilustraci k -<(A =4> B) je ekvivalentní A A -<B, k -|(C a (~<A =4> -B)) je ekvivalentní ->C v (->A a ->B) a k ->((A     B)     C) je ekvivalentní (A     B) a ->C).
Metoda 1.16. Převod formule ip do normálního tvaru F(ip).
Pro převod použijeme funktory T a Q s neformálním významem F(X) jako „je pravda, že X" a Q(X) jako „nenípravda, že X". Tyto funktory definujeme induktivními předpisy následovně:
F {A) =  A g{A) = ^A
F(^)     = Ghv) =
F(íP^Íj) = F{<p)^F&) G(v^^) = ^)a^W F(<pA4>)    = ^)aj(ír) G(<pA4>)    = G(tp)VG(4>)
F{^y^)   = J^VJW        G&vý)   = G(if)AGW F(íp^íj)  = F{^)^F{^)       G(tp^i>) = (^)A5W)v(%)AJW) Pro predikátové formule toto rozšíříme ještě o pravidla:
F(Vx.ip)   =  Vx.F(ip) G(Vx.ip)   = 3x.G(<p)
F(3x.(p)   =  3x. F((p) G(3x. ip)   = Vx.Q((p)
Komentář: Uvažme formuli —<(A =4> ~^(B V -|(C => —iA))). Užitím uvedeného postupu 1.16 získáme:
F(->(A => ->(B V -i(C => -<A)))) = Q(A    -i(B V -i(C => -*A))) =
F (A) a G{^{B V -i(C => -"Á))) = AAJ(BV-(C^nA))
A a (F(B) v F(-i(C => -"Á))) = A a (B v G{C => ^A))
AA(BV(J(C)AM)) = A A (B V (C A F(A))) A A (B y (C A A))
9
Formuli A a {B v (C a A)) lze dále zjednodušit na (ekvivalentní) formuli A a {B v C). To ale je již z našeho pohledu matematicky neformální (heuristický) postup.
Uvedené formální předpisy takto vyjadřují intuitivní postup převodu J-'(íp) do „lidsky čitelného tvaru".
Navazující studium
Látka této úvodní lekce má velmi široký záběr. S potřebou formálního zápisu tvrzení a důkazů se setkáte nejen v tomto, ale i ve všech dalších matematických předmětech, které zároveň studujete či budete studovat, a principy budou stále stejné. Proto se je snažte pochopit a zažít už na zde uvedených jednoduchých příkladech a vše si procvičte. V další lekci budeme pokračovat přehledem důkazových technik.
Na druhou stranu je matematická logika v této lekci uvedena jen velmi omezeně na nejlehčí akceptovatelné intuitivní úrovni a její další rozvoj je ponechán samostatným kurzům. Na FI MU to bude navazující předmět IB101 Úvod do logiky. Zájemce o studium matematických hlubin logiky a třeba slavných Gódelových poznatků můžeme později odkázat na předmět MA007 Matematická logika.
10
2   Důkazové techniky, Indukce
Úvod
Náš hlubší úvod do matematických formalismů pro informatiku pokračujeme základním přehledem technik matematických důkazů. Třebaže matematické dokazování a příslušné techniky mohou někomu připadat neprůhledné (a možná zbytečné), jejich pochopení a zvládnutí není samoúčelné, neboť nám pomáhá si mnoho uvědomit o studovaných problémech samotných. Konečně, jak si můžeme být jisti svými poznatky, když bychom pro ně nebyli schopni poskytnout důkazy?
Během studia tohoto předmětu poznáte (a ti méně šťastní až s překvapením u zkoušek), že vlastně vše, k čemu naším výkladem směřujeme, se dá neformálně shrnout slovy „ naučit se přesně vyjadřovat a být si svými tvrzeními naprosto jisti" a analogicky „naučit se navrhovat správné algoritmy a být si i svými programy naprosto jisti".
Z důkazových postupů je pro nás informatiky asi nej důležitější technika důkazů matematickou indukcí, která je svou podstatou velmi blízká počítačovým programům (coby iterace cyklů). V dalším výkladu budeme indukci hojně využívat, především v Lekcích 10 a 11.
Cíle
Cílem této lekce je popsat základní techniky matematických důkazů, z nichž největší důraz klademe na matematickou indukci. Každý student by se měl alespoň naučit formálně psané důkazy číst a pochopit. (Pro vysvětlení, z Lekce 1 víme, že matematický důkaz má „jednotnou formu" Deňnice 1.1, ale nyní se věnujeme takříkajíc šablonám, podle nichž takový korektní důkaz sestavíme.)
2.1   Přehled základních důkazových technik
V matematice je často používaných několik následujících způsobů - technik, jak k danému tvrzení nalézt korektní formální důkaz. (Uvědomme si, že jedno tvrzení mívá mnoho různých, stejně korektních, důkazů; ty se však mohou výrazně lišit svou složitostí.) Tyto techniky si v bodech shrneme zde:
• Přímé odvození. To je způsob, o kterém jsme se dosud bavili.
Postupujeme přímo od předpokladů k závěru, ale sami poznáte, že taková „přímá" cesta je obtížně k nalezení.
• Kontmpozíce (také obrácením či nepřímý důkaz). Místo věty
„Jestliže platí předpoklady, pak platí závěr." budeme dokazovat ekvivalentní větu
„Jestliže neplatí závěr, pak neplatí alespoň jeden z předpokladů."
• Důkaz sporem. Místo věty
„Jestliže platí předpoklady, pak platí závěr."
budeme dokazovat větu
„Jestliže platí předpoklady a platí opak závěru, pak platí opak jednoho z předpokladů (nebo platí jiné zjevně nepravdivé tvrzení}."
• Matematická indukce. Pokročilá technika, kterou zde popíšeme později...
11
Tyto techniky jsou asi nejlépe ilustrovány následovnými příklady důkazů. Příklad důkazu kontrapozicí
Definice: Prvočíslo je celé číslo p > 1 a nemá jiné dělitele než lap.
Příklad 2.1.  Na důkaz kontrapozicí (obrácením).
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché. Důkaz: Obráceného tvrzení - budeme tedy dokazovat, že
je-li p sudé, pak p buď není větší než 2, nebo p není prvočíslo.
Připomínáme, že podle definice je p sudé, právě když lze psát p = 2 • k, kde k je celé. Jsou dvě možnosti:
• k < 1. Pak p = 2k není větší než 2.
. k > 1. Pak p = 2 • k není prvočíslo podle definice. ^
Poznámka: Důkazy kontrapozicí pracují s negací (opakem) předpokladů a závěru. Je-li např. závěrem komplikované tvrzení tvaru
„z toho, že z A a B plyne C, vyplývá, že z A nebo C plyne A a Bíl,
není pouhou intuicí snadné zjistit, co je vlastně jeho negací. Proto se nebojte využívat snadného mechanického postupu Metody 1.16 ke správnému „znegovaní" do normálního tvaru.
Příklady důkazu sporem
Příklad 2.2.  Jiný přístup k Důkazu 2.1.
Věta. Jestliže p je prvočíslo větší než 2, pak p je liché.
Důkaz sporem: Nechť tedy p je prvočíslo větší než 2, které je sudé. Pak p = 2 • k pro nějaké k > 1, tedy p není prvočíslo, spor (s předpokladem, že p je prvočíslo). ^
Důkaz sporem je natolik specifický a důležitý v matematice, že si zaslouží širší vysvětlení. Co je vlastně jeho podstatou? Je to (zcela přirozený) předpoklad, že v konzistentní teorii nelze zároveň odvodit tvrzení i jeho negaci. Jestliže tedy ve schématu
„Jestliže platí předpoklady a platí opak závěru, pak platí opak jednoho z předpokladů, nebo platí jiné zjevně nepravdivé tvrzení."
odvodíme k některému předpokladu jeho spor, nebo případně jiné tvrzení, které odporuje všeobecně přijatým faktům (přesněji axiomům, například 0 = 1), pak něco musí být „špatně". Co však v našem tvrzení může (nezapomeňte předpoklad konzistence) být chybné? Původní předpoklady byly dány, takže zbývá jedině náš dodatečný předpoklad, že platí opak závěru. Tudíž opak závěru nemůže nikdy platit a dvojí negací odvodíme, že platí původní závěr.
Příklad 2.3. Opět sporem.
Věta. Číslo y/2 není racionální.
Důkaz sporem: Nechť tedy \f2 je racionální, tj. nechť existují nesoudělná celá kladná čísla r, s taková, že \f2 = r/s.
12
- Pak 2 = r2/s2, tedy r2 = 2 • s2, proto r2 je dělitelné dvěma. Z toho plyne, že i r je dělitelné dvěma (proč? opět na to můžete jít sporem...).
- Jelikož r je dělitelné dvěma, jer2 dělitelné dokonce čtyřmi, tedy r 2 = 4 • m pro nějaké m. Pak ale také 4 • m = 2 • s2, tedy 2 • m = s2 a proto s2 je dělitelné dvěma.
- Z toho plyne, že s je také dělitelné dvěma. Celkem dostáváme, že r i s jsou dělitelné dvěma, jsou tedy soudělná a to je spor (s definicí racionálního čísla). □
Komentář:  „Nevíte-li, jak nějakou větu dokázat, zkuste důkaz sporem... "
2.2   Věty typu „tehdy a jen tehdy"
Uvažujme nyní (v matematice poměrně hojné) věty tvaru
„Nechť platí předpoklady P. Pak tvrzení A platí tehdy a jen tehdy, platídi tvrzení B."
Příklady jiných jazykových formulací téže věty jsou:
* Za předpokladů P je tvrzení B nutnou a postačující podmínkou pro platnost tvrzení A.
* Za předpokladů P je tvrzení A nutnou a postačující podmínkou pro platnost tvrzení B.
* Nechť platí předpoklady P. Pak tvrzení A platí právě tehdy když platí tvrzení B.
Fakt: Důkaz vět tohoto tvaru má vždy dvě části(!). Je třeba dokázat:
* Jestliže platí předpoklady P a tvrzení A, pak platí tvrzení B.
* Jestliže platí předpoklady P a tvrzení B, pak platí tvrzení A.
Příklad 2.4.  Na důkaz typu „tehdy a jen tehdy".
Věta. Dokažte, že pro každá dvě celá čísla a, b platí, že a < b právě tehdy, když 2a < 2b.
Důkaz: Nezapomínáme, že našim úkolem je dokázat oba směry tvrzení (implikace zleva doprava a zprava doleva). Začneme s prvním: Předpoklad a < b je definičně ekvivalentní tomu, že b = a + k pro nějaké přirozené k > 0. Potom 2b = 2a+k = 2a ■ 2k = í • 2a pro nějaké přirozené í = 2k > 2, a tudíž 2b — 2a = (í — 1) • 2a > 1 • 2a > 0 . Tím je první část důkazu hotova.
V opačném směru postupujeme z předpokladu 2a < 2b. Vydělením obou stran nerovnosti kladným číslem 2a získáme 26/2a = 2b~a > 1. Dále postupujeme sporem. Nechť tedy a > b, neboli a — b = m>0. Potom máme 2a~b = 2 ■ ... 2y > 1. Avšak celkově
mx
1 = 2° = 2a~b ■ 2b~a > 1 • 1 = 1 je sporné. Proto zbývá požadovaný závěr a < b. □
Komentář: Je možno se někdy oddělenému zpracování obou směrů takového tvrzení vyhnout? Ano, stačí dělat pouze tzv. ekvivalentní úpravy, ale je to velmi nebezpečné. Co například tvrzení „a = b právě když ax = bxíl? To přece dokážeme vynásobením obou stran rovnosti stejným číslem x...
Je to sice téměř pravda, ale(!) musíme si všimnout, že násobení obou stran rovnosti je ekvivalentní úpravou jen pro i / 0; jinak nazpět dělíme nulou (což na světě dokáže pouze Chuck Norris). Zapamatujte si, že nejlepší cestou, jak se takovým chybám a problémům vyhnout, je skutečně poctivě dokazovat každý směr ekvivalence zvlášť.
13
2.3   Matematická indukce
Pokud se souhrnně podíváme na důkazové techniky v matematice, všimneme si, že matematická indukce je skoro „dvorní" důkazovou technikou diskrétní matematiky. To proto, že umožňuje pohodlně dokazovat i složitá tvrzení po jednotlivých (diskrétních) krocích od počátečního.
Uvažme tedy větu ve tvaru:
„Pro každé přirozené (celé) n > ko platíT(n).u
Zde k0 je nějaké pevné přir. číslo a T(n) je tvrzení parametrizované čís. n. Příkladem je třeba tvrzení:
Pro každé n>0 platí, že n přímek dělí rovinu nejvýše na ^n(n + 1) + 1 oblastí. Definice 2.5. Princip matematické indukce říká, že k důkazu věty
„Pro každé přirozené (celé) n > k$ platíT(n).u stačí ověřit platnost těchto dvou tvrzení:
• T(k0) (tzv. báze neboli základ indukce)
• Pro každé n > k$; jestliže platí T(n), (indukční předpoklad) pak platí také T(n + 1). (indukční krok)
Formálně řečeno, matematická indukce je axiomem aritmetiky přirozených čísel. Poznámka: Pozor, v tomto předmětu počítáme 0 za přirozené číslo!
Opět jako v předešlém si tuto techniku ilustrujeme množstvím názorných příkladů.
Příklady důkazů indukcí
Příklad 2.6.  Velmi jednoduchá a přímočará indukce.
Věta. Pro každé přirozené, n > 1 je stejná pravděpodobnost, že při současném hodu n kostkami bude výsledný součet sudý, jako, že bude lichý.
Důkaz: Základ indukce je zde zřejmý: Na jedné kostce (poctivé!) jsou tři lichá a tři sudá čísla, takže obě skupiny padají se stejnou pravděpodobností.
Indukční krok pro n > 1: Nechť psn pravděpodobnost, že při hodu n kostkami bude výsledný součet sudý, a pln je pravděpodobnost lichého. Podle indukčního předpokladu Je Pn = Pn = \- Hoďme navíc (n + l)-ní kostkou. Podle toho, zda na ní padne liché nebo sudé číslo, je pravděpodobnost celkového sudého součtu rovna
3 ř 3 s 1 ~6Pn + ~6Pn = -2
a stejně pro pravděpodobnost celkového lichého součtu. □
Příklad 2.7.   Ukázka skutečné důkazové „síly" principu matematické indukce. Věta. Pro každé n > 0 platí, že n přímek dělí rovinu nejvýše na 1
-n(n + 1) + 1
oblastí.
14
Důkaz: Pro bázi indukce stačí, že 0 přímek dělí rovinu na jednu část. (Všimněte si také, že 1 přímka dělí rovinu na dvě části, jen pro lepší pochopení důkazu.)
Mějme nyní rovinu rozdělenou n přímkami na nejvýše |n(n+l) + l částí. Další, (n+1)-ní přímka je rozdělena průsečíky s předchozími přímkami na nejvýše n + 1 úseků a každý z nich oddělí novou část roviny. Celkem tedy bude rovina rozdělena našimi přímkami na nejvýše tento počet oblastí:
1 111
-n(n + l) + l + (n + 1) = -n(n + 1) + - • 2(n + 1) + 1 = -(n + l)(n + 2) + 1
□
Příklad 2.8. Další indukční důkaz rozepsaný v podrobných krocích. Věta. Pro každé n > 0 platí Yľj=o3 = n(n2+1') .
Důkaz indukci vzhledem k n.
Báze: Musíme dokázat tvrzení T(0), což je v tomto případě rovnost J2j=0 j -Tato rovnost (zjevně) platí.
Indukční krok: Musíme dokázat následující tvrzení pro n > 0:
Jestliže platí YTj=o 3 = n(n2+1') > Pak platí Y^j=q 3 =        , kde q = n + 1.
Předpokládejme tedy, že Y^j=o3 = a pokusme se dokázat, že pak také
q
3=0
q(q+l)     (n + l)(n + 2)
To už plyne úpravou:
n(n + l) n(n + 1) + 2(n + 1)       (n + l)(n + 2)
i=o i=0
2 2 2
Podle principu matematické indukce je celý důkaz hotov. □
Poznámka: Výsledek Příkladu 2.8 je ukázkou tzv. sumačního vzorce pro posloupnost přirozených čísel. Jinou ukázkou je třeba vztah
1 + 3 H-----h (2n - 3) + (2n - 1) = 1 + (2n - 1) + 3 + (2n - 3) H----= 2n • ^ = n2,
nebo 12+22H-----hra2 = ^ra(n + l)(2n + l) a 13+23H-----hra3 = (1 + 2 H-----h n)2 = \n2{n + l)2.
Odvozování a práce s jednoduchými sumačními vzorci by také měla náležet do výbavy schopného informatika, princip matematické indukce je zde klíčový.
15
2.4   Komentáře k matematické indukci
Pro správné a úspěšné použití indukce v dokazování je vhodné si zapamatovat několik cenných rad:
* Základní trik všech důkazů matematickou indukcí je vhodná reformulace tvrzení T(n + 1) tak, aby se „odvolávalo" na tvrzení T(n).
- Dobře se vždy podívejte, v čem se liší tvrzení T(n + 1) od tvrzení T(n). Tento „rozdíl" budete muset v důkaze zdůvodnit.
* Pozor, občas je potřeba „zesílit" tvrzení T(n), aby indukční krok správně „fungoval".
- Velkým problémem bohužel je, že není možno podat návod, jak vhodné „zesílení" nalézt (ani kdy jej vůbec hledat). Jedná se vlastně o pokusy a „hádání z křišťálové koule".
* Často se chybuje v důkazu indukčního kroku, neboť ten bývá většinou výrazně obtížnější než báze, ale o to zrádnější jsou chyby v samotné zdánlivě snadné bázi!
- Dejte si dobrý pozor, od které hodnoty n > k0 je indukční krok univerzálně platný a jestli případně báze nezahrnuje více než jednu hodnotu...
Zesílení indukčního kroku
Příklad 2.9. Když je nutno indukční krok zesílit... Věta. Pro každé n > 1 platí
,,111 1
s(n) =--1---1---1-----h —-r < 1.
y J    1-2    2-3    3-4 n(n + l)
Důkaz: Báze indukce je zřejmá, neboť ^ < 1.
Co však indukční krok"? Předpoklad s(n) < 1 je sám o sobě „příliš slabý" na to, aby bylo možno tvrdit s(n + 1) = s(n) + ,   , A ,    < 1.
\     1     / v   / (n+l)(n+2)
Neznamená to ještě, že by tvrzení nebylo platné, jen je potřeba náš indukční předpoklad zesílit. Budeme dokazovat
Tvrzení. Pro každé přirozené n > 1 platí s(n) < 1 — ^j-j- < 1.
To platí pro n = 1 (nezapomeňte ověřit!) a dále už úpravou jen dokončíme zesílený indukční krok:
l i i
s(n + l) = s(ri) + ----r < 1
(n + l)(n + 2) ~       n + 1     (n + l)(n + 2)
-(n + 2) + l     _ x J_ (n + l)(n + 2) ' n+ 2
□
Rozšíření báze a předpokladu
Mimo zesilování tvrzení indukčního kroku jsme někdy okolnostmi nuceni i k rozšiřování samotné báze indukce a s ní indukčního předpokladu na více než jednu hodnotu parametru n.
16
- Můžeme například předpokládat platnost (parametrizovaných) tvrzení T(n) iT(n + l) zároveň, a pak odvozovat platnost T(n+2). Toto lze samozřejmě zobecnit na jakýkoliv počet předpokládaných parametrů.
- Můžeme dokonce předpokládat platnost tvrzení T(j) pro všechna j = k0, k0 + 1,..., n najednou a dokazovat T(n + 1). Toto typicky využijeme v případech, kdy indukční krok „rozdělí" problém T(n + 1) na dvě menší části a z nich pak odvodí platnost T(n + 1).
Fakt: Obě prezentovaná „rozšíření" jsou v konečném důsledku jen speciálními instancemi základní matematické indukce; použité rozšířené možnosti pouze zjednodušují formální zápis důkazu.
Příklad 2.10. Když je nutno rozšířit bázi a indukční předpoklad...
Věta. Nectí funkce f pro každé n > 0 splňuje vztah f(n + 2) = 2f(n + 1) — f(n). Pokud platí /(O) = 1 a zároveň /(l) = 2, tak platí f(n) = n + 1 pro všechna přirozená n > 0.
Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2f(n + 1) — f(n) naznačuje, že bychom měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n > 0; jestliže platí T (n); neboli f(n) = n + 1, a zároveň platí T (n + 1); f(n + 1) = n + 2, pak platí také T(n + 2); f(n + 2) = n + 3.
Báze indukce - pozor, zde už musíme ověřit dvě hodnoty
/(O) = 0 + 1 = 1,   /(l) = 1 + 1 = 2.
Náš indukční krok tak nyní může využít celého rozšířeného předpokladu, znalosti hodnot f(n) i f{n + 1), pro ověření
f(n + 2) = 2f(n + 1) - f{n) = 2-(n + l + l)-(n + l)=n + 3 = n + 2 + l.
□
Komentář: Jak by tento důkaz měl být formulován v „tradiční" indukci? („Substitucí" nového tvrzení.)
Závěrem malý „problém"
Příklad 2.11. Aneb jak snadno lze v matematické indukci udělat chybu. Věta. („nevěta")
V každém stádu o n > 1 koních mají všichni koně stejnou barvu.
Důkaz indukcí vzhledem k n. Báze: Ve stádu o jednom koni mají všichni koně stejnou barvu.
Indukční krok: Nechť S = \K\,..., Kn+i} je stádo o n + 1 koních. Dokážeme, že všichni koně mají stejnou barvu. Uvažme dvě
- S' = {K1,KÄ,...,Kn}
- S" = {K2,..., Kn, Kn+i)
17
Podle indukčního předpokladu mají všichni koně ve stádu S' stejnou barvu B'. Podobně všichni koně ve stádu S" mají podle indukčního předpokladu stejnou barvu B". Dokážeme, že B' = B", tedy že všichni koně ve stádu S mají stejnou barvu. To ale plyne z toho, že koně K2,..., Kn patří jak do stáda S', tak i do stáda S". □
Komentář: Ale to už je podvod! Vidíte, kde?
Navazující studium
Jak jsme již řekli, matematické důkazy a jejich chápání jsou nezbytné ke studiu vysokoškolských matematických předmětů. Bez schopnosti přesného vyjadřování a chápání deňnic a vět se informatik neobejde, ani pokud se zaměřuje čistě aplikovaným směrem; viz třeba správné pochopení různých norem a speciňkací.
Na druhou stranu umění "tvořit" nové matematické důkazy je dosti obtížné a nedá se jemu jen tak snadno naučit - vyžaduje to mnoho pokročilé praxe. Jelikož je schopnost formálního matematického dokazování nezbytná (převážně jen) v teoretických informatických disciplínách, není tato část kritická v celém předmětu (a u zkoušek se objevíš menším důrazem), ale to neznamená, že byste se jí mohli zcela vyhýbat. Obzvláště techniku matematické indukce by měl každý informatik aspoň trochu ovládat, neboť s jejím použitím se zajisté ještě mnohokráte setkáte v budoucím studiu.
18
3   Množiny a jejich prvky
Úvod
V přehledu matematických formalismů informatiky se v této a příští lekci zaměříme na základní datové typy matematiky, tj. na množiny, relace a funkce. Netradiční sousloví „datové typy" matematiky zde volíme záměrně, abychom zdůraznili jejich fundamentálnost pro výstavbu navazující teorie v analogii k programování.
O množinách jste sice zajisté slyšeli už na základní škole, ale podstatou našeho předmětu je uvést povětšinou neformálně známé pojmy na patřičnou formální úroveň nutnou pro teoretické základy informatiky. V případě konečné teorie množin si zde vystačíme s tzv. „naivním" pohledem, který dostatečně matematicky přesně vystihuje všechny jejich konečné aspekty (o aspektech nekonečných množin se krátce zmíníme až v Lekci 12).
Cíle
V této lekci si ukážeme první krok k seriózně vybudované matematické teorii množin -tzv. naivní teorii množin, která nám velmi dobře poslouží ve všech konečných případech. Na to navážeme zavedením základního množinového kalkulu, shrnutím běžných vlastností množin a uvedeme si příklady rekurzivně definovaných posloupností.
3.1   Pojem množiny
Položme si hned na úvod tu nej důležitější otázku: Co je vlastně množina?
Na tuto otázku bohužel není zcela jednoduchá odpověď... Abychom se vůbec někam v
našem úvodu dostali, spokojíme se zatím jen s přirozeným „naivním pohledem".
Definice naivní teorie množin: „Množina je soubor prvků a je svými prvky plně určena. "
Komentář: Příklady zápisu množin výčtem prvků
0,   {a,b},   {b, a},   {a,b,a},   {{a, b}},   {0, {0}, {{0}}},   {x \ x je liché přirozené číslo}.
Co je ale pak prvek? Tady pozor, pojem prvku sám o sobě nemá matematický význam, svého významu totiž nabývá pouze ve spojení „být prvkem množiny". Prvky množiny tak může být cokoliv, mimo jiné i dalším množiny.
Komentář: Relativitu významu vztahu „prvek-množina" si můžeme přiblížit třeba na vztahu „podřízený-nadřízený" z běžného pracovního života. Tam také nemá smysl jen říkat, že je někdo podřízeným, aniž řekneme také jeho nadřízeného. Přitom i vedoucí je někomu ještě podřízený a naopak i ten poslední podřízený pracovník může být pánem třeba svého psa. Podobně je tomu s množinou jako „nadřízenou" svých prvků.
Ale přece jenom... v dobře definovaném kontextu lze (omezeně) mluvit o prvcích jako samostatných entitách. Formálně se například jedná o prvky pevně dané nosné množiny.
Značení množin a jejich prvků:
• x G M    „x je prvkem množiny M",
• 0   je prázdná množina {}.
19
Komentář: Některé vlastnosti vztahu „být prvkem" jsou
* at{a,b}, a^{{a,b}},  {a, b} £ {{a, &}}, a 0 0, 0 £ {0}, 0 0 0,
* rovnost množin dle svých prvků {a,b} = {b, a} = {a,b,a},  {a, b} ^ {{a, b}}. Značení: Počet prvků (mohutnost) množiny A zapisujeme \A\.
Komentář:    |0| = 0,   |{0}| = 1,   \{a,b,c}\=3,   \{{a, b}, c}\ = 2.
Jednoduché srovnání množin
Vztah „být prvkem množiny" přirozeně nám podává i způsob porovnávání množin mezi sebou. Jedná se o klíčovou část teorie množin.
Definice: Množina A je podmnožinou množiny B, právě když každý prvek A je prvkem B. Píšeme A C B nebo obráceně B D A. Říkáme také, že se jedná o inkluzi.
* Platí {a} C {a} C {a, b} £ {{a, b}},   0 C {0},
* A C B právě když A C B &, A ^ B   (A je vlastni podmnožinou B). Z naivní definice množiny pak přímo vyplývá následující:
Definice: Dvě množiny jsou si rovny A = B právě když A C B & B C A.
* Podle naivní definice jsou totiž množiny A a, B stejné, mají-li stejné prvky.
* Důkaz rovnosti množin A = B má obvykle dvě části:   Odděleně se dokáží inkluze A C B a B C A.
Ukázky nekonečných množin
Značení: Běžné číselné množiny v matematice jsou následující
* N = {0,1, 2, 3,... } je množina přirozených čísel,
* Z = {..., —2, — 1, 0,1, 2, 3,... } je množina celých čísel,
* Z+ = {1, 2, 3,... } je množina celých kladných čísel,
* Q je množina racionálních čísel (zlomků).
* R je množina reálných čísel.
Komentář: Tyto uvedené číselné množiny jsou vesměs nekonečné, na rozdíl od konečných množin uvažovaných v předchozím „naivním" pohledu. Pojem nekonečné množiny se přímo v matematice objevil až teprve v 19. století a bylo s ním spojeno několik paradoxů ukazujících, že naivní pohled na teorii množin pro nekonečné množiny nedostačuje. My se k problematice nekonečných množin, Kantorově větě a Russelově paradoxu vrátíme v závěru našeho předmětu v Lekci 12.
3.2   Množinové operace
Začněme se základními operacemi množinového kalkulu, které zajisté na intuitivní úrovni již ovládáte ze školy. Pro formální úplnost podáme jejich přesné definice, na které se můžete odvolávat v důkazech.
20
Základní operace
Definice 3.1. Sjednocení U a průnik H dvou množin A, B definujeme
AU B  =   {x \ x e A nebo x G B} ,
A H B   =   {x \ x £ A & současně x G B} .
AU B
AnB
* Příklady {a, b, c} U {a, d} = {a, b, c, d},   {a, b, c} H {a, d} = {a}.
* Vždy platí „distributivita"   A f] (B U C) = (A f] B) U (A f] C) a A U (B D C) = (AU B) (1 (AU C)
* a také „asociativita" Ar\(BC\C) = (Ar\B)C\C (stejně pro U) a „komutativita" AC\B = B H A (stejně pro U).
Komentář: Asociativita a komutativita operací sjednocení a průniku je na jednu stranu zcela přirozená, na druhou stranu však velmi důležitá například pro platnost následující definice.
Definice: Pro libovolný počet množin indexovaných pomocí I rozšířeně definujeme
^ Ai   =   {x | x G A-i pro nějaké i E 1} , ^ Ai  =   {x | x G Ai pro každé i G /} .
Komentář: Nechť Ai = {2 • i} pro každé i G N. Pak U«eN ^* Je množina všech sudých přirozených čísel. Nechť Bi = {x \ x G N, x > i} pro každé i G N. Pak HíeN Bi = 0-
Množinový rozdíl
Definice 3.2. Rozdíl \ a symetrický rozdíl A dvou množin A, B definujeme
A\B  =   {x \ x £ A & současně x G" B} , AAB  =   (A\B) U (B\ A) .
A\B    ^^-JxC^ AAB
* Příklady {a, b, c} \ {a, b, d} = {c},    {a, b, c}A{a, b, d} = {c, d}.
* Vždy platí například A \ (B n C) = (A \ B) U (A \ C) apod.
Definice: Pro libovolný počet množin indexovaných pomocí konečné I rozšířeně defin-
/V^j Ai = {x | x G Ai pro lichý počet i G /} .
ujeme
21
Komentář: Povšimněte si, že operace rozdílu není asociativní ani komutativní (ostatně stejně je tomu u aritmetického rozdílu). Symetrický rozdíl už asociativní i komutativní je, není to však na první pohled vidět. Uměli byste toto dokázat?
Definice: Nechť A C M. Doplněk A vzhledem k M je množina A = M \ A.
Komentář: Jedná se o poněkud specifickou operaci, která musí být vztažena vzhledem k nosné množině M ! Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = 0.
* Vždy pro ACM platí A = A („dvojí" doplněk).
* Vždy pro A, B C M platí A U B = Iľl5a Ad B = ÄUB. (Viz Vennovy diagramy.) Uspořádané dvojice a kartézský součin
Zatímco prvky v množinách jsou zcela neuspořádané, jsou mnohé situace, kdy musíme pracovat se „seřazenými" výčty prvků. V teorii množin lze takovéto seřazení definovat oklikou následovně:
Definice: Uspořádaná dvojíce (a,b) je zadána množinou {{a}, {a, b}}.
Fakt: Platí (a, b) = (c, d) právě když a = c a současně b = d. Uměli byste toto sami dokázat přímo z podané definice?
* Co je podle definice (a, a)? Je to (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}.
Definice 3.3. Kartézský součin dvou množin A, B definujeme jako množinu všech uspořádaných dvojic ze složek z A a B
A x B = {(a, b) | a G A, b G B} .
* Příklady {a, b} x {a} = {(a, a), (6, a)}, {c, d} x {a, 6} = {(c, a), (c, b), {d, a), {d, b)}.
* Platí 0xV = 0 = Vx0 pro každou množinu X.
* Jednoduchá mnemotechnická pomůcka říká |Ax5| = |A|-|5|.
Definice: Pro každé k G N, k > 0 definujeme uspořádanou k-tící {a\, ■ ■ ■ , ak) induktivně
- (ai) = ai,
- (di, ■ ■ ■ ,di, <2i+l) = ((«1, • • • ,dí), <2i+l).
Všimněte si, že definice používá tzv. rekurentní vztah, blíže viz Oddíl 3.4.
Fakt: Platí (ai, • • • ,a^) = {b\, ■ ■ ■ ,bk) právě když a« = 6« pro každé i G N kde 1 < i < k.
Definice kartézského součinu více množin: Pro každé A; G N definujeme
A\ x • • • x Ak = {{dl-, ■ ■ ■ , cbk) | Oj G Ai pro každé 1 < i < k} .
* Například Z3 = ZxZxZ = {(i,j, k) | i,j, k G Z}.
* Co je A°7   {0}, neboť jediná uspořádaná 0-tice je právě prázdná 0.
Poznámka: Podle uvedené definice není součin asociativní, tj. obecně nemusí platit, že A x {B x C) = {A x B) x C. V matematické praxi je někdy výhodnější uvažovat upravenou definici, podle níž součin asociativní je. Pro účely této přednášky není podstatné, k jaké definici se přikloníme. Prezentované definice a věty „fungují" pro obě varianty.
22
Potenční množina
Definice 3.4. Potenční množina množiny A, neboli množina všech podmnožin, je definovaná vztahem
2A = {B | B C A} .
Důkaz: Stručně indukcí podle \A\: Pro A = 0 platí \2A\ = |{0}| = 1. Pro každý další prvek b ^ A rozdělíme všechny podmnožiny A U {b} „napolovic" na ty neobsahující b a na ty obsahující b, tudíž
3.3   Porovnávání a určení množin
Pro obecnou ilustraci formálního množinového kalkulu si ukažme dva důkazy rovností mezi množinovými výrazy. Podobně lze (rozepsáním příslušných definic) rutinně dokazovat další množinové vztahy.
Věta 3.6. Pro každé dvě množiny A, B C M platí AU B = A C\ B.
Důkaz v obou směrech rovnosti.
. A U B C A n B: Pro x E M platí x E A U B, právě když x g AU B, neboli když zároveň x £ A a x £ B. To znamená x E A a, zároveň x E B, z čehož vyplývá požadované x G A H B.
• AU B D A C\ B: Pro x E M platí x G A H B, právě když x E A a, zároveň x E B, neboli když zároveň x ^ A a x ^ B. To znamená i^4UB,z čehož vyplývá požadované x E A U B. g
Věta 3.7. Pro každé tři množiny A, B, C platí
Důkaz (viz ilustrační obrázek). ^»—
. A\(B H C) C (A \ B) \J(A\C): Je-li x E A \ (B H C), pak x E A a zároveň x ^ (5ílC), neboli x ^ B nebo x ^ C. Pro první možnost máme iG(A\ 5), pro druhou x E (A\C).
. Naopak A\ (B (1 C) D (A \ B) U (A \ C): Je-li x E (A\ B) U (A\ C), pak x E (A\ B) nebo iG(A\ C). Pro první možnost máme x E A a zároveň x ^ 5, z čehož plyne x E A a zároveň i^(BnC),a tudíž i G A \ (B íl C). Druhá možnost je
2^4u{6}| _ 2 . |2A| = 2lAl+1 = 2lj4u^^
□
A\(BnC) = (A \ B) \J(A\C).
analogická.
□
23
Charakteristický vektor (pod)množiny
V případech, kdy všechny uvažované množiny jsou podmnožinami nějaké konečné nosné množiny X, což není neobvyklé v programátorských aplikacích, s výhodou využijeme následující reprezentaci množin.
Definice: Mějme nosnou množinu X = {xi,x2,... ,xn}. Pro A c X definujeme charakteristický vektor xa jako
xa = (ci, C2,..., cn), kde Q = 1 pro Xi G A a q = 0 jinak.
Užitečnost této reprezentace je ilustrována také následovnými fakty.
• Platí A = B právě když xa = xb-
• Množinové operace jsou realizovány „bitovými funkcemi"
sjednocení ~ OR, průnik ~ AND, symetrický rozdíl ~ XOR.
Princip inkluze a exkluze
Tento důležitý a zajímavý kombinatorický princip je někdy také nazýván „princip zapojeni a vypojení''. Používá se ke zjišťování počtů prvků množin s neprázdnými průniky.
Věta 3.8. Počet prvků ve sjednocení dvou či tří množin spočítáme:
\AUB\ = \A\ + \B\ - \AC\B\ \AUBUC\ = \A\ + \B\ + \C\ -\Ar\B\ - \AnC\ - \BnC\ + \AnBnC\
Důkaz: Uvedeme si podrobný důkaz prvního vztahu |A U 5| = \A\ + \B\ — \AC\ B\, přičemž druhá část je analogická (viz obrázková ilustrace). Nechť x G A U B. Pokud x B, tak je x G A a prvek x je započítán na pravé straně \A\ + \B\ — \A fl B\ právě jednou v \A\. Obdobně je to v případě x G" A. Nakonec pro x G A H B je ve vztahu \A\ + \B\ — \AC\B\ tento prvek x započítán také 1 + 1 — 1 = 1 krát. □
Komentář: Všimněte si, že Větu 3.8 lze stejně tak využít k výpočtu počtu prvků v průniku množin...
Příklad 3.9. Z 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou obrazovku, 10 je poškrábaných a 12 má jinou vadu. Přitom 3 televize mají současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu. Kolik televizí je celkem vadných ?
Řešení: Dosazením \A\ = 5, \B\ = 10, \C\ = 12, \A H B n C\ = 3, (zde pozor) \A n B\ = 3 + 0, \A n C\ = 3 + 0, \B n C\ = 3 + 4 do Věty 3.8 zjistíme výsledek 17. □
24
Poznámka. Jen stručně, bez důkazu a bližšího vysvětlení, si uvedeme obecnou formu principu inkluze a exkluze:
n
im= e (-i)|j|-x-
j=l 0^7C{l,...,n} iel
(Jeho znalost nebude v předmětu vyžadována.)
3.4   Posloupnosti a rekurentní vztahy
Uspořádané fc-tice (Oddíl 3.2) jsou také nazývány konečnými posloupnostmi délky k, neboli seřazeními prvků z dané neprázdné množiny hodnot (opakování prvků je povoleno). Tento pohled lze přirozeně zobecnit na nekonečné posloupnosti, avšak musíme sáhnout k trochu pokročilejším pojmům (viz také Oddíl 4.1 o funkcích):
Definice: Nekonečná posloupnost p je funkcí z N do svého oboru hodnot H, neboli p : N —y H. Mimo „funkčního" zápisu p (n) často používáme „indexovou" formu zápisu funkční hodnoty pn.
Poznámka: Oborem hodnot posloupnosti obvykle bývá nějaká číselná množina, ale může to být i jakákoliv jiná množina. Také definiční obor posloupnosti může začínat od nuly nebo i od jedničky, jak je v aplikacích potřeba.
• Příklady posloupností:
* Po = 0, pi = 2,... ,pi = 2i,... je posloupnost sudých nezáporných čísel.
* 3, 3.1, 3.14, 3.141,... je posloupnost postupných dekadických rozvojů tt.
* 1, —1, 1, —1,... je posloupnost určená vztahem Pí = (—1)*, i > 0.
* Pokud chceme stejnou posloupnost 1, —1, 1, —1,... zadat jako g^, i > 1, tak ji určíme vzorcem g« = (—l)l_1.
• Posloupnost je rostoucí (či klesající), pokud pn+± > pn (pn+i < Pn) Pro všechna n. Rekurentní definice posloupnosti
Slovem rekurentní označujeme takové definice (či popisy), které se v jistých bodech odvolávají samy na sebe. (Už jste se setkali s „rekurzí" při programování? A víte, co znamená?) Místo nepřehledných formálních definic si rekurentní vztahy uvedeme několika názornými ukázkami.
• Zadámedi posloupnost pn vztahy p0 = 1 a pn = 2pn_1 pro n > 0, pak platí pn = 2n pro všechna n.
• Obdobně můžeme zadat posloupnost qn vztahy qľ = 1 a qn = qn-\ + n pro n > 1. Potom platí qn = ^n(n + 1) pro všechna n. Uměli byste toto dokázat indukcí? Viz Příklad 2.8.
• Známá Fibonacciho posloupnost je zadaná vztahy f\ = f'2 = 1 a fn = fn-\ + fn-2 Pro n > 2.
Příklad 3.10. Posloupnost f je zadaná rekurentní defínicí
/(O) = 3    a    /(n + l) = 2-/(n) + l
25
pro všechna přirozená n. Určete hodnotu f(n) explicitním vzorcem v závislosti na n.
Řešení: V první fázi řešení takového příkladu musíme nějak „uhodnout" hledaný vzorec pro f(n). Jak? Zkusíme vypočítat několik prvních hodnot a uvidíme...
/(I) = 2-/(0) + l=2-3 + l = 7
f(2) = 2-/(l) + l =2-7+1 = 15
/(3) = 2 • f (2) + 1 = 2 • 15 + 1 = 31
f (A) = 2-/(3) + l =2-31 + 1 =63
Nepřipomínají nám tato čísla něco? Co třeba posloupnost 8 — 1, 16 — 1, 32 — 1, 64 — 1... ? Bystrému čtenáři se již asi podařilo uhodnout, že půjde o mocniny dvou snížené o 1. Přesněji, f(n) = 2n+2 — 1 (proč je exponent n + 2? inu proto, aby správně vyšlo /(O)).
Ve druhé nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n. . Báze: /(O) = 20+2 -1 = 4-1 = 3 platí.
• Indukční krok: za využití indukčního předpokladu
f(n + 1) = 2 • f(n) + 1 = 2- (2n+2 - 1) + 1 = 2 • 2n+2 - 2 + 1 = 2(n+1)+2 - 1. což také platí.
Podle principu matematické indukce je nyní dokázáno, že pro zadanou rekurentní posloupnost / platí f(n) = 2n+2 — 1 pro všechna přirozená n. □
Navazující studium
I když jste se s "množinami" setkávali už od základní školy, do matematické teorie množin asi nahlédnete na VS poprvé. Nezalekněte se na úvod formality vyjadřování, která je bohužel nezbytná, a naučte se s množinami a relacemi dobře pracovat aspoň na zde ukázané naivní úrovni konečné teorie množin. (Lehký náhled na obecně nekonečné množiny a jejich zdánlivé paradoxy i informatické aplikace si ukážeme později v Lekci 12...)
Dále si srovnejte pojem posloupnosti s pojmem funkce v Oddílu 4.1 a také si později povšimněte blízké koncepční podobnosti rekurentních deňnic s induktivními deňnicemi množin a funkcí v Oddíle 6.5.
26
4   Relace a funkce, Ekvivalence
Úvod
V návaznosti na předchozí lekci si podrobně rozebereme matematické formalismy relací a funkcí. Na rozdíl od množin, které se v jisté velmi naivní formě objevují už na základní škole, se relacím v jejich abstraktní podobě moc pozornosti ve výuce nevěnuje. Stejně tak s pojmem funkce jste se již setkali na nižších stupních škol, ale povětšinou jen ve spojení s aritmetickými a analytickými funkcemi tvaru x + 1, x2 — y, či sin x, 1 + cos x2, atd.
Jak uvidíte nyní, pojmy relace i funkce jsou zcela abstraktní a neváže se ně žádný analytický vzorec výpočtu či podobné. Přitom na pojem (zcela obecné) relace velmi brzo narazí každý informatik při studiu dat a databází. Není to však jen oblast relačních databází, ale i jiná místa informatiky, kde se obecné funkce a relace skrývají či přímo explicitně objevují. Nejčastěji se setkáte s binárními relacemi, například vždy, když rozdělujete objekty podle „shodných" znaků (relace ekvivalence), nebo když objekty mezi sebou „porovnáváte" (relace uspořádání). Na tyto dvě základní oblasti se dále zaměříme.
Cíle
Úkolem této lekce je vybudovat matematický aparát (konečných) relací, s primárním zaměřením na funkce a binární relace typu ekvivalence a uspořádání. Ve vztahu k binárním relacím je zavedeno množství pojmů, které jsou později užitečné v různých oblastech matematiky i informatiky. Látka pak plynule pokračuje Lekcí 5.
4.1   Relace a funkce nad množinami
Vedle množin dalším důležitým základním „datovým typem" matematiky jsou relace, kterým vzhledem k jejich mnohotvárnému použití v informatice věnujeme významnou pozornost v této i dvou příštích lekcích.
Definice 4.1. Relace mezi množinami A\, ■ ■ ■ ,Ak, pro k G N,
je libovolná podmnožina kartézského součinu
R C Ai x • • • x Ak .
Pokud A\ = ■ ■ ■ = Ak = A, hovoříme o k-drní relaci R na A. Speciálně tak mluvíme třeba o binární (k = 2), ternární (k = 3) nebo unární (k = 1) relaci.
Komentář: Příklady relací.
* {(1, a), (2, a), (2, b)} je relace mezi {1, 2, 3} a {a, b}.
* {(i, 2 • i) | i £ N} je binární relace na N.
* {(i,j,i + j) \i,j £ N} je ternární relace na N.
* {3 • i | i G N} je unární relace na N.
* Jaký význam vlastně mají unární a nulární relace na A?
Uvědomme si, jak obecně je relace definována - její definice umožňuje podchytit skutečně libovolné „vztahy" mezi prvky téže i různých množin. V praxi se relace velmi široce využívají třeba v relačních databázích...
27
Funkce mezi množinami
Za první setkání s instancemi relací se většinou dá považovat pojem funkce. Přitom tradiční „školní" pojetí funkce ji obvykle identifikuje s nějakým výpočetním (analytickým) předpisem či vzorcem. Pojem funkce je však daleko obecnější a zcela abstraktní.
Definice 4.2. (Totální) funkce z množiny A do množiny B
je relace / mezi A a, B taková, že pro každé x E A existuje právě jedno y E B takové, že {x, y) E /. Množina A se nazývá definiční obor a množina B obor hodnot funkce /.
Komentář: Neformálně řečeno, ve funkci / je každé „vstupní" hodnotě x přiřazena jednoznačně „výstupní" hodnota y. (V obecné relaci počty „přiřazených" dvojic neomezujeme. ..)
Na druhou stranu si všimněte, že definiční obor i obor hodnot jsou součástí definice konkrétní funkce, neboli například v ukázce je oborem hodnot B = {a, b, c, d}, přestože samotné c není hodnotou pro žádný vstup.
Značení: Místo (x,y) G / píšeme obvykle f(x) = y. Zápis / : A —>• B říká, že / je funkce s definičním oborem A a oborem hodnot B. Funkcím se také říká zobrazení
Komentář: Příklady funkcí jsou třeba následující.
* Definujeme funkci / : N —> N předpisem f (x) = x + 8. Pak / = {(x, x + 8) | x G N}.
* Definujeme funkci plus :NxN-íN předpisem plus (i, j) = i + j. Pak plus = {(i, j, i + j) \i,j G N}.
Parciální funkce
Definice: Pokud naši Definici 4.2 upravíme tak, že požadujeme pro každé x E A nejvýše jedno y E B takové, že (x, y) E f, obdržíme definici parciální funkce z A do B.
Komentář:
V parciální funkci / nemusí být pro některé „vstupní" hodnoty x funkční hodnota definována (viz například f (2) v uvedeném obrázku).
Pro nedefinovanou hodnotu používáme znak _L.
Komentář: Následuje několik příkladů parciálních funkcí.
28
* Definujeme parciální funkci / : TL —> N předpisem
, .      í 3 + i    jestliže x > 0. Hx>=\ j_ jinak.
Tj. / = {(x,3 + x) | x G N}.
* Také funkce / : R —> R daná běžným analytickým předpisem f(x) = log x je jen parciální - není definována pro x < 0.
* Co je relace, přiřazující lidem v CR jejich (česká) rodná čísla?
4.2   Reprezentace konečných relací
Oblastí, kde informatici nejčastěji potkají obecné relace, je bezesporu ukládání dat. To proto, že shromažďovaná data, stejně jako relace, především sledují vztahy mezi objekty. Na druhou stranu je relační databáze zcela obecnou ukázkou reprezentace jakékoliv relace, kterou si ilustrujeme příkladem.
Příklad 4.3. Tabulka relační databáze prezentuje obecnou relaci. Definujme následující množiny („elementární typy")
* ZNAK = {a, • • • ,z,A,--- , Z, mezera},
* ČÍSLICE = {0,1, 2, 3,4, 5, 6, 7, 8, 9}.
Dále definujeme tyto množiny („odvozené typy")
* JMÉNO = ZNAK15,     PŘÍJMENÍ = ZNAK20,     VEK = ČÍSLICE3,
* ZAMESTNANEC  „G" JMÉNO x PŘÍJMENÍ x VEK. Relaci „typu" ZAMESTNANEC pak lze reprezentovat tabulkou:
jméno	příjmení	vek
Jan	Novák	42
Petr	Vichr	28
Pavel	Zima	26
Stanislav	Novotný	52
□
Reprezentace binárních relací na množině
Jistě čtenáři uznají, že zadání relace výčtem jejích složek není pro člověka (na rozdíl od počítače) tím nej příjemnějším způsobem. Je tedy přirozené se ptát, jak co nejnázorněji takovou relaci, alespoň v její nejčastější binární podobě, ukázat.
Značení: Binární relaci i? C M x M lze jednoznačně znázornit jejím grafem:
• Prvky M znázorníme jako body v rovině.
• Prvek (a, b) G R znázorníme jako orientovanou hranu („šipku") z a do b. Je-li a = b, pak je touto hranou „smyčka" na a.
29
Komentář: Pozor, nejedná se o „grafy funkcí" známé z matematické analýzy.
Například mějme M = {a,b,c,d,e, /} a R = {(a,a), (a,b), (b,c), (b, d), (b, e), (b, f), (d, c), (e, c), (/, c), (e, d), (e, /), (/, b)}, pak:
c
V případě, že M je nekonečná nebo „velká", může být reprezentace R jejím grafem nepraktická (záleží také na míře „pravidelnosti" R).
Značení: Binární relaci R C M x M \ze jednoznačně zapsat také pomocí matice relace - matice A typu M x M s hodnotami z {0,1}, kde g^j = 1 právě když (i, j) G R.
1 0  0  0 0\
0 1111
0 0   0   0 0
0 10   0 0
0 110 1
1 1   0   0 0/
4.3   Vlastnosti binárních relací
Pro začátek dalšího matematického výkladu relací si výčtem a doprovodnými schematickými obrázky uvedeme pět základních vlastností binárních relací, které nás typicky v matematice zajímají.
Definice 4.4.   Nechť R C M x M. Binární relace R je
• reflexivní, právě když pro každé a E M platí (a, a) G R:
• ireflexivní, právě když pro každé a E M platí (a, a) £ R:
• symetrická, právě když pro každé a, b G M platí, že jestliže (a, b) G R, pak také (b, a) G R;
a
• antisymetrická, právě když pro každé a,b G M platí, že jestliže (a, b), (b, a) G R, pak
30
• tranzitivní, právě když pro každé a,b,c E M platí, že jestliže (a,b), (b,c) G R, pak
Následují dva základní typy binárních relací; kde i? je
• relace ekvivalence, právě když je i? reflexivní, symetrická a tranzitivní:
• částečné uspořádání, právě když je R reflexivní, antisymetrická a tranzitivní (často říkáme jen uspořádání).
Komentář: Pozor, může být relace symetrická i antisymetrická zároveň? Ano!
Vezměte si relaci R = {(x, x) \ x G M}, která obě jmenované vlastnosti splňuje. Proto pokud jste třeba dotázáni, zda relace je symetrická, nestačí se v odpovědi odvolávat na fakt, že je antisymetrická(!), neboť tyto vlastnosti se nevylučují.
Příklad 4.5. Několik příkladů relací defínovaných v přirozeném jazyce.
Nechť M je množina všech studentů 1. ročníku FI. Uvažme postupně relace R C M x M definované takto
* (x, y) G R právě když x a y mají stejné rodné číslo:
* (x, y) G R právě když x má stejnou výšku jako y (dejme tomu na celé mm):
* (x, y) E R právě když výška x a y se neliší více jak o 2 mm:
* (x, y) E R právě když x má alespoň takovou výšku jako y:
* (x, y) E R právě když x má jinou výšku než y (dejme tomu na celé mm):
* (x, y) E R právě když x je zamilován(a) do y.
Zamyslete se podrobně, které z definovaných vlastností tyto jednotlivé relace mají. Které z nich tedy jsou ekvivalencí nebo uspořádáním? □
Příklad 4.6. Jaké vlastnosti mají následující relace?
* Buď f? C N x N definovaná takto (x, y) E R právě když x dělí y. (Částečné uspořádání. ale ne každá dvě čísla jsou porovnatelná.)
* Buď i?CNxN definovaná takto {x, y) E R právě když x a y mají stejný zbytek po dělení číslem 5. {Ekvivalence.)
* Nechť F = {f \ f : ¥S —^N}je množina funkcí. Buď R C F x F definovaná takto (f, g) E R právě když f (x) < g (x) pro všechna x. (Ireňexivní, antisymetrická a tranzitivní, ale ne reflexivní - striktně řečeno není uspořádáním.) □
a
b
c
31
4.4   Relace ekvivalence
Nyní se hlouběji podívejme na první specifický typ binární relace zmíněný výše: Podle Definice 4.4 je relace R C M x M ekvivalence právě když R je reflexivní, symetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace i? je ekvivalence.
Komentář: Jak vypadá graf relace ekvivalence? Poměrně příznačně, jak nám ukazuje následující obrázek (všimněte si absence šipek, která je dána symetrií relace).
9
6
Neformálně řečeno; ekvivalence je relace i? C M x M, taková, že (x, y) G i? právě když x a y jsou v nějakém smyslu „stejné".
Značení. V případě relace ekvivalence se někdy lze setkat s pojmenováním jako ~ či « místo R. Místo (x, y) G R se pak píše x »2 y.
Příklad 4.7. Nectí M je množina všech studentů 1. ročníku FI. Uvažme postupně relace R C M x M defínované následovně a zkoumejme, zda se jedná o ekvivalence:
* (x, y) E R právě když x má stejnou výšku jako y:
* (x, y) E R právě když x má stejnou barvu vlasů jako y:
* (x, y) E R právě když x, y mají stejnou výšku a stejnou barvu vlasů;
* (x, y) E R právě když x, y mají stejnou výšku nebo stejnou barvu vlasů.
U kterého body se nejedná o relaci ekvivalence a proč? Je to poslední případ, kdy není splněna tranzitivita. □
Uvedený příklad ukazuje na náaledující univerzální poznatek, který může platit (a taky platí) pouze pro průnik a nikoliv pro sjednocení.
Tvrzení 4.8. Nechi R, S jsou dvě relace ekvivalence na stejné množině M. Pak jejich průnik R C\ S je opět relací ekvivalence.
Důkaz (náznak): Jelikož reflexivita a symetrie je zřejmá, stačí snadno ověřit platnost tranzitivity na RílS. Nechť (a, b), (b, c) E RC\S, pak podle tranzitivity každé samostatné z R, S plyne (a, c) G R a zároveň (a, c) E S. □
Příklad 4.9. Nechť i? C N x N je binární relace defínovaná takto: (x,y) E R právě když \x — y\ je dělitelné třemi.
V jakém smyslu jsou zde x a, y „stejné"? Dávají stejný zbytek po dělení třemi. □
Příklad 4.10. Buď R binární relace mezi všemi studenty na přednášce FP.IB000 defínovaná takto: (x, y) E R právě když x i y sedí v první lavici.
Už na „první pohled" jde o relaci symetrickou a tranzitivní. Proč se v tomto případě nejedná o relaci ekvivalence? Protože není reflexivní pro studenty sedící v dalších lavicích. (Takže si dávejte dobrý pozor na správné pochopení definic.) □
32
4.5   Rozklady a jejich vztah k ekvivalencím
Náplní následující části výkladu je ukázat jiný přirozený pohled na ekvivalence. Tento nový pohled nám matematicky formalizuje představu ekvivalence jako rozdělení prvků nosné množiny M na „hromádky", přičemž prvky každé jednotlivé hromádky jsou si navzájem v jistém smyslu „stejné".
Definice 4.11. Rozklad množiny. Nechť M je množina.
Rozklad (na) M je množina podmnožin M C 2M splňující následující tři podmínky:
- 0 ^ M (tj. každý prvek M je neprázdná podmnožina M):
- pokud A,B eN, pak buď A = B nebo A H B = 0:
- UAeMA = M-
Prvkům M se také říká třídy rozkladu.
Komentář:
* Buď M = {a, b, c, d}. Pak M = {{a}, {b, c}, {d}} je rozklad na M.
* Nechť A0 = {k G N | k mod 3 = 0}, Ax = {k G N | k mod 3 = 1}, A2 = {k G N j k mod 3 = 2}. Pak J\í = {^0,^1,^2} je rozklad všech přirozených čísel N podle zbytkových tříd.
Každý rozklad M na M jednoznačně určuje jistou ekvivalenci R^f na M:
Věta 4.12. Nechi M je množina a M rozklad na M. Nechi Rjy C M x M je relace na M definovaná takto
(x, y) E Rjy právě když existuje A E M taková, že x, y E A.
Pak R^f je ekvivalence na M.
Důkaz: Dokážeme, že Rjy je reůexivní, symetrická a tranzitivní {Dennice 4.4).
• Reflexivita: Buď x E M libovolné. Jelikož M je rozklad na M, musí existovat A E M takové, že x E A (jinak spor se třetí podmínkou z Defínice 4.11). Proto (x,x) E Rjy, tedy R^f je reflexivní.
• Symetrie: Nechť (x,y) E Rjy. Podle definice Rjy pak existuje A E M taková, že x, y E A. To ale znamená, že také (y,x) E Rj^ podle definice R^f, tedy R^f je symetrická.
• Tranzitivita: Nechť (x,y), (y,z) E Rjy. Podle definice Rjy existují A, B E M takové, žex,yEAay,zEB. Jelikož A H B 7^ 0, podle druhé podmínky z Defínice 4.11 platí A = B. Tedy x, z E A = B, proto (x, z) E Rj^ podle definice R^f. □
Každá ekvivalence R na, M naopak jednoznačně určuje jistý rozklad M/R na M:
Věta 4.13. Nechť M je množina a R ekvivalence na M. Pro každé x E M definujeme množinu
[x] = {yEM\ (x,y)ER}. Pak {[x] I x E M} je rozklad na M, který značíme M/R a čteme „rozklad M podle R".
33
Důkaz: Dokážeme, že M/R splňuje podmínky Defínice 4.11.
• Pro každé [x] E M/R platí [x] ^ 0, neboť x G [x].
• Nechť [x], [y] G M j R. Ukážeme, že pokud [x] H [y] 7^ 0, pak [x] = [y].
Jestliže [x] H [y] 7^ 0, existuje z E M takové, že z E [x] a z E [y]. Podle definice [x] a [y] to znamená, že (x, z), (y, z) G R. Jelikož R je symetrická a (y, z) G R, platí (z, y) G R. Jelikož (x, z), (z, y) E R a, R ]e tranzitivní, platí (x, y) E R. Proto také (y, x) E R (opět ze symetrie R). Nyní dokážeme, že [y] = [x]:
* v[x] ^ [y] ": Nechť v G [x]. Pak (x, v) G R podle definice [x]. Dále (y, x) G i? (viz výše), tedy (y, v) G i? neboť R je tranzitivní. To podle definice [y] znamená, že v G [y].
* j,[y] ^ M ": Nechť u G [y]. Pak (y, v) G i? podle definice [y]. Dále (x, y) G R (viz výše), tedy (x, v) G i? neboť i? je tranzitivní. To podle definice [x] znamená, že v G [x].
• Platí |J,, e M,R [x] = M, neboť x E [x] pro každé x E M.
Navazující studium
Mějte na paměti, že na pojmech množin, relací a funkcí jsou vystavěny prakticky všechny skutečné datové struktury používané v dnešní informatice, což můžete vidět na relačních databázích (viz také Lekce 6) a na často se vyskytujících induktivních dennících (Oddíl 6.5). S relacemi ekvivalence i jimi implicitně deňnovanými rozklady množin se lze setkat tam, kde nějaké objekty "rozdělujeme do přihrádek" podle nějakých sdílených znaků nebo jiných kritérií. Principy takových rozkladů vám zajisté byly intuitivně známy ještě dříve, než jste vůbec slyšeli o matematickém pojmu ekvivalence, v této lekci jsme si je jen uvedli na formálních základech. Toto formální pojetí relací ekvivalence a rozkladů budete potřebovat v různých navazujících předmětech, například u teorie automatů.
34
5   Uspořádané množiny, Uzávěry
Úvod
V této lekci dále pokračujeme probíráním binárních relací na množinách jako nástrojů vyjadřujících vztahy mezi objekty. Zaměřujeme se nyní především na relace „ srovnávající" objekty podle jejich vlastností. Takto vágně opsané relace mívají jasné společné znaky, které se objevují ve zde uvedené formální dehnici relace uspořádání. Následně se také zabýváme způsobem, jak libovolnou relaci „obohatit" o nějakou vlastnost. Tento úkol vede na rozšiřování naší relace (tj. přidávání dvojic) do vzniku jejího takzvaného uzávěru.
Cíle
Dehnujeme relace uspořádání a mnohé další pojmy k nim se vztahující, například Hasseovy diagramy. Studující by měli porozumět matematické problematice uspořádaných množin a naučit se je správně používat. Závěrem si ukážeme operátory uzávěrů relací.
5.1   Uspořádání a uspořádané množiny
Podle Definice 4.4 je relace R C M x M (částečné) uspořádání právě když R je reflexivní, antisymetrická a tranzitivní. Tyto tři vlastnosti tedy musí být splněny a ověřeny k důkazu toho, že daná relace R je uspořádáním.
Komentář: Neformálně řečeno: uspořádání je taková relace i? C M x M, kde (x,y) G R právě když x je v nějakém smyslu „menší nebo rovno" než y. Mohou ovšem existovat taková x, y G M, kde neplatí (x, y) G R ani (y, x) G R. (Pak říkáme, že x a y jsou nesrovnatelné.)
Jak názorně zobrazit (částečné) uspořádání? Příklad zjednodušeného zakreslení (jsou vynechány šipky vyplývající z reflexivity a tranzitivity, viz Oddíl 5.3) je zde:
8 12
dělitelnost:
2 3      5 7 11
Všimněte si, že je někdy zvykem „větší" prvky kreslit nad ty „menší".
Značení. Pro větší přehlednost se relace uspořádání často značí symboly jako C či ^ místo prostého R. I my tak často budeme psát třeba x ^ y místo {x, y) G R.
Poznámka: Zajisté jste se již neformálně setkali s „neostrým" uspořádáním čísel < a „ostrým" uspořádáním < . Všimněte si dobře, že námi definované uspořádání je vždy „neostré". Pokud byste naopak chtěli definovat „ostréíl uspořádání, mělo by vlastnosti ireňexivní, antisymetrická a tranzitivní. (Příliš se však tato varianta nepoužívá.) Nadále budeme pracovat pouze s neostrým uspořádáním, ale smyčky vyplývající z reflexivity budeme pro větší přehlednost v obrázcích vynechávat.
35
Uspořádaná množina
Matematicky důležitějším pojmem než samotná relace uspořádání je uspořádaná množina, neboli soubor prvků s pevně zvoleným uspořádáním na nich.
Definice 5.1. Uspořádaná množina je dvojice (M, ^), kde M je množina a ^ je (částečné) uspořádání na M.
Definice: Uspořádání ^ na M je lineární (nebo také úplné), pokud každé dva prvky M jsou v -< srovnatelné.
Příklady uspořádaných množin
Příklad 5.2. Nechi M je množina všech studentů 1. ročníku FI. Uvažme postupně relace uspořádání R C M x M defínované následovně (jedná se vždy o uspořádání?):
* (x, y) E R právě když x má alespoň takovou výšku jako y:
* (x, y) E R právě když y má alespoň takovou výšku jako x:
* (x, y) E R právě když x a y mají stejné rodné číslo.
Ano, i v posledním bodě se jedná o uspořádání! (Dobře si promyslete, proč. Které dvojice jsou vůbec porovnatelné?) □
Příklad 5.3. Další ukázky uspořádaných množin následují zde:
* (N, <) je lineárně uspořádaná množina, kde < má „obvyklý" význam.
* (N, | ), kde a\b je relace dělitelnosti „a dělí 6" na přirozených číslech, je uspořádaná množina. Toto uspořádání není lineární.
* Buď M množina. Pak (2M, C) je uspořádaná množina (říkáme inkluzí). Které dvojice jsou v uspořádání inkluzí nesrovnatelné!
la b, c}
□
Komentář: Zamyslete se také, jak vypadá relace dělitelnosti na celých (tj. i záporných) číslech. Proč se už nejedná o uspořádání? Blíže viz konec Oddílu 5.2.
Užitečnou dovedností je umět popsat uspořádání „větší množiny" pomocí „malých" složek. Neformálně lze toto uvést následujícími příklady:
Příklad 5.4. Uspořádání „po složkách".
Nechť (A, <a) a (B, <b) jsou uspořádané množiny. Definujme binární relaci C na A x B předpisem
(a,b) C (ď, b')    právě když    a <a a! a, b <b V. Pak (A x B, C) je uspořádaná množina. Toto uspořádání se nazývá „po složkách". □
36
Příklad 5.5. Lexikografické uspořádání.
Nechť (A, <a) a (B, <b) jsou uspořádané množiny. Definujme binární relaci ^ na A x B předpisem
(a, b) ^ (a', b')    právě když    buď a <a a'ao / a', nebo a = a' a 6 6'.
Pak (AxB, ^) je uspořádaná množina. Navíc pokud <a i <b jsou lineární, je i -< lineární. Toto uspořádání se nazývá lexikografické. □
Fakt: Jsou-li (Ai, <i), ■ ■ ■ ,(An,<n) uspořádané množiny, kde n > 2, pak množinu Ai x • • • x An lze uspořádat třeba po složkách nebo lexikografícky. Všimněte si, že lexikograficky se například řadí slova ve slovníku...
5.2   Další pojmy uspořádaných množin
K tématu uspořádaných množin se vztahuje množství drobných pojmů, které potkáte v různých oblastech matematiky i informatiky.
Definice 5.6.   Nechť (M, ^) je uspořádaná množina. • x E M je minimální právě když pro každé y E M platí, že jestliže y ^ x, pak x ^ y. (Tj. x je minimální právě když neexistuje žádný prvek ostře menší než x.)
x
• x G M je maximální právě když pro každé y E M platí, že jestliže x ^ y, pak y ^ x. (Tj. x je maximální právě když neexistuje žádný prvek ostře větší než x.)
• x G M je nejmenší právě když pro každé y E M platí, že x <y.
X
> x E M je největší právě když pro každé y E M platí, že y <x.
> x E M pokrývá y E M právě když x ^ y, y ^ x a neexistuje žádné z E M takové, že x^z^yay^z^x. x
x E M je do/m' závora (mez) množiny ACM právě když x ^ y pro každé y E A.
y e
A A
A
x E M ]e horní závora (mez) množiny ACM právě když y -< x pro každé y E A.
37
• x G M je ínfimum množiny ACM právě když x je největší dolní závora množiny A.
» x G M je supremum množiny A C M, právě když x je nejmenší horní závora množiny A.
• A C M je řetězec v uspořádání ^ právě když (A, ^) je lineárně uspořádaná množina.
Komentář: Tuto dlouhou definici se sluší poněkud neformálně okomentovat. Za prvé, s pojmy nejmenšího a největšího prvku jste se už intuitivně setkali mnohokrát, ale (matematicky slabší) pojmy minimálního a maximálního působí někdy problémy. Zapamatujte si proto dobře, že minimálních prvků může mít množina několik, jsou to prostě všechny ty "vespod", ale nejmenší prvek existuje nejvýše jeden a je to pouze ten unikátní minimální prvek množiny. Stejně pro maximální...
Další poznámka se vztahuje k infimu a supremu množiny. Jak jsme napsali (a asi totéž znáte z matematické analýzy), množina nemusí mít nejmenší ani největší prvek, ale v mnoha případech je lze "nahradit" po řadě infimem a supremem, které hrají v jistých ohledech podobnou roli. Avšak ani supremum a infimum nemusí vždy existovat.
Pozor! Některé uvedené definice mají dosti „netriviální chování" na nekonečných množinách. Proto je budeme obvykle uvažovat jen nad konečnými množinami.
Příklad 5.7. Proč má každá uspořádaná množina nejvýše jeden největší prvek?
Tvrzení dokážeme sporem: Nechť m i n jsou největší prvky uspořádané množiny (M, ^). Pak podle Definice 5.6 platí n ^ m i m ^ n zároveň. Ovšem jelikož uspořádání musí být antisymetrické, pak platí m = n a největší prvek je jen jeden. □
Relace předuspořádání
Mimo uspořádání chápaných striktně antisymetricky se v praxi často setkáme s „sko-rouspořádáními", ve kterých některé očividně různé prvky stojí na stejné úrovni naší preference. Jak třeba uspořádáte různé počítače podle výkonu nebo studenty podle známek A-E? To matematicky podchytí následující pojem.
Definice: Relace R C M x M je předuspořádání (také kvazíuspořádání, nebo polouspořádání) právě když R je reůexivní a tranzitivní.
Komentář: Rozdíl mezi uspořádáním a předuspořádáním je (neformálně řečeno!) v tom, že u předuspořádání srovnáváme prvky podle kritéria, které není pro daný prvek jedinečné. V předuspořádání takto mohou vznikat „balíky" (třídy) se stejnou hodnotou kritéria, což
38
schematicky ilustrujeme na následujícím obrázku.
©
Důležitým poznatkem je, že předuspořádání se „až tak moc" neliší od dřívějšího uspořádání - přirozeně totiž odvodíme následující:
Věta 5.8. Je-li C předuspořádání na M, můžeme definovat relaci ~ na M předpisem
Pak (Mj ~, -<) je uspořádaná množina indukovaná C.
Komentář: Pro ukázku si vezměme relaci dělitelnosti na tl. Pak třeba —2 ~ 2. Jádrem zde jsou dvojice čísel stejné absolutní hodnoty.
Důkaz (náznak): Tranzitivita a reflexivita relace ~ vyplývá z tranzitivity a reflexivity relace C. Symetrie ~ pak je přímým důsledkem její definice. Tudíž ~ skutečně je relací ekvivalence a M j ~ je platný rozklad nosné množiny.
Tranzitivita a reflexivita relace -< se opět dědí z relace C. Její antisymetrie vyplývá následující úvahou: Pokud [x] ^ [y] a [y] ^ [x], pak podle naší definice x C y a y C x, neboli i ~ i/ a [i] = [y] podle definice tříd rozkladu. Pozor, nej důležitější částí této větve důkazu je však ještě zdůvodnění, že naše podaná definice vztahu [x] ^ [y] je korektní, což znamená, že její platnost nezávisí na konkrétní volbě reprezentantů x z [x] a y z [y].
Poslední zmíněné tvrzení dokážeme sporem: Nechť x, x' G [x] a y, y' E [y] jsou (možná různí) reprezentanti dvou zkoumaných tříd rozkladu M j ~, pro které však platí x C y a x' □ í/. Podle definice třídy rozkladu je x ~ y a rr' ~ y' a z tranzitivity x C y C ?/' C x' C x a tudíž [x] = [y] a na volbě reprezentanta skutečně nezáleží. □
5.3   Hasseovské diagramy
Motivací zavedení tzv. Hasseovských diagramů uspořádaných množin jsou přehlednější „obrázky" než u grafů relací. Například si srovnejte následující ukázky:
Definice: Hasseovský diagram konečné uspořádané množiny (M, ^) je jeho (jednoznačné) grafické znázornění získané takto:
x ~ y    právě když    x C y a y C x.
Pak ~ je ekvivalence na M, která se nazývá jádro předuspořádání'C. Na rozkladu Mj ~ pak lze zavést relaci -< definovanou takto
[x] ^ [y]    právě když x C y.
39
* Do první „horizontální vrstvy" zakreslíme body odpovídající mininálním prvkům {M, ^). (Tj. které nepokrývají nic. Pojem pokrývání prvku najdete v Definici 5.6.)
* Máme-li již zakreslenu vrstvu i, pak do vrstvy i + 1 (která je „nad" vrstvou i) zakreslíme všechny nezakreslené prvky, které pokrývají pouze prvky vrstev < i. Pokud prvek x vrstvy i + 1 pokrývá prvek y vrstvy < i, spojíme x a y neorientovanou hranou (tj. „čárou").
Příklad 5.9. Relaci inkluze na čtyřprvkové množině {a,b,c,d} zakreslíme Has-seovským diagramem takto:
Komentář: Jak vidíme, v Hasseovském diagramu „vynecháváme" ty hrany relace ^, které vyplývají z reňexivity či tranzitivity. To celý obrázek výrazně zpřehlední, a přitom nedochází ke ztrátě informace. Lze vynechat i šipky na hranách, neboť dle definice všechny míří „vzhůru". Také pojem „vrstvy" v definici je jen velmi neformální, důležité je, že větší (pokrývající) prvky jsou nad menšími (pokrývanými).
5.4   Uzávěry relací
Posledním bodem našeho výkladu je postup, jak danou relaci můžeme „obohatit" o zvolenou vlastnost (například proto, že naše data o relaci jsou neúplná a vlastnost je tak poškozena).
Definice: Buď V (nějaká) vlastnost binárních relací. Řekneme, že V je uzavíratelná, pokud splňuje následující podmínky:
* Pro každou množinu M a každou relaci R C M x M existuje alespoň jedna relace S C M x M, která má vlastnost V a pro kterou platí R C S.
* Nechť J je množina a nechť Ri C M x M je relace mající vlastnost V pro každé i E I. Pak relace f]ieI rí má vlastnost V.
Fakt: Libovolná kombinace vlastností reňexivita, symetrie, tranzitivita je uzavíratelná vlastnost. Antisymetrie není uzavíratelná vlastnost.
Věta 5.10. Nechť V je uzavíratelná vlastnost binárních relací. Buď M množina a R libovolná binární relace na M. Pak pro množinu všech relací S D R na M majících vlastnost V existuje infímum Ry (vzhledem k množinové inkluzi), které samo má vlastnost V.
Definice: Tuto „nejmenší" relaci Ry s vlastností V nazýváme V-uzávěrrelace R.
Tvrzení 5.11. Nechť f? je binární relace na M. Pak platí následující poznatky.
* Reflexivní uzávěr R je přesně relace R U {(x, x) | x G M}.
□
40
* Symetrický uzávěr R je přesně relace R= {(x,y) | (x, y) G R nebo (y, x) G R}.
* Tranzitivní uzávěr R je přesně relace R+ = T1 (R), kde T je funkce, která pro každou binární relaci S vrátí relaci
T (S) = S U {(x, z) | existuje y takové, že (x, y), (y, z) G S}
a T1 = X ° '"" ° 7~y Je 2-krát iterovaná aplikace funkce T.
i
* Reflexivní a tranzitivní uzávěr f? je přesně relace R* = Q+, kde Q je reflexivní uzávěr R.
* Reflexivní, symetrický a tranzitivní uzávěr R (tj. nejmenší ekvivalence obsahující R) je přesně relace (Q)+, kde Q je reflexivní uzávěr f?.
* Na pořadí aplikování uzávěrů vlastností záleží!
Komentář: Význam reflexivních a symetrických uzávěrů je z předchozího docela zřejmý. Význam tranzitivního uzávěru R+ je následovný: Do R+ přidáme všechny ty dvojice (x, z) takové, že v i? se lze „dostat po šipkách" z x do z. Nakreslete si to na papír pro nějakou jednoduchou relaci, abyste význam tranzitivního uzávěru lépe pochopili.
•-í=—•-í=—•-2> •
A jak bylo dříve řečeno, antisymetrický uzávěr relace prostě nemá smysl. Například buď fiCNxN definovaná takto: R = {(i, i +1) | i G N}. Pak R* je běžné lineární uspořádání < přirozených čísel.
Příklad 5.12. Proč při výpočtu tranzitivního uzávěru relace na konečné množině podle vzorce R+ = \Jt*L1T"t(R) vždy stačí uvažovat konečně mnoho členů tohoto sjednocení?
Pro odpověď si uvědomme zásadní fakt — pokud 7~í+1 = T\ tak už platí 7~í+fc = T% pro všechna přirozená k. Neboli je potřeba sjednotit jen tolik prvních členů, dokud se ony „zvětšují", což může nastat jen konečně krát nad konečnou množinou. Mimo jiné tak vidíme, že uvedený popis tranzitivního uzávěru je konstruktivní. □
Rozšiřující studium
I v této lekci se pojednává o látce, kterou určitě čtenáři na inuitivní úrovni znají (vždy umění si věci „uspořádat" je jednou ze základních lidských dovedností). Přesto správné matematické uchopení podstaty uspořádání vyžaduje se prokousat několika nesnadnými formálními deňnicemi. Všimněte si, že hlavní těžkosti pojmu uspořádané množiny se vztahují k částečným, tedy ne-lineárním, uspořádáním, kdy běžnému lidskému uvažování není zcela intuitivně jasné nakládání s nesrovnatelnými dvojicemi. Ostatně to dobře znáte ze života, kdy seřazujete objekty (výrobky, apod) podle více kritérií a přirozeně tak vyvstávají nesrovnatelné dvojice.
41
6   Skládání relací a funkcí
Úvod
Vraťme se nyní k látce Lekce 3. Z jejího pokročilého obsahu jsme doposud velmi detailně probírali relace a jejich jednotlivé vlastnosti. Nyní se podívejme, jak lze relace mezi sebou skládat, což je například základní technika práce s relačními databázemi. Je však i jiné místo, kde jste se zajisté se skládáním relací setkali - jedná se o skládání funkcí. Jak například spočítáte na kalkulačce výsledek složitějšího vzorce?
Mimo to se ještě zobecněně vrátíme k problematice „postupných" (induktivních a rekurentních) dehnic a vztahů. Jedná se vlastně o matematické analogie rekurzivních programů a jejich správné formální pochopení oceníme mimo jiné i při programování samotném.
Cíle
V této lekci dehnujeme základní vlastnosti funkcí a především popíšeme a podrobně rozebereme skládání relací a návazně skládání funkcí jako relací (jako model nám poslouží permutace). Na závěr se stručně podíváme na problematiku induktivních dehnic funkcí, coby na rozšíření rekurentních vztahů z Oddílu 3.4.
6.1   Vlastnosti funkcí
Funkce je podle Definice 4.2 speciálním případem (obvykle binární) relace, majícím pro každou hodnotu levé strany jedinou (funkční) hodnotu pravé strany. Více o funkcích řekne následující definice.
Definice 6.1. Funkce (případně parciální funkce) / : a —> b je * ínjektívní (nebo také prostá) právě když pro každé x,y G a, x ^ y platí f(x) ý f{v)\
* surjektívní (nebo také „na") právě když pro každé y E b existuje x E a takové, že
f (x) = y,
	"V—i	(7)
		Y
* bíjektívní (vzáj. jednoznačná) právě když je injektivní a současně surjektivní.
Funkce nás coby speciální případ relací budou provázet i ve zbytku lekce. Komentář: Následují jiné ukázky vlastností funkcí. * Funkce plus : N x N —> N je surjektivní, ale není prostá.
42
* Funkce g : Z —> N daná předpisem
g(x
je bijektivní.
* Funkce 0 : (
* Funkce 0 : (
—2x — 1 jestliže x < O, 2x jinak
0 je bijektivní.
{a, b} je injektivní, ale není surjektivní.
* Dokázali byste nalézt bijektivní funkci NxN-> N?
6.2   Inverzní relace a skládání relací
K použitelné práci s relacemi v aplikacích se dostaneme, pokud budeme umět relace správně „skládat" a „převracet". K tomu nás přivedou zase následující definice.
Definice: Nechť R C A x B je binární relace mezi A a B. Inverzní relace k relaci R se značí R^1 a je definována takto:
R-1 = {(b,a) | (a, b) G R}
R:
R    je tedy relace mezi B a A.
A
R
-i.
Komentář: Příklady inverzí pro relace-funkce.
* Inverzí bijektivní funkce f(x) = x + 1 na Z je funkce f^1(x)
* Inverzí prosté funkce f(x) = ex na R je parciální funkce
= x — 1. x) = ln x.
* Funkce g(x) = x mod 3 není prostá na N, a proto její inverzí je „jen "relace g 1 = {(a,6) a = 6 mod 3}. Konkr. g'1 = {(0, 0), (0, 3), (0, 6),... , (1,1), (1,4),... , (2, 2), (2, 5),... }.
Tvrzení 6.2. Mějme funkcí f : A —^ B. Pak její inverzní relace f^1 je
a) parciální funkce právě když f je prostá,
b) funkce právě když f je bijektivní.
Důkaz vyplývá přímo z definic funkce a inverze relace. □ Následuje klíčová definice, pro jejiž bližší ilustraci odkazujeme také na Příklad 6.4. Definice 6.3. Složení (kompozice) relací R a S.
Nechť RCAxB&SCBxC jsou binární relace. Složení relací R a S (v tomto pořadí!) je relace S o R G A x C definovaná takto:
S o R = {(a, c) | existuje b G B takové, že (a, b) G R, (b, c) G S}
43
Komentář: Několik matematických příkladů skládání relací následuje zde. Jg~li
- A = {a,b},   5 = {1,2},   C = {X,Y},
- R = {(a,l),(b,l),(b,2)},   S = {(1,X)}, pak složením vznikne relace
- SoR = {(a,X),(b,X)}.
* Složením funkcí h(x) = x2 a f(x) = x + 1 na R vznikne funkce
(foh)(x)=f(h(x)) = x2 + l.
* Složením těchže funkcí „naopak" ale vznikne funkce (h o /) (x) = h(f(x)) = (x + l)2.
Poznámka: Nepříjemné je, že v některých oblastech matematiky (například v algebře při skládání zobrazení) se setkáme s právě opačným zápisem skládání, kdy se místo S o R píše R ■ S nebo jen RS. Proto je si vždy dobré slovně ujasnit, které pořadí skládaných relací máme na mysli. My zde zásadně budeme používat pořadí S o R.
6.3   Skládání relací „v praxi"
Podívejme se nyní, jak se skládání relací přirozeně objevuje v práci s relačními databázemi. (Dá se zjednodušeně říci, že právě v operátoru skládání tabulkových relací tkví hlavní smysl relačních databází...)
Příklad 6.4. Skládání v relační databázi studentů, jejich předmětů a fakult.
Mějme dvě binární relace - jednu R přiřazující studentům MU kódy jejich zapsaných předmětů, druhou S přiřazující kódy předmětů jejich mateřským fakultám. Malý výsek z těchto relací může v tabulkové reprezentaci vypadat třeba následovně.
R :
student (učo)	předmět (kód)		předmět (kód)	fakulta MU
121334	MA010		MA010	FI
133935	M4135	S :	IB000	FI
133935	IA102		IA102	FI
155878	M1050		M1050	PřF
155878	IB000		M4135	PřF
Jak z těchto „tabulkových" relací zjistíme, kteří studenti mají zapsané předměty na kterých fakultách (třeba na FI)?
44
Jedná se jednoduše o složení relací S o R. V našem příkladě tabulkové reprezentace vyjde výsledek:
SoR:
student (učo)	fakulta MU
121334	FI
133935	FI
133935	PřF
155878	FI
155878	PřF
□
Zobecněné skládání relací
V praktických použitích relačních tabulek povětšinou nevystačíme jen s binárními relacemi, takže je přirozené se ptát, jestli lze podobně skládat i více-ární relace. Odpověď je snadná - lze to a ani nepotřebujeme novou definici, vystačíme s tou, kterou už máme výše uvedenou.
Definice: (skládání relací vyšší arity):
Mějme relace T C K\ x _řr2 x • • • x Kk a U C L\ x L2 x • • • x Lp, přičemž pro nějaké m < min(A;, l) platí L\ = Kk-m+i, L2 = Kk-m+2, ■ ■ ■, Lm = Kk- Pak relaci T lze složit s relací U na zvolených m složkách L1;..., Lm („překrytí") s použitím Defínice 6.3 takto:
Položme A = Kľ x ■ ■ ■ x Kk_m, B = Li x ■ ■ ■ x Lm a C = L
m+l
x Lp.
* Příslušné relace pak jsou  R = {(a, b) G A x B | (ai,... a^-m, b±,... bm) G T} a S = {(b,č) G B x C | (b1,...bm,cm+1,...ce) G U}.
* Nakonec přirozeně položme U om T ~ S o R, takže vyjde
UomT = {(a, č) | ex. 6 G -B, že (ai,... afc_m, &i,... bm) G T a (&i,... bm, cm+1,... cp>) G U) .
Schematicky pro snažší orientaci ve složkách našich relací:
T C Kľx U C
U om T C    iři x
x Kk-m x    Kk-m+1 X ■ ■ ■ X Kk
L\    x ''' x Lm   xL^yi^Y x ''' x Lp]
x Kk-m x       ._ _.       x L-m+l X ■ ■ ■ X Lp
a * c
Opět je nejjednodušší si koncept skládání vícečetných relací ilustrovat příkladem.
Příklad 6.5. Skládání v relační databázi pasažérů a letů u leteckých společností.
Podívejme se na příklad hypotetické rezervace letů pro cestující, relace T. Jak známo (tzv. codeshare), letecké společnosti si mezi sebou „dělí" místa v letadlech, takže různé lety (podle kódů) jsou ve skutečnosti realizovány stejným letadlem jedné ze společností. To zase ukazuje relace U.
T :
pasažér	datum	let		datum	let	letadlo
Petr	5.11.	OK535		5.11.	OK535	CSA
Pavel	6.11.	OK535	U :	5.11.	AF2378	ČSA
Jan	5.11.	AF2378		5.11.	DL5457	ČSA
Josef	5.11.	DL5457		6.11.	OK535	AirFrance
Alena	6.11.	AF2378		6.11.	AF2378	AirFrance
45
Ptáme-li se nyní, setkají se Petr a Josef na palubě stejného letadla? Případně, čí letadlo to bude? Odpovědi nám dá složení relací U o2 T, jak je posáno výše.
pasažér	letadlo
Petr Josef Pavel	CSA ČSA AirFrance
Zkuste se zamyslet, lze tyto dvě relace skládat ještě jinak? Co by pak bylo významem?
□
6.4   Skládání funkcí, permutace
Soustřeďme se nyní na další oblast, kde běžně a přirozeně používáme skládání relací, aniž si to uvědomujeme.
Fakt: Mějme zobrazení (funkce) f: A^tB&g: B^tC. Pak jejich složením coby relací v tomto pořadí vznikne zobrazení {g o /) : A —> C definované
Í9° f)(x) =g(f(x)).
Komentář:
* Jak například na běžné kalkulačce vypočteme hodnotu funkce sin2 x ? Složíme (v tomto pořadí) „elementární" funkce f(x) = sin x a g(x) = x2.
* Jak bychom na „elementární" funkce rozložili aritmetický výraz 21og(x2 + 1)? Ve správném pořadí složíme funkce fi(x) = x2, f2(3;) = x + 1, fs(x) = log x a f^x) = 2x.
* A jak bychom obdobně vyjádřili složením funkcí aritmetický výraz sin x + cos x? Opět je odpověď přímočará, vezmeme „elementární" funkce g\{x) = sin x a §2{x) = cosx, a pak je „složíme" další funkcí h{x, y) = x + y. Vidíme však, že takto pojaté „skládání" už nezapadá hladce do našeho zjednodušeného formalismu skládání relací.
Pro nedostatek prostoru si skládání funkcí s více parametry nedefinujeme, ale sami vidíte, že obdobné skládání se v programátorské praxi vyskytuje doslova „na každém rohu" a ani se nad tím nepozastavujeme.
Skládání permutací
Po zbytek tohoto oddílu se zaměříme na permutace coby speciální případ (bijektivních) zobrazení.
Definice: Nechť permutace 7r množiny {1,2,... ,12} je určena seřazením jejích prvků (pi,... ,pn)- Pak 7T je zároveň bijektivním zobrazením {1,... ,12} —> {1,... ,12} definovaným předpisem tt(í) = pi. Tudíž lze permutace skládat jako relace podle Definice 6.3.
Poznámka: Všechny permutace množiny {1,2,... ,n} spolu s operací skládání tvoří grupu, zvanou symetrická grupa Sn. Permutační grupy (podgrupy symetrické grupy) jsou velice důležité v algebře, neboť každá grupa je vlastně isomorfní některé permutační grupě.
46
Komentář: Příkladem permutace vyskytujícím se v programátorské praxi je třeba zobrazení i i—> (i + 1) mod n ("inkrement"). Často se třeba lze setkat (aniž si to mnohdy uvědomujeme) s permutacemi při indexaci prvků polí.
V kontextu pohledu na funkce a jejich skládání coby relací si zavedeme jiný, názornější, způsob zápisu permutací - pomocí jejich cyklů.
Definice: Nechť 7r je permutace na množině A. Cyklem v 7r rozumíme posloupnost (ai, a2, . . ., Ofc) různých prvků A takovou, že 7r(<2j) = ai+1 pro i = 1,2,..., k — 1 a 7r(afc) = d\.
Jak název napovídá, v zápise cyklu (ai, a2,..., ak) není důležité, kterým prvkem začneme, ale jen dodržení cyklického pořadí. Cyklus v permutaci může mít i jen jeden prvek (zobrazený na sebe).
Komentář: Nakreslete si (vámi zvolenou) permutaci tv obrázkem, ve kterém vedete šipku vždy od prvku i k prvku tt(í). Pak uvidíte, že cykly dle naší definice jsou právě cykly tvořené šipkami ve vašem obrázku. S tímto grafickým zobrazením pro vás nebude problém pochopit následující látku.
Například permutaci (5, 3,4, 8, 6,1, 7, 2) si lze obrázkem nakreslit takto:
Reprezentace permutací jejich cykly
Věta 6.6. Každou permutací tt na konečné množině A lze zapsat jako složení cyklů na disjunktních podmnožinách (rozkladu) A.
Důkaz: Vezmeme libovolný prvek aľ G A a iterujeme zobrazení a2 = ^(^í)? a3 = 7r(a2); atd., až se dostaneme „zpět" k ak+í = ^(a^.) = aľ. Proč tento proces skončí? Protože A je konečná a tudíž ke zopakování některého prvku ak+í musí dojít. Nadto je 7r prostá, a proto nemůže nastat ir(ak) = clj pro j > 1. Takto získáme první cyklus (ai,..., a^).
Induktivně pokračujeme s hledáním dalších cyklů ve zbylé množině A \ {a±,..., a^}, dokud nezůstane prázdná. □
Značení permutace jejími cykly: Nechť se permutace 7r podle Věty 6.6 skládá z cyklů (ai,..., a*;), (bi,... ,bi) až třeba (z1}..., zm). Pak zapíšeme
7T = ((ai,..., ak) (h,..., bi) ... (Z!, ...,zm)).
Komentář: Primitivní pseudonáhodné generátory v počítačích iterují z náhodného počátku permutaci danou vztahem i \—> (i + p) mod q. Je pochopitelné, že tato permutace nesmí obsahovat krátké cykly, lépe řečeno, měla by se skládat z jediného (dlouhého) cyklu. (Pro úplnost, jedná se o permutaci množiny {0,1,... , q — 1}).
Příklad 6.7. Ukázka skládání permutací daných svými cykly.
Vezměme 7-prvkovou permutaci 7r = (3,4, 5, 6, 7,1, 2). Ta se skládá z jediného cyklu (1, 3, 5, 7, 2,4, 6). Jiná permutace o~ = (5, 3,4, 2, 6,1, 7) se rozkládá na tři cykly (1, 5, 6),
47
(2, 3,4} a (7). Nyní určíme složení a on těchto dvou permutací (už přímo v zápisu cykly):
(Nezapomínejme, že první se ve složení aplikuje pravá permutace!)
Postup skládání jsme použili následovný: 1 se zobrazí v permutaci vpravo na 3 a pak vlevo na 4. Následně 4 se zobrazí na 6 a pak na 1. Tím „uzavřeme" první cyklus (1,4). Dále se 2 zobrazí na 4 a pak hned zpět na 2, tj. má samostatný cyklus.   Zbylý cyklus
6.5   Induktivní definice množin a funkcí
Vzpomeňme si na definici posloupnosti rekurentním vztahem z Oddílu 3.4. Přímým zobecněním dřívějších rekurentních definic je následující koncept.
Definice 6.8. Induktivní definice množiny.
Jedná se obecně o popis (nějaké) množiny M v následujícím tvaru:
• Je dáno několik pevných (bazických) prvků a±, cí2, ...,     G M.
• Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) x±,... ,xe G M, pak také y G M. V tomto případě je y typicky funkcí y = fi(xi,..., xe).
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující těmto pravidlům.
Poznámka: Vidíte podobnost této definice s uzávěrem relace? (Věta 5.10.) Komentář:
• Pro nejbližší příklad induktivní definice se obrátíme na množinu všech přirozených čísel, která je formálně zavedena následovně.
- 0 G N
- Je-li i G N, pak také i + 1 G N.
• Pro každé y G N můžeme definovat jinou množinu My C N induktivně takto:
- y G My
- Jestliže x G My a x + 1 je liché, pak x + 2 G My. Pak například M3 = {3}, nebo M4 = {4 + 2i | i G N}.
• Dalším příkladem induktivní definice je už známé zavedení výrokových formulí z Oddílu 1.5. Uměli byste teď přesně říci, co tam byly bázické prvky a jaká byla induktivní pravidla? A jaká byla v definici formulí role přítomných závorek? K tomu se blíže vyjádříme v Definici 6.9.
((1, 5, 6)(2, 3,4}(7}) o ((1, 3, 5, 7, 2,4, 6}) = ((1,4}(2}(3, 6, 5, 7})
(3, 6, 5, 7} určíme analogicky.
□
48
Jednoznačnost induktivních definic
Definice: Řekneme, že daná induktivní definice množiny M je jednoznačná, právě když každý prvek M lze odvodit z bázických prvků pomocí induktivních pravidel právě jedním způsobem.
Komentář: Definujme například množinu M C N induktivně takto:
- 2,3 G M
- Jestliže x, y G M a x < y, pak také x2 + y2 a x ■ y jsou prvky M.
Proč tato induktivní definice není jednoznačná? Například číslo 8 G M lze odvodit způsobem 8 = 2 • (2 • 2), ale zároveň zcela jinak 8 = 22 + 22.
V čem tedy spočívá důležitost jednoznačných induktivních definic množin? Je to především v dalším možném využití induktivní definice množiny jako „základny" pro odvozené vyšší definice, viz následující Definice 6.9 a třeba doplňková Věta 6.12. Stručně a neformálně řečeno, hlavní role jednoznačnosti induktivní definice je v možnosti pak přiřadit prvkům této induktivní množiny nějaký „jednoznačný význam".
Definice 6.9. Induktivní definice funkce z induktivní množiny.
Nechť množina M je dána jednoznačnou induktivní definicí. Pak říkáme, že funkce ÍF :
M —> X je definována induktivně (vzhledem k induktivní definici M), pokud je řečeno:
• Pro každý z bázických prvků ai,a,2,... ,a,k G M je určeno ÍF(ai) = q, kde q je konstanta.
• Pro každé induktivní pravidlo typu
:'Jsou-li (libovolné prvky) x±,... ,xe G M, pak také f(x\,..., x A G M" je definováno
F( f(%i, ■ ■ ■, %e)) na základě hodnot ÍF(xi),..., ÍF{xe).
Komentář: Pro příklad se podívejme třeba do manuálových stránek unixového příkazu test EXPRESSION:
EXPRESSION is true or falše and sets exit status.    It is one of: ! EXPRESSION EXPRESSION is falše
EXPRESSI0N1 -a EXPRESSI0N2 both EXPRESSI0N1 and EXPRESSI0N2 are true EXPRESSI0N1 -o EXPRESSI0N2 either EXPRESSI0N1 or EXPRESSI0N2 is true [-n] STRING the length of STRING is nonzero
STRING1 = STRING2 the strings are equal
Vidíte, jak tato ukázka koresponduje s Definicí 6.9? Induktivní definice se „strukturální" indukcí
Závěrem ještě doplňkově zařazujeme malou ukázku, kterak přirozeně zkombinovat induktivní definice s „pokročilou formou matematické indukce" v dokazování, s tzv. strukturální indukcí.
Příklad 6.10. Jednoduché aritmetické výrazy a jejich význam.
Nechť je dána abeceda E = {0,1, 2, 3,4, 5, 6, 7, 8, 9, 0, ©, (,)}. Definujme množinu jednoduchých výrazů SExp C S* induktivně takto:
49
- Dekadický zápis každého přirozeného čísla n je prvek SExp.
- Jestliže x, y E SExp, pak také (x) 0 (y) a (x) © (y) jsou prvky SExp. (Jak vidíme, díky nucenému závorkování je tato induktivní definice jednoznačná.)
Tímto jsme aritmetickým výrazům přiřadili jejich „formu", tedy syntaxi.
Pro přiřazení „významu", tj. sémantiky aritmetického výrazu, následně definujme funkci Val: SExp —> N induktivně takto:
- Bázické prvky: Val(n) = n, kde n je dekadický zápis přirozeného čísla n.
- První induktivní pravidlo: Val((x) © (y)) = Val(x) + Val(y).
- Druhé induktivní pravidlo: Val((x) 0 (y)) = Val(x) ■ Val(y).
Co je tedy správným významem uvedených aritmetických výrazů? (Příklad 6.11) □
Příklad 6.11. Důkaz správnosti přiřazeného „významu" Val: SExp —> N.
Věta. Pro každý výraz s G SExp je hodnota Val(s) z Příkladu 6.10 číselně rovna výsledku vyhodnocení výrazu s podle běžných zvyklostí aritmetiky.
Jelikož pojednáváme o induktivně definované funkci Val, je přirozené pro důkaz jejích vlastností aplikovat matematickou indukci. Na rozdíl od dříve probíraných příkladů zde nevidíme žádný celočíselný „parametr n", a proto si jej budeme muset nejprve definovat. Naši indukci tedy povedeme podle „délky l odvození výrazu s" definované jako počet aplikací induktivních pravidel potřebných k odvození s G SExp.
Důkaz: V bázi indukce ověříme vyhodnocení bázických prvků, kteréžto jsou zde dekadické zápisy přirozených čísel. Platí Val(n) = n, což skutečně odpovídá zvyklostem aritmetiky.
V indukčním kroku se podíváme na vyhodnocení Val((x) © (y)) = Val(x) + Val(y). Podle běžných zvyklostí aritmetiky by hodnota Val((x) © (y)) měla být rovna součtu vyhodnocení výrazu x, což je podle indukčního předpokladu rovno Val(x) (x má zřejmě kratší délku odvození), a vyhodnocení výrazu y, což je podle indukčního předpokladu rovno Val(y). Takže skutečně Val((x) © (y)) = Val(x) + Val(y).
Druhé pravidlo Val((x) 0 (y)) se dořeší analogicky. □
Dodatek: důkaz pro normální tvar formule
V Oddíle 1.5 jsme stručně zavedli výrokovou matematickou logiku a výrokové formule. Nyní si snadno můžeme všimnout, že jak definice syntaxe, tak i definice sémantiky výrokové logiky jsou induktivní ve smyslu (po řadě) Definic 6.8 a 6.9. Také Metoda 1.16 pro převod formule do normálního tvaru je induktivní, a proto je na místě následující ilustrativní ukázka důkazu strukturální indukcí:
Věta 6.12. Pro libovolnou výrokovou formuli ip platí (viz Metoda 1.16), že
a) ÍF((p) je ekvivalentní formule k ip v normálním tvaru
b) a Q(íp) je formule v normálním tvaru ekvivalentní negaci ~np.
Důkaz povedeme indukcí ke struktuře formule, neboli indukci povedeme podle „délky" l - počtu aplikací induktivních pravidel při sestavování formule ip. • Báze indukce (l = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že J-'(A) = A je ekvivalentní A a Q(A) = -<A je ekvivalentní -<A.
50
• V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule ip délky nejvýše l. Vezmeme si formuli ip délky £+1, která je utvořená jedním z následujících způsobů:
* ifj = -np (= je „definiční rovnítko" pro formule). Podle výše uvedeného induktivního předpisu je J7^) = J7(-></?) = G (f)- Podle indukčního předpokladu pak je G(íp) formule v normálním tvaru ekvivalentní ~np = ip. Obdobně pro funktor Q vyjádříme G(ip) = G(~"f) = F(ip). Podle indukčního předpokladu pak je .F(</?) formule v normálním tvaru ekvivalentní 99 a to je dále ekvivalentní -1-199 = —iip podle Tvrzení 1.13.
* ifj = (tpi =>- tp2). Podle výše uvedeného induktivního předpisuje J7^) = =>• if2) = Fifi) =>• Jr(if2)- Podle indukčního předpokladu jsou Ffyi) i ^{^2) formule v normálním tvaru ekvivalentní ipi a p>2- Potom i Ffyi) =>• T'(^2) je v normálním tvaru dle definice a podle sémantiky =>- je ta ekvivalentní formuli
{<Pi     P2) =
Obdobně rozepíšeme G(ip) = G(<Pi =>• ^2) = Fityi) A G(^2)- Jelikož a je pro nás jen zkratka, výraz dále rozepíšeme G{ip) = _,(^r(v;,i) =^ ~^G{lf2))- Podle indukčního předpokladu (a dvojí negace) jsou Ffyi) a -<G(f2) P° řadě ekvivalentní formulím <pi a <p2- Tudíž nakonec odvodíme, že G{ip) je ekvivalentní negaci formule ipi =>- ip2, což jsme zde měli dokázat.
* ifj = (<pi v</?2)- Zde si musíme opět uvědomit, že spojka v je pro nás jen zkratka, a přepsat ip = (-1^1 =>• ^2)■ Potom podle předchozích dokázaných případů víme, že Fijp) = .T7(-i</?i =>• 1P2) = ^(-npi) =>• ^(^2) je ekvivalentní formuli (-><pi =>• ^2) = ífj, což bylo třeba dokázat. Stejně tak G{ip) = G(~"fi =>• f 2) = Jr(~'íPi) A G(^2) je podle předchozích případů důkazu ekvivalentní (—upi a -1^2) =
* ifj = (<pi a if2) a ip = (ifi     if2) už dokončíme analogicky.
Rozšiřující studium
S formalizací pojmu funkce a jejími vlastnostmi se setkáváte především v matematice, avšak například na bijektivní funkce narazíte při ukládání dat při volbě klíče apod. Pro informatiku jsou spíše důležitější relace a jejich skládání, na nichž je založena mimo jiné práce s relačními databázemi. Poslední částí lekce je problematika induktivních defínic, které ač ve formálním podání mohou nejprve vypadat nepochopitelně, jsou ve skutečnosti zcela přirozenou popisnou metodou v mnoha aplikačních sférách informatiky a jejich alespoň intuitivní chápání pro vás bude v dalším studiu nezbytné. Schválně, zkuste se podívat zrovna do vaší oblíbené oblasti informatiky, kde všude induktivní definice, tj. ty odvolávající se rekurzivně samy na sebe pro „menšípřípady", najdete (třeba nepřímo).
51
7   Pojem grafu, ve zkratce
Úvod
Třebaže grafy jsou jen jednou z mnoha struktur v matematice a vlastně pouze speciálním případem binárních relací, vydobyly si svou užitečností a názorností důležité místo na slunci. Dá se bez nadsázky říci, že teorie grafů je asi nejvýznamnější součástí soudobé diskrétní matematiky, a proto se jí budeme věnovat po tři následující lekce. Avšak pozor, nepleťme si graf s grafem funkce!
Neformálně řečeno, graf se skládá z vrcholů (představme si je jako nakreslené „puntíky") a z hran, které spojují dvojice vrcholů mezi sebou. Své důležité místo v informatice si grafy získaly dobře vyváženou kombinací svých vlastností - snadno pochopitelným názorným nakreslením a zároveň jednoduchým zpracováním na počítačích. Díky těmto vlastnostem se grafy prosadily jako vhodný matematický model pro popis různých vztahů mezi daty a objekty.
Cíle
Deňnujeme, co je graf a jaké jsou nejzákladnější grafové pojmy (třeba hrany a stupně, podgrafy, souvislost). Klademe důraz na to, aby se čtenář naučil grafy „uchopit" a pracovat s nima, také aby správně viděl „stejnost" (isomorňsmus) grafů. Poté se věnujeme nej jednoduššímu druhu grafů, totiž stromům. Jedná se vesměs o pojmy, které se hojně vyskytují v obvyklých informatických aplikacích grafů.
7.1   Definice grafu
Hned na úvod přistoupíme k formální definici grafu. Bude se jednat o definici tzv. jednoduchého neorientovaného grafu, který budeme považovat za základní, pokud neřekneme jinak. Svým způsobem navazujeme na reprezentace relací v Oddíle 4.2.
Definice 7.1. Graf je uspořádaná dvojice G = (V, E),
kde V je množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů; tj. E C .
Značení: Hranu mezi vrcholy uati píšeme jako {u, v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední a hrana uv vychází z vrcholů u a v. Na množinu vrcholů známého grafu G odkazujeme jako na V(G), na množinu hran E(G).
Komentář: Grafy se často zadávají přímo názorným obrázkem, jinak je lze formálně zadat výčtem vrcholů a výčtem hran. Například:
1 _
2 3 4
f = {1,2,3,4},    E = {{1,2}, {1,3}, {1,4}, {3,4}}
Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace.
52
Stupně vrcholů v grafu
Máme-li graf, často nás zajímá, kolik z kterého vrcholu vychází hran-spojnic, neboli kolik má vrchol „sousedů". Proto jedním z prvních definovaným pojmů bude stupeň vrcholu v grafu.
Definice 7.2. Stupněm vrcholu v v grafu G
rozumíme počet hran vycházejících z v. Stupeň v v grafu G značíme de (v).
Komentář: Slovo „vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí u neorientovaných grafů říkat, že hrana vychází z obou svých konců zároveň.
stupně
Například v nakreslené ukázce jsou stupně přímo zapsány u vrcholů.
Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň d.
Značení: Nejvyššístupeň v grafu G značíme A(G) a nejnižší b~(G).
Věta 7.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran.
Důkaz. Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát - jednou za každý její konec. Proto výsledek vyjde sudý. □
Příklad 7.4. Zodpovězte si sami následující otázky:
* Kolik hran má graf se 17 vrcholy stupňů 4?
* Existují dva „různé" grafy se 6 vrcholy stupňů 2? □
Běžné typy grafů
Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Jde čistě o věc konvence a autoři se mohou v některých názvech lišit (i přicházet s novými názvy), avšak následujících pět názvů patří k všeobecným základům teorie grafů.
Kružnice délky n má n > 3 vrcholů spojených do jednoho cyklu n hranami:
3
Cr
Cesta délky n > 0 má n + 1 vrcholů spojených za sebou n hranami:
n   n + 1
53
Úplný graf na n > 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem q) hran):
K
n
Úplný bipartitní graf na m > lan > 1 vrcholech má m+n vrcholů ve dvou skupinách (partitách), přičemž hranami jsou pospojované všechny m-n dvojice z různých skupin:
12    3 4
m
1    2    3 • • • n
Hvězda s n > 1 rameny je zvláštní název pro úplný bipartitní graf K\^n:
3
'n
Příklad 7.5. Zodpovězte si sami následující otázky:
* Pro jakou hodnotu n je úplný graf Kn zároveň cestou?
* Pro jakou hodnotu n je úplný graf Kn zároveň kružnicí?
* Pro jaké hodnoty m,n > 0 je úplný bipartitní graf Km,n zároveň kružnicí?
* Kolik hran musíte přidat do kružnice délky 6, aby vznikl úplný graf na 6 vrcholech?
* Pro jaké hodnoty m, n > 0 úplný bipartitní graf Kmn neobsahuje žádnou kružnici? □
Zmínka o orientovaných grafech
V Lekci 9 si zavedeme také takzvané orientované grafy, které každé hraně přiřazují jistý směr. Formálně orientované grafy budou mít množinu orientovaných hran A C V (G) x
V (G) a zobrazíme je takto...
54
7.2   Podgrafy a Isomorfismus
Dva základní nástroje pro práci s grafy jsou následující; možnost popisovat „část grafu" (podobně jako podmnožinu množiny, avšak je nutno se vyvarovat nekorektních situací) a poznávat „stejnost" dvou grafů.
Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholů V(H) C V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V(H).
Píšeme H C G, tj. stejně jako množinová inkluze (ale význam je trochu jiný).
Komentář: Na následujícím obrázku vidíme zvýrazněné podmnožiny vrcholů hran. Proč se vlevo nejedná o podgraf? Obrázek vpravo už podgrafem je.
Definice: Indukovaným podgrafem je podgraf H C G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H).
„Stejnost" grafů
Pozorný čtenář si možná již při čtení předchozího oddílu položil otázku: Co když vezmeme jeden graf (třeba kružnici délky 4) a nakreslíme nebo zapíšeme jej jednou tak, podruhé zase jinak - je to stále tentýž graf nebo ne? Viz obrázky dole.
Přísně formálně řečeno, každé další nakreslení jistého grafu, třeba té kružnice C4, je jiným grafem, ale přitom bychom rádi řekli, že různá nakreslení téhož grafu jsou „stále stejná". Pro tuto stejnost grafů se vžil pojem isomorfní grafy.
Definice 7.6. Isomorfismus ~ grafů G a, H
je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —> V(H), pro které platí, že každá dvojice vrcholů u,v G V(G) je spojená hranou v G právě tehdy, když je dvojice f(u),f(v) spojená hranou v H.
Grafy G a H jsou isomorfní, pokud mezi nimi existuje isomorfismus. Píšeme G ~ H.
Fakt: Mějme isomorfismus / grafů G a H. Pak platí následující
* G a H mají stejný počet hran,
* / zobrazuje na sebe vrcholy stejných stupňů, tj. de (v) = dnifív)).
55
Komentář:
U nakreslených dvou grafů objevíme isomorfismus velmi snadno - podíváme se, jak si odpovídají vrcholy stejných stupňů.
Příklad 7.7. Jsou následující dva grafy isomorfní?
Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého.
Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické, proto si bez újmy na obecnosti můžeme vybrat, že nejlevější vrchol prvního grafu, označme jej 1, se zobrazí na nejlevější vrchol ľ v druhém grafu (taky stupně tři). Očíslujme zbylé vrcholy prvního grafu 2,... ,6 v kladném smyslu, jak je ukázáno na následujícím obrázku. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu (pravý spodní). Pak je již jasně vidět, že další sousedé 2, 6 vrcholu 1 se zobrazí na analogické sousedy 2', 6' vrcholu ľ v druhém grafu, a stejně je to i se zbylými vrcholy 3, 5. Výsledný isomorfismus vypadá v odpovídajícím značení vrcholů takto:
Abychom mohli s isomorfismem grafů přirozeně pracovat, je potřeba vědět následující fakt:
Věta 7.8. Relace „být isomorfní" ~ na třídě všech grafů je ekvivalencí.
Důkaz. Relace ~ je reflexivní, protože graf je isomorfní sám sobě identickým zobrazením. Relace je také symetrická, neboť bijektivní zobrazení lze jednoznačně obrátit. Tranzitivnost ~ se snadno dokáže skládáním zobrazení-isomorfismů. □
Důsledkem je, že všechny možné grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud mluvíme o grafu, myslíme tím obvykle jeho celou třídu isomorfismu, tj. nezáleží nám na konkrétní prezentaci grafu.
Komentář: Je uvedený přístup, tj. zaměňování konkrétního grafu za celou jeho třídu isomorfismu, v matematice neobvyklý? Ne, například už v geometrii jste říkali „čtverec o straně 2" či „jednotkový kruh" a podobně, aniž jste měli na mysli konkrétní obrázek, nýbrž celou třídu všech těchto shodných objektů.
56
Další grafové pojmy
Definice: Mějme libovolný graf G.
* Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice v G.
* Speciálně říkáme trojúhelník kružnici délky 3.
* Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta v G.
* Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika v G. (Někdy se za kliku považuje pouze takový úplný podgraf, který je maximální vzhledem k uspořádání inkluzí.)
* Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G.
* Indukovanému podgrafu H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G.
Komentář: Uvažujme následující ukázky grafů:
2\-/3 2\-/3
První z ukázaných grafů například neobsahuje žádný trojúhelník, ale obsahuje kružnici délky 4, dokonce indukovanou. Druhý graf trojúhelník obsahuje a kružnici délky 4 taktéž. První graf obsahuje cestu délky 4 na vrcholech 1, 2, 3,4, 5, ale ta není indukovaná. Indukovaná cesta délky 4 v něm je třeba 2,3,4,5,6. Druhý graf tyto cesty také obsahuje, ale naopak žádná z nich není indukovaná. První graf má největší kliku velikosti 2 - jedinou hranu, kdežto druhý graf má větší kliku na vrcholech 3,4, 5. Největší nezávislá množina u obou grafů má 3 vrcholy 2,4, 6.
Příklad 7.9. Jsou následující dva grafy isomorfní?
Postupovat budeme jako v Příkladě 7.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude vycházet, že? Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. □
Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit) isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde tedy najde nějaký univerzální postup pro nalezení isomorfismu? Bohužel vás musíme zklamat, žádný rozumný univerzální postup není znám a zatím platí, že jediná vždy fungující cesta pro
57
nalezení či nenalezení isomorfismu mezi dvěma grafy je ve stylu vyzkoušejte všechny možnosti bijekcí mezi vrcholy těchto grafů. (Těch je, jak známo, až n\)
7.3   Souvislost grafů, komponenty
Důležitou globální vlastností grafů je souvislost, tedy možnost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Tuto vlastnost si nyní upřesníme.
Lema 7.10. Mějme relací ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy x ~ y právě když existuje v G cesta začínající v x a končící v y. Pak ~ je relací ekvivalence.
Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou cestou délky 0. Symetrická je také, protože cestu z x do y snadno v neorientovaném grafu obrátíme na cestu z y do x. Pro důkaz tranzitivity si označme P cestu z x do y a Q cestu z y do z. Pak P U Q nemusí být cesta; mohou se navzájem protínat. Avšak pokud označíme P' C P část cesty z x do prvního vrcholu v průniku s Q, tak P1 U Q už je cesta z x do z. □
Dennice 7.11. Komponentami souvislosti  grafu G nazveme
třídy ekvivalence výše popsané (Lema 7.10) relace ~ na V(G). Jinak se také komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence.
Komentář: Podívejte se, kolik komponent souvislosti má tento graf:
Vidíte v obrázku všechny tři komponenty? Jedna z nich je izolovaným vrcholem, druhá hranou (tj. grafem isomorfním K2) a třetí je to zbývající.
Definice 7.12. Graf G je souvislý
pokud je G tvořený nejvýše jednou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou.
Poznámka: Prázdný graf je souvislý a má 0 komponent. Komentář: Který z těchto dvou grafů je souvislý?
7.4   Stromy — grafy bez kružnic
Podrobnější studium některých užitečných aspektů grafů začneme u toho nej jednoduššího typu grafu - na stromech, jež jsou mimo jiné základem mnoha datových typů používaných v informatice.
58
Komentář:
Charakteristickými znaky stromů je absence kružnic a souvislost...
Definice 7.13. Strom je jednoduchý souvislý graf T bez kružnic.
Komentář: Obecněji les je jednoduchý graf bez kružnic (nemusí být souvislý). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a prázdný graf jsou také stromy. Grafy bez kružnic také obecně nazýváme acyklické.
Vlastnosti stromů
Přehled základních vlastností stromů je pro nás zároveň příležitostí si ukázat několik nových hezkých matematických důkazů a naučit se správně zdůvodňovat v oblasti grafů.
Lema 7.14. Strom s více než jedním vrcholem obsahuje vrchol stupně 1.
Důkaz: Souvislý graf s více než jedním vrcholem nemůže mít vrchol stupně 0. Proto vezmeme strom Tav něm libovolný vrchol v. Sestrojíme nyní co nejdelší cestu S v T začínající ve v: S začne libovolnou hranou vycházející z v; v každém dalším vrcholu u, do kterého se dostaneme a má stupeň větší než 1, lze pak pokračovat cestu S další novou hranou.
Pokud by se v S poprvé zopakoval některý vrchol, získali bychom kružnici, což ve stromě nelze. Proto cesta S musí jednou skončit v nějakém vrcholu stupně 1 v T. □
Komentář: Zamyslete se, proč v každém stromě s více než jedním vrcholem jsou alespoň dva vrcholy stupně 1 (odpověď je skrytá už v předchozím důkaze). Zároveň si odpovězte, jestli lze tvrdit, že každý strom s více než jedním vrcholem obsahuje tři vrcholy stupně 1.
Věta 7.15. Strom na n vrcholech má přesně n — 1 hran pro n > 1.
Důkaz: Toto tvrzení dokážeme indukcí podle n. Strom s jedním vrcholem má n — 1 = 0 hran. Nechť T je strom na n > 1 vrcholech. Podle Lematu 7.14 má T vrchol v stupně 1. Označme T' = T — v graf vzniklý z T odebráním vrcholu v. Pak T" je také souvislý bez kružnic, tudíž strom na n — 1 vrcholech. Dle indukčního předpokladu T" má n — 1 — 1 hran, a proto T má n — 1 — 1 + 1 = n — 1 hran. □
Věta 7.16. Mezí každými dvěma vrcholy stromu vede právě jediná cesta.
59
Důkaz:
Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u,v vede nějaká cesta. Pokud by existovaly dvě různé cesty P\,P2 mezi u,v, tak bychom vzali jejich symetrický rozdíl, podgraf H = PľAP2 s neprázdnou množinou hran, kde H zřejmě má všechny stupně sudé. Na druhou stranu se však podgraf stromu musí opět skládat z komponent stromů, a tudíž obsahovat vrchol stupně 1 podle Lematu 7.14, spor. Proto cesta mezi u a v existuje jen jedna. □
Důsledek 7.17. Přidáním jedné nové hrany do stromu vznikne právě jedna kružnice.
Důkaz: Nechť mezi vrcholy u,v ve stromu T není hrana. Přidáním hrany e = uv vznikne právě jedna kružnice z e a jediné cesty mezi u,v v T podle Věty 7.16. □
Alternativní charakterizace stromů
Z předchozích tvrzení vyplývá následující alternativní charakterizace stromů, která ukazuje důležitost jich samotných i jako tzv. koster obecných grafů (viz Oddíl 8.4).
Na dané množině vrcholů je (vzhledem k inkluzi množin hran) strom
• minimální souvislý graf (plyne z Věty 7.16)
• a zároveň maximální acyklický graf (plyne z Důsledku 7.17).
Jen tak mimochodem, kolik dokážete nalézt neisomorfních stromů na 4 nebo 5 vrcholech? Vidíte, že jich není mnoho? Nakreslete si je všechny.
7.5   Použití a implementace grafů
Závěrem si v našem studijním textu nastíníme některé základní motivace pro zavedení a použití grafů při popisu a řešení problémů například v informatice.
Příklad 7.18. Ukázky některých problémů „ze života" popsatelných grafy. Podotýkáme, že tyto ukázky jsou často velmi zjednodušené (pro jejich lepší přístupnost širokému okruhu čtenářů), ale to neubírá jejich motivačnímu potenciálu.
• Vyjádření mezilidských vztahů - „mají se rádi", „kamarádí se", „nesnesou jeden druhého", apod:
Zde jednotlivé osoby tvoří vrcholy grafu a vztahy jsou hranami (často neorientované, ale i orientace je přípustná). Všimněme si coby zajímavosti, jak tento model přirozeně preferuje „párový" pohled na vztahy - hrany přece spojují jen dvojice vrcholů. Třebaže například vztah „kamarádí se" může být obecně platný pro větší skupinky lidí než dvojice, stejně se obvykle vyjadřuje klikou v grafu (každí dva v našem družstvu jsou dobří kamarádi...). Tato obecně pojímaná tendence vyjadřovat i složitější vztahy těmi párovými je vodou na mlýn použití teorie grafů jako téměř univerzálního vyjadřovacího prostředku v podobných případech.
60
Na druhou stranu i teorie grafů disponuje pojmem tzv. hypergrafu umožňujícího použití hran libovolné arity (počtu koncových vrcholů), ale rozsah výskytu hypergrafu v teorii i aplikacích je oproti grafům vskutku zanedbatelný.
• Vyjádření závislostí mezi objekty nebo procesy:
Představme si situace, ve kterých jednotlivé entity (modelované jako vrcholy) závisí na výstupech jiných entit a naopak poskytují výstupy další entitám. Typickým příkladem mohou být závislosti jednotlivých kroků výrobního nebo rozhodovacího procesu. Ty pak vedou k definici orientovaného grafu na dané množině vrcholů/entit, tj. použití hran „se šipkami". Všimněme si, že závislosti často bývají časového charakteru (přičemž směr závislosti je implicitně jasný) a pak je nezbytnou doplňkovou podmínkou vyloučení výskytu orientovaných cyklů v modelovém grafu. Na druhou stranu existují i situace, kdy cyklické závislosti jsou dovoleny a mají svůj význam.
Pro ještě jednu ukázku závislostí z běžného života informatika se podíváme na správu balíčků softwaru například v Linuxovýxh distribucích. V tom případě jsou jednotlivé balíčky vrcholy grafu, jejich vyžadované závislosti popisují odchozí hrany a jejich poskytované vlastnosti jsou příchozími hranami grafu závislostí. Korektní instalace zvoleného balíčku pak řeší problém zahrnutí všech dalších vrcholů „dosažitelných" ze zvoleného. Vše je navíc komplikováno správou verzí balíčků, ale to už je mimo rámec našeho úvodního slova.
• Modelování technických či dopravních sítí grafy:
V takových případech bývají vrcholy grafu jednotlivá technická zařízení jako třeba rozvodny, routery, křižovatky a podobně, kdežto hrany jsou tvořeny spojnicemi/vedením mezi vrcholy. Často se zde setkáváme s orientovanými grafy a obecně multigrafy. K této probematice se blíže vyjadřuje Lekce 9.
• Vizualizace vztahů a závislostí pro lidského pozorovatele:
Nejen při řešení cvičných příkladů v naší učebnici, ale i v mnoha reálných aplikacích využívajících grafy jako modely, je velmi potřebné tyto grafy vizualizovat (tj. hezky nakreslit) pro lidského pozorovatele. Jedná se obecně o poměrně obtížný úkol, který přesahuje hranice našeho textu. □
Zpracování grafu počítačem
Mějme jednoduchý graf G na n vrcholech a značme vrcholy jednoduše čísly v(g) = {0,1,... ,n — 1}. Pro počítačovou implementaci grafu g se nabízejí dva základní způsoby které budeme implicitně využívat i v některých algoritmech následujících lekcí.
• Implementace maticí sousednosti, tj. dvourozměrným polem g[][], ve kterém g [i] [j]=l znamená hranu mezi vrcholy i a j.
• Implementace výčtem sousedů, tj. použitím opět dvourozměrné pole h[] [] a navíc pole d[] stupňů vrcholů. Zde prvky h [i] [0] ,h[i] [1] , . . . ,h[i] [d[i]-l] udávají seznam sousedů vrcholu i.
Poznámka: Dávejte si pozor na symetrii hran v implementaci! To znamená, že pokud uložíte hranu g [i] [j]=l, tak musíte zároveň uložit i hranu g[j] [i]=l, jinak se dočkáte nepříjemných překvapení. Totéž se týká i seznamů sousedů.
61
Komentář: Implementace maticí sousednosti je hezká svou jednoduchostí. Druhá možnost se však mnohem lépe hodí pro grafy s malým počtem hran, což nastává ve většině praktických aplikací. (Navíc je implementace výčtem sousedů vhodná i pro multigrafy.) Ke grafům lze do zvláštních polí přidat také ohodnocení vrcholů a hran libovolnými čísly či značkami...
Rozšiřující studium
Grafy můžeme v informatice potkat doslova na každém kroku, mimo jiné hojně už v základních kurzech algoritmizace. Nejen že grafy (především stromy) jsou základem mnoha programátorských datových struktur, ale představují i vhodný model pro spoustu praktických problémů. Oněch pár lekcí teorie grafů v našem učebním textu je jen lehkým úvodem, přečemž na FI MU lze pokračovat v jejím studiu v předmětu MA010.
Rozsáhlý matematický úvod do teorie grafů je zahrnut ve skvělé knize Kapitoly z diskrétní matematiky autorů Jiřího Matouška a Jaroslava Nešetřila. Vřele ji doporučujeme jako doplňkový studijní zdroj všem, kteří chtějí lépe pochopit grafy z jejich matematické stránky.
62
8   Procházení grafu a odvozené úlohy
Úvod
Na rozdíl od předchozí lekce, která se zjednodušeně řečeno zabývala grafy z pohledu matematika, tedy podáním dennice a obrázků, nyní se hlouběji podíváme na grafy z algoritmické či programátorské perspektivy. Proto se v prvé řadě podíváme na obecné schéma procházení grafu, které je základem mnoha užitečných algoritmů na grafech. Poté se hlouběji zaměříme na dvě speciňcké grafové úlohy - hledání nejkratší cesty a minimální kostry, hojně se vyskytující v mnoha praktických obměnách. Na základě obecného schématu si uvedeme jejich jednoduché a velmi efektivní algoritmy.
Cíle
Zjednodušeně podáme obecné schéma algoritmu procházení grafu. Deňnujeme poté dvě konkrétní grafové úlohy, hledání nejkratší cesty mezi dvěma vrcholy a hledání nejmenší kostry, obojí v grafu s hranami ohodnocenými reálnými délkami. Na základě předchozího pak vysvětlíme Dijkstrův algoritmus pro nejkratší cesty a Kruskalův a Jarníkův algoritmus pro minimální kostru.
8.1   Jak obecně projít souvislý graf
S úlohou procházení grafu se svým způsobem setkávají už děti, když hledají cestu z bludiště (jejich naivní postup se dá přirovnat k procházení „do hloubky"). Celý problém má ale mnohem širší záběr a s vhodnou implementací dodatečných lokálních funkcí lze pouhým prohledáním grafu podat odpověď na jiné zajímavé otázky, jako najít nejkratší cestu, minimální kostru, komponenty vyšší souvislosti, apod. Navíc se procházení grafu vyskytuje jako podúloha v jiných algoritmech.
Metoda 8.1. Schéma algoritmu pro procházení grafem
Pro vytvoření co nejobecnějšího schématu si pomůžeme následujícími datovými stavy a pomocnou strukturou:
• Vrchol grafu: má stavy ...
* iniciační - dostane na začátku,
* nalezený - implicitní stav poté, co jsme jej přes některou hranu nalezli (a odložili ke zpracování později),
* zpracovaný - poté, co jsme už probrali všechny hrany z něj vycházející,
* (případně ještě stav „post-zpracovaný", po dokončení všech jeho následníků).
• Úschovna: je pomocná datová struktura (množina s dodatečnými atributy),
* udržuje odložené, tj. nalezené a ještě nezpracované vrcholy, spolu s dodatečnou specifickou informací.
• Způsob, kterým se vybírají vrcholy z úschovny ke zpracování, určuje variantu algoritmu procházení grafu.
• V prohledávaných vrcholech a hranách se volitelně provádějí dodatečné programové akce pro prohledání a zpracování našeho grafu.
63
Samotný algoritmus pak popíšeme v následujících obecných bodech. (V této souvislosti dodáváme, že podrobněji se budeme způsobu formálního matematického zápisu algoritmů věnovat v Lekci 10, ale zde si vystačíme s běžným jazykem.)
Algoritmus 8.2. Generické procházení souvislé komponenty G grafu
• Vstup:   Souvislý graf G, daný seznamem vrcholů a seznamy vycházejících hran z každého vrcholu, plus případné ohodnocení vrcholů a hran.
• Vybereme libovolný počátek prohledávání u G V (G); úschovna U <r- {u}.
• Dokud U ý 0? opakujeme:
* Zvolíme libovolně v G U; odebereme U <r- U \ {v}. (!)
* Pokud stav(v) = zpracovaný, jdeme zpět na start cyklu. (*)
* Případně provedeme libovolnou akci ZPRACUJ(y).
* Pro všechny hrany / G E (G) vycházející z v provedeme:
- Nechť w je druhý konec hrany / = vw:
- pokud stav(w) ^ zpracovaný, odložíme U <r- U U {w}. (**)
* stav(v)     zpracovaný; na start cyklu.
• Souvislý G je celý prohledaný a zpracovaný.
• Výstup: Případné výsledky spočítané během prohledávání.
Pozor, všimněte se, že v bodě (**) obecně dochází k násobnému ukládání odložených vrcholů, což v praktické implementaci často obejdeme pouhou změnou „odloženého stavu". Doplňkový bod (*) je nutný jen v případě, že násobně uložené kopie stejného vrcholu v zůstávají v úschovně.
Některé implementace procházení grafu
V Algoritmu 8.2 si dobře všimněte, jak je vlastně proveden krok (!); „zvolíme libovolně v G U" ? Právě tato volba je klíčová pro výslednou podobu projití grafu G:
• Procházení „do šířky", BFS - úschovna U je implementovaná jako fronta, neboli je voleno v E U od prvních vrcholů vložených do úschovny.
• Procházení „do hloubky", DFS- úschovna U je implementovaná jako zásobník, neboli je voleno v G U od později vložených do úschovny. (Zde je extrémně důležité, že opakované vložení vrcholu v do U jej posune na vršek zásobníku.)
Dále zmíníme i tyto dva konkrétní, staré a dobře známé algoritmy přímo založené na prohledávání grafu:
• Díjkstrův algoritmus pro nejkratší cestu - z úschovny vybíráme vždy vrchol nejbližší (dosud určenou celkovou vzáleností) k počátečnímu u.
• Jarníkův algoritmus pro minimální kostru - z úschovny vybíráme vždy vrchol nejbližší (délkou hrany) ke kterémukoliv již zpracovanému vrcholu.
Poznámka: Jarníkův algoritmus se ve světové literatuře se obvykle připisuje Američanu Primoví, který jej však objevil a publikoval až skoro 30 let po Jarníkovi. A co více, původ problému minimální kostry je úzce svázán s Brnem, jak si řekneme za chvíli.
64
Konkrétní ukázky BFS a DFS
Příklad 8.3. Ukázka průchodu následujícím grafem do šířky z vrcholu a.
9
h 4-
---r
a V-----V 6
Značení v prohledávaném grafu: barevně aktuálně zpracovávaný vrchol a jeho hrany objevující nové vrcholy, kroužkem a plnou čarou již zpracované vrcholy a hrany, tlustě výsledný strom prohledávání.
0 J > d
/i
c /i
c /i
	9 í		0 í	
—    S\~—-0 c		t--C	/i 0	
□
65
□
8.2   Vzdálenost v grafu
Mimo prohledávání celého souvislého grafu, čímž se zabýval předchozí oddíl, je častou úlohou se dostat z místa na místo nejkratší cestou. Ve zjednodušeném podání považujeme každou hranu grafu za jednotkově dlouhou a definujeme následující.
Definice 8.5. Vzdálenost dc(u, v) dvou vrcholů u, v v grafu G
je dána délkou nejkratší cesty mezi u a v v G. Pokud cesta mezi u,v neexistuje, je vzdálenost definována dc(u,v) = oo.
Komentář: Neformálně řečeno, vzdálenost mezi u,v je rovna nejmenšímu počtu hran, které musíme překonat, pokud se chceme dostat z u do v. Speciálně dc(u,u) = 0.
Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc(u,v) = dc(v,u).
Lema 8.6. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost:
Vu,v,wEV(G) :   dG(u,v) + dG(v,w) > dG(u,w) .
Důkaz. Postupujeme podobně jako v důkaze Lematu 7.10 - pokud máme cesty P,P' mezi u,v a mezi v,w, tak existuje cesta Q C P U P' mezi u,w, jež má zřejmě délku nejvýše dG(u,v) + dc(v,w). Skutečná vzdálenost mezi u,w pak už může být jen menší.
□
BFS a zjištění vzdálenosti
Jak nejsnadněji určíme vzdálenost v grafu? Stačí si povšimnout hezkých vlastností procházení grafu do šířky.
Věta 8.7. Algoritmus procházení grafu do šířky lze použít pro výpočet grafové vzdálenosti z daného vrcholu u.
Toto je poměrně jednoduchá aplikace, kdy počátečnímu vrcholu u přiřadíme vzdálenost 0, a pak vždy každému dalšímu nalezenému vrcholu v přiřadíme vzdálenost o 1 větší než byla vzdálenost vrcholu, ze kterého byl nalezen. Důkaz se opírá o následující tvrzení:
66
* Nechť u,v,w jsou vrcholy souvislého grafu G takové, že dG(u,v) < dG(u,w). Pak při algoritmu procházení grafu G do šířky z vrcholu u je vrchol v nalezen dříve než vrchol w.
V důkaze postupujeme indukcí podle vzdálenosti dG(u,v): Pro dG(u,v) = 0, tj. u = v je tvrzení jasné - vrchol u jako počátek prohledávání byl nalezen první. Proto nechť dG(u,v) = d > 0 a označme v' souseda vrcholu v bližšího k u, tedy de (u, v') = d — 1. Obdobně uvažme libovolného souseda w' vrcholu w. Pak
dG(u, w') > dG(u, w) - 1 > dG(u, v) - 1 = dG(u, v'),
a tudíž vrchol v' byl nalezen v prohledávání do šířky dříve než vrchol w' podle indukčního předpokladu. To znamená, že v' se dostal do fronty úschovny dříve než w'. Proto sousedé v' (mezi nimiž je v, ale ne w neboť v'w není hranou) jsou při pokračujícím prohledávání také nalezeni dříve, než w coby soused w'. □
8.3   Hledání nejkratší cesty
V dalším textu se již budeme věnovat grafům s „obecně dlouhými" hranami. Zároveň předesíláme, že přednášená látka stejně dobře může stavět na orientovaných grafech.
Definice: Vážený graf je graf G spolu s ohodnocením w hran reálnými čísly w : E(G) —> R. Kladně vážený graf (G,w) je takový, že w(e) > 0 pro všechny hrany e.
Definice 8.8. (vážená vzdálenost)   Mějme (kladně) vážený graf (G,w). Váženou délkou cesty P je
oZ(P) = V        w(e).
Váženou vzdáleností v (G,w) mezi dvěma vrcholy u,v pak je
d.Q(u,v) = min{cř^(P) : P je cesta s konci u,v} .
Lema 8.9. Vážená vzdálenost v nezáporně vážených grafech (i orientovaných grafech) splňuje trojúhelníkovou nerovnost.
Příklad 8.10. Podívejme se na následující ohodnocený graf (čísla u hran udávají jejich váhy-délky.)
Vzdálenost mezi vrcholy a, c je 3, stejně tak mezi b, c. Co ale mezi a, 6? Je jejich vzdálenost 6? Kdepak, vzdálenost a, b je 5, její cesta vede po „horních" vrcholech, jak je vyznačeno. Povšimněte si, že tento příklad zároveň ukazuje, že postup prohledáváním do šířky není korektní pro hledání vzdáleností ve váženém grafu. □
67
Problém nejkratší cesty
Problém nejkratší cesty mezi dvojicí vrcholů prostě hledá váženou vzdálenost vrcholů a příslušnou cestu. Jedná se patrně o nejznámější „grafový" problém v praktických aplikacích, jenž nalezneme od vyhledávání dopravních spojení, GPS navigací, plánování pohybů robota, až po třeba rozhodovací systémy.
Tento problém se nejčastěji řeší implementací klasického Díjkstrova algoritmu, který je vhodnou úpravou procházení grafu do šířky - vybírá vždy vrchol s nejmenší vzdáleností mezi uschovanými vrcholy.
Dijkstrův algoritmus
Algoritmus 8.11. Hledání nejkratší cesty mezi u a v v kladně váženém grafu.
Tento algoritmus využívá proměnnou hodnotu (pole) d(x) k ukládání nalezených vzdáleností do každého vrcholu x, vedle samotného vrcholu, přičemž tuto hodnotu postupně „vylepšuje" až do finálního zpracování vrcholu.
• Vstup:   Souvislý graf G, daný seznamem vrcholů a seznamy vycházejících hran z každého vrcholu, plus váhy w hran. Počáteční vrchol u a koncový v.
• Úschovna U <r- |(it, d{u) = 0)}.
• Dokud U Ý 0? opakujeme:
* Zvolíme (x, d(x)) G U takové, že d(x) je minimální. Odebereme U <r- U\ |(rr, d{x))}.
* Pokud x = v, algoritmus může skončit.
* Pro všechny hrany / G E (G) vycházející z x provedeme:
- Nechť y je druhý konec hrany / = xy:
a nechť ď(y) = d{x) + w(f)   (nová cesta do y přes x).
- Pokud (y, d(y)) <£ U, nebo (y, d(y)) G U pro d(y) > ď(y), odložíme U<r- (U\{(y,d(y))})u{(y, ď(y))} (výměna za novou, lepší dočasnou vzdálenost do y).
• Výstup: d{v) udává váženou vzdálenost z u do v.
Poznámka: V konkrétní implementaci Dijkstrova algoritmu nejspíše využijeme nějakou datovou strukturu podporující rychlé vkládání prvků a vybírání podle minimální hodnoty klíče - nejlépe tedy haldu, a k tomu pole d[x] přímo ukládající průběžně aktualizovanou dočasnou váženou vzdálenost z u do každého x.
Komentář: Klíčem k pochopení činnosti Dijkstrova algoritmu je „uvidět", že v každé jeho fázi jsou správně nalezeny všechny nejkratší cesty z u vedoucí po zpracovaných vrcholech. Postupem prohledávání grafu se tak jednou dostaneme až k určení správné vzdálenosti cíle v.
Příklad 8.12. Ukázka běhu Dijkstrova Algoritmu 8.11 pro nalezení nejkratší cesty mezi vrcholy u, v v následujícím váženém grafu.
68
Důkaz správnosti
Věta 8.13. Díjkstrův Algoritmus 8.11 pro kladně vážený graf (G,w) vždy správně najde nejkratší cestu mezi danými vrcholy u,v.
Důkaz vede přes následující zesílené tvrzení indukcí:
• V každé iteraci Algoritmu 8.11 hodnota d(x) udává nejkratší vzdálenost z vrcholu u do x při cestě pouze po už zpracovaných vnitřních vrcholech.
V bázi indukce dovolujeme pouze cesty používající u a x, tj. jen hrany vycházející z u. Ty jsou v první iteraci algoritmu probrány a jejich délky uloženy do U. V každém dalším kroku je vybrán jako vrchol x ke zpracování ten, který má ze všech nezpracovaných
69
vrcholů nejkratší nalezenou vzdálenost od počátku u. V tom okamžiku je d(x) platnou vzdáleností do x, neboť jakákoliv cesta přes jiný nezpracovaný vrchol nemůže být kratší díky nezápornosti vah w.  Z toho pak vyplývá, že zpracování vrcholu x správně upraví
8.4   Problém minimální kostry
Na závěr této lekce se zaměříme ještě na jednu tradiční úlohu, která se koncepčně podobá problému nejkratší cesty. V tomto případě nebudeme hledat nejkratší spojení mezi dvojicí vrcholů, ale mezi všemi vrcholy najednou - této úloze se říká minimální kostra neboli MST („minimum spanning tree"). V návaznosti na Oddíl 7.4 definujeme toto:
Definice: Podgraf T C G souvislého grafu G se nazývá kostrou, pokud
* T je stromem a
* V(T) = V(G), neboli T propojuje všechny vrcholy G.
Váhou (délkou) kostry T C G váženého souvislého grafu (G, w) rozumíme
Definice 8.14. Problém minimální kostry (MST) ve váženém souv. grafu (G,w) hledá kostru T C G s nejmenší možnou vahou (přes všechny kostry grafu G).
Komentář: Problém minimálni kostry je ve skutečnosti historicky úzce svázán s jižní Moravou a Brnem, konkrétně s elektrifikací jihomoravských vesnic ve dvacátých letech! Právě na základě tohoto praktického optimalizačního problému brněnský matematik Otakar Borůvka jako první v matematické literatuře zformuloval a podal řešení problému minimální kostry v roce 1928. První ne-českou publikací na toto téma je až Kruskalův hladový algoritmus z roku 1956.
Hladové řešení minimální kostry
Následující postup tzv. hladového nalezení minimální kostry pochází od Kruskala.
Metoda 8.15. Hladový postup pro minimální kostru grafu (G,w).
Mějme dán souvislý vážený graf G s ohodnocením hran w.
• Seřadíme všechny hrany G jako E(G) = (e\, e2,..., em) tak, že w(ei) < w(e2) < ■ • • < w(em).
• Inicializujeme prázdnou kostru T = (V(G), ty).
• Po řadě pro i = 1,2,... ,m provedeme následující:
* Pokud T + e,i nevytváří kružnici, tak E(T) ^— E(T) U {ej}.
(Neboli pokud e« spojuje různé komponenty souvislosti dosavadního T.)
• Na konci T obsahuje minimální kostru grafu G (případně jednu z několika takových). Věta 8.16. Hladový postup korektně spočítá minimální kostru váženého grafu (G,w).
dočasné vzdálenosti odložené do U. Důkaz indukcí je hotov.
□
70
Důkaz (náznak): Pro spor předpokládejme, že 7\ je kostra spočítaná Metodou 8.15 a T2 nějaká minimální kostra, kde cř^(T2) < dg(Ti) a rozdíl |£,(T1)A£,(T2)| je nejmenší. Nechť i je nejmenší index takový, že G E(T1)AE(T2). Pak nutně G E (Ti) \ E(T2) (proč?), a tudíž T2 + podle Důsledku 7.17 obsahuje kružnici procházející také hranou e j pro j > i. Potom však T3 = (T2 + e«) \ {e,-} je další kostrou mající váhu cř^(T2) + w(e,i) — w(cj) > cř^(T2), a proto w(e,i) = w(cj). Tudíž T3 je minimální kostra „bližší" Tí ve smyslu symetrického rozdílu, což je spor s volbou T2. □
Jarníkův (Primův) algoritmus
Ač koncepčně velmi jednoduchá, má Metoda 8.15 některé problematické implementační detaily, pro které je mnohem častěji používán následující algoritmus (často připisován američanu Primoví, ale mnohem dříve publikován Vojtěchem Jarníkem v 1930), založený na běžném procházení grafu.
Algoritmus 8.17. Hledání minimální kostry ve váženém grafu (G,w).
Opět mějme dán souvislý vážený graf G s ohodnocením hran w. Níže uvedená specifická implementace procházení grafu využívá úschovnu rozšířeným způsobem, kdy ukládá i příchozí hranu do vrcholu.
• Vstup:   Souvislý graf G, daný seznamem vrcholů a seznamy vycházejících hran z každého vrcholu, plus váhy w hran.
• Vybereme libovolný počátek prohledávání u G V (G); úschovna U G- {(-u, 0)}. Kostra T = (V(G), f/}).
• Dokud U Ý 0? opakujeme:
* Zvolíme (x, e) E U takové, že w(é) je minimálni (kde w(0) = 0). Odebereme U ^— U \ {(x, e)}.
* Přidáme E (T) ^— E (T) U {e}  (nová hrana do budoucí kostry).
* Pro všechny hrany / G E (G) vycházející z x provedeme:
- Nechť y je druhý konec hrany / = xy.
- Pokud (y, /') G' U, nebo (y, /') G U pro nějaké w(f') > w(f). odložíme U<r- (U\{(y,f')})u{(y,f)}
(nalezena kratší hrana f mezi zpracovanými a nezpracovanými vrcholy).
• Výstup: T udává výslednou minimálni kostru.
Poznámka: V konkrétní implementaci postupujeme stejně jako u Dijkstrova Algoritmu 8.11. nejlépe za použití haldy ukládající dvojice (y, f) podle klíče w(f).
Rozšiřující studium
S běžnými grafovými algoritmy, které zahrnují zde uvedené a mnohem více, se studenti informatiky seznámí hlouběji v každém kurzu návrhu algoritmů. (Navíc jsou běžné grafové algoritmy výborně popsány na Wikipedii...) Rozšíření postupu prohledávání grafu nám například umožní vyhledávat 2-souvislé nebo silně-souvislé komponenty. Pro hledání nejkratší cesty také existují soňstikovanější algoritmy, které jsou schopny pracovat i za přítomnosti záporných hran (ale bez záporných cyklů), jako třeba Johnsonův algoritmus. My si dále uvedeme jako příklad Floyd-Warshallův algoritmus s důkazem správnosti v Lekci 11.
71
Celkově je třeba říci, že v našem kurzu se na rozdíl od kurzů algoritmických nezabýváme vůbec otázkami programátorské implementace a efektivity, nýbrž studujeme matematické aspekty grafových úloh a metod jejich řešení. Oba pohledy by pak dobře vybavený informatik měl znát.
Pokud máte navíc zájem se dozvědět více o zajímavé české historii problému minimální kostry, přečtěte si v dříve zmíněné knize Kapitoly z diskrétní matematiky autorů Jiřího Matouška a Jaroslava Nešetřila.
72
9   Orientované grafy, Toky v sítích
Uvod
Fakt, že grafy se často používají k modelování různých druhů sítí z reálného světa, byl vidět již v předchozí lekci. Na rozdíl třeba od cestních sítí se nyní budeme zabývat typem síťových úloh, ve kterých není podstatná délka hran a spojení, nýbž jejich propustnost. (Typickými příklady jsou potrubní nebo počítačové sítě.) Základní úlohou v této oblasti je problém nalezení maximálního toku v síti za podmínky respektování daných kapacit hran. I na tento problém si uvedeme jednoduchý klasický algoritmus a především si budeme všímat mnohých důležitých matematických důsledků tohoto algoritmu, jmenovitě vázaných k tzv. dualitě maximálního toku a minimálního řezu, která přirozeně vysvětluje optimalitu řešení mnohých úloh. Následně si ukážeme široké využití toků v síti, které sahá od grafové souvislosti až třeba pro problém segmentace obrazu.
Jelikož pro zkoumaný typ sííových úloh je klíčová implicitní orientace každé hrany, v této lekci začneme samotnou dennici orientovaného grafu a základními vlastnostmi; obdobně úvodní látce vyložené o grafech v Lekci 7.
Zadefinujeme orientované grafy a uvedeme si jejich základní vlastnosti, včetně orientované souvislosti. Deňnujeme pojem sítě s kapacitami hran a ukážeme si základní algoritmus pro úlohu hledání maximálního toku. Probereme některé důležité teoretické důsledky postupu nalezení maximálního toku; především dualitu toku a řezu, vyšší úrovně souvislosti grafu, hledání bipartitního párování a systémů různých reprezentantů.
9.1    Základní pojmy orientovaných grafů
Požadavek explicitně vyjádřit směr hrany přirozeně vede na následující definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.)
Definice 9.1. Orientovaný graf je uspořádaná dvojice D = (V, E), kde V je množina vrcholů & E C V x V je množina hran - tj. podmnožina vybraných uspořádaných dvojic vrcholů.
Pojmy podgrafu a isomorfismu se přirozeně přenášejí na orientované grafy.
Značení: Hrana (u, v) (zvaná také šipka) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v,u) je různá od (u,v). Speciálně hrana tvaru (u, u) se nazývá orientovaná smyčka.
Komentář: Orientované grafy odpovídají relacím, které nemusí být symetrické. Mezi stejnou dvojicí vrcholů mohou tudíž existovat dvě hrany v obou směrech, nebo jen kterákoliv jedna z
Cíle
73
nich nebo žádná. Všimněte si také, že orientované grafy implicitně odlišujeme od obyčejných použitím písmene D místo dřívějších G, H.
Například orientovaná cesta délky n > 0 je následujícím grafem na n + 1 vrcholech
a orientovaná kružnice (také cyklus) délky n > 1 vypadá takto:
4^3 2
6      ... n
Definice: Počet hran začínajících ve vrcholu u orientovaného grafu D nazveme výstupním stupněm d^u) a počet hran končících v u nazveme vstupním stupněm d^u).
Komentář: Součet všech výstupních stupňů je přirozeně roven součtu všech vstupních stupňů orientovaného grafu. Důkaz viz Věta 7.3.
Všimněte si, že některá literatura používá opačná znaménka ( —/+) při značení výstupních a vstupních stupňů, ale s tím nic nenaděláme a čtenář se prostě vždy musí zorientovat a zjistit aktuální situaci.
Definice: Symetrizací orientovaného grafu D rozumíme neorientovaný graf G vzniklý „zapomenutím směru hran" v D, přesněji V(G) = V(D) a uv G E(G) právě když {(u,v),(v,u)}nE(D)r®.
Souvislost na orientovaných grafech
Pojem orientované souvislosti grafu D je natolik fundamentálně odlišný od neorientovaného případu (což je dáno právě jeho „směrovostí"), že si zaslouží samostatnou diskusi i v našem zběžném pohledu na orientované grafy. Uvedeme si na ni odstupňovaně tři základní pohledy:
• Slabá souvislost. Jedná se o tradiční souvislost na symetrizaci grafu D
Komentář: Zjednodušeně a názorně se dá říci, že při cestování grafem „zapomeneme" směr šipek. Na obrázku:
®-2> •-2> • <í-• <í-•-3=-®
Tento přístup sice může vypadat poněkud nesmyslně - proč šipky zavádět a pak zapomínat jejich směr, avšak brzy u tzv. nenasycených cest uvidíme smysl představy, že cesta v orient-vaném grafu se „tlačí" proti směru hrany.
74
• Dosažitelnost (směrem „ven"). Orientovaný graf D je dosažitelný směrem ven, pokud v něm existuje vrchol v G V (D) takový, že každý vrchol x G V (D) je dosažitelný orientovaným sledem z v.
V ®-3>
Komentář: Podrobným zkoumáním následujícího obrázku zjistíme, že jeho graf není dosažitelný směrem ven, neboť chybí možnost dosáhnout vrchol b úplně vpravo. Na druhou stranu po vypuštění b je zbylý graf dosažitelný ven z vrcholu a vlevo.
• Silná souvislost. Nechť »2 je binární relace na vrcholové množině V(D) orientovaného grafu D taková, že u ~ v právě když existuje dvojice orientovaných cest - jedna z u dowa druhá z v do u v grafu D. Pak »2 je relace ekvivalence.
Definice 9.2. Silné komponenty orientovaného grafu D
jsou třídy ekvivalance relace »2 uvedené v předchozím. Orientovaný graf D je silně souvislý pokud má nejvýše jednu silnou komponentu.
Komentář: Pro ilustraci si mírně upravíme dříve prezentovaný orientovaný graf tak, že bude dosažitelný z nejlevějšího vrcholu. Je výsledek silně souvislý?
Z.
Ne, na obrázku jsou vyznačené jeho 4 silné komponenty. Vpravo zároveň uvádíme pro ilustraci obrázek kondenzace silných komponent tohoto grafu, což je acyklický orientovaný graf s vrcholy reprezentujícími zmíněné silné komponenty a směry hran mezi nima.
Pro zvídavé čtenáře poznamenáváme, že si mohou definici silné komponenty porovnat s jádrem předuspořádání v Oddíle 5.2. Kde vidíte drobný rozdíl?
75
9.2   Definice sítě a toku
Základní strukturou pro reprezentaci sítí je vážený orientovaný graf (přičemž implicitní směr hran je v tomto kontextu nezbytný). Váhy (hran) v takovém modelu vyjadřují „kapacity" jednotlivých spojů a nás zajímá, jak mnoho uvažované substance dokážeme (různými cestami) přenést z daného zdroje do stoku. Podstata substance není důležitá, ale ta musí být vhodně rozdělitelná.
Definice 9.3. Síť je čtveřice S = (D,z,s,w), kde
* D je orientovaný graf,
* vrcholy z G V (D), s G V (D) jsou zdroj a stok,
* w : E(D) —> R+ je kladné ohodnocení hran, zvané kapacita hran.
Na obrázku je zakreslena síť s vyznačeným zdrojem z a stokem s, jejíž kapacity hran jsou zapsány čísly u hran. Šipky udávají směr hran, tedy směr proudění uvažované substance po spojnicích. Pokud směr proudění není důležitý, vedeme mezi vrcholy dvojici opačně orientovaných hran se stejnou kapacitou. Kapacity hran pak omezují maximální množství přenášené substance.
Poznámka: V praxi může být zdrojů a stoků více, ale v definici stačí pouze jeden zdroj a stok, z něhož / do nějž vedou hrany do ostatních zdrojů / stoků. (Dokonce pak různé zdroje a stoky mohou mít své kapacity.)
Velikost toku v síti
V souladu s praktickými aspekty nás u toku v síti zajímá především to, jaké „množství" substance (velikost toku) se skutečně přenese od zdroje ke stoku.
Značení: Pro jednoduchost píšeme ve výrazech značku e —y v pro hranu e přicházející do vrcholu v a e     v pro hranu e vycházející z v.
Definice 9.4. Tok v síti  S = (D,z,s,w) je funkce / : E(D) —> R^ splňující
* Ve G E (D) : 0 < f (e) < w(e),
* Vv(=V(D),vŕz,s:  E/(e)= E /(e)-
Velikost toku / je dána výrazem ||/|| = E f(e) ~ E f(e)-
e<—z e—>z
Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve formátu F/C, kde F je hodnota toku na hraně a C je její kapacita.
76
Komentář: Neformálně tok znamená, kolik substance je každou hranou zrovna přenášeno (ve směru této hrany, proto hrany musí být orientované). Tok je pochopitelně nezáporný a dosahuje nejvýše dané kapacity hrany. Navíc je nutno v každém vrcholu mimo z, s splnit podmínku „zachování substance".
Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5.
Poznámka: Obdobně se dá velikost toku definovat u stoku, neboť platí následující identita odvozená a faktu zachování substance (mimo z, s) v definici toku
o = E (/(«) - /(«)) = E í E   - E /(«)) = E í E   - E m
edE vďV  \e<—v e—>v /       v=z,s \e-i-v e—>v
Proto velikost toku počítaná u zdroje je rovna opačné velikosti toku počítaného u stoku
ÍE/(e)-E/(e)) = ÍE/(e)-E/(e)
\e<— z e—>z / \e—>s e-(—s
9.3   Nalezení maximálního toku
Naším úkolem je najít co největší přípustný tok v dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy. Navíc tyto algoritmy mají zajímavé teoretické souvislosti a důsledky uvedené později.
Definice 9.5. Úloha hledání maximálního toku v síti S = (D,z,s,w).
Úkolem je v síti S najít tok / ze zdroje z do stoku s podle Definice 9.4 takový, který
maximalizuje velikost ||/||.
Komentář: Tok velikosti 5 uvedený v ukázce v předchozí části nebyl optimální, neboť v této síti najdeme i tok velikosti 6:
Jak však poznáme, že větší tok již v dané síti neexistuje? V této konkrétní ukázce to není obtížné, vidíme totiž, že obě dvě hrany přicházející do stoku mají součet kapacit 2+4 + 6, takže více než 6 do stoku ani přitéct nemůže. V obecnosti lze použít obdobnou úvahu, kdy najdeme podmnožinu hran, které nelze tokem „obejít" a které v součtu kapacit dají velikost našeho toku. Existuje však taková množina hran vždy? Odpověď nám dá následující definice a věta.
77
Pojem řezu v síti
Definice 9.6. Rez v síti  S = (D, z, s, w) je podmnožina hran X C E(D)
taková, že v podgrafu D — X (tj. po odebrání hran X z D) nezbude žádná orientovaná
cesta ze z do s. Velikostí řezu X rozumíme součet kapacit hran z X, tj. ||X|| = ^2eeX w(e).
Zcela klíčovým poznatkem síťových úloh je následující velmi hezká charakterizace jejich optimálního řešení
Věta 9.7. Maximální velikost přípustného toku v síti je vždy rovna minimální velikosti řezu v ní.
Komentář: Na následujícím obrázku vidíme trochu jinou síť s ukázkou netriviálního minimálního řezu velikosti 5, naznačeného svislou čárkovanou čarou. Všimněte si dobře, že definice řezu mluví o přerušení všech orientovaných cest ze z do s, takže do řezu stačí započítat hrany jdoucí přes svislou čáru od z do s, ale ne hranu jdoucí zpět. Proto je velikost vyznačeného řezu 1+4 = 5.
Důkaz Věty 9.7 bude proveden následujícím Algoritmem 9.9.
Nenasycené cesty v síti
Definice: Mějme síť S a v ní tok /. Nenasycená cesta P (v S vzhledem k /) je neorientovaná cesta v D mezi určenými vrcholy (obvykle ze z do s), tj. posloupnost navazujících libovolně orientovaných hran e±, e2,..., em, kde /(e^) < w(ei) pro e« ve směru ze z do s a /(e^) > 0 pro e j v opačném směru.
Hodnotě w(e,i) — /(e^) > 0 pro hrany e^ ve směru z u do v a hodnotě f(cj) > 0 pro hrany Cj v opačném směru říkáme rezerva kapacity hran. Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran.
Komentář: Zde vidíme příklad nenasycené cesty ze zdroje do stoku s minimální rezervou
kapacity +1.
rezerva kapacity:
1/2 1/1
+1 +1
+1
2/3
+2 +2
> 0
Všimněte si dobře, že cesta není orientovaná, takže hrany na ní jsou v obou směrech.
Metoda 9.8. Maximální tok vylepšováním nenasycených cest.
Základní myšlenkou této jednoduché metody hledání maximálního toku v dané sítí je prostě opakovaně vylepšovat tok podél nalezených nenasycených cest.
Komentář: Ve výše zakresleném obrázku nenasycené cesty byla minimální rezerva kapacity ve výši +1, a tudíž nasycením této cesty o velikost toku 1 vzniká následující fragment
78
přípustného toku v síti:
4/4     2/2     0/1     1/3 3/4
Zajímavé je se podívat, co se stalo s prostředními zpětně orientovanými hranami - fakticky byl jejich zpětný tok o 1 snížen/zastaven, přičemž toto množství nyní „teče doprava" (velmi neformálně řečeno).
Fakt: Je-li minimální rezerva kapacity hran nenasycené cesty P ze z do s ve výši r > 0. pak tok ze z do s zvýšíme o hodnotu r následovně:
• pro hrany    G E (P) ve směru ze z do s zvýšíme tok na /'(e^) = f(eí) + r-
• pro hrany e,- G E (P) ve směru ze s do z snížíme tok na /'(e,) = /(e,) — r. Výsledný tok /' pak bude opět přípustný.
Základní algoritmus nenasycených cest
Rámcové implementační podrobnosti Metody 9.8 následují v popise konkrétního algoritmu.
Algoritmus 9.9. Ford-Fulkersonův pro tok v síti.
• Vstup: Síť S = (D,z,s,w) podle Definice 9.3.
. Tok /<- (0,0,... 0).
• Dále opakujeme následující:
* Prohledáváním grafu najdeme množinu U vrcholů D, do kterých se dostaneme ze z po nenasycených cestách.
* Pokud s G U, nechť P značí nalezenou nenasycenou cestu v S ze z do s.
- Zvětšíme tok / o minimální rezervu kapacity hran v P.
• Opakujeme kroky výše, dokud nenastane s .
• Výstup: Vypíšeme maximální tok / a také minimální řez jako množinu všech hran vedoucích z U do V(D) — U.
Příklad 9.10. Ukázka průběhu Algoritmu 9.9
Následují obrázky jednotlivých kroků algoritmu, kde vždy levý obrázek zvýrazní nenasycenou cestu a vpravo se nasycením zvýší celkový tok.
s)    tok = 0
79
v* Jí I K\
s) nasyceno
Závěrečný obrázek pak ukazuje výsledný tok velikosti 5 zároveň se zvýrazněným minimálním řezem stejné velikosti. □
Důkaz a důsledky Ford Fulkersonova algoritmu
Důkaz správnosti Algoritmu 9.9:  Pro každý tok / a každý řez X v síti S platí ||/|| < |X||. Jestliže po zastavení algoritmu s tokem / nalezneme v síti S řez o stejné velikosti 11-^11 = 11/11? Je Jasné, že jsme našli maximální možný tok v síti S.   (Pozor, zastavení algoritmu jsme zatím nezdůvodnili, to není tak jednoduché.)
Takže dokažme, že po zastavení algoritmu nastane rovnost ||/|| = ||X||, kde X je vypsaný řez mezi U a zbytkem grafu D. Vezměme tok f v S bez nenasycené cesty ze z do s. Pak množina U z algoritmu neobsahuje s. Schematicky vypadá situace takto:
/(e) = w(e)
©
U
©
Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e ^— U (odcházející
80
z U) plný tok f (e) = w(é) a každá hrana e —> U (přicházející do U) tok /(e) = 0, takže
E /(e) - E /(e) = E /(e) = E»(g) = n*n ■
Na druhou stranu, když v sumě uvažujeme všechny hrany grafu indukované na naší množině U, tj. e G i?(Z) f U), analogicky dostaneme požadované
o= E (^)-/(^) = EÍE/(e)-E/(e))-ÍE/(e)-E/(e)
eeE(D\U) velí \e^v e-^v )        \e<-U e-^V
= (s/(«)-£/(<))-(£/(«)-£/(«)
\e*^z e—>z / \e-<—C e—>U
= 11/11-11^11 , tj. ll/ll = ||X||.
□
Z důkazu Algoritmu 9.9 pak odvodíme několik zajímavých faktů:
Fakt: Pokud zajistíme, že Algoritmus 9.9 vždy skončí, zároveň tím dokážeme i platnost Věty 9.7.
Fakt: Pro celočíselné kapacity hran sítě S Algoritmus 9.9 vždy skončí. Pro další využití v teorii grafů je asi nej důležitější tento poznatek:
Důsledek 9.11. Pokud jsou kapacity hran sítě S celočíselné, optimální tok také vyjde celočíselně.
Důkaz: Postupujeme jednoduchou indukcí podle iterací Algoritmu 9.9: Algoritmus začíná s celočíselným tokem 0. V každé další iteraci bude na počátku tok všemi hranami celočíselný, tudíž i rezervy kapacit hran vyjdou (rozdílem od celočíselné kapacity) celočíselně. Proto i hodnoty toku budou změněny jen celočíselně, což zakončuje indukční krok. □
9.4   Zobecněné použití sítí
Pojmy sítě a toků v ní lze v kombinatorické optimalizaci zobecnit a využít několika směry. My si zde stručně uvedeme následující možnosti.
• Sítě s kapacitami vrcholů:
U sítě můžeme zadat kapacity vrcholů, neboli kapacitní váhová funkce je dána jako w : E(D) U V (D) —> R+. Takovou síť „zdvojením" vrcholů snadno převedeme na běžnou síť, ve které kapacity původních vrcholů budou uvedeny u nových hran spojujících zdvojené vrcholy. Viz neformální schéma:
5
81
• Sítě s dolními kapacitami:
Pro hrany sítě lze zadat také jejich minimální kapacity, tedy dolní meze přípustného toku, jako váhovou funkci l : E(D) —> Rg". Přípustný tok pak musí splňovat l(e) < f(e) < w(e) pro všechny hrany e. (V této modifikaci úlohy již přípustný tok nemusí vůbec existovat.)
Bipartitní párování
Biparitní grafy jsou grafy, jejichž vrcholy lze rozdělit do dvou množin tak, že všechny hrany vedou jen mezi těmito množinami, neboli podgrafy úplných bipartitních grafů.
Definice: Párování v (nyní biparitním) grafu G je podmnožina hran M C E(G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol.
Komentář: Úlohu nalézt v daném bipartitním grafu co největší párování lze poměrně snadno vyřešit pomocí toků ve vhodně definované síti. Uvedená metoda použití toků v síti na řešení problému párování přitom hezky ilustruje obecný přístup, jakým toky v sítích pomohou řešit i úlohy, které na první pohled se sítěmi nemají nic společného.
Metoda 9.12. Nalezení bipartitního párování
Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme síť S následovně:
• Všechny hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1.
• Nyní najdeme (celočíselný) maximální tok v S Algoritmem 9.9. Do párování vložíme ty hrany grafu G, které mají nenulový tok.
Důkaz správnosti Metody 9.12: Podle Důsledku 9.11 bude maximální tok celočíselný, a proto každou hranou poteče buď 0 nebo 1. Jelikož však do každého vrcholu v A může ze zdroje přitéct jen tok 1, bude z každého vrcholu A vybrána do párování nejvýše jedna hrana. Stejně tak odvodíme, že z každého vrcholu B bude vybrána nejvýše jedna hrana, a proto vybraná množina skutečně bude párováním. Zároveň to bude největší možné párování, protože z každého párování lze naopak vytvořit tok příslušné velikosti a větší než nalezený tok v S neexistuje. □
Poznámka: Popsaná metoda je základem tzv. Maďarského algoritmu pro párování v bipartitních grafech. Úlohu nalezení maximálního párování lze definovat i pro obecné grafy a také ji efektivně algoritmicky vyřešit, ale příslušný algoritmus [Edmondsův] není jednoduchý.
Výběr různých reprezentantů
Definice: Nechť M1,M2,...,Mk jsou neprázdné množiny. Systémem různých reprezentantů množin M1}M2, ■ ■ ■, nazýváme takovou posloupnost různých prvků (x1,x2,... ,xk), že Xi E Mi pro i = 1, 2,..., k.
82
Důležitým a dobře známým výsledkem v této oblasti je Hallova věta plně popisující, kdy lze systém různých reprezentantů daných množin nalézt.
Věta 9.13. Nechť Mi, M2,..., Mk jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí
VJc{l,2,...,fc}: |l M*
> \ J\
nebolí pokud sjednoceni libovolné skupiny z těchto množin má alespoň tolik prvků, kolík množin je sjednoceno.
Důkaz: Označme x±, x2,..., xm po řadě všechny prvky ve sjednocení M\VJM2\J- ■ -UMk-Definujeme si bipartitní graf G na množině vrcholů {1,2,..., k}\J{xi,X2, ■ ■ ■, xm}U{u, v}, ve kterém jsou hrany {u, i} pro i = 1, 2,..., k, hrany {v, Xj} pro j = 1, 2,..., m a hrany {i,Xj} pro všechny dvojice       pro které x j G Mj.
Komentář: Konstrukce našeho grafu G je obdobná konstrukci sítě v Algoritmu ??: Vrcholy u a v odpovídají zdroji a stoku, ostatní hrany přicházející do vrcholu x j znázorňují všechny z daných množin, které obsahují prvek Xj.
Cesta mezi u a v má tvar u, i, Xj, v, a tudíž ukazuje na reprezentanta Xj G Mi. Systém různých reprezentantů tak odpovídá k disjunktním cestám mezi u a, v. Nechť X ]e nyní libovolná minimální^ množina vrcholů v G, neobsahující samotné u a v, po jejímž odebrání z grafu nezbude žádná cesta mezi u a. v. Podle této úvahy mají naše množiny systém různých reprezentantů, právě když každá taková oddělující množina X má aspoň k prvků.
Položme J = {1, 2,..., k} \ X. Pak každá hrana z J (mimo u) vede do vrcholů z X H {xi,..., xm} (aby nevznikla cesta mezi u,v), a proto
|l I   Mj =\xn{x1,...,xm}\ = \x\-\xn{i,...,k}\ = \x\-k + \j\.
(První rovnost vyplývá z minimality množiny X.) Vidíme tedy, že |AT| > k pro všechny (minimální) volby oddělující X, právě když \J-eJMj > \J\ pro všechny volby J, což je dokazovaná podmínka naší věty. □
Poznámka: Tento důkaz nám také dává návod, jak systém různých reprezentantů pro dané množiny nalézt - stačí použít Algoritmus 9.9 na vhodně odvozenou síť.
Rozšiřující studium
83
10   Formalizace a důkazy pro algoritmy
Úvod
Po předchozí převážně matematické látce se náš výklad obrací bezprostředně k informatice. Mnozí z vás si asi již všimli, že umění programovat není zdaleka jen o tom naučit se syntaxi programovacího jazyka, ale především o schopnosti vytvářet a správně formálně zapisovat algoritmy. Přitom třeba situace, kdy programátorem zapsaný kód ve skutečnosti počítá něco trochu jiného, než si autor představuje, je snad nejčastější programátorskou chybou - o to zákeřnější, že ji žádný „chytrý" překladač nemůže odhalit.
Proto již na počátku studia informatiky je žádoucí klást důraz na správné chápání zápisu algoritmů i na přesné důkazy jejich vlastností a správnosti. A to je téma, kterému se budeme věnovat po převážný zbytek předmětu FLIB000.
Cíle
Bude zaveden způsob formálního zápisu algoritmů pro potřeby dalšího výkladu, nezávisle na konkrétních programovacích jazycích. Na tomto formalismu pak bude ukazováno správné chápání chování algoritmů a příklady důkazů na konkrétních „malých" algoritmech. Nejdůležitější technikou důkazů bude matematická indukce.
10.1   Formální popis algoritmu
Před samotným závěrem našeho matematického kurzu si položme klíčovou otázku, co je vlastně algoritmus? Když se na tím zamyslíte, asi zjistíte, že to není tak jednoduché přesně říci. Dokonce je to natolik obtížná otázka, že si zde můžeme podat jen docela zjednodušenou (či naivní?) odpověď, přesto však dostatečnou pro zamýšlenou demonstraci matematických důkazů pro běžné algoritmy.
Poznámka: Za definici algoritmu je obecně přijímána tzv. Church-Turingova teze tvrdící, že všechny algoritmy lze „simulovat" na Turingově stroji. Jedná se sice o přesnou, ale značně nepraktickou definici. Mimo Turingova stroje existují i jiné matematické modely výpočtů, jako třeba stroj RAM, který je abstrakcí skutečného strojového kódu, nebo také třeba tzv. neprocedurální (neimperativní) modely zahrnující funkcionální a logické programování.
Konvence 10.1. Zjednodušeně zde algoritmem rozumíme konečnou posloupnost elementárních výpočetních kroků, ve které každý další krok vhodné1 využívá (neboli závisí na) vstupní údaje či hodnoty vypočtené v předchozích krocích. Tuto závislost přitom pojímáme zcela obecně nejen na operandy, ale i na vykonávané instrukce v krocích.
Pro zápis algoritmu a jeho zpřehlednění a zkrácení využíváme řídící konstrukce -podmíněná větvení a cykly.
Komentář: Vidíte, jak blízké si jsou konstruktivní matematické důkazy a algoritmy v našem pojetí? Jedná se nakonec o jeden ze záměrů našeho přístupu...
1Zvídaví studenti si mohou na tomto místě uvědomit, že ve slůvku „vhodně" se skrývá celá hloubka Church-Turingovy teze. V žádném případě tak nelze mechanicky bez zamyšlení obracet, že by každá posloupnost kroků atd ... byla algoritmem ve smyslu této teze (viz také Lekce 12).
84
Příklad 10.2. Zápis algoritmu pro výpočet průměru daného pole a[] s n prvky. Algoritmus.
• Inicializujeme sum     0 :
• postupně pro i=0,l,2, . . . ,n-l provedeme
* sum     sum+a[i] :
• vypíšeme podíl (sum/n) . □
Ve „vyšší úrovni" formálnosti (s jasnějším vyznačením elementárních kroků a řídících struktur algoritmu) se totéž dá zapsat jako:
Algoritmus 10.3. Průměr z daného pole a[] s n prvky.
input pole a [] délky n; sum 0;
foreach   i     0,1,2,...,n-l do sum     sum+a[i] ;
done
res sum/n; output res;
Symbolický zápis algoritmů
Značení. Pro potřeby symbolického formálního zápisu algoritmů v předmětu FI: IB000 si zavedeme následující pravidla:
* Proměnné nebudeme deklarovat ani typovat, pole odlišíme závorkami p[].
* Přiřazení hodnoty zapisujeme a^—b, případně a := b, ale nikdy ne a=b.
* Jako elementární operace je možné použít jakékoliv aritmetické výrazy v běžném matematickém zápise. Rozsahem a přesností čísel se zde nezabýváme.
* Podmíněné větvení uvedeme klíčovými slovy if ... then . . . else ... f i , kde eis e větev lze vynechat (a někdy, na jednom řádku, i f i).
* Pevný cyklus uvedeme klíčovými slovy foreach ... do ... done, kde část za foreach musí obsahovat předem danou množinu hodnot pro přiřazování do řídící proměnné.
* Podmíněný cyklus uvedeme klíčovými slovy while ... do ... done . Zde se může za while vyskytovat jakákoliv logická podmínka.
* V zápise používáme jasné odsazování (zleva) podle úrovně zanoření řídících struktur (což jsou if, foreach, while).
* Pokud je to dostatečně jasné, elementární operace nebo podmínky můžeme i ve formálním zápise popsat běžným jazykem.
Vyzbrojeni tímto značením a matematickým aparátem „dokazování" si nyní můžeme dovolit se podívat na mnohé základní (a jednoduché) algoritmy novým kritickým pohledem.
85
Co počítá následující algoritmus?
Příklad 10.4. Je dán následující symbolicky zapsaný algoritmus. Co je jeho výstupem v závislosti na vstupech a,b?
Algoritmus 10.5.
input a, b;
res 7;
foreach   i1,2,...,b-l,b do res  <r- res + a + 2-b + 8;
done
output res;
Nejprve si zkusmo vypočítáme hodnoty výsledku res v počátečních iteracích cyklu:
b = 0:    res = 7,
6=1:    res = 7 + a + 26 + 8,
6 = 2:    res = 7 + (a + 26 + 8) + (a+ 26+ 8), ...
Co dále? Výčet hodnot naznačuje pravidelnost a závěr, že obecný výsledek po 6 iteracích cyklu bude mít hodnotu
res = 7 + 6(a + 26 + 8) = ab + 2b2 +86 + 7.
Jak však toto dokážeme? Nejlépe asi indukcí podle vstupní hodnoty 6, ale to není formálně úplně přesné, neboť s hodnotou 6 musíme pracovat jako se zcela obecným pevným parametrem a zároveň ji měnit (?) podle potřeb indukce. Pro tuto část odkazujeme do Oddílu 10.3. □
10.2   O „správnosti" a dokazování programů
Jak se máme přesvědčit, že je daný program počítá „správně"?
* Co třeba ladění programů? Jelikož počet možných vstupních hodnot je (v principu) neohraničený, nelze otestovat všechna možná vstupní data.
* Situace je zvláště komplikovaná v případě paralelních, randomizovaných, interaktivních a nekončících programů (operační systémy, systémy řízení provozu apod.). Takové systémy mají nedeterministické chování a opakované experimenty vedou k různým výsledkům. (Nelze je tudíž ani rozumně ladit, respektive ladění poskytne jen velmi nedostatečnou záruku správného chování za jiných okolností...)
* V některých případech je však třeba mít naprostou jistotu, že program funguje tak jak má, případně že splňuje základní bezpečnostní požadavky.
- Pro „malé" algoritmy je možné podat přesný matematický důkaz správnosti.
- Narůstající složitosti programových systémů a požadavky na jejich bezpečnost si pak vynucují vývoj jiných „spolehlivých" formálních verifíkačních metod.
Komentář: Mimochodem, co to vlastně znamená „počítat správně"?
86
Ukázka formálního důkazu algoritmu
Příklad 10.6. Je dán následující symbolicky zapsaný algoritmus. Dokažte, že jeho výsledkem je „výměna" vstupních hodnot a, b.
Algoritmus 10.7.
input a, b;
a <r-  a+b;
b <r-  a-b;
a        a-b;
output a, b;
Pro správný formální důkaz si musíme nejprve uvědomit, že je třeba symbolicky odlišit od sebe proměnné a,b od jejich daných vstupních hodnot, třeba ha,hb- Nyní v krocích algoritmu počítáme hodnoty proměnných:
* a = ha, b = hb,
* a    a + b = ha + hb,   b = hb,
* a = ha + hb,   b ^ a — b = ha + hb — hb = ha,
* a ^ a - b = ha + hb - ha = hb,   b = ha,
V jednotlivých krocích tak jasně vidíme, že pro kterékoliv vstupní hodnoty ha, hb bude ve výsledku obsahem proměnné a hodnota hb a obsahem proměnné b hodnota ha. Tímto jsme s důkazem hotovi. □
10.3   Jednoduché indukční dokazování
Příklad 10.6 je poněkud extrémní ukázkou ve smyslu toho, že v praxi jen málokdy zkoumaný algoritmus udělá tak málo kroků, že bychom každý krok mohli studovat zvlášť. Především počet kroků (cyklů či iterací) býva proměnný a závislý na vstupu a pak musí nastoupit lepší důkazové prostředky, především matematická indukce, která je „jako stvořená" pro formální uchopení opakovaných sekvencí v algoritmech.
Příklad 10.8. Dokažte, že následující algoritmus v závislosti na vstupech a, b navrátí výsledek ab + 2b2 + 86 + 7 (viz Příklad 10.4).
Algoritmus 10.9.
input a, b;
res 7;
foreach   i     1,2,...,b-l,b do res  <r- res + a + 2-b + 8;
done
output res;
V prvé řadě si z důvodu formální přesnosti přeznačíme mez cyklu v algoritmu na foreach i 1,2,...,c do .. (kde c = b). To děláme proto, že jinak by se nám pletla hodnota b vstupující do přiřazení do proměnné res s hodnotou počtu provedených iterací cyklu. Poté postupujeme přirozeně indukcí podle počtu c iterací (už nezávisle na vstupní hodnotě b); dokazujeme, že výsledek výpočtu algoritmu bude
res = (a + 2b + 8)c + 7 = ac + 26c + 8c + 7.
87
Pro c = 0 je výsledek správně res = 0 + 7. Pokud dále předpokládáme platnost vztahu r es = ac + 26c + 8c + 7 po nějakých c iteracích cyklu f oreach, tak následující iterace pro i     c + 1 (jejíž průběh na samotné hodnotě i nezáleží) změní hodnotu na
res <r- res + a + 26 + 8 = ac + a + 26c + 26 + 8c + 8 + 7 = = a(c + 1) + 26(c + 1) + 8(c + 1) + 7.
Důkaz indukcí je tím hotov. □
Příklad 10.10. Zjistěte, kolik znaků 'x' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 10.11. foreach   i<h-l,2,3,...,n-l,n do
foreach   j     1,2,3, . . . ,i-l,i do vytiskni   ' x' ;
done
done
Nejprve si uvědomíme, že druhý (vnořený) cyklus vždy vytiskne celkem i znaků 'x'. Proto iterací prvního cyklu (nejspíše) dostaneme postupně 1 + 2 + • • • + n znaků ;x; na výstupu, což již víme (Příklad 2.8), že je celkem \n(n + 1). Budeme tedy dokazovat následující tvrzení:
Věta.   Pro každé přirozené n Algoritmus 10.11 vypíše právě ^n(n+l) znaků 'x'.
Důkaz: Postupujeme indukcí podle n. Báze pro n = 0 je zřejmá, neprovede se ani jedna iterace cyklu a tudíž bude vytištěno 0 znaků 'x', což je správně.
Nechť tedy tvrzení platí pro jakékoliv uq a položme n = uq + 1. Prvních uq iterací vnějšího cyklu podle indukčního předpokladu vypíše (ve vnitřním cyklu) celkem |n0(n0 + 1) znaků 'x'. Pak již následuje jen jedna poslední iterace vnějšího cyklu s i <h- n=n0+l a v ní se vnitřní cyklus j ^— 1,2,... ,i=n iteruje celkem n = uq + 1 -krát. Celkem tedy bude vytištěn tento počet znaků ' x':
1 1 1
-n0(n0 + 1) + n0 + 1 = -(n0 + 1 + l)(n0 + 1) = ^n(n + 1)
Důkaz indukčního kroku je hotov. □
10.4   Rekurzivní algoritmy
Rekurentní vztahy posloupností, stručně uvedené v Oddíle 3.4, mají svou přirozenou obdobu v rekurzivně zapsaných algoritmech. Zjednodušeně řečeno to jsou algoritmy, které se v průběhu výpočtu odvolávají na výsledky sebe sama pro jiné (pokud možno striktně menší) vstupní hodnoty. U takových algoritmů je zvláště důležité kontrolovat jejich správnost a také proveditelnost. My si tuto oblast algoritmů osvětlíme několika jednoduchými příklady.
Příklad 10.12. Symbolický zápis jednoduchého rekurzivního algoritmu.
Algoritmus. Rekurzivní funkce factorial(x)
if x < 1 then   t 1;
else   t      x • factorial(x-l);
return t
88
Co je výsledkem výpočtu?  Jednoduše řečeno, výsledkem je faktoriál vstupní přirozené
hodnoty x, tj. hodnota x\ = x ■ (x — 1).....2-1. (Záporné a necelé vstupní hodnoty x pro
zjednodušení ignorujeme, ale poctivě napsaný program by si samozřejmě měl přípustnost vstupu kontrolovat sám!) Všimněte si ještě, že algoritmus i pro vstup x = 0 správně vyhodnotí 0! = 1. □
Fibonacciho čísla
Pro další příklad rekurze se vrátíme k Oddílu 3.4, kde byla zmíněna známá Fibonacciho posloupnost 1,1, 2, 3, 5, 8,13, 21, 34, 55,89,144,.... Ve skutečnosti tuto posloupnost budeme uvažovat již od nultého členu, tj. jako 0,1,1, 2, 3, 5, 8,13, 21,....
Algoritmus 10.13. Rekurzivní výpočet funkce fibonacci(x)
Pro dané přirozené x > 0 vypočítáme x-té Fibonacciho číslo následovně:
if x < 2 then   t x;
else   t       fibonacci(x-l)+fibonacci(x-2); return t
Komentář: Správnost Algoritmu 10.13 je víceméně zřejmá z jeho přímé podoby s rekurentním vzorcem v definici Fibonacciho čísel. Zamyslete se však, jak je to s praktickou „proveditelností1 takového algoritmu... Vidíte (případně si zkuste naprogramovat), že čas výpočtu roste velmi rychle? Třebaže hodnotu fibonacci(30) tímto algoritmem spočítáte poměrně rychle, s výpočtem fibonacci(40) už budete mít větší problémy a fibonacci(50) asi bude mimo vaše možnosti. To skutečně není dobrý algoritmus! Podívejte se také na bodoucí Příklad 11.5, který odhaduje, jak mnoho (exponenciálně) kroků výpočtu je potřeba.
Proto si v dalším Příkladu 10.14 uvedeme poněkud (ve skutečnosti velmi výrazně) lepší algoritmus výpočtu, podobající se přirozenému lidskému postupu psaní členů posloupnosti „do řádku na papír". Doporučujeme si oba algoritmy zkusit implementovat a mezi sebou porovnat.
Příklad 10.14. Nerekurzivní algoritmus pro Fibonacciho čísla.
Dokažte, že následující algoritmus pro každé přirozené n počítá tutéž hodnotu jako rekurentní funkce fibonacci(n) v Algoritmu 10.13 (ale mnohem mnohem rychleji).
Algoritmus . input n;
b[0] <- 0;    b[l] <- 1; foreach   i     2,3, . . . ,n do b [i]   <r- b[i-l]+b[i-2] ;
done
output b[n]
Důkaz: Indukcí podle řídící proměnné i budeme dokazovat, že po i-té iteraci cyklu algoritmu bude vždy platit b [i] = fibonacci(i): Co se týče báze indukce, toto vyplývá z úvodního přiřazení. Pro libovolné i > 2 předpokládáme platnost indukčního předpokladu b[j] = fibonacci(j) pro j G {i — l,i — 2}. V i-té iteraci cyklu pak nastane b[i] b[i — 1] + b[i — 2] = fibonacci{i — 1) + fibonacci(i — 2) = fibonacci{i) podle definice. Tím je důkaz hotov pro hodnotu i = n. □
89
Rozšiřující studium
Náš výklad pohlíží na algoritmy a programování tzv. procedurálním neboli imperativním paradigmatem. Vedle toho existují i jiné přístupy k programování, jako zmíněné funkcionální nebo logické. Na FI se s jinými přístupy studenti seznámí třeba v předmětu Neimperativní programování. Pro náš předmět však výběr výpočetního paradigmatu není nejdůležitější.
Smyslem této lekce bylo především ukázat, že u jednoduchých algoritmů lze (a je vhodné) je matematicky formálně zapisovat i dokazovat jejich správnost. Samozřejmě je iluzorní předpokládat, že obdobné důkazy správnosti podáme i pro velké softwarové projekty čítající až milióny řádků, ale postupy a techniky naučené při ověřování jednoduchých algoritmů s úspěchem využijete i při kontrole a ladění jednotlivých kousků velkých projektů.
O mnoha různých pokročilých technikách formální verifikace programů se v případě zájmu dozvíte v pokračujícím studiu. Tyto techniky jsou schopny na vhodném „modelu" rutinně a matematicky přesně ověřovat (ne)existenci mnoha běžných programátorských chyb.
90
11   Pokročilé dokazování nad algoritmy
Úvod
Přímo navazujeme na Lekci 10 a pokračujeme v ukázkách matematického dokazování nad vybranými krátkými algoritmy Výklad již bude trochu náročnější a místo uměle přichystaných (a v podstatě triviálních) příkladů se budeme věnovat i několika obecným dobře známým algoritmům. Dá se říci, že tato lekce je „vrcholem" v naší snaze o matematické dokazování algoritmů v informatice. Soustřeďte se v ukázkách důkazů na pochopení, jak jednotlivé formální matematické kroky korespondují s průběhem algoritmů.
Cíle
Naší snahou v těchto dvou lekcích je čtenáři ukázat poměrně vyčerpávající přehled způsobů a triků, které lze využít k analýze a dokazování správnosti rozumně krátkých algoritmů. Tyto poznatky by měly základem toho, aby si čtenář jako programátor uměl po sobě své algoritmy „přečíst" a ověřit jejich skutečnou správnost na lokální úrovni.
11.1   Dokazování konečnosti algoritmu
Co bývá snad ještě horší, než chybný výsledek algoritmu? Je to situace, kdy spuštěný algoritmus běží „do nekonečna" a vůbec se nezastaví.
Komentář: Všimněte si, že jsme se zatím v důkazech Lekce 10 vůbec nezamýšleli nad tím, zda naše algoritmy vůbec skončí. (To není samozřejmé a důkaz konečnosti je nutno v obecnosti podávat!) Prozatím jsme však ukazovali algoritmy využívající jen f oreach cykly, přitom podle naší konvence obsahuje f oreach cyklus předem danou konečnou množinu hodnot pro řídící proměnnou, neboli náš f oreach cyklus vždy musí skončit. Ale už v příštím algoritmu využijeme while cyklus, u kterého vůbec není jasné kdy a jestli skončí, a tudíž bude potřebný i důkaz konečnosti.
Právě nad takovou situací a její možnou prevencí se v tomto oddíle zamyslíme. Předesíláme, že další podnětná látka k témuž tématu se nachází ještě v Lekci 12.
Příklad 11.1. Zastaví se vždy výpočet následujícího primitivního algoritmu? Algoritmus 11.2. input x; while   x>5 do x  <r- x+1;
done
output x
Odpověď je samozřejmě NE, jak každý vidí pro jakýkoliv vstup x větší než 5. Jak však tuto negativní odpověď matematicky dokázat? To není zcela jednoduché, a proto si pomůžeme následujícím trikem:
• Předpokládejme pro spor, že Algoritmus 11.2 někdy skončí pro x > 5. Nechť přirozené n > 5 je zvoleno tak, že Algoritmus 11.2 skončí pro x = n po nejmenším možném počtu l průchodů cyklem while.
Pak jistě l > 0, neboť na začátku je podmínka x>5 splněna z definice n. Po prvním průchodu pak x = n + 1 > 5, avšak nyní již Algoritmus 11.2 musí skončit po l — 1 < l dalších průchodech cyklu. To je spor s volbou x = n coby vstupní hodnoty s nejmenším
91
možným počtem průchodů (pro x = n + 1 totiž do ukončení výpočtu proběhne o jeden průchod méně - o ten jeden vykonaný na začátku naší úvahy). □
Když algoritmus vždy končí
Na rozdíl od předchozí ukázky se budeme dále věnovat pozitivním případům, kdy algoritmy poslušně končí své výpočty.
Metoda 11.3. Jednoduchý důkaz konečnosti.
Máme-li za úkol dokázat, že algoritmus skončí, vhodný postup je následující:
* Sledujeme zvolený celočíselný a zdola ohraničený parametr algoritmu (třeba přirozené číslo) a dokážeme, že se jeho hodnota v průběhu algoritmu neustále ostře zmenšuje.
* Případně předchozí přístup rozšíříme na zvolenou k-tici přirozených parametrů a dokážeme, že se jejich hodnoty v průběhu algoritmu lexikograficky ostře zmenšují.
Jedná se zde vlastně o vhodné (a zjednodušené pro daný účel) využití principu matematické indukce. Pozor, naše „parametry" vůbec nemusejí být proměnnými v programu, a přesto jsou s programem implicitně nerozlučně svázány.
Komentář: Například pro rekurzivní funkci factorial(x) z Příkladu 10.12 přímo využijeme parametr x, který se ostře zmenšuje, pro snadný důkaz ukončenosti.
Zamyslíme-li se nad Metodou 11.3 do hloubky (matematické), zjistíme, že stejně jako matematická indukce je založená na této vlastnosti: V každé podmnožině přirozených čísel existuje jedno nejmenší (tomu se říká dobré uspořádání). Proto garance zmenšování přirozené hodnoty parametru algoritmu prostě musí znamenat ukončenost jeho výpočtu, bez ohledu na to, co náš vymyšlený parametr znamená. Nejlépe je to ilustrovat názornými příklady.
Příklad 11.4. Dokažte, že následující algoritmus vždy skončí pro jakýkoliv přirozený vstup x.
Algoritmus .
input   x;
while   x<100 do
y  <r-  0;     x  <r- x+1; while   y<x do y <r- y+1;
done
done
Postupujme podle Metody 11.3 - jak však dosáhneme „zmenšování parametru", když hodnoty proměnných x,y se zvětšují? To není až tolik obtížné, prostě budeme hodnoty x,y vhodně odečítat od velké konstanty. Vtip je v tom dobře zvolit vzorec parametru (vlastním odhadem chování algoritmu doplněným o poznání, že v proměnných x,y se nevyskytnou nikdy hodnoty větší než 100):
p(x,y) = 1012 — 101 • x — y
Pak je již rutinou dokázat, že v průběhu algoritmu (tj. pokud se aspoň jednou vnoří do cyklu) je vždy p(x, y) > 0 a v každém průchodu vnějšího i vnitřního cyklu se p(x, y) ostře zmenší. Čtenář nechť si toto ověří sám. □
92
Příklad 11.5. Dokažte, že následující algoritmus (viz dřívější 10.13) vždy skončí pro jakýkoliv přirozený vstup x.
Algoritmus . Rekurzivní výpočet funkce fibonacci(x)  pro přirozené x. if x < 2 then   t x;
else   t       fibonacci(x-l)+fibonacci(x-2); return t
Nyní je na první pohled přirozené sledovat přímo parametr x. Indukcí podle něj pak snadno odvodíme, že výpočet fibonacci(x) vždy skončí, neboť jsou rekurzivně volány jen menší hodnoty parametru. V čem je tedy možný nedostatek tohoto přímého přístupu? V zásadě pouze jediný; nezískáme z něj žádný rozumný horní odhad počtu kroků algoritmu. Pro vysvětlení, problém spočívá zhruba v tom, že v bodě fibonacci(x-l)+fibonacci(x-2) se výpočet „rozvětvuje" a my musíme vhodným způsobem umět sečíst počty kroků obou větví.
Na druhou stranu při trikové volbě parametru p(x) = 2X pro Metodu 11.3 v každé iteraci rekurzivního volání fibonacci(x) pro x > 2 nastane
p(x - 1) + p(x - 2) = T'1 + T'2 < 2 • 2*-1 - K T
a počet iterací výpočtu fibonacci(n) tak bude vždy nejen konečný, ale podle uvedené úvahy přímo striktně menší než 2n.
Přesto, tento algoritmus je velmi pomalý a mnohem lepšího výpočetního času výpočtu Fibonacciho čísel dosáhneme třeba s alternativním algoritmem Příkladu 10.14. □
Dodatek: Jak konstruovat cykly permutace
Pro mírně složitější ilustraci výše uvedeného konceptu dokazování konečnosti se podíváme na snadný postup nalezení rozkladu permutace na cykly, u kterého však vůbec není na první pohled jasné, zda má skončit.
Algoritmus 11.6. Cykly permutace.
Pro danou permutací tt na n-prvkové neprázdné množině A = {1,2,... ,n} vypíšeme její cykly (víz Oddíl 6.4) takto:
U <r-  {1,2,...,n} = A; while        0 do
x        min(U) ;      (nejmenší prvek množiny)
začínáme výpis cyklu ' (' ;
while   xGU do vytiskneme x;
U    <r-    U\{x} J        X    <r-    7r(x) J
done
ukončíme výpis cyklu ')' ;
done
Jak dokážeme správnost a konečnost tohoto algoritmu? Platí, že přímá aplikace indukce podle n nepřinese nic podstatného. Důkaz si tentokrát rozdělíme na dvě části (podle dvou while cyklů).
93
Věta. Za předpokladu, že vnitřní while cyklus pro jakoukoliv počáteční volbu x skončí, vypíše cyklus permutace 7r obsahující x a odebere všechny prvky tohoto cyklu z množiny U, Algoritmus 11.6 vždy skončí se správným výsledkem.
Důkaz: Postupujeme indukcí podle počtu cyklů v permutaci 7r. Jediný cyklus v 7r (báze indukce) je vypsán dle předpokladu věty a množina U zůstane prázdná, tudíž vnější while cyklus skončí po první iteraci a výsledek je správný.
Podle Věty 6.6 se každá permutace dá zapsat jako složení disjunktních cyklů. Nechť 7T je tedy složena z l > 1 cyklů. Po první iteraci while cyklu zbude v restrikci permutace 7T na množinu U celkem l — 1 cyklů. Podle indukčního předpokladu pak tyto zbylé cykly budou správně vypsány a algoritmus skončí. □
Komentář: Vidíte, že v tomto důkaze indukcí je indukční krok zcela triviální a důležitý je zde především základ indukce?
Věta. Pokud 7r je permutace, tak vnitřní while cyklus vždy skončí a nalezne v 7T cyklus obsahující libovolný počáteční prvek x G U. Navíc všechny prvky nalezeného cyklu odebere z množiny U.
Důkaz: Zde přímo zopakujeme argument důkazu Věty 6.6: Vezmeme libovolný prvek x = x\ G U a iterujeme zobrazení Xí+i = tv(xí) pro i = 1, 2..., až dojde ke zopakování prvku Xk = Xj pro k > j > 1. (To musí nastat, neboť A je konečná.) Jelikož prvek Xj byl již odebrán z U, v kroku x = x^ dojde k ukončení našeho while cyklu. Nadto je 7r prostá, a proto nemůže nastat x\~ = x j = tt(xj_i) pro j > 1. Takto byl nalezen a odebrán z U cyklus (a1;..., a^-i) a důkaz je hotov. □
11.2   Přehled technik důkazu indukcí
Doposud v našem textu byla matematická indukce představována ve své přímočaré formě, kdy dokazované tvrzení obvykle přímo nabízelo celočíselný parametr, podle nějž bylo potřebné indukci vést. Indukční krok pak prostě zpracoval přechod „n —> n + 1". To však u dokazování správnosti algoritmů typicky neplatí a našim cílem zde je ukázat možné techniky, jak správně indukci na dokazování algoritmů aplikovat. Uvidíme, jak si z nabízejících se parametrů správně vybrat a jak je případně kombinovat.
Technika fixace parametru
První technika důkazu prostě dopředu za některé parametry dosazuje (obecně zvolené) konstanty. Tato technika je vhodná pro případy, kdy je sice v algoritmu více parametrů, ale „zjevně" dochází ke změně jen jednoho (nebo části) z nich a chování algoritmu ke zbylým „neměnným" parametrům je dobře předvídatelné.
Příklad 11.7. Mějme následující algoritmus. Co je jeho výsledkem výpočtu?
Algoritmus .
input   x, y; res  ^— 0; while   x>0 do
res  ^— res + y;     x  ^— x-1;
done
output   res;
94
Sledováním algoritmu zjistíme, že hodnota proměnné re s bude narůstajícím součtem y + • • • + y, dokud se x nesníží na nulu. Poté odhadneme:
Věta. Pro každé x,y G N Algoritmus 11.7 vypočítá hodnotu součinu res = x ■ y.
Jaký je vhodný postup k důkazu tohoto tvrzení indukcí? Je snadno vidět, že na hodnotě vstupu y vlastně nijak podstatně nezáleží (lze y fíxovat) a důležité je sledovat x. Tato úvaha nás dovede k následujícímu:
Důkaz: Budiž hy G N libovolné ale pro další úvahy pevné. Dokážeme, že pro každý vstup x G N je výsledkem výpočtu hodnota r0 + x ■ hy, kde hy byla hodnota vstupu y a r0 byla hodnota v proměnné res na začátku uvažovaného výpočtu (pro potřeby indukce, r0 = 0 na úplném začátku). Podle principu matematické indukce uplatněné na parametr x dostáváme snadno:
* Báze x = 0 znamená, že tělo cyklu ve výpočtu už ani jednou neproběhne a výsledkem bude počáteční vq.
* Indukční krok. Nechť je tvrzení známo pro x = i a uvažujme nyní vstup x = i + 1 > 0. Prvním průchodem cyklem se uloží res res + y = r0 + hy = rx a x ^— x — 1 = i. Začáteční hodnota vstupu y nyní (pro naše indukční úvahy) tudíž je r q + hy = r\ a podle indukčního předpokladu je výsledkem výpočtu hodnota
r\ + i ■ hy = (r0 + hy) + i ■ hy = r0 + (i + 1) • hy = r0 + x ■ hy .
Důkaz matematickou indukcí je tímto ukončen. □ Komentář: Všimněte si, že techniku fixace parametru jsme mlčky použili již v Příkladě 10.8.
Indukce k součtu parametrů
Druhou techniku je vhodné použít především v případech, kdy se v průběhu algoritmu vždy některý parametr zmenšuje, ale pokaždé je to některý jiný parametr, takže v indukci se nelze zaměřit jen na jeden z nich. Jedná se spíše o situaci u rekurzivních algoritmů.
Příklad 11.8. Je dán následující rekurentní algoritmus.
Algoritmus. Funkce kombinační (m,n)  pro přirozená m, n. res  <— 1;
if m>0 A n>0 then
res  ^— kombinační(m-1,n) + kombinační(m,n-1);
fi
return res;
Výše uvedený vzorec (a ostatně i název funkce) naznačuje, že funkce má co společného s kombinačními čísly a Pascalovým trojúhelníkem
a + l\ / a \ fa b + l) = {b + l) + {b
je však třeba správně „nastavit" význam parametrů a,b...
Věta. Pro každé parametry m,n G N je výsledkem výpočtu funkce kombinační (m,n) hodnota r = (m^n) (kombinační číslo) - počet všech m-prvkových podmnožin (m + n)-prvkové množiny.
95
Důkaz indukcí vzhledem k součtu parametrů i = m + n:
* Báze i = m + n = 0 pro m,n G N znamená, že m = n = 0. Zde však s výhodou využijeme tzv. „rozšíření bázeĹÍ na všechny hraniční případy m = 0 nebo n = 0 zvlášť. V obou rozšířených případech daná podmínka algoritmu není splněna, a proto výsledek výpočtu bude iniciální res = 1. Je toto platná odpověď?
Kolik je prázdných podmnožin (m = 0) jakékoliv množiny? Jedna, 0. Kolik je m-prvkových podmnožin (n = 0) m-prvkové množiny? Zase jedna, ta množina samotná. Tím je důkaz rozšířené báze indukce dokončen.
* Indukční krok přechází na součet i + 1 = m + n pro m,n > 0. Nyní je podmínka algoritmu splněna a vykonají se rekurentní volání
kombinační(m-1,n) + kombinační(m,n-l).
Rekurentní volání se vztahují k výběru podmnožin m — l+n = m + n — 1 = i-prvkové množiny, například M = {1,2,...,«}. Výsledkem tedy je, podle indukčního předpokladu pro součet i, počet (m — l)-prvkových plus m-prvkových podmnožin množiny M.
Kolik nyní je m-prvkových podmnožin (i + l)-prvkové množiny M' = M U {i + 1}? Pokud ze všech podmnožin odebereme prvek i + 1, dostaneme právě m-prvkové podmnožiny (z těch neobsahujících i + 1) plus (m — l)-prvkové podmnožiny (z těch původně obsahujících i + 1). A to je přesně rovno kombinacni(m-1 ,n) + kombinacni(m,n-l), jak jsme měli dokázat. □
Zesílení dokazovaného tvrzení
Velmi častou situací při dokazování algoritmu je, že se zajímáme o hodnoty některých proměnných nebo „výstupy" některé funkce, ale ke správnému matematickému důkazu musíme „postihnout" i chování jiných funkcí a proměnných v algoritmu. Taková situace pak typicky vede na potřebu zesílení požadovaného tvrzení v matematické indukci.
Příklad 11.9. Zjistěte, kolik znaků 'z' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus.
Algoritmus 11.10.
st  ^ "z" ;
foreach   i«—1,2,3,...,n-l,n do
vytiskni řetězec  st;
st  ^—  st . st ;     (zřetězení dvou kopií st za sebou)
done
Zkusíme-li si výpočet simulovat pro n = 0,1,2,3,4..., postupně dostaneme počty 'z' jako 0,1,3,7,15.... Na základě toho již není obtížné „uhodnout", že počet 'z' bude (asi) obecně určen vztahem 2n — 1. Toto je však třeba dokázat!
Komentář: Jak záhy zjistíme, matematická indukce na naše tvrzení přímo „nezabírá", ale mnohem lépe se nám povede s následujícím přirozeným zesílením dokazovaného tvrzení:
Věta. Pro každé přirozené n Algoritmus 11.10 vypíše právě 2n — 1 znaků 'z' a proměnná st bude na konci výpočtu obsahovat řetězec 2n znaků ' z'.
96
Důkaz: Postupujeme indukcí podle n. ~Báze pro n = 0 je zřejmá, neprovede se ani jedna iterace cyklu a tudíž bude vytištěno 0 = 2° — 1 znaků 'z', což bylo třeba dokázat. Mimo to proměnná st iniciálně obsahuje 1=2° znak 'z'.
Nechť tedy tvrzení platí pro jakékoliv uq a položme n = uq + 1. Podle indukčního předpokladu po prvních uq iteracích bude vytištěno 2n° — 1 znaků ' z' a proměnná st bude obsahovat řetězec 2n° znaků 'z' .v poslední iteraci cyklu (pro i n=n0+l) vytiskneme dalších 2n° znaků 'z' (z proměnné st) a dále řetězec st „zdvojnásobíme". Proto po n iteracích bude vytištěno celkem 2n° — 1 + 2n° = 2n°+1 — 1 = 2n — 1 znaků 'z' a v st bude uloženo 2 • 2n° = 2no+1 = 2n znaků 'z'. □
11.3   Zajímavé algoritmy aritmetiky
Pro další ukázky důkazových technik pro algoritmy se podíváme na některé krátké algoritmy z oblasti aritmetiky. Například „zbytkové" umocňování na velmi vysoké exponenty je podkladem známé RSA šifry:
Algoritmus 11.11. Binární postup umocňování.
Pro daná čísla a, b vypočteme jejich celočíselnou mocninu (omezenou na zbytkové třídy modulo m kvůli prevenci přetečení rozsahu celých čísel v počítači), tj. ab mod m, následujícím postupem.
res <— 1;
while   b > 0 do
if   b mod 2 > 0   then res        (res-a)  mod  m ; b        |_b/2j ;     a        (a-a)  mod  m ;
done
output res;
K důkazu správnosti algoritmu použijeme indukci podle délky l binárního zápisu čísla b. Věta.  Algoritmus 11.11 skončí a vždy správně vypočte hodnotu ab mod m.
Důkaz: Báze indukce je pro l = 1, kdy 6 = 0 nebo 6=1. Přitom pro 6 = 0 se cyklus vůbec nevykoná a výsledek je res = 1. Pro 6 = 1 se vykoná jen jedna iterace cyklu a výsledek je res = a  mod m.
Nechť tvrzení platí pro £q > 1 a uvažme l = £q + 1. Pak zřejmě 6 > 2 a vykonají se alespoň dvě iterace cyklu. Po první iteraci budou hodnoty proměnných po řadě
ai = a2,  6i = [6/2J  a   res = n = (ab mod 2)   mod m .
Tudíž délka binárního zápisu b\ bude jen £q a podle indukčního předpokladu zbylé iterace algoritmu skončí s výsledkem
res = ri ■ abl  mod m = (ab mod 2 • a2^2-!)  mod m = ab mod m.
□
Euklidův algoritmus
Již z dávných dob antiky pochází následující zajímavý a koneckonců velmi jednoduchý postup-algoritmus pro nalezení největšího společného dělitele dvou čísel.
97
Algoritmus 11.12. Euklidův pro největšího společného dělitele.
Pro zadaná přirozená čísla p, q počítá následovně: input   p, q; while   p>0 A q>0 do
if   p>q   then   p  <G- p-q; else   q <G- q-p;
done
output p+q;
Věta. Pro každé p,q G N na vstupu algoritmus vrátí hodnotu největšího společného dělitele čísel pag, nebo 0 pro p = q = 0.
Důkaz opět povedeme indukcí podle součtu i = p + q vstupních hodnot. (Jak jsme psali, je to přirozená volba v situaci, kdy každý průchod cyklem algoritmu sníží jedno z p, q, avšak není jasné, které z nich.)
• Báze indukce pro i = p + q = Oje zřejmá; cyklus algoritmu neproběhne a výsledek ihned bude 0.
• Ve skutečnosti je zase výhodné uvažovat rozšířenou bázi, která zahrnuje i případy, kdy jen jedno z p, q je nulové (Proč? Jedná se o všechny případy, kdy průchod cyklem neproběhne, neboli touto indukcí sledujeme počet průchodů cyklem.) Pak výsledek p + q bude roven tomu nenulovému z obou sčítanců, což je v tomto případě zároveň jejich největší společný dělitel.
• Indukční krok. Mějme nyní vstupní hodnoty p = /íp>0ag = lí?>0 - tehdy dojde k prvnímu průchodu tělem cyklu našeho algoritmu. Předpokládejme hp > hq; poté po prvním průchodu tělem cyklu budou hodnoty p = hp — hq a q = hq, přičemž nyní p + q = hp < hp + hq = i.
Podle indukčního předpokladu (jelikož nyní p + q < i) tudíž výsledkem algoritmu pro vstupy p = hp — hq a q = hq bude největší společný dělitel NSD(hp — hq, hq). Symetricky pro hp < hq algoritmus vrátí NSD(hp, hq — hp). (Kde NSD() krátce označuje největšího společného dělitele.) Důkaz proto bude dokončen následujícím Lematem 11.13. □
Lema 11.13. Pro každá přirozená a, b platí NS D (a, b) = N SD(a — b,b) = NSD(a,b — a). Komentář: Všimněte si, že dělitelnost je dobře definována i na záporných celých číslech.
Důkaz: Ověříme, že c = NSD(a — b,b) je také největší společný dělitel čísel a a b (druhá část je pak symetrická).
• Jelikož číslo c dělí čísla a — b a b, dělí i jejich součet (a — b) + b = a. Potom c je společným dělitelem a a b.
• Naopak nechť d nějaký společný dělitel čísel a a b. Pak d dělí také rozdíl a — b. Tedy d je společný dělitel čísel a — b a b. Jelikož c je největší společný dělitel těchto dvou čísel, nutně d dělí c a závěr platí. □
Relativně rychlé odmocnění
Na závěr oddílu si ukážeme jeden netradiční krátký algoritmus a jeho analýzu a důkaz ponecháme zde otevřené. Dokážete popsat, na čem je algoritmus založen?
98
Algoritmus 11.14. Celočíselná odmocnina.
Pro dané přirozené číslo x vypočteme dolní celou část jeho odmocniny [^/x\:
p ^— x;     res 0; while   p > 0 do
while   (res + p)2 < x   do res        res + p;
p <- Lp/2J ;
done
output res ;
Poznámka: Zamysleli jste se, jaký mají algoritmy v tomto oddíle vlastně význam? Vždyť stejné úlohy jistě sami vyřešíte každý jednou jednoduchou f oreach smyčkou. Podívejte se však (alespoň velmi zhruba) na počet kroků, které zde uvedené algoritmy potřebují vykonat k získání výsledku, a srovnejte si to s počty kroků oněch „jednoduchých" algoritmů.
Pro skutečně velká vstupní čísla zjistíte propastný rozdíl - s takovým „jednoduchým" algoritmem, třeba 'f oreach i <— 1, . . .b do res <— res-a mod m done', se pro obrovské hodnoty b výsledku nikdy nedočkáte, kdežto Algoritmus 11.11 stále poběží velmi rychle. (Spočítáte, jak rychle?) Obdobně je tomu u Algoritmu 11.14.
11.4   Dynamický algoritmus
Lekci zakončíme krátkou, ale velmi hezkou ukázkou tzv. dynamického algoritmu, který je znám pod jmény Floyd-Warshallův.
Komentář: Klíčovou myšlenkou dynamických algoritmů je rozklad problému na pod-problémy, jejichž řešení jsou postupně ukládána pro další možné použití. Metoda je obzvláště vhodná v případech, kdy rozložené podúlohy si jsou podobné a mohou se opakovat.
Metoda 11.15. Dynamický výpočet všech nejkratších cest
mezí vrcholy v grafu g na množině vrcholů v(g) = {vq,Vi, ... ,vn-i}.
• Na počátku nechť d[i,j] udává 1 (případně váhu-délku hrany {ví,Vj}), nebo oc pokud hrana mezi i, j není.
• Po kroku t > 0 nechť platí, že d[i,j] udává délku nejkratší cesty mezi vi}Vj, který užívá pouze vnitřní vrcholy z množiny {vq,v1} ... ,vt_{\ (prázdné v t = 0).
• Při přechodu z kroku t na následující krok t + 1 upravujeme vzdálenost pro každou dvojici vrcholů Ví,Vj - jsou vždy pouhé dvě možnosti:
* Buď je cesta délky d [i, j] z předchozího kroku t stále nejlepší (tj. nově povolený vrchol vt nám nepomůže),
* nebo cestu vylepšíme spojením přes nově povolený vrchol vt, čímž získáme menší vzdálenost d[i,t]+d[t,j] —>-d[i,j]. (Nakreslete si obrázek.)
• Po N krocích úprav je výpočet hotov. Výpočet nejkratších cest
Alternativně si zapíšeme postup této metody až překvapivě krátkým symbolickým algoritmem:
99
Algoritmus 11.16. Výpočet všech nejkratších cest; Floyd-Warshall
input    ' Pole d [, ] délek hran (nebo oo) grafu G' ;
foreach   t        0, l,...,iV—1 do
foreach   i <-0,1,..., iV - 1, j <-0,1,..., iV - 1 do d[i,j]   <r- min(d[i,j] , d[i,t]+d[t,j] );
done
done
output ' Matice vzdáleností dvojic d [, ] ' ;
Poznámka: V praktické implementaci pro symbol oo použijeme velkou konstantu, třeba MAX_INT/2. (Nelze použít přímo MAX.INT, neboť by pak došlo k aritmetickému přetečení.)
Věta 11.17. Algoritmus 11.16 v poli d[i,j] správně vypočte vzdálenost mezi každou dvojicí vrcholů vi}Vj.
Důkaz povedeme matematickou indukcí podle řídící proměnné t cyklu. Báze je snadná - na počátku kroku t = 0 udává d[i, j] vzdálenost mezi i a j po cestách, které nemají vnitřní vrcholy (tj. pouze případně existující hranu).
Přejdemedi na krok t + 1, musíme určit nejkratší cestu P mezi j a j takovou, že P používá (mimo Ví, Vj) pouze vrcholy {-uo, v±,..., vt}. Tuto nejkratší cestu P si hypoteticky představme: Pokud vt V(P), pak d[i,j] již udává správnou vzdálenost. Jinak vt G V (P) a označíme Px podcestu v P od počátku v,i do vt a obdobně P2 podcestu od vt do konce Vj. Podle indukčního předpokladu je pak délka P rovna d [i ,t] +d [t, j].
Po provedení kroku t = N — 1 jsme hotovi se všemi vrcholy. □
Rozšiřující studium
100
12   Nekonečné množiny, Zastavení algoritmu
Úvod
Bystrého čtenáře může snadno napadnout myšlenka, proč se vlastně zabýváme dokazováním správnosti algoritmů a programů, když by to přece (snad?) mohl za nás dělat automaticky počítač samotný. Bohužel to však nejde a je hlavním cílem této lekce ukázat matematické důvody proč tomu tak je.
Konkrétně si dokážeme, že nelze algoritmicky rozhodnout, zda se daný algoritmus na svém vstupu zastaví nebo ne. Hlavními nástroji, které použijeme, budou nekonečné množiny a důkazová technika tzv. Cantorovy diagonály, která se ve velké míře používá právě v teoretické informatice. Touto lekcí se tak krátce vymaníme ze zajetí naivní teorie množin, která právě v této oblasti má své nepřekonatelné limity. (Pro zvídavé - obdobně, ale mnohem složitěji, lze dokázat že ani matematické důkazy nelze obecně algoritmicky konstruovat...)
Cíle
Zavedeme si ve zjednodušeném (a stále „poněkud naivním") pohledu nekonečné množiny a na nich techniku důkazu Cantorovou diagonálou. Pak tuto klíčovou důkazovou techniku teoretické informatiky využijeme k důkazu algoritmické neřešitelnosti problému zastavení.
12.1    O nekonečných množinách a kardinalitě
Zatímco v naivní teorii jsme si velikost konečné množiny definovali jednoduše jako počet jejích prvků vyjádřený přirozeným číslem, pro nekonečné množiny je situace obtížná a mnohem méně intuitivní. Co nám třeba brání zavést pro velikost nekonečné množiny symbol oo? Ponejvíce závažný fakt, že není „nekonečno" jako „nekonečno" (Věta 12.2)!
Právě proto si pro určení mohutnosti nekonečných množin musíme vypomoci následujícím příměrem: Velikosti dvou hromádek jablek dokážeme i bez počítání porovnat tak, že budeme z obou hromádek po řadě odebírat dvojice jablek (z každé jedno), až dokud první hromádka nezůstane prázdná - druhá hromádka pak je větší (nebo nejvýše rovna) té první.
Definice: Množina A je „nejvýše tak velká" jako množina B, právě když existuje injek-tivní funkce / : A —>• B. Množiny A a, B jsou „stejně velké" právě když mezi nimi existuje bijekce. V případech nekonečných množin pak místo "velikosti" mluvíme formálně o jejich
Komentář: Uvedená definice kardinality množin „funguje" velmi dobře i pro nekonečné množiny:
* Například N a TL mají stejnou kardinalitu (jsou „stejně velké", tzv. spočetně nekonečné).
* Lze snadno ukázat, že i (Q je spočetně nekonečná, tj. existuje bijekce / : N —> (Q, stejně jako bijekce h : N —> N2.
* Existují ale i nekonečné množiny, které jsou „striktně větší" než libovolná spočetná množina (příkladem je R ve Větě 12.2).
* Později dokážeme, že existuje nekonečná posloupnost nekonečných množin, z nichž každá je striktně větší než všechny předchozí.
101
Pro porovnávání velikostí množin někdy s výhodou využijeme následující přirozené, ale nelehké tvrzení (bez důkazu):
Věta 12.1. Pro libovolné dvě množiny A, B (i nekonečné) platí, že pokud existuje injekce A —>• B a zároveň i injekce B —>• A, pak existuje bijekce mezi A a B.
Cantorova diagonála, aneb kolik je reálných čísel
Prvním klíčovým poznatkem ukazujícím na neintuitivní chování nekonečných množin je následující důkaz, který dal historicky vzniknout metodě tzv. Cantorovy diagonály.
Věta 12.2. Neexistuje žádné surjektivní zobrazení g : N —y R.
Důsledek 12.3. Neexistuje žádné injektivní (tudíž ani bijektivní) zobrazení h : R —y N. Neformálně řečeno, reálnych čísel je striktně více než všech přirozených.
Důkaz (Věty 12.2 sporem): Nechť takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu (0,1). Podle hodnot zobrazení g si takto můžeme „uspořádat" dekadické zápisy všech reálných čísel v intervalu (0,1) po řádcích do tabulky:
Nyní sestrojíme číslo a G (0,1) následovně; jeho i-tá číslice za desetinnou čárkou bude 1, pokud v 2-tém řádku tabulky na diagonále není 1, jinak to bude 2. V našem příkladě a = 0.21211...
Kde se naše číslo a v tabulce nachází? (Nezapomeňme, g byla surjektivní, takže a někde musí být.) Konstrukce však ukazuje, že a se od každého čísla v tabulce liší na aspoň jednom desetinném místě, to je spor. (Až na drobný technický detail s rozvojem
12.2    „Naivní" množinové paradoxy
Analogickým způsobem k Větě 12.2 lze dokázat následovné zobecnění vyjadřující se o jakékoliv množině a jí přiřazené striktně větší.
Věta 12.4. Nechť M je libovolná množina. Pak existuje injektivní zobrazení f : M —> 2M, ale neexistuje žádné bijektivní zobrazení g : M —y 2M.
Důkaz: Dokážeme nejprve existenci /. Stačí ale položit f(x) = {x} pro každé x G M. Pak / : M —y 2M je zjevně injektivní.
Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bijekce g : M —>• 2M. Uvažme množinu K C M definovanou takto:
Jelikož g je bijektivní a K G 2M, musí existovat y G M takové, že g(y) = K. Nyní rozlišíme dvě možnosti:
9(0) 9(1) 9(2) 9(3) 2(4)
0. 15427578325 0. 4 0. 1 0. 3 0. 9
□
K = {x G M I x G" g (x)}.
102
- y G g(y). Tj. y G K. Pak ale y £ g(y) z definice Jí, spor.
~ V    g{y)- To podle definice J\" znamená, že y G Jí, tj. y G spor.
□
Komentář: Dvě navazující poznámky. • Technika použitá v důkazech Vět 12.2 a 12.4 se nazývá Cantorova diagonální metoda, nebo také zkráceně diagonalizace.
Konstrukci množiny K lze znázornit pomocí následující tabulky:
		b     c d
g(o) t		v-  -  V •••
9(b)		Ar V
9{c)	-	X A^ • • •
g(d)		
Symbol y/ resp. — říká, že prvek uvedený v záhlaví sloupce patří resp. nepatří do množiny uvedené v záhlaví řádku. Tedy např. d G g (b) a a 0 g (d). Množina K poté obsahuje ty diagonálni prvky označené —, tj. „převrací" význam diagonály.
• Z toho, že nekonečna mohou být „různě velká", lze lehce odvodit řadu dalších faktů. V jistém smyslu je např. množina všech problémů větší než množina všech algoritmů (obě množiny jsou nekonečné), a proto nutně existují problémy, které nejsou algoritmicky řešitelné.
Cantorův paradox
Naivní teorie množin, jak jsme si ji uvedli i v tomto předmětu, trpí mnoha neduhy a nepřesnostmi, které vyplynou na povrch především při „neopatrné manipulaci" s nekonečnými množinami. Abychom se těmto „neopatrnostem" vyhnuli bez přílišné formalizace, dva základní z těchto paradoxů si nyní ukážeme.
Příklad 12.5. Uvážíme-li nyní nekonečnou posloupnost množin
A1,A2,A3,A4,---
kde A\ = N a Ai+1 = 2Ai pro každé i G N, je vidět, že všechny množiny jsou nekonečné a každá je striktně větší než libovolná předchozí.
Kde však v tomto řazení mohutností bude „množina všech množin"? Na tuto otázku, jak sami asi cítíte, nelze podat odpověď. Co to však znamená? □
* Takto se koncem 19. století objevil první Cantorův paradox nově vznikající teorie množin.
* Dnešní moderní vysvětlení paradoxu je jednoduché, prostě „množinu všech množin" nelze definovat, taková v matematice neexistuje.
Brzy se však ukázalo, že je ještě mnohem hůř...
103
Russelův paradox
Fakt: Není pravda, že každý soubor prvků lze považovat za množinu.
* Nechť X = {M | M je množina taková, že M ^ M}. Platí X G X ?
- Ano. Tj. X G X. Pak ale X splňuje X X.
- Ne. Pak X splňuje vlastnost X ^ X, tedy X je prvkem X, tj., X G X.
* Obě možné odpovědi vedou ke sporu. X tedy nelze prohlásit za množinu. Jak je ale něco takového vůbec možné?
Komentář: Vidíte u Russelova paradoxu podobnost přístupu s Cantorovou diagonalizací? Russelův paradox se objevil začátkem 20. století a jeho „jednoduchost" zasahující úplné základy matematiky (teorie množin) si vynutila hledání seriózního rozřešení a rozvoj formální matematické logiky.
Pro ilustraci tohoto paradoxu, slyšeli jste už, že „v malém městečku žije holič, který holí právě ty muže městečka, kteří se sami neholí"? Zmíněné paradoxy naivní teorie množin zatím v tomto kurzu nerozřešíme, ale zapamatujeme si, že většina matematických a informatických disciplín vystačí s „intuitivně bezpečnými" množinami.
12.3   Algoritmická neřešitelnost problému zastavení
Výše vysvětlené myšlenky diagonalizace a principů základních paradoxů naivní teorie množin sice vypadají „velmi matematicky". Přesto je však téměř beze změny lze aplikovat i na bytostně informatickou otázku, zda lze algoritmicky poznat, pro které vstupy se daný algoritmus vůbec zastaví. Negativní odpověď na tuto otázku je jedním z fundamentálních výsledků informatiky a přitom má překvapivě krátký a čistý důkaz diagonalizací.
Fakt: Uvědomme si (velmi neformálně) několik základních myšlenek.
* Program v každém programovacím jazyce je konečná posloupnost složená z konečně mnoha symbolů (písmena, číslice, mezery, speciální znaky, apod.) Nechť E je množina všech těchto symbolů. Množina všech programů je tedy jistě podmnožinou množiny UieN^1' která je spočetně nekonečná. Existuje tedy bijekce / mezi množinou N a množinou všech programů. Pro každé j G N označme symbolem Pj program f(j). Pro každý program P tedy existuje i G N takové, že P = Pí.
* Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné mnočiny T. Množina všech možných vstupů je tedy spočetně nekonečná a existuje bijekce g mezi množinou N a množinou všech vstupů. Pro každé j G N označme symbolem Vj vstup g(j).
* Předpokládejme, že existuje program H alt, který pro dané i, j G N zastaví s výstupem ano/ne podle toho, zda Pí pro vstup Vj zastaví, nebo ne.
* Tento předpoklad dále dovedeme ke sporu dokazujícímu, že problém zastavení nemá algoritmické řešení.
Věta 12.6. Neexistuje program Halt, který by pro vstup (Pi} Vj) správně rozhodl, zda se program Pí zastaví na vstupu Vj.
Důkaz: Sporem uvažme program Diag s následujícím kódem:
104
input k;
if   iJa/£(k,k) =ano   then   while true do ; done
(Program Díag(k) má na rozdíl od Halt jen jeden vstup k, což bude důležité.) Fungování programu Díag lze znázornit za pomocí následující tabulky:
	Po Pi	p2    p3 ...
		- v •••
v1	V\	
v2	— V\	
v3		
Symbol resp. — říká, že program uvedený v záhlaví sloupce zastaví resp. nezastaví pro vstup uvedený v záhlaví řádku. Program Díag „zneguje" diagonálu této tabulky.
Podle našeho předpokladu (Díag je program a posloupnost Pí zahrnuje všechny programy) existuje j G N takové, že Díag = Pj. Zastaví Díag pro vstup Vp.
- Ano. Podle kódu Díag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví.
- Ne. Podle kódu Díag pak ale if test neuspěje, a tento program tedy zastaví. Předpoklad existence programu Halt tedy vede ke sporu. □
Komentář: Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti. Metoda diagonalizace se také často využívá v teorii složitosti k důkazu toho, že dané dvě složitostní třídy jsou různé.
Rozšiřující studium
Látka této lekce zabrousila až do teoretických hlubin matematické logiky a teorie množin. Další studium v těchto oblastech se dá očekávat hlavně u studentů speciňcky zaměřených teoretickým směrem (a mířících spíše do akademické než aplikační sféry), zajímajících se o matematiku samotnou nebo o teorii vyčíslitelnosti. Proto také uvedené pokročilé poznatky nebudou vyžadovány u zkoušky tohoto předmětu.
105
Závěrem
Gratulujeme všem, kteří se naším nelehkým učebním textem „prokousali" až sem, a přejeme mnoho úspěchů v dalším studiu informatiky.
Konečně znovu připomínáme, že nedílnou součástí našeho studijního textu je Interaktivní osnova předmětu IB000 v IS MU a v ní přiložené online odpovědníky určené k procvičování přednesené látky.
http://is.muni.cz/el/1433/podzim2012/IB000/index.qwarp
106