3
Mnoˇ ziny, Relace a Funkce
V pˇrehledu matematick´ych formalism˚ u informatiky se v t´eto lekci zamˇeˇr´ıme na z´akladn´ı datov´e typy“ matematiky, tj. na mnoˇziny, relace a funkce. O mnoˇzin´ach jste sice ” zajist´e slyˇseli uˇz na z´akladn´ı ˇskole, ale podstatou naˇseho pˇredmˇetu je uv´est povˇetˇsinou neform´alnˇe zn´am´e pojmy na patˇriˇcnou form´aln´ı ´ uroveˇ n nutnou pro teoretick´e z´aklady informatiky.
2
Struˇ cn´ y pˇrehled lekce * Uveden´ı mnoˇzin a operac´ı mnoˇzinov´eho kalkulu. * Nˇekter´e vlastnosti mnoˇzin, princip inkluze a exkluze. * Relace a definice funkc´ı, z´akladn´ı vlastnosti. * Posloupnosti a rekurentn´ı vztahy. Petr Hlinˇ en´ y, FI MU Brno
1
FI: IB000: Mnoˇ ziny, Relace a Funkce
3.1
*
Pojem mnoˇ ziny Co je vlastnˇe mnoˇ zina?2 Na tuto ot´azku bohuˇzel nen´ı zcela jednoduch´ a odpovˇed’. . .
• Naivn´ı pohled: Mnoˇzina je soubor prvk˚ u a je sv´ymi prvky plnˇe urˇcena.“ 2 ” • Pozor, nen´ı skuteˇcn´eho rozd´ılu mezi mnoˇzinami“ a prvky“. ” ” Mnoˇziny mohou b´yt prvky jin´ych mnoˇzin!2 • Pˇr´ıklady:
∅, {a, b}, {b, a}, {a, b, a}, {{a, b}}, {x | x je lich´e pˇrirozen´e ˇc´ıslo}2
{∅, {∅}, {{∅}}},
Znaˇ cen´ı: Poˇcet prvk˚ u (mohutnost) mnoˇziny A zapisujeme |A|. • |∅| = 0,
|{∅}| = 1,
|{a, b, c}| = 3, |{{a, b}, c}| = 22
Znaˇ cen´ı mnoˇzin a jejich prvk˚ u: • x∈M
x je prvkem mnoˇziny M“. 2 ” • nˇekter´e vlastnosti a ∈ {a, b}, a 6∈ {{a, b}}, • pr´azdn´a mnoˇzina ∅, a 6∈ ∅, ∅ ∈ {∅},
∅ 6∈ ∅,
• rovnost mnoˇzin {a, b} = {b, a} = {a, b, a}, Petr Hlinˇ en´ y, FI MU Brno
2
{a, b} ∈ {{a, b}},
{a, b} = 6 {{a, b}}.
FI: IB000: Mnoˇ ziny, Relace a Funkce
Definice: Mnoˇzina A je podmnoˇzinou mnoˇziny B, pr´avˇe kdyˇz kaˇzd´y prvek A je prvkem B. P´ıˇseme A ⊆ B nebo tak´e B ⊇ A; ˇr´ık´ame tak´e, ˇze se jedn´a o inkluzi. 2 • Plat´ı {a} ⊆ {a} ⊆ {a, b} 6⊆ {{a, b}}, • A ⊂ B pr´avˇe kdyˇz A ⊆ B a A 6= B
∅ ⊆ {∅},
(A je vlastn´ı podmnoˇzinou B).2
Definice: Dvˇe mnoˇziny jsou si rovny A = B pr´ avˇe kdyˇz A ⊆ B a B ⊆ A. • Podle definice jsou mnoˇziny A a B stejn´e, maj´ı-li stejn´e prvky.2 • D˚ ukaz rovnosti mnoˇzin A = B m´ a obvykle dvˇe ˇc´asti: Oddˇelenˇe se dok´aˇz´ı inkluze A ⊆ B a B ⊆ A.
Petr Hlinˇ en´ y, FI MU Brno
3
FI: IB000: Mnoˇ ziny, Relace a Funkce
Znaˇ cen´ı: Nˇekter´e bˇeˇzn´e mnoˇziny v matematice se znaˇc´ı ∗ ∗ ∗ ∗ ∗
N = {0, 1, 2, 3, . . . } je mnoˇzina pˇrirozen´ych ˇc´ısel, Z = {. . . , −2, −1, 0, 1, 2, 3, . . . } je mnoˇzina cel´ych ˇc´ısel, Z+ = {1, 2, 3, . . . } je mnoˇzina cel´ych kladn´ych ˇc´ısel, Q je mnoˇzina racion´aln´ıch ˇc´ısel (zlomk˚u). R je mnoˇzina re´aln´ych ˇc´ısel. 2
Pozn´ amka: Tyto uveden´e ˇc´ıseln´e mnoˇziny jsou vesmˇes nekoneˇcn´e, na rozd´ıl od koneˇcn´ych mnoˇzin uvaˇzovan´ych v pˇredchoz´ım naivn´ım“ pohledu. 2 ” Pojem nekoneˇcn´e mnoˇziny se pˇr´ımo v matematice objevil aˇz teprve v 19. stolet´ı a u ukazuj´ıc´ıch, ˇze naivn´ı pohled na teorii mnoˇzin pro bylo s n´ım spojeno nˇekolik paradox˚ nekoneˇcn´e mnoˇziny nedostaˇcuje. My se k problematice nekoneˇcn´ych mnoˇzin, Kantorovˇe vˇetˇe a Russelovˇe paradoxu vr´at´ıme v z´avˇeru naˇseho pˇredmˇetu.
Petr Hlinˇ en´ y, FI MU Brno
4
FI: IB000: Mnoˇ ziny, Relace a Funkce
3.2
Mnoˇ zinov´ e operace
Definice: Sjednocen´ı ∪ a pr˚ unik ∩ dvou mnoˇzin A, B definujeme A ∪ B = {x | x ∈ A nebo x ∈ B}2 ,
A ∩ B = {x | x ∈ A a souˇcasnˇe x ∈ B} .2 • Pˇr´ıklady {a, b, c} ∪ {a, d} = {a, b, c, d},
{a, b, c} ∩ {a, d} = {a}.
2
• Vˇzdy plat´ı distributivita“ A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ” a A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). 2
Definice: Pro libovoln´y poˇcet mnoˇzin indexovan´ych pomoc´ı I rozˇs´ıˇrenˇe [ Ai = {x | x ∈ Ai pro nˇejak´e i ∈ I}2 , i∈I \ Ai = {x | x ∈ Ai pro kaˇzd´e i ∈ I} .2 i∈I
• Necht’ Ai = {2 · i} pro kaˇzd´e i ∈ pˇrirozen´ych ˇc´ısel.2 • Necht’ Bi = {x | x ∈ Petr Hlinˇ en´ y, FI MU Brno
N. Pak Si∈N Ai je mnoˇzina vˇsech sud´ych
N, x ≥ i} pro kaˇzd´e i ∈ N. Pak Ti∈N Bi = ∅. 5
FI: IB000: Mnoˇ ziny, Relace a Funkce
Definice: Rozd´ıl \ a symetrick´y rozd´ıl ∆ dvou mnoˇzin A, B definujeme A \ B = {x | x ∈ A a souˇcasnˇe x 6∈ B}2 , A∆B = A \ B ∪ B \ A .2 • Pˇr´ıklady {a, b, c} \ {a, b, d} = {c},
{a, b, c}∆{a, b, d} = {c, d}.
• Vˇzdy plat´ı napˇr´ıklad A \ (B ∩ C) = (A \ B) ∪ (A \ C) apod.
2
2
Definice: Necht’ A ⊆ M . Doplnˇek A vzhledem k M je mnoˇzina A = M \ A. • Jedn´a se o ponˇekud specifickou operaci, kter´ a mus´ı b´yt vztaˇzena vzhledem k nosn´e mnoˇzinˇe M ! 2 • Je-li M = {a, b, c}, pak {a, b} = {c}. Je-li M = {a, b}, pak {a, b} = ∅. • Vˇzdy pro A ⊆ M plat´ı A = A ( dvoj´ı“ doplnˇek). 2 ” • Vˇzdy pro A, B ⊆ M plat´ı A ∪ B = A ∩ B a A ∩ B = A ∪ B. (Viz Vennovy diagramy.)
Petr Hlinˇ en´ y, FI MU Brno
6
FI: IB000: Mnoˇ ziny, Relace a Funkce
2
Uspoˇr´ adan´ e dvojice a kart´ ezsk´ y souˇ cin Definice: Uspoˇr´adan´a dvojice (a, b) je zad´ ana mnoˇzinou {{a}, {a, b}}.2 Fakt: Plat´ı (a, b) = (c, d) pr´ avˇe kdyˇz a = c a souˇcasnˇe b = d.2 Pˇr´ıklad 3.1. Co je podle definice (a, a)?2 (a, a) = {{a}, {a, a}} = {{a}, {a}} = {{a}}.
2
Definice 3.2. Kart´ ezsk´ y souˇ cin dvou mnoˇzin A, B definujeme jako mnoˇzinu vˇsech uspoˇr´adan´ych dvojic ze sloˇzek z A a B A × B = {(a, b) | a ∈ A, b ∈ B} . 2
• Pˇr´ıklady {a, b} × {a} = {(a, a), (b, a)}, {c, d} × {a, b} = {(c, a), (c, b), (d, a), (d, b)}.2 • Plat´ı ∅ × X = ∅ pro kaˇzdou mnoˇzinu X.
2
• Mnemotechnick´a pom˚ ucka
|A × B| = |A| · |B| . Petr Hlinˇ en´ y, FI MU Brno
7
FI: IB000: Mnoˇ ziny, Relace a Funkce
2
Skl´ ad´ an´ı souˇ cinu
N
Definice: Pro kaˇzd´e k ∈ , k > 0 definujeme uspoˇr´adanou k-tici (a1 , · · · , ak ) induktivnˇe takto – (a1 ) = a1 , – (a1 , · · · , ai , ai+1 ) = ((a1 , · · · , ai ), ai+1 ).2 Fakt: Plat´ı (a1 , · · · , ak ) = (b1 , · · · , bk ) pr´ avˇe kdyˇz ai = bi pro kaˇzd´e 1 ≤ i ≤ k.2 Definice kart´ezsk´eho souˇcinu v´ıce mnoˇzin: Pro kaˇzd´e k ∈
N definujeme
A1 × · · · × Ak = {(a1 , · · · , ak ) | ai ∈ Ai pro kaˇzd´e 1 ≤ i ≤ k} .2
Z
Z Z Z
Z
• Pˇr´ıklad 3 = × × = {(i, j, k) | i, j, k ∈ }. • Co je A0 ?2 {∅}, nebot’ jedin´ a uspoˇr´ adan´ a 0-tice je pr´avˇe pr´azdn´a ∅. Pozn´ amka: Podle uveden´e definice nen´ı souˇcin asociativn´ı, tj. obecnˇe nemus´ı platit, ˇze A × (B × C) = (A × B) × C.2
V matematick´e praxi je nˇekdy v´yhodnˇejˇs´ı uvaˇzovat upravenou“ definici, podle n´ıˇz ” souˇcin asociativn´ı je. Pro ´ uˇcely t´eto pˇredn´aˇsky nen´ı podstatn´e, k jak´e definici se pˇriklon´ıme. Prezentovan´e definice a vˇety funguj´ı“ pro obˇe varianty. ” Petr Hlinˇ en´ y, FI MU Brno
8
FI: IB000: Mnoˇ ziny, Relace a Funkce
Potenˇ cn´ı mnoˇ zina Definice 3.3. Potenˇ cn´ı mnoˇ zina mnoˇziny A, neboli mnoˇzina vˇsech podmnoˇzin, je definovan´ a vztahem 2A = {B | B ⊆ A} . 2
• Plat´ı napˇr´ıklad 2{a,b} = {∅, {a}, {b}, {a, b}},
• 2∅ = {∅}, 2{∅,{∅}} = {∅, {∅}, {{∅}}, {∅, {∅}}},
• 2{a}×{a,b} = {∅, {(a, a)}, {(a, b)}, {(a, a), (a, b)}}.2 Vˇ eta 3.4. Poˇcet prvk˚ u potenˇcn´ı mnoˇziny splˇ nuje |2A | = 2|A| .2 D˚ ukaz: Struˇcnˇe indukc´ı podle |A|: Pro A = ∅ plat´ı |2A | = |{∅}| = 1.
Pro kaˇzd´y dalˇs´ı prvek b 6∈ A rozdˇel´ıme vˇsechny podmnoˇziny A∪{b} napolovic“ ” na ty neobsahuj´ıc´ı b a na ty obsahuj´ıc´ı b, tud´ıˇz A∪{b} 2 = 2 · 2A = 2|A|+1 = 2|A∪{b}| . 2 Petr Hlinˇ en´ y, FI MU Brno
9
FI: IB000: Mnoˇ ziny, Relace a Funkce
3.3
Porovn´ av´ an´ı a urˇ cen´ı mnoˇ zin
Vˇ eta 3.5. Pro kaˇzd´e dvˇe mnoˇziny A, B ⊆ M plat´ı A ∪ B = A ∩ B.
2
D˚ ukaz v obou smˇerech rovnosti. • A ∪ B ⊆ A ∩ B:
2
∗ Pro x ∈ M plat´ı x ∈ A ∪ B, pr´ avˇe kdyˇz x 6∈ A ∪ B, neboli kdyˇz z´aroveˇ n x 6∈ A a x 6∈ B.
∗ To znamen´a x ∈ A a z´ aroveˇ n x ∈ B, z ˇcehoˇz vypl´yv´a poˇzadovan´e x ∈ A ∩ B. 2 • A ∪ B ⊇ A ∩ B:
∗ Pro x ∈ M plat´ı x ∈ A ∩ B, pr´ avˇe kdyˇz x ∈ A a z´aroveˇ n x ∈ B, neboli kdyˇz z´aroveˇ n x 6∈ A a x 6∈ B. 2 ∗ To znamen´a x 6∈ A ∪ B, z ˇcehoˇz vypl´yv´ a poˇzadovan´e x ∈ A ∪ B.
Petr Hlinˇ en´ y, FI MU Brno
10
FI: IB000: Mnoˇ ziny, Relace a Funkce
2
Vˇ eta 3.6. Pro kaˇzd´e tˇri mnoˇziny A, B, C plat´ı A \ (B ∩ C) = (A \ B) ∪ (A \ C) .2 D˚ ukaz. • A \ (B ∩ C) ⊆ (A \ B) ∪ (A \ C):
∗ Je-li x ∈ A \ (B ∩ C), pak x ∈ A a z´ aroveˇ n x 6∈ (B ∩ C), neboli x 6∈ B nebo x 6∈ C.
∗ Pro prvn´ı moˇznost m´ ame x ∈ (A \ B), pro druhou x ∈ (A \ C).2
• Naopak A \ (B ∩ C) ⊇ (A \ B) ∪ (A \ C):
∗ Je-li x ∈ (A \ B) ∪ (A \ C), pak x ∈ (A \ B) nebo x ∈ (A \ C).
∗ Pro prvn´ı moˇznost m´ ame x ∈ A a z´ aroveˇ n x 6∈ B, aroveˇ n x 6∈ (B ∩ C), a tud´ıˇz x ∈ A \ (B ∩ C).2 z ˇcehoˇz plyne x ∈ A a z´ ∗ Druh´a moˇznost je analogick´ a.
Petr Hlinˇ en´ y, FI MU Brno
2
11
FI: IB000: Mnoˇ ziny, Relace a Funkce
Charakteristick´ y vektor (pod)mnoˇ ziny V pˇr´ıpadech, kdy vˇsechny uvaˇzovan´e mnoˇziny jsou podmnoˇzinami nˇejak´e nosn´e atorsk´ych aplikac´ıch, s v´yhodou mnoˇziny X, coˇz nen´ı neobvykl´e v program´ vyuˇzijeme n´asleduj´ıc´ı reprezentaci mnoˇzin. Definice: Mˇejme nosnou mnoˇzinu X = {x1 , x2 , . . . , xn }. Pro A ⊆ X definujeme charakteristick´y vektor χA jako χA = (c1 , c2 , . . . , cn ), kde ci = 1 pro xi ∈ A a ci = 0 jinak.2 • Plat´ı A = B pr´avˇe kdyˇz χA = χB .
• Mnoˇzinov´e operace jsou realizov´ any bitov´ymi funkcemi“ ” sjednocen´ı ∼ OR, pr˚ unik ∼ AND, symetrick´y rozd´ıl ∼ XOR.
Petr Hlinˇ en´ y, FI MU Brno
12
FI: IB000: Mnoˇ ziny, Relace a Funkce
Princip inkluze a exkluze Tento d˚ uleˇzit´y a zaj´ımav´y kombinatorick´y princip je nˇekdy tak´e naz´yv´an princip ” zapojen´ı a vypojen´ı“.
Vˇ eta 3.7. Poˇcet prvk˚ u ve sjednocen´ı dvou ˇci tˇr´ı mnoˇzin spoˇc´ıt´ame: |A ∪ B| = |A| + |B| − |A ∩ B| |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|2
Vˇsimnˇete si, ˇze vˇetu lze stejnˇe tak vyuˇz´ıt k v´ypoˇctu poˇctu prvk˚ u v pr˚ uniku mnoˇzin. . . Petr Hlinˇ en´ y, FI MU Brno
13
FI: IB000: Mnoˇ ziny, Relace a Funkce
Pˇr´ıklad 3.8. Z 1000 televiz´ı jich pˇri prvn´ı kontrole na v´yrobn´ı lince m´a 5 vadnou obrazovku, 10 je poˇskr´aban´ych a 12 m´ a jinou vadu. Pˇritom 3 televize maj´ı souˇcasnˇe vˇsechny tˇri vady a 4 jin´e jsou poˇskr´ aban´e a maj´ı jinou vadu. Kolik televiz´ı je celkem vadn´ych? 2 ˇ sen´ı: Dosazen´ım |A| = 5, |B| = 10, |C| = 12, |A ∩ B ∩ C| = 3, |A ∩ B| = Reˇ 3 + 0, |A ∩ C| = 3 + 0, |B ∩ C| = 3 + 4 do Vˇety 3.7 zjist´ıme v´ysledek 17. 2 2 Pozn´ amka. Jen struˇcnˇe, bez d˚ ukazu a bliˇzˇs´ıho vysvˇetlen´ı, si uvedeme obecnou formu principu inkluze a exkluze: n \ X [ |I|−1 (−1) · Ai Aj = j=1 ∅6=I⊆{1,...,n} i∈I (Jeho znalost nebude v pˇredmˇetu vyˇzadov´ana.)
Petr Hlinˇ en´ y, FI MU Brno
14
FI: IB000: Mnoˇ ziny, Relace a Funkce
3.4
Relace a funkce mezi (nad) mnoˇ zinami
Dalˇs´ım d˚ uleˇzit´ym z´akladn´ım datov´ym typem“ matematiky jsou relace, kter´ym ” vzhledem k jejich rozs´ahl´emu pouˇzit´ı v informatice vˇenujeme zv´yˇsenou pozornost. Definice 3.9. Relace mezi mnoˇzinami A1 , · · · , Ak , pro k ∈ je libovoln´a podmnoˇzina kart´ezsk´eho souˇcinu
N,
R ⊆ A1 × · · · × Ak .2 Pokud A1 = · · · = Ak = A, hovoˇr´ıme o k-´ arn´ı relaci R na A.
2
Pˇr´ıklady relac´ı. • {(1, a), (2, a)} je relace mezi {1, 2, 3} a {a, b}.
N} je bin´arn´ı relace na N.2 • {(i, j, i + j) | i, j ∈ N} je tern´ arn´ı relace na N. • {3 · i | i ∈ N} je un´ arn´ı relace na N.2 • {(i, 2 · i) | i ∈
• Jak´y v´yznam vlastnˇe maj´ı un´ arn´ı a nul´ arn´ı relace na A? Petr Hlinˇ en´ y, FI MU Brno
15
FI: IB000: Mnoˇ ziny, Relace a Funkce
Funkce mezi mnoˇ zinami Definice 3.10. (Tot´ aln´ı) funkce z mnoˇziny A do mnoˇziny B je relace f mezi A a B takov´ a, ˇze pro kaˇzd´e x ∈ A existuje pr´avˇe jedno y ∈ B takov´e, ˇze (x, y) ∈ f .2 Mnoˇzina A se naz´yv´a definiˇcn´ı obor a mnoˇzina B obor hodnot funkce f .
Neform´alnˇe ˇreˇceno, ve funkci f je kaˇzd´e vstupn´ı“ hodnotˇe x pˇriˇrazena jednoznaˇcnˇe ” v´ystupn´ı“ hodnota y. ” (V obecn´e relaci poˇcty pˇriˇrazen´ych“ dvojic neomezujeme. . . ) 2 ”
Znaˇ cen´ı: M´ısto (x, y) ∈ f p´ıˇseme obvykle f (x) = y.
Z´ apis f : A → B ˇr´ık´a, ˇze f je funkce s def. oborem A a oborem hodnot B.2 Funkc´ım se tak´e ˇr´ık´a zobrazen´ı.
N N
• Definujeme funkci f : → pˇredpisem f (x) = x+8. Tj. f = {(x, x+8) | x ∈ }.2 • Definujeme funkci plus : × → pˇredpisem plus(i, j) = i + j. Tj. plus = {(i, j, i + j) | i, j ∈ }.
N
Petr Hlinˇ en´ y, FI MU Brno
N N N N 16
FI: IB000: Mnoˇ ziny, Relace a Funkce
Definice: Pokud naˇs´ı definici funkce uprav´ıme tak, ˇze poˇzadujeme pro kaˇzd´e x ∈ A nejv´yˇse jedno y ∈ B takov´e, ˇze (x, y) ∈ f , obdrˇz´ıme definici parci´aln´ı funkce z A do B.2 V parci´aln´ı funkci p nemus´ı b´yt pro nˇekter´e vstupn´ı“ hodnoty x funkˇcn´ı hodnota ” definov´ana.
Pro nedefinovanou hodnotu pouˇz´ıv´ ame znak ⊥. Dalˇs´ı pˇr´ıklady funkc´ı. • Definujeme parci´aln´ı funkci f : → 3+x f (x) = ⊥
2
Z N pˇredpisem jestliˇze x ≥ 0, jinak.
N
Tj. f = {(x, 3 + x) | x ∈ }. 2 • Tak´e funkce f : → dan´ a bˇeˇzn´ym analytick´ym pˇredpisem √ f (x) = x
R R
je jen parci´aln´ı – nen´ı definov´ ana pro x < 0.2 ˇ jejich rodn´ • Co je relace, pˇriˇrazuj´ıc´ı lidem v CR a ˇc´ısla? Petr Hlinˇ en´ y, FI MU Brno
17
FI: IB000: Mnoˇ ziny, Relace a Funkce
3.5
Posloupnosti a rekurentn´ı vztahy
Definice: Funkce p :
N → R se naz´yv´a posloupnost.
Mimo funkˇcn´ıho“ z´apisu p(n) ˇcasto pouˇz´ıv´ ame indexovou“ formu z´apisu pn2. ” ” Pozn´ amka: Obor hodnot posloupnosti m˚ uˇze b´yt i jin´y neˇz re´aln´a ˇc´ısla. Na posloupnost se tak´e d´ıv´ame jako na seˇrazen´ı“ vybran´ych prvk˚ u z oboru hodnot, s povolen´ym ” opakov´an´ım hodnot (nemus´ı b´yt prost´a). 2 Tak´e def. obor posl. m˚ uˇze zaˇc´ınat od nuly nebo i od jedniˇcky, jak je v aplikac´ıch potˇreba.
• Pˇr´ıklady posloupnost´ı:
∗ p0 = 0, p1 = 2, . . . , pi = 2i, . . . je posloupnost sud´ych nez´aporn´ych ˇc´ısel.2 ∗ 3, 3.1, 3.14, 3.141, . . . je posloupnost postupn´ych dekadick´ych rozvoj˚ u π. ∗ 1, −1, 1, −1, . . . je posloupnost urˇcen´a vztahem pi = (−1)i , i ≥ 0.
2
∗ Pokud chceme stejnou posloupnost 1, −1, 1, −1, . . . zadat jako qi , i ≥ 1, tak ji urˇc´ıme vzorcem qi = (−1)i−1 . 2
• Posloupnost je rostouc´ı (ˇci klesaj´ıc´ı), pokud pn+1 > pn ( pn+1 < pn ) pro vˇsechna n. Petr Hlinˇ en´ y, FI MU Brno
18
FI: IB000: Mnoˇ ziny, Relace a Funkce
Rekurentn´ı definice posloupnosti Slovem rekurentn´ı oznaˇcujeme takov´e definice (ˇci popisy), kter´e se v jist´ych bodech odvol´avaj´ı samy na sebe. (Uˇz jste se setkali s rekurz´ı“ pˇri programov´ an´ı? A v´ıte, co znamen´a?) ” Uk´azky rekurentn´ıch vztah˚ u:
2
• Zad´ame-li posloupnost pn vztahy p0 = 1 a pn = 2pn−1 pro n > 0, pak plat´ı pn = 2n pro vˇsechna n. 2 • Obdobnˇe m˚ uˇzeme zadat posloupnost qn vztahy q1 = 1 a qn = qn−1 + n pro n > 1. Potom plat´ı qn = 21 n(n + 1) pro vˇsechna n. Umˇeli byste toto dok´ azat indukc´ı? 2 • Zn´am´a Fibonacciho posloupnost je zadan´ a vztahy f1 = f2 = 1 a fn = fn−1 + fn−2 pro n > 2.
Petr Hlinˇ en´ y, FI MU Brno
19
FI: IB000: Mnoˇ ziny, Relace a Funkce
Pˇr´ıklad 3.11. Posloupnost f je zadan´ a rekurentn´ı definic´ı f (0) = 3
a
f (n + 1) = 2 · f (n) + 1
pro vˇsechna pˇrirozen´a n. Urˇcete hodnotu f (n) vzorcem v z´avislosti na n.
2
ˇ sen´ı: V prvn´ı f´azi ˇreˇsen´ı takov´eho pˇr´ıkladu mus´ıme nˇejak uhodnout“ hledan´y Reˇ ” vzorec pro f (n). Jak? Zkus´ıme vypoˇc´ıtat nˇekolik prvn´ıch hodnot a uvid´ıme. . . f (1) = 2 · f (0) + 1 = 2 · 3 + 1 = 7
f (2) = 2 · f (1) + 1 = 2 · 7 + 1 = 15
f (3) = 2 · f (2) + 1 = 2 · 15 + 1 = 31
f (4) = 2 · f (3) + 1 = 2 · 31 + 1 = 632 Nepˇripom´ınaj´ı n´am tato ˇc´ısla nˇeco? Co tˇreba posloupnost 8 − 1, 16 − 1, 32 − 1, 64 − 1. . . ? Bystr´emu ˇcten´ aˇri se jiˇz asi podaˇrilo uhodnout, ˇze p˚ ujde o mocniny n+2 − 1. 2 dvou sn´ıˇzen´e o 1. Pˇresnˇeji, f (n) = 2 Ve druh´e nesm´ıme ale zapomenout spr´ avnost naˇseho vˇeˇstˇen´ı“ dok´azat, nejl´epe ” matematickou indukc´ı podle n. 2 Petr Hlinˇ en´ y, FI MU Brno
20
FI: IB000: Mnoˇ ziny, Relace a Funkce
