Matematyka dyskretna (tryb zaoczny) – cz. II p > 1
Z
p = {
,
1
,
0
,
2 ..., p − }
1
2
a, b ∈ Z
a mod p ∈ Z
a = p
+ 2mod p
p
p
a
a div p
a mod p = a − p p
5−mod2
5
5 − 2
= 5 − 2 ⋅ 2 = 1
2
20 mod 4
20
20 − 4
= 20 − 20 = 0
4
− 5mod3
5
− 5 − 3 −
= 5
− − 3⋅ (− 2) = 1
3
c ⋅ ( a mod p) = c ⋅ a mod c ⋅ p a
a
c ⋅ a
c ⋅ a mod p ⋅
= c ⋅ a − c ⋅ p ⋅
= c ⋅ a − c ⋅ p ⋅
= c ⋅ a mod c ⋅ p p
p
c ⋅ p
2 ⋅ (11mod3)
11
= 2 ⋅ 11− 3⋅
= 2 ⋅ (11− 3⋅3) = 2 ⋅ 2 = 4
3
22
22 mod 6 = 22 − 6 ⋅
= 22 − 6 ⋅3 = 4
6
a, b ∈ Z
p
a \ b 0 1
a + p ⋅ b = ( a + b)mod p 0
0 1 dodawanie
1
1 0
a \ b 0 1
a ⋅ p ⋅ b = ( a ⋅ b)mod p 0
0 0 mno enie
p = 2
1
0 1
p = 4
Z =
4
{ ,1,
0
}
3
,
2
+
∗4 0 1 2 3
4
0 1 2 3
0
0 1 1 3
0 0 0 0 0
1
1 2 3 0
1 0 1 1 3
2
2 3 0 1
2 0 2 0 2
3
3 0 1 2
3 0 3 2 1
( a+ b)mod p =( a mod p)+ mod p ( b
p)
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu 1
Matematyka dyskretna (tryb zaoczny) – cz. II ( a⋅ b)mod p = ( a mod p)∗ mod p ( b
p)
(5+6)mod2=1
(5+ 6)mod2 = (5mod2)+
= +
=
2 (6 mod 2)
1 2 0 1
(11+19)mod4 = 1(1mod4) +
= +
=
4 (19 mod 4)
3 4 3 2
(11∗19)mod4 = (11mod4)∗
= ∗
=
4 (19 mod 4)
3 4 3 1
-- Dzielenie liczb
m, n ∈ Z
( m ≥ n ≥ 0)
k \ m - liczba k jest podzielnikiem liczby m k \ m ⇔ m = ik
( m mod k ≠ 0)
k \ m
(− k)\ m
NWD( m, n) = max{ k : k \ m, k \ }
m NWD( m )
0
, = m
NWD 3
( 0 1
, )
2
30 = 21 ⋅ 31 ⋅ 51 ⋅ 70 ⋅110 ⋅130 ⋅170 ⋅...
NWD( m, n) =
P min m , n
∏∞
i
{ i i}
i 1
=
12 = 21 ⋅ 31 ⋅ 50 ⋅ 70 ⋅110 ⋅...
min{ ,
1 2}
min{ }
1
,
1
min{ ,
1 0}
NWD 3
( 0 1
, 2) = 2
⋅3
⋅3
= 2 ⋅3 = 6
NWD( , mn)
m ≥ n
n ≠ 0
Wspólne dzielniki s takie same jak wspólne dzielniki n, m mod n var a, b : integer; d : integer; a = NWD( m, n) a := m;
b := n;
repeat
( a, b) := ( b, a mod b) r := a mod b;
until ( b = 0)
z := b;
d := a;
b := r;
end;
NWD(6 ,32 )0
a b r = a mod b
63 20
3
20 3
2
Algorytm ten wykonuje si max. 2log
razy.
2 ( m + n)
3
2
1
2
1
0
1
0
NWD( , mn)
2
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu
Matematyka dyskretna (tryb zaoczny) – cz. II var a,b,g : integer
a := m;
b := n;
repeat
q := 20 i r b;
( a, b) := ( b, a − q = b) until ( b = 0); d := 2;
a b +2 b − qb 2− q− b 135 40
3
−120
15
40 13
2
− 30
10
10
9
2
−10
0
5
0
-- Algorytm Euklidesa AE( , mn) d = NWD( m n
. )
a = Sm ⋅ t
n
a = m ; 2′ := n; S := 1; S′ := 0; t := 0; q := a div a′ ;
( ,2 a′)=(2′, a− q∗ a′) ( S, S′) := ( S′, S − q ∗ S′) ( t, t′) := ( t′, t − q − t′) until ( a′ = 0);
d := a;
a 2′ q 2− q+ a′ t t′ t − q∗ t 135 40 3
15
0
1
− 3
1
40 15 2
10
1
− 3
7
0
15 10 1
5
− 3
7
−10
1
10
5
2
0
7
−10
27
− 2
5
0
−10 27
3
−
−
d = 5
s ⋅ m + t ⋅ n = 3⋅135 + (−10)⋅ 40 = 405 − 400 = 5
t = −10
b = 3
f ( n) = O( g( n) je eli istnieje c > 0 o tej własno ci, e f ( n) ≤ c ⋅ g( n) dla dostatecznie du ych warto ci n
g( n) = 1
f ( n) = O( )
1
istnieje pewne c > 0 takie, e f ( n) ≤ c Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu 3
Matematyka dyskretna (tryb zaoczny) – cz. II 1
f ( n) =
c = 1
n
f ( n) = 5 n +1
g( n)
2
= n
c = 1
2
2
− n ≤ 5 n +1 ≤ n
-36
31
36
dla n = 6
--
2
n − 5 n +10 = O( 2
n ) istnieje takie c, e f ( n) 2
≤ c ⋅ n
f ( n)
2
2
2
2
2
= n − 5 n +10 ≤ n + − 5 n + 10 ≤ n + 5 n +10 n a + b ≤ a + b
a ⋅ b = a ⋅ b
2
n ≤ n
2
n ≥ 1 dla n ≥ 1
-- --
1. 1 < ... 4
3
2
3
< n < n < n < n < n < ...
wyka , e dowolne n = O( n) < n = O( 2
n )< n = O( 3
n )
// ka dy wyraz jest < od tego po jego prawej 1
1
2. k ≥ 1;
wyka , e n =
+ k
O n
-- --
Własno ci
1) f ( n) = O( g( n) oraz k = const. = 7 k ⋅ f ( n) = O( g( n) Istnieje takie c, e f ( n) ≤ c ⋅ g( n) k ⋅ f ( n) = k ⋅ f ( n) ≤ c ⋅ k ⋅ g( n) = c ⋅ g( n) 2) f ( n) = O( g( n) , h( n) = O( g( h) f ( n)+ h( n) = O( g( n) f ( n)+ h( n) ≤ f ( n) + h( n) ≤ ( c + c 1 ) ⋅ g ( n)
c
2
f ( n)⋅ h( n) = O( a( n)⋅ b( n) f ( n) = O( g( n) oraz g( n) = O( h( n) f ( n) = O( h( n) f ( n) ≤ c ⋅ g( n) g( n) ≤ c
1⋅ h( n)
f ( n) ≤ c ⋅ c 1 ⋅ h( n) 4
Wy sza Szkoła Komunikacji i Zarz dzania w Poznaniu