ÿþA L G O R Y T M Y I S T R U K T U R Y D A N Y C H
( z a l i c z e n i e s e m e s t r u l e t n i e g o 2 0 0 1 / 2 0 0 2 r o k I - g r u p a A )
O d p o w i e d z i :
Z a d . 1 .
B
C
A
D
F
E
M a c i e r z i n c y d e n c j i :
A B C D E F
A - 1 0 0 0 0
B 1 - 1 0 0 0
C 0 0 - 0 0 0
D 1 0 0 - 1 0
E 0 0 0 1 - 1
F 1 0 1 0 0 -
L i s t a w w e k t o r z e z w a r t o [c i o w a n i e m w e k t o r a :
V a l .
1 A B
2 B A C
0 C
2 D A E
2 E D F
2 F A C
Z a d . 2 .
C
m o c ( T A ) = 2 m o c ( T ) = 2 3 = 8
m o c ( T 1 ) = m o c ( T A ) * m o c ( T B ) * m o c ( T D ) = 8 * 3 * 5 = 1 2 0
m o c ( T 2 ) = m o c ( T 1 ) 5 = 1 2 0 5
Z a d . 3 .
A
B C
D E F G
H J K L M
N a s t p n i k w z Ba A
N
P o u s u n i c i u w z Ba A i r e k o n s t r u k c j i B S T :
K
B C
D E F G
H J N L M
Z a d . 4 .
Ac z e n i e H 1 i H 2
L i s t a :
5 1 9 1 2 7 1 5
1 1 3 2
1 0 4 5
2
3
K o l e j n e f a z y Bc z e n i a d r z e w d w u m i a n o w y c h :
5 1 9
7 1 5
1 0
1 2 3 2
4 5
1 1 2
3
K o p i e c H 1 2 :
5 1 9
1 5
1 0 7
1 2 3 2
4 5
1 1 2
3
Ac z e n i e H 1 2 i H 3
L i s t a i o s t a t e c z n a k o n f i g u r a c j a k o p c a d w u m i a n o w e g o H :
6 1 9
5
1 5
5
1 0 7
1 2 3 2
4 5
1 1 2
3
Z a d . 5 .
M a k s y m a l n a l i c z b a w z Bó w N d ( k ) , k t ó r e m o |n a u m i e [c i n a k p o z i o m a c h
d r z e w a r z d u d , w y n o s i :
-
N ( k ) = = 1 + d + d + . . . + d -
"d
=
M a k s y m a l n a l i c z b a k l u c z y d l a k a |d e g o w z Ba w y n o s i ( d 1 ) .
D l a d r z e w a b i n a r n e g o d = 2 . Z k a |d y m w z Be m m o |e b y z w i z a n y c o n a j w y |e j
1 k l u c z .
S t d z a l e |n o [c i :
L i c z b a p o z i o m ó w M a k s y m a l n a l i c z b a w z Bó w M a k s y m a l n a l i c z b a k l u c z y
1 1 1
2 1 + 2 = 3 3
3 3 + 4 = 7 7
4 7 + 8 = 1 5 1 5
5 1 5 + 1 6 = 3 1 3 1
6 3 1 + 3 2 = 6 3 6 3
L i c z b a p o z i o m ó w o b s a d z o n y c h p r z e z w z By s k o j a r z o n e z 6 3 r e k o r d a m i b a z y
d a n y c h , k t ó r y c h l o k a l i z a c j a z a l e |y o d s k Ba d o w e j r e k o r d u p r z y j t e j j a k o k l u c z , w
d o s k o n a l e w y w a |o n y m d r z e w i e b i n a r n y m w y n o s i k 2 = 6 .
D l a d r z e w a r z d u 5 - t e g o d = 5 . Z k a |d y m w z Be m m o g b y z w i z a n e c o
n a j w y |e j 4 k l u c z e .
S t d z a l e |n o [c i :
L i c z b a p o z i o m ó w M a k s y m a l n a l i c z b a w z Bó w M a k s y m a l n a l i c z b a k l u c z y
1 1 4
2 1 + 5 = 6 2 4
3 6 + 2 5 = 3 1 1 2 4
L i c z b a p o z i o m ó w o b s a d z o n y c h p r z e z w z By s k o j a r z o n e z 6 3 r e k o r d a m i b a z y
d a n y c h , k t ó r y c h l o k a l i z a c j a z a l e |y o d s k Ba d o w e j r e k o r d u p r z y j t e j j a k o k l u c z , w
d o s k o n a l e z r ó w n o w a |o n y m d r z e w i e r z d u 5 - t e g o w y n o s i k 5 = 3 .
S t o s u n e k l i c z b y p o z i o m ó w o b u s t r u k t u r :
k 6
= = 2
k 3
Z a d . 6 .
S t a n p o c z t k o w y :
1 3 5 9 7 8 6 4 2
P o d z i a By :
1 3 5 9 7 8 6 4 2
1 3 5 9 7 8 6 4 2
1 3 5 9 7 8 6 4 2
1 3 5 9 7 8 6 4 2
1 3
S c a l a n i e :
1 3
1 3 5 7 9 6 8 2 4
1 3 5 7 9 2 4 6 8
1 2 3 4 5 6 7 8 9
Z a d . 7 .
S u m a c z s t o [c i d l a w s z y s t k i c h z n a k ó w w y n o s i :
6 4 + 4 + 3 2 + 7 4 + 8 + 2 + 1 6 = 2 0 0
1 - s z y p o d z i a B:
0 - { A , B , C } ( Bc z n a c z s t o [ w z g l d n a = 6 4 + 4 + 3 2 = 1 0 0 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 { D , E , F , G } ( Bc z n a c z s t o [ w z g l d n a = 7 4 + 8 + 2 + 1 6 = 1 0 0 )
2 - g i p o d z i a B:
0 0 - { A } ( c z s t o [ w z g l d n a = 6 4 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
0 1 - { B , C } ( Bc z n a c z s t o [ w z g l d n a = 4 + 3 2 = 3 6 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 0 { D } ( c z s t o [ w z g l d n a = 7 4 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 { E , F , G } ( Bc z n a c z s t o [ w z g l d n a = 8 + 2 + 1 6 = 2 6 )
3 - c i p o d z i a B:
0 1 0 - { B } ( c z s t o [ w z g l d n a = 4 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
0 1 1 - { C } ( c z s t o [ w z g l d n a = 3 2 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 0 { E , F } ( Bc z n a c z s t o [ w z g l d n a = 8 + 2 = 1 0 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 1 - { G } ( c z s t o [ w z g l d n a = 1 6 )
4 - t y p o d z i a B:
1 1 0 0 - { E } ( c z s t o [ w z g l d n a = 8 )
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 0 1 - { F } ( c z s t o [ w z g l d n a = 2 )
O s t a t e c z n a t a b e l a k o d ó w b i n a r n y c h :
x A B C D E F G
k o d 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1
U W A G A : D o p u s z c z a l n e s i n n e r o z w i z a n i a , w y n i k a j c e z a r b i t r a l n y c h d e c y z j i ,
k t ó r e m u z d w ó c h p o d z b i o r ó w p r z y p o r z d k o w a b i t o w a r t o [c i 1 , a k t ó r e m u b i t o
w a r t o [c i 0 ( n i e z m i e n i a t o f a k t u , |e o s t a t e c z n y k o d m u s i b y k o d e m
p r z e d r o s t k o w y m , z a [ d Bu g o [c i c i g ó w b i n a r n y c h p r z y p o r z d k o w a n y c h
p o s z c z e g ó l n y m z n a k o m a l f a b e t u p o w i n n y b y t a k i e , j a k w p o w y |s z e j t a b e l i ) .
Z a d . 8 .
N a l e |y o b l i c z y 5 1 8 m o d 7 .
n = 7 a = 5 k = 1 8 = 1 . 2 4 + 0 . 2 3 + 0 . 2 2 + 1 . 2 1 + 0 . 2 0
K r o k i w s t p n e :
b = 1 k `" 0 x = 5 k 0 `" 1
K o l e j n e i t e r a c j e :
i = 1
x = 5 2 m o d 7 = 2 5 m o d 7 = 4 k 1 = 1 b = 4 . 1 m o d 7 = 4
i = 2
x = 4 2 m o d 7 = 1 6 m o d 7 = 2 k 2 = 0
i = 3
x = 2 2 m o d 7 = 4 m o d 7 = 4 k 3 = 0
i = 4
x = 4 2 m o d 7 = 1 6 m o d 7 = 2 k 4 = 1 b = 2 . 4 m o d 7 = 1
O d p o w i e d z: 5 1 8 m o d 7 = 1
U W A G A : R o z w i z a n i e p r e m i o w a n e 2 - m a p u n k t a m i ( s t o s u j c e t w i e r d z e n i e
F e r m a t a - E u l e r a ) j e s t n a s t p u j c e :
Æ( 7 ) = 6 5 1 8 m o d 7 = 5 3 * Æ( 7 ) m o d 7 = ( 5 Æ( 7 ) ) 3 m o d 7 = 1 3 m o d 7 = 1
Z a d . 9 .
K o n f i g u r a c j a k o p c a b i n a r n e g o o 4 - c h w z Ba c h :
D l a c z t e r e c h r ó |n y c h w a r t o [c i k l u c z y i s t n i e j e 4 ! = 2 4 r ó z n y c h p r z y p o r z d k o w a D
k l u c z y w z Bo m . K o r z e n i e m m o |e b y w y Bc z n i e w z e B o n a j w i k s z e j w a r t o [c i
k l u c z a ( c z y l i w z e B z k l u c z e m 2 4 ) . P o z o s t a j e z a t e m 3 ! = 6 m o |l i w o [c i . J e g o
p r a w y m p o t o m k i e m m o |e b y w z e B z k l u c z e m o w a r t o [c i r ó w n e j k a |d e j z
p o z o s t a By c h t r z e c h m o |l i w y c h . A l e w ó w c z a s u p o r z d k o w a n i e p o z o s t a By c h
d w ó c h w z Bó w w p r a w y m p o d d r z e w i e k o r z e n i a j e d n o z n a c z n i e w y n i k a z
p o r z d k u k o p c o w e g o . W n i o s e k : z 4 - c h w z Bó w o p o d a n y c h w a r t o [c i a c h k l u c z y
m o |n a u t w o r z y t y l k o 3 r ó |n e k o p c e b i n a r n e z o r i e n t o w a n e n a m a k s i m u m :
2 4
2 4
1 3
2 1
7
2 1
7
1 3
2 4
2 1
1 3
7
Z a d . 1 0 .
L i c z b a e l e m e n t ó w Z 1 3 :
| Z 1 3 | = Æ ( 1 3 ) = 1 2
L i c z b a g e n e r a t o r ó w :
Æ ( Æ ( 1 3 ) ) = Æ ( 1 2 ) = Æ ( 2 2 * 3 ) =
1 1 1 2
öøëø1 öø. = 1 2 * * = 4
1 2 ëø1 - ÷øìø - ÷ø
ìø
2 3 2 3
íø øøíø øø
4 1 4 2 4 3 4 4 4 5 4 6
4 3 1 2 9 1 0 1
L i c z b a 4 n i e j e s t g e n e r a t o r e m Z 1 3 .
R e s z t k w a d r a t o w y c h w Z j e s t Æ ( 1 2 ) / 2 = 6 . T r z y e l e m e n t y Q 1 3 j u | s
1 3
z n a n e ( 1 , 3 , 9 ) . D o w y z n a c z e n i a p o z o s t a By c h p o z o s t a j e m e t o d a p r ó b i b Bd ó w
a l b o w y z n a c z e n i e j e d n e g o z 4 - c h g e n e r a t o r ó w i j e g o p a r z y s t y c h p o t g .
S p r a w d zm y , c z y l i c z b a 2 j e s t g e n e r a t o r e m g r u p y m u l t i p l i k a t y w n e j Z * 1 3 .
2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 1 0 2 1 1 2 1 2
2 4 8 3 6 1 2 1 1 9 5 1 0 7 1
L i c z b a 2 j e s t g e n e r a t o r e m Z 1 3 .
A z a t e m z b i ó r r e s z t k w a d r a t o w y c h w Z 1 3 t o Q 1 3 = { 1 , 3 , 4 , 9 , 1 0 , 1 2 } .
A L G O R Y T M Y I S T R U K T U R Y D A N Y C H
( z a l i c z e n i e s e m e s t r u l e t n i e g o 2 0 0 1 / 2 0 0 2 r o k I - g r u p a B )
O d p o w i e d z i :
Z a d . 1 .
B
C
A
D
F
E
M a c i e r z i n c y d e n c j i :
A B C D E F
A - 1 0 0 0 0
B 0 - 1 0 0 0
C 0 0 - 1 0 0
D 1 0 0 - 0 0
E 0 1 0 1 - 1
F 1 0 0 0 0 -
L i s t a w w e k t o r z e z w a r t o [c i o w a n i e m w e k t o r a :
V a l .
1 A B
1 B C
1 C D
1 D A
3 E B D F
1 F A
Z a d . 2 .
m o c ( T A ) = m o c ( T B ) * m o c ( T C ) * m o c ( T D ) = 3 * 3 * 5 = 4 5
m o c ( T 1 ) = 2 m o c ( T A ) = 2 4 5
m o c ( T 2 ) = m o c ( T A ) 5 = 4 5 5
Z a d . 3 .
A
B C
D E F G
H J K L M
N a s t p n i k w z Ba B
N
P o u s u n i c i u w z Ba B i r e k o n s t r u k c j i B S T :
A
J C
D E F G
H K L M
N
Z a d . 4 .
Ac z e n i e H 1 i H 2
L i s t a :
5 1 2
1 9
7 1 5
1 0
4 5 3 2
3 1
K o l e j n e f a z y Bc z e n i a d r z e w d w u m i a n o w y c h :
1 2
1 9
7 1 5
1 0
5
4 5 3 2
3 1
1 9
7 1 5
1 0
1 2
4 5 3 2
3 1
5
K o p i e c H 1 2 :
1 5
1 9
3 2
7
1 0
1 2
1
4 5
5
3
Ac z e n i e H 1 2 i H 3
L i s t a i o s t a t e c z n a k o n f i g u r a c j a k o p c a d w u m i a n o w e g o H :
8
1 5
6
1 9
5
3 2
7
1 0
1 2
1
4 5
5
3
Z a d . 5 .
M a k s y m a l n a l i c z b a w z Bó w N d ( k ) , k t ó r e m o |n a u m i e [c i n a k p o z i o m a c h
d r z e w a r z d u d , w y n o s i :
-
N ( k ) = = 1 + d + d + . . . + d -
"d
=
M a k s y m a l n a l i c z b a k l u c z y d l a k a |d e g o w z Ba w y n o s i ( d 1 ) .
D l a d r z e w a b i n a r n e g o d = 2 . Z k a |d y m w z Be m m o |e b y z w i z a n y c o n a j w y |e j
1 k l u c z .
S t d z a l e |n o [c i :
L i c z b a p o z i o m ó w M a k s y m a l n a l i c z b a w z Bó w M a k s y m a l n a l i c z b a k l u c z y
1 1 1
2 1 + 2 = 3 3
3 3 + 4 = 7 7
4 7 + 8 = 1 5 1 5
5 1 5 + 1 6 = 3 1 3 1
6 3 1 + 3 2 = 6 3 6 3
7 6 3 + 6 4 = 1 2 7 1 2 7
L i c z b a p o z i o m ó w o b s a d z o n y c h p r z e z w z By s k o j a r z o n e z 1 0 0 r e k o r d a m i b a z y
d a n y c h , k t ó r y c h l o k a l i z a c j a z a l e |y o d s k Ba d o w e j r e k o r d u p r z y j t e j j a k o k l u c z , w
d o s k o n a l e w y w a |o n y m d r z e w i e b i n a r n y m w y n o s i k 2 = 7 .
D l a d r z e w a r z d u 3 - t e g o d = 3 . Z k a |d y m w z Be m m o g b y z w i z a n e c o
n a j w y |e j 2 k l u c z e .
S t d z a l e |n o [c i :
L i c z b a p o z i o m ó w M a k s y m a l n a l i c z b a w z Bó w M a k s y m a l n a l i c z b a k l u c z y
1 1 2
2 1 + 3 = 4 8
3 4 + 9 = 1 3 2 6
4 1 3 + 2 7 = 4 0 8 0
5 4 0 + 8 1 = 1 2 1 2 4 2
L i c z b a p o z i o m ó w o b s a d z o n y c h p r z e z w z By s k o j a r z o n e z 1 0 0 r e k o r d a m i b a z y
d a n y c h , k t ó r y c h l o k a l i z a c j a z a l e |y o d s k Ba d o w e j r e k o r d u p r z y j t e j j a k o k l u c z , w
d o s k o n a l e z r ó w n o w a |o n y m d r z e w i e r z d u 3 - e g o w y n o s i k 3 = 5 .
S t o s u n e k l i c z b y p o z i o m ó w o b u s t r u k t u r :
k
7
= = 1 , 4
k 5
Z a d . 6 .
S t a n p o c z t k o w y t a b l i c y A [ ] :
7 7 1 3 1 2 4 7 8
P r z y j t o N M A X = 8 .
T a b l i c a C [ ] p o p i e r w s z e j c z [c i z l i c z a n i a :
2 1 1 1 0 0 3 1
T a b l i c a C [ ] p o d r u g i e j c z [c i z l i c z a n i a ( p r z y r o s t o w e g o ) :
2 3 4 5 5 5 8 9
W s t a w i a n i e d o t a b l i c y w y n i k o w e j B [ ] :
A [ 9 ] = 8
B C
8 2 3 4 5 5 5 8 8
A [ 8 ] = 7
B C
7 8 2 3 4 5 5 5 7 8
A [ 7 ] = 4
B C
4 7 8 2 3 4 4 5 5 7 8
A [ 6 ] = 2
B C
2 4 7 8 2 2 4 4 5 5 7 8
A [ 5 ] = 1
B C
1 2 4 7 8 1 2 4 4 5 5 7 8
A [ 4 ] = 3
B C
1 2 3 4 7 8 1 2 3 4 5 5 7 8
A [ 3 ] = 1
B C
1 1 2 3 4 7 8 0 2 3 4 5 5 7 8
A [ 2 ] = 7
B C
1 1 2 3 4 7 7 8 0 2 3 4 5 5 6 8
A [ 1 ] = 7
B C
1 1 2 3 4 7 7 7 8 0 2 3 4 5 5 5 8
Z a d . 7 .
L i s t a z n a k ó w p o u p o r z d k o w a n i u z g o d n i e z r o s n c c z s t o [c i :
{ F } 3 1
{ D } 2 5
{ C } 1 2
{ G } 1 1
{ A } 1 0
{ B } 8
{ E } 1
p o 1 - y m k r o k u :
{ F } 3 1
{ D } 2 5
{ C } 1 2
{ G } 1 1
{ A } 1 0
{ B , E } 9 { B } Ð! [ . . . 1 ] , { E } Ð! [ . . . 0 ]
p o 2 - i m k r o k u :
{ F } 3 1
{ D } 2 5
{ C } 1 2
{ G } 1 1
{ A , B , E } 1 9 { A } Ð! [ . . . 1 ] , { B } Ð! [ . . . 0 1 ] , { E } Ð! [ . . . 0 0 ]
p o 3 - i m k r o k u :
{ F } 3 1
{ D } 2 5
{ C , G } 2 3 { C } Ð! [ . . . 1 ] , { G } Ð! [ . . . 0 ]
{ A , B , E } 1 9 { A } Ð! [ . . . 1 ] , { B } Ð! [ . . . 0 1 ] , { E } Ð! [ . . . 0 0 ]
p o 4 - y m k r o k u :
{ F } 3 1
{ D } 2 5
{ C , G , A , B , E } 4 2 { C } Ð! [ . . . 1 1 ] , { G } Ð! [ . . . 1 0 ] , { A } Ð! [ . . . 0 1 ] ,
{ B } Ð! [ . . . 0 0 1 ] , { E } Ð! [ . . . 0 0 0 ]
p o 5 - y m k r o k u :
{ F , D } 5 6 { F } Ð! [ . . . 1 ] , { D } Ð! [ . . . 0 ]
{ C , G , A , B , E } 4 2 { C } Ð! [ . . . 1 1 ] , { G } Ð! [ . . . 1 0 ] , { A } Ð! [ . . . 0 1 ] ,
{ B } Ð! [ . . . 0 0 1 ] , { E } Ð! [ . . . 0 0 0 ]
p o o s t a t n i m 6 - y m k r o k u :
{ F } Ð! [ 1 1 ] , { D } Ð! [ 1 0 ] , { C } Ð! [ 0 1 1 ] , { G } Ð! [ 0 1 0 ] ,
{ A } Ð! [ 0 0 1 ] , { B } Ð! [ 0 0 0 1 ] , { E } Ð! [ 0 0 0 0 ]
O s t a t e c z n a t a b e l a k o d ó w b i n a r n y c h :
x A B C D E F G
k o d 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0
U W A G A : D o p u s z c z a l n e s i n n e r o z w i z a n i a , w y n i k a j c e z a r b i t r a l n y c h d e c y z j i ,
k t ó r e m u z d w ó c h p o d z b i o r ó w p r z y p o r z d k o w a b i t o w a r t o [c i 1 , a k t ó r e m u b i t o
w a r t o [c i 0 ( n i e z m i e n i a t o f a k t u , |e o s t a t e c z n y k o d m u s i b y k o d e m
p r z e d r o s t k o w y m , z a [ d Bu g o [c i c i g ó w b i n a r n y c h p r z y p o r z d k o w a n y c h
p o s z c z e g ó l n y m z n a k o m a l f a b e t u p o w i n n y b y t a k i e , j a k w p o w y |s z e j t a b e l i ) .
K r o k i w i o d c e d o u z y s k a n i a o s t a t e c z n e g o k o d u H u f f m a n a m o g b y
p r z e d s t a w i o n e w f o r m i e g r a f i c z n e j i l u s t r u j c e j t w o r z e n i e d r z e w a H u f f m a n a .
Z a d . 8 .
N a l e |y o b l i c z y 5 1 7 m o d 6 .
n = 6 a = 5 k = 1 7 = 1 . 2 4 + 0 . 2 3 + 0 . 2 2 + 0 . 2 1 + 1 . 2 0
K r o k i w s t p n e :
b = 1 k `" 0 x = 5 k 0 = 1 b = 5
K o l e j n e i t e r a c j e :
i = 1
x = 5 2 m o d 6 = 2 5 m o d 6 = 1 k 1 = 0
i = 2
x = 1 2 m o d 6 = 1 m o d 6 = 1 k 2 = 0
i = 3
x = 1 2 m o d 6 = 1 m o d 6 = 1 k 3 = 0
i = 4
x = 1 2 m o d 6 = 1 m o d 6 = 1 k 4 = 1 b = 1 . 5 m o d 6 = 5
O d p o w i e d z: 5 1 7 m o d 6 = 5
U W A G A : R o z w i z a n i e p r e m i o w a n e 2 - m a p u n k t a m i ( s t o s u j c e t w i e r d z e n i e
F e r m a t a - E u l e r a ) j e s t n a s t p u j c e :
Æ( 6 ) = Æ( 2 ) * Æ( 3 ) = 1 * 2 = 2
5 1 7 m o d 7 = 5 8 * Æ( 6 ) + 1 m o d 7 = ( 5 Æ( 6 ) ) 8 * 5 1 m o d 7 = 1 8 * 5 1 m o d 7 = 5
Z a d . 9 .
K a |d y z c z t e r e c h w z Bó w m o |e b y k o r z e n i e m d r z e w a B S T .
J e |e l i k o r z e n i e m j e s t w z e B o n a j w i k s z e j w a r t o [c i k l u c z a , t o j e g o l e w e
p o d d r z e w o z a w i e r a w s z y s t k i e p o z o s t a Be w z By . K o r z e n i e m t e g o p o d d r z e w a
m o |e b y k a |d y z t r z e c h p o z o s t a By c h w z Bó w . W p r z y p a d k u , g d y j e s t t o w z e B o
[r o d k o w e j w a r t o [c i k l u c z a , i s t n i e j e t y l k o j e d n a m o |l i w o [ l o k a l i z a c j i
p o z o s t a By c h w z Bó w ( m u s z b y o d p o w i e d n i o : l e w y m i p r a w y m p o t o m k i e m ) . W
p r z y p a d k u , g d y j e s t t o w z e B o n a j w i k s z e j l u b n a j m n i e j s z e j w a r t o [c i k l u c z a
s p o [r ó d w z Bó w r ó |n y c h o d k o r z e n i a d r z e w a , p o z o s t a j d w i e m o |l i w o [c i
s k o n f i g u r o w a n i a p o z o s t a By c h d w ó c h w z Bó w j a k o p a r y r o d z i c p o t o m e k .
R a z e m : 5 m o |l i w o [c i .
L u s t r z a n y p r z y p a d e k d o t y c z y s y t u a c j i , g d y k o r z e n i e m d r z e w a B S T j e s t w z e B
o n a j m n i e j s z e j w a r t o [c i k l u c z a .
J e |e l i k o r z e n i e m j e s t w z e B o d r u g i e j w k o l e j n o [c i z g o d n e j z u p o r z d k o w a n i e m
d r z e w a B S T w a r t o [c i k l u c z a , t o j e g o l e w e p o d d r z e w o z a w i e r a t y l k o w z e B o
n a j m n i e j s z e j w a r t o [c i k l u c z a , z a [ p r a w y d w a p o z o s t a Be w z By , c o u m o |l i w i a
u t w o r z e n i e t y l k o 2 r ó |n y c h d r z e w B S T .
L u s t r z a n y p r z y p a d e k d o t y c z y s y t u a c j i , g d y k o r z e n i e m d r z e w a B S T j e s t w z e B
o 3 - e j w k o l e j n o [c i w a r t o [c i k l u c z a . K Ba n i a s i r e k u r e n c j a ! ! !
W s u m i e r ó |n y c h m o |l i w y c h d r z e w j e s t : 5 + 5 + 2 + 2 = 1 4 . P o n i |e j p r z e d s t a w i o n o
g r a f i c z n i e i c h k o n f i g u r a c j e .
1 2
1 2
1 2
9
9
6
6
3
1 2 3 9
6 1 2
3
3
3
6
9
9
6
3 3 3
9 6 6
6 1 2 1 2 9
3 9
3
1 2
1 2
1 2
6
9
9
6
6 6
9 1 2
3 3
1 2 9
9 9
3 6
1 2 1 2
6 3
Z a d . 1 0 .
L i c z b a e l e m e n t ó w Z 1 1 :
| Z 1 1 | = Æ ( 1 1 ) = 1 0
L i c z b a g e n e r a t o r ó w :
Æ ( Æ ( 1 1 ) ) = Æ ( 1 0 ) = Æ ( 2 * 5 ) =
1 1 1 4
öøëø1 öø. = 1 0 * * = 4
1 0 ëø1 - ÷øìø - ÷ø
ìø
2 5 2 5
íø øøíø øø
S p r a w d zm y , c z y l i c z b a 2 j e s t g e n e r a t o r e m g r u p y m u l t i p l i k a t y w n e j Z * 1 3 .
2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 1 0
2 4 8 5 1 0 9 7 3 6 1
L i c z b a 2 j e s t g e n e r a t o r e m Z 1 1 .
A z a t e m z b i ó r r e s z t k w a d r a t o w y c h w Z 1 1 t o Q 1 1 = { 1 , 3 , 4 , 5 , 9 } .
Wyszukiwarka
Podobne podstrony:
ZALICZENIE CZERWIEC 2002Przykładowe zadania na zaliczenie matematyki z semestru 1 z rozwiązaniamiTest po 6 klasie czerwiec 2002 sportZaliczenia czerwiec 2014Kolokwium zaliczeniowe sem 1 07 08 rozwiazaniaRozwiązanie Egzaminu potwierdzającego kwalifikacje zawodowe tec hnik mechanik czerwiec 2010Egzamin zawodowy praktyczny technik spedytor czerwiec 2012 (przykładowe rozwiązanie)4 zadania zaliczenia opis rozwiązaniaczerwiec2012 rozwiazania2002 czerwiecwięcej podobnych podstron