Matematika pro informatiku 4

Matematika pro informatiku 4 Doc. RNDr. Alena Šolcová, Ph. D., KTI FIT ČVUT v Praze 7.března 2011 Evropský sociální fond Investujeme do vaší budoucnosti Alena Šolcová

Lámejte si hlavu - L1 • Určete všechny podgrupy v grupě zadané Cayleyho tabulkou: x

x x

y y

z z

y

y

z

x

z

z

x

y

• Odpovědi zasílejte na adresu: [email protected]. Do předmětu zprávy: Jméno, číslo skupiny, L1 2.12.2011

Alena Šolcová, FIT CVUT v Praze

2

Lámejte si hlavu L2 1. Ověřte, zda dané zobrazení je homomorfismus: : (Z, +) (R, +), n = 2n + 1 2. Najděte všechna řešení kongruence 27x + 24 50x + 8 (mod 7) Odpovědi zasílejte na [email protected] Subjekt: Jméno, číslo skupiny, L2 2.12.2011


3

Zbytkové třídy podle modulu n Definice: • Podmnožiny v Z skládající se právě ze všech čísel, která při dělení číslem n mají stejný zbytek , nazveme zbytkové třídy podle modulu n . • Množina zbytkových tříd podle modulu n je rozkladem množiny Z. Třídy jsou disjunktní a jejich počet je n. Každá zbytková třída podle modulu n je úplně určena libovolným svým prvkem. • Různé zbytkové třídy nemohou mít žádné společné prvky. Vysvětlete! 2.12.2011


4

Příklad: Všechny zbytkové třídy mod 5 0= 1= 2= 3= 4=

2.12.2011

{…, -15, -10, -5, 0, 5, 10, 15, …} {…, -14, -9, -4, 1, 6, 11, 16, …} {…, -13, -8, -3, 2, 7, 12, 17, …} {…, -12, -7, -2, 3, 8, 13, 18, …} {…, -11, -6, -1, 4, 9, 14, 19, …} Z5 = {0, 1, 2, 3, 4} Alena Šolcová, FIT CVUT v Praze

5

Skládání kongruencí Věta: Platí-li a a1 (mod n), b b1 (mod n), potom 1. a + b a1 + b1 (mod n) 2. a . b a1 . b1 (mod n) Sečteme-li dvě čísla z některých zbytkových tříd podle modulu n, pak výsledek patří do některé zbytkové třídy podle modulu n. Sečteme-li však další dvě čísla, z těchto zbytkových tříd, patří jejich součet opět do stejné třídy, jako patřil součet původních čísel. 2.12.2011


6

Sčítání zbytkových tříd • Jsou-li a, b dvě zbytkové třídy z množiny Zn , pak třídu a + b nazveme součtem tříd a, b a píšeme a + b = a + b . • Příklad: Z5 = {0, 1, 2, 3, 4} je množina zbytkových tříd podle modulu 5. Potom 1 + 3 = 4, 2 + 3 = 0, …

2.12.2011


7

Součin zbytkových tříd • Jsou-li a, b zbytkové třídy z množiny Zn, pak třídu ab nazýváme součin zbytkových tříd a, b a píšeme ab = a . b Příklad: Pro třídy ze Z5 platí např. 2 . 1 = 2 3.4=2

2.12.2011


8

Vlastnosti operací na zbytkových třídách Věta: Je-li n libovolné přirozené číslo a Zn množina zbytkových tříd podle modulu n, pak (Zn, +) je konečná abelovská grupa řádu n. Třída 0 je neutrální prvek . Třída opačná k a = n – a = -a … inverzní prvek „.“

Násobení zbytkových tříd – složitější: Věta: Nechť n > 1 je přirozené číslo. Pak násobení „.“ zbytkových tříd podle modulu n je asociativní a komutativní operace na Zn. Přitom v Zn existuje neutrální prvek vzhledem k „.“, který je roven třídě 1 . Pro třídu 0 neexistuje inverzní prvek. Není grupa! 2.12.2011


9

(Zn \ {0}) a operace násobení Věta: Je-li n > 1 přirozené číslo, pak ((Zn \ {0}), .) je grupa (abelovská), právě tehdy, když n je prvočíslo. Tabulky pro násobení podle modulů 4 a 5 1

2

1

1

2

3

2

2

0

2

3

3

2

1

2.12.2011

1

2

3

4

1

1

2

3

4

2

2

4

1

3

3

3

1

4

2

4

4

3

2

1

3


10

Čínská věta o zbytcích • Řešení soustavy lineárních kongruencí jedné proměnné bylo známo již ve staré Číně, Indii a Řecku Příklad Mistra Suna (mezi 287-473): • Najdi číslo, které při dělení třemi dá zbytek 1, při dělení dvěma dá zbytek 5 a při dělení třemi dá zbytek 7. • Převedeme-li do jazyka kongruencí: x

1 (mod 3 ), x

2.12.2011

2 (mod 5 ), x Alena Šolcová, FIT CVUT v Praze

3 (mod 7 ) 11

Algebra a algoritmy Algoritmy pro výpočet kořenů polynomů – Bolzanova věta Metoda půlení intervalů Newtonova metoda Generátory pseudonáhodných čísel Eukleidovy algoritmy

2.12.2011


12

Slovo algoritmus • Abu Abd Allah Muhammad ibn Musa alChwarismi (asi 825) - algoritmus • Otec Abdulláha, Mohammeda, syn Mojžíšův, narozený v Chorezmu (povodí řeky Abu –Darji) • Kitab al-jabr wa’l-muqabala • Pravidla pro odvozování a srovnávání

2.12.2011


13

Literatura • Heinz Zemanek: Lecture notes in Computer Science 122 (1981), 1-81. • Donald E. Knuth: Umění programování, Computer Press, Brno 2008 (1997 in English The Art of Computer Programming)

2.12.2011


14

Algoritmus E • Eukleidův algoritmus Jsou-li dána dvě kladná celá čísla m a n, nalezněte jejich největšího společného dělitele, tedy největší kladné celé číslo, kterým jsou beze zbytku dělitelná m i n.

• E1. (Nalezení zbytku) Vydělte m číslem n a nechť r je zbytek, 0 ≤ r < n. • E2. (Je zbytek roven nule?) Pokud r = 0, algoritmus končí a n je odpověď • E3. (Redukce) Přiřaďte m← n, n← r a vraťte se do kroku E1. 2.12.2011


15

Algoritmus E

Nalezení zbytku

2.12.2011

Je zbytek roven nule?


Redukce

16

Algoritmus A1 Modernější Eukleidův algoritmus Jsou-li dána nezáporná celá čísla u a v, pak tento algoritmus nalezne jejich největšího společného dělitele. Pokud algoritmus aplikujeme na Abs(u) a Abs(v), nalezne NSD libovolných dvou celých čísel u a v. A1. v = 0? Je-li v = 0, algoritmus končí a vydá v jako odpověď. A2. Výpočet u mov v Přiřaďte r ← u mod v, u← v, v←r a vraťte se na krok A1. Operacemi v tomto kroku se sníží hodnota v, avšak NSD(u,v) zůstane beze změny. 2.12.2011


17

Příklad na použití algoritmu A • Určete NSD (40902, 24140): • NSD (40902, 24140) = NSD (24140, 16762) = = NSD (16762, 7378) = NSD (7378, 2006) = = NSD (2006, 1360) = NSD (1360, 646) = = NSD (646, 68) = NSD (68, 34) = NSD (34, 0) = = 34 Správnost použití algoritmu plyne z ekvivalence NSD (u, v) = NSD (v, u – qv) pro lib. celé q 2.12.2011


18

Bolzanova věta o překročení řeky Nechť f je spojitá funkce na intervalu a nechť platí f (a) . f (b) < 0. Potom existuje bod x v intervalu (a, b), pro který je f (x) = 0.

2.12.2011


19

Metoda půlení intervalů • Metoda půlení intervalu je numerická metoda , která slouží k přibližnému určení kořene rovnice ve tvaru f(x)= 0. Předpoklady: f(x) je spojitá na < a , b > f(a) má opačné znaménko než f(b)

Přesnost je určena velikostí intervalu,v němž se bude nacházet skutečná hodnota kořene.

2.12.2011


20

Metoda půlení intervalu – příklad Hledáme nulový bod funkce f(x) = x2 – 2 Jako výchozí interval zvolíme <0,2> Platí: f(0) = –2<0, f(2) = 2>0. Střed intervalu: 1 ... f(1)= –1 f(1)<0, tedy nahradíme levý krajní bod středem, tj. bodem 1 a1 = 1 b1 = 2 … f(1.5) = 0.25 >0 a2 = 1 b2 = 1.5 … f(1.25) = -0.4375 < 0 a3 = 1.25 b3 = 1.5 … f(1.375) = -0.1093… < 0 a4 = 1.375 b4 = 1.5 … f(1.4375) = 0.0664… > 0 a5 = 1.375 b5 = 1.4375 … f(1.40625) = -0.0224… < 0 a6 = 1.40625 b6 = 1.4375 … f(1.421875) = 0.0217… > 0 a7 = 1.40625 b7 = 1.421875 … f(1.4140625) = -0.0004…<0 Kořen leží v intervalu <1.40625, 1.421875>, střed intervalu: 1.4140625, správná hodnota 1.4142135… 2.12.2011


21

Newtonova metoda •

Jeden krok metody tečen při hledání řešení f(x) = 0. xn představuje původní odhad, v bodě f(xn) je sestrojena tečna ke křivce f(x). V místě, kde tečna protíná osu x, se nachází nový odhad xn + 1.

•

Metoda tečen je iterační numerická metoda žívaná v numerické matematice k numerickému řešení soustav nelineárních rovnic. Nazývá se také Newtonova metoda (nebo Newton-Raphsonova metoda) a metodou tečen je označována, protože přesnější aproximace řešení rovnice f(x) = 0 se hledá ve směru tečny funkce f(x).

2.12.2011


22

Popis algoritmu • Newtonova metoda tečen slouží k nalezení řešení rovnice f(x) = 0 za předpokladu, že známe derivaci funkce f'(x), tedy směrnici tečny. Pro jednoduchost dále předpokládejme, že x i f(x) jsou skaláry.

• Dalším nezbytným předpokladem je znalost počáteční hodnoty x0, v jejíž blízkosti hledáme řešení. Pokud se funkce f(x) chová rozumně (je spojitá, hladká a monotónní v intervalu, ve kterém hledáme řešení), lze očekávat řešení v místě, kde tečna sestrojená z bodu f(x0) protíná osu x. • (Směrnice této tečny je f'(x0).) Tento průsečík označíme x1 a vypočteme jej podle následujícího vztahu. • Za splnění výše uvedených předpokladů by měla hodnota f(x1) být blíže nule než původní f(x0). Stejný postup můžeme opakovat a najít tak ještě přesnější hodnotu xk. • Iteraci provádíme tak dlouho, dokud hodnota f(xk) neleží dostatečně blízko nuly. 2.12.2011


23

Popis algoritmu II • Nechť f(x0) = y0 a je známa derivace f’ (x0) = k. • Nahradíme funkci Taylorovým polynomem 1. stupně: f (x) = y0 + k (x-x0) • Hledáme nulový bod: Řešíme lineární rovnici pro neznámou x 0 = y0 + k (x – x0) kx = kx0 – y0 x = x0 – y0 /k • Vzorec pro další iteraci tedy je xk+1 = xk – f(xk) / f’ (xk), k=0,1,2,… 2.12.2011


24

Příklad: Výpočet druhé odmocniny Úkolem je vypočítat druhou odmocninu kladného reálného čísla a. Problém lze definovat také jako nalezení kořenu funkce f(x) = x2 − a, neboli řešení rovnice f(x) = 0. • Vypočteme derivaci f'(x). f'(x) = 2x Dosadíme do obecného vzorce a upravíme.

• Získáváme tak rekurentní rovnici, u které jako počáteční podmínku můžeme zvolit x0 = a.

2.12.2011


25

Ukázka výpočtu , neboli x2 − 9 = 0, metodou tečen. Výpočet (druhé odmocniny z devíti) bude podle výše uvedeného algoritmu probíhat následovně. • a=9 • • • • • •

x0 = 9 x1 = 5 x2 = 3.4 x3 = 3.02352941176471 x4 = 3.00009155413138 x5 = 3.00000000139698 x6 = 3.00000000000000

• x7 = 3.00000000000000

• Je vidět, že po několika málo krocích se hodnota xk nemění a ustálí se (konverguje) na hodnotě 3, což odpovídá správnému výsledku. 2.12.2011


26

Poznámka 1 Aproximace derivace • Pokud známe pouze funkci f(x) a neznáme její derivaci f'(x), můžeme se pokusit derivaci nahradit numerickou derivací. • Případně je možné řešit úlohu metodou sečen, která znalost derivace nevyžaduje. • Rychlost konvergence Newtonovy metody je kvadratická, tj. s každým krokem se počet správných číslic přibližně zdvojnásobí. • Pro nevhodné počáteční podmínky nemusí Newtonova metoda konvergovat. • Jestliže funkce není hladká, je lepší použít metodu půlení intervalu, která konverguje vždy. 2.12.2011


27

Poznámka 2 - Vektory • Je-li funkce f(x) skalární funkcí vektorového argumentu („z vektoru vypočte skalár“), je nutné hledat xk+1 proti směru gradientu. Předpis pro iteraci lze potom napsat takto:

• Pokud je funkce f(x) vektorovou funkcí vektorového argumentu („z vektoru vypočte vektor“), lze předpis pro iteraci napsat takto:

2.12.2011


28

Jacobiho matice • Matice J je takzvaná Jacobiho matice (a její determinant jakobián) obsahující parciální derivace.

2.12.2011


29

Algoritmus pro generování náhodných čísel • Čísla, která vybíráme náhodně jsou užitečná v řadě aplikací: A. Simulace B. Vzorkování C. Numerická analýza D. Programování počítačů E. Rozhodování F. Kryptografie G. Estetika 2.12.2011


30

Návrh Johna von Neumanna • 1946 – použít čtverec předchozího náhodného čísla a vzít z něho prostřední číslice. • Př. 5772156649 – 10-ciferná čísla • 33317792380594909201 • Námitka: Jak může být posloupnost cifer náhodná, když je plně určena svým předchůdcem?

2.12.2011


31

Generátor K – Knuth 1959 – Generátor supernáhodných čísel • K1. Výběr počtu iterací Přiřaďte Y ← X/109 • K2. Výběr náhodného kroku Přiřaďte Z ← (X/108) mod 10 Přejděte na K(3 + Z) • K3. Zajištění 5 x 109 Je-li X < 5000000000, přiřaďte X ← X + 5000000000 • K4. Prostředek čtverce Nahraďte X za (X2/105) mod 10 • K5. Násobení Nahraďte X za (1001001001) mod 1010 • K6. Pseudokomplement Jestliže X < 100000000, pak přiřaďte X ← X + 9814055677, jinak přiřaďte X ← 1010 - X 2.12.2011


32

Generátor K • K7. Výměna polovin Prohoďte nižších 5 číslic čísla X s vyššími pěti číslicemi • K8. Násobení Proveďte totéž co v K5. • K9. Zmenšení číslic Zmenšete každou nenulovou číslici v desítkové reprezentaci čísla X o 1. • K10. Úprava o 99 999 Je-li X < 105, přiřaďte X ← X2 + 99999, jinak přiřaďte X ← X - 99999 • K11. Normalizace (Nyní nemůže být X = 0.) Je-li X < 109, přiřaďte X ← 10 X a opakujte tento krok. • K12. Upravený prostředek čtverce Nahraďte X za (X(X - 1)/105) mod1010 . • K13. Opakovat? Je-li Y> 0 , zmenšete Y o 1 a vraaťte se na krok K2. Je-li Y = 0, algoritmus končí a X je „náhodná hodnota“.

2.12.2011


33

Generátor K • Nevydává nekonečně mnoho náhodných čísel. • Za určitých podmínek konverguje. • Zkuste aplikovat K na X = 3830941686 • Náhodná čísla nelze generovat náhodně zvolenou metodou, lépe je podpořit výpočet teorií. • K je pro procvičení, existují lepší generátory, např. lineární kongruentní posloupnosti. 2.12.2011


34

Lámejte si hlavu – H5 • Dejme tomu, že potřebujete náhodně zvolit nějakou desítkovou číslici, ale bez počítače, která z metod je vhodná a proč? • A)Podíváte se na náramkové hodinky, a pokud se sekundová ručička nachází v poloze mezi 6n a 6(n+1) sekundami, zvolíte číslici n. • B) Požádáte přítele, aby si myslel náhodné číslo, a vezmete číslici, kterou vám navrhne. 2.12.2011


35

Matematika pro informatiku 4

Recommend Documents