IB107 Vyčíslitelnost a složitost úvod, while-programy, makropříkazy, Churchova teze Jan Strejček Fakulta informatiky Masarykova univerzita trocha historie Hilbertův program ■ formulovat konečnou množinu axiomů tak, aby z nich pomocí odvozovacích pravidel bylo možné získat právě veškerá pravdivá matematická tvrzení první Godelova věta o neúplnosti (1931) ► taková množina axiomů neexistuje ani pro tvrzení o aritmetice přirozených čísel se sčítáním a násobením IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 2/18 základní otázky vyčíslitelnost ■ Které problémy jsou algoritmicky řešitelné a které ne? ■ Co to vlastně je algoritmus? ■ Jaké jsou důvody neexistence algoritmů pro řešení některých problémů? složitost ■ Jsou všechny algoritmicky řešitelné problémy stejně těžké? ■ Jaká je složitost algoritmu? ■ Co je to složitost problému? IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 3/18 algoritmus požadavky ■ konečný zápis ■ vykonává se mechanicky ■ jednotlivé kroky algoritmu se vykonávají diskrétně formalismy pro popis algoritmů ■ Turingův stroj ■ A-kalkul ■ Postovy systémy ■ C++, python, ... ■ while-programy IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 4/18 notace ■ N = {0,1,2,...} ■ M+ = nezáporná reálná čísla ■ částečné funkce (neboli zobrazení) f: X -> Y m definiční obor dom(f) ■ obor hodnot range(f) ■ nedefinováno _L ■ totální funkce f: X ^ Y ■ obraz množiny A c Nk při zobrazení f: Nk -> N f (A) = {f (a) | aedom{f)nA} ■ vzor množiny B c N při zobrazení f: Nk -> N r1 (B) = {a | a g dom(f) a ŕ(a) g e} IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 5/18 syntaxe while-programů (var) Var = {x, y , z,. . . , X-| 5 x3? • • •} (asgt) —>► (i/ar) := 0 (var) := (var) +1 (var) := (var) - 1 (stm) —>► (asgf) while (var) ^ (var) do (stm) I (seq) —>► (stm) (seq)\ (stm) (prg) —>► begin end begin (seq) end P je množina všech programů. IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 6/18 sémantika while-programů intuitivně ■ proměnné nabývají hodnot z N ■ během běhu programu se hodnoty proměnných mění ■ výsledkem odečítání do záporu je 0 ■ zajímá nás, jak program změní počáteční hodnoty na hodnoty po doběhnutí programu (pokud program skončí) formálně ■ stav a : Var h-^ N ■ Env je množina všech stavů ■ sémantika programu P je dána částečnou funkcí Pí : Env -> Env IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 7/18 sémantika while-programů modifikace jedné proměnné stavu a{y) pokud y ^ x a pokud y = x a[x^a](y) = n-násobná kompozice funkce f f°(x) 1 X f"+\x) = f(fn(x)) odečítaní na N x - y pokud x > y 0 jinak xey = IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 8/18 sémantika while-programů lx:=0j(a) [x:=y+1](a) [x := y -11(a) while x^ydoáj(ff) [begin end] (cr) begin 5 end](cr) přičemž |5](_L) = cr[x <- 0] df = cr[X <- cr(y) + 1] 1 Cr[x^cr(y)e1] ' [ó]n(cr) kde n je nejmenší číslo takové, že [ó]n(cr) je 1 J definováno a M»M = MV)(y) ± pokud takové n neexistuje = mam*)) df = a = = _|_ IB107 Vyčíslitelnost a složitost: úvod, while-programy, makropříkazy, Churchova teze 9/18 sémantická funkce programu Definice 4.1 (sémantická funkce programu) Necht P je while-program aj > 0. Sémantická funkce (arity j) programu P je funkce ^ : N7' —^ N definovaná jako lpí (