Matematika pro informatiku 10

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

Vybrané problémy teorie čísel Prvočísla a jejich rozmístění Goldbachova hypotéza. Číselně teoretické funkce. Základní vlastnosti kongruencí. Čínská věta o zbytcích. Kvadratická kongruence. Gaussovy algoritmy. Výpočet kalendáře.

1.11.2011

Alena Šolcová, FIT CVUT v Praze

2

Prvočísla a jejich rozmístění • • • •

(Primes and their distribution) Prvočísla (Primes) Základní věta aritmetiky (Fundamental Theorem of Arithmetic) Eratosthenovo síto (The Sieve of Eratosthenes) Goldbachova hypotéza (The Goldbach Conjecture)

1.11.2011


3

Základní věta aritmetiky Každé kladné celé číslo n > 1 může být vyjádřeno jako součin prvočísel. Tento rozklad je jednoznačný. • Důsledek: Kladné celé číslo n > 1 může být vyjádřeno v kanonickém tvaru jediným způsobem n = p1k1 p2k2 …prkr , kde každé ki je kladné celé číslo pro i = 1, 2, …, r a každé pi je prvočíslo takové, že p1 < p2 < …< pr 1.11.2011


4

Příklady • 360 = 23 32 5 • 4725 = 33 52 7 • 17640 = 23 32 5 72 • • • •

65536 = 216 143 = 11 . 13 1679 = 23 . 73 1271 = 31 . 41

1.11.2011


5

Testování prvočíselnosti Je-li a složené celé číslo, pak můžeme psát a = b.c, kde 1 < b < a a 1 < c < a . Předpokládame-li, že b ≤ c, dostaneme b2 ≤ bc = a, a dále b ≤ √a. Protože b > 1, má b podle ZVA nejméně jednoho prvočíselného dělitele p. Pak platí p ≤ b ≤ √a, dále p|b a b|a p|a. Složené číslo a má vždy prvočíselného dělitele p ≤ √a, odtud plyne: stačí testovat čísla menší než √a nebo rovna √a. 1.11.2011


6

Testování prvočíselnosti - příklady Příklad: a = 509 22 < √509 < 23 Otestujeme jako možné dělitele prvočísla menší než 22, tj. { 2, 3, 5, 7, 11, 13, 17, 19}. Protože žádné z nich není dělitel 509, musí být dané a prvočíslo.

1.11.2011


7

Testování prvočíselnosti - příklady Příklad : a = 2093 45 < √2093 < 46 Otestujeme jako možné dělitele prvočísla menší než 22, tj. { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}. První dělitel 2093 je 7: 2093 = 7 . 299 17 < √299 < 18, testujeme ,2, 3, 5, 7, 11, 13První dělitel 299 je 13: 299 = 13 . 23. 23 je též prvočíslo. Rozklad čísla je 2093 = 7 . 13 . 23. 1.11.2011


8

Eratosthenovo síto

1.11.2011

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100


9

Čísla dělitelná dvěma, třemi a pěti

1.11.2011


10

Ératosthenés z Kyrény • 276 – 194 př. n. l. • Žil v Alexandrii. • Přezdívka „Beta“ • • • •

Vyměřil obvod Země Přítel Archimédův Je po něm pojmenován kráter na Měsíci. Ératosthenovo síto v XI. knize Eukleidových Základů • Otázka: Existuje největší prvočíslo? 1.11.2011


11

Obvod Země

1.11.2011


12

Eukleidova věta – The Euclid Theorem • Věta: Počet všech prvočísel je nekonečný. Důkaz: Eukleidés postupuje sporem. Nechť existuje rostoucí posloupnost prvočísel p1 = 2, p2 = 3, p3 = 5, p4 = 7 … a pn je poslední z nich. Uvažujme P = p1 p2 … pn + 1. Protože P > 1 podle ZVA je P dělitelné nějakým prvočíslem. 1.11.2011


13

Důkaz Eukleidovy věty • p1 p2 … pn jsou jediná prvočísla menší než P, proto další prvočíslo p se musí rovnat jednomu z nich. • Když spojíme dělitelnost p|p1 p2 … pn a p|P, dostaneme p|P - p1 p2 … pn, ekvivalentně p|1 . • Jediný kladný dělitel čísla 1 je 1, ale p > 1, tj. spor! • Žádný konečný seznam prvočísel není úplný, počet prvočísel je nekonečný. The number of primes is infinite. Eukleidova čísla (Euclid Numbers) jsou čísla tvaru p1 p2 … pn + 1, mezi nimi je asi 19 prvočísel. 1.11.2011


14

Goldbachova hypotéza • Rozmístění prvočísel (Prime Distribution) mezi čísly složenými – neznáme odpověď. • Prvočíselná dvojčata (Prime Twins): dvojice lichých čísel (p, p + 2) - 11 a 13, 17 a 19 nebo 1000000000061 a 1000000000063. Intervaly mezi prvočísly jsou libovolně dlouhé. Nejdelší mezera má 1132 složených čísel. Otázka: Je počet prvočíselných dvojčat konečný? 1.11.2011


15

Goldbachova hypotéza • 1742 píše Christian Goldbach Leonhardu Eulerovi: Každé sudé číslo může být vyjádřeno součtem dvou čísel, jež jsou prvočísla nebo jedničky. • Prověřeno do 4 . 1014 • Ukážeme si rozklady do 30: 1.11.2011


16

Goldbachovy rozklady 2 = 4 = 6 = 8 = 10 = 12 = 14 = 16 = 18 = 20 = 22 = 24 = 26 = 28 = 30 = 1.11.2011

1+1 2+2 3+3 3+5 3+7 5+7 3 + 11 3 + 13 5 + 13 3 + 17 3 + 19 5 + 19 3 + 23 5 + 23 7 + 23

= = = = = = = = = = = = = =

1+ 3 1+ 5 1+ 7 5+ 5 1 + 11 7+ 7 5 + 11 7 + 11 7 + 13 5 + 17 7 + 17 7 + 19 11 + 17 11 + 19

=

1 + 13

= = = = =

1 1 11 11 13

=

13 + 17

+ + + + +

17 19 11 13 13


= 1 + 24

=

1 + 29 17

Lámejte si hlavu – L101 • Použijte Ératosthenova síta k rozkladu čísla 94 na součet dvou prvočísel. • Kolik takových rozkladů existuje?

1.11.2011


18

Goldbachova hypotéza • Euler omezil hypotézu takto: Libovolné sudé číslo (≥ 6) tvaru 4n + 2 je součet dvou čísel, jež jsou prvočísla tvaru 4n + 1 nebo 1. Lze ukázat: Každé sudé číslo je součtem 6 nebo méně prvočísel. Lemma: Součin dvou nebo více čísel tvaru 4n + 1 je též tvaru 4n + 1. Dokažte si samostatně. Věta: Počet prvočísel tvaru 4n + 3 je nekonečný. Důkaz sporem. 1.11.2011


19

Dirichletova věta • Věta: Jestliže a a b jsou vzájemně nesoudělná čísla, pak aritmetická posloupnost a, a + b, a + 2b, a + 3b … obsahuje nekonečně mnoho prvočísel. Dirichlet zjistil např. , že je nekonečně mnoho prvočísel končících na 999: 1999, 100999, 1000999, … . Tato aritmetická posloupnost je určena tvarem 1000k + 999 a nsd(1000, 999) =1 1.11.2011


20

Čemu se dlouho věřilo? • Euler se také někdy mýlil. V roce 1772 ukázal, že kvadratický polynom • f(n) = n2 + n + 41 dává pouze prvočíselné hodnoty. Prověřil pouze tyto hodnoty ,0, 1, 2, …, 39-. Použil metodu neúplné indukce. f(40) = 402 + 40 + 41 = 40(40 + 1) + 41 = 40 . 41 + 41 = 41 (40 + 1) = 412 složené číslo f(41) = 412 + 41 + 41 = 41 (41 + 1 + 1) = 41 . 43 f(42) = 422 + 42 + 41 = 1847 opět dává prvočíslo. 1.11.2011


21

Číselně teoretické funkce •

• • • •

(Number-Theoretic Functions) Součet a počet dělitelů (The Sum and Number of Divisiors) Möbiova funkce (The Möbius inversion formula) Celá část čísla (The Greatest Integer Function) Eulerova funkce (Euler’s Phi-Function) August Ferdinand Möbius, Leonhard Euler

1.11.2011


22

Součet a počet dělitelů Definice: Je dáno kladné celé číslo n, označíme τ (n) počet kladných dělitelů čísla n a σ(n) součet těchto dělitelů. Příklad: n = 12. Má tyto kladné dělitele {1, 2, 3, 4, 6, 12}, tedy τ (12) = 6, σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 Určete funkce τ (n) a σ(n) pro prvních několik n. 1.11.2011


23

Součet a počet dělitelů • Věta: τ (n) = 2 právě tehdy, když n je prvočíslo. • Věta: σ(n) = n + 1 právě tehdy, když n je prvočíslo. • Obě funkce jsou multiplikativní, tj. τ (mn) = τ (m) τ (n) σ(mn) = σ(m) σ(n), pro libovolná vzájemně nesoudělná m, n. 1.11.2011


24

Möbiova funkce • August Ferdinand Möbius • Definice: Pro kladné celé číslo n definujeme 1 je-li n = 1 0 funkci μ (n) =

je-li p2|n pro nějaké

prvočíslo p (-1)r je-li n = p1 p2 … pr , kde pi jsou různá prvočísla.

1.11.2011


25

Vlastnosti Möbiovy funkce Příklad: μ(30) = μ (2 . 3 . 5) = (-1)3 = -1 μ(1) = 1, μ(2) = -1, μ(3) = -1, μ(4) = 0, μ(5) = -1, μ(6) = 1.

Věta: Funkce μ je multiplikativní funkce. Zkuste samostatně dokázat. Aplikace najdeme v teorii čísel, kombinatorice, fyzice apod. 1.11.2011


26

Funkce “celá část čísla“ The Greatest Integer Function, „Bracket“ Function Definice: Pro libovolné reálné číslo x , označíme [x] nejbližší celé číslo menší než x, tedy x splňuje podmínku x – 1 < [x] < x. Příklady: [-3/2] = -2, *√2+ = 1, *1/3+ = 0, [π] = 3 [-π] = 4 Věta: [x] = x právě tehdy, když x je celé číslo. Libovolné reálné číslo lze zapsat ve tvaru x = [x] + θ, kde 0 ≤ θ < 1. 1.11.2011


27

Eulerova funkce (Euler’s Phi-Function) Definice: Pro n 1 (n) označuje počet kladných celých čísel nesoudělných s n a menších nebo rovných než n. Příklad: (30) = 8 {1, 7, 11, 13, 17, 19, 23, 29}, (1) = 1, (2) = 1, (3) = 2, (4) = 2, (5) = 4, (6) = 2, (7) = 6 1.11.2011


28

Některé vlastnosti funkce Věta: Je-li n prvočíslo, pak každé celé číslo menší než n je nesoudělné s n, tedy (n) = n – 1 Věta: Je-li n > 1 složené, pak má n dělitele d takové, že jsou v intervalu 1 < d < n. To znamená, že nejméně dvě čísla mezi 1, 2, 3, …, n nejsou soudělná s n, totiž d a n, tj. (n) ≤ n – 2 1.11.2011


29

Některé vlastnosti funkce Věta: Jestliže p je prvočíslo a k > 0, pak (pk) = pk- pk – 1= pk (1 – 1/p) Příklad: (9) = (32) = 32 – 3 = 6 {1, 2, 4, 5, 7, 8} (16) = (24) = 24 – 23 = 16 – 8 = 8 {1, 3, 5, 7, 9, 11, 13, 15} Věta: Funkce je multiplikativní, tj. (m.n)= (m) . (n), kde m a n jsou nesoudělná. 1.11.2011


30 =

Gaussova věta Pro každé kladné celé číslo n ≤ 1 platí n = ∑d|n (d) (sčítá se přes všechny kladné dělitele d čísla n).

1.11.2011


31

Příklad • Nechť je n = 10. • Čísla mezi 0 a n rozdělíme do tříd podle d. Je-li d kladný dělitel čísla n, uložíme celé číslo m mezi prvky třídy Sd, jestliže platí nsd(m,n) = d Sd = {m|nsd (m,n) = d, 1 ≤ m ≤ n}. S1 = {1, 3, 7, 9} S2 = {2, 4, 6, 8} S5 = {5} S10 = {10} (10) = 4, (5) = 4, (2) = 1, (1) = 1 ∑d|10 (d) = (10) + (5) + (2) + (1) = 4 + 4 + 1 + 1 = 10 1.11.2011


32

Teorie kongruencí • • • • •

(The Theory of Congruences) Carl Friedrich Gauss Základní vlastnosti kongruencí Lineární kongruence Čínská věta o zbytcích Kvadratická kongruence ¨

1.11.2011


33

Základní vlastnosti kongruencí Definice: Nechť n je kladné celé číslo. Dvě čísla a a b jsou kongruentní podle modulu n a b (mod n), jestliže n dělí rozdíl a – b, tedy a – b = kn pro k celé. Kongruence je zobecněná forma ekvivalence. Věta: Nechť n > 1, a,b, c, d jsou libovolná celá čísla. Pak platí a) a a (mod n) b) Je-li a b (mod n), pak b a (mod n) 1.11.2011


34

Základní vlastnosti kongruencí Věta: c) Je-li a

b (mod n) a b

c (mod n), pak a

c (mod n).

d) a

b (mod n) a c d (mod n), pak a + b c + d (mod n) a ac bd (mod n). e) Je-li a b (mod n), pak a + c b + c (mod n) a ac bc (mod n). f) Je-li a b (mod n), pak ak bk (mod n), pro libovolné kladné k. 1.11.2011


35

Příklad - kongruence • Ukažte, že 41 dělí 2020 – 1 • Začneme tím, že 25 -9 (mod 41), jinak také 220 81 . 81 (mod 41) Ale 81 -1 (mod 41), a tedy 81. 81 1 (mod 41). Podle vlastností kongruence pokračujeme: 220 -1 81 . 81 - 1 1 – 1 0 (mod 41), tedy 41 dělí 2020 – 1. 1.11.2011


36

Příklad - kongruence • Chceme najít zbytek po dělení součtu 1! + 2! + 3! + 4! + … + 99! + 100! číslem 12. • Zahájíme zjištěním, že 4! 24 (mod 12), takže Pro k ≥ 4 platí k! 4! + 5 . 6 … k 0 . 5 . 6 … k 0 (mod 12) Takto dostaneme 1! + 2! + 3! + 4! + … + 99! + 100! 1! + 2! + 3! + 0 + … + 0 9 (mod 12) Odtud součet dává zbytek 9 při dělení 12. 1.11.2011


37

Další vlastnosti • Věta: Je-li ca cb (mod n), pak a c (mod n/d), kde d = nsd (c,n). • Důsledek: Je-li ca cb (mod n) a nsd(c,n) = 1, pak a b (mod n). • Důsledek: Je-li ca cb (mod p), a p nedělí c, kde p je prvočíslo, pak a b (mod p). Důkaz: Podmínky: p nedělí c a p je prvočíslo implikují nsd(c, p) = 1. 1.11.2011


38

Příklady • Uvažujme o kongruenci 33 15 (mod 9), tj. 3. 11 3 . 5 (mod 9). Protože nsd (3, 9) = 3 podle předcházející věty můžeme psát 11 5 (mod 3). • Jinou kongruenci -35 45 (mod 8) můžeme rozložit stejným způsobem na 5 (-7) 5. 9 (mod 8). Čísla 5 a 8 jsou nesoudělná, proto upravíme na -7 9 (mod 8). 1.11.2011


39

Čínská věta o zbytcích The Chinese Remainder Theorem

Věta: Nechť n1, n2, …, nr kladná celá čísla taková, že nsd (ni, nj) = 1 pro i ≠ j. Pak soustava lineárních kongruencí x a1 (mod n1) x a2 (mod n2) . . . x ar (mod nr) má jedno řešení x modulo n, kde n = n1, n2, …, nr 1.11.2011


40

Příklad Problém Sun-Tsu (Sun Zi) • Vyřešte soustavu kongruencí x 2 (mod 3) x 3 (mod 5) x 2 (mod 7) Řešení: n = 3. 5. 7 = 105 N1 = n/3 = 35, N2 = n/5 = 21 N3 = n/7 = 15 Sestavíme lineární kongruence: 35x 1 (mod 3), 21x 1 (mod 5), 15x 1 (mod 7), které dávají řešení pro x1 = 2, x2 = 1, x3 = 1 x = 2. 35 . 2 + 3 . 21 . 1 + 2 . 15 . 1 = 233 Mod 105, dostáváme jediné řešení x = 233 23 (mod 105) 1.11.2011


41

Zákon kvadratické reciprocity (The Quadratic Reciprocity Law) • Eulerovo kriterium (The Euler Criterion) • Legendrův symbol (The Legendre Symbol)

1.11.2011


42

Kvadratické reziduum • Definice: Nechť p je liché prvočíslo a nsd (a,p) = 1. Má-li kvadratická kongruence x2 a (mod p) řešení x, pak řekneme, že a je kvadratické reziduum čísla p. Jestliže žádné takové x neexistuje, nazývá se a kvadratické nereziduum čísla p. 1.11.2011


43

Příklad kvadratického rezidua pro n=13 Určíme čtverce všech zbytkových tříd (mod 13): 12 122 1 22 112 4 32 102 9 42 9 2 3 52 82 12 62 72 10 Kvadratická rezidua čísla 13 jsou: 1,3,4,9,10,12. Kvadratická nerezidua čísla 13 jsou: 2,5,6,7,8,11. 1.11.2011


44

Eulerovo kriterium Euler’s Criterion Věta: Nechť p je liché prvočíslo a platí nsd(a,p) = 1, pak číslo a je kvadratické reziduum prvočísla p právě tehdy, když a(p-1)/2 1 (mod p)

1.11.2011


45

Legendrův symbol a jeho vlastnosti • Definice: Nechť p je liché prvočíslo a nechť nsd (a, p) = 1. Legendrův symbol (a/p) je definován takto: 1

je-li a kvadratické reziduum p

(a/p) = -1

1.11.2011

je-li a kvadratické nereziduum p Alena Šolcová, FIT CVUT v Praze

46

Příklady • Příklad: Nechť p = 13. Použijeme-li Legendrův symbol, pak mohou být výsledky zaznamenány takto: 1 = (1/13) = (3/13) = (4/13) = (9/13) = = (10/13) = (12/13) -1 = (2/13) = (5/13) = (6/13) = (7/13) = (8/13) = (11/13)

1.11.2011


47

Vlastnosti Legendrova symbolu Nechť p je liché prvočíslo a nechť celá čísla a a b jsou nesoudělná s p. Potom (a) Jestliže a b (mod p), pak (a/p)=(b/p). (b) (a2/p) = 1. (c) (a/p) a(p-1)/2 (mod p). (d) (ab/p) = (a/p)(b/p). (e) (1/p) = 1 a (-1/p) = (-1)(p-1)/2.

Příklad: Existuje nějaké řešení kongruence x2 –46 (mod 17) ? (-46/17) = (-1/17) (46/17) = (-1)8 (12/17) = (3.22/17) = = (3/17) (22/17) = (3/17) 38 812 (-4)2 = -1 … NEEX. 8 254 84 642 132 -1 Nebo jinak: (-46/17) = (5/17) 5 1.11.2011 Alena Šolcová, FIT CVUT v Praze 48

Zákon kvadratické reciprocity Quadratic Reciprocity Law – Theorema aureum Věta: Jsou-li p a q různá lichá čísla, pak (p/q) (q/p) = (-1)(p-1)/2. (q-1)/2

Důsledek: Jsou-li p a q různá lichá čísla, pak (q/p), je-li p 1 (mod 4) nebo q 1 (mod 4) (p/q) = -(q/p), je-li p q 3 (mod 4) 1.11.2011


49

Příklad Uvažujme o Legendrově symbolu (29/53) Protože 29 1 (mod 4) a 53 1 (mod 4), můžeme upravit (29/53) = (53/29) = (24/29) = (2/29) (3/29) (4/29) = (2/29) (3/29). (2/29) = -1, druhý LS invertujeme (3/29) = (29/3) = (2/3) = -1, dále použijeme kongruenci. 29 2 (mod 3) a dostaneme (29/53) = (2/29) (3/29) = (-1)(-1) = 1. 1.11.2011


50

Pokračování • Zákon kvadratické reciprocity dává odpověď na nalezení prvočísel p ≠ 3, pro něž je 3 kvadrtatické reziduum. Protože 3 3 (mod 4) z důsledku Zákona kvadratické reciprocity plyne: (3/p) = (p/3), je-li p 1 (mod 4), nebo -(p/3), je-li p 3 (mod 4). Dále probereme p 1 (mod 3) nebo p 1 (mod 4). Podle věty o vlastnostech LS platí: (p/3)= 1, je-li p 1 (mod 3), nebo -1 , je-li p 2 (mod 3). 1.11.2011


51

Pokračování 2 Odtud plyne (3/p) = 1 právě tehdy, když p 1 (mod 4) a p 1 (mod 3) nebo p 3 (mod 4) a p 2 (mod 3).

1.11.2011


52

Lámejte si hlavu – L11 Najděte všechna řešení kvadratické kongruence x2

196 (mod 1357)

Odpověď zašlete na adresu [email protected] Předmět: JménoPříjmeníČíslo skupiny-L11 1.11.2011


53

Výpočet Velikonoc Gaussův algoritmus Pro období 1900 – 2099 volíme konstanty m = 24 a n = 5. Nechť a, b, c, d, e jsou nejmenší nezáporná čísla, která splňují kongruence a r (mod 19), b r (mod 4), c r (mod 7), d (m + 19a) (mod 30), e (n + 2b + 4c + 6d) (mod 19). Pak pro d + e < 10 připadá velikonoční neděle na březnový den, který výpočteme jako (22 + d + e). 1.11.2011


54

Výpočet Velikonoc 2 • Pro d + e = 35 připadá velikonoční neděle na (d + e – 16) – tý den v dubnu a ve zbývajících případech měsíce dubna na den (d + e – 9). Tento algoritmus má však nejméně dvě výjimky, roky 1954 a 2049, kdy velikonoční neděle nepřipadne na 25. dubna.

1.11.2011


55

Literatura • Křížek, M. , Somer, L., Šolcová, A.: Kouzlo čísel, ed. Galileo, Academia, Praha 2009 • Burton, D. : Elementary Number Theory, Mc Graw Hill, Boston 2007, 6th Edition • Křížek, M. , Luca, F. , Somer, L.: 17 Lectures on Fermat Numbers, From Number Theory to Geometry,Springer, New York 2001 • Šolcová, A, Křížek, M., Mink, G.: Matematik Pierre Fermat, CEFRES, Praha 2002 1.11.2011


56

Čísla speciálních tvarů V další přednášce o teorii čísel se budeme zabývat čísly speciálních tvarů a jejich vlastnostmi. 2. května • Mersennova čísla • Fermatova čísla • Dokonalá čísla (Perfect Numbers) • Spřátelená čísla (Amicable Numbers) • Reprezentace přiroz. čísel jako součet čtverců • Fibonacciova čísla atp. 1.11.2011


57

Program přednášky 

  

    

   

14. 2. - 21. 2. Obecná algebra: grupy, konečné grupy, Cayleyho tabulky, typy grup, permutační, alternující, cyklické, grupy symetrií, normální podgrupy. Homomorfismy. AS (2+4) 28. 2. Konečná tělesa, prvočíselný řád tělesa, okruh a jeho vlastnosti, obor integrity. KK (2) 7. 3. Algebra a algoritmy (algoritmy pro výpočet kořenů polynomů - Newtonova metoda, Lehmerova-Schurova metoda, atd.) AS (4) 14. 3. Vybrané problémy teorie grafů, typy hamiltonovských problémů. Algoritmická teorie grafů. KK (2) 21. 3. Algebraická řešení kombinatorických problémů, Pólyova enumerace. KK (4) 28. 3. Konvexní množiny, konvexní obal, ryze konvexní množina, věta o oddělování konvexních množin, Minkowského věta o projekci. KK (2) 4. 4. Vybrané problémy teorie čísel, kvadratická kongruence, Gaussovy algoritmy. AS (4) 11. 4. Fuzzy matematika (MH 2) 18. 4. Malá Fermatova věta, testování prvočíselnosti, Pépinův test, teorie čísel a geometrie, konstruovatelnost mnohoúhelníků. Rychlé algoritmy: násobení, numerické hledání odmocnin. KK (4) 25. 4. velikonoční pondělí 2. 5. Speciální prvočísla - faktoriální, palindromická, cyklická, Gaussova, Eisensteinova prvočísla. Vlastnosti Fermatových prvočísel, příklady aplikací. AS (2) Konvexní analýza JM (2) 9. 5. Optimalizace MH(2)

1.11.2011


58

Matematika pro informatiku 10

Recommend Documents