1 Základní formalismy: Důkaz a Algoritmus 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 odliší řadového „programátora", kterých jsou dnes mraky i bez VS vzdělání, od skutečného a mnohem lépe placeného IT experta, c Stručný přehled lekce * Pochopení formálního zápisu a významu matematických tvrzení (vět) a jejich důkazů. * Rozbor logické struktury matematických vět, konstruktivnosti důkazů. * Správný formální zápis postupu - algoritmu, ve světle matematických formalismů. Detr Hliněný, Fl MU Brno 1 Fl: IB000: Základní formalisnry 1.1 Úvod 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, c • Uvažme matematickou větu (neboli tvrzení) tvaru „Jestliže platí předpoklady, pak platí závěr", c • 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, c 0 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 prostě celou problematiku uvedeme názornými příklady. >etr Hliněný, Fl MU Brno 2 Fl: IB000: Základní formalism ŕ 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é. Poznámka pro připomenutí: - Sudé číslo je celé číslo dělitelné , tj. tvaru 2k. - Liché číslo je celé číslo nedělitelné 2, tj. tvaru 2k+í. c 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, l celé předpoklad 3) x = a + b = 2k + 2l + l + l 1,2) a komutativita sčítání (axiom)c 4) x = 2{k + l) + 2 ■ 1 3) a distributivnost násobenia 5) x = 2{k + 1 + 1) 4) a opět distributivnost násobenie 6) x = Im, m celé 5)am = fc + / + lje celé číslo (axiom) D . Petr Hliněný, Fl MU Brno Fl: IB000: Základní formalismy Příklad 1.3. Dokažte následující tvrzení: Věta. Jestliže x ay jsou racionální čísla pro která platí x < y, pak existuje racionální číslo z pro které platí x < z x, neboť ^ > 0. • Dále platí z < y, opět neboť ^ > 0. • Celkem x < z < y. c Poznámka. Alternativní formulace Věty z Příkladu 1.3 mohou znít: - Pro každé i,j/£Q, kde x < y, existuje z G Q takové, že x < z < y. - Množina racionálních čísel je hustá. Detr Hliněný, Fl MU Brno 4 Fl: IB000: Základní formalisnry D 1.2 Struktura matematických vět a důkazů • První krok formálního důkazu je uvědomit si, co 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 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í. • Příklady běžné formulace matematických vět: * Konečná množina má konečně mnoho podmnožin.d * sin2(o:) +cos2(a) = l.n * Graf je rovinný jestliže neobsahuje podrozdělení K& nebo K^.c • Často pomůže pouhé rozepsání definic pojmů, které se v dané větě vyskytují. • Všimněte si také, jaký je správný logický význam matematického tvrzení vysloveného touto formou „implikace". Především, pokud předpoklady nejsou splněny nebo jsou sporné, tak celé tvrzení je platné bez ohledu na pravdivost závěru! Petr Hliněný, Fl MU Brno 5 Fl: IB000: Základní formalismy Jak „moc formální" mají důkazy vlastně být? * * 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. Detr Hliněný, Fl MU Brno 6 Fl: IB000: Základní formalisnry 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. • Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán návod na jeho konstrukci, c Příklad 1.4. čistě existenčního důkazu. Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu sportky v roce 2009. Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2009. 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 2009 skutečně vylosován. G To je ale „podvod", že? A přece není.. . Formálně správně to je prostě tak a tečka. Petr Hliněný. Fl MU Brno _______________________________: IB000: Základní formalismy ŕ Fakt. Pro informatické i další aplikované disciplíny je důležitá konstruktivnost důkazů vět, které se zde objevují, c 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.5. „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á, c 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í i.) 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 21-n + ... + 21-n =-----7-»O. Jelikož je toto číslo (pravděpodobnost) pro n > 7 menší než 1, bude existovat obarvení bez jednobarevných zvolených podmnožin. g Petr Hliněný, Fl MU Brno Fl: IB000: Základní formalismy 17 Položme si otázku, co je vlastně algoritmus? 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. u Konvence 1.6. Zjednodušeně zde algoritmem rozumíme konečnou posloupnost elementárních výpočetních kroků, ve které každý další krok vhodně 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. 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... Petr Hliněný, Fl MU Brno 9 Fl: IB000: Základní formalismy í Příklad 1.7. Zápis algoritmu pro výpočet průměru z daného pole a [] s n prvky. • Inicializujeme sum^ O; • postupně pro i=0,l,2, . . . ,n-l provedeme * sum <—sum+a [i] ; • vypíšeme podíl (sum/n) . c D Ve „vyšší úrovni" formálnosti (s jasnějším vyznačením řídících struktur algoritmu) se totéž dá zapsat jako: Algoritmus 1.8. Průměr z daného pole a [] s n prvky. sum <— 0; foreach i<—0,1,2,...,n-l do sum <— sum+a[i]; done res <— sum/n; output res; 3etr Hliněný, Fl MU Brno 10 Fl: IB000: Základní formalismy Značení. Pro potřeby symbolického formálního zápisu algoritmů v předmětu Fl: IB000 si zavedeme následovnou konvenci: • 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 elem. 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, c • Podmíněné větvení uvedeme klíčovými slovy if ... then . . . else ... f i , kde else větev lze vynechat (a někdy, na jednom řádku, i f i). • Pevný cyklus uvedeme klíčovými slovy f oreach ... do ... done , kde část za f oreach 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, c • 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. Petr Hliněný, Fl MU Brno 11 Fl: IB000: Základní formalism Malé srovnání závěrem Jak to tedy je s vhodnou a únosnou mírou formalizace u matematických důkazů i u zápisu algoritmů?_______________________ zcela formální běžná úroveň matematika algoritmy programovaní formální rozepsání všech elem. kroků (Příklad 1.2) rozepsání všech elem. kroků ve výpočetním modelu assembler / strojový kód (kde se s ním dnes běžně setkáte?) strukturovaný a matem, přesný text v běžném jazyce strukturovaný rozpis kroků (Algoritmus 1.8), i s využitím běžného jazyka „vyšší" (strukturované) programovací jazyky, například Java Pochopitelně se ve všech třech bodech obvykle držíme druhého přístupu, tedy běžné úrovně formality, pokud si specifické podmínky výslovně nevyžadují přístup nejvyšší formality. .. 3etr Hliněný, Fl MU Brno Fl: IB000: Základní formalismy